Криптографическая хеш-функция ( CHF ) — это хэш-алгоритм ( преобразование произвольной двоичной строки в двоичную строку с фиксированным размером битов), который имеет специальные свойства, желательные для криптографического приложения: [1]
Криптографические хэш-функции используются во многих приложениях информационной безопасности , особенно в цифровых подписях , кодах аутентификации сообщений (MAC) и других формах аутентификации . Их также можно использовать как обычные хэш-функции для индексации данных в хеш-таблицах , для снятия отпечатков пальцев , для обнаружения дубликатов данных или уникальной идентификации файлов, а также в качестве контрольных сумм для обнаружения случайного повреждения данных. Действительно, в контексте информационной безопасности криптографические хеш-значения иногда называют ( цифровыми ) отпечатками пальцев , контрольными суммами или просто хэш-значениями , хотя все эти термины обозначают более общие функции с довольно разными свойствами и целями. [2]
Некриптографические хэш-функции используются в хеш-таблицах , и для обнаружения случайных ошибок их конструкция часто не обеспечивает защиты от преднамеренной атаки. Например, атака типа «отказ в обслуживании» на хеш-таблицы возможна, если коллизии легко обнаружить, как в случае с функциями линейного циклического избыточного кода (CRC). [3]
Большинство криптографических хэш-функций предназначены для приема строки любой длины в качестве входных данных и создания хэш-значения фиксированной длины.
Криптографическая хэш-функция должна быть способна противостоять всем известным типам криптоаналитических атак . В теоретической криптографии уровень безопасности криптографической хеш-функции определяется с использованием следующих свойств:
Устойчивость к столкновению подразумевает сопротивление второму прообразу, но не подразумевает сопротивление прообразу. [5] В теоретической криптографии всегда предпочтительнее более слабое предположение, но на практике хеш-функция, устойчивая только к второму прообразу, считается небезопасной и поэтому не рекомендуется для реальных приложений.
Неформально эти свойства означают, что злоумышленник не может заменить или изменить входные данные без изменения их дайджеста. Таким образом, если две строки имеют одинаковый дайджест, можно быть вполне уверенным, что они идентичны. Второе сопротивление прообразу не позволяет злоумышленнику создать документ с тем же хешем, что и документ, который злоумышленник не может контролировать. Устойчивость к коллизиям не позволяет злоумышленнику создать два разных документа с одним и тем же хешем.
Функция, отвечающая этим критериям, все равно может иметь нежелательные свойства. В настоящее время популярные криптографические хеш-функции уязвимы для атак с расширением длины : учитывая hash( m ) и len( m ), но не m , выбрав подходящее m ′ , злоумышленник может вычислить хэш ( 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 объединяется с размером файла, предоставляя достаточную информацию для поиска источников файла, загрузки файла и проверки его содержимого. Магнитные ссылки — еще один пример. Такие хэши файлов часто являются верхним хешем списка хэшей или дерева хэшей , что дает дополнительные преимущества.
Одним из основных применений хэш -функции является обеспечение быстрого поиска данных в хеш-таблице . Криптографические хэш-функции, будучи хеш-функциями определенного типа, также хорошо подходят для этого приложения.
Однако по сравнению со стандартными хеш-функциями криптографические хэш-функции, как правило, требуют гораздо больших вычислительных затрат. По этой причине они, как правило, используются в контекстах, где пользователям необходимо защитить себя от возможности подделки (создания данных с тем же дайджестом, что и ожидаемые данные) потенциально злонамеренными участниками. [ нужна цитата ]
Хранилище с адресацией по содержимому (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 ) создаются с использованием специального блочного шифра в конструкции Дэвиса-Мейера или другой конструкции. Этот шифр также можно использовать в обычном режиме работы без таких же гарантий безопасности; например, ШАКАЛ , МЕДВЕДЬ и ЛЕВ .
Генераторы псевдослучайных чисел (PRNG) могут быть построены с использованием хэш-функций. Это делается путем объединения (секретного) случайного начального числа со счетчиком и его хеширования.
Некоторые хеш-функции, такие как 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 . [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 основан на существенно модифицированной версии расширенного стандарта шифрования (AES). Whirlpool создает хеш-дайджест длиной 512 бит (64 байта).
SHA-2 (алгоритм безопасного хеширования 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 (алгоритм безопасного хеширования 3) был выпущен NIST 5 августа 2015 года. SHA-3 является подмножеством более широкого семейства криптографических примитивов 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 во многом основана на функции сжатия BLAKE2, с самым большим отличием в том, что количество раундов уменьшено с 10 до 7. Внутренне BLAKE3 представляет собой дерево Меркла и поддерживает более высокие степени параллелизма, чем BLAKE2.
Существует длинный список криптографических хэш-функций, но многие из них оказались уязвимыми и не должны использоваться. Например, NIST выбрал 51 хэш-функцию [20] в качестве кандидатов на первый раунд конкурса хэшей 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, которая обнаружила коллизию примерно в 269 операциях хеширования, а не в 280 , ожидаемых для 160-битной хэш-функции. В августе 2005 г. сообщалось о еще одной атаке на SHA-1, в ходе которой были выявлены столкновения в 263 операциях . Известны и другие теоретические недостатки 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
Односторонние хеш-функции — это не просто алгоритмы шифрования, а рабочие лошадки современной криптографии.
