10 января 2013
Обзор атак на алгоритм хэширования MD5: поиск коллизий
Часть 3
Предыдущая часть статьи была завершена рассмотрением деталей атаки по поиску двухблочных коллизий для алгоритма MD5, опубликованной в работе [1].
Практически сразу же после появления в открытом доступе работы [1] Властимил Клима опубликовал работу [2], в которой содержалось подробное описание атаки, результаты которой были опубликованы Климой немногим ранее [3]. В данном методе также использовался дифференциальный криптоанализ с комбинацией разности, определяемой операцией XOR, и разности, определяемой операцией вычитания по модулю 232. Атака Властимила Климы требует заметно меньшей трудоемкости, чем опубликованная в [1] атака китайских криптоаналитиков:
- 233 вместо 237 операций для поиска пары первых блоков;
- 229 (с предположительной, но недоказанной возможностью улучшения до 224) вместо 230 операций для поиска пары вторых блоков.
Стоит отметить, что Властимил Клима также использовал в своей атаке технологию модификации сообщений; в [2], он утверждает, что предложил данную технологию независимо от достижений китайских специалистов. Однако, возможно, благодаря тому факту, что технические детали своей атаки Клима опубликовал на 25 дней позже, чем Ванг и Ю, изобретателями модификации сообщений считаются авторы работы [1]. Кроме того, при разработке своей атаки Клима все-таки ориентировался на ранее опубликованные коллизии [4] и попытки реконструкции неопубликованной атаки Ванг и ее коллег [5].
Использование технологии модификации сообщений при поиске коллизий проиллюстрировано на рис. 1.
Рис. 1 Использование технологии модификации сообщений
Джун Яджима (Jun Yajima) и Такеши Шимояма (Takeshi Shimoyama) в работах [6] и [7] скорректировали атаку китайских специалистов в части модификации сообщений, что не позволило им уменьшить трудоемкость атаки, но привело к нахождению двухблочных коллизий с альтернативной структурой сообщений.
В том же 2005 г. несколько специалистов из Японии опубликовали работу [8], в которой улучшили результаты предыдущих работ, предложив метод поиска коллизий, общая трудоемкость которого составляет 230 операций. Уменьшения трудоемкости авторы данного метода добились, в основном, за счет усиления технологии модификации сообщений. Аналогичных результатов добились авторы альтернативного варианта модификации сообщений, опубликовавшие практически одновременно с японскими специалистами работу [9].
Отметим, что 2005 г. оказался богат на различные исследования алгоритма MD5, многие из которых были инициированы вышедшей в 2004 г. работой [1] и посвящены некоторому качественному и количественному усилению опубликованных в ней результатов. Результаты анализа MD5 (помимо атак, посвященных поиску коллизий, были и другие результаты, которые будут рассмотрены в последующих статьях) показали не только недостаточную криптостойкость данного алгоритма хэширования, но и вызвали некоторые сомнения в том, что активно используемая с 1989 г. схема Меркля-Дамгаарда (на которой основан алгоритм MD5; подробное описание данной схемы было дано в [10]) в принципе может использоваться в качестве основы для криптографически стойких алгоритмов хэширования [11].
Кроме того, авторы работы [11] пересмотрели схему двухблочной коллизии, как показано на рис. 2 (сравните со схемой, данной на рис. 1 в [12]). В уточненной схеме видно, что в части обработки вторых блоков присутствует псевдо-коллизия, т. е. (в данном случае) получение эквивалентных результатов хэширования при произвольных начальных значениях, не совпадающих для двух хэшируемых сообщений. В результате, авторы данной работы делают вывод о том, что стойкость к нахождению псевдо-коллизий (для противодействия подобным многоблочным атакам) должна закладываться в алгоритмы хэширования на этапе их проектирования; авторы [11] при этом признают, что данное требование является достаточно жестким и сложно реализуемым на практике.
Рис. 2 Уточненная схема двухблочной коллизии
В начале следующего года вышла работа ряда специалистов из США [13], в которой наиболее подробно была описана атака китайских криптоаналитиков (более подробно, чем в первоисточнике [1]). Кроме того, авторы работы [13] предложили ряд новых идей по возможному улучшению технологии модификации сообщений и метода поиска коллизий в целом, а также опубликовали исходные тексты программы, позволяющей автоматизировать поиск коллизий по опубликованной в [13] методологии.
Практически одновременно с работой [13] вышла еще одна работа Властимила Климы [14], в которой он предложил концепцию «туннелей» в функции сжатия алгоритма MD5. Туннели можно представить как дополнительные условия, увеличивающие вероятность нахождения коллизии, которые:
- не противоречат основным условиям (условия возникновения коллизии обычно устанавливают абсолютные или относительные значения битов переменных a…d на протяжении всех итераций функции сжатия (см. описание алгоритма в [15]), не ограничивая при этом выбор значений большинства битов данных переменных);
- относительно легко могут быть удовлетворены при модификации сообщений.
Клима вводит несколько видов туннелей, каждый из которых может быть использован при нахождении коллизий:
- детерминированные туннели, существующие вне зависимости от каких-либо факторов;
- вероятностные туннели, которые могут существовать с определенной вероятностью;
- динамические туннели, использование которых может различаться в зависимости от значений определенных битов переменных a…d на определенных итерациях.
В своей работе Клима не приводит значений трудоемкости, требуемой для нахождения коллизии с использованием туннелей, но приводит экспериментальные результаты, согласно которым среднее время нахождения коллизии для MD5 на обычном персональном компьютере составляет 17 секунд, что однозначно являлось лучшим результатом на начало 2006 г.
В том же году вышла работа [16], авторы которой выполнили алгоритмизацию процесса определения условий возникновения коллизии. Входными данными для этого алгоритма являются результаты дифференциального криптоанализа в части определения оптимальных разностей между блоками сообщений и значениями переменных a…d на различных итерациях при обработке блоков. Условия возникновения коллизии до этого определялись вручную путем кропотливого и трудоемкого анализа используемых в алгоритме преобразований. Отметим, что в данной работе не были предложены какие-либо более быстрые методы нахождения коллизий по сравнению с существующими на тот момент.
Продолжение следует
Литература
- Wang X., Yu H. How to Break MD5 and Other Hash Functions. // http://citeseerx.ist.psu.edu – Shandong University, Jinan, China.
- Klima V. Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications. // http://eprint.iacr.org – March 31, 2005 – Prague, Czech Republic.
- Klima V. Finding MD5 Collisions – a Toy For a Notebook. // http://eprint.iacr.org – March 5, 2005.
- 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.
- Hawkes P., Paddon M., Rose G. G. Musings on the Wang et al. MD5 Collision. // http://eprint.iacr.org – Qualcomm Australia, Gladesville, Australia.
- Yajima J., Shimoyama T. Wang’s sufficient conditions of MD5 are not sufficient. // http://eprint.iacr.org – Fujitsu Laboratories Ltd.
- Yajima J., Shimoyama T. On the collision search and the sufficient conditions of MD5. // http://sciencelinks.jp (Abstract).
- Sasaki Y., Naito Y., Kunihiro N., Ohta K. Improved Collision Attack on MD5. // http://eprint.iacr.org – The University of Electro-Communications, Japan.
- Liang J., Lai X. Improved Collision Attack on Hash Function MD5. // http://eprint.iacr.org – Shanghai Jiao Tong University, Shanghai, China.
- Панасенко С. Алгоритм хэширования MD4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=32437 – 19.03.2012 г.
- Gauravaram P., Millan W., Neito J. G. Some thoughts on Collision Attacks in the Hash Functions MD5, SHA-0 and SHA-1. // http://eprint.iacr.org – Queensland University of Technology, Australia.
- Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 2. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=37811 – 05.12.2012 г.
- Black J., Cochran M., Highland T. A Study of the MD5 Attacks: Insights and Improvements. // http://www.cs.colorado.edu – March 3, 2006.
- Klima V. Tunnels in Hash Functions: MD5 Collisions Within a Minute. // http://eprint.iacr.org – Version 1 March 2006, version 2 April 2006 – Prague, Czech Republic.
- Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35484 – 13.08.2012 г.
- Sasaki Y., Naito Y., Yajima J., Shimoyama T., Kunihiro N., Ohta K. How to Construct Sufficient Condition in Searching Collisions of MD5. // http://eprint.iacr.org.
