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

Rambler's Top100

OZON.ru

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

Карта сайта

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

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

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

 

Продолжим обзор атак на алгоритм хэширования MD5. Данная статья посвящена атакам на различные приложения и протоколы, в которых используется или использовался данный алгоритм, а также атакам на различные надстройки над алгоритмом MD5. Рассмотрим именно те атаки, которые эксплуатируют особенности или слабости алгоритма MD5, а не какие-либо другие возможные уязвимости конкретного протокола или приложения.

Атаки на различные применения алгоритма MD5 достаточно тесно переплетаются с рассмотренными в предыдущих статьях атаками по поиску коллизий и прообразов для данного алгоритма. Многие атаки на применения конструировались на основе атак по поиску коллизий, после чего, в ряде случаев, успешные атаки на применения давали толчок криптоаналитикам для усиления результатов атак по поиску коллизий и т. д.

Первой широко известной работой, посвященной криптоанализу специфичного применения MD5, можно считать работу Марку-Юхани Сааринена (Markku-Juhani Saarinen) [1], вышедшую в 2003 г. Данная работа рассматривает несколько вариантов надстроек над алгоритмами хэширования, позволяющих использовать их в качестве алгоритмов блочного шифрования. Одна из таких надстроек – алгоритм MDC-MD5, позволяющий шифровать данные с помощью алгоритма хэширования MD5.

Надстройка MDC (Message Digest Cipher – шифр на основе дайджеста сообщения) была предложена в 1993 г. Питером Гутманом (Peter Gutmann) и использована в качестве алгоритма шифрования (на основе алгоритма хэширования SHA-1) в разработанной Гутманом файловой системе SFS (Secure FileSystem), поддерживающей прозрачное (т. е. автоматически выполняемое по мере необходимости) шифрование файлов [2]. Сааринен предложил аналогичную надстройку над алгоритмом MD5, определенную в [1] следующим образом (см. рис. 1):

MDC-MD5

где:

В своем анализе Сааринен указал на потенциальную уязвимость алгоритма MDC-MD5 (проистекающую благодаря найденным Хансом Доббертином коллизиям функции сжатия алгоритма MD5 [4] – подробно см. в [5]), которая может привести к атаке на данный алгоритм, направленной на вычисление ключа шифрования, с трудоемкостью, меньшей трудоемкости полного перебора ключей. Конкретные детали атаки в работе [1] не были приведены. Кроме того, Сааринен отметил, что подобные атаки сильно зависят от конкретной используемой схемы расширения ключа шифрования (т. е. процедуры вычисления K1Kn из исходного ключа). В последующих исследованиях тема анализа алгоритма MDC-MD5 не поднималась.

Прорывом в части атак на применения алгоритма MD5 стала вышедшая в 2004 г. работа Ондрея Микля (Ondrej Mikle) [6]. Ее автор был вдохновлен коллизиями, опубликованными китайскими специалистами в работе [7]. Он использовал коллизии для конструирования пар самораспаковывающихся архивов с совпадающими хэш-значениями, вычисленными по алгоритму MD5, при этом входящие в архивы файлы имеют различное содержимое. Схема атаки Микля приведена на рис. 2. Отметим, что в данном случае автор несколько неверно использует понятие «самораспаковывающийся архив» (self-extract archive): на самом деле, в работе [6] имеется в виду, что программа self-extract.exe является распаковщиком, использующим в качестве входных данных архивы data.pak. Файлы data.pak являются различными (поскольку различаются файлы contract.pdf), но их хэши MD5 совпадают.

Наиболее интересным в данной атаке можно считать то, что, в отличие от «абстрактных» коллизий (когда формирующие коллизию сообщения не имеют осмысленного значения), опубликованных в работе [7], файлы, содержащиеся в паре архивов, имеют осмысленное значение. В работе [6] приводится пример двух осмысленных и для многих случаев актуальных сообщений, содержащихся в таких файлах:

В результате данная ситуация приводит к абсолютно осмысленной и реально действующей атаке – достаточно представить, что корректный файл data.pak подписан электронной подписью на основе хэша MD5 (что вполне возможно, хотя более правильным было бы подписать не архив, а файл contract.pdf) – такая подпись будет верна и для архива с содержимым, измененным злоумышленником.

Атака Микля основана на следующей идее использования любой пары сообщений, дающих абстрактную коллизию:

В результате атака не накладывает ограничения ни на формат файлов с сообщениями, ни на их количество и содержимое. В [6] описан также вариант атаки с действительно самораспаковывающимся архивом, который содержит как код разархивации, так и описанный выше набор данных (см. рис. 4). Можно утверждать, что сфера применения у такой атаки существенно шире, чем у предыдущей.

Таким образом, атака Микля представляет собой пример оригинального использования коллизии алгоритма хэширования для построения практически применимой атаки против, в частности, схемы электронной подписи сообщений. Некоторые другие сценарии атаки также приведены в работе [6].

Литература

  1. Saarinen M.-J. O. Cryptanalysis of Block Ciphers Based on SHA-1 and MD5. // http://www.m-js.com – Helsinki University of Technology, Finland.
  2. Gutmann P. C. SFS. Secure FileSystem. Version 1.20. // http://web.textfiles.com – 1993-1995.
  3. Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – 13.08.2012 г.
  4. Dobbertin H. Cryptanalysis of MD5 Compress. // http://cseweb.ucsd.edu – May 2, 1996 – German Information Security Agency.
  5. Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 1. // Sec.ru. – 09.11.2012 г.
  6. Mikle O. Practical Attacks on Digital Signatures Using MD5 Message Digest. // http://eprint.iacr.org – Charles University, Prague, Czech Republic – December 2, 2004.
  7. 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.

Рисунки:

  1. Алгоритм MDC-MD5.
  2. Схема атаки Ондрея Микля.
  3. Использование управляющего бита.
  4. Атака с самораспаковывающимся архивом.

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