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 hIV with initialisation vector IV. Then NMAC is defined as H(K,M)=hK2(hK1(M)0), 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)=hIV(K20||hIV(K10||M)0). 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 hIV 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:
- HMACBell the version defined by Bellare.
- HMACstd the version from the standard [RFC2104], where the key length is 128 or 160 bits.
- HMACNIST the NIST standardised version [pdf] where the key length is 80 bits.
The second result shown is that HMACNIST will not be secure in the multi-user setting. Assume we have 2a 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 280-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.
No comments:
Post a Comment