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

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

Безопасные алгоритмы хеширования
Концепции
хэш-функции , SHA , DSA
Основные стандарты
ША-0 , ША-1 , ША-2 , ША-3

( Криптографическая хэш-функция CHF ) — это хеш-алгоритм ( преобразование произвольной двоичной строки в двоичную строку с фиксированным размером $n$ бит), который имеет специальные свойства, желательные для криптографического приложения:

• вероятность того или иного $n$-битный выходной результат ( хеш-значение ) для случайной входной строки («сообщения») равен $2^{-n}$ ( как и любой хороший хеш ), поэтому значение хеш-функции можно использовать в качестве представителя сообщения;
• найти входную строку, соответствующую заданному значению хеш-функции ( прообразу ), невозможно, если предположить, что все входные строки одинаково вероятны. Сопротивление , такому поиску количественно оценивается как уровень безопасности криптографический хэш с $n$ ожидается, что биты хэш-значения будут иметь сопротивления прообразу силу $n$ бит, если только пространство возможных входных значений не значительно меньше, чем $2^{n}$ (практический пример можно найти в § Атаки на хешированные пароли );
• Сила сопротивления второго прообраза с теми же ожиданиями относится к аналогичной проблеме поиска второго сообщения, соответствующего заданному значению хеш-функции, когда одно сообщение уже известно;
• найти любую пару разных сообщений, которые дают одно и то же значение хеш-функции ( коллизия ), также невозможно, ожидается, что криптографический хэш будет иметь сопротивления коллизиям силу $n/2$ бит (ниже из-за парадокса дня рождения ).

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

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

Свойства

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

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

Сопротивление предобразу

Учитывая значение хеш-функции h , должно быть сложно найти сообщение m такое, что h = hash( m ) . Это понятие связано с понятием односторонней функции . Функции, у которых отсутствует это свойство, уязвимы для атак на прообразы .

Второе сопротивление прообразу

Учитывая входное значение m ₁ , должно быть сложно найти другой входной сигнал m ₂ такой, что hash( m ₁ ) = hash( m ₂ ) . Это свойство иногда называют слабым сопротивлением столкновению . Функции, у которых отсутствует это свойство, уязвимы для атак второго прообраза .

Устойчивость к столкновениям

Должно быть сложно найти два разных сообщения m ₁ и m _2, такие что hash( m ₁ ) = hash( m ₂ ) . Такая пара называется криптографической коллизией хэшей . Это свойство иногда называют сильным сопротивлением столкновению . Для этого требуется хеш-значение как минимум в два раза длиннее, чем требуется для устойчивости к прообразу; в противном случае коллизии могут быть обнаружены с помощью атаки на день рождения .

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

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

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

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

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

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

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

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

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

Иллюстрация

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Доказательство работы

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

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

Дайджест сообщения также может служить средством надежной идентификации файла; несколько управления исходным кодом систем , включая 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 Эту форму принимают .

Широкая труба

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

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

других криптографических

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

Коды аутентификации сообщений (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 . Это гарантирует, что метод поиска коллизий в одной из хеш-функций не повредит данные, защищенные обеими хэш-функциями.

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

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

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

MD5

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

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

SHA-1

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

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.

РИПЕМД-160

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

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

Водоворот

Основная статья: Whirlpool (хэш-функция)

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

ША-2

Основная статья: ША-2

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

SHA-3 (алгоритм безопасного хеширования 3) был выпущен NIST 5 августа 2015 года. SHA-3 является подмножеством более широкого семейства криптографических примитивов Keccak. Алгоритм Кекчака — это работа Гвидо Бертони, Джоан Дэмен, Майкла Питерса и Жиля Ван Аша. Keccak основан на губчатой ​​конструкции, которую также можно использовать для создания других криптографических примитивов, таких как поточный шифр. SHA-3 обеспечивает те же выходные размеры, что и SHA-2: 224, 256, 384 и 512 бит.

Настраиваемые выходные размеры также можно получить с помощью функций SHAKE-128 и SHAKE-256. Здесь расширения имени -128 и -256 подразумевают уровень безопасности функции, а не размер вывода в битах.

БЛЕЙК2

Основная статья: БЛЕЙК2

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, включая настраиваемый размер вывода.

БЛЕЙК3

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

BLAKE3, улучшенная версия BLAKE2, была анонсирована 9 января 2020 года. Ее создали Джек О'Коннор, Жан-Филипп Омассон, Сэмюэл Невес и Зуко Уилкокс-О'Хирн. BLAKE3 — это единый алгоритм, в отличие от BLAKE и BLAKE2, которые представляют собой семейства алгоритмов с несколькими вариантами. Функция сжатия BLAKE3 во многом основана на функции сжатия BLAKE2, с самым большим отличием в том, что количество раундов уменьшено с 10 до 7. Внутренне BLAKE3 представляет собой дерево Меркла и поддерживает более высокие степени параллелизма, чем BLAKE2.

Атаки на криптографические алгоритмы хеширования

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

Даже если хеш-функция ни разу не была взломана, успешная атака на ослабленный вариант может подорвать доверие экспертов. Например, в августе 2004 года коллизии были обнаружены в нескольких популярных на тот момент хэш-функциях, включая MD5. Эти недостатки поставили под сомнение безопасность более сильных алгоритмов, основанных на слабых хэш-функциях, в частности SHA-1 (усиленная версия SHA-0), RIPEMD-128 и RIPEMD-160 (обе усиленные версии RIPEMD).

12 августа 2004 г. Жу, Каррибо, Лемюэль и Жалби объявили о коллизии полного алгоритма SHA-0. Жу и др. добился этого, используя обобщение атаки Шабо и Жу. Они обнаружили, что столкновение имело сложность 2. ⁵¹ и потребовало около 80 000 часов процессорного времени на суперкомпьютере с 256 процессорами Itanium 2 , что эквивалентно 13 дням постоянного использования суперкомпьютера.

В феврале 2005 года сообщалось о нападении на SHA-1, в результате которого столкновение произошло примерно через 2 часа. ⁶⁹ операции хеширования, а не 2 ⁸⁰ ожидается для 160-битной хэш-функции. В августе 2005 года сообщалось о еще одной атаке на SHA-1, в результате которой произошли столкновения в 2 ⁶³ операции. Известны и другие теоретические недостатки SHA-1: а в феврале 2017 года Google объявил о коллизии в SHA-1. Исследователи безопасности рекомендуют, чтобы новые приложения могли избежать этих проблем, используя более поздние члены семейства SHA, такие как SHA-2 , или используя такие методы, как рандомизированное хеширование. которые не требуют сопротивления столкновению.

Успешная практическая атака сломала MD5, используемый в сертификатах безопасности транспортного уровня в 2008 году.

Многие криптографические хеши основаны на конструкции Меркла-Дамгорда . Все криптографические хэши, которые напрямую используют полный результат конструкции Меркла-Дамгорда, уязвимы для атак с расширением длины . Это делает алгоритмы хеширования MD5, SHA-1, RIPEMD-160, Whirlpool и SHA-256/SHA-512 уязвимыми для этой конкретной атаки. SHA-3, BLAKE2, BLAKE3 и усеченные варианты SHA-2 не уязвимы для атак этого типа.

Атаки на хешированные пароли

Основная статья: Взлом пароля

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

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

Использование криптографической соли предотвращает некоторые атаки, такие как создание файлов с предварительным вычислением хеш-значений, например, радужных таблиц . возможен поиск порядка 100 миллиардов тестов в секунду Но с помощью высокопроизводительных графических процессоров , что делает возможными прямые атаки даже с использованием соли. США Национальный институт стандартов и технологий рекомендует хранить пароли с использованием специальных хешей, называемых функциями деривации ключей (KDF), которые были созданы для замедления поиска методом перебора. Медленные хэши включают pbkdf2 , bcrypt , scrypt , argon2 , Balloon и некоторые новейшие режимы Unix crypt . Для KDF, которые выполняют несколько хэшей для замедления выполнения, NIST рекомендует количество итераций 10 000 или более.

См. также

• Лавинный эффект
• Сравнение криптографических хэш-функций
• Криптографическая гибкость
• КРИПТРЕК
• Исправление файлов
• HMAC
• Хэш-цепочка
• Атака с расширением длины
• MD5CRK
• Код аутентификации сообщения
• НЕССИ
• Список слов PGP
• Случайный оракул
• Безопасность криптографических хэш-функций
• ША-3
• Универсальная односторонняя хэш-функция

Ссылки

Источники

• Харник, Дэнни; Килиан, Джо; Наор, Мони; Рейнгольд, Омер; Розен, Алон (2005). «О надежных сумматорах для невнимательного переноса и других примитивов». Достижения в криптологии – EUROCRYPT 2005 . Конспекты лекций по информатике. Том. 3494. стр. 96–113. дои : 10.1007/11426639_6 . ISBN  978-3-540-25910-7 . ISSN   0302-9743 .
• Хох, Джонатан Дж.; Шамир, Ади (2008). «О силе составного хэш-объединителя, когда все хэш-функции слабы». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 5126. стр. 616–630. дои : 10.1007/978-3-540-70583-3_50 . ISBN  978-3-540-70582-6 . ISSN   0302-9743 .
• Жу, Антуан (2004). «Мультиколлизии в итерированных хэш-функциях. Применение к каскадным конструкциям». Достижения в криптологии – КРИПТО 2004 . Конспекты лекций по информатике. Том. 3152. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 306–316. дои : 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. дои : 10.1007/11426639_28 . ISBN  978-3-540-25910-7 . ISSN   0302-9743 . Архивировано из оригинала 16 марта 2017 г. Проверено 18 июля 2017 г.
• Кац, Джонатан; Линделл, Иегуда (2014). Введение в современную криптографию (2-е изд.). ЦРК Пресс. ISBN  978-1-4665-7026-9 .
• Любашевский Вадим; Миччанчо, Даниэле; Пейкерт, Крис; Розен, Алон (2008). «SWIFFT: скромное предложение по хешированию БПФ». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 5086. стр. 54–72. дои : 10.1007/978-3-540-71039-4_4 . ISBN  978-3-540-71038-7 . ISSN   0302-9743 .
• Мендель, Флориан; Рехбергер, Кристиан; Шлеффер, Мартин (2009). «MD5 слабее, чем слабый: атаки на составные объединители». Достижения в криптологии – ASIACRYPT 2009 . Конспекты лекций по информатике. Том. 5912. стр. 144–161. дои : 10.1007/978-3-642-10366-7_9 . ISBN  978-3-642-10365-0 . ISSN   0302-9743 .
• Нанди, Мридул; Пол, Сурадьюти (2010). «Ускорение Wide-Pipe: безопасное и быстрое хеширование» . Прогресс в криптологии — INDOCRYPT 2010 . Конспекты лекций по информатике. Том. 6498. стр. 144–162. дои : 10.1007/978-3-642-17401-8_12 . ISBN  978-3-642-17400-1 . ISSN   0302-9743 .
• Рогауэй, П.; Шримптон, Т. (2004). «Основы криптографических хеш-функций: определения, последствия и разделение устойчивости к прообразу, устойчивости к второму прообразу и устойчивости к столкновениям» . В Рое, Б.; Майер, В. (ред.). Быстрое программное шифрование: 11-й международный семинар, FSE 2004 . Том. 3017. Конспекты лекций по информатике: Springer. стр. 371–388. ISBN  3-540-22171-9 . Архивировано из оригинала 30 ноября 2022 г. Проверено 30 ноября 2022 г.

• Менезес, Альфред Дж.; ван Оршот, Пол К.; Ванстон, Скотт А. (7 декабря 2018 г.). «Хеш-функции» . Справочник по прикладной криптографии . ЦРК Пресс. стр. 33–. ISBN  978-0-429-88132-9 .
• Омассон, Жан-Филипп (6 ноября 2017 г.). Серьезная криптография: практическое введение в современное шифрование . Нет крахмального пресса. ISBN  978-1-59327-826-7 . OCLC   1012843116 .

Внешние ссылки

• Паар, Кристоф; Пельцль, Ян (2009). «11: Хэш-функции» . Понимание криптографии, Учебник для студентов и практиков . Спрингер . Архивировано из оригинала 8 декабря 2012 г. (сопутствующий веб-сайт содержит онлайн-курс по криптографии, в котором рассматриваются хеш-функции)
• «Веб-сайт хеш-функций ECRYPT» .
• Булдас, А. (2011). «Серия мини-лекций о криптографических хэш-функциях» . Архивировано из оригинала 6 декабря 2012 г.
• Приложение на основе Python с открытым исходным кодом и графическим интерфейсом, используемым для проверки загрузок.