Re: When will md5crk complete?

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 05/25/04


Date: Tue, 25 May 2004 12:38:10 GMT

Simon Johnson wrote:
>>Hello,
>>
>>This is the scheme of "birthday attack"; this is not what JLC claims to
>>fight against: in his site the examples he gives are attacks against
>>existing certificates, and in that case birthday attack doesn't apply (it
>>is
>>not the same probability to find two documents having same hash than to
>>find
>>a certificate having *the* same hash as a given one).
>
>
> Unfortunately, I have to conceed that JLC's attack is of little consequence
> to breaking certificates.
> His core message is correct however: you shouldn't be using MD5.
>
> Once collisions are known to exist you're on tricky ground. There might be a
> trick that you can use
> against the SSL certificate if you have a hash function for which a fair
> number of known collisions. Athough, I think that's unlikely.

By this logic though you could argue the differential attacks on MD4 are
not "real". I mean [afaik] you can't produce arbitrary collisions with
MD4 [efficiently]. So let's all use MD4 it's much faster!

The point of md5crk is to show that *any* 128-bit hash is too small.
After random collisions can be efficiently produced the hash can't be
used to hash unstructured data. While I think JL [btw: call him Jean
Luc or JL but not JLC.] may have over-estimated the impact of this
program nobody else has shown collisions in MD5 and it will be certainly
interesting to see.

I mean Dobbertin got some press for showing *pseudo* collisions of MD5
so let's cut JL some slack here ;-)

That and I'm getting good rates on md5crk .... !!!

Tom