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

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

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

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

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

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

• Стойкость к коллизиям первого рода: для заданного сообщения $~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₁ = X | | Y, M₂ = H(X) | | Y, H(M₁) = H(M₂), то есть нарушается свойство стойкости к коллизиям первого рода.

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

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

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

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

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

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

См. также

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

Ссылки

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