Rambler's Top100

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

Карта сайта

 

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

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

 

Практически одновременно с обсуждавшейся в предыдущей части статьи работой Ондрея Микля [1] вышла работа Дэна Камински (Dan Kaminsky) [2], в которой также рассматриваются возможности практического применения найденных китайскими криптоаналитиками в [3] абстрактных коллизий для алгоритма MD5.

Камински обратил особое внимание на возможность «расширения» коллизии (которую использовал и Микль в своей атаке), присущую любым алгоритмам хэширования, основанным на схеме Меркля-Дамгаарда (схема была подробно описана в [4]): двухблочную коллизию можно распространить на произвольное количество блоков за счет дополнения к дающим коллизию блокам идентичных фрагментов произвольной длины (см. рис. 1). Т. е. если сообщения x и y дают коллизию (MD5(x) = MD5(y)), а q – любое сообщение, то:

MD5(x || q) = MD5(y || q),

где || обозначает конкатенацию сообщений.

Отметим также тот факт, что в случае, когда коллизия может быть найдена для произвольного значения вектора инициализации (двухблочные коллизии китайских криптоаналитиков могут быть найдены для любых значений IV [3]), «расширение» коллизии может происходить «в обратную сторону» – присоединением произвольного сообщения перед двухблочной коллизией. Т. е. если t – присоединяемое сообщение, а сообщения x’ и y’ дают следующую коллизию: MD5’(x’) = MD5’(y’), где MD5’() – алгоритм хэширования, аналогичный MD5, но использующий в качестве вектора инициализации значение MD5(t), то (см. рис. 2):

MD5(t || x’) = MD5(t || y’).

Возможна и комбинация данных методов – «расширение» коллизии присоединением сообщения как перед, так и после двух дающих коллизию блоков:

MD5(t || x’ || q) = MD5(t || y’ || q).

Используя возможность «расширения» коллизии, Камински попытался атаковать программу Tripwire – программу отслеживания изменений в файлах операционной системы [5], использующую, в числе прочих алгоритмов, алгоритм MD5 для контроля целостности файлов. Для атаки Камински разработал программу Stripwire, позволяющую подменить зашифрованный файл, содержащий программу на языке Perl, другим файлом с эквивалентным значением хэша MD5. Однако, Камински признал, что практическое применение программы Stripwire для реальной атаки невозможно, поскольку ложный файл в данном случае может содержать только неосмысленную информацию. Т. е., в отличие от атаки Микля, сконструировать практически применимую атаку на основе абстрактной коллизии Камински не удалось.

Кроме того, работа [2] содержит ряд рассуждений на тему крайне отрицательного влияния найденных в MD5 коллизий на применяющие данный алгоритм системы; прежде всего, системы электронной подписи и системы управления цифровыми правами (DRM – Digital Right Management). Камински, в частности, делает вывод о том, что, благодаря коллизиям, электронная подпись, рассчитанная с использованием MD5, больше не имеет юридической силы. Основной вывод работы [2] таков: найденные абстрактные коллизии еще не являются основанием для массового отказа от использования MD5, но все должны быть готовы к тому, что MD5 в обозримом будущем будет полностью взломан. Следовательно, предпочтительно использовать более стойкие алгоритмы хэширования.

Работа Дэна Камински вызвала бурную дискуссию среди известных экспертов по криптографии [6], начатую Беном Лорье (Ben Laurie), который отметил бессмысленность атаки Камински при том, что, в общем случае, подмена одного исполняемого файла другим может являться хорошей целью атаки. В ответ на данное замечание свои варианты атак (с различной степенью практической применимости) предложили Адам Бэк (Adam Back), Ондрей Микль, Джон Келси (John Kelsey) и Дэвид Вагнер (David Wagner). Рассмотрим один из сценариев атаки, предложенный Джоном Келси.

Келси предположил возможность использования хэша MD5 для верификации большого простого числа, обладающего всеми необходимыми свойствами для использования в алгоритме Диффи-Хеллмана. Алгоритм Диффи-Хеллмана позволяет двум пользователям удаленно вычислить общий секретный ключ (для последующего использования в качестве ключа симметричного шифрования) на основе пар асимметричных ключей: каждый из этих двух пользователей вычисляет общий ключ на основе своего секретного и чужого открытого ключа (см. рис. 3; алгоритм Диффи-Хеллмана и варианты его использования подробно описаны, например, в [7]):

K = (Kpi)Ksj mod p = (Kpj)Ksi mod p,

где:

В данном случае большое простое число используется в качестве модуля криптосистемы p. Если заменить данное число составным, алгоритм Диффи-Хеллмана относительно легко вскрывается, позволяя атакующему получить доступ к вычисляемому ключу. Бен Лорье сразу предложил атакуемое простое число (в шестнадцатеричном виде):

D131DD02C5E6EEC4693D9A0698AFF95C2FCAB58712467EAB4004583EB8FB7F8955AD340609F4B30283E488832571415A085125E8F7CDC99FD91DBDF280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E2B487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080A80D1EC69821BCB6A8839396F9652B6FF72A700000000000000000000000000000001B.

Данное число может быть заменено составным числом, имеющим то же самое хэш-значение, вычисленное по алгоритму MD5:

D131DD02C5E6EEC4693D9A0698AFF95C2FCAB50712467EAB4004583EB8FB7F8955AD340609F4B30283E4888325F1415A085125E8F7CDC99FD91DBD7280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E23487DA03FD02396306D248CDA0E99F33420F577EE8CE54B67080280D1EC69821BCB6A8839396F965AB6FF72A700000000000000000000000000000001B.

Такая подмена позволит злоумышленнику атаковать алгоритм Диффи-Хеллмана.

Нельзя утверждать, что атака Джона Келси однозначно практически применима, тем не менее, ее сценарий выглядит правдоподобным. Отметим также высказывание Дэвида Вагнера в [6]: «Я уверен, что единственный безопасный образ мыслей сейчас состоит в предположении, что стойкость MD5 против коллизий отсутствует полностью».

В феврале 2005 г. вышел отчет [8] экспертов европейского проекта ECRYPT (крупный исследовательский проект по различным аспектам криптологии, объединяющий ряд известных университетов и исследовательских подразделений корпораций [9]), посвященный опубликованным в 2004 г. коллизиям для ряда широко распространенных алгоритмов хэширования. В числе прочего, эксперты отметили, что абстрактные коллизии достаточно сложно применимы для практических атак в реальных ситуациях, в том числе, против схем электронной подписи; для схем электронной подписи более важна стойкость алгоритма хэширования против поиска прообразов. Вывод экспертов относительно MD5 таков: несмотря на то, что практическое применение коллизий в настоящий момент весьма ограниченно, ECRYPT не рекомендует в дальнейшем использовать алгоритм MD5 в приложениях электронной подписи со средними или высокими требованиями к безопасности. Вместо MD5 рекомендуется использовать семейство алгоритмов SHA-2 [10] или алгоритм Whirlpool [11].

Литература

  1. Mikle O. Practical Attacks on Digital Signatures Using MD5 Message Digest. // http://eprint.iacr.org – Charles University, Prague, Czech Republic – December 2, 2004.
  2. Kaminsky D. MD5 To Be Considered Harmful Someday. // http://eprint.iacr.org – Avaya – 06-Dec-2004.
  3. Wang X., Feng D., Lai X., Yu H. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. // http://eprint.iacr.org – Revised on August 17, 2004.
  4. Панасенко С. Алгоритм хэширования MD4. // Sec.ru. – 19.03.2012 г.
  5. Open Source Tripwire. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
  6. Laurie B., et al. The Pointlessness of the MD5 “attacks”. // Доступно на сайте http://diswww.mit.edu в архиве cryptography@c2.net – Dec 14, 2004 – Jan 5, 2005.
  7. Панасенко С. П., Батура В. П. Основы криптографии для экономистов: учебное пособие. Под ред. Л. Г. Гагариной. – М.: Финансы и статистика, 2005 – 176 с.
  8. Recent Collision Attacks on Hash Functions: ECRYPT Position Paper. // http://www.ecrypt.eu.org – Revision 1.1 – 17. February 2005.
  9. ECRYPT. Network of Excellence in Cryptology. // http://www.ecrypt.eu.org/ecrypt1.
  10. FIPS PUB 180-2. Secure Hash Standard. // http://csrc.nist.gov – National Institute of Standards and Technology – 2002 August 1.
  11. Barreto P. S. L. M., Rijmen V. The Whirlpool Hashing Function. // http://www.larc.usp.br – Revised on May 24, 2003

Рисунки:

  1. «Расширение» коллизии.
  2. Альтернативный метод «расширения» коллизии.
  3. Алгоритм Диффи-Хеллмана.

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

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