HMAC

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

HMAC (сокращение от англ. hash-based message authentication code, код аутентификации (проверки подлинности) сообщений, использующий хеш-функции) — в информатике (криптографии), один из механизмов проверки целостности информации, позволяющий гарантировать то, что данные, передаваемые или хранящиеся в ненадёжной среде, не были изменены посторонними лицами (см. человек посередине). Механизм HMAC использует MAC, описан в RFC 2104, в стандартах организаций ANSI, IETF, ISO и NIST. MAC — стандарт, описывающий способ обмена данными и способ проверки целостности передаваемых данных с использованием секретного ключа. Два клиента, использующие MAC, как правило, разделяют общий секретный ключ. HMAC — надстройка над MAC; механизм обмена данными с использованием секретного ключа (как в MAC) и хеш-функций. В зависимости от используемой хеш-функции выделяют[1] HMAC-MD5, HMAC-SHA1, HMAC-RIPEMD128, HMAC-RIPEMD160 и т. п.

История[править | править вики-текст]

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

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

В июне 1996 года[2] Хьюго Кравчик (англ. Krawczyk Hugo, сотрудник фирмы IBM), Михир Беллар (англ. Bellare Mihir, сотрудник калифорнийского университета в Сан-Диего (UCSD)) и Ран Каннетти (англ. Canetti Ran, сотрудник фирмы 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];
  • К, key — секретный ключ (общий для отправителя и получателя);
  • K0 — изменённый ключ K (уменьшенный или увеличенный до размера блока (до b байт));
  • L — размер в байтах строки, возвращаемой хэш-функцией H; L зависит от выбранной хэш-функции и обычно меньше размера блока;
Хэш-функция H b, байт L, байт
MD5 64 16
SHA-1 64 20
out = H( in )
b = length( in )
L = length( out )
  • opad — блок вида ( 0x5c 0x5c 0x5c ... 0x5c), где байт 0x5c повторяется b раз; 0x5c — константа, магическое число, приведённое в RFC 2104; «o» от «outer»[1];
  • text — сообщение (данные), которое будет передаваться отправителем и подлинность которого будет проверяться получателем;
  • n — длина сообщения text в битах.

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

Схема работы алгоритма 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
  1. Получить блок Si размером в b байт с помощью операции «побитовое исключающее ИЛИ» («xor», «\oplus»):
Si = xor( K0, ipad ) = K0 \oplus ipad.
  1. Получить блок So размером в b байт с помощью операции «побитовое исключающее ИЛИ»:
So = xor( K0, opad ) = K0 \oplus opad.
  1. Разбить сообщение (данные, набор байт) text на блоки размером b байт.
  2. Склеить строку (последовательность байт) Si с каждым блоком сообщения М.
  3. К строке, полученной на прошлом шаге, применить хэш-функцию Н.
  4. Склеить строку So со строкой, полученной от хэш-функции H на прошлом шаге.
  5. К строке, полученной на прошлом шаге, применить хэш-функцию Н.

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

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

На рисунке показана более эффективная реализация алгоритма 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

Примеры кода[править | править вики-текст]

Пример реализации алгоритма HMAC-MD5 с помощью функций стандартной библиотекой языка Python[3]:

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

Одна из возможных реализаций алгоритма HMAC-MD5 на языке PHP[4]:

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 бит (5 байт). Второй параметр — сообщение 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 = "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.
Выполняем операцию «побитовое исключающее ИЛИ»

K0 \oplus ipad :
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636

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

( K \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 \oplus ipad ) || text ) :
0d42b899 d804e19e bfd86fc4 4f414045 dfc9e39a

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

K0 \oplus opad :
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c

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

( K0 \oplus opad ) || H( ( K \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 \oplus opad ) || H( ( K \oplus ipad ) || text ) ) :
2e492768 aa339e32 a9280569 c5d02626 2b912431

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

Вопросы использования[править | править вики-текст]

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

Безопасность[править | править вики-текст]

Безопасность любой функции 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, злоумышленник не сможет генерировать пару («сообщение», «код») в удалённом (оффлайн) режиме, так как злоумышленник не знает ключа K. Таким образом, злоумышленник должен следить за последовательностью сообщений, порождаемых HMAC с тем же ключом, и выполнять атаку на них. Для хэш-кода длиной 128 бит требуется 2^{64} блоков или 2^{72} битов, сгенерированных с помощью того же ключа. Для 1-Гбит соединения нужно было бы следить за потоком сообщений, если он не изменяет ключ K, в течение 150 000 лет, чтобы добиться успеха. Таким образом, если скорость имеет значение, вполне приемлемо использовать MD5, а не SHA-1 в качестве встроенных хэш-функций для HMAC.

См. также[править | править вики-текст]

Источники[править | править вики-текст]

  • Блэк У. Интернет протоколы безопасности. Москва: издательство «Питер». 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.

Примечания[править | править вики-текст]

  1. 1 2 3 4 5 6 7 Krawczyk H., Bellare M., Canetti R. «HMAC: Keyed-hashing for message authentication». RFC 2104. Февраль 1997.
  2. Mihir Bellare, Ran Canetti и Hugo Krawczyk. «Keying hash functions for message authentication». 1996. Скачать PDF.
  3. реализация на языке Python (англ.). — source code. Архивировано из первоисточника 4 июня 2012.
  4. реализация на языке PHP (англ.). — source code. Архивировано из первоисточника 4 июня 2012.

Ссылки[править | править вики-текст]

  • 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.