Можно ли вычислить секретный ключ HMAC, если научиться инвертировать хеш-функции?

Приветствую, Хабр!  В анализе криптографических алгоритмов достаточно часто используется понятие оракула. Оракул – это некоторая гипотетическая вычислительная сущность, которая может мгновенно выполнять конкретные требуемые криптоаналитику операции. Например, выдавать истинно случайные числа (случайный оракул), или зашифровывать/расшифровывать данные на некотором априори известном оракулу ключе шифрования (соответственно, оракул зашифрования/расшифрования). 
Предлагаю в этой статье пойти дальше и рассмотреть оракул, способный найти прообраз (точнее, совокупность возможных прообразов) заданного хеш-кода конкретной хеш-функции. Поскольку хеш-функции часто используются в более сложных конструкциях, предлагаем посмотреть и порассуждать, как наличие такого оракула влияет на свойства вышележащих криптографических механизмов. В качестве их примера рассмотрим конструкции HMAC (Hash-based Message Authentication Codes – коды аутентификации сообщений на основе хеширования).

Оракул поиска прообразов
Оракула, который умеет находить прообразы заданных хеш-кодов, так и назовем оракулом поиска прообразов, обозначим его как P. Предположим, что у атакующего есть доступ к такому оракулу, в результате которого он может запросить у оракула (и немедленно получить) прообразы для некоторого хеш-кода h заранее зафиксированной хеш-функции:

где s – длина в битах каждого из прообразов, которые хочет получить атакующий, а множество из z прообразов заданной длины s, найденных оракулом, обозначается

Отметим, что при отсутствии зафиксированной длины искомых прообразов их количество либо является бесконечным (если хеш-функция не ограничивает размер входного значения), либо весьма большим, если ограничение на размер входного значения есть (в этом случае оно обычно очень большое – например, 264 – 1 бит для SHA2-256 [1]). Если же размер зафиксирован, то количество найденных прообразов z может быть оценено следующим образом (при близком к равновероятному распределении выходных хеш-кодов по множеству входных значений):

где n – размер выходного значения хеш-функции в битах.
Подразумеваем здесь, что s > n. Однако значения s ≤ n также допустимы, в этих случаях z может интерпретироваться как вероятность нахождения одного прообраза для заданного хеш-кода.
HMAC
Коды аутентификации сообщения на основе хеширования HMAC были предложены в 1996 г. в [2], они активно используются в ряде криптографических протоколов. Вычисление HMAC производится так:

где:

• m – входное сообщение произвольного размера (с учетом возможных ограничений нижележащей хеш-функции hash);
  
• K – секретный ключ для вычисления HMAC, а k – результат его дополнения или выравнивания под размер блока данных (b бит) хеш-функции hash;
  
• ipad и opad – фиксированные (стандартизованные) b-битные константы.

Входные сообщения m и соответствующие им значения HMAC обычно известны атакующему, поскольку передаются в открытом виде.
Предположим, что у атакующего есть оракул поиска прообразов и известная пара сообщения m (длины len) и его HMAC-кода h, рассчитанного с использованием (выровненного или дополненного) ключа k. Видно, что в этом случае атакующий легко получит с помощью оракула набор возможных промежуточных значений:

Вопрос: Сможет ли атакующий в этом случае получить корректное значение секретного ключа k (что позволит ему впоследствии подделать HMAC любого сообщения на этом ключе)?
Методика поиска секретного ключа
Позволю себе предложить следующую методику определения секретного ключа k с помощью оракула поиска прообразов P:
Шаг 1. С помощью оракула атакующий получает множество возможных прообразов (назовем эти прообразы «внешними»):

где s = b + n, т. е. мощность данного множества

Каждый возможный прообраз ci представляет собой конкатенацию двух частей:



где:

• ki – возможное значение искомого ключа k, соответствующее прообразу ci;
  
• mi – сообщение, соответствующее прообразу ci.

Шаг 2. Правая часть каждого возможного прообраза ci, i =1,....,z«прогоняется» через оракул поиска прообразов с целью получения для каждого из них еще одного множества возможных прообразов (назовем эти прообразы «внутренними»):

где

– j-й внутренний прообраз, полученный из правой части i-го внешнего прообраза.
Каждый из внутренних прообразов также состоит из двух частей:


В этом случае уже из внутреннего прообраза получается еще один кандидат в искомые ключи:

Шаг 3. Для определения, какой из кандидатов в секретные ключи является верным, выполняется полный перебор по следующим значениям:


Критериями нахождения верного ключа являются следующие:


В (крайне маловероятном) случае совпадения данных значений для нескольких кандидатов в ключи, необходима вторая пара m и h для выделения из них корректного.
Оценка трудоемкости
Среднюю трудоемкость нахождения корректного ключа HMAC (не принимая во внимание требования к памяти и возможные ложные совпадения) в соответствии с описанной выше методикой можно оценить следующим образом:

• обращений к оракулу поиска прообразов:
  
  
• сравнений в процессе перебора:
  

Для ряда широко используемых хеш-функций можно привести конкретные цифры:

Хеш-функция	Размер блока (равный длине ключа k) b, бит	Размер выходного значения n, бит	Размер прообразов s, бит	Обращений к оракулу	Сравнений
(нижняя граница для len = 1)
MD5	512	128	640	2511	2896
RIPEMD-160	512	160	672	2511	2864
SHA2-256	512	256	768	2511	2768
SHA2-512	1024	512	1536	21023	21536
SHA3-256	1088	256	1344	21087	21920
SHA3-512	576	512	1088	2575	2640
Стрибог-256	512	256	768	2511	2768
Стрибог-512	512	512	1024	2511	2512

Как видно из таблицы, трудоемкость описанной выше атаки по поиску секретного ключа HMAC с использованием оракула поиска прообразов является крайне высокой и на много порядков превышает гипотетическую границу практической применимости, что показано на примере ряда широко используемых хеш-функций (и должно являться справедливым для прочих криптографических хеш-функций с достаточно большим размером блока). 
Заключение
Таким образом, можно сделать вывод, что конструкция HMAC является крайне удачной и даже в случае наличия у атакующего такого мощнейшего средства, как оракул поиска прообразов, по факту является стойкой в части определения секретного ключа.

Литература

1.  FIPS 180-4.Secure Hash Standard (SHS). August 2015.
2.  M. Bellare, R. Canetti, H. Krawczyk. Keying Hash Functions for Message Authentication. CRYPTO 1996.

-Источник