[Cfrg] HMAC with MD5 and SHA-1

[Hugo Krawczyk <hugo at ee.technion.ac.il>]

I originally intended this message as a clarification to the
confusion expressed, or reflected, by many of the msgs to this list
regarding the applicability of the new collision-finding results to
HMAC with MD5 and SHA-1. I am not sure it will really help but I'll
send it anyway.  Try it at your own risk :)

In general MD5 and SHA-1 are used for MANY applications each with a
different set of assumptions on these functions. The main
application (in the sense that this is what these functions were
defined for initially) is for collision resistance. This poperty is
important for providing non-repudiation guarantees in the setting of
digital signatures, but is not essential for authentication-only uses
of signatures (such as in the signature mode of IKE). Yet, I
would say that as a general principle, any hash function that is
strongly suspected to be weak in regards to collision resistance
should be abandoned for all uses of signatures. The reason is that
it is not always easy to make a general determination as whether an
application assumes non-repudiation or not. In particular, I would
strongly discourage using these functions with digital certificates.

MD5 should have been in the above category of "must abandon" (for
signature applications!) for the past 10 years or so since
Hans Dobbertin showed that MD5 has very WEAK collision resistance
properties.  The latest results rather than shaking our confidence
on MD5, should serve to shake the 9-years old MD5's coffin (I know
many ignored its death, and in that sense this last nail may help...)

Now, all of this is irrelevant to the use of MD5 or SHA-1 in the
context of HMAC. The properties required from these functions in
the HMAC context are very different. In particular, known collisions
(for KNOWN IVs) in the underlying hash functions are IRRLEVANT to
the security of HMAC. In the case of HMAC-MD5, for example, there is
no known weakness in its use for HMAC even though, as said, the
function is dead as collision resistant for almost 10 years.
Moreover, the break of MD5 by Dobbertin in 1995 not only did not
break the use of HMAC with MD5 but actually contributed to the
adoption of HMAC as it served to highlight HMAC's careful design
that avoided any reliance on collision resistance with known IVs.

The only relevance of collisions in the case of HMAC is when such
collisions can be found even when the IV keeps
changing and is SECRET. None of the known results (old and new)
can find such collisions better than through exhaustive search.
And even if some shortcut is eventually found (say, one in which
finding a collision with a secret IV takes 2^50 trials for MD5
rather than 2^64), these attacks would probably still need such a
number (2^50) of applications of HMAC by the legal holder of the key
and under the same key on 2^50 different inputs!

Am I hinting that HMAC-MD5, for example, will never be broken?
Not at all.  The point is that the type of cryptanalysis required
against MD5 in the context of HMAC is very different than collision
resistance. This is true also in the other direction: it can
perfectly be the case that certain functions (say SHA-1) be broken
one day for use with HMAC but still be perfectly secure for
collision resistance. As an example, for applications that use HMAC
as a PRF, it would be enough to show that the 7th bit of SHA-1 when
computed with random IVs in some set of chosen inputs is
significantly biased from 1/2. (For uses as MAC a break is much harder.)

Bottom line: there is nothing today that calls into question the
uses of SHA-1 and MD5 with HMAC. I have always recommended using
SHA-1 as a more robust function in general and leaving MD5 only for
the cases that its relative speed (double that of SHA-1) is a REAL
issue.  As far as I've seen so far, this may be the case only when
HMAC is used (as originally intended) as a MAC function.  In this
case, applying HMAC to each piece of information that is transmitted
in a session presents a performance issue (however, even in this
case, if encryption is also performed on the data then the relative
speed advantage of MD5 vs SHA-1 is quite lost).  On the other hand,
when HMAC is used as a PRF (as in the case of TLS handshake and IKE
key derivation) then MD5's better performance is irrelevant.
Indeed, these protcols use a handful of calls to these functions per
connection establishment (a negligible amount of operations,
especially when PK operations are involved too).

[Another reason to be more conservative with the use of HMAC for PRF
is that these uses, for example for key derivation, usually require
security also after the use, as opposed to MAC functions whose
security is relevant only at the time of use.]

In other words, at this point there is no room for panic.
Of course, this is a good reminder for the shaky security of our
basic primitives and for the need to design protocols in an
algorithm-independent way. And is certainly a good time to take a
minute of silence for the long-dead collision resistance of MD5.
HMAC with SHA-1, and even  MD5, can be used with careful confidence
until the next cryptanalysis wave (some hope for an interesting
Crypto'2005 :)

Hugo



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