From: "David F. Ogren" <ogren@cris.com>
Date: Mon, 1 Jul 1996 17:05:33 +0800
To: cypherpunks@toad.com
Subject: Re: rsync and md4
Message-ID: <199607010408.AAA21171@darius.cris.com>
MIME-Version: 1.0
Content-Type: text/plain


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