Криптографическая хеш-функция - Cryptographic hash function

[Хеш-алгоритмы]
Концепции
хэш-функции  · SHA  · DSA
Основные стандарты
SHA-0  · SHA-1  · SHA-2  · SHA-3
Криптографическая хеш-функция (в частности, SHA-1 ) на работе. Небольшое изменение во вводе (в слове «сверх») резко меняет вывод (дайджест). Это так называемый лавинный эффект.

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

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

  • это детерминированный, что означает, что одно и то же сообщение всегда приводит к одному и тому же хешу
  • быстро вычислить хэш-значение для любого данного сообщения
  • невозможно сгенерировать сообщение, которое дает заданное значение хеш-функции (то есть отменить процесс, который сгенерировал данное значение хеш-функции)
  • невозможно найти два разных сообщения с одинаковым значением хеш-функции
  • небольшое изменение в сообщении должно изменить хеш-значение настолько сильно, что новое хеш-значение будет казаться некоррелированным со старым хеш-значением (лавинный эффект )[3]

Криптографические хеш-функции имеют много информационная безопасность приложений, особенно в цифровые подписи, коды аутентификации сообщений (MAC) и другие формы аутентификация. Их также можно использовать как обычные хэш-функции, чтобы индексировать данные в хеш-таблицы, за снятие отпечатков пальцев, чтобы обнаруживать повторяющиеся данные или однозначно идентифицировать файлы, а также контрольные суммы для обнаружения случайного повреждения данных. Действительно, в контексте информационной безопасности криптографические хеш-значения иногда называют (цифровой) отпечатки пальцев, контрольные суммы, или просто хеш-значения, хотя все эти термины обозначают более общие функции с довольно разными свойствами и целями.

Характеристики

Большинство криптографических хеш-функций предназначены для нить любой длины в качестве входных данных и производят хеш-значение фиксированной длины.

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

  • Сопротивление до изображения
    Учитывая хеш-значение час должно быть трудно найти какое-либо сообщение м такой, что час = хэш (м). Эта концепция связана с концепцией односторонняя функция. Функции, у которых отсутствует это свойство, уязвимы для атака на прообраз.
  • Сопротивление второго прообраза
    Учитывая ввод м1, должно быть сложно найти другой вход м2 такой, что хэш (м1) = хеш (м2). Это свойство иногда называют слабое сопротивление столкновению. Функции, у которых отсутствует это свойство, уязвимы для второстепенные атаки.
  • Сопротивление столкновению
    Должно быть сложно найти два разных сообщения м1 и м2 такой, что хэш (м1) = хеш (м2). Такая пара называется криптографической. хэш-коллизия. Это свойство иногда называют сильное сопротивление столкновению. Он требует, чтобы значение хеш-функции было как минимум в два раза длиннее, чем требуется для сопротивления прообразу; в противном случае столкновения могут быть обнаружены атака на день рождения.[4]

Сопротивление столкновениям подразумевает сопротивление второму предварительному изображению, но не подразумевает сопротивление предварительному изображению.[5] Более слабое предположение всегда предпочтительнее в теоретической криптографии, но на практике хеш-функция, которая устойчива только ко второму прообразу, считается небезопасной и поэтому не рекомендуется для реальных приложений.

Неформально эти свойства означают, что злонамеренный противник не может заменить или изменить входные данные без изменения их дайджеста. Таким образом, если две строки имеют один и тот же дайджест, можно быть уверенным, что они идентичны. Сопротивление второму прообразу не позволяет злоумышленнику создать документ с тем же хешем, что и документ, который злоумышленник не может контролировать. Устойчивость к конфликтам не позволяет злоумышленнику создать два разных документа с одним и тем же хешем.

Функция, отвечающая этим критериям, может иметь нежелательные свойства. Популярные в настоящее время криптографические хеш-функции уязвимы для удлинение нападения: данный хэш (м) и len (м) но нет м, выбрав подходящий м′ злоумышленник может вычислить хэш (м ∥ м′), где ∥ означает конкатенация.[6] Это свойство можно использовать для взлома простых схем аутентификации, основанных на хэш-функциях. В HMAC строительные работы вокруг этих проблем.

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

Алгоритмы контрольной суммы, такие как CRC32 и другие циклический контроль избыточности, разработаны для удовлетворения гораздо более слабых требований и обычно не подходят в качестве криптографических хэш-функций. Например, CRC использовалась для проверки целостности сообщения в WEP стандарт шифрования, но была легко обнаружена атака, использующая линейность контрольной суммы.

Степень сложности

В криптографической практике «сложный» обычно означает «почти наверняка вне досягаемости любого злоумышленника, которому необходимо препятствовать взлому системы, пока безопасность системы считается важной». Таким образом, значение термина в некоторой степени зависит от приложения, поскольку усилия, которые злонамеренный агент может вложить в задачу, обычно пропорциональны его ожидаемой выгоде. Однако, поскольку требуемые усилия обычно умножаются на длину дайджеста, даже тысячукратное преимущество в вычислительной мощности можно нейтрализовать, добавив к последнему несколько десятков бит.

Для сообщений, выбранных из ограниченного набора сообщений, например пароли или других коротких сообщений, возможно инвертировать хэш, попробовав все возможные сообщения в наборе. Поскольку криптографические хеш-функции обычно предназначены для быстрого вычисления, специальные ключевые производные функции требующие больших вычислительных ресурсов, которые делают такие атака грубой силой труднее.

В некоторых теоретический анализ "сложно" имеет особое математическое значение, например, "не разрешимо в асимптотический полиномиальное время ". Такое толкование трудность важны при изучении доказуемо безопасные криптографические хеш-функции но обычно не имеют прочной связи с практической безопасностью. Например, экспоненциальное время алгоритм иногда все еще может быть достаточно быстрым, чтобы осуществить возможную атаку. И наоборот, алгоритм с полиномиальным временем (например, тот, который требует п20 шаги для п-цифровые клавиши) могут быть слишком медленными для практического использования.

Иллюстрация

Иллюстрация потенциального использования криптографического хеша выглядит следующим образом: Алиса ставит перед трудной математической задачей Боб и утверждает, что она решила это. Боб хотел бы попробовать это сам, но все же хотел бы убедиться, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш-код и сообщает Бобу значение хеш-функции (сохраняя при этом решение в секрете). Затем, когда Боб сам придумывает решение несколько дней спустя, Алиса может доказать, что у нее было решение раньше, открыв его, попросив Боба хэшировать его и проверить, соответствует ли оно хэш-значению, данному ему ранее. (Это пример простого схема обязательств; на практике Алиса и Боб часто будут компьютерными программами, и секрет будет сложнее подделать, чем заявленное решение головоломки.)

Приложения

Проверка целостности сообщений и файлов

Основная статья: Проверка файла

Важным применением безопасных хэшей является проверка целостность сообщения. Сравнение дайджестов сообщения (хеш-дайджестов сообщения), вычисленных до и после передачи, может определить, были ли внесены какие-либо изменения в сообщение или файл.

MD5, SHA-1, или же SHA-2 хеш-дайджесты иногда публикуются на веб-сайтах или форумах, чтобы проверить целостность загруженных файлов,[8] включая файлы, полученные с помощью обмен файлами Такие как зеркальное отображение. Эта практика устанавливает цепь доверия до тех пор, пока хэши размещаются на надежном сайте - обычно исходном сайте - аутентифицированном HTTPS. Использование криптографического хэша и цепочки доверия позволяет обнаруживать злонамеренные изменения в файле. Другой коды обнаружения ошибок Такие как циклический контроль избыточности предотвращает только незлонамеренные изменения файла.

Генерация и проверка подписи

Основная статья: Цифровой подписи

Почти все цифровой подписи схемы требуют, чтобы криптографический хеш вычислялся для сообщения. Это позволяет выполнять вычисление подписи для относительно небольшого хэш-дайджеста статического размера. Сообщение считается подлинным, если проверка подписи прошла успешно, учитывая подпись и пересчитанный хэш-дайджест сообщения. Таким образом, свойство целостности сообщения криптографического хэша используется для создания безопасных и эффективных схем цифровой подписи.

Проверка пароля

Основная статья: Хеширование паролей

Пароль проверка обычно полагается на криптографические хэши. Сохранение всех паролей пользователей как открытый текст может привести к серьезному нарушению безопасности, если файл паролей будет скомпрометирован. Один из способов уменьшить эту опасность - хранить только хеш-дайджест каждого пароля. Для аутентификации пользователя пароль, представленный пользователем, хешируется и сравнивается с сохраненным хешем. При хешировании пароля требуется метод сброса пароля; исходные пароли не могут быть пересчитаны из сохраненного хеш-значения.

Стандартные криптографические хеш-функции рассчитаны на быстрое вычисление, и, как следствие, можно пробовать угаданные пароли с высокой скоростью. Общий графические процессоры может пробовать миллиарды возможных паролей каждую секунду. Функции хеширования паролей, которые выполняют растяжение ключа - Такие как PBKDF2, зашифровать или же Аргон2 - обычно используют повторные вызовы криптографического хэша для увеличения времени (а в некоторых случаях и памяти компьютера), необходимого для выполнения атака грубой силой на сохраненных дайджестах паролей. Хеш пароля требует использования большого случайного, не секретного соль значение, которое можно сохранить с хешем пароля. Соль рандомизирует вывод хэша пароля, что делает невозможным для злоумышленника хранить таблицы паролей и предварительно вычисленный хеш-значения, с которыми можно сравнить хеш-дайджест пароля.

Выходные данные хэш-функции пароля также можно использовать в качестве криптографического ключа. Поэтому хэши паролей также известны как основанные на паролях. ключевые производные функции (PBKDFs).

Доказательство работы

Основная статья: Система подтверждения работы

Система доказательства работы (или протокол, или функция) - это экономическая мера сдерживания атаки отказа в обслуживании и другие злоупотребления службами, такие как спам в сети, когда требуется некоторая работа со стороны инициатора запроса службы, что обычно означает время обработки на компьютере. Ключевой особенностью этих схем является их асимметрия: работа должна быть умеренно сложной (но выполнимой) со стороны запрашивающей стороны, но легкой для проверки поставщиком услуг. Одна популярная система - используется в Биткойн майнинг и Hashcash - использует частичную инверсию хэша, чтобы доказать, что работа была выполнена, чтобы разблокировать награду за майнинг в биткойнах, а также в качестве токена доброй воли для отправки электронного письма в Hashcash. Отправитель должен найти сообщение, хеш-значение которого начинается с числа нулевых битов. Средняя работа, которую отправитель должен выполнить, чтобы найти допустимое сообщение, экспоненциально зависит от количества нулевых битов, требуемых в хэш-значении, в то время как получатель может проверить достоверность сообщения, выполнив одну хеш-функцию. Например, в Hashcash отправителю предлагается сгенерировать заголовок, 160-битное хэш-значение SHA-1 которого содержит первые 20 бит как нули. Отправителю в среднем придется попробовать 219 раз, чтобы найти действительный заголовок.

Идентификатор файла или данных

Дайджест сообщения также может служить средством надежной идентификации файла; несколько управление исходным кодом системы, в том числе Git, Mercurial и Монотонный, использовать sha1sum различных типов контента (содержимое файлов, деревья каталогов, информация о происхождении и т. д.) для их уникальной идентификации. Хэши используются для идентификации файлов на пиринговый обмен файлами сети. Например, в ed2k ссылка, MD4 -вариантный хэш сочетается с размером файла, предоставляя достаточную информацию для поиска источников файлов, загрузки файла и проверки его содержимого. Магнитные ссылки еще один пример. Такие хэши файлов часто являются верхним хешем список хешей или хеш-дерево что дает дополнительные преимущества.

Одно из основных приложений хэш-функция позволяет быстро искать данные в хеш-таблица. Криптографические хеш-функции, являясь хэш-функциями определенного типа, также хорошо подходят для этого приложения.

Однако по сравнению со стандартными хеш-функциями криптографические хеш-функции имеют тенденцию быть гораздо более дорогостоящими в вычислительном отношении. По этой причине они, как правило, используются в контекстах, где пользователям необходимо защитить себя от возможности подделки (создания данных с тем же дайджестом, что и ожидаемые данные) потенциально злонамеренными участниками.

Хеш-функции на основе блочных шифров

Есть несколько способов использовать блочный шифр для создания криптографической хеш-функции, в частности функция одностороннего сжатия.

Методы напоминают режимы работы блочного шифра обычно используется для шифрования. Многие известные хэш-функции, в том числе MD4, MD5, SHA-1 и SHA-2 построены из компонентов, подобных блочному шифру, предназначенных для этой цели, с обратной связью, чтобы гарантировать, что результирующая функция не обратима. SHA-3 финалисты включили функции с компонентами блочного шифра (например, Моток, БЛЕЙК ) хотя функция окончательно выбрана, Кечак, был построен на криптографическая губка вместо.

Стандартный блочный шифр, например AES может использоваться вместо этих пользовательских блочных шифров; это может быть полезно, когда Встроенная система необходимо реализовать как шифрование, так и хеширование с минимальным размером кода или площадью оборудования. Однако такой подход может иметь издержки с точки зрения эффективности и безопасности. Шифры в хэш-функциях созданы для хеширования: они используют большие ключи и блоки, могут эффективно менять ключи в каждом блоке, и были разработаны и проверены на устойчивость к связанные ключевые атаки. Шифры общего назначения имеют разные цели проектирования. В частности, AES имеет размеры ключей и блоков, которые делают его нетривиальным для генерации длинных хеш-значений; Шифрование AES становится менее эффективным, когда ключ меняет каждый блок; и атаки связанных ключей делают его потенциально менее безопасным для использования в хэш-функции, чем для шифрования.

Дизайн хеш-функции

Строительство Меркле-Дамгарда

Основная статья: Строительство Меркле-Дамгарда
Хэш-конструкция Меркла – Дамгарда.

Хеш-функция должна иметь возможность обрабатывать сообщение произвольной длины в вывод фиксированной длины. Этого можно достичь, разбив ввод на серию блоков одинакового размера и последовательно работая с ними, используя функция одностороннего сжатия. Функция сжатия может быть либо специально разработана для хеширования, либо построена на основе блочного шифра. Хеш-функция, построенная с помощью конструкции Меркла-Дамгарда, так же устойчива к столкновениям, как и ее функция сжатия; любая коллизия для полной хеш-функции может быть прослежена до коллизии в функции сжатия.

Последний обработанный блок также должен быть однозначно длина с подкладкой; это имеет решающее значение для безопасности этой конструкции. Эта конструкция называется Строительство Меркле-Дамгарда. Наиболее распространенные классические хеш-функции, включая SHA-1 и MD5, примите эту форму.

Широкая труба против узкой трубы

Прямое применение конструкции Меркла – Дамгарда, где размер хеш-вывода равен размеру внутреннего состояния (между каждым этапом сжатия), приводит к узкая труба хеш-дизайн. Эта конструкция вызывает множество врожденных недостатков, в том числе удлинение, мультиколлизии,[9] атаки с длинными сообщениями,[10] генерация и вставка атак,[нужна цитата ] а также не могут быть распараллелены. В результате современные хеш-функции построены на широкая труба конструкции, которые имеют больший размер внутреннего состояния - в диапазоне от настроек конструкции Меркла-Дамгарда[9] к новым постройкам, таким как конструкция из губки и Строительство HAIFA.[11] Ни один из абитуриентов Конкурс хеш-функций NIST используйте классическую конструкцию Меркла – Дамгарда.[12]

Между тем, усечение вывода более длинного хэша, например, используемого в SHA-512/256, также предотвращает многие из этих атак.[13]

Использование при построении других криптографических примитивов

Хеш-функции могут использоваться для создания других криптографических примитивов. Чтобы эти другие примитивы были криптографически безопасными, необходимо позаботиться о их правильном построении.

Коды аутентификации сообщений (MAC) (также называемые хеш-функциями с ключом) часто строятся из хеш-функций. HMAC это такой MAC.

Как только блочные шифры могут использоваться для построения хэш-функций, хэш-функции могут использоваться для построения блочных шифров. Лубы-Ракофф конструкции, использующие хэш-функции, могут быть доказуемо безопасными, если безопасна лежащая в основе хэш-функция. Кроме того, многие хеш-функции (в том числе SHA-1 и SHA-2 ) построены с использованием блочного шифра специального назначения в Дэвис-Мейер или другая конструкция. Этот шифр также можно использовать в обычном режиме работы без тех же гарантий безопасности. Видеть ШАКАЛ, НЕСТИ и Лев.

Генераторы псевдослучайных чисел (PRNG) могут быть построены с использованием хэш-функций. Это делается путем объединения (секретного) случайного числа со счетчиком и его хеширования.

Некоторые хэш-функции, например Моток, Кечак, и RadioGatún выводить произвольно длинный поток и может использоваться как потоковый шифр, а потоковые шифры также могут быть построены из хэш-функций дайджеста фиксированной длины. Часто это делается путем создания криптографически безопасный генератор псевдослучайных чисел а затем используя свой поток случайных байтов как ключевой поток. ТЮЛЕНЬ это поточный шифр, который использует SHA-1 для создания внутренних таблиц, которые затем используются в генераторе потока ключей, более или менее не связанном с алгоритмом хеширования. Не гарантируется, что SEAL будет таким же сильным (или слабым), как SHA-1. Точно так же ключевое расширение HC-128 и HC-256 потоковые шифры активно используют SHA-256 хеш-функция.

Конкатенация

Конкатенация выходные данные от нескольких хэш-функций обеспечивают устойчивость к конфликтам на уровне самого сильного из алгоритмов, включенных в объединенный результат.[нужна цитата ] Например, более старые версии Безопасность транспортного уровня (TLS) и уровень защищенных сокетов (SSL) используется объединенный MD5 и SHA-1 суммы.[14][15] Это гарантирует, что метод поиска коллизий в одной из хеш-функций не повредит данные, защищенные обеими хеш-функциями.[нужна цитата ]

За Строительство Меркле-Дамгарда хэш-функции, объединенная функция столь же устойчива к столкновениям, как и ее самый сильный компонент, но не более устойчива к столкновениям.[нужна цитата ] Антуан Жу заметил, что 2-столкновения приводят к п-коллизии: если злоумышленник может найти два сообщения с одним и тем же хешем MD5, злоумышленник может найти столько сообщений, сколько желает злоумышленник, с идентичными хешами MD5 без особого труда.[16] Среди n сообщений с одинаковым хешем MD5, вероятно, будет конфликт в SHA-1. Дополнительная работа, необходимая для поиска коллизии SHA-1 (помимо экспоненциального поиска дня рождения), требует только полиномиальное время.[17][18]

Криптографические хеш-алгоритмы

Существует множество криптографических алгоритмов хеширования; в этом разделе перечислены несколько алгоритмов, на которые довольно часто ссылаются. Более обширный список можно найти на странице, содержащей сравнение криптографических хеш-функций.

MD5

Основная статья: MD5

MD5 был разработан Рональдом Ривестом в 1991 году для замены более ранней хэш-функции MD4 и был определен в 1992 году как RFC 1321. Коллизии с MD5 могут быть вычислены в течение нескольких секунд, что делает алгоритм непригодным для большинства случаев использования, когда требуется криптографический хэш. MD5 дает дайджест из 128 бит (16 байт).

SHA-1

Основная статья: SHA-1

SHA-1 был разработан в рамках правительственной Замковый камень проект. Первоначальная спецификация алгоритма - теперь обычно называемая SHA-0 - была опубликована в 1993 году под названием Secure Hash Standard, FIPS PUB 180, правительственным агентством стандартов США NIST (Национальный институт стандартов и технологий). Он был отозван Агентством национальной безопасности вскоре после публикации и заменен пересмотренной версией, опубликованной в 1995 году в FIPS PUB 180-1 и обычно обозначаемой как SHA-1. Коллизии с полным алгоритмом SHA-1 могут быть произведены с использованием разбитая атака и хеш-функцию следует считать неработающей. SHA-1 создает хеш-дайджест из 160 бит (20 байтов).

Документы могут ссылаться на SHA-1 как на «SHA», даже если это может конфликтовать с другими стандартными алгоритмами хеширования, такими как SHA-0, SHA-2 и SHA-3.

РИПЭМД-160

Основная статья: РИПЭМД-160

RIPEMD (Дайджест сообщений оценки примитивов целостности RACE) - это семейство криптографических хеш-функций, разработанных в Лёвене, Бельгия, Гансом Доббертином, Антуном Босселером и Бартом Пренелем в исследовательской группе COSIC при Католикском университете в Лёвене и впервые опубликованных в 1996 году. RIPEMD был основан на принципах проектирования, используемых в MD4, и по своим характеристикам аналогичен более популярному SHA-1. Однако RIPEMD-160 не сломался. Как следует из названия, RIPEMD-160 создает хеш-дайджест размером 160 бит (20 байт).

Водоворот

Основная статья: Whirlpool (криптография)

Whirlpool - это криптографическая хэш-функция, разработанная Винсентом Риджменом и Пауло С. Л. М. Баррето, которые впервые описали ее в 2000 году. Whirlpool основан на существенно модифицированной версии Advanced Encryption Standard (AES). Whirlpool создает хеш-дайджест размером 512 бит (64 байта).

SHA-2

Основная статья: 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

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 под названием BLAKE2 была анонсирована 21 декабря 2012 года. Она была создана Жан-Филиппом Аумассоном, Сэмюэлем Невесом, Зуко Уилкокс-О'Хирном и Кристианом Виннерлейном с целью замены широко используемых, но неработающих MD5 и SHA. -1 алгоритмы. При запуске на 64-битных архитектурах x64 и ARM BLAKE2b работает быстрее, чем SHA-3, SHA-2, SHA-1 и MD5. Хотя BLAKE и BLAKE2 не были стандартизированы, как SHA-3, BLAKE2 использовался во многих протоколах, включая Аргон2 хэш пароля для высокой эффективности, которую он предлагает на современных процессорах. Поскольку BLAKE был кандидатом на SHA-3, BLAKE и BLAKE2 предлагают те же выходные размеры, что и SHA-3, включая настраиваемый выходной размер.

BLAKE3

Основная статья: 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).[нужна цитата ]

12 августа 2004 года Жу, Каррибо, Лемюэль и Джалби объявили о конфликте полного алгоритма SHA-0.[нужна цитата ] Joux et al.сделал это, используя обобщение атаки Шабо и Жу. Они обнаружили, что столкновение имело сложность 251 и потребовало около 80 000 процессорных часов на суперкомпьютер с 256 Itanium 2 процессоров - эквивалентно 13 дням непрерывного использования суперкомпьютера.[нужна цитата ]

В феврале 2005 г. сообщалось об атаке на SHA-1, в результате которой произошло столкновение примерно через 2 часа.69 операции хеширования, а не 280 ожидается для 160-битной хеш-функции. В августе 2005 г. сообщалось об очередной атаке на SHA-1, в результате которой обнаруживались коллизии в 263 операции. Известны и другие теоретические недостатки SHA-1:[21][22] а в феврале 2017 года Google объявил о коллизии в SHA-1.[23] Исследователи безопасности рекомендуют, чтобы новые приложения могли избежать этих проблем, используя более поздних членов семейства SHA, таких как SHA-2, или используя такие методы, как рандомизированное хеширование[24][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, зашифровать, аргон2, Воздушный шар и некоторые недавние способы Крипта Unix. Для KSF, которые выполняют несколько хешей для замедления выполнения, NIST рекомендует количество итераций 10 000 или больше.[30]:5.1.1.2

Смотрите также

Рекомендации

Цитаты

  1. ^ а б Шай Галеви и Хьюго Кравчик, Рандомизированное хеширование и цифровые подписи
  2. ^ Шнайер, Брюс. «Криптоанализ MD5 и SHA: время для нового стандарта». Computerworld. Архивировано из оригинал на 2016-03-16. Получено 2016-04-20. Односторонние хеш-функции - это не просто алгоритмы шифрования, но и рабочие лошадки современной криптографии.
  3. ^ Аль-Кувари, Саиф; Давенпорт, Джеймс Х .; Брэдфорд, Рассел Дж. (2011). «Криптографические хеш-функции: последние тенденции дизайна и концепции безопасности». Цитировать журнал требует | журнал = (помощь)
  4. ^ Кац и Линделл 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. ^ а б Удачи, Стефан (2004). «Принципы разработки итерированных хеш-функций» - через Cryptology ePrint Archive, Отчет 2004/253. Цитировать журнал требует | журнал = (помощь)
  10. ^ Келси и Шнайер 2005 С. 474–490.
  11. ^ Бихам, Эли; Дункельман, Орр (24 августа 2006 г.). Платформа для итеративных хеш-функций - HAIFA. Второй семинар NIST по криптографическому хешированию - через Cryptology ePrint Archive: Report 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. ^ Joux 2004 С. 306–316.
  17. ^ Финни, Хэл (20 августа 2004 г.). «Еще проблемы с хеш-функциями». Список рассылки криптографии. Архивировано из оригинал 9 апреля 2016 г.. Получено 25 мая, 2016.
  18. ^ Хох и Шамир 2008, стр. 616-630.
  19. ^ Эндрю Регеншайд, Рэй Перлнер, Шу-Джен Чанг, Джон Келси, Мридул Нанди, Сурадьюти Пол, Отчет о состоянии первого раунда конкурса алгоритмов шифрования SHA-3
  20. ^ Сяоюнь Ван, Дэнго Фэн, Сюэцзя Лай, Хунбо Ю, Коллизии для хеш-функций MD4, MD5, HAVAL-128 и RIPEMD
  21. ^ Сяоюнь Ван, Ицюнь Лиза Инь, и Хунбо Ю, Поиск коллизий в полном SHA-1
  22. ^ Брюс Шнайер, Криптоанализ SHA-1 (резюмирует результаты Ванга и др. и их значение)
  23. ^ Фокс-Брюстер, Томас. «Google просто« разбил »старый криптографический алгоритм - вот почему это важно для веб-безопасности». Forbes. Получено 2017-02-24.
  24. ^ Шай Халеви, Уго Кравчик, Обновленная информация о случайном хешировании
  25. ^ Александр Сотиров, Марк Стивенс, Якоб Аппельбаум, Арьен Ленстра, Дэвид Мольнар, Даг Арне Освик, Бенне де Вегер, MD5 сегодня считается опасным: создание поддельного сертификата CA, по состоянию на 29 марта 2009 г.
  26. ^ Суинхо, Дэн (17 апреля 2020 г.). «15 крупнейших утечек данных в 21 веке». Журнал CSO.
  27. ^ Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов». Ars Technica. Получено 2020-11-23.
  28. ^ Клэберн, Томас (14 февраля 2019 г.). «Использовать 8-значный пароль Windows NTLM? Не надо. Каждый из них может быть взломан менее чем за 2,5 часа». www.theregister.co.uk. Получено 2020-11-26.
  29. ^ «Потрясающая производительность графического процессора». Improsec. 3 января 2020 г.
  30. ^ а б Грасси Пол А. (июнь 2017 г.). SP 800-63B-3 - Рекомендации по цифровой идентификации, аутентификации и управлению жизненным циклом. NIST. Дои:10.6028 / NIST.SP.800-63b.

Источники

внешняя ссылка