Re: [Cfrg] RE: Who needs collision-resistance, anyway?

Charanjit Jutla writes:
> In the TCR model, the adversary chooses M first, and then is given IV
> (or key) and so he again tries the magic differential to get M'
> and will succeed with prob epsilon. This ASSUMES that the magic
> differential works equally well on all IV, and there is good reason to
> believe this is indeed the case.
> 
> Hence the rejection of MD5*.

That assumption doesn't sound like a good one to me.

After reading the paper on cryptanalysis of MD5 by Wang and Yu, it does
not look to me like their attack works in this way.  I think they rely
crucially on knowledge of the IV.  In particular, they choose a magic
differential.  However, their differential has a very low probability,
and it only works if a whole bunch of conditions on the message bits are
satisfied.  Then they pick a message which satisfies these conditions.
Even this still has too low a probability, so they derive some ways to
start with such a message and modify it to bypass a round or two for free.
See their section on multi-message modifications.

To put it another way, their attack seems to succeed at breaking the
collision-resistance, but they don't claim that it breaks the second
preimage resistance of the hash function.  If there were a magic
differential that worked for all messages (and didn't require their
constraints and message modification techniques), then second preimage
resistance would be broken.  Second preimage resistance is indeed a
necessary condition for TCR security.

In previous work, Dobbertin has a successful second pre-image attack
on MD4.  This means that there is no hope for MD4 to be TCR-secure.
Reading the paper by Wang, Lai, Feng, Chen, and Yu on MD4, they say
that they applied their techniques to MD4, and got a different second
pre-image attack on MD4.  However, their attack only works for a 2^-122
fraction of messages M.  They report briefly in the conclusion that there
is an improvement due to Yu, Wang, et al which improves this to 2^-72,
and that for SHA-0, it is 2^-107.

I don't see any other discussion of the possibility of second pre-image
attacks on MD5 or SHA1 in their paper, and I don't see any discussion
of the TCR property.  Presumably this will require some analysis.

It could well turn out that their techniques generalize to also find
second pre-images and break the TCR property, but I don't think it follows
trivially from the existence of collisions.  Likewise, I don't think we
can reject SHA1* out of hand based merely on the existence of collisions
(even ones based on differential analysis).

http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf
http://www.infosec.sdu.edu.cn/paper/md4-ripemd-attck.pdf
http://www.infosec.sdu.edu.cn/people/wangxiaoyun.htm

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