Hal Finney hal at
Tue Aug 17 02:04:10 EDT 2004

My guess is that HMAC is not vulnerable.  The basic structure of HMAC is

	Hash (key1 ||  Hash(key2 || Msg))

The attacker does not know the key(s) and is allowed to request MACs
on chosen messages; then he must produce a valid MAC on a new message.

The initial paper from Wang eg al announcing the results is unusual in
that it merely exhibits the collisions, while providing no information
whatsoever about how they were obtained.  They are simply presented as
a fait accompli, astonishing in their very existence.  It reminds me
of the story of how Cole demonstrated that the 67th Mersenne number was
nonprime, by silently walking to the backboard and patiently working out
the value of 2^67 - 1, and then the product of its two factors, by hand.

The nature of the exhibited hash collisions is that they are values which
differ in only a very few bits: 6 bits out of 1024 for the MD5 collisions;
4 bits out of 512 for the MD4.  Obviously it's not the case that for
most strings, you can toggle these 4 or 6 bits and produce a collision!
Instead, the authors must have some technique to create very special
strings which allow the changes made by these few bits to cancel each
other out.

If the attacker could find two messages such that there was an inner hash
collision, Hash(key2 || Msg1)  ==  Hash(key2 || Msg2), he could break
HMAC.  He'd get a MAC on Msg1 and then he could use that same MAC on Msg2.

But it seems impossible to find a collision like this without knowing
key2.  These hash functions are highly nonlinear and the choice of Msg1
and Msg2 would be completely dependent on key2.  Change 1 bit of key2
and half the bits of Msg1 and Msg2 would very probably have to change.

If the attacker knew key2, it sounds like the new attacks would likely
work to find an inner collision.  But without knowing that, there would
be no way to choose Msg1 and Msg2.

Given the special form of the colliding values, it appears that the
new technique does not solve hash inversion, or finding collisions
with arbitrary bit differentials.  The one possibility that I could
imagine for a threat to HMAC is their comment that the attack on MD4
(for which collisions were already known) is so easy that it can be done
by hand calculation.  Maybe that would suggest that given the proper
differentials, a non-negligible fraction of randomly chosen values would
collide.  Then conceivably you could get lucky and find a collision
without even knowing key2.  But that seems like a very remote possibility.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list