Re: CRC was: Re: beta testing version

Bruce Guenter <bruceg(at)em(dot)ca> writes:
> MD5 is a cryptographic hash, which means (AFAIK) that ideally it is
> impossible to produce a collision using any other method than brute
> force attempts.

True but irrelevant. What we need to worry about is the probability
that a random error will be detected, not the computational effort that
a malicious attacker would need in order to insert an undetectable
error.

MD5 is designed for a purpose that really doesn't have much to do with
error detection, when you think about it. It says "you will have a hard
time computing a different string that produces the same hash as some
prespecified string". This is not the same as promising
better-than-random odds against a damaged copy of some string having the
same hash as the original. CRC, on the other hand, is specifically
designed for error detection, and for localized errors (such as a
corrupted byte or two) it does a provably better-than-random job.
For nonlocalized errors you don't get a guarantee, but you do get
same-as-random odds of detection (ie, 1 in 2^N for an N-bit CRC).
I really doubt that MD5 can beat a CRC with the same number of output
bits for the purpose of error detection; given the lack of guarantee
about short burst errors, I doubt it's even as good. (Wild-pointer
stomps on disk buffers are an example of the sort of thing that may
look like a burst error.)

Now, if you are worried about crypto-capable gremlins living in your
file system, maybe what you want is MD5. But I'm inclined to think that
CRC is more appropriate for the job at hand.

regards, tom lane