HKDF: как получать новые ключи и при чем тут хэш-функции04.12.2020 15:33

Для современных алгоритмов шифрования одним из факторов, влияющих на криптостойкость, является длина ключа. Согласно стандарту NIST, криптографическая стойкость алгоритмов должна быть не менее 112 бит. Для симметричных алгоритмов это означает, что минимальная длина ключа должна составлять 224 бит, для асимметричных, основанных на теории чисел (например, на решении задачи факторизации для алгоритма RSA), минимальная надёжная длина — 2048 бит [1]. Не спасает от использования ключей большого размера и криптография на эллиптических кривых.

Но что поделать, если существующие ключи не обладают достаточной длиной для их безопасного использования в выбранных нами алгоритмах? Или же нам нужно получить больше ключей, чем у нас есть? Тут на помощь приходит KDF (Key Derivation Function) — это функция, которая формирует один или несколько криптографически стойких секретных ключей на основе заданного секретного значения (в литературе именуемого главным, а иногда мастер ключом) с помощью псевдослучайной функции. И что особенно важно, она позволяет задавать длину ключа, создаваемого в результате своей работы, а его стойкость будет такой же, как и у случайного ключа той же длины [2], [3].

Именно о KDF и пойдет речь далее. Мы рассмотрим общий принцип работы, одну из версий этой функции — HKDF, а также разберем, как она может быть реализована на Python’е.

Часть 1. Общий принцип работы KDF

Замечательная статья с введением в тему: ссылка

В целом, работу KDF можно представить как процесс из двух шагов, именуемый «извлечь-затем-растянуть» (по-английски — extract-and-expand):

сначала из главного ключа «извлекается» псевдослучайный ключ фиксированной длины. Его цель — «сконцентрировать» энтропию входного ключа в короткий, но криптографически стойкий ключ. Необходимость этого шага будет обоснована чуть ниже;
затем значение, сгенерированное на первом шаге, «растягивается» в ключ заданной длины или в несколько ключей. Во втором случае задается их суммарная длина.

Рис 1. Алгоритм работы KDF [4]

Рассмотрим каждый из шагов работы функции более детально.

Randomness Extraction:
Первую часть нашего алгоритма — шаг извлечения ключа из входных данных — можно представить как функцию двух аргументов:

PRK = XTR (XTSalt, SKM)

где:

SKM (Source Keying Material) — секретное (в некоторой литературе обозначаемое как главное) значение, на основе которого формируется сначала псевдослучайный ключ PRK, а затем — ключ заданной длины или несколько ключей. Это и есть тот ключ, который «растягивает» KDF;
XTR (randomness eXTRactor) — экстрактор случайности. Его можно представить как функцию, принимающую на вход исходный ключ SKM и генерирующую на его основе выходной ключ PRK. Важное свойство этой функции заключается в том, что созданный с ее помощью ключ выглядит независимым от источника и является равномерно распределённым (в статистическом и вычислительном смысле);
PRK (PseudoRandom Key) — псевдослучайный ключ. Это значение является выходным для первого шага алгоритма;
XTSalt (eXTractor Salt) — криптографическая соль, т.е. случайное (не обязательно секретное) значение, используемое для усложнения определения прообраза функции, создающей псевдослучайный ключ. Оно может быть константой или не использоваться вовсе.

Пока это выглядит как довольно абстрактное определение с горой аббревиатур, приправленных солью. Но это лишь общий вид — в конкретных реализациях KDF места обозначений занимают реальные данные и криптографические функции. Например, HKDF, о которой пойдет речь во второй части статьи, в качестве экстрактора использует хэш-функции.

Key Expansion:
На втором шаге из полученного ранее псевдослучайного ключа (PRK) создается ключ заданной длины L, или же набор ключей той же суммарной длины. Также представим этот процесс в виде функции:

$DKM = PRF^{*} (PRK, CTXinfo, L)$

где:

PRF* (PseudoRandom Function with variable length) — псевдослучайная функция, способная выдавать значения переменной длины. Для достижения этого свойства зачастую используют обычную псевдослучайную функцию с расширением выходных данных с помощью различных режимов работы, таких как counter и feedback mode;
CTXInfo (context information) — строка контекстной информации (так же, как и соль, может быть просто заданной заранее константой, в том числе нулем). Содержит в себе сведения, например, о приложении, в котором используется функция;
PRK — выходное значение первого шага;
DKM (Derived Keying Material) — выходной ключ длины L.

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

Оказывается, в этом переходе между шагами кроется наибольшая сложность в разработке функций формирования ключа. Если главный ключ не является случайным или псевдослучайным, KDF не может «растянуть» его так, чтобы получившийся ключ был криптографически стойким. Этим обосновывается необходимость первого шага, на котором из «неидеальных» входных данных формируется псевдослучайный ключ, который служит основой для последующей генерации выходного ключа.

Конечно же, если главный ключ — уже (псевдо-)случайное значение, его можно использовать в качестве входных данных второго шага, пропустив первый. Например, premaster secret в протоколе TLS является псевдослучайной строкой, за исключением первых двух байт (IETF). Но даже в таком случае шаг извлечения может быть необходимым, если, например, размер главного ключа больше, чем того требует псевдослучайная функция PRF* (этот параметр зависит от реализации PRF* в конкретном алгоритме).

Часть 2. HKDF

HKDF (HMAC Key Derivation Function) является одной из реализаций механизма KDF. В алгоритме KDF в качестве псевдослучайной функции (обозначенной выше как PRF*), а также экстрактора псевдослучайной ключа, используется механизм HMAC.

Алгоритм HKDF
Представим схему HMAC в виде функции от двух аргументов, где первый из них — это всегда ключ, а второй — данные, которые будут хэшироваться вместе с ключом. Также обозначим как HashLen размер выходных данных (в октетах), используемый в данном алгоритме. Символом || обозначается конкатенация («склеивание») строк. То есть под записью HMAC (key, a || b) подразумевается, что хэш-функция с заданным ключом key действует на конкатенацию a и b.

Зная это, алгоритм HKDF можно записать в виде:

HKDF(XTS, SKM, CTXinfo, L) = K = K(1) || K(2) || ... || K(t)

где XTS, SKM и CTXInfo обозначают то же, что и в общем принципе работы KDF, а значения K (i), i = 1,…, t определяются согласно правилу:

PRK = HMAC-Hash (XTS, SKM) — первый шаг алгоритма, на котором из исходных данных ключа (SKM) генерируется псевдослучайный ключ (PRK). При этом длина PRK определяется функцией, используемой в конкретной схеме HMAC (HMAC-Hash) и составляет HashLen октетов. Обратите внимание, что ключом для этой хэш-функции является соль, а «сообщением» — наш исходный ключ. В случае, когда энтропия SKM достаточно велика, PRK будет не отличим от случайного.
K (1) = HMAC-Hash (PRK, CTXinfo || 0),
K (i+1) = HMAC-Hash (PRK, K (i) || CTXinfo || i), 1 ≤ i < t,

где t = L/HashLen — количество «блоков», необходимых для получения конечного ключа длины L. Число i в формуле для второго и последующих шагов представляется в шестнадцатеричном виде. В случае, когда требуемая длина ключа не кратна HashLen, выходным значением алгоритма являются L первых октетов K. При этом существует ограничение на L: L ≤ 255 * HashLen.

Рис 2. Схема работы HKDF [4]

Как было отмечено в описании общего алгоритма KDF, соль — опциональное поле; при отсутствии предоставленного значения, на вход подается строка нулей длины HashLen. Но ее использование существенно увеличивает безопасность всей схемы, уменьшает зависимость выходного ключа от главного, и гарантирует независимость результатов работы хэш-функций, ведь значение XTSalt является ее ключом на шаге создания PRK.

@nusr_et via Instagram

Еще одним необязательным аргументом является контекстная информация. Однако для некоторых приложений она является необходимым условием работы. Дело в том, что контекст позволяет связать получившийся в результате работы алгоритма «длинный» ключ с информацией, специфичной для приложений и пользователей. Такой информацией может служить, например, номера протоколов, идентификаторы алгоритмов и т.д. Это становится особенно важным, когда разные приложения используют HKDF с одним и тем же входным главным ключом, потому что в этом случае контекст позволяет генерировать различные выходные данные. Единственным и крайне важным условием для контекстной информации является ее независимость от входного ключа SKM.

Часть 3. Реализация HKDF

Схема HKDF реализована во многих языках программирования: Java, JavaScript, PHP, Python. Рассмотрим, например, реализацию на питоне, чтобы разобраться в принципе ее работы не только на уровне описания алгоритма, но и работающей функции:

import hashlib
import hmac
from math import ceil

hash_len = 32

def hmac_sha256(key, data):
    return hmac.new(key, data, hashlib.sha256).digest()

def hkdf(length: int, ikm, salt: bytes = b"", CTXinfo: bytes = b"") -> bytes:
    # соль - опциональное поле, поэтому, если не задано пользователем,
    # используем строку нулей длины hash_len:
    if len(salt) == 0:
        salt = bytes([0] * hash_len)
    
    # Первый шаг: из предоставленного ключа генерируем псевдослучайный ключ
    # с помощью хэш-функции:
    prk = hmac_sha256(salt, ikm)
    
    k_i = b"0"  # на первом шаге в хэш-функцию подается 0
    dkm = b""   # Derived Keying Material
    t = ceil(length / hash_len)
    
    # Второй шаг: с помощью хэш-функции вычисляем K(i), конкатенация которых
    # и является результатом работы функции. Заметим, что на каждом шаге 
    # для вычисления K(i) используется предыдущее значение K(i-1):
    for i in range(t):
        k_i = hmac_sha256(prk, k_i + CTXinfo + bytes([1 + i]))
        dkm += k_i
    
    # Если длина не кратна hash_len, то возвращаются первые length октетов:
    return dkm[:length]

Убедимся в работоспособности примера:

>>> output = hkdf(100, b"input_key", b"add_some_salt")
>>>
>>> print(''.join('{:02x}'.format(byte) for byte in output))
2bcd8350cc31b6945b23b2a47add4d5ec4b1bd9fad0387590bf4e9f4d34ea456e63267c765e7cd5451df1f6f18f41eaba20de594fd8c6a008120276438d18fc4122ec152fff03204c966261b60408a569b6b0e3527ae4a34570c62b2d060fd15f3176a36
>>>
>>> print(len(out))
100

Как можно увидеть, наша функция hkdf сгенерировала ключ output на основе входного ключа «input_key» и соли «add_some_salt». Обратите внимание, что на вход подаются не строки, а последовательности байтов, они лишь представлены в виде строк для наглядности. Конвертируется одно в другое вот так. Длина выходного ключа составила 100 байт, именно столько, сколько мы потребовали первым аргументом!

Источники мудрости: