Re: CRC, hash & Co. - Mailing list pgsql-hackers

On Sat, Dec 09, 2000 at 01:58:29PM +1100, Horst Herb wrote:
> There have been some misconceptions in previous mails.
>
> 1.) A CRC is _not_ stronger than a hash. CRC is a subset of the hash domain,
> defined as "a fast error-check hash based on mod 2 polynomial operations"
> which has typically no crypto strength (and does not need it either for most
> purposes).

Not true, unless your definition of strength is different than mine.
The point under question is if different data can produce the same hash
as correct data.  A CRC will always be different if the difference is a
burst error of N-1 bits or less (N being the size of the CRC), and has a
2^N chance of being different for all other errors.  Cryptographic
hashes can only claim the 2^N factor, with no guarantees.

> 2.) Theoretically, an optimal MD5 implementation can't be faster than an
> optimal CRC-32 implementation. Check it yourself: download openssl
> (www.openssl.org) or Peter Gutmans cryptlib where all sorts of hashes and
> CRC-32 are implemented in a very reasonable way. Write a tiny routine
> generating random strings, popping them through the hash function. You will
> see, CRC-32 is typically several times faster.

You check it yourself.  I'll send you a copy of my benchmarking code
under seperate cover.  All the core hashes except for CRC were taken
from openssl.  As per my last message, CRC on Celeron/P2/P3 sucks, and
in the worst case would only be 1.5 times faster than MD5.  MD4 would be
near par with CRC.

> 3.) There are many domains where you need to protect yout database not only
> against random accidental glitches, but also against malicious attacks. In
> these cases, CRC-32 (and other CRCs without any cryptographic strength) are
> no help.

If you have malicious attackers who can deliberately modify live data in
a database, you have problems beyond what any kind of hash can protect
against.

> 4.) Without CRC/hash facility, we will have no means of checking our data
> integrity at all. At least in my domain (medical) most developers are
> craving for database backends where we don't have to re-implement the
> integrity checking stuff again and again. If postgres could provide this, it
> would be a strong argument in favour of postgres.

I agree that it would be useful to CRC data blocks to protect against
bad data errors.  If you're data is really that sensitive, though, you
may be looking for ECC, not CRC or hash facilities.

> 5.) As opposed to a previous posting (Bruce ?), MD5 has been shown to be
> "crackable" (deliberate collison feasible withavailable technology)

No, it hasn't, unless you can provide us a reference to a paper showing
that.  I've seen references that there are internal collisions in the
MD5 reduction function, but still no way to produce collisions on the
final digest.
--
Bruce Guenter <bruceg@em.ca>                       http://em.ca/~bruceg/