19 февраля 2013
Обзор атак на приложения и протоколы, использующие алгоритм MD5
Часть 1
Продолжим обзор атак на алгоритм хэширования 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):
C0 = IV;
| Ci = Mi ⊕ ( h ( Ci-1 , Ki ) |
 |
Ci-1 ), i = 1…n, |
где:
- IV – стандартный вектор инициализации алгоритма MD5;
- n – количество блоков шифруемых данных;
- M1…Mn – 128-битные блоки шифруемых данных;
- C1…Cn – 128-битные блоки шифртекста;
- K1…Kn – фрагменты расширенного ключа, предназначенные для шифрования конкретных блоков данных (Сааринен не уточняет размер данных фрагментов и процедуру расширения ключа);
- h (x, y) – функция сжатия алгоритма MD5, где x – текущее значение регистров A…D (MD5 подробно описан в [3]), а y – хэшируемый блок данных;
-
 |
– операция пословного сложения операндов по модулю 232; |
Рис. 1 Алгоритм MDC-MD5
В своем анализе Сааринен указал на потенциальную уязвимость алгоритма 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 совпадают.
Рис. 2 Схема атаки Ондрея Микля
Наиболее интересным в данной атаке можно считать то, что, в отличие от «абстрактных» коллизий (когда формирующие коллизию сообщения не имеют осмысленного значения), опубликованных в работе [7], файлы, содержащиеся в паре архивов, имеют осмысленное значение. В работе [6] приводится пример двух осмысленных и для многих случаев актуальных сообщений, содержащихся в таких файлах:
- файл 1: «At the price of $376,495 Alf Blowfish sells his house to Ann Bonidea»;
- файл 2: «At the price of $276,495 Alf Blowfish sells his house to Ann Bonidea».
В результате данная ситуация приводит к абсолютно осмысленной и реально действующей атаке – достаточно представить, что корректный файл data.pak подписан электронной подписью на основе хэша MD5 (что вполне возможно, хотя более правильным было бы подписать не архив, а файл contract.pdf) – такая подпись будет верна и для архива с содержимым, измененным злоумышленником.
Атака Микля основана на следующей идее использования любой пары сообщений, дающих абстрактную коллизию:
- каждый из архивов data pak содержит не только файл contract.pdf, а следующую информацию:
- одно из двух сообщений, дающих коллизию;
- корректный файл contract.pdf;
- подмененный файл contract.pdf.
- специально написанный автором атаки распаковщик self-extract.exe использует различающийся бит (или один из различающихся битов, если таких несколько) сообщения, дающего коллизию, в качестве управляющего бита, значение которого указывает программе, какой из находящихся в архиве файлов contract.pdf распаковывать (см. рис. 3).
Рис. 3 Использование управляющего бита
В результате атака не накладывает ограничения ни на формат файлов с сообщениями, ни на их количество и содержимое. В [6] описан также вариант атаки с действительно самораспаковывающимся архивом, который содержит как код разархивации, так и описанный выше набор данных (см. рис. 4). Можно утверждать, что сфера применения у такой атаки существенно шире, чем у предыдущей.
Рис. 4 Атака с самораспаковывающимся архивом
Таким образом, атака Микля представляет собой пример оригинального использования коллизии алгоритма хэширования для построения практически применимой атаки против, в частности, схемы электронной подписи сообщений. Некоторые другие сценарии атаки также приведены в работе [6].
Продолжение следует
Литература
- Saarinen M.-J. O. Cryptanalysis of Block Ciphers Based on SHA-1 and MD5. // http://www.m-js.com – Helsinki University of Technology, Finland.
- Gutmann P. C. SFS. Secure FileSystem. Version 1.20. // http://web.textfiles.com – 1993-1995.
- Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35484 – 13.08.2012 г..
- Dobbertin H. Cryptanalysis of MD5 Compress. // http://cseweb.ucsd.edu – May 2, 1996 – German Information Security Agency.
- Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 1. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=37139 – 09.11.2012 г.
- Mikle O. Practical Attacks on Digital Signatures Using MD5 Message Digest. // http://eprint.iacr.org – Charles University, Prague, Czech Republic – December 2, 2004.
- 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.
