23 мая 2013
Обзор атак на приложения и протоколы, использующие алгоритм MD5
Часть 4
Продолжим рассмотрение атак на приложения и протоколы, в которых используется алгоритм хэширования 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 |
Нет |
|
Подмена существующих программ |
Нет |
|
Подмена новых программ |
Есть |
Неотказуемость, аутентификация, целостность |
Обсудим приведенные в таблице сведения.
- Свойство целостности подписанных сообщений атакуется с помощью подготовки пары сообщений специального формата с эквивалентных хэшем, одно из которых предлагается подписать жертве атаки. Здесь применим предложенный Даумом и Лаксом в [5] сценарий, когда злоумышленник является секретарем жертвы, в совокупности с рассмотренными в предыдущих частях статьи методами конструирования пар сообщений различных форматов.
- Подпись новых сертификатов, а также свойство неотказуемости подписи сообщений, атакуются путем конструирования двух сертификатов с эквивалентным хэшем. Существующие сертификаты остаются вне опасности, поскольку в данном случае абстрактная коллизия неприменима.
- Приложения, использующие HMAC-надстройки (были подробно описаны в [6]), не атакуются, поскольку на момент выхода работы [4] практически реализуемые атаки на HMAC-MD5 не были предложены.
- Под «подменой программ» подразумевается атака, целью которой является подмена санкционированного программного обеспечения на выполняющее, например, какие-либо злонамеренные функции. Предполагается, что целью атаки в данном случае является какой-либо банк программного обеспечения или репутационная база данных, где программы идентифицируется их хэш-значениями, вычисленными с помощью алгоритма MD5. Используя абстрактные коллизии как переключатель функционала программы, разработчик программы легко может создать пару программных модулей с эквивалентным хэшем и принципиально различающимися возможностями. Как и существующие сертификаты, существующие программы неатакуемы, поскольку для атаки на них требуется поиск прообраза, а не коллизии.
Во всех приведенных в таблице случаях атаки имеют различные ограничения по возможности их применения. Тем не менее, атаки практически применимы, и факт их наличия должен был ускорить отказ от использования алгоритма MD5.
Что касается надстроек HMAC и NMAC, то первые известные попытки распространения атак на алгоритм MD5 на данные надстройки над алгоритмом были сделаны в том же 2006 г. в работах [7] и [8], которые обсуждались ранее в [9]. В части надстроек над MD5 авторы работы [8] предложили атаку на алгоритм NMAC-MD5, позволяющую получить следующие результаты:
Цель атаки |
Требуемое количество данных |
Трудоемкость |
Вычисление внутреннего ключа k1 (см. [6]) |
247 |
1 |
Поиск второго прообраза для выбранного атакующим сообщения |
247 |
245 |
Атаки основаны на коллизиях внутренней функции хэширования алгоритма NMAC. В [8] отмечено, что внешняя функция хэширования скрывает результат выполнения внутренней функции, но не скрывает факт возникновения внутренней коллизии.
Несмотря на невысокую трудоемкость, данные атаки можно считать практически неприменимыми, поскольку:
- требуемое количество данных представляет собой результаты вычисления значений NMAC 246 случайных блоков данных на двух связанных ключах (секретных ключах, значения которых связаны известным простым соотношением; в данном случае пара связанных внутренних ключей k1 NMAC-надстройки различается только значением старшего бита ключей; атаки с использованием связанных ключей подробно рассматриваются, например, в [9]); использование связанных ключей существенно сужает возможный контекст применения атаки;
- поиск второго прообраза возможен только для выбранного атакующим сообщения (а не для произвольного сообщения), что, фактически, представляет собой поиск абстрактной коллизии – двух сообщений с эквивалентным хэшем NMAC-MD5;
- атаки являются вероятностными, что, фактически, увеличивает общую трудоемкость успешной атаки.
Альтернативный вариант атаки по поиску второго прообраза для NMAC-MD5 был предложен в 2007 г. в работе [10]. Атака принципиально отличается от опубликованной в [8] тем, что она позволяет найти второй прообраз для произвольного сообщения (т. е. это первая известная реальная атака, направленная на поиск прообраза для NMAC-MD5). Опубликованная в [10] атака также использует связанные ключи; ее требования к ресурсам, однако, существенно выше: для успешной атаки требуется 251 блоков данных при трудоемкости 2100 операций. Таким образом, данная атака также не является практически применимой.
Продолжение следует
Литература
- Hoffman P., Schneier B. RFC 4270. Attacks on Cryptographic Hashes in Internet Protocols. // http://tools.ietf.org – November 2005.
- Lenstra A., de Weger B. On the possibility of constructing meaningful hash collisions for public keys. // http://www.win.tue.nl.
- FIPS PUB 180-2. Secure Hash Standard. // http://csrc.nist.gov – National Institute of Standards and Technology – 2002 August 1.
- 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.
- Lucks S., Daum M. The Story of Alice and her Boss: Hash Functions and the Blind Passenger Attack. // http://www.cits.rub.de.
- Панасенко С. Алгоритмы аутентификации сообщений HMAC и NMAC. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35050 – 16.07.2012 г.
- 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.
- Contini S., Yin Y. L. Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. // http://www.iacr.org – 2006.
- Панасенко С. Обзор результатов криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35251 – 30.07.2012 г.
- 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.
Об авторе:
Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.
С автором можно связаться: по телефонам (499)731-0000, (499)731-2050
или по E-mail serg@panasenko.ru
Мнения экспертов
Очередная часть статьи, посвященная анализу возможностей осуществления атак на приложения и протоколы, использующие алгоритм MD5, как и предыдущие части получилась великолепной. Автор последовательно излагает изменение взглядов и подходов к проведению атак, привлекает читателя к анализу опубликованных результатов, доходчиво обосновывает собственные выводы. Объем работы соответствует требованиям, предъявляемым к публикуемым материалам. По содержанию статьи видно, что автор проделывает огромную аналитическую работу, систематизируя разрозненные сведения, тем самым делая представленный материал полезным для разнородной читательской аудитории нашего портала. Полагаю нужным опубликовать представленный материал.
-
 Левицкий О.И.
ОАО НПО «Наука»
Ведущий специалист по информационной безопасности
Статья на профессиональном уровне описывает подходы криптоанализа в вопросах построения сценариев атак на приложения и протоколы, использующие алгоритм MD5. Наглядно показан прикладной аспект злоумышленного использования сконструированной пары сертификатов на основе «двухстороннего расширения» коллизии. Статья рассчитана на специалистов, глубоко изучающих условия и тенденции развития криптоанализа.
-
 Лукоянов В.А.
ЗАО ВТБ Специализированный депозитарий
Руковолитель Центра управления сертификатами
Статья носит познавательный характер и позволяет неискушенному специалисту в историческом обзоре проследить развитие методов осуществления атак на приложения и протоколы, использующие алгоритм MD5. Может быть полезна студентам при написании курсовых и дипломных работ, а также соискателям ученых степеней в области криптографии. Автору целесообразно усилить практическую направленность обзоров, указав области применения результатов атак на приложения и протоколы при построении криптографических систем.
Ваши комментарии:
Для того, чтобы оставлять коментарии, Вам нужно авторизоваться на Sec.Ru. Если У Вас еще нет аккаунта, пройдите процедуру регистрации.
|
|
