Рис. 1 Графическое представление HMAC для одноблочного сообщения
Данная статья завершает исторический обзор, посвященный алгоритму хэширования 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 и 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:
Отметим, что относительно невысокая трудоемкость данных атак делает возможной их практическую реализацию. Поэтому (это указано и в [2]) алгоритмы HMAC-MD4 и NMAC-MD4 после публикации данных результатов следовало как можно быстрее перестать использовать.
Как и в работе [1], в [2] были предложены атаки на алгоритмы аутентификации сообщений на основе ряда других хэш-функций. Кроме того, авторы работы [2] предложили универсальную методику атак на HMAC и NMAC, а также возможные направления атак на нижележащие алгоритмы хэширования, позволяющие впоследствии атаковать надстройки над ними.
Еще одна универсальная методика атак на HMAC и NMAC была предложена в работе [3] (2007 г.). Суть методики в использовании коллизий алгоритма хэширования, лежащего в основе HMAC/NMAC, для нахождения вектора инициализации данного алгоритма. Поскольку в HMAC/NMAC в качестве вектора инициализации используется секретный ключ (в NMAC) либо результат его обработки функцией сжатия алгоритма хэширования (в 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], которые пока находятся за гранью практической применимости.
Литература: