|
Обзор атак на приложения и протоколы, использующие алгоритм 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):
где:
– операция пословного сложения операндов по модулю 232;В своем анализе Сааринен указал на потенциальную уязвимость алгоритма MDC-MD5 (проистекающую благодаря найденным Хансом Доббертином коллизиям функции сжатия алгоритма MD5 [4] – подробно см. в [5]), которая может привести к атаке на данный алгоритм, направленной на вычисление ключа шифрования, с трудоемкостью, меньшей трудоемкости полного перебора ключей. Конкретные детали атаки в работе [1] не были приведены. Кроме того, Сааринен отметил, что подобные атаки сильно зависят от конкретной используемой схемы расширения ключа шифрования (т. е. процедуры вычисления K1…Kn из исходного ключа). В последующих исследованиях тема анализа алгоритма 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].
Литература
Рисунки:
