18 июня 2012

Обзор криптоаналитических исследований алгоритма MD4: поиск прообразов и попытки усиления

Данная статья является продолжением предыдущей («Обзор криптоаналитических исследований алгоритма MD4: усеченные варианты и поиск коллизий») и посвящена обзору атак на алгоритм хэширования MD4, направленных на поиск прообраза, а также описанию вариантов усиления алгоритма MD4 против известных и перспективных атак.

Поиск прообразов

После предложенной в 1997 г. Доббертином атаки на усеченный алгоритм MD4 достаточно долгое время не было опубликовано каких-либо атак, направленных на поиск прообразов для полнораундового алгоритма MD4. Первая такая атака была представлена в 2005 г. в упоминавшейся в предыдущей статье работе Ванг и ее коллег [1] как модификация атаки, направленной на поиск коллизии. Данная атака позволяет мгновенно (эквивалентно одной операции хэширования) найти второй прообраз, но атака применима только к классу слабых сообщений; вероятность того, что произвольное сообщение окажется слабым, равна 2^-122.
В том же 2005 г. другой коллектив авторов с участием Ванг опубликовал работу [2], в которой результаты работы [1] были усилены в части поиска прообразов: теперь вероятность того, что произвольное сообщение окажется слабым, равна 2^-56; вычисление второго прообраза для слабого сообщения по-прежнему происходит мгновенно. Кроме того, авторы данной атаки предложили способ конвертации любого сообщения в слабое, незначительно отличающееся от исходного; для этого требуется около 2²⁷ операций. Отметим, однако, что такая технология вряд ли может быть использована при построении практически применимых атак на алгоритм хэширования.
Существенного прогресса в поиске прообразов достиг в 2008 г. Лоран (G. Leurent). Он опубликовал работу [3], в которой описал следующий метод вычисления прообразов для функции сжатия алгоритма MD4 (имеется в виду функция fb() – криптографическое ядро алгоритма):

Атака основана на поиске псевдо-прообразов, т. е. в атаке не фиксируется начальное значение алгоритма хэширования (IV).
Выбирается начальное сообщение (initial message), т. е. пара IV и M (где M – хэшируемое сообщение), обладающее специфичными свойствами (выбор критериев формирования начального сообщения, по мнению автора атаки, является одним из ее ключевых факторов).
Используя дифференциальный криптоанализ, автор атаки осуществляет поиск набора связанных с начальным сообщений (family of related messages), таких, что в процессе атаки может контролироваться их обработка алгоритмом MD4.
В процессе данного поиска алгоритм MD4 представляется в виде системы уравнений относительно переменных a…d и 32-битных слов блока сообщения.
На поиск 2³² связанных сообщений требуется выполнение 2³² операций хэширования. Однако, в результате одно из этих сообщений будет представлять собой частичный псевдо-прообраз (partial pseudo-preimage), результат хэширования которого будет совпадать с целевым хэш-значением (H) в 32 битах.
Повторяя предыдущие действия 2³² раз, осуществляется поиск частичного псевдо-прообраза для 64 битов H. В результате для поиска полного псевдо-прообраза требуется 2⁹⁶ операций (вместо 2¹²⁸ для 128-битного алгоритма хэширования MD4).

Для распространения данной атаки целиком на алгоритм MD4 используется атака «встреча посередине»: вычисляется множество псевдо-прообразов хэш-значения H, хэшируется множество случайных сообщений и используется парадокс «дней рождения» для «встречи посередине» (см. описание данного типа атак, например, в [4]). В [3] показано, что, если для поиска псевдо-прообраза n-битного алгоритма хэширования требуется 2^S операций, то для поиска первого прообраза необходимо 2^1+(n+S)/2 операций. Т. е. в данном случае 2¹¹³ операций (оптимизировано автором [3] до 2¹⁰² операций), что неосуществимо на практике, но существенно лучше полного перебора.
Метод применим для любого сообщения, но его трудоемкость находится за пределами практической реализуемости.

Попытки модификации алгоритма MD4 с целью его усиления

Несмотря на успешные атаки по поиску коллизий и рекомендации экспертов использовать более стойкие алгоритмы хэширования [5, 6], к 2005 г. в мире использовались сотни тысяч экземпляров устройств и программ, в которых был реализован алгоритм MD4 [7]. Следовательно, актуальным был бы алгоритм хэширования со следующими характеристиками:

эквивалентный по своим параметрам алгоритму MD4;
стойкий против всех известных атак на MD4;
полученный путем незначительной модификации MD4 (или путем создания надстройки над MD4), что позволило бы за счет незначительных усилий заменить MD4 таким алгоритмом.

В 2005 г. авторы работы [7] предложили модификацию алгоритма MD4, в которой в каждую итерацию алгоритма вводилась одна дополнительная операция: после применения к 32-битной переменной операции циклического сдвига на sj битов перед дальнейшим использованием переменная t обрабатывалась следующим образом:
t = t1^’|| t2^’|| t3^’|| t4^’|| t5 || t6 || t7 || t8,
где:

|| – операция конкатенации;
t1…t8 – 4-битные фрагменты исходной переменной t;
t1’…t4’ – значения первых четырех фрагментов после выполнения данных операций:

t1^’= t1 * t5,
t2^’= t6 * t2,
t3^’= t3 * t7,
t4^’= t8 * t4,
где операция * представляет собой нелинейную операцию преобразования двух 4-битовых фрагментов в один 4-битовый фрагмент согласно таблице, в качестве примера которой в [7] приведена следующая таблица:

*	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	A	4	5	9	6	0	E	1	2	C	D	F	3	8	B	7
1	5	B	C	8	4	E	0	7	3	2	F	A	1	9	D	6
2	C	5	2	D	F	8	A	E	1	3	6	7	B	0	9	4
3	7	D	3	E	2	1	B	C	5	9	4	8	0	F	6	A
4	1	2	4	A	B	7	8	9	0	D	3	E	6	C	5	F
5	4	A	8	B	D	2	C	6	E	F	5	9	7	3	1	0
6	0	E	D	2	8	3	6	5	C	B	7	4	9	A	F	1
7	B	6	0	5	9	D	4	8	7	A	2	3	F	1	E	C
8	D	8	6	1	C	A	F	0	B	5	9	2	4	7	3	E
9	2	F	1	0	7	C	5	B	9	6	8	D	A	E	4	3
A	6	C	B	7	A	F	1	3	4	8	E	0	D	5	2	9
B	8	1	F	6	3	9	7	4	A	E	C	5	2	D	0	B
C	F	3	9	4	E	6	2	D	8	7	0	1	C	B	A	5
D	E	9	7	3	1	B	D	F	6	0	A	C	5	4	8	2
E	3	0	E	C	5	4	9	A	F	1	B	6	8	2	7	D
F	9	7	A	F	0	5	3	2	D	4	1	B	E	6	C	8

Выходное значение операции * находится на пересечении строки и столбца, соответствующих входным значениям.
Графически данное дополнительное преобразование представлено на рис. 1.

Рис. 1 Дополнительное преобразование модифицированного алгоритма MD4

Авторы модифицированного алгоритма MD4 доказали, что такой алгоритм обладает весьма высокой криптостойкостью: к нему не применима ни одна из известных атак на MD4, а также крайне маловероятно нахождение практически применимых атак на данный алгоритм в обозримом будущем. Однако, усиленный MD4 не получил распространения, в том числе, из-за низкого быстродействия – в 1,5 – 5 раз более низкого по сравнению с оригинальным алгоритмом MD4.

Исследование надстроек над алгоритмом MD4

Помимо атак на алгоритм MD4, криптоаналитики предлагали различные атаки на протоколы, в которых MD4 использовался или мог бы использоваться, а также атаки на различные варианты применений алгоритма хэширования, среди которых, например, метод ключевого хэширования HMAC (Hash-Based Message Authentication Codes – коды аутентификации сообщений на основе хэш-функций) [8]. Эти атаки будут рассмотрены в одной из последующих статей данного цикла.

Литература

Wang X., Lai X., Feng D., Chen H., Yu X. Cryptanalysis of the Hash Functions MD4 and RIPEMD. // http://www.infosec.sdu.edu.cn – 2005.
Yu H., Wang G., Zhang G., Wang X. The Second-Preimage Attack on MD4. // http://infosec.sdu.edu.cn – Shandong University, Jinan, China – 2005.
Leurent G. MD4 is Not One-Way. // http://www.di.ens.fr – Ecole Normale Superieure, Paris, France.
Панасенко С. П. Алгоритмы шифрования. Специальный справочник. – СПб.: БХВ-Петрбург, 2009 – 576 с.
Van Rompay B., Preneel B., Vandewalle J. On the security of dedicated hash functions. // http://citeseerx.ist.psu.edu – Katholieke Universiteit Leuven, Heverlee, Belgium.
Robshaw M. J. B. On Recent Results for MD2, MD4, and MD5. // ftp://ftp.rsa.com – RSA Laboratories’ Bulletin – #4 – November 12, 1996.
Gligoroski D., Markovski S., Knapskog S. J. A Fix of the MD4 Family of Hash Functions – Quasigroup Fold. // http://csrc.nist.gov – NIST Cryptographic Hash Workshop, 31 Oct – 1 Nov 2005.
Krawczyk H., Bellare M., Canetti R. RFC 2104. HMAC: Keyed-Hashing for Message Authentication. // http://tools.ietf.org – February 1997.