Сложный

4 мин

7.6K

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

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

Оракул поиска прообразов

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

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

Отметим, что при отсутствии зафиксированной длины искомых прообразов их количество либо является бесконечным (если хеш-функция не ограничивает размер входного значения), либо весьма большим, если ограничение на размер входного значения есть (в этом случае оно обычно очень большое – например, 2⁶⁴ – 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, т. е. мощность данного множества

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

где:

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

• m_i – сообщение, соответствующее прообразу c_i.

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

где

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

Каждый из внутренних прообразов также состоит из двух частей:

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

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

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

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

Оценка трудоемкости

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

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

  

• сравнений в процессе перебора:

  

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

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

Заключение

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