24 января 2013

Обзор атак на алгоритм хэширования MD5: поиск прообразов

Продолжим обзор атак на алгоритм хэширования MD5. Рассмотрим атаки по поиску прообразов.
Первые из работ, посвященных поиску прообразов для алгоритма MD5, – это работы коллектива специалистов из исследовательского подразделения компании Microsoft – Microsoft Research [1-2], опубликованные в 2007 г. В данных работах был предложен алгоритм инвертирования функции сжатия алгоритма MD5. Авторы отметили, что:

множество возможных сообщений бесконечно, тогда как множество хэш-значений для 128-битного алгоритма хэширования содержит 2¹²⁸ элементов;
предполагая, что алгоритм хэширования равномерно распределяет множество входных значений между 2¹²⁸ выходными значениями, можно утверждать, что любое конкретное выходное значение h имеет бесконечное количество прообразов (т. е. сообщений, хэш которых эквивалентен заданному);
следовательно, если зафиксировать определенным образом часть сообщения (т. е. искомого прообраза), то существует возможность определить искомый одноблочный прообраз, вычислив оставшиеся его биты (см. рис. 1).

width=

Рис. 1 Подход к поиску одноблочного прообраза

Фиксируя определенные биты искомого прообраза (что, в частности, необходимо для формирования корректного дополнения сообщения, если атака направлена на полнораундовый алгоритм, – см. описание алгоритма MD5 в [3]) и сводя задачу инвертирования итераций функции сжатия к задаче выполнимости булевых формул, авторы данных работ предложили атаку, позволяющую вычислить первый прообраз (т. е. сообщение, хэш которого эквивалентен заданному) для усеченной функции сжатия алгоритма MD5 с 26 итерациями; трудоемкость данной атаки в работах [1] и [2] не указана.
Результаты специалистов Microsoft Research были усилены в опубликованной в 2008 г. работе Ю Сасаки (Yu Sasaki) и Казумаро Аоки (Kazumaro Aoki) [4]. В данной работе были достигнуты следующие результаты:

атака, позволяющая найти первый прообраз для усеченной функции сжатия алгоритма MD5 с 44 итерациями (начиная с третьей), с трудоемкостью 2⁹⁶ операций;
аналогичная трудоемкость требуется для поиска первого прообраза для модифицированной функции сжатия алгоритма MD5 с 51 итерацией, но с измененным порядком раундов.

В своей следующей работе [5] тем же криптоаналитикам удалось атаковать уже 63 итерации функции сжатия MD5 из 64 – для поиска прообраза для такого алгоритма требуется 2¹²¹ операций.
Параллельно с работами [4] и [5] анализ MD5 с целью поиска атаки, направленной на вычисление прообразов, выполняли Жан-Филип Омассон (Jean-Philippe Aumasson), Уилли Мейер (Willi Meier) и Флориан Мендель (Florian Mendel). Их результаты были опубликованы в работе [6]. Они также предложили атаку по поиску первого прообраза с трудоемкостью 2¹⁰² операций для усеченной функции сжатия MD5 с 47 итерациями.
Кроме того, в работе [6] был предложен метод оптимизации полного перебора для поиска прообраза для полнораундового алгоритма MD5, заключающийся в изменении порядка вычислений. С помощью данного метода удалось добиться:

двукратного сокращения трудоемкости по сравнению с теоретической (2¹²⁸ операций) при поиске первого прообраза – 2¹²⁷ операций;
трудоемкости 2^125,7 операций при поиске первого псевдо-прообраза (т. е. первого прообраза для MD5 с нестандартным начальным заполнением регистров A…D – IV).

Таким образом, работу [6] можно считать первой работой, в которой была предложена атака по поиску прообраза для полнораундового алгоритма MD5. Результаты этой работы были усилены в еще одной работе Сасаки и Аоки [7], вышедшей в 2009 г.:

для успешного поиска первого прообраза требуется выполнение 2^123,4 операций;
для успешного поиска первого псевдо-прообраза требуется 2^116,9 операций.

Обе атаки требуют также наличия 2⁴⁵ блоков памяти. Атаки являются сертификационными, т. е. их трудоемкость заведомо превосходит практически возможную. Тем не менее, трудоемкость атак ниже теоретической трудоемкости поиска прообраза с помощью полного перебора; следовательно, наличие таких атак говорит о наличии потенциальных уязвимостей в алгоритме (в данном случае – в части однонаправленности алгоритма хэширования).
Аналогичного результата – поиска прообразов для полнораундового алгоритма MD5 с трудоемкостью 2^123,4 операций – добились китайские специалисты в альтернативной работе [8], которая была опубликована в декабре 2009 г.
В последующие годы не были опубликованы какие-либо работы, улучшающие результаты работ [7] и [8]. Таким образом, можно утверждать, что:

MD5 существенно лучше противостоит атакам по поиску прообразов, чем атакам, направленным на поиск коллизий – трудоемкость 2^123,4 операций находится далеко за гранью возможностей современной вычислительной техники;
хотя алгоритм MD5 перестал быть основной мишенью для криптоаналитиков в связи с резким сокращением его применений в последние годы (что будет обсуждаться в последующих статьях), весьма вероятно, что результаты данных работ будут усилены в будущем.

Литература

De D., Kumarasubramanian A., Venkatesan R. Inversion Attacks on Secure Hash Functions Using SAT Solvers. // http://rd.springer.com (Abstract) – Microsoft Research, 2007.
Kumarasubramanian A., De D., Venkatesan R. Inversion Attacks on Secure Hash Functions Using SAT Solvers. // http://www.csi.ucd.ie – Microsoft Research.
Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35484 – 13.08.2012 г.
Sasaki Y., Aoki K. Preimage Attacks on Step-Reduced MD5. // http://link.springer.com (Abstract) – 2008.
Aoki K., Sasaki Y. Preimage Attacks on One-Block MD4, 63-Step MD5 and More. // http://link.springer.com (Abstract) – 2009.
Aumasson J.-P., Meier W., Mendel F. Preimage Attacks on 3-Pass HAVAL and Step-Reduced MD5. // http://131002.net.
Sasaki Y., Aoki K. Finding Preimages in Full MD5 Faster than Exhaustive Search. // http://www.iacr.org – NTT Corporation, Tokyo, Japan.
Mao M., Chen S., Xu J. Construction of the Initial Structure for Preimage Attack of MD5. // http://www.lw20.com (Abstract) – 11-14 Dec. 2009 – Univ. of Electron. Sci. & Technol. of China, Chengdu, China.

Просмотров: 3206

Мнения экспертов

Левицкий О.И.
ОАО НПО «Наука»
Ведущий специалист по информационной безопасности

Опубликованный материал представляет собой добротно подготовленный обзорный анализ атак, разработанных в целях обнаружения коллизий и прообразов для алгоритма MD5. Позволяет на профессиональном уровне получить представление о данном сегменте криптоаналитических исследований. Может быть полезен широкому кругу читателей, интересующихся вопросами криптозащиты как в ознакомительном, так и в прикладном аспекте.

Крюков А.Н.
Рязанское высшее воздушно-десантное командное училище им. В.Ф.Маргелова
преподаватель

Предлагаемые для рецензии работы Панасенко С.П. продолжают серию его публикаций на сайте sec.ru. Они представляют собой часть первой главы докторской диссертации по криптоанализу, написанной автором самостоятельно и имеющей практическую ценность. Объём итоговой работы, количество использованных зарубежных источников не соответствовали правилам публикации материалов на сайте, поэтому автор разделил главу на отдельные части. Эксперт полагает, что, если результаты, полученные автором в третьей главе, могут быть опубликованы в открытой печати, читатели также смогут с ними познакомиться.