16 июля 2012
Алгоритмы аутентификации сообщений HMAC и NMAC
В предыдущих статьях был подробно описан алгоритм хэширования MD4 и рассмотрены текущие результаты его криптоанализа. Поскольку алгоритм MD4 использовался (и используется до сих пор) не только в «чистом» виде, но и в различных алгоритмах аутентификации сообщений, обзор данного алгоритма будет неполным без рассмотрения двух его вариантов: HMAC-MD4 и NMAC-MD4. Начнем с описания алгоритмов ключевого хэширования HMAC и NMAC, а обзору криптоанализа HMAC-MD4 и NMAC-MD4 будет посвящена следующая статья.
Коды аутентификации сообщений
Код аутентификации сообщения (Message authentication code – MAC) представляет собой криптографическую контрольную сумму сообщения. MAC вычисляется на основе ключа и текста сообщения произвольной длины и используется для проверки целостности сообщения [1]. Для вычисления MAC используются ключевые алгоритмы хэширования (или ключевые надстройки над алгоритмами хэширования), алгоритмы блочного шифрования или специальные алгоритмы вычисления кодов аутентификации сообщений.
В отличие от алгоритмов электронной цифровой подписи (ЭЦП), в которых для вычисления ЭЦП используется закрытый ключ, а для проверки ЭЦП – вычисляемый из закрытого открытый ключ, при вычислении и проверке MAC используется один и тот же секретный ключ. Следовательно, в отличие от ЭЦП, MAC не используется для установления авторства сообщения, поскольку секретный ключ принадлежит более, чем одному пользователю.
Схема использования MAC приведена на рис. 1.
Рис. 1 Схема использования MAC
Алгоритм HMAC
Алгоритм HMAC (Hash-based Message Authentication Code – код аутентификации сообщения на основе хэширования), фактически, является надстройкой над алгоритмом хэширования, которая позволяет вычислять хэш-значение с использованием ключа с помощью, практически, произвольного бесключевого алгоритма хэширования [2]. HMAC является не единственным алгоритмом аутентификации данных на основе хэш-функций, но наиболее распространенным из подобных алгоритмов.
HMAC является одним из вариантов MAC и, следовательно, используется для контроля целостности сообщений. В данном случае в основе алгоритма лежит функция хэширования, которая позволяет вычислить код аутентификации сообщения следующим образом (см. рис. 2):
- Размер ключа выравнивается с размером блока используемого алгоритма хэширования:
- если ключ key длиннее блока, он укорачивается путем применения к нему используемого алгоритма хэширования hash (этот вариант не показан на рис. 2):
key = hash(key);
отметим, что размер выходного значения алгоритма хэширования обычно много меньше размера блока хэшируемых данных – например, соответственно 128 и 512 битов для алгоритма MD4; в [2] рекомендуется минимальный размер ключа, равный размеру выходного значения алгоритма хэширования;
- если размер ключа меньше размера блока, то выровненный ключ k получается путем дополнения до размера блока нулевыми битами исходного (или укороченного) ключа key.
- Выровненный ключ k складывается по модулю 2 с константой C1, которая представляет собой блок данных, заполненный байтами с шестнадцатеричным значением 36; аналогичным образом ключ k также складывается с константой C2, которая представляет собой блок данных, заполненный байтами с шестнадцатеричным значением 5С:
ki = k ⊕ C1;
ko = k ⊕ C2.
- Вычисляется хэш-значение от результата конкатенации модифицированного ключа ki и сообщения m:
t = hash(ki || m).
- Выходным значением алгоритма HMAC является хэш-значение от результата конкатенации модифицированного ключа ko и полученного на предыдущем шаге значения t:
hmac = hash(ko || t).
Таким образом, при вычислении HMAC используемый алгоритм хэширования применяется дважды; каждый раз с участием модифицированного ключа. Размер выходного значения алгоритма HMAC равен размеру выходного значения алгоритма хэширования, а общая формула вычисления HMAC (без учета выравнивания ключа) выглядит следующим образом:
HMAC(k, m) = hash((k ⊕ C2) || hash((k ⊕ C1) || m)).
Рис. 2 Вычисление HMAC
Алгоритмы, построенные с помощью HMAC, традиционно называют следующим образом:
- «HMAC-x», где «x» – используемый алгоритм хэширования, например, HMAC-MD4;
- «HMAC-x-k» в тех случаях, где выходное значение алгоритма хэширования может быть усечено (т. е. может использоваться частично); в данном случае «k» – размер выходного значения алгоритма HMAC в битах; пример – алгоритм HMAC-SHA1-80 [2].
Стоит отметить, что быстродействие HMAC не намного хуже, чем у используемой функции хэширования, что особенно заметно при хэшировании длинных сообщений, поскольку само сообщение при использовании HMAC обрабатывается однократно [3].
Криптостойкость HMAC
Криптостойкость HMAC зависит, прежде всего, от следующих факторов [4]:
- криптостойкость используемого алгоритма хэширования;
- размер выходного значения алгоритма;
- размер и качество ключа.
В [2] показано, что контексты атак на HMAC и «классическое» использование алгоритма хэширования заметно различаются. Атакующий алгоритм HMAC может преследовать следующие цели:
- подобрать сообщение, HMAC которого равен эталонному или равен HMAC эталонного сообщения [3]; это похоже на атаки на классическое применение алгоритма хэширования по поиску первого или второго прообраза;
- найти корректную пару «сообщение – код аутентификации данного сообщения» или вычислить код аутентификации сообщения для заданного сообщения без знания секретного ключа [5];
- получить ключ, используемый для вычисления HMAC [5].
Алгоритм NMAC
Алгоритм NMAC был также предложен авторами алгоритма HMAC в [6]. Данный алгоритм позволяет использовать при аутентификации сообщений два ключа: k1 и k2. Формула вычисления NMAC крайне проста:
NMAC(k1, k2, m) = hash(k2, hash(k1, m)),
где второй параметр функции hash() обозначает хэшируемое сообщение, а первый параметр – нестандартный вектор инициализации, в качестве которого используется ключ (соответственно, k1 и k2 обозначают уже выровненные до размера вектора инициализации ключи).
NMAC является, фактически, обобщением HMAC, поскольку ключи k1 и k2 можно использовать независимо, а можно представить как производные от единственного ключа k, вычисляемые следующим образом [3]:
k1 = h(k ⊕ C1);
k2 = h(k ⊕ C2),
где h() – функция сжатия используемого алгоритма хэширования; в данном случае применяется стандартный вектор инициализации алгоритма.
Схема NMAC приведена на рис. 3.
Рис. 3 Вычисление NMAC
Литература:
- Message authentication code. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
- Krawczyk H., Bellare M., Canetti R. RFC 2104. HMAC: Keyed-Hashing for Message Authentication. // http://tools.ietf.org – February 1997.
- Kim J., Biryukov A., Preneel B., Hong S. On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0, and SHA-1. // http://eprint.iacr.org – 2006.
- HMAC. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
- Contini S., Yin Y. L. Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. // http://www.iacr.org – 2006.
- Bellare M., Canetti R., Krawczyk H. Keying Hash Functions for Message Authentication. // http://cseweb.ucsd.edu – June 1996.
