[361] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Bill Stewart)
Mon Mar 17 09:50:53 1997
Date: Sun, 16 Mar 1997 22:15:01 -0800
To: Munro Saunders <munro@ci.com.au>
From: Bill Stewart <stewarts@ix.netcom.com>
Cc: coderpunks@toad.com, cryptography@c2.net,
"Perry E. Metzger" <perry@piermont.com>
In-Reply-To: <199703170253.NAA26509@mippet.ci.com.au>
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.)
