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

Sorry, but I just found out that many of my mails bounced because I was using 
my secondary email address =8-0

----------  Forwarded Message  ----------
Subject: Re: [HACKERS] CRC, hash & Co.
Date: Mon, 11 Dec 2000 07:13:31 +1100
From: Horst Herb <horst@hherb.com>
To: pgsql-hackers@postgresql.org


On Sunday 10 December 2000 17:35, you wrote:
> > 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.

It is not my definition, but the definition found in any technical / IT

dictionary I could grab. Examples:
> > 3.) There are many domains where you need to protect your 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.

In the medical domain, the "malicious attacker" is often the user himself.
For medico-legal reasons, we need a complete audit trail proofing that no
alterations have been made to medical records. For practical reasons, the
quickest means (AFAIK) to achieve this is digesting the digests of all entries
(or at least those of the change log) and store these externally on a trusted
authentication server. No matter how unlikely such a manipulation is; for a
court case you always need the state-of-the-art precautions.

> > 5.) As opposed to a previous posting (Bruce ?), MD5 has been shown to be
> > "crackable" (deliberate collision feasible with available 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.

You are partially right. It was only the compression function of MD5. But
that's enough.
"An iterated hash function is thus in this regard at most as strong as its
compression function" ( A.J.Menezes, P.C.van Oorschot, S.A.Vanstone "Handbook
of Applied Cryptography", CRC Press, 1999, link to online version:
http://www.cacr.math.uwaterloo.ca/hac/ ).
Read Cryptobytes Vol.2 No.2 Summer 1996; Hans Dobbertin: The status of MD5
after a recent attack
(ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto2n2.pdf).
and
RSA Data security recommended already 1996 that MD4 should no longer be used
and that MD5 "should not be used for future applications that require the
hash function to be collision resistant"
(ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf)
Even in S/MIME MD5 "is only provided for backwards compatibility" for that
very reason
(http://web.elastic.org/~fche/mirrors/www.jya.com/pgpfaq-ss.htm#SubMD5Broke)
and Bruce Schneier stated that he is "wary of MD5" ( B.Schneier, "Applied
Cryptography, Second Edition", Wiley, 1996 (cited at
http://web.elastic.org/~fche/mirrors/www.jya.com/pgpfaq-ss.htm, I am still
trying to find the original quote in the book))

For further reference I recommend the "Handbook of applied cryptography"
which surprisingly is available online (full text) at
http://www.cacr.math.uwaterloo.ca/hac/

Please remember that the whole reason for my reasoning is that we need a
run-time definable choice of CRCs/digests as no one single hash will suit all
needs.

Horst

-------------------------------------------------------