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

Структура ключевых итерационных схем хеширования.

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

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

Рис. 2. Общая схема итерационной хеш-функции

Информация представляется в виде последовательности блоков Mi определенной длины Lm, если необходимо, то дополняется до размера кратного длине блока.

Совокупность блоков {Mi} последовательно обрабатывается в цикловой функции (рис. 3). Результат последней итерации поступает на выход хеш-функции в виде образа: h = H(Мi), где h є R, R – множество значений хеш-функции.

Рис. 3. Структура хеш-функции CBC-MAC ISO/IEC 6796

Хеш-функция называется стойкой по 2-му прообразу тогда и только тогда, когда вычислительно неосуществимо для фиксированного М1 найти такое М2? М1, что Н(М1) = Н(М2).

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

В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере en:IBM_p690) находить коллизии.

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

В 2008 году Сотиров Александр, Марк Стивенс (Marc Stevens), Якоб Аппельбаум (Jacob Appelbaum) опубликовали на конференции 25th Chaos Communication Congress статью, в которой показали возможность генерирования поддельных цифровых сертификатов, на основе использования коллизий MD5.

Дата добавления: 2013-12-13