30 июля 2012
Обзор результатов криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4
Данная статья завершает исторический обзор, посвященный алгоритму хэширования MD4. Она описывает результаты криптоанализа алгоритмов аутентификации сообщений на основе MD4: HMAC-MD4 и NMAC-MD4. Конструкции HMAC и NMAC были подробно описаны в предыдущей статье.
Начало атакам на алгоритм HMAC-MD4 положила работа [1], авторы которой сделали вывод о том, что атаки на MD4 могут быть расширены на HMAC-MD4. Это справедливо и для HMAC-алгоритмов, основанных на других алгоритмах хэширования, вопреки существовавшему на тот момент (2006 г.) мнению, что HMAC-надстройка существенно меняет контекст атаки на нижележащий алгоритм хэширования, делая невозможным применение существующих атак на алгоритм к его HMAC-варианту.
Авторы работы [1] предложили альтернативное графическое представление алгоритма HMAC, которое (для одноблочного сообщения M) приведено на рис. 1.
Рис. 1 Графическое представление HMACдля одноблочного сообщения
Для атаки на HMAC используется дифференциальный криптоанализ, в котором применяются квартеты одноблочных сообщений Mi, Mi’, Mj и Mj’ с определенной разностью a:
Mi ⊕ Mi’ = Mj ⊕ Mj’ = a,
причем сообщения Mi и Mj выбираются случайным образом.
Каждая четверка сообщений проверяется на наличие коллизии, т. е. справедливо ли следующее равенство применительно к выходным значениям алгоритма HMAC Ci, Ci’, Cj и Cj’:
Ci ⊕ Cj = Ci’ ⊕ Cj’ = 0 или Ci ⊕ Cj’ = Ci’ ⊕ Cj = 0.
Схема такой коллизии приведена на рис. 2 (на рисунке не показаны ключевые элементы, разности показаны прерывистыми линиями).
Рис. 2 Коллизия для квартета одноблочных сообщений
В части криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4 в работе [1] были достигнуты следующие результаты:
- для атаки на HMAC-MD4, позволяющей без знания секретного ключа найти корректную пару «сообщение – код аутентификации данного сообщения» с вероятностью успеха 93 %, необходимо наличие 258 выбранных сообщений и результатов их обработки алгоритмом HMAC-MD4;
- полностью аналогичным образом можно атаковать и алгоритм NMAC-MD4.
Анализ HMAC и NMAC был независимо выполнен в работе [2], вышедшей в том же 2006 г., в которой также было показано, что слабая функция хэширования может скомпрометировать HMAC и NMAC, построенные на ее основе, а также любые другие вышележащие конструкции при их недостаточной криптостойкости.
Авторы [2] использовали найденные ранее коллизии для алгоритма MD4 при построении коллизии для внутренней функции хэширования HMAC- или NMAC-MD4, т. е. для функции hash(k1, m) при использовании NMAC. Схема такой внутренней коллизии двух многоблочных сообщений M1 и M2 для HMAC-варианта приведена на рис. 3. Как отмечено в [2], внешняя функция хэширования скрывает результат выполнения внутренней функции, но не может скрыть факт возникновения такой внутренней коллизии (поскольку в случае внутренней коллизии совпадут выходные значения HMAC или NMAC).
Рис. 3 Внутренняя коллизия алгоритма HMAC
Следующий шаг атаки – создание набора специально выбранных сообщений, внутренние коллизии на которых позволят полностью определить значение внутреннего секретного ключа (т. е. h(k ⊕ C1) в HMAC или k1 в NMAC). В результате авторы [2] предложили следующие атаки на HMAC-MD4 и NMAC-MD4:
- 258 операций достаточно для нахождения корректной пары «сообщение – код аутентификации данного сообщения» без знания секретного ключа;
- 263 операций достаточно для вычисления внутреннего секретного ключа.
Отметим, что относительно невысокая трудоемкость данных атак делает возможной их практическую реализацию. Поэтому (это указано и в [2]) алгоритмы HMAC-MD4 и NMAC-MD4 после публикации данных результатов следовало как можно быстрее перестать использовать.
Как и в работе [1], в [2] были предложены атаки на алгоритмы аутентификации сообщений на основе ряда других хэш-функций. Кроме того, авторы работы [2] предложили универсальную методику атак на HMAC и NMAC, а также возможные направления атак на нижележащие алгоритмы хэширования, позволяющие впоследствии атаковать надстройки над ними.
Еще одна универсальная методика атак на HMAC и NMAC была предложена в работе [3] (2007 г.). Суть методики в использовании коллизий алгоритма хэширования, лежащего в основе HMAC/NMAC, для нахождения вектора инициализации данного алгоритма. Поскольку в HMAC/NMAC в качестве вектора инициализации используется секретный ключ (в NMAC) либо результат его обработки функцией сжатия алгоритма хэширования (в HMAC), данная атака позволяет:
- для NMAC – определить значения секретных ключей k1 и k2;
- для HMAC – определить значения h(k ⊕ C1) и h(k ⊕ C2), знания которых (без знания значения k) достаточно для последующей подделки кодов аутентификации сообщений, т. е. данный случай можно считать эквивалентным полному раскрытию секретного ключа алгоритма HMAC.
В частности, в [3] описана атака на алгоритмы HMAC-MD4 и NMAC-MD4, позволяющая вычислить описанные выше ключевые элементы данных алгоритмов. Для успешной реализации атаки необходимы значения HMAC/NMAC 288 выбранных сообщений; вычислительная трудоемкость атаки составляет 295 операций.
Результаты предыдущей работы были усилены авторами вышедшей в следующем году работы [4], в которой было предложено для вычисления ключа использовать не коллизии, а near-коллизии, которые существенно проще получить. В результате количество данных, необходимых для успешной атаки, было снижено с 288 до 272 сообщений и результатов их обработки алгоритмом HMAC/NMAC, а трудоемкость атаки была снижена с 295 до 277 операций.
Какие-либо последующие работы, посвященные анализу HMAC-MD4 и NMAC-MD4, не получили широкой известности. Последние достижения в криптоанализе данных алгоритмов показывают явную зависимость криптостойкости HMAC и NMAC от криптостойкости нижележащих алгоритмов хэширования. Поскольку активный криптоанализ HMAC и NMAC продолжается, в ближайшие годы возможно дальнейшее усиление результатов работы [4], которые пока находятся за гранью практической применимости.
Литература:
- Kim J., Biryukov A., Preneel B., Hong S. On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0, and SHA-1. // http://eprint.iacr.org – 2006.
- Contini S., Yin Y. L. Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. // http://www.iacr.org – 2006.
- Fouque P.-A., Leurent G., Nguyen P. Q. Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. // http://Citeseerx.ist.psu.edu – Ecole Normale Superieure, Paris, France – 2007.
- Wang L., Ohta K., Kunihiro N. New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. // http://www.iacr.org – The University of Electro-Communications, Tokyo, Japan – 2008.
