17 января 2013
Обзор атак на алгоритм хэширования MD5: поиск коллизий
Часть 4
В предыдущей части статьи были рассмотрены криптоаналитические исследования алгоритма MD5, результаты которых были опубликованы в 2005 и в начале 2006 гг. Лучшего результата на то время добился Властимил Клима, метод которого позволял найти двухблочную коллизию в среднем за 17 секунд работы персонального компьютера средней производительности [1].
Практически в то же время Марк Стивенс (Marc Stevens) опубликовал работу [2], которая была основана на более ранних исследованиях алгоритма MD5. Стивенсу удалось предложить альтернативный алгоритм поиска двухблочной коллизии со средней трудоемкостью 232,25 операций, что оказалось несколько хуже некоторых из опубликованных ранее результатов. Однако, уже в следующем году Стивенсу удалось улучшить результаты Климы: Стивенс алгоритмизировал процесс определения оптимальных разностей между переменными состояния на различных итерациях при обработке блоков; после чего он предложил более оптимальные соотношения по сравнению со всеми, предложенными ранее, в результате чего, частично использовав методы из своей более ранней работы [2], а также использовав предложенные Климой в [1] туннели (см. предыдущую часть статьи), достиг средней трудоемкости нахождения двухблочной коллизии, составляющей 223,5 операций. В результате среднее время поиска двухблочной коллизии на обычном персональном компьютере сократилось до четырех секунд [3].
Между двумя работами Стивенса был предложен еще один альтернативный метод (в части модификации сообщений) поиска коллизий для MD5 в работе [4]; ее авторам удалось достичь трудоемкости 229 операций, что также было улучшено Стивенсом в [3].
Тао Кси (Tao Xie) и другие авторы вышедшей в конце 2007 г. работы [5] отметили, что все недавние успешные атаки, направленные на поиск коллизии для алгоритма MD5, использовали одни и те же значения разности хэшируемых блоков ΔM0 и ΔM1 и переменных состояния после обработки первой пары блоков, а именно те значения, которые были описаны Ванг и Ю в работе [6] (см. описание в [7]). В работе [5] были предложены принципы поиска оптимальных разностей, а также альтернативный вариант разностей:
ΔM0 = (0, 0, 0, 0, 0, 0, -28, 0, 0, 231, 0, 0, 0, 0, 0, 231),
ΔM1 = (0, 0, 0, 0, 0, 0, 28, 0, 0, 231, 0, 0, 0, 0, 0, 231),
а разность между каждой парой переменных состояния A…D после обработки первой пары блоков составляет 231 - 223. На основе этих разностей были разработаны критерии возникновения коллизии и предложена атака, трудоемкость которой составила 236 операций, что оказалось значительно хуже результатов более ранних работ, в частности, [1] и [3].
Несколько позже, но также в 2008 г. тот же коллектив авторов опубликовал еще одну работу [8], в которой было предложено множество разностей между парами блоков, которые могли бы быть использованы при нахождении коллизий для MD5. В [8] было отмечено, что предыдущие разности ΔM0 и ΔM1, предложенные в работах [6] и [5], были трехбитовыми (т. е. блоки сообщений Mx и Mx’ различались значениями трех битов), что, вероятно, не является оптимальным при поиске коллизий. В результате в работе [8] была предложена атака, основанная на следующих разностях между блоками:
ΔM0 = (0, 0, 0, 0, 0, 0, 0, 0, 231, 0, 0, 0, 0, 0, 0, 0),
ΔM1 = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
а разность между каждой парой переменных состояния A…D после обработки первой пары блоков составляет 231. Т. е. разность между первыми блоками является однобитовой, а вторые блоки дающих коллизию сообщений эквивалентны. Схема такой коллизии приведена на рис. 1.
Отметим, что, фактически, в части обработки вторых блоков сообщений атака использует именно тот вид псевдо-коллизии для функции сжатия алгоритма MD5, который предложили ден Боер и Босселаерс еще в 1993 г. в [9] – сравните данный рисунок с рис. 1 в [10], где дается описание такой псевдо-коллизии.
Рис. 1 Двухблочная коллизия с эквивалентными вторыми блоками
Трудоемкость атаки составила в среднем 220,96 операций; для ее осуществления требовалось меньше секунды работы неспециализированного компьютера. Авторы [8] особо отметили, что данная трудоемкость атаки уже позволяет выполнять атаки «на лету», т. е. в процессе работы используемых на практике протоколов (данная тема будет подробно обсуждаться в последующих статьях).
Отметим, что идея об использовании однобитовых разностей была высказана ранее коллективом японских специалистов в работе [11], в которой была представлена атака по поиску коллизий для MD5, основанная на однобитовых разностях, с трудоемкостью 242 операций. В [8] Тао Кси и его коллегам удалось использовать данную идею для построения атаки с принципиально меньшей трудоемкостью.
Отметим также вышедшую в 2008 г. работу [12], авторы которой использовали туннели [1] и алгоритм, предложенный Стивенсом в [3], для разработки новой атаки по поиску двухблочной коллизии для MD5 (с использованием альтернативных трехбитовых разностей), но не улучшили опубликованные в [8] результаты.
В 2009 г. вышла работа интернационального коллектива криптологов с участием упомянутого ранее Марка Стивенса [13], в которой в части поиска двухблочных коллизий для MD5 были существенно улучшены результаты работы [8] – теперь для данной атаки на MD5 требуется не более 216 операций (для атаки была использована четырехбитовая разность между первыми блоками). Таким образом, успешный поиск коллизий стал измеряться в миллисекундах работы компьютера.
Следующего прорыва в поиске коллизий для MD5 добились Тао Кси и Денггуо Фенг (Dengguo Feng) в вышедшей в том же году работе [14]. Они предложили разделить все вероятностные условия возникновения коллизии на несколько (n) независимых (не влияющих друг на друга) групп; в результате такого разделения общая трудоемкость атаки (C) будет являться суммой трудоемкостей C1…Cn, требуемых для удовлетворения групп условий:
Следовательно, порядок общей трудоемкости атаки будет определяться максимальным из значений C1…Cn, а главной задачей успешной атаки на MD5 стала оптимальная группировка условий возникновения коллизий. Основные результаты, достигнутые с использованием данной концепции, таковы [14]:
- найдены два варианта разностей первых блоков, каждый из которых приводит к атаке с трудоемкостью 210 операций:
ΔM0 = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 231, 0, 0, 0, 0),
ΔM0 = (0, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 231, 0);
- впервые предложена разность сообщений, на основе которой может быть найдена одноблочная коллизия (что, однако, в работе [14] не было доказано):
ΔM = (0, 0, 0, 0, 0, 210, 0, 0, 0, 0, 231, 0, 0, 0, 0, 0).
В декабре 2010 г. Тао Кси и Денггуо Фенг опубликовали короткое сообщение [15], в котором привели пример одноблочной коллизии; формирующие коллизию сообщения имеют именно приведенную выше двухбитовую разность. В [15] сказано, что детали атаки пока не могут быть опубликованы.
Кси и Фенг предложили приз в размере 10 000 долларов США криптоаналитику, который сможет до 1 января 2013 г. предложить альтернативную одноблочную коллизию для MD5. Данный приз получил Марк Стивенс, который опубликовал в январе 2012 г. работу [16]. В данной работе было приведено описание атаки, а также дан пример одноблочной коллизии для алгоритма MD5, основывающейся на альтернативной разности сообщений:
ΔM = (0, 0, 0, 0, 0, 0, 0, 0, 225, 0, 0, 0, 0, 231, 0, 0).
Средняя трудоемкость атаки Стивенса составила 249,8 операций.
На текущий момент (конец декабря 2012 г.) работы [14] и [16] представляют наилучшие опубликованные атаки на алгоритм MD5 в части поиска двухблочных и одноблочных коллизий соответственно. Однако, возможно, что неопубликованная (анонсированная в [15]) атака Кси и Фенга обладает меньшей трудоемкостью, чем описанная в [16] атака Стивенса.
Литература:
- 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.
- Stevens M. Fast Collision Attack on MD5. // http://eprint.iacr.org – Eindhoven University of Technology, Eindhoven, The Netherlands.
- Stevens M. M. J. On Collisions for MD5. Master’s Thesis. // http://www.win.tue.nl – Eindhoven University of Technology – June 2007.
- Sasaki Y., Naito Y., Kunihiro N., Ohta K. Improved Collision Attacks on MD4 and MD5. // http://dl.acm.org (Abstract) – University of Electro-Communications, Japan – January 2007.
- Xie T., Feng D., Liu F. A New Collision Differential For MD5 With Its Full Differential Path. // http://eprint.iacr.org.
- Wang X., Yu H. How to Break MD5 and Other Hash Functions. // http://citeseerx.ist.psu.edu – Shandong University, Jinan, China.
- Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 2. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=37811 – 05.12.2012 г.
- Xie T., Liu F., Feng D. Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5? // http://eprint.iacr.org.
- Den Boer B., Bosselaers A. Collisions for the compression function of MD5. // http://citeseerx.ist.psu.edu – 23 July 1993.
- Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 1. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=37139 – 09.11.2012 г.
- Sasaki Y., Wang L., Kunihiro N., Ohta K. New Message Differences for Collision Attacks on MD4 and MD5. // http://dl.acm.org (Abstract) – January 2008.
- Vabek J., Joscak D., Bohacek M., Tuma J. A New type of 2-Block Collisions in MD5. // http://link.springer.com (Abstract) – Charles University in Prague, Czech Republic – 2008.
- Stevens M., Sotirov A., Appelbaum J., Lenstra A., Molnar D., Osvik D. A., de Weger B. Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate. // http://marc-stevens.nl – 2009.
- Xie T., Feng D. How To Find Weak Input Differences For MD5 Collision Attacks. // http://eprint.iacr.org.
- Xie T., Feng D. Construct MD5 Collisions Using Just A Single Block Of Message (Announcement). // http://eprint.iacr.org – December 2010.
- Stevens M. Single-block collision attack on MD5. // http://marc-stevens.nl – Cryptology Group, CWI, Amsterdam, The Netherlands – January 29, 2012.
