Re: [Cfrg] Re: [saag] Bad day at the hash function factory

[Mihir Bellare <mihir at cs.ucsd.edu>]

> I believe that the proof that HMAC is secure requires a collision resistant
> hash function.

That's not true. It requires that the hash function have a weaker property
(called weak collision resistance in our Crypto 96 paper that provides the
security proof), namely that it be hard to find collisions under a hidden key,
given oracle access to the keyed hash function. (This is the security condition
for the inner application of the two in HMAC). You can think of this as finding
collisions for a hidden initial state. In general an attack finding collisions
(in the normal sense, for a known initial state) need not be able to find
collisions for a hidden initial state. This has to be looked into separately.

Dobbertin's attacks did not lift to hidden state. The new attacks do work with
any known initial state, but what one can do for hidden initial state has not
been looked at carefully yet.

At Crypto 04 I asked Antoine Joux, who found the attacks on SHA-0, whether they
lifted to hidden state and result in an attack on HMAC-SHA-0. He thought there
may be a possibility that he could produce two messages that with probability
around 2^{-60} collided under a random initial state, resulting in a 2^{60}
time attack on HMAC-SHA-0, improving the naive birthday 2^{80} time one.
However, he warned this was a very rough guess that he could not confirm, and
he would look into it further. (And I would wait for confirmation from him
before assuming there is even such an attack.) Similarly, one would have to
look into the attacks on MD5 to see what can be done for hidden initial state.

But note all this is for HMAC-SHA-0, which one in any case should not be
using. There is nothing known against (SHA-1 or) HMAC-SHA-1.

Also, Joux believes that NIST announced SHA-1 because the NSA must have,
already in 1995, discovered the attacks on SHA-0 that emerged in the public
community only know. If so, there is some reason to think that SHA-1 has built
in defenses to these attacks, and might retain its strength. 

-Mihir





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