HMAC

HMAC (сокращение от англ. hash-based message authentication code, хеш-код идентификации сообщений). Наличие способа проверить целостность информации, передаваемой или хранящийся в ненадежной среде является неотъемлемой и необходимой частью мира открытых вычислений и коммуникаций. Механизмы, которые предоставляют такие проверки целостности на основе секретного ключа, обычно называют кодом аутентичности сообщения(MAC). Как правило, МАС используется между двумя сторонами, которые разделяют секретный ключ для проверки подлинности информации, передаваемой между этими сторонами. Этот стандарт определяет MAC. Механизм, который использует криптографические хеш-функции в сочетании с секретным ключом называется HMAC.

Основная цель:

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

Разработчики: Хьюго Кравчик, Михир Беллар и Ран Каннетти.

Описание

В последние годы наблюдается повышенный интерес к разработке MAC на основе криптографических хэш-функций, например, MD5, SHA-1 или RIPEMD-160. А мотивы этого интереса просты:

• Криптографические хэш-функции обычно в программах работают быстрее, чем при использовании симметричных блочных шифров, такие как DES.
• Библиотечные коды для криптографической хэш-функции широко доступны.
• Хэш-функции, такие как MD5, не предназначены для использования в качестве MAC и не могут быть использованы непосредственно для этой цели, поскольку они не опираются на секретный ключ. Было сделано несколько предложений для включения секретного ключа в существующие хэш-алгоритмы. HMAC получил наибольшую поддержку.

HMAC был выбран в качестве обязательной (англ. mandatory to implement) при реализации MAC для IP-безопасности, и используется в других интернет-протоколах, таких, как Transport Layer Security (TLS, который вскоре заменит Secure Sockets Layer) и Secure Electronic Transaction (SET).

Принцип работы

Эффективная реализация HMAC

На рисунке 1 показан общий алгоритм HMAC:

1. Если длина ключа К = b, то $K_{0}$ = K . Переходим сразу к шагу 4.
2. Если длина ключа K > b, то применяем H к ключу K для получения L-байтовой строки. Добавить нули к левой части этой строки для создания b-байтовой строки $K_{0}$.Переходим сразу к шагу 4.
3. Если длина ключа K < b то добавляем нули к левой части K для создания b-байтовой строки $K_{0}$ (например, если К имеет длину 20 байтов и b = 64, то к левой части К будет добавлено 44 нулевых байта 0x00).
4. $K_{0}$ $\oplus$ ipad — (xor побитовое исключающее ИЛИ) для получения b-байтового блока $S_{i}$.
5. Сложить М с $S_{i}$.
6. Применить Н к потоку, созданному на шаге 5.
7. $K_{0}$ $\oplus$ opad для получения b-байтового блока $S_{o}$.
8. Сложить результат хеширования на шаге 6 с $S_{o}$.
9. Применить Н к потоку, созданному на шаге 8 и вывести результат.

или если выразить одной математической формулой : $\mathrm {HMAC} _{K}(m)=h{\Bigg (}(K\oplus \mathrm {opad} )\|h{\Big (}(K\oplus \mathrm {ipad} )\|m{\Big )}{\Bigg )}$

Более эффективная реализация возможна, как показано на рисунке 2. Где F является функция сжатия для хэш-функции, которая принимает в качестве аргументов: переменную N и блок длиной b байт, и производит разбиение блока в цепочку блоков с длиной каждого N байтов. Эти операции необходимо выполнить только в самом начале и каждый раз, когда ключ изменяется. В этой реализации, появляется только один дополнительный элемент - функция сжатия F для нормальной работы хэш-функции. Это реализация особенно целесообразна, если большинство сообщений, для которых вычисляется MAC , короткие.

HMAC параметры и обозначения

HMAC алгоритм использует следующие параметры:

• b - размер блока (в байтах).
• H - хэш-функция.
• ipad - блок вида : (0x363636 ... 3636). Повторяется b раз.
• К - секретный ключ.
• $K_{0}$ - это K после предварительной необходимой обработки для получения b-байтового ключа.
• L - размер блока (в байтах) на выходе хэш-функции.
• opad - блок вида : (0x5c5c5c ... 5c5c). Повторяется b раз.
• М - передаваемое сообщение. Длина сообщения N бит.

Криптографический ключ

Размер ключа, К, должен быть больше или равен $L/2$. Стоит обратить внимание, что ключи с размером больше чем L байт уже не существенно увеличивают криптографическую стойкость функции.

Псевдокод

Следующий псевдокод показывает как HMAC может быть реализован:

FUNCTION hmac(key, msg):
    IF len(key) > blocksize THEN: // Если ключ БОЛЬШЕ чем размер блока...
        key = hash(key) // Укорачиваем ключ до размера результата хеш-функции
        //    (Размер результата хеш-функции обычно МЕНЬШЕ (а не равен) чем размер блока хеш-функции)
    END_IF
    IF len(key) < blocksize THEN: // Если ключ МЕНЬШЕ чем размер блока хеш-функции...
        key = key ∥ zeroes(blocksize - len(key)) // Дополняем ключ нулевой последовательностью
    END_IF
    
    ipad = ['\x36' * blocksize] // Где оператор "*" - указывает сколько раз повторять элемент последовательности,
    opad = ['\x5c' * blocksize] //    а blocksize - это размер блока хэш-функции, 
    
    ikeypad = ipad ⊕ key // Где оператор "⊕" - осуществляет побитовое ИСКЛЮЧАЮЩЕЕ-ИЛИ (XOR)
    okeypad = opad ⊕ key
    
    RETURN hash(okeypad ∥ hash(ikeypad ∥ msg)) // Где оператор "∥" - осуществляет операцию конкатенации
END_FUNCTION

Возможные реализации

Представленные ниже языки программирования были выбраны из-за наличия стандартных библиотек, поддерживающих данный алгоритм. Пример использования реализации алгоритма на языке Python:

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

Одна из возможных реализаций алгоритма на языке PHP:

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)));
 }

Примеры

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

Первый параметр — 160-битный ключ. Второй параметр — передаваемое сообщение. На выходе мы получаем 160-битный код аутентификации.

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

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

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

Рассмотрим более подробно алгоритм HMAC на примере хэш-функции SHA-1 с 20-байтовым ключом:
Имеем: текстовое сообщение
Text: Hello World

и 20-байтовый ключ в шестнадцатеричном виде
Key:
0x707172737475767778797a7b7c7d7e7f80818283

1 шаг:
Дополняем Key нулевыми байтами до размера блока SHA-1(64 байта)
$K_{0}$:
70717273 74757677 78797a7b 7c7d7e7f
80818283 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

2 шаг:
Побитовое исключающее ИЛИ
$K_{0}$ $\oplus$ ipad:
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636

3 шаг:
Конкатенация исходного сообщения с результатом на шаге 2
(Key $\oplus$ ipad)||text:
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636
48656c6c 6f20576f 726c64

4 шаг:
Применим SНA-1 к результату, созданному на шаге 3
Hash((Key $\oplus$ ipad)||text):
0d42b899 d804e19e bfd86fc4 4f414045 dfc9e39a

5 шаг:
Побитовое исключающее ИЛИ
$K_{0}$ $\oplus$ opad:
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c

6 шаг:
Конкатенация результата хеширования на шаге 4 с результатом на шаге 5
($K_{0}$ $\oplus$ opad) || Hash((Key $\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 шаг:
Применим SНA-1 к результату, созданному на шаге 6
HMAC(Key, Text) = Hash(($K_{0}$ $\oplus$ opad) || Hash((Key $\oplus$ ipad)||text)):
2e492768 aa339e32 a9280569 c5d02626 2b912431
получили 20 байтовый HMAC(Key, Text)

Вопросы использования

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

Безопасность

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

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

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

Стандартизация

Конструкция HMAC стандартизирована организациями ANSI, IETF, ISO и NIST.

См. также

• Message authentication code
• IPSec
• MD5
• RSA
• SHA-1
• DES

Источники

• У. Блэк — Интернет протоколы безопасности, Москва, издательство «Питер», 2001 ISBN 5-318-00002-9 (ISBN 0-13-014249-2 английский оригинал)
• RFC 2104
• Stallings W — Cryptography and Network Security Principles and Practices, 2005 ISBN 0-13-187316-4

Ссылки

• http://www.faqs.org/rfcs/rfc2104.html
• http://www.ietf.org/rfc/rfc4226.txt