04 июня 2012

Алгоритм хэширования MD4: обзор криптоаналитических исследований

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

Криптоанализ алгоритма MD4 во многом шел параллельно с криптоанализом более поздних алгоритмов, частично унаследовавших от MD4 его структуру и используемые в нем преобразования. Прежде всего, это алгоритм MD5 (алгоритму MD5 будут посвящены последующие статьи данного цикла), а также бывшие стандарты хэширования США SHA-0 и SHA-1; данные алгоритмы описаны в документах [1] и [2]. Несмотря на тесную взаимосвязь подходов и методов, используемых в атаках на эти (и некоторые другие) алгоритмы хэширования, попробуем рассмотреть основные результаты криптоанализа именно в применении к алгоритму MD4.

Исследования усеченных вариантов MD4

Начало атакам на алгоритм MD4, направленным на поиск коллизии, положила работа Берта ден Боера (Bert den Boer) и Антоона Босселаерса (Antoon Bosselaers) [3], вышедшая уже на следующий год после опубликования алгоритма MD4 [4] – в 1991 г. Ее авторы использовали неопубликованную идею, высказанную известным криптологом Ральфом Мерклем (Ralph Merkle) в 1990 г., о том, что укороченный вариант алгоритма с двумя первыми раундами вместо трех (под «раундом» здесь и далее понимается совокупность 16 итераций алгоритма MD4, использующих одну и ту же функцию f_j (), т. е. раунд формируют итерации 0…15, 16…31 или 32…47) является крайне слабым: для 99,99 % значений векторов инициализации такого алгоритма легко найти два сообщения с одним и тем же хэш-значением, т. е. найти коллизию. Ден Боер и Босселаерс алгоритмизировали вычисление коллизий для MD4 с двумя первыми раундами, а также предложили аналогичную атаку на вариант MD4 с двумя последними раундами. Данная атака на усеченный алгоритм MD4 позволяет находить пары 512-битных сообщений с одинаковым хэшем; сообщения каждой такой пары эквивалентны в восьми 32-битных словах, в остальных же различаются на определенную величину.

Отметим, что в [3] авторы атаки утверждали о невозможности ее распространения на полнораундовый алгоритм MD4. Однако, в [5] Серж Воденэ (Serge Vaudenay) утверждает, что данная атака при ее применении к полнораундовому алгоритму MD4 дает возможность получить near-коллизию (т. е. два сообщения с почти одинаковыми – различающимися несколькими битами – хэш-значениями). Near-коллизии в дальнейшем могут быть использованы в контексте некоторых атак на алгоритм хэширования (near-коллизии были использованы, например, в работе [6], где описана позволяющая найти коллизию многоблочных сообщений атака на алгоритм SHA-0, на первом этапе которой используется именно поиск near-коллизии – см. рис. 1), но от нахождения near-коллизии до реального поиска коллизий все-таки еще весьма далеко. Кроме того, Воденэ предложил альтернативный метод поиска коллизий для укороченного алгоритма MD4 без третьего раунда, который также позволяет найти near-коллизию (при различающихся 16 битах хэш-значения) для полнораундового MD4.

Рис. 1 Использование near-коллизии для поиска коллизии двухблочных сообщений

В 1997 г. Ханс Доббертин (Hans Dobbertin) предложил первую атаку, направленную на поиск первого и второго прообраза¹ для укороченного (без третьего раунда) алгоритма MD4 [7]. Данная атака является реализуемой на практике, позволяя вычислить прообраз менее, чем за час на обычном персональном компьютере. Детали атаки Доббертина описаны в [8]. Атака основана на неблагоприятном свойстве функции f_j (x, y, z) = (x & y) | (x & z) | (y & z), применяемой во втором раунде алгоритма MD4: если любые две входные переменные имеют эквивалентные значения, то результат данной функции не зависит от значения третьей переменной. Доббертин также предположил, что аналогичным образом атакуется и вариант алгоритма MD4 без первого раунда, поскольку в этом варианте также используется описанная выше функция f_j ().

Поиск коллизий

Первый метод поиска коллизий для полнораундового алгоритма MD4 был предложен Хансом Доббертином в работе [9] (в открытой литературе подробное описание метода Доббертина можно найти, например, в [10]). Согласно [10], основная идея метода – представление функции сжатия алгоритма MD4 в виде системы уравнений, описывающих соотношения между следующими величинами:

значениями регистров A…D или временных переменных a…d на различных этапах работы алгоритма;
словами хэшируемого сообщения.

Такие системы уравнений обычно оказываются весьма громоздкими и крайне сложными для решения (если решение в принципе возможно). Похожим путем шли и авторы упомянутых выше работ [3] и [5], атакуя укороченные варианты MD4. Однако, Доббертину удалось, путем ввода специфических ограничений на значения величин, значительно упростить систему уравнений до решаемого вида. Одним из таких ограничений являлась «внутренняя коллизия» (inner collision) двух сообщений – ситуация, когда совпадали промежуточные значения переменных a…d при хэшировании двух сообщений. Аналогичным образом, Доббертин ввел и использовал понятие «внутренняя near-коллизия» (inner almost collision²). В результате, атака Доббертина на MD4 позволяет вычислять пары сообщений с одинаковым хэш-значением; сообщения в каждой паре являются одноблочными, с совпадающими всеми словами, кроме одного. Трудоемкость вычисления пары сообщений эквивалентна 220 операциям хэширования, т. е. весьма невелика. Графически метод Доббертина изображен на рис. 2. Отметим, что метод Доббертина оказался также применим и к расширенному алгоритму MD4 (описанному в предыдущей статье варианту MD4 с 256-битным хэшем).

¹Первым прообразом называют сообщение, результат хэширования которого равен заданному хэш-значению. Вторым прообразом называют сообщение, результат хэширования которого равен результату хэширования заданного сообщения. Контексты и методы атак, направленных на поиск первого и второго прообраза, могут различаться.

² Впоследствии более широко применялся термин «near collision» вместо «almost collision».

Рис. 2 Метод Доббертина

В ответ на атаку Доббертина компания RSA выпустила официальный бюллетень [11], в котором констатировала, что лежащие в основе алгоритма MD4 решения «представляют собой неоправданный компромисс между безопасностью и скоростью». Вследствие этого, компания RSA порекомендовала не использовать алгоритм MD4 в дальнейшем, а использовать вместо него алгоритм MD5, «обладающий более консервативным дизайном» (отметим, что всего двумя годами позже вышла работа известных экспертов [8], в которой рекомендовалось отказаться и от алгоритма MD5 в силу его недостаточной криптостойкости). Несмотря на это, алгоритм MD4 использовался в различных приложениях достаточно долго (обзору применений MD4 будет посвящена одна из следующих статей данного цикла).
В 1997 г. Кассельман (P. R. Kasselman) в работе [12] предложил альтернативный алгоритм использования внутренних near-коллизий, позволяющий в 64 раза уменьшить трудоемкость вычисления коллизии методом Доббертина. Однако, работа Кассельмана не получила широкой известности.

В 2004 и последующих годах вышел ряд работ китайских криптоаналитиков под руководством профессора Ксиаоюн Ванг (Xiaoyun Wang), в которых были представлены новые атаки на алгоритм MD4, в частности:

В работе [13] (2004 г.) были анонсированы новые методы поиска коллизий (с примерами коллизий) для ряда алгоритмов хэширования, в том числе, для алгоритма MD4; описание данных методов было представлено в последующих работах.
Один из новых методов поиска коллизий для алгоритма MD4 был описан в работе [14] (2005 г.). Данный метод использовал дифференциальный криптоанализ³ и позволял найти коллизию с крайне низкой трудоемкостью; суть метода в следующем:
с помощью дифференциального криптоанализа авторы нашли необходимое соотношение между сообщениями, приводящее к коллизии;
поскольку найденное соотношение давало коллизию с крайне низкой вероятностью – 2¹²², авторы атаки применили технологию модификации сообщений⁴, которая позволила очень сильно увеличить вероятность коллизии – до 2⁶ – 2².

Общая трудоемкость нахождения коллизии с помощью данного метода не превышает 28 операций. Т. е. метод значительно эффективнее опубликованных ранее методов Доббертина и Кассельмана и позволяет мгновенно находить коллизии для алгоритма MD4.
В том же 2005 г. вышла работа ряда японских ученых [17] в которой метод поиска коллизий, представленный в работе [14], был значительно усилен за счет улучшенной модификации сообщений. Усиленный метод позволял находить коллизии с еще меньшей трудоемкостью (не более трех операций) и со значительно увеличенной вероятностью, почти равной 1.

³Дифференциальный криптоанализ – один из методов анализа алгоритмов симметричного шифрования [15]. Он основан на анализе пар открытых текстов, между которыми существует определенная разность (difference). Разность обычно определяется как результат применения операции XOR к анализируемым текстам (но может быть и определена иначе – например, как результат их вычитания по модулю 232). С некоторыми изменениями дифференциальный криптоанализ используется для анализа алгоритмов хэширования.

⁴Технология модификации сообщений (message modification) направлена на увеличение вероятности нахождения коллизии путем модификации различных фрагментов сообщений с целью достижения ими определенных критериев [16].

В 2006 г. Мартин Шлаффер (Martin Schlaffer) и Элизабет Освальд (Elisabeth Oswald) отметили, что поиск оптимальных соотношений между парами сообщений, лежащий в основе дифференциального криптоанализа алгоритма MD4 до сих пор велся «вручную, под большим влиянием интуиции» [18]. Шлаффер и Освальд в работе [18] предложили алгоритм, позволяющий находить такие соотношения автоматизированным путем; в подтверждение корректности данного алгоритма они предложили более тысячи соотношений для дифференциального криптоанализа MD4, причем, по мнению авторов данного алгоритма, некоторые из соотношений более оптимальны, чем использованные ранее, для дальнейшего анализа с помощью технологии модификации сообщений. В следующем году вышла еще одна работа ряда французских криптоаналитиков [19], в которой был предложен альтернативный, полностью автоматизированный алгоритм (алгоритм Шлаффера и Освальд требовал выполнения некоторых ручных операций) поиска соотношений для дифференциального криптоанализа MD4. Новый алгоритм позволял задавать некоторые характеристики для искомых соотношений, что полезно при поиске соотношений, оптимальных для различных контекстов атак на MD4 (алгоритм был использован в ряде атак на надстройки над MD4, об этих атаках – в одной из следующих статей).
В том же 2007 г. вышла работа [20], в которой, с учетом опыта предыдущих атак на MD4, была предложена более оптимальная внутренняя коллизия, использование которой позволило мгновенно (не более двух операций хэширования) находить коллизию для всех сообщений.

Литература

FIPS PUB 180. Secure Hash Standard. // http://security.isu.edu – National Institute of Standards and Technology – 1993 May 11.
FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.
Den Boer B., Bosselaers A. An Attack on the Last Two Rounds of MD4. // http://citeseerx.ist.psu.edu – 15 October 1991.
Rivest R. RFC 1186: The MD4 Message Digest Algorithm. // http://www.ietf.org – MIT Laboratory for Computer Science – October 1990.
Vaudenay S. On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER. // http://citeseer.ist.psu.edu – Ecole Normale Superieure – November 1994.
Biham E., Chen R, Joux A., Carribault P., Lemuet C., Jalby W. Collisions of SHA-0 and Reduced SHA-1. // http://www.iacr.org.
Dobbertin H. The First Two Rounds of MD4 are Not One-Way. // http://cseweb.ucsd.edu – German Information Security Agency – March 21, 1997.
Van Rompay B., Preneel B., Vandewalle J. On the security of dedicated hash functions. // http://citeseerx.ist.psu.edu – Katholieke Universiteit Leuven, Heverlee, Belgium.
Dobbertin H. Cryptanalysis of MD4 (Abstract). // http://www.springerlink.com – German Information Security Agency, Bonn, Germany – 23 October 1995 – Journal of Cryptology (1998) 11: 253-271.
Daum M. Cryptanalysis of Hash Functions of the MD4-Family. // http://www.cits.rub.de – Ruhr-Universitat Bochum – May 2005.
Robshaw M. J. B. On Recent Results for MD2, MD4, and MD5. // ftp://ftp.rsa.com – RSA Laboratories’ Bulletin – #4 – November 12, 1996.
Kasselman P. R. A Fast Attack on the MD4 Hash Function. // http://www.mathcs.emory.edu – Ciphertec – 1997.
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.
Wang X., Lai X., Feng D., Chen H., Yu X. Cryptanalysis of the Hash Functions MD4 and RIPEMD. // http://www.infosec.sdu.edu.cn – 2005.
Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems. // http://citeseer.ist.psu.edu – The Weizmann Institute of Science, Israel – July 19, 1990.
Wang X., Yu H. How to Break MD5 and Other Hash Functions. // http://citeseerx.ist.rsu.edu – Shandong University, Jinan, China.
Naito Y., Sasaki Y., Kunihiro N., Ohta K. Improved Collision Attack on MD4. // http://eprint.iacr.org – The University of Electro-Communications, Japan.
Schlaffer M., Oswald E. Searching for Differential Paths in MD4. // http://www.iacr.org – Graz University of Technology, Graz, Austria.
Fouque P.-A., Leurent G., Nguyen P. Automatic Search of Differential Path in MD4. // http://events.iaik.tugraz.at – Ecole Normale Superieure, Paris, France.
Sasaki Y., Wang L., Ohta K., Kunihiro N. New Message Difference for MD4. // http://www.iacr.org – The University of Electro-Communications, Tokyo, Japan.