Re: rsync and md4

["David F. Ogren" <ogren@cris.com>]

-----BEGIN PGP SIGNED MESSAGE-----

> On Sat, 29 Jun 1996, Andrew Tridgell wrote:
> 
> > Now I'd like to calculate some probabilities of failure of the
> > algorithm. The fundamental thing I need to know to do the calculation
> > is the probability of a random piece of data of length n having the
> > same md4 checksum as another given piece of data of the same length.
> 
> MD4 is a hashing algorithm, but it can be used for checksuming.
> >
> > A first guess might be 2^-128 but I know that this sort of thing is
> > rarely that simple. Is md4 that good?
> 
> 2^-64.

Are you sure?  MD5 is a 128 bit hash, and the probability of collision with 
a specific random piece of data (of any length) should be 2^-128.  I could 
be wrong, but do you have any explanation of why you think the answer is 
2^-64.

<snip>

> > Why md4? I chose md4 because it seemed to be the fastest of the
> > reputedly strong, publicly available checksum algorithms. Suggestions
> > for alternative algorithms are welcome.

MD4 is the fastest hash I am aware of.  However, there has been some 
successful attacks against two rounds of MD4.  Although this is not to 
suggest that MD4 is insecure, MD5 almost as fast (~1.3 times slower) and 
more secure.
David F. Ogren                | 
ogren@concentric.net          | "A man without religion is like a fish
PGP Key ID: 0xC626E311        |  without a bicycle"
- ------------------------------|----------------------------------------
Don't know what PGP is?       | Need my public key?  It's available
Send a message to me with the | by server or by sending me a message
subject GETPGPINFO            | with the subject GETPGPKEY
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMdXI1fBB6nnGJuMRAQFghwP/W0ZzdAYcbsdsCcrA97cwfw4uwug8sJWd
bjWD4Z+ski7kE4HN7bj2dRLFGke6EQZ8DiebnLIRPqGCxeyxdzotqcrsdKrgp+eN
eMfjp0Y3wVwvrPn2kVI5M0iI9kpX8tvvLh7Kp3OBvHdsBTim4aPPuM8xR2SHLSgv
/SYnhEBeYLA=
=VPWe
-----END PGP SIGNATURE-----