Re: rsync and md4

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

Subject: Re: rsync and md4
To: perry@piermont.com, ogren@cris.com
Cc: markm@voicenet.com, Andrew.Tridgell@anu.edu.au, cypherpunks@toad.com

> 
> "David F. Ogren" writes:

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

But this isn't a birthday attack. Its a comparison between one specific 
file and one randomly chosen one.

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

Unless you are aware of some attack that I'm not, this is the most current 
information on MD4 and MD5:

MD4 has had successful attacks on limited rounds.  It has _not_ been 
completely cracked.

MD5 has not been broken.  A weakness has been shown, but collisions still 
cannot be developed.  So checksums should still be secure.  Additionally, 
in this case we are more concerned with the chance of random collisions 
than intentional collisions.

In fact, I was probably wrong to suggest MD5.  It _is_ more secure, but 
speed is his first priority, not security.  SHA1 is a good hash algorithm 
as far as security goes (I've used it myself), but it's over three times 
slower than MD4.


- --
David F. Ogren                | 
ogren@concentric.net          | "A man without religion is like a fish
PGP Key ID: 0x6458EB29        |  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
- --
David F. Ogren                | 
ogren@concentric.net          | "A man without religion is like a fish
PGP Key ID: 0x6458EB29        |  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

iQEVAwUBMddOi+SLhCBkWOspAQHLTgf7BsDpCO2nhxsHYOunVv8abXWgITexhM/Z
vmYWaz2Lgu3tBYZHXIG7B2ijTikZ7u8RgMGd9esipjFxOks1bHRQwYbVbWeDUDb3
O0c5TmPPmZt/7PscUEw1D3hhtj8HeGmn9pfu0y/I54OnMIJzbvNMICpMtLLDXJCu
PhpUoAfamyRdWl9OYAvZ3LBMLBdGagzCh/jPxCQ9gEBq0aYMkxF1/qlfIMdmegow
H/uL+TRgN5roTIKDZPGPZWYbdLbf0NT00avPz5qKaA5BkOpxYgeRKtoBHdYC5krH
O2NZGZqb5LRKgxW9+IvCWoUoJQTB6IXP+YDU7p4pbn/Y/QORSHzqGA==
=WA0Y
-----END PGP SIGNATURE-----

"David F. Ogren" 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.
> > 
> 
> Unless you are aware of some attack that I'm not, this is the most current 
> information on MD4 and MD5:
> 
> MD4 has had successful attacks on limited rounds.  It has _not_ been 
> completely cracked.

Could you please quit spewing inaccurate information?

Dobbertin completely cracked MD4 already, and found MD5 collisions in
a document circulated on May 2nd that mean it isn't far behind.

The comments you are making are dangerous because they encourage
people who don't know better to think that hashes which are known
unsafe are safe. Please quit posting until you start monitoring the
field enough to have accurate sources of information.

[...]
Forward from sci.crypt on 11 Jun 1996 14:22:03 GMT
  <dobbertin@skom.rhein.de> wrote (Re: "MD5 discussion"):

>In view of the continuing discussion about MD5, I want to make a few
>comments, which hopefully can help to avoid some misunderstandings
>and misinterpretations:

>1. In February 1996 my paper "Cryptanalysis of MD4" appeared (Fast
>Software Encryption, Cambridge Proceedings, Lecture Notes in Computer
>Sciences, vol. 1039, Springer-Verlag, 1996, pp. 71-82). In this
>paper, as an example two versions of a contract are given with the
>same MD4 hash value. Alf sells his house to Ann, in the first version
>the price is $176,495 and in the second it is $276,495. The contracts
>have been prepared by Alf. Now if Ann signs the first version with
>$176,495 then Alf can altered to price to $276.495 ...  In principle
>this risk occurs, if you use a hash function for which (senseful)
>collisions can be found, whenever you allow another person to have
>influence on the contents of a document you are signing.
[...]