02 июня 2014

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

Сергей Панасенко,
зам. директора Фирмы «АНКАД»
по науке и системной интеграции,
кандидат технических наук

В отличие от широко распространенного алгоритма MD5, криптоанализу которого было посвящено множество работ, алгоритм MD6 распространения, практически, не получил, в результате чего он привлек несравнимо меньшее внимание криптоаналитиков. Широкую известность получило относительно немного работ по криптоанализу данного алгоритма.

Начало исследованиям алгоритма MD6 положила магистерская диссертация [1] одного из авторов алгоритма – Кристофера Кратчфилда (Christopher Crutchfield). Данная работа вышла еще до опубликования самого алгоритма – в июне 2008 г. Она была целиком посвящена обоснованию достаточной криптостойкости алгоритма MD6; основные положения данной работы вошли в опубликованную в октябре 2008 г. спецификацию алгоритма [2].

В начале 2009 г. вышли две работы Дмитрия Ховратовича (Dmitry Khovratovich) и его коллег из университета Люксембурга [3-5]. Авторы данных работ смогли представить внутреннее состояние функции сжатия алгоритма MD6 в виде системы линейных уравнений и применить впоследствии для ее решения метод Гаусса. В результате криптоанализа было доказано, что выполнением до 33 раундов внутреннего преобразования функции сжатия (напомним, что алгоритм MD6-160 выполняет 80 раундов – см. подробное описание MD6 в [6]) вырабатывается последовательность, не обладающая характеристиками псевдослучайной. Теоретически, данный метод можно использовать для последующего нахождения коллизий усеченной функции сжатия алгоритма.

В феврале 2009 г. вышла также работа [7], авторами которой были несколько криптологов из числа авторов алгоритма MD6. В данной работе они доказали, что полнораундовая функция сжатия алгоритма MD6, как и алгоритм целиком, вырабатывают последовательности, не отличимые от псевдослучайных. Авторы [7] сделали вывод об отсутствии в алгоритме MD6 структурных слабостей, из-за которых, в частности, были бы необходимы какие-либо ограничения на использование алгоритма.

Тогда же, в феврале 2009 г., Шахрам Хазей (Shahram Khazaei) и Уилли Мейер (Willi Meier) опубликовали коллизию функции сжатия алгоритма MD6, усеченной до 16 раундов, приводящую также к near-коллизии функции сжатия, усеченной до 19 раундов включительно. Трудоемкость вычисления коллизии составляла 2³⁰ операций при незначительных требованиях к памяти [5, 8] (детали атаки подробно описаны в [9] и [10]). В июле 2009 г. результаты Хазея и Мейера были усилены Томасом Ходанеком (Thomas Hodanek), который ускорил атаку на 16-раундовую функцию сжатия до 2¹⁷ операций [11].

1 июля 2009 г. авторы алгоритма MD6 направили в NIST комментарий [12], содержащий список их собственных замечаний относительно алгоритма MD6 и конкурса SHA-3, в котором данный алгоритм участвовал. Несмотря на то, что в документе [12] (см. также [13]) было сказано, что «NIST вправе выбрать алгоритм MD6 в следующий раунд конкурса при желании», документ, фактически, представлял собой отзыв данного алгоритма с конкурса SHA-3, как минимум, по следующим причинам:

по мнению авторов MD6, алгоритм SHA-3 должен быть не медленнее, чем аналогичный алгоритм семейства SHA-2; для того, чтобы удовлетворить данному условию, количество раундов функции сжатия алгоритма MD6 необходимо было бы уменьшить до порядка 30-40 вместо текущих 80-168 (в зависимости от параметров алгоритма – см. [6]);
авторы алгоритма нашли незначительную ошибку в собственном доказательстве стойкости MD6 против дифференциального криптоанализа, которое было ранее опубликовано в [1] и [2]; в результате, появилась необходимость нового доказательства данного свойства алгоритма MD6, в том числе, с учетом требуемого уменьшения количества раундов функции сжатия алгоритма;
наконец, как написали авторы MD6 в [13], им неизвестны какие-либо успешные результаты атак на данный алгоритм, но «в настоящий момент MD6 не соответствует нашим собственным стандартам, соответствие которым мы считаем обязательным для SHA-3, поэтому лучше, если NIST поищет среди других алгоритмов».

После этого не выглядит удивительным тот факт, что алгоритм MD6 не был выбран во второй раунд конкурса SHA-3 [14].

В том же 2009 вышла работа [15], в которой были предложены следующие атаки на усеченные версии алгоритма MD6:

авторы работы применили предложенную годом ранее в [16] «кубическую атаку» (cube attack, один из вариантов алгебраического криптоанализа) к ключевой версии алгоритма MD6, усеченной до 14 раундов; данная атака позволила вычислить 128-битный ключ алгоритма с трудоемкостью около 2²² операций;
путем модификации кубической атаки, авторы работы получили технологию «кубического тестирования» (cube tester), позволившую им создать различитель (алгоритм, позволяющий отличить атакуемую функцию от случайно и равновероятно выбранной функции) для 18-раундового алгоритма MD6 (трудоемкость – 2¹⁷ операций); различитель предложен также для незначительно модифицированного (с нулевыми раундовыми константами S_j – см. [6]) алгоритма MD6 с 66 раундами (2²⁴ операций).

Последней из получивших широкую известность работ, посвященных криптоанализу алгоритма MD6, была вышедшая в 2011 г. работа Этана Хейлмана (Ethan Heilman) [17]. Автор данной работы предложил новые доказательства достаточной криптостойкости алгоритма MD6 против дифференциального криптоанализа; доказанный запас криптостойкости алгоритма MD6 по сравнению с доказанным ранее авторами алгоритма был увеличен в два раза. Таким образом, выводы авторов алгоритма о его недостаточной криптостойкости, изложенные в [12], были опровергнуты. Тем не менее, вернуть алгоритм MD6 в список участников второго раунда конкурса SHA-3 было уже поздно: алгоритм MD6 выбыл из конкурса и, как одно из следствий, не получил широкого распространения.

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

Литература

Crutchfield C. Y. Security Proofs for the MD6 Hash Function Mode of Operation. // http://csrc.nist.gov – Massachusetts Institute of Technology – June 2008.
Rivest R. L., Agre B., Bailey D. V., Crutchfield C., Dodis Y., Fleming K. E., Khan A., Krishnamurthy J., Lin Y., Reyzin L., Shen E., Sukha J., Sutherland D., Tromer E., Yin Y. L. The MD6 hash function. A proposal to NIST for SHA-3. // http://csrc.nist.gov – Massachusetts Institute of Technology, Cambridge, MA – October 27, 2008.
Khovratovich D., Biryukov A., Nikolic I. Gaussian Cryptanalysis of Hash Functions: Collisions and Distinguishers. // http://www.dagstuhl.de – University of Luxembourg – 16 January 2009.
Khovratovich D. Nonrandomness of the 33-round MD6. // http://fse2009rump.cr.yp.to – University of Luxembourg – 2009.
The ECRYPT Hash Function Website. MD6. // http://ehash.iaik.tugraz.at.
Панасенко С. Алгоритм хэширования MD6. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=43766 – 22.11.2013 г.
Dodis Y., Reyzin L., Rivest R. L., Shen E. Indifferentiability of Permutation-Based Compression Functions and Tree-Based Modes of Operation, with Applications to MD6. // http://groups.csail.mit.edu.
Khazaei S. Сообщение в NIST от 24 февраля 2009 г. // http://ehash.iaik.tugraz.at.
Brier E., Khazaei S., Meier W., Peyrin T. Linearization Framework for Collision Attacks: Application to CubeHash and MD6 (Extended Version). // http://eprint.iacr.org.
Khazaei S. Neutrality-Based Symmetric Cryptanalysis. // http://infoscience.epfl.ch – Ecole Polytechnique Federale de Lausanne, Suisse, 2010.
Hodanek T. Analysis of Reduced MD6 – Abstract. // http://events.iaik.tugraz.at – Graz University of Technology, Austria.
Rivest R. L. OFFICIAL COMMENT: MD6. // http://groups.csail.mit.edu – 01 Jul 2009.
The MD6 Hash Algorithm. // http://groups.csail.mit.edu.
Regenscheid A., Perlner R., Chang S., Kelsey J., Nandi M., Paul S. Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition. // http://csrc.nist.gov – National Institute of Standards and Technology, Gaithersburg, MD – September 2009.
Aumasson J.-P., Dinur I., Meier W., Shamir A. Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium. // http://iacr.org – 2009.
Dinur I., Shamir A. Cube Attacks on Tweakable Black Box Polynomials. // http://eprint.iacr.org – 2008.
Heilman E. Restoring the Differential Resistance of MD6. // http://eprint.iacr.org – September 21, 2011.

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

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

Веретенников А.А.
-
кандидат технических наук

Не всегда встретишь статью, в которой даже сложные вещи излагаются столь интересно и понятно. Примером отличного изложения материала, на мой взгляд, является весь цикл публикаций Панасенко С.П. В отношении данной статьи отмечу следующее. Автор приводит различные точки зрения экспертов в отношении алгоритма MD6, как первоначальных, восторженных взглядов, так и последующих критических. Познавательным представляется сюжет, связанный с участием алгоритма MD6 на конкурсе по выбору новой хэш-функции (SHA-3), объявленном NIST в 2007 г. (обзор «финалистов» данного конкурса на портале sec.ru в своё время был также сделан Сергеем Петровичем). В представленном материале все факты подтверждены необходимыми ссылками, изложены последовательно, сжато, «без воды». Полагаю статью интересной для широкого круга читателей портала sec.ru и рекомендую её для публикации.

Шепитько Г.Е.

Статья носит познавательный характер и изложена на хорошем методическом уровне. Однако автор сухим языком протокола только фиксирует историю событий. Нет собственного мнения автора, поэтому отсутствуют выводы к работе. Пожелания автору: сделать хотя бы приближённую оценку срока жизни алгоритма MD6 и указать область его применения, несмотря на то, что он выбыл из конкурса. Статья представляет интерес для профессионалов и может быть рекомендована к опубликованию.