Re: [Cfrg] HMAC-MD5

[daw at cs.berkeley.edu (David Wagner)]

Russ Housley  wrote:
>At the SAAG session last week, Sam and I were asked about 
>HMAC-MD5.  Is it safe to keep using it?  Should we encourage people 
>to use HMAC-SHA1 or HMAC-SHA256 instead?  Why?

As far as I can tell, it seems to be safe to continue using HMAC-MD5.
Bellare has recently provided strong evidence that the known collision
attacks on MD5 do not endanger HMAC.
  http://eprint.iacr.org/2006/043

In particular, Bellare shows that, if (a) the MD5 compression function
is a PRF and (b) the MD5 compression function has some very simple
related-key properties, then (c) HMAC-MD5 should be secure.  Assumption
(a) seems pretty plausible, especially since Bellare's proof only requires
that (a.1) the MD5 compression function must be a PRF when the attacker
gets to specify just two chosen inputs, and (a.2) the MD5 compression
function must be a PRF when the attacker gets to see the output of it
on many random inputs.  Assumption (b) also seems pretty plausible.
Consequently, HMAC-MD5 doesn't seem to be at too much risk from the
current attacks, as far as I can tell.

If you asked me for my advice, I would say this.  For old designs, don't
bother to switch.  For new designs, if there are no other considerations,
my preference list would be AES-OMAC, HMAC-SHA1, then HMAC-MD5 (in order
of decreasing safety) -- but for most purposes, they are probably all
good enough and unlikely to be the weakest point in the system, and it's
probably not worth spending too much time agonizing over the choie.

Let me ask a question.  Is there any reason to be restricted to HMAC?
Can you use a block cipher based construction?  I am a big fan of NIST's
AES-OMAC construction.  AES-OMAC comes with a security proof, so it would
be a big surprise if AES-OMAC is broken (and it would probably mean that
there is something fundamentally wrong with AES).  All else being equal,
AES-OMAC would be my own top choice for a MAC.

But I know that's not quite what you were asking, so maybe there is some
reason why you want a hash-based MAC rather than a block cipher-based MAC.
If I were building a new design and had to choose between HMAC-MD5
and HMAC-SHA1, I would probably choose HMAC-SHA1, unless there is some
compelling reason not to, merely on grounds of being conservative and
since it doesn't cost.  (If a 160-bit MAC tag is longer than you want,
just truncate the output of HMAC-SHA1 to whatever length you prefer.)

The lesson I take away from the hash function attacks is that we don't
understand as much about hash functions as we thought we did, so it's very
hard to predict the future.  In comparison, our understanding of block
ciphers looks considerably more solid.  That's why I prefer OMAC to HMAC.

Still, if you want a hash-based MAC, the new attack methods been more
effective at MD5 than against SHA1, so if you told me that one of HMAC-MD5
or HMAC-SHA1 was going to fall and you asked me to bet which one would
fall first, I would guess (without any great conviction) that HMAC-SHA1
would be more likely to survive longer than HMAC-MD5.

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg