Криптографическая хэш-функция ( CHF ) — это алгоритм хэширования ( отображение произвольной двоичной строки в двоичную строку с фиксированным размером бит), обладающий особыми свойствами, желательными для криптографического применения: [1]
Криптографические хэш-функции имеют множество приложений информационной безопасности , в частности, в цифровых подписях , кодах аутентификации сообщений (MAC) и других формах аутентификации . Их также можно использовать как обычные хэш-функции , для индексации данных в хэш-таблицах , для снятия отпечатков пальцев , для обнаружения дубликатов данных или уникальной идентификации файлов, а также в качестве контрольных сумм для обнаружения случайного повреждения данных. Действительно, в контексте информационной безопасности криптографические хэш-значения иногда называют ( цифровыми ) отпечатками пальцев , контрольными суммами или просто хэш-значениями , хотя все эти термины обозначают более общие функции с довольно разными свойствами и целями. [2]
Некриптографические хэш-функции используются в хэш-таблицах и для обнаружения случайных ошибок; их конструкции часто не обеспечивают сопротивления преднамеренной атаке. Например, атака типа «отказ в обслуживании» на хэш-таблицы возможна, если коллизии легко найти, как в случае функций линейного циклического избыточного кода (CRC). [3]
Большинство криптографических хеш-функций предназначены для приема в качестве входных данных строки любой длины и создания хеш-значения фиксированной длины.
Криптографическая хэш-функция должна быть способна противостоять всем известным типам криптоаналитических атак . В теоретической криптографии уровень безопасности криптографической хэш-функции определяется с использованием следующих свойств:
Устойчивость к коллизиям подразумевает устойчивость ко второму прообразу, но не подразумевает устойчивость к прообразу. [5] Более слабое предположение всегда предпочтительнее в теоретической криптографии, но на практике хэш-функция, устойчивая только ко второму прообразу, считается небезопасной и поэтому не рекомендуется для реальных приложений.
Неформально эти свойства означают, что злонамеренный противник не может заменить или изменить входные данные, не изменив их дайджест. Таким образом, если две строки имеют одинаковый дайджест, можно быть уверенным, что они идентичны. Устойчивость ко второму прообразу не позволяет злоумышленнику создать документ с тем же хешем, что и документ, который злоумышленник не может контролировать. Устойчивость к коллизиям не позволяет злоумышленнику создать два разных документа с тем же хешем.
Функция, соответствующая этим критериям, может по-прежнему иметь нежелательные свойства. В настоящее время популярные криптографические хэш-функции уязвимы для атак с расширением длины : имея hash( m ) и len( m ), но не m , выбрав подходящий m ′ , злоумышленник может вычислить hash( m ∥ m ′ ) , где ∥ обозначает конкатенацию . [6] Это свойство можно использовать для взлома наивных схем аутентификации, основанных на хэш-функциях. Конструкция HMAC обходит эти проблемы.
На практике, устойчивость к коллизиям недостаточна для многих практических применений. В дополнение к устойчивости к коллизиям, для противника должно быть невозможным найти два сообщения с существенно похожими дайджестами; или вывести какую-либо полезную информацию о данных, имея только их дайджест. В частности, хеш-функция должна вести себя как можно больше как случайная функция (часто называемая случайным оракулом в доказательствах безопасности), оставаясь при этом детерминированной и эффективно вычисляемой. Это исключает функции, подобные функции SWIFFT , которая может быть строго доказана как устойчивая к коллизиям, предполагая, что определенные проблемы на идеальных решетках являются вычислительно сложными, но, как линейная функция, не удовлетворяет этим дополнительным свойствам. [7]
Алгоритмы контрольной суммы, такие как CRC32 и другие циклические проверки избыточности , разработаны для удовлетворения гораздо более слабых требований и, как правило, не подходят в качестве криптографических хэш-функций. Например, CRC использовался для целостности сообщений в стандарте шифрования WEP , но была легко обнаружена атака, которая использовала линейность контрольной суммы.
В криптографической практике «сложный» обычно означает «почти наверняка вне досягаемости любого противника, которому необходимо помешать взломать систему до тех пор, пока безопасность системы считается важной». Поэтому значение термина в некоторой степени зависит от приложения, поскольку усилия, которые злоумышленник может приложить для выполнения задачи, обычно пропорциональны его ожидаемому выигрышу. Однако, поскольку необходимые усилия обычно умножаются с длиной дайджеста, даже тысячекратное преимущество в вычислительной мощности может быть нейтрализовано добавлением дюжины бит к последнему.
Для сообщений, выбранных из ограниченного набора сообщений, например паролей или других коротких сообщений, может быть целесообразно инвертировать хэш, перебирая все возможные сообщения в наборе. Поскольку криптографические хэш-функции обычно предназначены для быстрого вычисления, были разработаны специальные функции вывода ключей , требующие больших вычислительных ресурсов, что делает такие атаки методом перебора более сложными.
В некоторых теоретических анализах «сложный» имеет определенное математическое значение, например, «неразрешимый за асимптотическое полиномиальное время ». Такие интерпретации сложности важны при изучении доказуемо безопасных криптографических хеш-функций , но обычно не имеют прочной связи с практической безопасностью. Например, алгоритм с экспоненциальным временем иногда может быть достаточно быстрым, чтобы осуществить осуществимую атаку. И наоборот, алгоритм с полиномиальным временем (например, требующий n 20 шагов для n -значных ключей) может быть слишком медленным для любого практического использования.
Иллюстрация потенциального использования криптографического хеша выглядит следующим образом: Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать сам, но при этом хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу значение хеша (сохраняя решение в секрете). Затем, когда Боб сам придумывает решение несколько дней спустя, Алиса может доказать, что у нее было решение раньше, раскрыв его и попросив Боба хешировать его и проверить, что оно соответствует значению хеша, данному ему ранее. (Это пример простой схемы обязательств ; на практике Алиса и Боб часто будут компьютерными программами, и секрет будет чем-то менее легко поддельным, чем заявленное решение головоломки.)
Важным применением безопасных хэшей является проверка целостности сообщений . Сравнение дайджестов сообщений (хэш-дайджестов сообщения), рассчитанных до и после передачи, может определить, были ли внесены какие-либо изменения в сообщение или файл .
Хеш-дайджесты MD5 , SHA-1 или SHA-2 иногда публикуются на веб-сайтах или форумах для проверки целостности загруженных файлов, [8] включая файлы, извлеченные с помощью обмена файлами, например, зеркалирования . Эта практика устанавливает цепочку доверия , пока хеши публикуются на доверенном сайте — обычно на исходном сайте — с аутентификацией HTTPS . Использование криптографического хеша и цепочки доверия обнаруживает вредоносные изменения в файле. Некриптографические коды обнаружения ошибок, такие как циклические проверки избыточности, предотвращают только невредоносные изменения файла, поскольку преднамеренную подделку можно легко создать с коллизионным значением кода.
Почти все схемы цифровой подписи требуют вычисления криптографического хеша над сообщением. Это позволяет выполнять вычисление подписи на относительно небольшом, статически размерном хеш-дайджесте. Сообщение считается подлинным, если проверка подписи проходит успешно, учитывая подпись и пересчитанный хеш-дайджест над сообщением. Таким образом, свойство целостности сообщения криптографического хеша используется для создания безопасных и эффективных схем цифровой подписи.
Проверка пароля обычно основана на криптографических хэшах. Хранение всех паролей пользователей в виде открытого текста может привести к серьезному нарушению безопасности, если файл паролей будет скомпрометирован. Один из способов уменьшить эту опасность — хранить только хэш-дайджест каждого пароля. Для аутентификации пользователя пароль, представленный пользователем, хэшируется и сравнивается с сохраненным хэшем. При выполнении хэширования пароля требуется метод сброса пароля; исходные пароли не могут быть пересчитаны из сохраненного значения хэша.
Однако использование стандартных криптографических хэш-функций, таких как ряд SHA, больше не считается безопасным для хранения паролей. [9] : 5.1.1.2 Эти алгоритмы разработаны для быстрого вычисления, поэтому, если хэшированные значения скомпрометированы, можно пробовать угадывать пароли с высокой скоростью. Обычные графические процессоры могут пробовать миллиарды возможных паролей каждую секунду. Функции хэширования паролей, которые выполняют растяжение ключа , такие как PBKDF2 , scrypt или Argon2 , обычно используют повторные вызовы криптографического хеша для увеличения времени (и в некоторых случаях памяти компьютера), необходимого для выполнения атак методом перебора на сохраненные хэш-дайджесты паролей. Подробнее см. в § Атаки на хэшированные пароли.
Хэш пароля также требует использования большого случайного, несекретного значения соли , которое может храниться вместе с хешем пароля. Соль хэшируется с паролем, изменяя сопоставление хеша пароля для каждого пароля, тем самым делая невозможным для злоумышленника хранить таблицы предварительно вычисленных значений хеша, с которыми можно сравнивать хеш-дайджест пароля, или параллельно тестировать большое количество украденных значений хеша.
Система доказательства работы (или протокол, или функция) — это экономическая мера для предотвращения атак типа «отказ в обслуживании» и других злоупотреблений услугами, таких как спам в сети, требующая от запрашивающей стороны выполнения некоторой работы, обычно означающей время обработки компьютером. Ключевой особенностью этих схем является их асимметрия: работа должна быть умеренно сложной (но выполнимой) на стороне запрашивающей стороны, но легко проверяемой для поставщика услуг. Одна популярная система, используемая в майнинге биткойнов и Hashcash , использует частичные инверсии хеша для доказательства того, что работа была выполнена, для разблокировки вознаграждения за майнинг в биткойнах и в качестве токена доброй воли для отправки электронного письма в Hashcash. Отправителю необходимо найти сообщение, хеш-значение которого начинается с нескольких нулевых битов. Средняя работа, которую необходимо выполнить отправителю для поиска допустимого сообщения, экспоненциально зависит от количества нулевых битов, требуемых в хеш-значении, в то время как получатель может проверить допустимость сообщения, выполнив одну хеш-функцию. Например, в Hashcash отправителю предлагается сгенерировать заголовок, 160-битное значение хэша SHA-1 которого имеет первые 20 бит как нули. Отправителю в среднем придется попробовать 2 19 раз, чтобы найти допустимый заголовок.
Дайджест сообщения также может служить средством надежной идентификации файла; несколько систем управления исходным кодом , включая Git , Mercurial и Monotone , используют sha1sum различных типов контента (контента файла, деревьев каталогов, информации о предках и т. д.) для их уникальной идентификации. Хэши используются для идентификации файлов в одноранговых файлообменных сетях. Например, в ссылке ed2k хэш -вариант MD4 объединяется с размером файла, предоставляя достаточную информацию для поиска источников файла, загрузки файла и проверки его содержимого. Magnet-ссылки являются еще одним примером. Такие хэши файлов часто являются верхним хешем списка хэшей или хэш-дерева , что обеспечивает дополнительные преимущества.
Одно из основных применений хэш-функции — быстрый поиск данных в хэш-таблице . Будучи хэш-функциями особого рода, криптографические хэш-функции также хорошо подходят для этого применения.
Однако, по сравнению со стандартными хэш-функциями, криптографические хэш-функции, как правило, намного более дороги в вычислительном отношении. По этой причине они, как правило, используются в контекстах, где пользователям необходимо защитить себя от возможности подделки (создания данных с тем же дайджестом, что и ожидаемые данные) потенциально злонамеренными участниками. [ необходима цитата ]
Хранилище с адресацией по содержимому (CAS), также называемое хранилищем с адресацией по содержимому или хранилищем с фиксированным содержимым, — это способ хранения информации, позволяющий извлекать ее на основе ее содержимого, а не ее имени или местоположения. Оно использовалось для высокоскоростного хранения и извлечения фиксированного содержимого, например документов, хранящихся в соответствии с государственными нормами [ требуется цитата ] . Хранилище с адресацией по содержимому похоже на память с адресацией по содержимому .
Системы CAS работают, пропуская содержимое файла через криптографическую хэш-функцию для генерации уникального ключа, «адреса содержимого». Каталог файловой системы хранит эти адреса и указатель на физическое хранилище содержимого. Поскольку попытка сохранить тот же файл сгенерирует тот же ключ, системы CAS гарантируют, что файлы внутри них являются уникальными, а поскольку изменение файла приведет к созданию нового ключа, системы CAS гарантируют, что файл не изменился.
CAS стал значимым рынком в 2000-х годах, особенно после введения в 2002 году в США Закона Сарбейнса-Оксли , который требовал хранения огромного количества документов в течение длительного времени и извлечения их лишь изредка. Постоянно растущая производительность традиционных файловых систем и новых программных систем подорвали ценность устаревших систем CAS, которые стали все более редкими примерно после 2018 года [ необходима цитата ] . Тем не менее, принципы адресуемости контента продолжают представлять большой интерес для компьютерных ученых и составляют ядро многочисленных новых технологий, таких как одноранговый обмен файлами , криптовалюты и распределенные вычисления .Существует несколько методов использования блочного шифра для построения криптографической хеш-функции, в частности односторонней функции сжатия .
Методы напоминают режимы работы блочного шифра, обычно используемые для шифрования. Многие известные хеш-функции, включая MD4 , MD5 , SHA-1 и SHA-2 , построены из компонентов, подобных блочному шифру, разработанных для этой цели, с обратной связью, гарантирующей, что результирующая функция необратима. Финалисты SHA-3 включали функции с компонентами, подобными блочному шифру (например, Skein , BLAKE ), хотя окончательно выбранная функция Keccak была построена на криптографической губке .
Вместо этих пользовательских блочных шифров можно использовать стандартный блочный шифр, такой как AES ; это может быть полезно, когда встроенной системе необходимо реализовать как шифрование, так и хеширование с минимальным размером кода или аппаратной областью. Однако такой подход может иметь издержки в плане эффективности и безопасности. Шифры в хеш-функциях созданы для хеширования: они используют большие ключи и блоки, могут эффективно менять ключи в каждом блоке и были разработаны и проверены на устойчивость к атакам со связанными ключами . Универсальные шифры, как правило, имеют другие цели проектирования. В частности, AES имеет размеры ключей и блоков, которые делают его нетривиальным для использования для генерации длинных значений хеш-функции; шифрование AES становится менее эффективным, когда ключ изменяет каждый блок; а атаки со связанными ключами делают его потенциально менее безопасным для использования в хеш-функции, чем для шифрования.
Хэш-функция должна быть способна преобразовывать сообщение произвольной длины в выходное сообщение фиксированной длины. Этого можно добиться, разбив входные данные на ряд блоков одинакового размера и последовательно обрабатывая их с помощью односторонней функции сжатия . Функция сжатия может быть специально разработана для хэширования или построена на основе блочного шифра. Хэш-функция, построенная с помощью конструкции Меркла–Дамгарда, так же устойчива к коллизиям, как и ее функция сжатия; любую коллизию для полной хэш-функции можно отследить до коллизии в функции сжатия.
Последний обработанный блок также должен быть однозначно дополнен длиной ; это имеет решающее значение для безопасности этой конструкции. Эта конструкция называется конструкцией Меркла–Дамгарда . Большинство распространенных классических хэш-функций, включая SHA-1 и MD5 , принимают эту форму.
Прямое применение конструкции Меркла–Дамгарда, где размер выходного хэша равен внутреннему размеру состояния (между каждым шагом сжатия), приводит к узкому конвейерному дизайну хэша. Этот дизайн вызывает множество присущих ему недостатков, включая удлинение длины , мультиколлизии, [10] атаки на длинные сообщения, [11] атаки «генерировать и вставить», [ необходима ссылка ] и также не может быть распараллелен. В результате современные хэш-функции построены на конструкциях с широким конвейером , которые имеют больший внутренний размер состояния – которые варьируются от ухищрений конструкции Меркла–Дамгарда [10] до новых конструкций, таких как конструкция губки и конструкция HAIFA . [12] Ни один из участников конкурса хэш-функций NIST не использует классическую конструкцию Меркла–Дамгарда. [13]
Между тем, усечение выходных данных более длинного хеша, например, используемого в SHA-512/256, также позволяет отразить многие из этих атак. [14]
Хэш-функции могут использоваться для построения других криптографических примитивов . Чтобы эти примитивы были криптографически безопасными, необходимо позаботиться об их правильном построении.
Коды аутентификации сообщений (MAC) (также называемые ключевыми хэш-функциями) часто строятся из хэш-функций. HMAC — это такой MAC.
Так же, как блочные шифры могут использоваться для построения хэш-функций, хэш-функции могут использоваться для построения блочных шифров. Конструкции Луби-Ракоффа с использованием хэш-функций могут быть доказуемо безопасными, если базовая хэш-функция безопасна. Кроме того, многие хэш-функции (включая SHA-1 и SHA-2 ) построены с использованием специального блочного шифра в конструкции Дэвиса-Майера или другой конструкции. Этот шифр также может использоваться в обычном режиме работы, без тех же гарантий безопасности; например, SHACAL , BEAR и LION .
Генераторы псевдослучайных чисел (ГПСЧ) могут быть построены с использованием хэш-функций. Это делается путем объединения (секретного) случайного начального числа со счетчиком и его хэширования.
Некоторые хэш-функции, такие как Skein , Keccak и RadioGatún , выводят произвольно длинный поток и могут использоваться как потоковый шифр , а потоковые шифры также могут быть построены из хэш-функций дайджеста фиксированной длины. Часто это делается путем первого построения криптографически безопасного генератора псевдослучайных чисел , а затем использования его потока случайных байтов в качестве keystream . SEAL — это потоковый шифр, который использует SHA-1 для генерации внутренних таблиц, которые затем используются в генераторе keystream более или менее независимо от алгоритма хэширования. SEAL не гарантирует, что он будет таким же сильным (или слабым), как SHA-1. Аналогично, расширение ключа потоковых шифров HC-128 и HC-256 интенсивно использует хэш-функцию SHA-256 .
Объединение выходных данных из нескольких хэш-функций обеспечивает устойчивость к коллизиям, такую же хорошую, как и самый сильный из алгоритмов, включенных в объединенный результат. [ требуется ссылка ] Например, старые версии Transport Layer Security (TLS) и Secure Sockets Layer (SSL) использовали объединенные суммы MD5 и SHA-1 . [15] [16] Это гарантирует, что метод поиска коллизий в одной из хэш-функций не нарушит данные, защищенные обеими хэш-функциями. [ требуется ссылка ]
Для хеш-функций построения Меркла–Дамгарда конкатенированная функция столь же устойчива к коллизиям, как и ее самый сильный компонент, но не более устойчива к коллизиям. [ требуется ссылка ] Антуан Жу заметил, что 2-коллизии приводят к n -коллизиям: если злоумышленнику возможно найти два сообщения с одинаковым хешем MD5, то он может найти столько дополнительных сообщений с тем же хешем MD5, сколько пожелает, без больших трудностей. [17] Среди этих n сообщений с одинаковым хешем MD5, скорее всего, будет коллизия в SHA-1. Дополнительная работа, необходимая для поиска коллизии SHA-1 (помимо экспоненциального поиска по дням рождения), требует только полиномиального времени . [18] [19]
Существует множество криптографических хэш-алгоритмов; в этом разделе перечислены несколько алгоритмов, которые упоминаются относительно часто. Более обширный список можно найти на странице, содержащей сравнение криптографических хэш-функций .
MD5 был разработан Рональдом Ривестом в 1991 году для замены более ранней хеш-функции MD4 и был определен в 1992 году как RFC 1321. Коллизии с MD5 могут быть вычислены в течение нескольких секунд, что делает алгоритм непригодным для большинства случаев использования, где требуется криптографический хеш. MD5 создает дайджест из 128 бит (16 байт).
SHA-1 был разработан в рамках проекта правительства США Capstone . Первоначальная спецификация алгоритма, которая теперь обычно называется SHA-0, была опубликована в 1993 году под названием Secure Hash Standard, FIPS PUB 180, агентством по стандартам правительства США NIST (Национальный институт стандартов и технологий). Она была отозвана АНБ вскоре после публикации и заменена пересмотренной версией, опубликованной в 1995 году в FIPS PUB 180-1 и обычно обозначаемой как SHA-1. Коллизии против полного алгоритма SHA-1 могут быть получены с помощью атаки Shattered , и хэш-функция должна считаться сломанной. SHA-1 создает хэш-дайджест размером 160 бит (20 байт).
В документах SHA-1 может называться просто «SHA», даже если это может конфликтовать с другими алгоритмами безопасного хэширования, такими как SHA-0, SHA-2 и SHA-3.
RIPEMD (RACE Integrity Primitives Evaluation Message Digest) — это семейство криптографических хэш-функций, разработанных в Лёвене, Бельгия, Гансом Доббертином, Антоном Босселаерсом и Бартом Пренелем в исследовательской группе COSIC в Лёвенском католическом университете и впервые опубликованных в 1996 году. RIPEMD был основан на принципах проектирования, используемых в MD4, и по производительности аналогичен более популярному SHA-1. Однако RIPEMD-160 не был взломан. Как следует из названия, RIPEMD-160 создает хэш-дайджест размером 160 бит (20 байт).
Whirlpool — это криптографическая хеш-функция, разработанная Винсентом Рейменом и Пауло СЛМ Баррето, которые впервые описали ее в 2000 году. Whirlpool основана на существенно измененной версии Advanced Encryption Standard (AES). Whirlpool создает хеш-дайджест размером 512 бит (64 байта).
SHA-2 (Secure Hash Algorithm 2) — это набор криптографических хеш-функций, разработанных Агентством национальной безопасности США (АНБ), впервые опубликованных в 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 (Secure Hash Algorithm 3) был выпущен NIST 5 августа 2015 года. SHA-3 является подмножеством более широкого семейства криптографических примитивов Keccak. Алгоритм Keccak является работой Гвидо Бертони, Джоан Дэмен, Майкла Питерса и Жиля Ван Аша. Keccak основан на конструкции губки, которая также может использоваться для построения других криптографических примитивов, таких как потоковый шифр. SHA-3 обеспечивает те же выходные размеры, что и SHA-2: 224, 256, 384 и 512 бит.
Настраиваемые выходные размеры также могут быть получены с помощью функций SHAKE-128 и SHAKE-256. Здесь расширения -128 и -256 к названию подразумевают уровень безопасности функции, а не выходной размер в битах.
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, улучшенная версия BLAKE2, была анонсирована 9 января 2020 года. Она была создана Джеком О'Коннором, Жаном-Филиппом Омассоном, Сэмюэлем Невесом и Зуко Уилкокс-О'Хирном. BLAKE3 — это единый алгоритм, в отличие от BLAKE и BLAKE2, которые являются семействами алгоритмов с несколькими вариантами. Функция сжатия BLAKE3 тесно связана с функцией BLAKE2s, причем самое большое отличие заключается в том, что количество раундов сокращено с 10 до 7. Внутренне BLAKE3 представляет собой дерево Меркла и поддерживает более высокие степени параллелизма, чем BLAKE2.
Существует длинный список криптографических хэш-функций, но многие из них оказались уязвимыми и не должны использоваться. Например, NIST выбрал 51 хэш-функцию [20] в качестве кандидатов для 1-го раунда конкурса хэшей SHA-3, из которых 10 были признаны сломанными, а 16 показали существенные слабости и поэтому не прошли в следующий раунд; более подробную информацию можно найти в основной статье о конкурсах хэш-функций NIST .
Даже если хеш-функция никогда не была взломана, успешная атака на ослабленный вариант может подорвать доверие экспертов. Например, в августе 2004 года были обнаружены коллизии в нескольких популярных тогда хеш-функциях, включая MD5. [21] Эти слабости поставили под вопрос безопасность более сильных алгоритмов, полученных из слабых хеш-функций, в частности, SHA-1 (усиленная версия SHA-0), RIPEMD-128 и RIPEMD-160 (обе усиленные версии RIPEMD). [22]
12 августа 2004 года Жу, Каррибо, Лемюэль и Жальби объявили о коллизии для полного алгоритма SHA-0. [17] Жу и др. добились этого, используя обобщение атаки Шабо и Жу. Они обнаружили, что коллизия имела сложность 2 51 и потребовала около 80 000 часов работы ЦП на суперкомпьютере с 256 процессорами Itanium 2 , что эквивалентно 13 дням постоянного использования суперкомпьютера. [ требуется цитата ]
В феврале 2005 года сообщалось об атаке на SHA-1, которая нашла бы коллизию примерно за 2,69 операций хеширования, а не за 2,80 , ожидаемых для 160-битной хеш-функции. В августе 2005 года сообщалось о другой атаке на SHA-1, которая нашла бы коллизии за 2,63 операций . Были известны и другие теоретические слабости SHA-1, [23] [24] , а в феврале 2017 года Google объявила о коллизии в SHA-1. [25] Исследователи безопасности рекомендуют, чтобы новые приложения могли избегать этих проблем, используя более поздние члены семейства SHA, такие как SHA-2 , или используя такие методы, как рандомизированное хеширование [26], которые не требуют устойчивости к коллизиям.
Успешная практическая атака взломала MD5 (используемый в сертификатах для безопасности транспортного уровня ) в 2008 году. [27]
Многие криптографические хэши основаны на конструкции Меркла–Дамгарда . Все криптографические хэши, которые напрямую используют полный вывод конструкции Меркла–Дамгарда, уязвимы для атак расширения длины . Это делает алгоритмы хэширования MD5, SHA-1, RIPEMD-160, Whirlpool и SHA-256 / SHA-512 уязвимыми для этой конкретной атаки. SHA-3, BLAKE2, BLAKE3 и усеченные варианты SHA-2 не уязвимы для этого типа атак. [ необходима цитата ]
Вместо того, чтобы хранить простые пароли пользователей, системы с контролируемым доступом часто хранят хэш каждого пароля пользователя в файле или базе данных. Когда кто-то запрашивает доступ, пароль, который он отправляет, хэшируется и сравнивается с сохраненным значением. Если база данных будет украдена (что случается слишком часто [28] ), у вора будут только хэш-значения, а не пароли.
Пароли все еще могут быть извлечены злоумышленником из хэшей, потому что большинство людей выбирают пароли предсказуемыми способами. Списки распространенных паролей широко распространены, и многие пароли достаточно короткие, чтобы даже все возможные комбинации могли быть проверены, если вычисление хэша не займет слишком много времени. [29]
Использование криптографической соли предотвращает некоторые атаки, такие как создание файлов предвычисленных значений хэша, например, радужных таблиц . Но поиск порядка 100 миллиардов тестов в секунду возможен с помощью высокопроизводительных графических процессоров , что делает возможными прямые атаки даже с солью. [30] [31] Национальный институт стандартов и технологий США рекомендует хранить пароли с использованием специальных хэшей, называемых функциями вывода ключей (KDF), которые были созданы для замедления поиска методом перебора. [9] : 5.1.1.2 Медленные хэши включают pbkdf2 , bcrypt , scrypt , argon2 , Balloon и некоторые недавние режимы Unix crypt . Для KDF, которые выполняют несколько хэшей для замедления выполнения, NIST рекомендует количество итераций 10 000 или более. [9] : 5.1.1.2
Гораздо больше, чем алгоритмы шифрования, односторонние хэш-функции являются рабочими лошадками современной криптографии.
