Обзор атак на приложения и протоколы, использующие алгоритм 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]:

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

• Свойство целостности подписанных сообщений атакуется с помощью подготовки пары сообщений специального формата с эквивалентных хэшем, одно из которых предлагается подписать жертве атаки. Здесь применим предложенный Даумом и Лаксом в [5] сценарий, когда злоумышленник является секретарем жертвы, в совокупности с рассмотренными в предыдущих частях статьи методами конструирования пар сообщений различных форматов.
• Подпись новых сертификатов, а также свойство неотказуемости подписи сообщений, атакуются путем конструирования двух сертификатов с эквивалентным хэшем. Существующие сертификаты остаются вне опасности, поскольку в данном случае абстрактная коллизия неприменима.
• Приложения, использующие HMAC-надстройки (были подробно описаны в [6]), не атакуются, поскольку на момент выхода работы [4] практически реализуемые атаки на HMAC-MD5 не были предложены.
• Под «подменой программ» подразумевается атака, целью которой является подмена санкционированного программного обеспечения на выполняющее, например, какие-либо злонамеренные функции. Предполагается, что целью атаки в данном случае является какой-либо банк программного обеспечения или репутационная база данных, где программы идентифицируется их хэш-значениями, вычисленными с помощью алгоритма MD5. Используя абстрактные коллизии как переключатель функционала программы, разработчик программы легко может создать пару программных модулей с эквивалентным хэшем и принципиально различающимися возможностями. Как и существующие сертификаты, существующие программы неатакуемы, поскольку для атаки на них требуется поиск прообраза, а не коллизии.

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

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

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

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

• требуемое количество данных представляет собой результаты вычисления значений NMAC 2⁴⁶ случайных блоков данных на двух связанных ключах (секретных ключах, значения которых связаны известным простым соотношением; в данном случае пара связанных внутренних ключей k1 NMAC-надстройки различается только значением старшего бита ключей; атаки с использованием связанных ключей подробно рассматриваются, например, в [9]); использование связанных ключей существенно сужает возможный контекст применения атаки;
• поиск второго прообраза возможен только для выбранного атакующим сообщения (а не для произвольного сообщения), что, фактически, представляет собой поиск абстрактной коллизии – двух сообщений с эквивалентным хэшем NMAC-MD5;
• атаки являются вероятностными, что, фактически, увеличивает общую трудоемкость успешной атаки.

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

Литература

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.

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

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