Криптографической хэш - функции ( CHF ) представляет собой математический алгоритм , который отображает данные произвольного размера (часто называют «сообщение») в битовый массив фиксированного размера (в «хэш - значение», «хэш», или «дайджеста сообщения») . Это односторонняя функция , то есть функция, которую практически невозможно инвертировать. [1] В идеале, единственный способ найти сообщение, которое производит данный хэш, - это попытаться перебором возможных входных данных, чтобы увидеть, производят ли они совпадение, или использовать радужную таблицу совпадающих хешей. Криптографические хеш-функции - основной инструмент современной криптографии.
Безопасные алгоритмы хеширования | |
---|---|
Концепции | |
хэш-функции · SHA · DSA | |
Основные стандарты | |
SHA-0 · SHA-1 · SHA-2 · SHA-3 | |
Идеальная криптографическая хеш-функция имеет следующие основные свойства:
- он детерминирован , что означает, что одно и то же сообщение всегда приводит к одному и тому же хешу
- быстро вычислить хеш-значение для любого данного сообщения
- невозможно сгенерировать сообщение, которое дает заданное значение хеш-функции (т.е. отменить процесс, который сгенерировал данное значение хеш-функции)
- невозможно найти два разных сообщения с одинаковым значением хеш-функции
- небольшое изменение в сообщении должно изменить хеш-значение настолько сильно, что новое хеш-значение будет казаться некоррелированным со старым хеш-значением ( эффект лавины ) [2]
Криптографические хеш-функции используются во многих приложениях для защиты информации, особенно в цифровых подписях , кодах аутентификации сообщений (MAC) и других формах аутентификации . Их также можно использовать в качестве обычных хэш-функций для индексации данных в хеш-таблицах , для снятия отпечатков пальцев , для обнаружения дублирующихся данных или однозначной идентификации файлов, а также в качестве контрольных сумм для обнаружения случайного повреждения данных. Действительно, в контексте информационной безопасности криптографические хеш-значения иногда называют ( цифровыми ) отпечатками пальцев , контрольными суммами или просто хеш-значениями , хотя все эти термины обозначают более общие функции с довольно разными свойствами и целями. [3]
Характеристики
Большинство криптографических хеш-функций предназначены для принятия на вход строки любой длины и создания хеш-значения фиксированной длины.
Криптографическая хеш-функция должна выдерживать все известные типы криптоаналитических атак . В теоретической криптографии уровень безопасности криптографической хеш-функции определяется с использованием следующих свойств:
- Сопротивление до изображения
- При заданном хэш-значении h должно быть сложно найти какое-либо сообщение m такое, что h = hash ( m ) . Эта концепция связана с односторонней функцией . Функции, у которых отсутствует это свойство, уязвимы для атак по прообразу .
- Сопротивление второго прообраза
- Учитывая вход m 1 , должно быть трудно найти другой вход m 2, такой, что hash ( m 1 ) = hash ( m 2 ) . Это свойство иногда называют слабым сопротивлением столкновению . Функции, у которых отсутствует это свойство, уязвимы для атак второго прообраза .
- Сопротивление столкновению
- Должно быть сложно найти два разных сообщения m 1 и m 2 такие, что hash ( m 1 ) = hash ( m 2 ) . Такая пара называется криптографической хеш-коллизией . Это свойство иногда называют сильным сопротивлением столкновениям . Для этого требуется хэш-значение как минимум в два раза длиннее, чем требуется для сопротивления прообразу; в противном случае столкновения могут быть обнаружены атакой по случаю дня рождения . [4]
Сопротивление столкновениям подразумевает сопротивление второму предварительному изображению, но не подразумевает сопротивление предварительному изображению. [5] Более слабое предположение всегда предпочтительнее в теоретической криптографии, но на практике хеш-функция, которая устойчива только ко второму прообразу, считается небезопасной и поэтому не рекомендуется для реальных приложений.
Неформально эти свойства означают, что злоумышленник не может заменить или изменить входные данные без изменения их дайджеста. Таким образом, если две строки имеют один и тот же дайджест, можно быть уверенным, что они идентичны. Сопротивление второму прообразу не позволяет злоумышленнику создать документ с тем же хешем, что и у документа, который злоумышленник не может контролировать. Устойчивость к коллизиям не позволяет злоумышленнику создать два разных документа с одним и тем же хешем.
Функция, отвечающая этим критериям, может иметь нежелательные свойства. Популярные в настоящее время криптографические хеш-функции уязвимы для атак с увеличением длины : учитывая хэш ( m ) и len ( m ), но не m , выбирая подходящее m ′ , злоумышленник может вычислить хэш ( m ∥ m ′ ) , где ∥ означает конкатенацию . [6] Это свойство можно использовать для взлома простых схем аутентификации, основанных на хэш-функциях. Конструкция HMAC решает эти проблемы.
На практике стойкость к столкновению недостаточна для многих практических применений. В дополнение к сопротивлению столкновениям, злоумышленник не может найти два сообщения с существенно похожими дайджестами; или сделать вывод о какой-либо полезной информации о данных, учитывая только их дайджест. В частности, хеш-функция должна вести себя, насколько это возможно, как случайная функция (часто называемая случайным оракулом в доказательствах безопасности), при этом оставаясь детерминированной и эффективно вычисляемой. Это исключает такие функции, как функция SWIFFT , устойчивость которой к столкновениям может быть строго доказана, если предположить, что определенные задачи на идеальных решетках сложны с вычислительной точки зрения, но как линейная функция не удовлетворяет этим дополнительным свойствам. [7]
Алгоритмы контрольной суммы, такие как CRC32 и другие проверки циклическим избыточным кодом , предназначены для удовлетворения гораздо более слабых требований и обычно не подходят в качестве криптографических хеш-функций. Например, в стандарте шифрования WEP для проверки целостности сообщений использовалась CRC , но была легко обнаружена атака, в которой использовалась линейность контрольной суммы.
Степень сложности
В криптографической практике «сложный» обычно означает «почти наверняка вне досягаемости любого злоумышленника, которому необходимо предотвратить взлом системы до тех пор, пока безопасность системы считается важной». Таким образом, значение термина в некоторой степени зависит от приложения, поскольку усилия, которые злонамеренный агент может вложить в задачу, обычно пропорциональны их ожидаемой выгоде. Однако, поскольку требуемые усилия обычно умножаются на длину дайджеста, даже тысячекратное преимущество в вычислительной мощности можно нейтрализовать, добавив к последнему несколько десятков бит.
Для сообщений, выбранных из ограниченного набора сообщений, например паролей или других коротких сообщений, может оказаться целесообразным инвертировать хэш, пробуя все возможные сообщения в наборе. Поскольку криптографические хеш-функции обычно рассчитаны на быстрое вычисление, были разработаны специальные функции вывода ключей, которые требуют больших вычислительных ресурсов, что затрудняет такие атаки методом перебора .
В некоторых теоретических исследованиях «сложно» имеет конкретный математический смысл, например «не разрешимо за асимптотическое полиномиальное время ». Такие интерпретации сложности важны при изучении доказуемо защищенных криптографических хеш-функций, но обычно не имеют прочной связи с практической безопасностью. Например, алгоритм экспоненциального времени иногда может быть достаточно быстрым, чтобы провести возможную атаку. И наоборот, алгоритм с полиномиальным временем (например, тот, который требует n 20 шагов для n -значных ключей) может быть слишком медленным для любого практического использования.
Иллюстрация
Пример потенциального использования криптографического хэша следующий: Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать это сам, но все же хотел бы убедиться, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш-код и сообщает Бобу значение хеш-функции (сохраняя при этом решение в секрете). Затем, когда Боб сам придумал решение несколько дней спустя, Алиса может доказать, что у нее было решение раньше, открыв его и попросив Боба хэшировать его и проверить, соответствует ли оно хеш-значению, данному ему ранее. (Это пример простой схемы обязательств ; на практике Алиса и Боб часто будут компьютерными программами, и секрет будет сложнее подделать, чем заявленное решение головоломки.)
Приложения
Проверка целостности сообщений и файлов
Важным применением безопасных хэшей является проверка целостности сообщения . Сравнивая дайджесты сообщения (хеш-дайджесты сообщения), вычисленные до и после передачи, можно определить, были ли внесены какие-либо изменения в сообщение или файл .
Хеш-дайджесты MD5 , SHA-1 или SHA-2 иногда публикуются на веб-сайтах или форумах, чтобы обеспечить проверку целостности загруженных файлов [8], включая файлы, полученные с помощью совместного использования файлов, например зеркального копирования . Эта практика устанавливает цепочку доверия до тех пор, пока хэши размещаются на надежном сайте - обычно исходном сайте - аутентифицированном по HTTPS . Использование криптографического хеша и цепочки доверия позволяет обнаруживать злонамеренные изменения в файле. Другие коды обнаружения ошибок, такие как циклические проверки избыточности, предотвращают только незлонамеренные изменения файла, сделанные другими.
Генерация и проверка подписи
Практически все схемы цифровой подписи требуют вычисления криптографического хеша для сообщения. Это позволяет выполнять вычисление подписи для относительно небольшого хэш-дайджеста статического размера. Сообщение считается подлинным, если проверка подписи прошла успешно с учетом подписи и пересчитанного хеш-дайджеста сообщения. Таким образом, свойство целостности сообщения криптографического хэша используется для создания безопасных и эффективных схем цифровой подписи.
Подтверждение пароля
Проверка пароля обычно основана на криптографических хэшах. Хранение всех паролей пользователей в виде открытого текста может привести к серьезному нарушению безопасности, если файл паролей будет скомпрометирован. Один из способов уменьшить эту опасность - хранить только хеш-дайджест каждого пароля. Для аутентификации пользователя пароль, представленный пользователем, хешируется и сравнивается с сохраненным хешем. При хешировании пароля требуется метод сброса пароля; исходные пароли не могут быть пересчитаны из сохраненного хеш-значения.
Стандартные криптографические хеш-функции рассчитаны на быстрое вычисление, и, как следствие, можно с высокой скоростью пробовать угаданные пароли. Обычные графические процессоры могут пробовать миллиарды возможных паролей каждую секунду. Функции хеширования паролей, которые выполняют растягивание ключей, такие как PBKDF2 , scrypt или Argon2, обычно используют повторные вызовы криптографического хеша для увеличения времени (а в некоторых случаях и памяти компьютера), необходимого для выполнения атак грубой силы на сохраненные хеш-дайджесты паролей. Хеш пароля требует использования большого случайного несекретного значения соли, которое может храниться вместе с хешем пароля. Соль рандомизирует вывод хэша пароля, что делает невозможным для злоумышленника хранить таблицы паролей и предварительно вычисленных хеш-значений, с которыми можно сравнивать хеш-дайджест пароля.
Выходные данные хеш-функции пароля также можно использовать в качестве криптографического ключа. Поэтому хэши паролей также известны как функции вывода ключей на основе паролей (PBKDF).
Доказательство работы
Система доказательства работы (или протокол, или функция) - это экономическая мера для предотвращения атак типа «отказ в обслуживании» и других злоупотреблений службами, таких как спам в сети, требуя некоторой работы от запрашивающей службы, что обычно означает время обработки компьютер. Ключевой особенностью этих схем является их асимметрия: работа должна быть умеренно сложной (но выполнимой) со стороны запрашивающей стороны, но легко проверяемой поставщиком услуг. Одна популярная система, используемая в майнинге биткойнов и Hashcash, использует частичную инверсию хэша, чтобы доказать, что работа была выполнена, разблокировать награду за майнинг в биткойнах и в качестве токена доброй воли для отправки электронной почты в Hashcash. Отправитель должен найти сообщение, хеш-значение которого начинается с числа нулевых битов. Средняя работа, которую отправитель должен выполнить, чтобы найти допустимое сообщение, экспоненциально зависит от количества нулевых битов, требуемых в хеш-значении, в то время как получатель может проверить достоверность сообщения, выполнив одну хеш-функцию. Например, в Hashcash отправителю предлагается сгенерировать заголовок, 160-битное хеш-значение SHA-1 которого содержит первые 20 битов как нули. Отправителю в среднем придется 2 19 попыток найти верный заголовок.
Идентификатор файла или данных
Дайджест сообщения также может служить средством надежной идентификации файла; несколько систем управления исходным кодом , включая Git , Mercurial и Monotone , используют sha1sum различных типов контента (содержимое файлов, деревья каталогов, информацию о происхождении и т. д.) для их уникальной идентификации. Хэши используются для идентификации файлов в одноранговых сетях обмена файлами . Например, в ссылке ed2k , MD4 -вариант хэш объединяется с размером файла, обеспечивая достаточную информацию для определения местоположения источников файлов, загрузка файла, и проверки его содержимого. Другой пример - магнитные ссылки . Такие хэши файлов часто являются верхним хешем хеш-списка или хэш-дерева, что дает дополнительные преимущества.
Одно из основных применений хеш-функции - обеспечить быстрый поиск данных в хеш-таблице . Криптографические хеш-функции, являясь хэш-функциями определенного вида, также хорошо подходят для этого приложения.
Однако по сравнению со стандартными хеш-функциями криптографические хеш-функции, как правило, намного дороже в вычислительном отношении. По этой причине они, как правило, используются в контекстах, где пользователям необходимо защитить себя от возможности подделки (создания данных с тем же дайджестом, что и ожидаемые данные) потенциально злонамеренными участниками.
Хеш-функции на основе блочных шифров
Существует несколько методов использования блочного шифра для создания криптографической хеш-функции, в частности, функции одностороннего сжатия .
Эти методы напоминают режимы работы блочного шифра, обычно используемые для шифрования. Многие хорошо известные хэш-функции, включая MD4 , MD5 , SHA-1 и SHA-2 , построены из компонентов, подобных блочному шифрованию, предназначенных для этой цели, с обратной связью, гарантирующей, что результирующая функция не обратима. Финалисты SHA-3 включили функции с компонентами, подобными блочному шифрованию (например, Skein , BLAKE ), хотя окончательно выбранная функция Keccak была построена на криптографической губке .
Стандартный блочный шифр, такой как AES, может использоваться вместо этих пользовательских блочных шифров; это может быть полезно, когда во встроенной системе необходимо реализовать как шифрование, так и хеширование с минимальным размером кода или площадью оборудования. Однако такой подход может иметь издержки с точки зрения эффективности и безопасности. Шифры в хэш-функциях созданы для хеширования: они используют большие ключи и блоки, могут эффективно менять ключи в каждом блоке, и были разработаны и проверены на устойчивость к атакам с использованием связанных ключей . Шифры общего назначения имеют разные цели проектирования. В частности, AES имеет размеры ключей и блоков, которые делают его нетривиальным для генерации длинных хеш-значений; Шифрование AES становится менее эффективным, когда ключ меняет каждый блок; атаки с использованием связанных ключей делают его потенциально менее безопасным для использования в хэш-функции, чем для шифрования.
Дизайн хеш-функции
Строительство Меркле-Дамгарда
Хеш-функция должна иметь возможность обрабатывать сообщение произвольной длины в вывод фиксированной длины. Этого можно достичь, разбив входные данные на серию блоков одинакового размера и последовательно работая с ними, используя функцию одностороннего сжатия . Функция сжатия может быть либо специально разработана для хеширования, либо построена на основе блочного шифра. Хэш-функция, построенная с помощью конструкции Меркла-Дамгарда, так же устойчива к столкновениям, как и ее функция сжатия; любая коллизия для полной хэш-функции может быть прослежена до коллизии в функции сжатия.
Последний обработанный блок также должен быть однозначно дополнен по длине ; это имеет решающее значение для безопасности этой конструкции. Эта конструкция называется конструкцией Меркла – Дамгарда . Наиболее распространенные классические хеш-функции, включая SHA-1 и MD5 , принимают эту форму.
Широкая труба против узкой трубы
Прямое применение конструкции Меркла-Дамгарда, где размер выходных данных хеш-функции равен размеру внутреннего состояния (между каждым этапом сжатия), приводит к узкой конвейерной схеме хеширования. Эта конструкция вызывает множество врожденных недостатков, включая увеличение длины, множественные коллизии, [9] атаки на длинные сообщения, [10] атаки с генерацией и вставкой, [ цитата необходима ], а также не может быть распараллелена. В результате современные функции хеширования построены на широкоэкранном трубные конструкциях , которые имеют больший внутренний размер состояния - которые варьируются от настроек в конструкции Меркла-Damgård [9] к новым конструкциям , таким как строительство губки и строительство HAIFA . [11] Ни один из участников конкурса хэш-функций NIST не использует классическую конструкцию Меркла – Дамгарда. [12]
Между тем, усечение вывода более длинного хэша, например, используемого в SHA-512/256, также предотвращает многие из этих атак. [13]
Использование при построении других криптографических примитивов
Хеш-функции могут использоваться для создания других криптографических примитивов. Чтобы эти другие примитивы были криптографически безопасными, необходимо позаботиться о их правильном построении.
Коды аутентификации сообщений (MAC) (также называемые ключевыми хэш-функциями) часто строятся из хэш-функций. HMAC - это такой MAC.
Так же, как блочные шифры могут использоваться для построения хеш-функций, хеш-функции могут использоваться для построения блочных шифров. Конструкции Luby-Rackoff, использующие хэш-функции, могут быть доказуемо безопасными, если базовая хеш-функция безопасна. Кроме того, многие хеш-функции (включая SHA-1 и SHA-2 ) построены с использованием блочного шифра специального назначения в конструкции Дэвиса-Мейера или другой конструкции. Этот шифр также можно использовать в обычном режиме работы без тех же гарантий безопасности. См. ШАКАЛ , МЕДВЕДЬ и ЛЬВ .
Генераторы псевдослучайных чисел (ГПСЧ) могут быть построены с использованием хэш-функций. Это делается путем объединения (секретного) случайного начального числа со счетчиком и его хеширования.
Некоторые хэш-функции, такие как Skein , Keccak и RadioGatún , выводят поток произвольной длины и могут использоваться в качестве потокового шифра , а потоковые шифры также могут быть построены из хеш-функций дайджеста фиксированной длины. Часто для этого сначала создают криптографически безопасный генератор псевдослучайных чисел, а затем используют его поток случайных байтов в качестве потока ключей . SEAL - это потоковый шифр, который использует SHA-1 для генерации внутренних таблиц, которые затем используются в генераторе потока ключей, более или менее не связанном с алгоритмом хеширования. Не гарантируется, что SEAL будет таким же сильным (или слабым), как SHA-1. Точно так же при расширении ключа потоковых шифров HC-128 и HC-256 интенсивно используется хеш-функция SHA-256 .
Конкатенация
Объединение выходных данных нескольких хэш-функций обеспечивает устойчивость к конфликтам на уровне самого сильного из алгоритмов, включенных в объединенный результат. [ необходима цитата ] Например, более старые версии Transport Layer Security (TLS) и Secure Sockets Layer (SSL) использовали сцепленные суммы MD5 и SHA-1 . [14] [15] Это гарантирует, что метод обнаружения коллизий в одной из хэш-функций не повредит данные, защищенные обеими хеш-функциями. [ необходима цитата ]
Для хэш-функций конструкции Меркла – Дамгарда объединенная функция столь же устойчива к столкновениям, как и ее самый сильный компонент, но не более устойчива к столкновениям. [ необходимая цитата ] Антуан Жу заметил, что 2-коллизии приводят к n -коллизиям: если злоумышленник может найти два сообщения с одним и тем же хешем MD5, то он может найти столько дополнительных сообщений с тем же хешем MD5, сколько пожелает. , без особого труда. [16] Среди этих n сообщений с одинаковым хешем MD5, вероятно, будет конфликт в SHA-1. Дополнительная работа, необходимая для поиска коллизии SHA-1 (помимо экспоненциального поиска дня рождения), требует только полиномиального времени . [17] [18]
Криптографические хеш-алгоритмы
Существует множество криптографических алгоритмов хеширования; в этом разделе перечислены несколько алгоритмов, на которые довольно часто ссылаются. Более обширный список можно найти на странице, содержащей сравнение криптографических хеш-функций .
MD5
MD5 был разработан Рональдом Ривестом в 1991 году для замены более ранней хэш-функции MD4 и был указан в 1992 году как RFC 1321. Коллизии с MD5 могут быть вычислены за секунды, что делает алгоритм непригодным для большинства случаев использования, когда требуется криптографический хеш. MD5 производит дайджест из 128 бит (16 байт).
SHA-1
SHA-1 был разработан в рамках проекта Capstone правительства США . Первоначальная спецификация алгоритма - теперь обычно называемая SHA-0 - была опубликована в 1993 году под названием Secure Hash Standard, FIPS PUB 180, агентством государственных стандартов США NIST (Национальным институтом стандартов и технологий). Он был отозван Агентством национальной безопасности вскоре после публикации и заменен пересмотренной версией, опубликованной в 1995 году в FIPS PUB 180-1 и обычно обозначаемой как SHA-1. Конфликты с полным алгоритмом SHA-1 могут быть произведены с использованием разбитой атаки, и хеш-функция должна считаться неработающей. SHA-1 создает хеш-дайджест из 160 бит (20 байтов).
Документы могут ссылаться на SHA-1 как на «SHA», даже если это может конфликтовать с другими алгоритмами безопасного хеширования, такими как SHA-0, SHA-2 и SHA-3.
РИПЭМД-160
RIPEMD (Дайджест сообщений оценки примитивов целостности RACE) - это семейство криптографических хэш-функций, разработанных в Лёвене, Бельгия, Хансом Доббертином, Антуном Босселером и Бартом Пренелем в исследовательской группе COSIC в Католическом университете Лёвена и впервые опубликованных в 1996 году. основан на принципах проектирования, используемых в MD4, и по своим характеристикам аналогичен более популярному SHA-1. Однако РИПЭМД-160 не сломался. Как следует из названия, RIPEMD-160 создает хеш-дайджест размером 160 бит (20 байт).
Водоворот
Whirlpool - это криптографическая хеш-функция, разработанная Винсентом Райменом и Пауло SLM Баррето, которые впервые описали ее в 2000 году. Whirlpool основан на существенно модифицированной версии Advanced Encryption Standard (AES). Whirlpool производит хеш-дайджест размером 512 бит (64 байта).
SHA-2
SHA-2 (Secure Hash Algorithm 2) - это набор криптографических хеш-функций, разработанный Агентством национальной безопасности США (NSA), впервые опубликованный в 2001 году. Они построены с использованием структуры Меркла-Дамгарда из функции одностороннего сжатия сам построен с использованием структуры Дэвиса-Мейера из (секретного) специализированного блочного шифра.
SHA-2 в основном состоит из двух алгоритмов хеширования: SHA-256 и SHA-512. SHA-224 - это вариант SHA-256 с разными начальными значениями и усеченным выводом. SHA-384 и менее известные SHA-512/224 и SHA-512/256 являются вариантами SHA-512. SHA-512 более безопасен, чем SHA-256, и обычно быстрее, чем SHA-256 на 64-битных машинах, таких как AMD64 .
Размер вывода в битах задается расширением имени «SHA», поэтому SHA-224 имеет размер вывода 224 бита (28 байтов); SHA-256, 32 байта; SHA-384, 48 байт; и SHA-512, 64 байта.
SHA-3
SHA-3 (алгоритм безопасного хеширования 3) был выпущен NIST 5 августа 2015 года. SHA-3 является подмножеством более широкого семейства криптографических примитивов Keccak. Алгоритм Keccak - это работа Гвидо Бертони, Джоан Дэмен, Майкла Петерса и Жиля Ван Аше. Keccak основан на конструкции губки, которая также может использоваться для создания других криптографических примитивов, таких как потоковый шифр. SHA-3 обеспечивает те же размеры вывода, что и SHA-2: 224, 256, 384 и 512 бит.
Настраиваемые выходные размеры также могут быть получены с помощью функций SHAKE-128 и SHAKE-256. Здесь расширения имени -128 и -256 означают степень защиты функции, а не размер вывода в битах.
BLAKE2
BLAKE2, улучшенная версия BLAKE, была анонсирована 21 декабря 2012 года. Она была создана Жан-Филиппом Аумассоном, Сэмюэлем Невесом, Зуко Уилкокс-О'Хирном и Кристианом Виннерлейном с целью замены широко используемых, но сломанных MD5 и Алгоритмы SHA-1. При запуске на 64-битных архитектурах x64 и ARM BLAKE2b работает быстрее, чем SHA-3, SHA-2, SHA-1 и MD5. Хотя BLAKE и BLAKE2 не были стандартизированы, как SHA-3, BLAKE2 использовался во многих протоколах, включая хэш пароля Argon2 , для обеспечения высокой эффективности, которую он предлагает на современных процессорах. Поскольку BLAKE был кандидатом на SHA-3, BLAKE и BLAKE2 оба предлагают те же размеры вывода, что и SHA-3, включая настраиваемый размер вывода.
BLAKE3
BLAKE3, улучшенная версия BLAKE2, была анонсирована 9 января 2020 года. Ее создали Джек О'Коннор, Жан-Филипп Аумассон, Сэмюэл Невес и Зуко Уилкокс-О'Хирн. BLAKE3 - это единый алгоритм, в отличие от BLAKE и BLAKE2, которые представляют собой семейства алгоритмов с несколькими вариантами. Функция сжатия BLAKE3 в значительной степени основана на функции сжатия BLAKE2, с самой большой разницей в том, что количество раундов сокращено с 10 до 7. Внутренне BLAKE3 является деревом Меркла и поддерживает более высокие степени параллелизма, чем BLAKE2.
Атаки на криптографические хеш-алгоритмы
Существует длинный список криптографических хеш-функций, но многие из них оказались уязвимыми и не должны использоваться. Например, NIST выбрал 51 хэш-функцию [19] в качестве кандидатов для первого раунда конкурса хеш-кодов SHA-3, из которых 10 были признаны неработающими, а 16 показали значительные недостатки и поэтому не прошли в следующий раунд; дополнительную информацию можно найти в основной статье о соревнованиях по хэш-функциям NIST .
Даже если хеш-функция никогда не нарушалась, успешная атака на ослабленный вариант может подорвать доверие экспертов. Например, в августе 2004 г. коллизии были обнаружены в нескольких популярных тогда хэш-функциях, включая MD5. [20] Эти недостатки поставили под сомнение безопасность более сильных алгоритмов, полученных на основе слабых хэш-функций, в частности, SHA-1 (усиленная версия SHA-0), RIPEMD-128 и RIPEMD-160 (обе усиленные версии RIPEMD ). [21]
12 августа 2004 г. Жу, Каррибо, Лемюэль и Джалби объявили о конфликте полного алгоритма SHA-0. [16] Joux et al. сделал это, используя обобщение атаки Шабо и Жу. Они обнаружили, что коллизия имела сложность 2 51 и потребовала около 80 000 процессорных часов на суперкомпьютере с 256 процессорами Itanium 2 , что эквивалентно 13 дням постоянного использования суперкомпьютера. [ необходима цитата ]
В феврале 2005 года сообщалось об атаке на SHA-1, в ходе которой обнаруживалась коллизия примерно в 2 69 хэш-операциях, а не в 2 80, ожидаемых для 160-битной хеш-функции. В августе 2005 года сообщалось об очередной атаке на SHA-1, в результате которой были обнаружены коллизии в 2 63 операциях. Известны и другие теоретические недостатки SHA-1: [22] [23], а в феврале 2017 года Google объявил о конфликте в SHA-1. [24] Исследователи безопасности рекомендуют, чтобы новые приложения могли избежать этих проблем, используя более поздние члены семейства SHA, такие как SHA-2 , или такие методы, как рандомизированное хеширование [1], которые не требуют устойчивости к коллизиям.
Успешная практическая атака взломала MD5, который использовался в сертификатах для безопасности транспортного уровня в 2008 году. [25]
Многие криптографические хэши основаны на конструкции Меркла-Дамгарда . Все криптографические хэши, которые напрямую используют полный вывод конструкции Меркла-Дамгарда, уязвимы для атак с увеличением длины . Это делает алгоритмы хеширования MD5, SHA-1, RIPEMD-160, Whirlpool и SHA-256 / SHA-512 уязвимыми для этой конкретной атаки. SHA-3, BLAKE2, BLAKE3 и усеченные варианты SHA-2 не уязвимы для этого типа атак. [ необходима цитата ]
Атаки на хешированные пароли
Обычно хеши используются для хранения данных аутентификации пароля. Вместо того, чтобы хранить открытый текст паролей пользователей, система контролируемого доступа хранит хэш каждого пароля пользователя в файле или базе данных. Когда кто-то запрашивает доступ, отправленный им пароль хешируется и сравнивается с сохраненным значением. Если база данных украдена (что случается слишком часто [26] ), вор будет иметь только хеш-значения, но не пароли.
Однако большинство людей выбирают пароли предсказуемым образом. Списки общих паролей широко распространены, и многие пароли достаточно короткие, чтобы можно было проверить все возможные комбинации при использовании быстрых хешей. [27] Использование криптографической соли предотвращает некоторые атаки, такие как создание файлов с предварительно вычисленными хэш-значениями, например, радужных таблиц . Но поиски порядка 100 миллиардов тестов в секунду возможны с помощью высокопроизводительных графических процессоров , что делает возможными прямые атаки даже с использованием соли. [28] [29] Соединенные Штаты Национального институт стандартов и технологии рекомендует хранить пароли , используя специальные хэш называемых ключевых функций деривации (KDFs) , которые были созданы для медленного поиска грубой силы. [30] : 5.1.1.2 Медленные хэши включают pbkdf2 , bcrypt , scrypt , argon2 , Balloon и некоторые недавние режимы шифрования Unix . Для KSF, которые выполняют несколько хешей для замедления выполнения, NIST рекомендует количество итераций 10 000 или больше. [30] : 5.1.1.2
Смотрите также
- Эффект лавины
- Сравнение криптографических хеш-функций
- Криптографическая гибкость
- CRYPTREC
- HMAC
- Хеш-цепочка
- Атака удлинения длины
- MD5CRK
- Код аутентификации сообщения
- НЕССИ
- Список слов PGP
- Случайный оракул
- Безопасность криптографических хеш-функций
- SHA-3
- Универсальная односторонняя хеш-функция
Рекомендации
Цитаты
- ^ a b Шай Халеви и Хьюго Кравчик, рандомизированное хеширование и цифровые подписи
- ^ Аль-Кувари, Саиф; Давенпорт, Джеймс Х .; Брэдфорд, Рассел Дж. (2011). «Криптографические хеш-функции: последние тенденции дизайна и концепции безопасности» . Архив криптологии ePrint . Отчет 2011/565.
- ^ Шнайер, Брюс . «Криптоанализ MD5 и SHA: время для нового стандарта» . Компьютерный мир . Архивировано из оригинала на 2016-03-16 . Проверено 20 апреля 2016 .
Односторонние хеш-функции - это не просто алгоритмы шифрования, но и рабочие лошадки современной криптографии.
- ^ Katz & Lindell 2014 , стр. 155-157, 190, 232.
- ^ Rogaway & Shrimpton 2004 , в гл. 5. Последствия.
- ^ Дуонг, тайский; Риццо, Джулиано. «Уязвимость Flickr, связанная с подделкой подписи API» .
- ^ Любашевский и др. 2008 , с. 54–72.
- ^ Перрин, Чад (5 декабря 2007 г.). «Используйте хэши MD5 для проверки загрузки программного обеспечения» . TechRepublic . Проверено 2 марта 2013 года .
- ^ а б Удачи, Стефан (2004). «Принципы проектирования итерированных хеш-функций» . Архив криптологии ePrint . Отчет 2004/253.
- ^ Kelsey & Шнайер 2005 , стр. 474-490.
- ^ Бихам, Эли; Дункельман, Орр (24 августа 2006 г.). Платформа для итеративных хеш-функций - HAIFA . Второй семинар NIST по криптографическому хешированию. Архив криптологии ePrint . Отчет 2007/278.
- ^ Нанди и Пол 2010 .
- ^ Добрауниг, Кристоф; Эйхлседер, Мария; Мендель, Флориан (февраль 2015 г.). Оценка безопасности SHA-224, SHA-512/224 и SHA-512/256 (PDF) (отчет).
- ^ Mendel et al. , п. 145: Конкатенация ... часто используется разработчиками для «хеджирования ставок» на хеш-функции. Объединитель формы MD5
- ^ Харник и др. 2005 , стр. 99: объединение хэш-функций, как предлагается в TLS ... гарантированно будет таким же безопасным, как и кандидат, который остается безопасным.
- ^ а б Жу 2004 .
- ^ Финни, Хэл (20 августа 2004 г.). «Еще проблемы с хеш-функциями» . Список рассылки криптографии . Архивировано из оригинала 9 апреля 2016 года . Проверено 25 мая 2016 года .
- ^ Хох и Шамир 2008 , стр. 616-630.
- ^ Эндрю Regenscheid, Рэй Perlner, Шу-Джен Чан, Джон Келси, Mridul Нанди, Саурадюти Пол, Доклад о состоянии первого раунда конкурса SHA-3 Cryptographic Hash Algorithm
- ^ XiaoyunWang, Dengguo Feng, Xuejia Lai, Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 и RIPEMD
- ^ Альшайхлы Имад Фахри; Алахмад Мохаммад Abdulateef (2015), «криптографическая хэш - функций», Справочник по исследованиям в области обнаружения угроз и контрмер в сетевой безопасности , IGI Global, С. 80-94,. DOI : 10,4018 / 978-1-4666-6583-5.ch006 , ISBN 978-1-4666-6583-5
- ^ Сяоюнь Ван, Ицюнь Лиза Инь и Хунбо Ю, Обнаружение коллизий в полном SHA-1
- ^ Брюс Шнайер, Криптоанализ SHA-1 (обобщает результаты Ванга и др. И их значение)
- ^ Фокс-Брюстер, Томас. «Google просто« разбил »старый криптографический алгоритм - вот почему это важно для веб-безопасности» . Forbes . Проверено 24 февраля 2017 .
- ↑ Александр Сотиров, Марк Стивенс, Джейкоб Аппельбаум, Арьен Ленстра, Дэвид Мольнар, Даг Арне Освик, Бенн де Вегер, MD5, который сегодня считается вредоносным: Создание поддельного сертификата CA , по состоянию на 29 марта 2009 г.
- ^ Суинхо, Дэн (17 апреля 2020 г.). «15 крупнейших утечек данных в 21 веке» . Журнал CSO.
- ^ Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов» . Ars Technica . Проверено 23 ноября 2020 .
- ^ Клэберн, Томас (14 февраля 2019 г.). «Использовать 8-значный пароль Windows NTLM? Не надо. Каждый из них может быть взломан менее чем за 2,5 часа» . www.theregister.co.uk . Проверено 26 ноября 2020 .
- ^ «Потрясающая производительность графического процессора» . Improsec. 3 января 2020 г.
- ^ а б Грасси Пол А. (июнь 2017 г.). SP 800-63B-3 - Рекомендации по цифровой идентификации, аутентификации и управлению жизненным циклом . NIST. DOI : 10.6028 / NIST.SP.800-63b .
Источники
- Харник, Дэнни; Килиан, Джо; Наор, Мони; Рейнгольд, Омер; Розен, Алон (2005). «О надежных комбайнерах для забвения передачи и других примитивов». Достижения в криптологии - EUROCRYPT 2005 . Конспект лекций по информатике. 3494 . С. 96–113. DOI : 10.1007 / 11426639_6 . ISBN 978-3-540-25910-7. ISSN 0302-9743 .
- Hoch, Джонатан Дж .; Шамир, Ади (2008). «О силе объединителя конкатенированных хешей, когда все хеш-функции слабые». Автоматы, языки и программирование . Конспект лекций по информатике. 5126 . С. 616–630. DOI : 10.1007 / 978-3-540-70583-3_50 . ISBN 978-3-540-70582-6. ISSN 0302-9743 .
- Жу, Антуан (2004). «Мультиколлизии в итерированных хэш-функциях. Применение к каскадным конструкциям». Достижения в криптологии - CRYPTO 2004 . Конспект лекций по информатике. 3152 . Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 306–316. DOI : 10.1007 / 978-3-540-28628-8_19 . ISBN 978-3-540-22668-0. ISSN 0302-9743 .
- Келси, Джон; Шнайер, Брюс (2005). «Вторые прообразы на n-битных хеш-функциях гораздо меньше, чем 2 n работы» . Достижения в криптологии - EUROCRYPT 2005 . Конспект лекций по информатике. 3494 . С. 474–490. DOI : 10.1007 / 11426639_28 . ISBN 978-3-540-25910-7. ISSN 0302-9743 .
- Кац, Джонатан; Линделл, Иегуда (2014). Введение в современную криптографию (2-е изд.). CRC Press. ISBN 978-1-4665-7026-9.
- Любашевский, Вадим; Микчанчо, Даниэле; Пайкерт, Крис; Розен, Алон (2008). «SWIFFT: скромное предложение по хешированию БПФ». Быстрое программное шифрование . Конспект лекций по информатике. 5086 . С. 54–72. DOI : 10.1007 / 978-3-540-71039-4_4 . ISBN 978-3-540-71038-7. ISSN 0302-9743 .
- Мендель, Флориан; Рехбергер, Кристиан; Шлеффер, Мартин (2009). «MD5 слабее, чем слабый: атаки на составные комбайнеры». Достижения в криптологии - ASIACRYPT 2009 . Конспект лекций по информатике. 5912 . С. 144–161. DOI : 10.1007 / 978-3-642-10366-7_9 . ISBN 978-3-642-10365-0. ISSN 0302-9743 .
- Нанди, Мридул; Пол, Сурадьюти (2010). «Ускорение широкой трубы: безопасное и быстрое хеширование» . Прогресс в криптологии - INDOCRYPT 2010 . Конспект лекций по информатике. 6498 . С. 144–162. DOI : 10.1007 / 978-3-642-17401-8_12 . ISBN 978-3-642-17400-1. ISSN 0302-9743 .
- Rogaway, P .; Шримптон, Т. (2004). «Основы криптографической хеш-функции: определения, значения и разделения для сопротивления прообразу, сопротивления второму прообразу и сопротивления столкновениям». CiteSeerX 10.1.1.3.6200 .
Внешние ссылки
- Паар, Кристоф; Пельцль, янв (2009). «11: Хеш-функции» . Понимание криптографии, Учебник для студентов и практиков . Springer . Архивировано из оригинала на 2012-12-08. (сопутствующий веб-сайт содержит онлайн-курс криптографии, охватывающий хеш-функции)
- «Веб-сайт с хеш-функцией ECRYPT» .
- Булдас, А. (2011). «Серия мини-лекций о криптографических хеш-функциях» . Архивировано из оригинала на 2012-12-06.