Просмотр кода страницы HMAC

'''HMAC''' ([[бэкроним|иногда расшифровывается]] как {{lang-en|hash-based message authentication code}}, код [[Аутентификация|аутентификации]] (проверки подлинности) сообщений, использующий [[Хеш-сумма|хеш]]-[[Функция (программирование)|функции]], или как {{lang-en|keyed-hash message authentication code}}, код аутентификации сообщений, использующий хеш-функции с ключом) — в [[Информатика|информатике]] ([[Криптография|криптографии]]), один из механизмов проверки целостности информации, позволяющий гарантировать то, что данные, передаваемые или хранящиеся в ненадёжной среде, не были изменены посторонними лицами (см. [[человек посередине]]). Механизм HMAC использует [[имитовставка|имитовставку (MAC)]], описан в RFC 2104, в стандартах организаций [[ANSI]], [[IEF]], [[ISO]] и [[NIST]]. MAC — стандарт, описывающий способ обмена данными и способ проверки целостности передаваемых данных с использованием секретного ключа. Два клиента, использующие MAC, как правило, используют общий секретный ключ. HMAC — надстройка над MAC; механизм обмена данными с использованием секретного ключа (как в MAC) и [[хеш-функция|хеш-функций]]. В названии может уточняться используемая хеш-функция<ref name="rfc2104" />: HMAC-[[MD5]], HMAC-[[SHA-1|SHA1]], HMAC-[[RIPEMD-128|RIPEMD128]], HMAC-[[RIPEMD-160|RIPEMD160]] и т. п.

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

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

В июне 1996 года<ref>Mihir Bellare, Ran Canetti и Hugo Krawczyk. «Keying hash functions for message authentication». 1996. [http://www-cse.ucsd.edu/users/mihir/papers/hmac.html#kmd5-paper Скачать PDF] {{Wayback|url=http://www-cse.ucsd.edu/users/mihir/papers/hmac.html#kmd5-paper |date=20090509205612 }}.</ref> Хьюго Кравчик ({{lang-en|Hugo Krawczyk}}, сотрудник фирмы [[IBM]]), {{iw|Беллар, Михир|Михир Беллар|en|Mihir Bellare}} ({{lang-en|Mihir Bellare}}, сотрудник [[Калифорнийский университет в Сан-Диего|калифорнийского университета в Сан-Диего (UCSD)]]) и Ран Каннетти ({{lang-en|Ran Canetti}}, сотрудник фирмы [[IBM]]) опубликовали описание механизма HMAC, а в феврале 1997 года ими же был выпущен RFC 2104. В HMAC данные «смешивались» с ключом, и хеш-функция применялась дважды.

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

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

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

== Применение ==
Реализация HMAC является обязательной ({{lang-en|mandatory to implement}}) для протокола [[IPsec]].

HMAC используется и в других протоколах [[интернет]]а, например, [[Transport Layer Security|TLS]]. 

== Описание алгоритма ==
; Обозначения:
* <code>b</code>, <code>block_size</code> — размер блока в [[байт]]ах;
* <code>H</code>, <code>hash</code> — хеш-функция;
* <code>ipad</code> — блок вида <code>( 0x36 0x36 0x36 ... 0x36 )</code>, где байт <code>0x36</code> повторяется <code>b</code> раз; <code>0x36</code> — константа, [[Магическое число (программирование)|магическое число]], приведённое в RFC 2104; «i» от «inner»<ref name="rfc2104" />;
* <code>K</code>, <code>key</code> — секретный ключ (общий для отправителя и получателя);
* <code>K<sub>0</sub></code> — изменённый ключ <code>K</code> (уменьшенный или увеличенный до размера блока (до <code>b</code> байт));
* <code>L</code> — размер в байтах строки, возвращаемой хеш-функцией <code>H</code>; <code>L</code> зависит от выбранной хеш-функции и обычно меньше размера блока;
{| class="wikitable"
! [[Хеш-функция]] <code>H</code>
! <code>b</code>, [[байт]]
! <code>L</code>, [[байт]]
|-
| [[MD5]] || 64 || 16
|-
| [[SHA-1]] || 64 || 20
|-
| [[SHA-2|SHA-224]] || 64 || 28
|-
| [[SHA-2|SHA-256]] || 64 || 32
|-
| [[SHA-2|SHA-512/224]] || 128 || 28
|-
| [[SHA-2|SHA-512/256]] || 128 || 32
|-
| [[SHA-2|SHA-384]] || 128 || 48
|-
| [[SHA-2|SHA-512]] || 128 || 64
|-
| [[SHA-3|SHA3-224]] || 144 || 28
|-
| [[SHA-3|SHA3-256]] || 136 || 32
|-
| [[SHA-3|SHA3-384]] || 104 || 48
|-
| [[SHA-3|SHA3-512]] || 72 || 64
|-
| colspan=3 | <code>out = H( in )<br />b = length( in )<br />L = length( out )</code>
|}
* <code>opad</code> — блок вида <code>( 0x5c 0x5c 0x5c ... 0x5c)</code>, где байт <code>0x5c</code> повторяется <code>b</code> раз; <code>0x5c</code> — константа, [[Магическое число (программирование)|магическое число]], приведённое в RFC 2104; «o» от «outer»<ref name="rfc2104" />;
* <code>text</code> — сообщение (данные), которое будет передаваться отправителем и подлинность которого будет проверяться получателем;
* <code>n</code> — длина сообщения <code>text</code> в [[бит]]ах.

Алгоритм HMAC можно записать в виде одной формулы<ref name="rfc2104" />:
<math>\operatorname{HMAC}_K(text) = \operatorname{H} \Bigg( ( K_0 \oplus opad ) \| \operatorname{H} \Big( ( K_0 \oplus ipad ) \| text \Big) \Bigg) ,</math>
где:
* «<math>\oplus</math>» — операция «побитовое [[Сложение по модулю 2|исключающее ИЛИ]]» или «xor»;
* «<math>\|</math>» — операция «[[Конкатенация|склейка]] строк» (последовательностей байт).

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

[[Файл:HMACFig2.jpg|thumbnail|300px| Реализация HMAC-[[MD5]]]]
[[File:SHAhmac.svg|thumb|right|400px|Реализация HMAC-[[SHA-1|SHA1]]]]

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

# Получить <code>K<sub>0</sub></code> путём уменьшения или увеличения ключа <code>K</code> до размера блока (до <code>b</code> байт).

::: 1.1. Если длина ключа <code>K</code> равна размеру блока, то копируем <code>K</code> в <code>K<sub>0</sub></code> без изменений и переходим к шагу 2.
   '''IF''' length( K ) == b '''THEN''' :
      K_0 = K
   '''END_IF'''

::: 1.2. Если длина ключа <code>K</code> больше размера блока, то к ключу <code>K</code> применяем хеш-функцию <code>H</code>, получаем строку размером в <code>L</code> байт, добавляем нули к правой части этой строки для создания строки размером в <code>b</code> байт, копируем результат в <code>K<sub>0</sub></code> и переходим к шагу 2.
   '''IF''' length( K ) > b '''THEN''' :
      x = H( K ) {{color|blue|''// length( x ) {{=}}{{=}} L''}}
      K_0 = zeros( x, b - L )
   '''END_IF'''

::: 1.3. Если длина ключа <code>K</code> меньше размера блока, то добавляем нули к правой части <code>K</code> для создания строки размером в <code>b</code> байт, копируем результат в <code>K<sub>0</sub></code> (например, если <code>length( К ) = 20</code> (в байтах) и <code>b = 64</code> (в байтах), то к правой части <code>К</code> будет добавлено <code>64 - 20 = 44</code> нулевых байта (<code>0x00</code>)) и переходим к шагу 2.
   '''IF''' length( K ) < b '''THEN''' :
      K_0 = zeros( K, b - length( K ) )
   '''END_IF'''

# <li value="2"> Получить блок <code>S<sub>i</sub></code> размером в <code>b</code> байт с помощью операции «побитовое [[Сложение по модулю 2|исключающее ИЛИ]]» («xor», {{nobr|«<math>\oplus</math>»}}):
<center>S<sub>i</sub> = xor( K<sub>0</sub>, ipad ) = K<sub>0</sub> <math>\oplus</math> ipad.</center>

# <li value="3"> Получить блок <code>S<sub>o</sub></code> размером в <code>b</code> байт с помощью операции «побитовое [[Сложение по модулю 2|исключающее ИЛИ]]»:
<center>S<sub>o</sub> = xor( K<sub>0</sub>, opad ) = K<sub>0</sub> <math>\oplus</math> opad.</center>

# <li value="4"> Разбить сообщение (данные, набор байт) <code>text</code> на блоки размером <code>b</code> байт.
# [[Конкатенация|Склеить]] строку (последовательность байт) <code>S<sub>i</sub></code> с каждым блоком сообщения <code>М</code>.
# К строке, полученной на прошлом шаге, применить хеш-функцию <code>Н</code>.
# [[Конкатенация|Склеить]] строку <code>S<sub>o</sub></code> со строкой, полученной от хеш-функции <code>H</code> на прошлом шаге.
# К строке, полученной на прошлом шаге, применить хеш-функцию <code>Н</code>.

Ключи размером меньше <code>L</code> байт, считаются<ref name="rfc2104" /> небезопасными ({{lang-en|strongly discouraged}}). Рекомендуется<ref name="rfc2104" /> выбирать ключи случайным образом и регулярно их менять. Ключи размером больше <code>L</code> байт, существенно не увеличивают<ref name="rfc2104" /> стойкость функции, могут использоваться, если имеются сомнения в случайности данных, используемых для создания ключа и получаемых от генератора случайных чисел.

Размер ключа <code>К</code> должен быть больше или равен <code>L/2</code> байт{{нет АИ|9|3|2015}}.

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

== Псевдокод ==
Далее приведён пример реализации '''HMAC''' на [[Псевдокод (язык описания алгоритмов)|псевдокоде]]:

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

=== Примеры кода ===
Пример реализации алгоритма HMAC-MD5 с помощью функций стандартной библиотеки языка [[Python]]<ref>{{cite web| author        =| authorlink        =| datepublished        =| url        =http://docs.python.org/library/hmac.html| title        =реализация на языке Python| format        =| work        =| publisher        =| accessdate        =| lang        =en| description        =source code| archiveurl        =https://www.webcitation.org/68A6JimOs?url=http://docs.python.org/library/hmac.html| archivedate        =2012-06-04| deadurl        =yes}}</ref>:
<source lang="python">
import hmac, hashlib
print(hmac.new(
    key=b'secret_shared_key',
    msg=open('message.txt', 'rb').read(),
    digestmod=hashlib.md5
).hexdigest())
</source>

Одна из возможных реализаций алгоритма HMAC-MD5 на языке [[PHP]]<ref>{{cite web| author        =| authorlink        =| datepublished        =| url        =http://php.net/manual/en/function.mhash.php| title        =реализация на языке PHP| format        =| work        =| publisher        =| accessdate        =| lang        =en| description        =source code| archiveurl        =https://www.webcitation.org/68A6KImOH?url=http://php.net/manual/en/function.mhash.php| archivedate        =2012-06-04| deadurl        =yes}}</ref>:
<source lang="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 ) ) );
 }
</source>

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

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

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

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

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

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

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

; Шаг 1. Дополняем ключ <code>K</code> нулевыми байтами до размера блока. Размер блока хеш-функции [[SHA-1]] равен 64 байтам.
<code>K<sub>0</sub>: <br />
70717273 74757677 78797a7b 7c7d7e7f<br />
80818283 00000000 00000000 00000000<br />
00000000 00000000 00000000 00000000<br />
00000000 00000000 00000000 00000000</code>

; Шаг 2. Выполняем операцию «побитовое исключающее ИЛИ» c константой <code>0x36</code>.
<code>K<sub>0</sub> <math>\oplus</math> ipad :<br />
46474445 42434041 4e4f4c4d 4a4b4849<br /> 
b6b7b4b5 36363636 36363636 36363636<br /> 
36363636 36363636 36363636 36363636<br /> 
36363636 36363636 36363636 36363636</code>

; Шаг 3. Выполняем склейку исходного сообщения со строкой, полученной на шаге 2.
<code>( K <math>\oplus</math> ipad ) || text :<br />
46474445 42434041 4e4f4c4d 4a4b4849<br /> 
b6b7b4b5 36363636 36363636 36363636<br /> 
36363636 36363636 36363636 36363636<br /> 
36363636 36363636 36363636 36363636<br />
48656c6c 6f20576f 726c64</code>

; Шаг 4. Применим хеш-функцию [[SHA-1]] к строке, полученной на прошлом шаге.
<code>H( ( K <math>\oplus</math> ipad ) || text ) :<br />
0d42b899 d804e19e bfd86fc4 4f414045 dfc9e39a</code>

; Шаг 5. Выполним операцию «побитовое исключающее ИЛИ» c константой <code>0x5c</code>.
<code>K<sub>0</sub> <math>\oplus</math> opad :<br />
2c2d2e2f 28292a2b 24252627 20212223<br />
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c<br />
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c<br />
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c</code>

; Шаг 6. Склейка строки, полученной на шаге 4, со строкой, полученной на шаге 5.
<code>( K<sub>0</sub> <math>\oplus</math> opad ) || H( ( K <math>\oplus</math> ipad ) || text ) :<br />
2c2d2e2f 28292a2b 24252627 20212223<br />
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c<br />
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c<br />
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c<br />
0d42b899 d804e19e bfd86fc4 4f414045<br />
dfc9e39a</code>

; Шаг 7. Применим хеш-функцию [[SHA-1]] к строке, полученной на прошлом шаге.
<code>HMAC( K, text ) = H( ( K<sub>0</sub> <math>\oplus</math> opad ) || H( ( K <math>\oplus</math> ipad ) || text ) ) :<br />
2e492768 aa339e32 a9280569 c5d02626 2b912431</code>

; Итог.: Получили строку <code>HMAC( K, text )</code> размером в 20 байт.

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

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

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

== См. также ==
* [[Message authentication code]] (MAC)
* Протокол [[IPsec]]
* Хеш-функция [[MD5]]
* [[RSA]]
* Хеш-функция [[SHA-1]]
* [[DES]]

== Источники ==
* Блэк&nbsp;У. Интернет протоколы безопасности. Москва: издательство «Питер». 2001. ISBN 5-318-00002-9 (ISBN оригинала на английском языке: ISBN 0-13-014249-2).
* [[RFC]] [https://tools.ietf.org/html/rfc2104 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.

== Примечания ==
{{Примечания|refs=
<ref name="rfc2104">Krawczyk H., Bellare M., Canetti R. «HMAC: Keyed-hashing for message authentication». [[RFC]] [https://tools.ietf.org/html/rfc2104 2104] {{Wayback|url=https://tools.ietf.org/html/rfc2104 |date=20210415003434 }}. Февраль 1997.</ref>
}}

== Ссылки ==
* HMAC{{ref-en}}.
* [http://www.faqs.org/rfcs/rfc2104.html RFC 2104]. HMAC. Февраль 1997.
* [http://www.ietf.org/rfc/rfc4226.txt RFC 4226]. M'Raihi D., Bellare M., Hoornaert F., Naccache D., Ranen O. «[[HOTP]]: an HMAC-based one-time password algorithm». Декабрь 2005.
* [https://web.archive.org/web/20160919140616/https://dev-tips.org/Generators/Hash/HMAC Generate HMAC Online]. Онлайн-генератор HMAC.

[[Категория:Аутентификация]]
[[Категория:Коды аутентификации сообщений]]
[[Категория:Криптографические хеш-функции]]