[362] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Lawrence C. Stewart)
Mon Mar 17 10:13:16 1997
Date: Mon, 17 Mar 1997 10:07:26 -0500
To: Bill Stewart <stewarts@ix.netcom.com>, Munro Saunders <munro@ci.com.au>
From: "Lawrence C. Stewart" <stewart@openmarket.com>
Cc: coderpunks@toad.com, cryptography@c2.net,
"Perry E. Metzger" <perry@piermont.com>, stewart@openmarket.com
Bill Stewart (howdy, fellow Stewart!) suggests using
H(m) = (SHA(m), CRC(m)) where "," is concatenation.
with the objective that it would be very hard to find m' such
that H(m) = H(m'), since that would require SHA(m) = SHA(m') and
CRC(m) = CRC(m').
That is likely true, but it isn't the attack one cares about.
The problem with non-cryptographic hashes like CRC is that the
attacker can run the algorithm forwards, rather than attempting
inversion. Because the aggregate hash is (SHA(m), CRC(m)), the
attacker can create (SHA(m), CRC(m')) trivially, creating a
valid-appearing message.
The attacker cannot easily create SHA(m) for arbitrary messages, so she
works hard to find an m' for which SHA(m) = SHA(m'), then the CRC
part of it is computed forwards as CRC(m').
-Larry
At 10:15 PM 3/16/97 -0800, Bill Stewart wrote:
>Munro and Perry have questioned my opinion here, but I think I can
>explain that it's relatively correct. Your objective is to find a
>hash function H(M) such that it's difficult to find either
>[Inversion:] m such that h = H(m) for a specific h, or
>[Birthday:] m1 and m2 such H(m1) = H(m2).
>
>Let H(M) = (H1(M) , H2(M)) where H1 is SHA1 and H2 is a CRC128.
>Thus H(m1) = H(m2) <=> H1(m1)=H1(m2) AND H2(m1)=H2(m2).
>Finding a local inverse to SHA1 is presumed hard, and
>finding a birthday attack on SHA1 is presumed to require ~2**80 tries.
>Can you find a mechanism for generating arbitrarily large sets of
>inputs for which CRC128(M) = CRC128(m0), with minimal effort ?
>If so, I guess I'm wrong ... it's happened before:-)
>So maybe you do need a real hash.
>
>>> Rather than a slow extra hash such as SHA1, you can probably do
>>> about as well by using a fast non-cryptographically-strong hash
>>> such as a CRC as the extra hash. The SHA1 gives you protection
>>> against inversion (perhaps reinforced some by the CRC), and the
>>> CRC gives you 64 or 128 extra bits to protect against birthday attacks.
>>
>>My initial impression is that non cryptographic techniques won't help.
>>There are quite fast techniques for finding a local inverse to a CRC.
>>So it adds only a small constant factor to the preparation of the attackers
>>trial messages, most work remains in matching the cryptographic
>>part of the hash. (I'll leave the details to others.)
>
>
># Thanks; Bill
># Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
># You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp
># (If this is a mailing list, please Cc: me on replies. Thanks.)
>
>
>
