Коллизия хеш-функции

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

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

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

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

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

• Стойкость к коллизиям первого рода: для заданного сообщения $~M$ должно быть практически невозможно подобрать другое сообщение $~M'$, имеющее такой же хеш.
• Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений $~(M,M')$, имеющих одинаковый хеш.

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

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

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

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

Однако, даже в том случае если хеш-функция обладает стойкостью к коллизиям первого рода, стойкостью к коллизиям второго рода, а также свойством необратимости, она может быть ненадёжной. Например существует так называемая атака расширения: зная $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 году, исследователи Сяоюнь Ван и Хунбо Ю из университета Шандонг в Китае, опубликовали алгоритм для поиска коллизий в хеш-функции MD5, причем их метод работает для любого инициализирующего вектора, а не только для вектора используемого по стандарту. Применение этого метода к MD4 позволяет найти коллизию меньше чем за секунду. Он также применим и к другим хеш-функциям, таким как RIPEMD и HAVAL.

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

Основная статья: Хеш-таблица

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

• Метод цепочек: Технология сцепления элементов (chaining) состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i; если таких элементов в множестве нет, в позиции i записан NULL.
• Открытая адресация: В отличие от хеширования с цепочками, при открытой адресации никаких списков нет, а все записи хранятся в самой хеш-таблице. Каждая ячейка таблицы содержит либо элемент динамического множества, либо NULL.

См. также

• Принцип Дирихле

Ссылки

• http://www.cryptography.com/cnews/hash.html
• http://www.cits.rub.de/MD5Collisions/
• http://eprint.iacr.org/2005/425.pdf — Improved Collision Attack on Hash Function MD5, very technical.
• Computer Algorithm Tutor