25.08 // Хэш-функция MD6 - кандидат на стандарт SHA-3

На прошедшей конференции Crypto 2008 Рональд Райвист представил новую хэш-функцию, которая претендует на более успешную замену самой широко распространённой ранее MD5.

В команду разработчиков входили:

Dan Bailey
Sarah Cheng
Christopher Crutchfield
Yevgeniy Dodis
Elliott Fleming
Asif Khan
Jayant Krishnamurthy
Yuncheng Lin
Leo Reyzin
Emily Shen
Jim Sukha
Eran Tromer
Yiqun Lisa Yin

А также организации:

Juniper Networks
Cilk Arts
NSF

Функция MD5 была создана в 1991 году, в тот самый год, когда был представлен WWW, а частоты обычных процессоров были не больше 33MHz. Она должна была отображать двоичную строку произвольной длины в строку размером d, быть устойчивой к коллизиям, нахождению прообразов и быть псевдослучайной.

После взлома функции MD5 и SHA-1 американский институт стандартов и технологий (NIST), объявил конкурс на создание хэш-функции SHA-3.

Новая функция MD6 предполагается доказуемо устойчивой к дифференциальному криптоанализу (с помощью которого была взломана MD5).

Разработчики использовали оригинальные идеи в дизайне хэш-функции. Так, размер обрабатываемого за один раз блока данных будет 512 байт (а не бит), что затрудняет проведение многих атак, даёт выигрыш в распараллеливании.

В разработке вместо традиционного дизайна Дамгарда-Меркла исползовалось сжатие при помощи древовидных структур. В узле каждого дерева находится сжимающая функция 4-1 (аналог деревьев Меркла с мини-функциями сжатия). Для малых процессоров вместо иерархической структуры деревьев, может использоваться последовательная.

MD6 поддерживает также хэширование с ключем 512-бит. Различные конструктивные особенности (нумерация узлов деревьев, root и z-биты на входе в подфункции) защищают функцию от атак вставок и расширения. Нелинейность функции достигается использованием всего трёх простейших операций: XOR, сложение и сдвиг с константами.

Количество раундов функции необычно велико: r = 40 + (d / 4). Так для 256 выхода потребуется 104 раунда, а для 512 – 168 раундов! При этом MD6-512 медленнее в полтора раза, чем SHA2-512 на 32-битных платформах и почти в четыре раза на 64-битных. Однако на многопроцессорных архитектурах она обгоняет её с ростом числа процессорных ядер, начиная с четырёх.

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

Алгебраический криптоанализ на основе SAT-алгоритмов может найти решения для менее чем 9 раундов (при больших затратах времени), частичные решения для 10-11 раундов и бесполезен против более чем 12 раундов. MD6 полностью проходит статистические тесты после 12 раундов. Дифференциальный криптоанализ менее эффективен, чем нахождение коллизий подбором.

Помимо слайдов презентации, показанной на CRYPTO-2008, в настоящий момент работа по созданию и обоснованию дизайна MD6 наиболее полно изложена в диссертации Кристофера Кратчфилда.

Другим наиболее широко известным ранее кандидатом на конкурс SHA-3 была хэш-функция MAELSTROM (D. L. G. Filho, P. S. L. M. Baretto, V. Rijmen), которая представляет собой модифицированный вариант функции WHIRLPOOL, но значительно более быстродействующий. Она основана на алгебраических операциях, аналогичным использованным в шифре AES-Rijndael и модифицированной схеме Дамгарда-Меркла.

Источник: Ronald Rivest Crypto 2008 presentation