A Message Authentication Code (MAC) is a function

*H*which when given a key

*K*and message

*M*outputs a tag

*t=H(K,M)*. This tag shall be sent along with the message and allows the recipient to verify that he receives the real message and that it has not been altered in any way. HMAC is the most widely used hash-based message authentication code (MAC) and was first proposed by Bellare, Canetti and Krawczyk (BCK) in 1996 [pdf]. In this paper they introduce the NMAC or Nested MAC construction.

Let

*f*be the compression function of the interated hash function

*h*with initialisation vector

_{IV}*IV*. Then NMAC is defined as

*H(K,M)=h*, where

_{K2}(h_{K1}(M)^{0})*K={K1,K2}*, each of

*c*bits. We assume that the size of

*M*is a multiple of the blocksize

*b*and we let the superscript

*0*denote padding with zeros to a multiple

*b*. Despite having no obvious security issues some engineers objected to this construction because (1) it needs two keys and (2) it requires that the IV changes. As a result of this HMAC was proposed where

*H(K,M)=h*. Here

_{IV}(K2^{0}||h_{IV}(K1^{0}||M)^{0})*K1*and

*K2*are simply obtained by XORing two fixed strings

*ipad*and

*opad*with the master key

*K*.

BCK give a proof for NMAC which can be extended to prove the security of HMAC. The proof demonstrates that NMAC is secure when (i) the compression function

*f*is a secure MAC and (ii) the hash function

*h*is (weakly) collision resistant. But in 2005 Wang et al. found collisions on both SHA-1 and MD5 [pdf] [pdf] which meant that the existing proof would not actually apply with hash functions used in practice. As a result the following year Bellare [pdf] presented a new proof for NMAC/HMAC which showed that if the compression function

_{IV}*f*is a PRF then NMAC is also a PRF.

Let us now describe the results presented by Koblitz and Menezes (KM). KM consider three different versions of HMAC:

- HMAC
^{Bell}the version defined by Bellare. - HMAC
^{std}the version from the standard [RFC2104], where the key length is 128 or 160 bits. - HMAC
^{NIST}the NIST standardised version [pdf] where the key length is 80 bits.

^{Bell}and HMAC

^{std}. Let

*f:{0,1}*x

^{c}*{0,1}*

^{b}*→*

*{0,1}*be a compression function which meets the conditions necessary for Bellare's proof to hold. We can now construct a new compression function

^{c}*f**which is the same as

*f*except when the last

*b-c*bits of the input agree with the last

*b-c*bits of the padding values

*opad*or

*ipad,*in which case it outputs

*0*. For HMAC

^{Bell}this will have no effect since the key is still masking the padding vector. In HMAC

^{std }since the key is only 128 or 160 bits it is padded with zeros before being XORed with

*opad*and

*ipad*. Therefore the final bits of

*K1*and

*K2*are the same as

*ipad*or

*opad*. The compression function will therefore output

*0*and the tag will now be independent of the keys.

The second result shown is that HMAC

^{NIST}will not be secure in the multi-user setting. Assume we have

*2*

*users. The adversary chooses a random message*

^{a}*M*and ask all users for a tag on this message. Next the adversary chooses random keys

*K*and computes

*H(K,M)*searching for a collision with one of the user's tags. Finally if the adversary finds a collision it is likely she has determined the key for that user (in some cases the collision may also be due to a small tag length). The expected number of keys the adversary must check before finding a collision is

*2*

*. Considering security in the multi-user setting is a practical aspect which needs to be further considered from a provable context since many proofs of security only apply in the single-user setting.*

^{80-a}The final sections of the paper present KM's concerns with Bellare's proof of security and their own new proof of security. Their main concern is related to the final "coin fixing" step in Bellare's proof, where he maximises the advantage of the adversary by hard-wiring two message

*M1**and

*M2**into its code. It is mathematically true to say that such a pair exists. The problem here is how this pair of messages can be found. KM's objection here arises because Bellare's proof is in the non-uniform model of complexity. In this model a proof can use an algorithm which exists mathematically but may not be easy to find. This has implications for our ability to provide concrete security results. Further discussion on the non-uniform model and its implications to provable security can found here by Koblitz and Menezes, and here by Bernstein and Lange.