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?
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.
-----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-----
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
participants (5)
-
Andrew Tridgell -
David F. Ogren -
Mark M. -
mpd＠netcom.com -
Perry E. Metzger