Криптография, защита компьютерных данных: информация, исследования, аналитика, экспертиза

Rambler's Top100

OZON.ru

Перейти на главную страницу

Карта сайта

Список статей

Обзор атак на приложения и протоколы, использующие алгоритм MD5, часть 4

© Сергей Панасенко, 2013

 

Продолжим рассмотрение атак на приложения и протоколы, в которых используется алгоритм хэширования MD5.

В ноябре 2005 г. вышла работа [1] двух известных экспертов по криптографии: Брюса Шнайера (Bruce Schneier) и Пола Хоффмана (Paul Hoffman), посвященная текущим атакам на алгоритмы хэширования MD5 и SHA-1 (в меньшей степени, чем MD5, поскольку атаки по поиску коллизий для SHA-1 на тот момент требовали несравнимо большей трудоемкости, чем атаки на MD5), широко используемые в различных сетевых протоколах. Эксперты классифицировали варианты использования алгоритмов хэширования в сетевых протоколах и пришли к выводу, что в подавляющем большинстве случаев применение абстрактных коллизий для конструирования практически применимых атак на сетевые протоколы невозможно, поскольку для этого требуются атаки, направленные на поиск прообраза, а не коллизии. Наиболее опасным применением абстрактных коллизий против сетевых протоколов авторы работы [1] посчитали рассмотренную в предыдущей части статьи атаку по конструированию двух сертификатов с эквивалентным хэш-значением MD5 [2], но и данная атака, по мнению Шнайера и Хоффмана, требовала выполнения слишком многих условий, противоречащих реальным процедурам выпуска сертификатов, что делает атаку практически неприменимой в реальном мире.

Тем не менее, авторы [1] сделали вывод о том, что необходимо задуматься о переходе на более стойкий алгоритм хэширования (в качестве которого они рекомендовали алгоритм SHA-256 [3]), а также о разработке сетевых протоколов, в которых было бы относительно просто переходить на новые алгоритмы хэширования при появлении эффективных атак против используемых алгоритмов).

Существенно менее оптимистичные выводы сделали авторы опубликованной в марте 2006 г. работы [4], которые показали, что опубликованные в течение 2005 г. атаки на приложения, использующие алгоритм MD5, весьма опасны для различных применений данного алгоритма. Авторы работы проанализировали степень подверженности атакам, основанным на абстрактных коллизиях, различных применений MD5 и сделали вывод о возможности успешных атак на некоторые из них – см. таблицу из работы [4]:

Применение Возможность атаки Атакуемые свойства
Подпись сообщений
Есть
Неотказуемость, целостность
Подпись существующих сертификатов
Нет
 
Подпись новых сертификатов
Есть
Аутентификация, неотказуемость
HMAC
Нет
 
Подмена существующих программ
Нет
 
Подмена новых программ
Есть
Неотказуемость, аутентификация, целостность

Обсудим приведенные в таблице сведения.

Во всех приведенных в таблице случаях атаки имеют различные ограничения по возможности их применения. Тем не менее, атаки практически применимы, и факт их наличия должен был ускорить отказ от использования алгоритма MD5.

Что касается надстроек HMAC и NMAC, то первые известные попытки распространения атак на алгоритм MD5 на данные надстройки над алгоритмом были сделаны в том же 2006 г. в работах [7] и [8], которые обсуждались ранее в [9]. В части надстроек над MD5 авторы работы [8] предложили атаку на алгоритм NMAC-MD5, позволяющую получить следующие результаты:

Цель атаки Требуемое количество данных Трудоемкость
Вычисление внутреннего ключа k1 (см. [6])
247
1
Поиск второго прообраза для выбранного атакующим сообщения
247
245

Атаки основаны на коллизиях внутренней функции хэширования алгоритма NMAC. В [8] отмечено, что внешняя функция хэширования скрывает результат выполнения внутренней функции, но не скрывает факт возникновения внутренней коллизии.

Несмотря на невысокую трудоемкость, данные атаки можно считать практически неприменимыми, поскольку:

Альтернативный вариант атаки по поиску второго прообраза для NMAC-MD5 был предложен в 2007 г. в работе [10]. Атака принципиально отличается от опубликованной в [8] тем, что она позволяет найти второй прообраз для произвольного сообщения (т. е. это первая известная реальная атака, направленная на поиск прообраза для NMAC-MD5). Опубликованная в [10] атака также использует связанные ключи; ее требования к ресурсам, однако, существенно выше: для успешной атаки требуется 251 блоков данных при трудоемкости 2100 операций. Таким образом, данная атака также не является практически применимой.

Литература

  1. Hoffman P., Schneier B. RFC 4270. Attacks on Cryptographic Hashes in Internet Protocols. // http://tools.ietf.org – November 2005.
  2. Lenstra A., de Weger B. On the possibility of constructing meaningful hash collisions for public keys. // http://www.win.tue.nl.
  3. FIPS PUB 180-2. Secure Hash Standard. // http://csrc.nist.gov – National Institute of Standards and Technology – 2002 August 1.
  4. Gauravaram P., McCullagh A., Dawson E. Attacks on MD5 and SHA-1: Is this the “Sword of Damocles” for Electronic Commerce? // http://www2.mat.dtu.dk – March 15, 2006.
  5. Lucks S., Daum M. The Story of Alice and her Boss: Hash Functions and the Blind Passenger Attack. // http://www.cits.rub.de.
  6. Панасенко С. Алгоритмы аутентификации сообщений HMAC и NMAC. // Sec.ru. – 16.07.2012 г.
  7. Kim J., Biryukov A., Preneel B., Hong S. On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0, and SHA-1. // http://eprint.iacr.org – 2006.
  8. Contini S., Yin Y. L. Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. // http://www.iacr.org – 2006.
  9. Панасенко С. Обзор результатов криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4. // Sec.ru. – 30.07.2012 г.
  10. Fouque P.-A., Leurent G., Nguyen P. Q. Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. // http://citeseerx.ist.psu.edu – Ecole Normale Superieure, Paris, France.

Предыдущая часть статьи

Следующая часть статьи