[383] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Bill Stewart)
Wed Mar 19 10:03:16 1997
Date: Tue, 18 Mar 1997 07:53:53 -0800
To: Munro Saunders <munro@ci.com.au>
From: Bill Stewart <stewarts@ix.netcom.com>
Cc: cryptography@c2.net
In-Reply-To: <199703180010.LAA13700@mippet.ci.com.au>
At 11:10 AM 3/18/97 +1100, Munro Saunders wrote:
>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.
Dave Wagner pointed out the problem quite well on cypherpunks -
that CRC is linear, and has zeroes, so you can find strings D1..Dn
such that CRC(Dj)=0, and therefore CRC(M xor Dj) = CRC(M).
Since it's only xor, that doesn't give you arbitrarily large numbers
of strings with identical hashes to feed to SHA, but you can at least
get 2**n, where n is the number of independent zero solutions.
>However, I have found a simple modification which may not
>suffer from this weakness - see below.
...
>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.
Looks interesting, at least ....
# 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.)
