Коллизия хэш-функции | это... Что такое Коллизия хэш-функции? (original) (raw)

Коллизией хеш-функции H называется два различных входных блока данных x и y таких, что H(x) = H(y).

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

Содержание

Коллизии криптографических хеш-функций

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

Для криптографических хеш-функций различают два типа стойкости к нахождению коллизий:

Пожалуй, самой простой атакой на нахождение коллизий является атака «дней рождения». С помощью этой атаки отыскание коллизии для хеш-функции разрядности n бит потребует в среднем около 2_n_ / 2 операций. Поэтому n_-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для нее близка к 2_n / 2.

Также ключевым свойством хеш-функций является их необратимость:

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

Однако, даже в том случае если хеш-функция обладает стойкостью к коллизиям первого рода, стойкостью к коллизиям второго рода, а также свойством необратимости, она может быть ненадёжной. Например существует так называемая атака расширения: зная H(x), можно вычислить H(x | | y) = H(H(x) | | y); которая, для некоторых хеш-функций, работает даже при обеспечении всех трёх свойств. Подразумевается, что нет необходимости знать X, а достаточно знать лишь его хэш. Таким образом можно, например, дописывать дополнительную информацию к чужому сообщению. Для предотвращения этой атаки используют различные методы: добавляют дополнительный раунд при хешировании, отличный от предыдущих; применяют многократное хеширование; или используют комбинацию предыдущих 2х методов.

Но атаку расширения можно рассмотреть и с другой стороны: если у нас есть некоторое сообщение X, и хэш-функция уязвима к атаке расширения, то легко можно найти коллизию первого рода - _M_1 = X | | Y, _M_2 = H(X) | | Y, H(_M_1) = H(_M_2), то есть нарушается свойство стойкости к коллизиям первого рода.

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

В 2005 году исследователи Ван Сяоюнь и Юй Хунбо из университета Шаньдун в Китае, опубликовали алгоритм для поиска , причём их метод работает для любого инициализирующего вектора, а не только для вектора, используемого по стандарту. Применение этого метода к HAVAL.

Разрешение коллизий в хеш-таблицах

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

См. также

Ссылки

Wikimedia Foundation.2010.