HMAC

RFC 2104 HMAC: Keyed-Hashing for Message Authentication

HMAC Algorithm in Detail

In cryptography, a keyed-Hash Message Authentication Code, or HMAC, is a type of message authentication code (MAC) calculated using a specific algorithm involving a cryptographic hash function in combination with a secret key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message. Any iterative cryptographic hash function, such as MD5 or SHA-1, may be used in the calculation of an HMAC; the resulting MAC algorithm is termed HMAC-MD5 or HMAC-SHA-1 accordingly. The cryptographic strength of the HMAC depends upon the cryptographic strength of the underlying hash function, on the size and quality of the key and the size of the hash output length in bits.

An iterative hash function breaks up a message into blocks of a fixed size and iterates over them with a compression function. For example, MD5 and SHA-1 operate on 512-bit blocks. The size of the output of HMAC is the same as that of the underlying hash function (128 or 160 bits in the case of MD5 and SHA-1), although it can be truncated if desired. Truncating the hash image reduces the security of the MAC which is upper bound by the birthday attack.


where h is a cryptographic hash function, K is a secret key padded with extra zeros to the block size of the hash function, m is the message to be authenticated, ∥ denotes concatenation, ⊕ denotes exclusive or (XOR), and the outer padding opad = 0x5c5c5c...5c5c and inner padding ipad = 0x363636...3636 are two one-block–long hexadecimal constants.


The construction and analysis of HMACs was first published in 1996 by Mihir Bellare, Ran Canetti, and Hugo Krawczyk, who also wrote RFC 2104. FIPS PUB 198 generalizes and standardizes the use of HMACs. HMAC-SHA-1 and HMAC-MD5 are used within the IPsec and TLS protocols.


The following pseudocode demonstrates how HMAC may be implemented.

function hmac (key, message)
opad = [0x5c * blocksize] // Where blocksize is that of the underlying hash function
ipad = [0x36 * blocksize]

if (length(key) < blocksize) then
key = key || [0x00 * (blocksize - length(key))] // Pad the key if shorter than blocksize
end if

for i from 0 to length(key) - 1 step 1
ipad[i] = ipad[i] XOR key[i]
opad[i] = opad[i] XOR key[i]
end for

return hash(opad || hash(ipad || message)) // Where || is concatenation
end function

Birthday Attack

A birthday attack is a type of cryptographic attack, so named because it exploits the mathematics behind the birthday paradox. Given a function f, the goal of the attack is to find two inputs x₁,x₂ such that f(x₁) = f(x₂). Such a pair x₁,x₂ is called a collision. The method used to find a collision is to simply evaluate the function f for different input values that may be chosen randomly or pseudorandomly until the same result is found more than once. Because of the birthday paradox this method can be rather efficient. Specifically, if a function f(x) yields any of H different outputs with equal probability and H is sufficiently large, then we expect to obtain a pair of different arguments x₁ and x₂ with f(x₁) = f(x₂) after evaluating the function for about different arguments on average.

It is easy to see that if the outputs of the function are distributed unevenly, then a collision can be found even faster. The notion of 'balance' of a hash function quantifies the resistance of the function to birthday attacks and allows the vulnerability of popular hashes such as MD and SHA to be estimated.

Digital signatures can be susceptible to a birthday attack. A message m is typically signed by first computing f(m), where f is a cryptographic hash function, and then using some secret key to sign f(m). Suppose Alice wants to trick Bob into signing a fraudulent contract. Alice prepares a fair contract m and a fraudulent one m'. She then finds a number of positions where m can be changed without changing the meaning, such as inserting commas, empty lines, one versus two spaces after a sentence, replacing synonyms, etc. By combining these changes, she can create a huge number of variations on m which are all fair contracts. In a similar manner, she also creates a huge number of variations on the fraudulent contract m'. She then applies the hash function to all these variations until she finds a version of the fair contract and a version of the fraudulent contract which have the same hash value, f(m) = f(m'). She presents the fair version to Bob for signing. After Bob has signed, Alice takes the signature and attaches it to the fraudulent contract. This signature then "proves" that Bob signed the fraudulent contract. This differs slightly from the original birthday problem, as Alice gains nothing by finding two fair or two fraudulent contracts with the same hash. Alice's optimum strategy is to generate "pairs" of one fair and one fraudulent contract. Then Alice compares each freshly-generated pair to all other pairs; that is, she compares the new fair hash to all previous fraudulent hashes, and the new fraudulent contract to all previous fair hashes (but doesn't bother comparing fair hashes to fair or fraudulent to fraudulent). The birthday problem equations apply where "n" is the number of pairs. (The number of hashes Alice actually generates is 2n.)

To avoid this attack, the output length of the hash function used for a signature scheme can be chosen large enough so that the birthday attack becomes computationally infeasible, i.e. about twice as many bits as are needed to prevent an ordinary brute force attack.

Pollard's rho algorithm for logarithms is an example for an algorithm using a birthday attack for the computation of discrete logarithms.