Хэш-функции сообщений с ключом (HMAC): принципы и безопасность.

Введение

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

Принципы проектирования

Разработка спецификации HMAC была обусловлена существованием атак на более простые механизмы объединения ключа с хэш-функцией. Например, можно предположить, что аналогичный уровень безопасности, обеспечиваемый HMAC, можно достичь с помощью MAC = H(ключ || сообщение). Однако этот метод имеет серьезный недостаток: для большинства хэш-функций легко добавить данные к сообщению, не зная ключа, и получить другой допустимый MAC ("атака на расширение длины"). Альтернативный вариант, добавление ключа с помощью MAC = H(сообщение || ключ), страдает от проблемы, что злоумышленник, способный найти коллизию в (неключевой) хэш-функции, сможет найти коллизию и в MAC (поскольку два сообщения m1 и m2, дающие одинаковый хэш, предоставят хэш-функции одно и то же начальное состояние перед хэшированием добавленного ключа, а значит, итоговый хэш будет одинаковым). Использование MAC = H(ключ || сообщение || ключ) лучше, но в различных работах по безопасности указываются уязвимости этого подхода, даже при использовании двух разных ключей. В текущей спецификации HMAC, определяемой как H(ключ || H(ключ || сообщение)), неизвестно атак на расширение длины, поскольку внешнее применение хэш-функции маскирует промежуточный результат внутренней хэш-функции. Значения ipad и opad не критичны для безопасности алгоритма, но были определены таким образом, чтобы иметь большое расстояние Хэмминга друг от друга, и, следовательно, внутренний и внешний ключи имели меньше общих битов. Безопасность HMAC требует, чтобы они отличались хотя бы в одном бите. Хэш-функция Keccak, выбранная NIST в качестве победителя конкурса SHA 3, не нуждается в этом вложенном подходе и может использоваться для генерации MAC, просто добавляя ключ к началу сообщения, поскольку она не подвержена атакам на расширение длины.

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

Криптографическая стойкость HMAC зависит от размера используемого секретного ключа и безопасности лежащей в основе хэш-функции. Доказано, что безопасность конструкции HMAC напрямую связана со свойствами безопасности используемой хэш-функции. Наиболее распространенная атака на HMAC — это перебор для раскрытия секретного ключа. HMAC значительно менее подвержен коллизиям, чем используемые в его основе алгоритмы хеширования. В частности, Михир Белларе доказал, что HMAC является псевдослучайной функцией (PRF) при единственном условии, что функция сжатия является PRF. Следовательно, HMAC MD5 не страдает от тех же недостатков, которые были обнаружены в MD5. RFC 2104 требует, чтобы "ключи длиной более B байт сначала хешировались с использованием H", что приводит к запутанной псевдоколлизии: если ключ длиннее размера хэш-блока (например, 64 байта для SHA-1), то HMAC(k, m) вычисляется как HMAC(H(k), m). Это свойство иногда рассматривается как потенциальная слабость HMAC в сценариях хеширования паролей: было продемонстрировано, что можно найти длинную ASCII-строку и случайное значение, хеш которых также будет ASCII-строкой, и оба значения будут давать одинаковый результат HMAC. В 2006 году Jongsung Kim, Alex Biryukov, Bart Preneel и Seokhie Hong показали, как отличить HMAC с усеченными версиями MD5 и SHA-1 или полными версиями HAVAL, MD4 и SHA-0 от случайной функции или HMAC с случайной функцией. Дифференциальные отличители позволяют злоумышленнику разработать атаку подделки на HMAC. Кроме того, дифференциальные и прямоугольные отличители могут привести к атакам по второму прообразу. HMAC с полной версией MD4 может быть подделан, используя эти знания. Эти атаки не противоречат доказательству безопасности HMAC, но дают представление о HMAC на основе существующих криптографических хэш-функций. В 2009 году Xiaoyun Wang и др. представили атаку различия на HMAC MD5 без использования связанных ключей. Она может отличить реализацию HMAC с MD5 от реализации со случайной функцией с 297 запросами с вероятностью 0,87. В 2011 году был опубликован информационный RFC 6151, в котором обобщены соображения безопасности в MD5 и HMAC MD5. Для HMAC MD5 RFC заключает, что, хотя безопасность самой хэш-функции MD5 серьезно скомпрометирована, известные в настоящее время "атаки на HMAC MD5 не указывают на практическую уязвимость при использовании в качестве кода аутентификации сообщений", но также добавляет, что "при разработке нового протокола набор шифров с HMAC MD5 не следует включать".

The cryptographic strength of the HMAC depends upon the size of the secret key that is used and the security of the underlying hash function used. It has been proven that the security of an HMAC construction is directly related to security properties of the hash function used. The most common attack against HMACs is brute force to uncover the secret key. HMACs are substantially less affected by collisions than their underlying hashing algorithms alone. In particular, Mihir Bellare proved that HMAC is a pseudo random function (PRF) under the sole assumption that the compression function is a PRF. Therefore, HMAC MD5 does not suffer from the same weaknesses that have been found in MD5. RFC 2104 requires that "keys longer than B bytes are first hashed using H" which leads to a confusing pseudo collision: if the key is longer than the hash block size (e. g. 64 bytes for SHA 1), then HMAC(k, m) is computed as HMAC(H(k), m). This property is sometimes raised as a possible weakness of HMAC in password hashing scenarios: it has been demonstrated that it's possible to find a long ASCII string and a random value whose hash will be also an ASCII string, and both values will produce the same HMAC output. In 2006, Jongsung Kim, Alex Biryukov, Bart Preneel, and Seokhie Hong showed how to distinguish HMAC with reduced versions of MD5 and SHA 1 or full versions of HAVAL, MD4, and SHA 0 from a random function or HMAC with a random function. Differential distinguishers allow an attacker to devise a forgery attack on HMAC. Furthermore, differential and rectangle distinguishers can lead to second preimage attacks. HMAC with the full version of MD4 can be forged with this knowledge. These attacks do not contradict the security proof of HMAC, but provide insight into HMAC based on existing cryptographic hash functions. In 2009, Xiaoyun Wang et al. presented a distinguishing attack on HMAC MD5 without using related keys. It can distinguish an instantiation of HMAC with MD5 from an instantiation with a random function with 297 queries with probability 0.87. In 2011 an informational RFC 6151 was published to summarize security considerations in MD5 and HMAC MD5. For HMAC MD5 the RFC summarizes that – although the security of the MD5 hash function itself is severely compromised – the currently known "attacks on HMAC MD5 do not seem to indicate a practical vulnerability when used as a message authentication code", but it also adds that "for a new protocol design, a ciphersuite with HMAC MD5 should not be included".