[373] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Munro Saunders)
Mon Mar 17 22:56:19 1997
From: Munro Saunders <munro@ci.com.au>
To: stewarts@ix.netcom.com (Bill Stewart)
Date: Tue, 18 Mar 1997 11:10:09 +1100 (EST)
Cc: 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
(I'm not sending this to coderpunks because it is rather theorectical.
If the cross posting was annoying me, it may well be annoying other people.)
Bill Stewart suggests a way of extending a cryptographic hash
with a non-cryptographic hash (like a CRC) to gain extra security
with little extra processing cost. The initial scheme would not
work because CRCs are linear and other non-cryptographic hashs
will probably have similar problems.
However, I have found a simple modification which may not
suffer from this weakness - see below.
I imagine that Bill Stewart may have written:
>
> >> >> 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.
>
> 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 modification (where "," is concatenation):
Superhash(M) = ( CRC(M , SHA1(M)) , SHA1(M) )
(We only have to do one SHA1 and one CRC.)
In this approach the non-linearity of SHA1 makes the CRC
(seriously) non-linear wrt to M.
Can anyone, see anything wrong with this?
(Apart from the fact that SHA1 should be quite sufficient
for the next decade or so.)
So the (hypothetical) assumption is: SHA1 is not sufficient
by itself; our attacker can do 2^80 searches.
Our attacker can do birthday attacks on SHA1,
but they can not yet invert it.
(This is another assumption, 2^80 searches may lead
to insight into weakness in SHA1 sufficent to break it entirely.)
Also I assume the CRC is not bigger than SHA1 (160 bits).
So is the above scheme as secure as the sum of the hash lengths?
(I find this very frustrating. It seems like a good idea,
as far as ten minute old ideas go, but feel like I could
spend a decade on it and not prove anything either way.
So I throw it to the wolves :-)
--
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
