Subject: [Cfrg] HMAC-MD5

From: Russ Housley <[email-masked]>
Date: Tue, 28 Mar 2006 16:20:59 -0500

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?

Please provide advice on this matter in the next two weeks.  We have 
on working group that needs this advice very soon.

Russ

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: Tue, 28 Mar 2006 23:05:01 +0000 (UTC)

>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.

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Tue, 28 Mar 2006 18:11:21 -0500

> on working group that needs this advice very soon.
There are no risks from HMAC-MD5 from collision attacks.  Hash function
design has suddenly become a very hot topic, though.  Collision-
finding attacks on MD5 have gotten a lot faster, and people are
starting to look very hard at the basic design.  I personally will not
be surprised if a preimage attack is found in the next two or three
years, in which case all bets are off.  (I've made this statement
before; others have disagreed with me on the likelihood of collision
attacks.) I'd rather avoid HMAC-MD5, just as a matter of
future-proofing.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: Russ Housley <[email-masked]>
Date: Wed, 29 Mar 2006 09:14:55 -0500

>Let me ask a question.  Is there any reason to be restricted to HMAC?

This was the question that was raised.  The working group already has 
HMAC-MD5 in their draft specification.  The question was raised to 
determine if there is a compelling reason to change.

In the TLS 1.2 design, there is a discussion about supporting 
non-hash-based integrity mechanisms.  In the current design, they use 
a combination of MD5 and SHA-1 in a HMAC-like construction.

Russ

---

From: Ben Laurie <[email-masked]>
Date: Wed, 29 Mar 2006 15:26:37 +0100

> attacks.) I'd rather avoid HMAC-MD5, just as a matter of

Just an extra data point, I believe the latest s/w for collisions has it
down to just two seconds!

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 29 Mar 2006 08:18:54 -0800

>down to just two seconds!

Serious question: why is this a data point for the question about 
HMAC-MD5? What part of being able to make essentially as many 
collisions as you want as quickly as you want affects whether or not 
we should continue to use HMAC-MD5?

--Paul Hoffman, Director
--VPN Consortium

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 29 Mar 2006 11:43:21 -0500

> we should continue to use HMAC-MD5?

I interpreted as a sign of how much better the attacks are getting --
people are looking at hash functions, and they're making progess on
attacks.

To be sure, from what I've heard the current attack technology doesn't
lend itself towards preimage attacks.  But I'll quote David Wagner
(albeit to draw a different conclusion): we don't know as much about
hash functions as we'd like.

---

From: Daniel Brown <[email-masked]>
Date: Wed, 29 Mar 2006 11:48:34 -0500

My 2c.

Dan Brown
(905) 501-3857
http://www.certicom.com

Russ Housley <[email-masked]> wrote on 03/28/2006 04:20:59 PM:

> ... 
> HMAC-MD5.  Is it safe to keep using it? 

Maybe for now - but for how much longer?  Many uses may not need future 
resilience, so it may be safe for existing implementations to continue 
using it in these cases.  Some uses (perhaps as a PRF?), however, may need 
future resilience.

> Should we encourage people 
> to use HMAC-SHA1 or HMAC-SHA256 instead? 

Yes, especially for new implementations or specifications.  There are 
other choices too.  For symmetric-key authentication (MAC), consider NIST 
SP 800-38B CMAC, which uses a block cipher, and UMAC.  For key derivation, 
there's NIST SP 800-56A KDF.  For random number generation, Draft NIST SP 
800-90 offers several choices.

> Why?

The recent collision attacks on MD5 - which, by the way, are actually more 
than collision attacks, they apparently work for any known IV, and thereby 
can be extended to secret IV as mentioned in the 1996 HMAC paper and in 
Bellare's recent paper too - illustrate that MD5 has severely failed to 
meet one of its design goals.

Arguably, its other design goals, particularly preimage-resistance, may be 
unaffected by failure of collision-resistance.  Similarly, other 
properties of MD5 that have been assumed although not being original 
design goals, such as being a good PRF or having a keyed compression 
function that is a good MAC, may not be affected either.  Indeed, it is a 
quite reasonable argument that (weak) collision resistance was a much more 
difficult design goal to attain than the other properties, and therefore 
it is expected that a collision would be found much earlier than other 
attacks.

Personally, I don't understand the collision attacks in detail, which puts 
me in a position of being unable to assess whether the general principles 
used to find collision can be extended to find other kinds of attacks. 
It's difficult to persuade me, at least until I understand the details, 
that if a "differential" can be used to find a collision, that they cannot 
be used to weaken, say, the PRF-like properties.

To persuade a wide audience that MD5 is safe, the audience have to take 
its security on faith.  Taking security on faith (albeit mixed with other 
assurances) is common for cryptography users, but the difference here is 
that the collision-resistance on MD5, previously taken on faith, has been 
broken.  In the case of MD5, there will be the continual problem of some 
MD5 users suddenly realizing that MD5 has been "broken", and then having 
to learn the subtleties about how using MD5 is actually safe depending if 
used correctly.  Even if certain uses of MD5 are safe, just to avoid these 
perception problems, it may be better to use some good alternatives 
without a previous conviction.  Also, there's the risk that if users gets 
access to MD5, say as part of a source implementation of HMAC-MD5, that 
they might use it in a wrong way in part of some customer application, 
after relying some outdated references stating MD5 is collision-resistant.

More technically, the original 1996 proof of the security of HMAC (more 
precisely, of NMAC) as a MAC, was based on a weak collision resistance 
property of the hash, that has now been severely broken for MD5.  On the 
other hand, an informal remark in the 1996 paper can be interpreted in 
such a way that to modify the collision property in such a way that it is 
not broken by the recent spate of attacks on MD5, and that the original 
1996 proof with some very minor adjustments can be carried over.  In 
discussions with Canetti, I was convinced of this, but I still feel that 
it would be better to formalize these adjusted definitions and proofs for 
wider scrutiny.

The modified 1996 proof and new proof of Bellare are positive for HMAC, 
perhaps including HMAC-MD5.  Because they are relatively newer proofs, 
however, other alternatives that have similarly aged proofs ought to be 
given equal consideration.  The security proof of HMAC was one of the main 
selling points of HMAC, and it's fair to treat other security proofs 
equally.

A quite different line of argument is the adage "if it ain't broke, don't 
fix it".  As HMAC-MD5 has been widely deployed, and nobody has broken it, 
this may be a compelling argument to many.   The flip side of this is 
"wait till it breaks", however, which is like not performing regular 
maintenance on a vehicle, just to save a few bucks in the short term. When 
a part starts to look rusty, if it's not yet broken, it may be time 
replace it with a new shiny part.  Of course, it does depend on a cost to 
benefit comparison.  Certainly, if one has an opportunity to replace it, 
without too much expense, then do so.  If a standard is being revised, 
then deprecating or replacing all uses of MD5 ought to be seriously 
considered.

---

From: Ben Laurie <[email-masked]>
Date: Wed, 29 Mar 2006 17:54:42 +0100

> people are looking at hash functions, and they're making progess on

Exactly. That kind of performance allows for extensive searches which
_might_ ultimately allow brute force attacks on more complex constructs
such as HMAC.

Cheers,

Ben.

---

From: [email-masked]
Date: Wed, 29 Mar 2006 12:59:14 +1100

I thought that HMAC-MD5 was vulnerable if the key is known? That is,
the underlying function is still broken, so why risk it?

Key management is hardly easy, so there no reason to give it extra weight ?

-- Michael