On Tue, 27 Nov 2001, Dave Huang wrote:
> How can it be theoretical? There are 2^128 possible 16-byte checksums,
> and 2^8192 possible 1Kbyte files (for example). There _have_ to be
> collisions. Now, with MD4, I can't give you an example of two files that
> have the same hash, without checking via brute force, but the
> possibility of a collision is there.

Actually, I guess MD4 has been broken after all (I don't keep up with
the crypto stuff :) http://www.rsa.com/rsalabs/faq/3-6-6.html says:

     Dobbertin [Dob95] has shown how collisions for the full
     version of MD4 can be found in under a minute on a typical PC.
     In recent work, Dobbertin (Fast Software Encryption, 1998) has
     shown that a reduced version of MD4 in which the third round
     of the compression function is not executed but everything
     else remains the same, is not one-way. Clearly, MD4 should now
     be considered broken.

     [Dob95]
     H. Dobbertin, Alf Swindles Ann, CryptoBytes (3) 1 (Autumn 1995).

So not only is it not theoretical, it doesn't take long to do. MD5 seems
to be okay for now :)