HMAC

Было замечено^[кем?], что скорость работы хеш-функций (например, MD5, SHA-1, RIPEMD128, RIPEMD-160) обычно выше скорости работы симметричных блочных шифров (например, DES). Возникло желание использовать хеш-функции в MAC, а наличие готовых библиотек с реализациями различных хеш-функций только подтолкнуло эту идею.

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

В июне 1996 года[2] Хьюго Кравчик (англ. Hugo Krawczyk, сотрудник фирмы IBM), Михир Беллар (англ. Mihir Bellare, сотрудник калифорнийского университета в Сан-Диего (UCSD)) и Ран Каннетти (англ. Ran Canetti, сотрудник фирмы IBM) опубликовали описание механизма HMAC, а в феврале 1997 года ими же был выпущен RFC 2104. В HMAC данные «смешивались» с ключом, и хеш-функция применялась дважды.

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

Преимущества HMAC:

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

Механизм HMAC был описан в стандартах организаций ANSI, IETF, ISO и NIST.

Реализация HMAC является обязательной (англ. mandatory to implement) для протокола IPsec.

HMAC используется и в других протоколах интернета, например, TLS. Ожидается^[кем?], что TLS вскоре заменит SSL и SET (англ.).

Обозначения

• b, block_size — размер блока в байтах;
• H, hash — хеш-функция;
• ipad — блок вида ( 0x36 0x36 0x36 ... 0x36 ), где байт 0x36 повторяется b раз; 0x36 — константа, магическое число, приведённое в RFC 2104; «i» от «inner»[1];
• K, key — секретный ключ (общий для отправителя и получателя);
• K0 — изменённый ключ K (уменьшенный или увеличенный до размера блока (до b байт));
• L — размер в байтах строки, возвращаемой хеш-функцией H; L зависит от выбранной хеш-функции и обычно меньше размера блока;

• opad — блок вида ( 0x5c 0x5c 0x5c ... 0x5c), где байт 0x5c повторяется b раз; 0x5c — константа, магическое число, приведённое в RFC 2104; «o» от «outer»[1];
• text — сообщение (данные), которое будет передаваться отправителем и подлинность которого будет проверяться получателем;
• n — длина сообщения text в битах.

Алгоритм HMAC можно записать в виде одной формулы[1]: ${\displaystyle \operatorname {HMAC} _{K}(text)=\operatorname {H} {\Bigg (}(K_{0}\oplus opad)\|\operatorname {H} {\Big (}(K_{0}\oplus ipad)\|text{\Big )}{\Bigg )},}$ где:

• «${\displaystyle \oplus }$» — операция «побитовое исключающее ИЛИ» или «xor»;
• «${\displaystyle \|}$» — операция «склейка строк» (последовательностей байт).

Схема работы алгоритма HMAC приведена на рисунках.

Реализация HMAC-MD5

Реализация HMAC-SHA1

Этапы работы алгоритм HMAC перечисленные ниже.

1. Получить K0 путём уменьшения или увеличения ключа K до размера блока (до b байт).

1.1. Если длина ключа K равна размеру блока, то копируем K в K0 без изменений и переходим к шагу 2.

  IF length( K ) == b THEN :
     K_0 = K
  END_IF

1.2. Если длина ключа K больше размера блока, то к ключу K применяем хеш-функцию H, получаем строку размером в L байт, добавляем нули к правой части этой строки для создания строки размером в b байт, копируем результат в K0 и переходим к шагу 2.

  IF length( K ) > b THEN :
     x = H( K ) // length( x ) == L
     K_0 = zeros( x, b - L )
  END_IF

1.3. Если длина ключа K меньше размера блока, то добавляем нули к правой части K для создания строки размером в b байт, копируем результат в K0 (например, если length( К ) = 20 (в байтах) и b = 64 (в байтах), то к правой части К будет добавлено 64 - 20 = 44 нулевых байта (0x00)) и переходим к шагу 2.

  IF length( K ) < b THEN :
     K_0 = zeros( K, b - length( K ) )
  END_IF

2. Получить блок Si размером в b байт с помощью операции «побитовое исключающее ИЛИ» («xor», «${\displaystyle \oplus }$»):

S_i = xor( K₀, ipad ) = K₀ ${\displaystyle \oplus }$ ipad.

3. Получить блок So размером в b байт с помощью операции «побитовое исключающее ИЛИ»:

S_o = xor( K₀, opad ) = K₀ ${\displaystyle \oplus }$ opad.

4. Разбить сообщение (данные, набор байт) text на блоки размером b байт.
5. Склеить строку (последовательность байт) Si с каждым блоком сообщения М.
6. К строке, полученной на прошлом шаге, применить хеш-функцию Н.
7. Склеить строку So со строкой, полученной от хеш-функции H на прошлом шаге.
8. К строке, полученной на прошлом шаге, применить хеш-функцию Н.

Ключи размером меньше L байт, считаются[1] небезопасными (англ. strongly discouraged). Рекомендуется[1] выбирать ключи случайным образом и регулярно их менять. Ключи размером больше L байт, существенно не увеличивают[1] стойкость функции, могут использоваться, если имеются сомнения в случайности данных, используемых для создания ключа и получаемых от генератора случайных чисел.

Размер ключа К должен быть больше или равен L/2 байт.

На рисунке показана более эффективная^{[уточнить]} реализация алгоритма HMAC-MD5. Реализация отличается использованием функции F. Использование этой реализации целесообразно, если большинство сообщений, для которых вычисляется MAC, короткие. Функция F — функция сжатия для хеш-функции H. В качестве аргументов F принимает переменную n и блок длиной в b байт. F производит разбиение блока на цепочку звеньев с длиной каждого звена в n байт. Функция F вызывается для каждого нового ключа один раз.

Далее приведён пример реализации HMAC на псевдокоде:

FUNCTION hmac( key, msg ) :
    // Если размер ключа больше, чем размер блока ...
    IF length( key ) > block_size THEN :
        // Укорачиваем ключ до размера результата хеш-функции
        key = hash( key )
        // (Размер результата хеш-функции обычно меньше (а не равен), чем размер блока хеш-функции)
    END_IF
    // Если ключ меньше, чем размер блока хеш-функции ...
    IF length( key ) < block_size THEN:
        // Дополняем ключ нулевой последовательностью
        key = key ∥ zeroes( block_size - length( key ))
        // оператор "∥" выполняет склейку строк (последовательностей байт)
    END_IF
    
    ipad = [ '\x36' * block_size ]
    // оператор "*" указывает количество повторений последовательности байт,
    // а block_size - размер блока хеш-функции, 
    opad = [ '\x5c' * block_size ]
    
    ikeypad = ipad ⊕ key
    // оператор "⊕" выполняет побитовое исключающее ИЛИ (xor)
    okeypad = opad ⊕ key
    
    RETURN hash( okeypad ∥ hash( ikeypad ∥ msg ) )
    // Оператор "∥" выполняет склейку строк
END_FUNCTION

import hmac, hashlib
print(hmac.new(
    key=b'secret_shared_key',
    msg=open('message.txt', 'rb').read(),
    digestmod=hashlib.md5
).hexdigest())

function hmac ( $key, $data ) {
    $b = 64; // block size according RFC 2104
    if ( strlen( $key ) > $b ) {
        $key = pack( "H*", md5( $key ) );
    }
    $key = str_pad( $key, $b, chr(0x00) );
    $ipad = str_pad( '', $b, chr(0x36) );
    $opad = str_pad( '', $b, chr(0x5c) );
    $k_ipad = $key ^ $ipad ;
    $k_opad = $key ^ $opad;
    return md5( $k_opad . pack("H*", md5( $k_ipad . $data ) ) );
 }

Продемонстрируем пример работы алгоритма для различных входных данных.

Первый параметр — ключ K размером в 160 бит (20 байт). Второй параметр — сообщение text, которое будет передаваться отправителем и подлинность которого будет проверяться получателем. На выходе мы получаем код аутентификации размером в 160 бит.

HMAC( K, text ) = HMAC( 0000000000000000000000000000000000000000, "" ) = 740ca4e7a701540b385df12fe57cff57

HMAC( K, text ) = HMAC( 0000000000000000000000000000000000000000, "Hello World" ) = a0e026219366a56cf843bd2051831327

HMAC( K, text ) = HMAC( 0000000000000000000000000000000000000001, "1" ) = c6b1d8489a204918643086ce346b86bc

Более подробно рассмотрим алгоритм HMAC-SHA1 с ключом размером в 20 байт.

Имеем: текстовое сообщение text = "Hello World" и 20-байтовый ключ в шестнадцатеричном виде K = 0x707172737475767778797a7b7c7d7e7f80818283

Шаг 1. Дополняем ключ K нулевыми байтами до размера блока. Размер блока хеш-функции SHA-1 равен 64 байтам.

K0:
70717273 74757677 78797a7b 7c7d7e7f
80818283 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

Шаг 2. Выполняем операцию «побитовое исключающее ИЛИ» c константой 0x36.

K0 ${\displaystyle \oplus }$ ipad :
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636

Шаг 3. Выполняем склейку исходного сообщения со строкой, полученной на шаге 2.

( K ${\displaystyle \oplus }$ ipad ) || text :
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636
48656c6c 6f20576f 726c64

Шаг 4. Применим хеш-функцию SHA-1 к строке, полученной на прошлом шаге.

H( ( K ${\displaystyle \oplus }$ ipad ) || text ) :
0d42b899 d804e19e bfd86fc4 4f414045 dfc9e39a

Шаг 5. Выполним операцию «побитовое исключающее ИЛИ» c константой 0x5c.

K0 ${\displaystyle \oplus }$ opad :
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c

Шаг 6. Склейка строки, полученной на шаге 4, со строкой, полученной на шаге 5.

( K0 ${\displaystyle \oplus }$ opad ) || H( ( K ${\displaystyle \oplus }$ ipad ) || text ) :
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
0d42b899 d804e19e bfd86fc4 4f414045
dfc9e39a

Шаг 7. Применим хеш-функцию SHA-1 к строке, полученной на прошлом шаге.

HMAC( K, text ) = H( ( K0 ${\displaystyle \oplus }$ opad ) || H( ( K ${\displaystyle \oplus }$ ipad ) || text ) ) :
2e492768 aa339e32 a9280569 c5d02626 2b912431

Итог.

Получили строку HMAC( K, text ) размером в 20 байт.

Полученный код аутентичности позволяет убедиться в том, что данные не изменялись каким бы то ни было способом с тех пор, как они были созданы, переданы или сохранены доверенным источником. Для такого рода проверки необходимо, чтобы, например, две доверяющие друг другу стороны заранее договорились об использовании секретного ключа, который известен только им. Тем самым гарантируется аутентичность источника и сообщения. Недостаток такого подхода очевиден — необходимо наличие двух доверяющих друг другу сторон.

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

Безопасность функции имитовставки (MAC) обычно выражается в терминах вероятности успешного взлома с количеством времени, потраченного на это, а также на получение пары (сообщение — MAC), созданной с тем же ключом. В сущности, это доказано в BELL96a, что при данном уровне усилия (время, сообщение — MAC) на сообщение, сгенерированное конечным пользователем, вероятность успешной атаки на HMAC эквивалентна атаке, произведённой на встроенную хеш-функцию:

1. В первом типе атаки мы можем рассматривать функции сжатия F в качестве эквивалента хеш-функции, применяемой для сообщения, состоящие из единичного блока длиной B бит. Для этого на вход хеш-функции подаётся случайное значение длиной N бит. Нападение на хеш-функцию требует или полного перебора ключа, который обладает уровнем сложности порядка ${\displaystyle 2^{n}}$, или с помощью атаки «дней рождения», которая является частным случаем второго нападения, что обсуждается далее.
2. Во втором типе атаки злоумышленник ищет два сообщения М и М', которые получаются от одинаковой хеш-функции: H( M ) = H( M' ). Этот тип атаки известен также как атака «дней рождения». Уровень сложности данной атаки равен ${\displaystyle 2^{n/2}}$ для хэша длины n. Исходя из этого, безопасность хеш-функции MD5 ставится под вопрос, потому что уровень сложности для него ${\displaystyle 2^{64}}$, что уже не выглядит невозможным при помощи современных^{[когда?]} технологий. Означает ли это, что 128-битная хеш-функция, такая, как MD5, не подходит для HMAC? Ответ на этот вопрос — нет, что последует из следующих аргументов. При атаке на MD5 злоумышленник может выбрать любой набор сообщений и работать оффлайн над поиском коллизий. Так как злоумышленник знает алгоритм хеширования и начальные условия, злоумышленник может создать хеш-код для каждого из сообщений. Однако, при атаке HMAC, злоумышленник не сможет генерировать пару («сообщение», «код») в удалённом (оффлайн) режиме, так как злоумышленник не знает ключа K. Таким образом, злоумышленник должен следить за последовательностью сообщений, порождаемых HMAC с тем же ключом, и выполнять атаку на них. Для хеш-кода длиной 128 бит требуется ${\displaystyle 2^{64}}$ блоков или ${\displaystyle 2^{72}}$ битов, сгенерированных с помощью того же ключа. Для 1-Гбит соединения нужно было бы следить за потоком сообщений, если ключ K не изменяется, в течение 150 000 лет для того чтобы добиться успеха. Таким образом, если скорость имеет значение, вполне приемлемо использовать MD5, а не SHA-1 в качестве встроенных хеш-функций для HMAC.

• Message authentication code (MAC)
• Протокол IPsec
• Хеш-функция MD5
• RSA
• Хеш-функция SHA-1
• DES

• Блэк У. Интернет протоколы безопасности. Москва: издательство «Питер». 2001. ISBN 5-318-00002-9 (ISBN оригинала на английском языке: ISBN 0-13-014249-2).
• RFC 2104. Krawczyk H., Bellare M., Canetti R. «HMAC: Keyed-hashing for message authentication». Февраль 1997.
• Stallings W. Cryptography and network security principles and practices. 2005. ISBN 0-13-187316-4.

• HMAC (англ.).
• RFC 2104. HMAC. Февраль 1997.
• RFC 4226. M'Raihi D., Bellare M., Hoornaert F., Naccache D., Ranen O. «HOTP: an HMAC-based one-time password algorithm». Декабрь 2005.
• Generate HMAC Online. Онлайн-генератор HMAC.