09 ноября 2012
Обзор атак на алгоритм хэширования MD5: поиск коллизий
Часть 1
За время активного использования алгоритма MD5 было предпринято множество попыток атаковать данный алгоритм. История криптоанализа MD5 весьма многогранна. Она тесно переплетается с криптоанализом ряда других алгоритмов хэширования (в том числе, рассмотренного ранее MD4); можно утверждать, что многие достижения в криптоанализе алгоритмов хэширования и успешные атаки на их применения были сделаны благодаря алгоритму MD5 и его популярности, весьма привлекавшей криптоаналитиков со всего мира.
Начнем с обзора атак на MD5, посвященных поиску коллизий.
Первая известная работа по криптоанализу MD5 была представлена Томасом Берсоном (Thomas A. Berson) в 1992 г. [1]. Поскольку в каждой итерации алгоритма MD5 активно применяются операции сложения по модулю 232, Берсон предложил использовать дифференциальный криптоанализ с разностью между обрабатываемыми данными, определяемой операцией вычитания по модулю 232, а не операцией XOR, активно применяемой в то время для дифференциального криптоанализа различных алгоритмов шифрования и хэширования – см., например, [2]. Предложенный Берсоном метод позволяет крайне легко анализировать результаты операций сложения по модулю 232, но усложняет анализ используемого в итерации MD5 побитового циклического сдвига, а также раундовых функций fj(), которые основаны на побитовых логических операциях. Берсон предложил методы, упрощающие анализ циклического сдвига и раундовых функций по модулю 232, а также привел пример их успешного применения для нескольких итераций алгоритма, что, однако, не было им распространено ни на функцию сжатия алгоритма MD5, ни на MD5 в целом.
Криптоанализ MD5 продолжили в 1993 г. ден Боер и Босселаерс (авторы упоминавшейся ранее работы [3] по криптоанализу MD4). В своей работе [4] они показали, что следующие изменения в MD5 по сравнению с MD4 не усилили криптостойкость алгоритма:
- Уникальность модифицирующих констант Tj не оказалась заметным усилением благодаря их происхождению:
Tj = trunc(abs(sin(j)) * 232),
где j (номер итерации) берется в радианах. Ден Боер и Босселаерс заметили, что в этом случае любые четыре последовательные константы Tj связаны простым соотношением, поскольку:
(sin(j) + sin(j + 2)) * sin(j + 2) = (sin(j + 1) + sin(j + 3)) * sin(j + 1)
Однако, стоит отметить, что при формировании констант Tj из значений синусов присутствует операция trunc(), следовательно, в аналогичном соотношении между последовательными константами Tj в лучшем случае возможно лишь приблизительное равенство, а не строгое, т. е.:
(Tj + Tj+2) * Tj+2 » (Tj+1 + Tj+3) * Tj+1
что видно на примере констант T22…T25. Причем, это редкий случай, когда функции sin(j)…sin(j + 3) дают результат с одинаковым знаком; в подавляющем большинстве случаев знак результатов выполнения данных функций различен, тогда в соотношение вмешивается функция abs(), полностью меняющая результаты вычислений, что делает невозможным использование приведенного выше соотношения на практике, что можно наблюдать на примере констант T1…T4.
- Сложение по модулю 232 с модифицируемой на предыдущей итерации переменной b ослабило алгоритм: авторы работы [4] показали, что данное нововведение можно использовать для нахождения псевдо-коллизий для функции сжатия алгоритма MD5 (в данном случае – двух различных значений состояния (регистров A…D), приводящих к коллизии функции сжатия при одном и том же значении расширенного блока данных, – см. рис. 1, на котором h() обозначает функцию сжатия алгоритма MD5) с незначительной трудоемкостью (216 операций). Этот результат также был подвергнут сомнению специалистами компании RSA Laboratories, которые в [5] утверждали, что данный (весьма специфический) вид псевдо-коллизии принципиально невозможно расширить до какой-либо атаки на алгоритм в целом.
Рис. 1 Псевдо-коллизия функции сжатия алгоритма MD5
В 1996 г. вышла работа Ханса Доббертина [6], в которой была приведена коллизия для функции сжатия алгоритма MD5 (т. е. два различных блока данных, приводящих к коллизии функции сжатия при фиксированном состоянии – см. рис. 2). По мнению Доббертина, данного результата было достаточно для пересмотра мнения о высокой криптостойкости алгоритма MD5 и для перехода с MD5 на какой-либо более стойкий алгоритм хэширования. Отметим, что алгоритм MD5 активно использовался, как минимум, в течение десяти лет после выхода данной работы, а в ряде применений используется и до сих пор.
Рис. 2 Коллизия функции сжатия алгоритма MD5
В вышедшей несколько позже работе [7] Доббертин пояснил технические детали атаки, позволившей найти коллизию, приведенную в работе [6]. Атака состоит в поиске двух блоков данных, незначительно (значением одного бита) различающихся в слове M[14], и выполняется следующим образом:
- слово M[14] первый раз используется в итерации 15, до которой обработка блоков идет идентично;
- цель первой фазы атаки состоит в подборе блоков данных таким образом, чтобы повторная обработка различающихся слов M[14] в итерации 26 привело к внутренней коллизии – эквивалентным значениям переменных a…d;
- аналогичным образом, до следующего использования слова M[14] в итерации 36 обработка блоков идентична, поскольку данные слово между итерациями 26 и 36 не используется;
- вторая фаза атаки – нахождение второй внутренней коллизии на итерации 51, на которой в последний раз используется слово M[14]; дальнейшая обработка дает эквивалентный результат, т. е. коллизию функции сжатия алгоритма MD5.
В той же работе Доббертин высказал уверенность в том, что MD5 не должен далее использоваться в приложениях электронной подписи и аналогичных, где требуется высокая криптостойкость алгоритма хэширования против нахождения коллизий. Использование MD5 в качестве однонаправленной хэш-функции и в HMAC-конструкциях на тот момент пока еще считалось безопасным.
Судя по тому, что работа Доббертина [7] была опубликована в официальном техническом бюллетене компании RSA Security (RSA Laboratories’ CryptoBytes), компания RSA согласилась с выводами и рекомендациями Ханса Доббертина.
Продолжение следует
Литература
- Berson T. A. Differential Cryptanalysis Mod 232 with Applications to MD5. // http://www.anagram.com – Anagram Laboratories, Palo Alto, CA, USA.
- Biham E., Shamir A. Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. // http://www.cs.technion.ac.il – The Weizmann Institute of Science, Rehovot, Israel.
- Den Boer B., Bosselaers A. An Attack on the Last Two Rounds of MD4. // http://citeseerx.ist.psu.edu – 15 October 1991.
- Den Boer B., Bosselaers A. Collisions for the compression function of MD5. // http://citeseerx.ist.psu.edu – 23 July 1993.
- Kaliski B. S. Jr., Robshaw M. J. B. On “Pseudocollisions” in the MD5 Message-Digest Algorithm. // http://www.cs.ucdavis.edu – April 23, 1993 – RSA Laboratories, Redwood City, CA, USA.
- Dobbertin H. Cryptanalysis of MD5 Compress. // http://cseweb.ucsd.edu – May 2, 1996 – German Information Security Agency.
- Dobbertin H. The Status of MD5 After a Recent Attack. // http://ftp.rsasecurity.com – German Information Security Agency – Bonn, Germany (опубликовано в RSA Laboratories’ CryptoBytes – 1996 – volume 2, number 2, pp. 1-6).
Об авторе:
Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.
С автором можно связаться: по телефонам (499)731-0000, (499)731-2050
или по E-mail serg@panasenko.ru
