Re: rsync and md4

-----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-----

"David F. Ogren" writes:
> > 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.

Does the phrase "birthday attack" mean anything to you?

> > > 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.

I'm afraid you are totally wrong here. MD4 has been completely
broken. I wouldn't trust it for anything. In fact, MD5 is no longer
trustworthy, either -- it was broken recently. Stick to SHA.

Perry

Perry writes:

> I'm afraid you are totally wrong here. MD4 has been completely
> broken. I wouldn't trust it for anything. In fact, MD5 is no longer
> trustworthy, either -- it was broken recently. Stick to SHA.

Has MD5 been broken again?  Or are you referring to that little
collision problem which is unlikely to affect the security of the
typical real life application?

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

On Sun, 30 Jun 1996, Mike Duvos wrote:

> Has MD5 been broken again?  Or are you referring to that little
> collision problem which is unlikely to affect the security of the
> typical real life application?

The point isn't whether MD5 can be attacked in a "real life" application, but
that there is a flaw in MD5.  This means that it is weaker than an algorithm
like SHA that has no known cryptanalytical attacks against it.  Besides, a
hashing algorithm with a 128-bit output can be broken as easily as a 64-bit
encryption key.  MD5 shouldn't be used for that reason alone.

- -- Mark

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
markm@voicenet.com              | finger -l for PGP key 0xe3bf2169
http://www.voicenet.com/~markm/ | d61734f2800486ae6f79bfeb70f95348
"Freedom is the freedom to say that two plus two make four.  If that
is granted, all else follows."  --George Orwell, _1984_


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMdblK7Zc+sv5siulAQHlCgP7BHta126r27mc0Xw9UKy4wnXhzu3AbRBM
QauVyh5hHvWKMJ7tXZEyDOtzvGCL3KalHCcXE7cfnybhOS6D+w9K/ZTafY0ASwP+
q6VHT1F3r0b616hL0wfp165X/qTVYKb4urWRU0p+hv9mQ0ET0ZoYpHJz66+7YJ5o
AcobTzBNQyk=
=oyfI
-----END PGP SIGNATURE-----

Mike Duvos writes:
> Perry writes:
> 
> > I'm afraid you are totally wrong here. MD4 has been completely
> > broken. I wouldn't trust it for anything. In fact, MD5 is no longer
> > trustworthy, either -- it was broken recently. Stick to SHA.
> 
> Has MD5 been broken again?  Or are you referring to that little
> collision problem which is unlikely to affect the security of the
> typical real life application?

I'm not refering to the old pseudocollision problem in the compression
from over a year back. A couple of months ago a real break was made as
I recall. It wasn't perfect but it was enough.

> 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.

I thought md5 was slower than that, but I'm only going by my
(addmitedly poor) memory of some comments in the tripwire docs. I'll
give it a go sometime.

One annoying think about the md4 implementation that I have is that on
little endian machines it byte reverses the words in the buffer its
hashing so I need to make a copy of the buffer each time. Is there a
version of md4 that doesn't do this?

Cheers, Andrew