From: "Perry E. Metzger" <perry@piermont.com>
Date: Mon, 1 Jul 1996 15:47:22 +0800
To: "David F. Ogren" <ogren@cris.com>
Subject: Re: rsync and md4
In-Reply-To: <199606300025.UAA04020@darius.cris.com>
Message-ID: <199606301747.NAA18634@jekyll.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



"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