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