Продолжим рассмотрение атак на приложения и протоколы, в которых используется алгоритм хэширования MD5.
В ноябре 2005 г. вышла работа [1] двух известных экспертов по криптографии: Брюса Шнайера (Bruce Schneier) и Пола Хоффмана (Paul Hoffman), посвященная текущим атакам на алгоритмы хэширования MD5 и SHA-1 (в меньшей степени, чем MD5, поскольку атаки по поиску коллизий для SHA-1 на тот момент требовали несравнимо большей трудоемкости, чем атаки на MD5), широко используемые в различных сетевых протоколах.
В статье описаны варианты использования алгоритмов, широко применяемых в современной криптографии, для сжатия данных. Прежде чем перейти к обсуждению целесообразности такого использования алгоритмов, опишем модель, с которой будем работать.
3
Менее, чем через две недели после выхода обсуждавшегося в предыдущей части статьи отчета ECRYPT, посвященного коллизиям для известных хэш-функций [1], вышла получившая широкую известность работа Арьена Ленстры (Arjen Lenstra), Ксиаоюн Ванг и Бена де Вегера (Benne de Weger) [2] (см. также [3], где представлена дополнительная информация, а наиболее полную информацию о данной атаке можно найти в работе [4], которая вышла несколько позднее). Данный коллектив криптоаналитиков представил метод конструирования пары значащих сертификатов формата X.509 [5] с эквивалентными хэш-значениями, вычисляемыми по алгоритму MD5.
Продолжим обзор атак на алгоритм хэширования MD5. Данная статья посвящена атакам на различные приложения и протоколы, в которых используется или использовался данный алгоритм, а также атакам на различные надстройки над алгоритмом MD5. Рассмотрим именно те атаки, которые эксплуатируют особенности или слабости алгоритма MD5, а не какие-либо другие возможные уязвимости конкретного протокола или приложения.
В предыдущей части статьи были рассмотрены криптоаналитические исследования алгоритма MD5, результаты которых были опубликованы в 2005 и в начале 2006 гг. Лучшего результата на то время добился Властимил Клима, метод которого позволял найти двухблочную коллизию в среднем за 17 секунд работы персонального компьютера средней производительности [1].
После описанной в первой части статьи работы [1] долгое время не появлялось каких-либо новых результатов в поиске коллизий для алгоритма MD5 – до 2004 г., когда была опубликована упомянутая ранее работа Ксиаоюн Ванг и ее коллег [2].
За время активного использования алгоритма MD5 было предпринято множество попыток атаковать данный алгоритм. История криптоанализа MD5 весьма многогранна. Она тесно переплетается с криптоанализом ряда других алгоритмов хэширования (в том числе, рассмотренного ранее MD4); можно утверждать, что многие достижения в криптоанализе алгоритмов хэширования и успешные атаки на их применения были сделаны благодаря алгоритму MD5 и его популярности, весьма привлекавшей криптоаналитиков со всего мира.
Национальный институт стандартов и технологии США (NIST) только что объявил победителя конкурса на стандартный хэш-алгоритм SHA-3.
Продолжаем цикл статей про алгоритмы хэширования семейства MD. Данная статья описывает структуру алгоритма MD5, который является наиболее широко известным и используемым алгоритмом хэширования среди алгоритмов MD.
В предыдущих статьях был подробно описан алгоритм хэширования MD4 и рассмотрены текущие результаты его криптоанализа. Поскольку алгоритм MD4 использовался (и используется до сих пор) не только в «чистом» виде, но и в различных алгоритмах аутентификации сообщений, обзор данного алгоритма будет неполным без рассмотрения двух его вариантов: HMAC-MD4 и NMAC-MD4. Начнем с описания алгоритмов ключевого хэширования HMAC и NMAC, а обзору криптоанализа HMAC-MD4 и NMAC-MD4 будет посвящена следующая статья.
