[360] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Munro Saunders)
Sun Mar 16 22:00:15 1997
From: Munro Saunders <munro@ci.com.au>
To: stewarts@ix.netcom.com (Bill Stewart)
Date: Mon, 17 Mar 1997 13:53:31 +1100 (EST)
Cc: coderpunks@toad.com, cryptography@c2.net
In-Reply-To: <3.0.1.32.19970316175537.0062fbe8@popd.ix.netcom.com> from "Bill Stewart" at Mar 16, 97 05:55:37 pm
Bill Stewart quotes the following text and gives the impression he beleives
it was written by me. It was it fact written by pbarreto@uninet.com.br
(Paulo Barreto). I may have contributed to this error.
> >> >> It is well known that a 160-bit hashing function like SHA1 is
> >> >> susceptible to a birthday attack of O(2^80) complexity.
> >> >> A question arises as to whether there is a possibility to cure
> >> >> this by running a 2-barreled version of SHA1 which has 2 SHA1
> >> >> contexts, one of which is (say) fed an extra constant byte
> >> >> after initialization.
I imagine that Bill Stewart may have written:
> 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.)
--
Munro Saunders Have 945764537344972374 nice days. P.O. Box 192,
munro@ci.com.au I am not an official spokesperson ERSKINEVILLE 2043
+61 2 9564 6368 for Elvis, IBM, M$ or Corinthian. AUSTRALIA
