Study Group: Another Look at HMAC

Today's study group was given by Joop and Enrique on Koblitz and Menezes's paper "Another Look at HMAC" [pdf].  This was also part of the invited talk given by Menezes at Eurocrypt this year [video].  Like several of the papers in the "Another look" series this paper has provoked much debate in the crypto community.  Here we will give an overview of the paper.

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_IV with initialisation vector IV. Then NMAC is defined as H(K,M)=h_K2(h_K1(M)⁰), where 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_IV(K2⁰||h_IV(K1⁰||M)⁰). Here 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_IV 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 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: 

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

KM's first result is to show a seperation between HMAC^Bell and HMAC^std.  Let f:{0,1}^cx{0,1}^b→{0,1}^c be a compression function which meets the conditions necessary for Bellare's proof to hold.  We can now construct a new compression function 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^a users.  The adversary chooses a random message 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^80-a.  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.

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.