Из Википедии, бесплатной энциклопедии
  (Перенаправлено из дайджеста сообщений )
Перейти к навигации Перейти к поиску
Криптографическая хеш-функция (в частности, SHA-1 ) в действии. Небольшое изменение во вводе (в слове «сверх») резко меняет вывод (дайджест). Это так называемый лавинный эффект .

Криптографической хэш - функции ( CHF ) представляет собой математический алгоритм , который отображает данные произвольного размера (часто называют «сообщение») в битовый массив фиксированного размера (в «хэш - значение», «хэш», или «дайджеста сообщения») . Это односторонняя функция , то есть функция, которую практически невозможно инвертировать. [1] В идеале, единственный способ найти сообщение, которое производит данный хэш, - это попытаться перебором возможных входных данных, чтобы увидеть, производят ли они совпадение, или использовать радужную таблицу совпадающих хешей. Криптографические хеш-функции - основной инструмент современной криптографии.

Идеальная криптографическая хеш-функция имеет следующие основные свойства:

  • он детерминирован , что означает, что одно и то же сообщение всегда приводит к одному и тому же хешу
  • быстро вычислить хеш-значение для любого данного сообщения
  • невозможно сгенерировать сообщение, которое дает заданное значение хеш-функции (т.е. отменить процесс, который сгенерировал данное значение хеш-функции)
  • невозможно найти два разных сообщения с одинаковым значением хеш-функции
  • небольшое изменение в сообщении должно изменить хеш-значение настолько сильно, что новое хеш-значение будет казаться некоррелированным со старым хеш-значением ( эффект лавины ) [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 , злоумышленник может вычислить хэш ( mm ) , где ∥ означает конкатенацию . [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] атаки с генерацией и вставкой, [ цитата необходима ], а также не может быть распараллелена. В результате современные хэш-функции строятся на конструкциях с широкими трубами, которые имеют больший размер внутреннего состояния - от доработок конструкции Меркла-Дамгарда [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.

RIPEMD-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] Соединенные Штаты Национальный институт стандартов и технологий рекомендует хранить пароли , используя специальные хэши называемые ключевые функции деривации(KDF), которые были созданы для замедления поиска методом грубой силы. [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
  • Универсальная односторонняя хеш-функция

Ссылки [ править ]

Цитаты [ править ]

  1. ^ a b Шай Халеви и Хьюго Кравчик, рандомизированное хеширование и цифровые подписи
  2. ^ Аль-Кувари, Саиф; Давенпорт, Джеймс Х .; Брэдфорд, Рассел Дж. (2011). «Криптографические хеш-функции: последние тенденции дизайна и концепции безопасности» . Cryptology ePrint Archive . Отчет 2011/565.
  3. ^ Шнайер, Брюс . «Криптоанализ MD5 и SHA: время для нового стандарта» . Компьютерный мир . Архивировано из оригинала на 2016-03-16 . Проверено 20 апреля 2016 . Односторонние хеш-функции - это не просто алгоритмы шифрования, но и рабочие лошадки современной криптографии.
  4. ^ Katz & Lindell 2014 , стр. 155-157, 190, 232.
  5. ^ Rogaway & Shrimpton 2004 , в гл. 5. Последствия.
  6. ^ Дуонг, тайский; Риццо, Джулиано. «Уязвимость Flickr, связанная с подделкой подписи API» .
  7. ^ Любашевский и др. 2008 , с. 54–72.
  8. Перрин, Чад (5 декабря 2007 г.). «Используйте хэши MD5 для проверки загрузки программного обеспечения» . TechRepublic . Проверено 2 марта 2013 года .
  9. ^ a b Удача, Стефан (2004). «Принципы проектирования итерированных хеш-функций» . Cryptology ePrint Archive . Отчет 2004/253.
  10. ^ Kelsey & Шнайер 2005 , стр. 474-490.
  11. ^ Бихам, Эли; Дункельман, Орр (24 августа 2006 г.). Платформа для итеративных хеш-функций - HAIFA . Второй семинар NIST по криптографическому хешированию. Cryptology ePrint Archive . Отчет 2007/278.
  12. ^ Нанди и Пол 2010 .
  13. ^ Добрауниг, Кристоф; Эйхлседер, Мария; Мендель, Флориан (февраль 2015 г.). Оценка безопасности SHA-224, SHA-512/224 и SHA-512/256 (PDF) (отчет).
  14. ^ Mendel et al. , п. 145: Конкатенация ... часто используется разработчиками для «хеджирования ставок» на хеш-функции. Объединитель формы MD5
  15. ^ Харник и др. 2005 , стр. 99: объединение хэш-функций, как предлагается в TLS ... гарантированно будет таким же безопасным, как и кандидат, который остается безопасным.
  16. ^ а б Жу 2004 .
  17. Рианна Финни, Хэл (20 августа 2004 г.). «Еще проблемы с хеш-функциями» . Список рассылки криптографии . Архивировано из оригинала 9 апреля 2016 года . Проверено 25 мая, 2016 .
  18. ^ Хох и Шамир 2008 , стр. 616-630.
  19. ^ Эндрю Regenscheid, Рэй Perlner, Шу-Джен Чан, Джон Келси, Mridul Нанди, Саурадюти Пол, Доклад о состоянии первого раунда конкурса SHA-3 Cryptographic Hash Algorithm
  20. ^ XiaoyunWang, Dengguo Feng, Xuejia Lai, Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 и RIPEMD
  21. ^ Alshaikhli, Имад Фахри; Алахмад Мохаммад Abdulateef (2015), «криптографическая хэш - функций», Справочник по исследованиям в области обнаружения угроз и контрмер в сетевой безопасности , IGI Global, С. 80-94,. DOI : 10,4018 / 978-1-4666-6583-5.ch006 , ISBN 978-1-4666-6583-5
  22. ^ Сяоюнь Ван, Ицюнь Лиза Инь и Хунбо Ю, Обнаружение коллизий в полном SHA-1
  23. ^ Брюс Шнайер, Криптоанализ SHA-1 (обобщает результаты Ванга и др. И их значение)
  24. ^ Фокс-Брюстер, Томас. «Google просто« разбил »старый криптографический алгоритм - вот почему это важно для веб-безопасности» . Forbes . Проверено 24 февраля 2017 .
  25. Александр Сотиров, Марк Стивенс, Джейкоб Аппельбаум, Арьен Ленстра, Дэвид Мольнар, Даг Арне Освик, Бенн де Вегер, MD5, который сегодня считается вредоносным: Создание поддельного сертификата CA , по состоянию на 29 марта 2009 г.
  26. ^ Swinhoe, Dan (17 апреля 2020). «15 крупнейших утечек данных в 21 веке» . Журнал CSO.
  27. ^ Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов» . Ars Technica . Проверено 23 ноября 2020 .
  28. ^ Claburn, Томас (14 февраля 2019). «Использовать 8-значный пароль Windows NTLM? Не надо. Каждый из них может быть взломан менее чем за 2,5 часа» . www.theregister.co.uk . Проверено 26 ноября 2020 .
  29. ^ «Потрясающая производительность графического процессора» . Improsec. 3 января 2020 г.
  30. ^ a b Грасси Пол А. (июнь 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 .
  • Хох, Джонатан Дж .; Шамир, Ади (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.