Данная статья завершает цикл статей, посвященных атакам на различные применения алгоритма хэширования MD5.
В шестой части статьи мы рассматривали работу [1], в которой были предложены атаки на команду APOP, используемую для усиленной (по сравнению с парольной) аутентификации пользователя на сервере электронной почты с применением алгоритма MD5.
Вернемся к работам, вышедшим в 2007 г., в частности, к рассмотренной в пятой части статьи работе [1], авторы которой предложили коллизии с выбранным префиксом и методику создания дающих коллизию пар сертификатов различных пользователей на их основе.
Продолжим обзор атак на различные приложения и протоколы, использующие алгоритм хэширования MD5.
В 2007 г. вышла работа [1] Жетана Лорана (Gaetan Leurent), которому удалось заметно усилить обсуждавшиеся в предыдущих частях статьи атаки Ванг и ее коллег [2] по поиску двухблочных коллизий для алгоритма MD5.
В конце 2006 г. очередного масштабного успеха в части атак на алгоритм MD5 и его приложения добились Стивенс, Ленстра и де Вегер. В ряде своих работ, вышедших в 2006-2007 гг. (в частности, в работах [1-3]), они предложили методику поиска коллизий для сообщений, префиксы которых имеют различающиеся хэш-значения (коллизия с выбранным префиксом – chosen-prefix collision).
Продолжим рассмотрение атак на приложения и протоколы, в которых используется алгоритм хэширования MD5.
В ноябре 2005 г. вышла работа [1] двух известных экспертов по криптографии: Брюса Шнайера (Bruce Schneier) и Пола Хоффмана (Paul Hoffman), посвященная текущим атакам на алгоритмы хэширования MD5 и SHA-1 (в меньшей степени, чем MD5, поскольку атаки по поиску коллизий для SHA-1 на тот момент требовали несравнимо большей трудоемкости, чем атаки на MD5), широко используемые в различных сетевых протоколах.
Менее, чем через две недели после выхода обсуждавшегося в предыдущей части статьи отчета ECRYPT, посвященного коллизиям для известных хэш-функций [1], вышла получившая широкую известность работа Арьена Ленстры (Arjen Lenstra), Ксиаоюн Ванг и Бена де Вегера (Benne de Weger) [2] (см. также [3], где представлена дополнительная информация, а наиболее полную информацию о данной атаке можно найти в работе [4], которая вышла несколько позднее). Данный коллектив криптоаналитиков представил метод конструирования пары значащих сертификатов формата X.509 [5] с эквивалентными хэш-значениями, вычисляемыми по алгоритму MD5.
Продолжим обзор атак на алгоритм хэширования MD5. Рассмотрим атаки по поиску прообразов.
Первые из работ, посвященных поиску прообразов для алгоритма MD5, – это работы коллектива специалистов из исследовательского подразделения компании Microsoft – Microsoft Research [1-2], опубликованные в 2007 г. В данных работах был предложен алгоритм инвертирования функции сжатия алгоритма MD5.
В предыдущей части статьи были рассмотрены криптоаналитические исследования алгоритма MD5, результаты которых были опубликованы в 2005 и в начале 2006 гг. Лучшего результата на то время добился Властимил Клима, метод которого позволял найти двухблочную коллизию в среднем за 17 секунд работы персонального компьютера средней производительности [1].
Предыдущая часть статьи была завершена рассмотрением деталей атаки по поиску двухблочных коллизий для алгоритма MD5, опубликованной в работе.
Практически сразу же после появления в открытом доступе работы Властимил Клима опубликовал работу, в которой содержалось подробное описание атаки, результаты которой были опубликованы Климой немногим ранее. В данном методе также использовался дифференциальный криптоанализ с комбинацией разности, определяемой операцией XOR, и разности, определяемой операцией вычитания по модулю 2
32.
После описанной в первой части статьи работы [1] долгое время не появлялось каких-либо новых результатов в поиске коллизий для алгоритма MD5 – до 2004 г., когда была опубликована упомянутая ранее работа Ксиаоюн Ванг и ее коллег [2].
