HMAC

Definition

This definition is taken from RFC 2104:

${\displaystyle \begin{array}{cc}\mathrm{HMAC}(K,m)& =\mathrm{H}((K^{\prime }\oplus opad)\parallel \mathrm{H}(\left(K^{\prime }\oplus ipad\right)\parallel m))\\ K^{\prime }& =\{\begin{array}{ll}\mathrm{H}\left(K\right)& \text{if}K\text{ is larger than block size}\\ K& \text{otherwise}\end{array}\end{array}}$

where

${\displaystyle \mathrm{H}}$ is a cryptographic hash function.

${\displaystyle m}$ is the message to be authenticated.

${\displaystyle K}$ is the secret key.

${\displaystyle K^{\prime }}$ is a block-sized key derived from the secret key, K; either by padding to the right with 0s up to the block size, or by hashing down to less than or equal to the block size first and then padding to the right with zeros.

${\displaystyle \parallel }$ denotes concatenation.

${\displaystyle \oplus }$ denotes bitwise exclusive or (XOR).

${\displaystyle opad}$ is the block-sized outer padding, consisting of repeated bytes valued 0x5c.

${\displaystyle ipad}$ is the block-sized inner padding, consisting of repeated bytes valued 0x36.

Implementation

The following pseudocode demonstrates how HMAC may be implemented. The block size is 512 bits (64 bytes) when using one of the following hash functions: SHA-1, MD5, RIPEMD-128.

<b id="mw0Q">function</b> hmac <b id="mw0g">is</b> <b id="mw0w">input:</b> key: Bytes <i id="mw1A">// Array of bytes</i> message: Bytes <i id="mw1Q">// Array of bytes to be hashed</i> hash: Function <i id="mw1g">// The hash function to use (e.g. SHA-1)</i> blockSize: Integer <i id="mw1w">// The block size of the hash function (e.g. 64 bytes for SHA-1)</i> <i id="mw2A">// Compute the block sized key</i> block_sized_key = computeBlockSizedKey(key, hash, blockSize) o_key_pad ← block_sized_key xor [0x5c blockSize] <i id="mw2Q">// Outer padded key</i> i_key_pad ← block_sized_key xor [0x36 blockSize] <i id="mw2g">// Inner padded key</i> <b id="mw2w">return</b> hash(o_key_pad ∥ hash(i_key_pad ∥ message))

<b id="mw3Q">function</b> computeBlockSizedKey <b id="mw3g">is</b> <b id="mw3w">input:</b> key: Bytes <i id="mw4A">// Array of bytes</i> hash: Function <i id="mw4Q">// The hash function to use (e.g. SHA-1)</i> blockSize: Integer <i id="mw4g">// The block size of the hash function (e.g. 64 bytes for SHA-1)</i> <i id="mw4w">// Keys longer than </i>blockSize<i id="mw5A"> are shortened by hashing them</i> <b id="mw5Q">if</b> (length(key) > blockSize) <b id="mw5g">then</b> key = hash(key) <i id="mw5w">// Keys shorter than </i>blockSize<i id="mw6A"> are padded to </i>blockSize<i id="mw6Q"> by padding with zeros on the right</i> <b id="mw6g">if</b> (length(key) < blockSize) <b id="mw6w">then</b> <b id="mw7A">return</b> Pad(key, blockSize) <i id="mw7Q">// Pad key with zeros to make it </i>blockSize<i id="mw7g"> bytes long</i> <b id="mw7w">return</b> key

Design principles

The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with MAC = H(key ∥ message). However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC ("length-extension attack"). The alternative, appending the key using MAC = H(message ∥ key), suffers from the problem that an attacker who can find a collision in the (unkeyed) hash function has a collision in the MAC (as two messages m1 and m2 yielding the same hash will provide the same start condition to the hash function before the appended key is hashed, hence the final hash will be the same). Using MAC = H(key ∥ message ∥ key) is better, but various security papers have suggested vulnerabilities with this approach, even when two different keys are used.

No known extension attacks have been found against the current HMAC specification which is defined as H(key ∥ H(key ∥ message)) because the outer application of the hash function masks the intermediate result of the internal hash. The values of ipad and opad are not critical to the security of the algorithm, but were defined in such a way to have a large Hamming distance from each other and so the inner and outer keys will have fewer bits in common. The security reduction of HMAC does require them to be different in at least one bit.

The Keccak hash function, that was selected by NIST as the SHA-3 competition winner, does not need this nested approach and can be used to generate a MAC by simply prepending the key to the message, as it is not susceptible to length-extension attacks.

Security

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 peculiar "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 2⁹⁷ 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".

In May 2011, RFC 6234 was published detailing the abstract theory and source code for SHA-based HMACs.

Examples

Here are some HMAC values, assuming 8-bit ASCII for the input and hexadecimal encoding for the output:

HMAC_MD5("key", "The quick brown fox jumps over the lazy dog") = 80070713463e7749b90c2dc24911e275 HMAC_SHA1("key", "The quick brown fox jumps over the lazy dog") = de7c9b85b8b78aa6bc8a7a36f70a90701c9db4d9 HMAC_SHA256("key", "The quick brown fox jumps over the lazy dog") = f7bc83f430538424b13298e6aa6fb143ef4d59a14946175997479dbc2d1a3cd8 HMAC_SHA512("key", "The quick brown fox jumps over the lazy dog") = b42af09057bac1e2d41708e48a902e09b5ff7f12ab428a4fe86653c73dd248fb82f948a549f7b791a5b41915ee4d1ec3935357e4e2317250d0372afa2ebeeb3a