My 2c.

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

Russ Housley <housley@vigilsec.com> 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.

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

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