Re: CRC

On Fri, Dec 08, 2000 at 12:19:39PM -0600, Bruce Guenter wrote:
> On Thu, Dec 07, 2000 at 04:01:23PM -0800, Nathan Myers wrote:
> > 1. Computing a CRC-64 takes only about twice as long as a CRC-32, for
> > 2^32 times the confidence. That's pretty cheap confidence.
>
> Incidentally, I benchmarked the previously mentioned 64-bit fingerprint,
> the standard 32-bit CRC, MD5 and SHA, and the fastest algorithm on my
> Celeron and on a PIII was MD5. The 64-bit fingerprint was only a hair
> slower, the CRC was (quite surprisingly) about 40% slower, and the
> implementation of SHA that I had available was a real dog. Taking an
> arbitrary 32 bits of a MD5 would likely be less collision prone than
> using a 32-bit CRC, and it appears faster as well.

This is very interesting. MD4 is faster than MD5. (MD5, described as
"MD4 with suspenders on", does some extra stuff to protect against more-
obscure attacks, of no interest to us.) Which 64-bit CRC code did you
use, Mark Mitchell's? Are you really saying MD5 was faster than CRC-32?

I don't know of any reason to think that 32 bits of an MD5 would be
better distributed than a CRC-32, or that having computed the 64 bits
there would be any point in throwing away half.

Current evidence suggests that MD4 would be a good choice for a hash
algorithm.

Nathan Myers
ncm(at)zembu(dot)com