Re: Infecting the KaZaA network? (moving here thread from 'traq)

[nestler () speakeasy net]

John Hall wrote:
> It is quite possible given two plaintexts of sufficient size, to ensure
> that they both have the same MD5 checksum.

I think this is significantly harder than you are making
it out to be. MD5 is a cryptographic checksum designed specifically
to resist this kind of "collision".

MD5 is weaker than SHA-1, but it is not so weak that you can just
go around forging it at will.

It would take about 2^64 hashes of random inputs to find two
distinct inputs with the same MD5 (a collision).
This is due to the birthday paradox and the 128 bit output of MD5.
Note that if you want to collide with a specific MD5 value
(as you would need to do to mount the infection you are talking about),
this problem is much harder.

In that case, you end up having to do more like 2^127 hashes
of random inputs to find another input that hashes to the
same MD5 as a specific fixed input (the file your are spoofing).

Don't hold your breath waiting for 2^127 hashes to finish.

-Ivan