[384] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Munro Saunders)
Wed Mar 19 10:10:36 1997
From: Munro Saunders <munro@ci.com.au>
To: daw@cs.berkeley.edu (David Wagner)
Date: Wed, 19 Mar 1997 17:35:18 +1100 (EST)
Cc: cryptography@c2.net, stewarts@ix.netcom.com (Bill Stewart),
kelsey@email.plnet.net (John Kelsey)
In-Reply-To: <5gn3jc$h5f@joseph.cs.berkeley.edu> from "David Wagner" at Mar 18, 97 02:05:32 pm
I imagine that David Wagner may have written:
> In article <199703180010.LAA13700@mippet.ci.com.au>,
> Munro Saunders <munro@ci.com.au> wrote:
> > My modification (where "," is concatenation):
> >
> > Superhash(M) = ( CRC(M , SHA1(M)) , SHA1(M) )
> >
> > Can anyone, see anything wrong with this?
>
> Yeah. This modification to Bill Stewart's proposal also falls to the
> same attacks on the original proposal that I posted.
> So your variant is no more secure than Bill Stewart's original proposal.
Its broken. Perhaps not for exactly the same reasons as Bill Stewart
gives, or maybe I just havn't understood him.
Here my collision attack:
1. Pick c, any possible output of the CRC.
2. Generate ~ 2^80 messages Mi which have c = CRC(Mi).
(Use the linear techniques described by Bill Stewart.)
(To be useful these messages will have to have some
other structure, see John Kelsey comments.)
3. Try SHA1(Mi) for each Mi.
(Use the cycling technique described by John Kelsey to save space.)
4. There will be (50%) two messages Mi, Mj with SHA1(Mi) = SHA1(Mj).
These two messages will collide in my Superhash:
a. CRC(Mi) = CRC(Mj)
b. SHA1(Mi) = SHA1(Mj)
c. CRC(Mi, SHA1(Mi)) = CRC(Mj, SHA1(Mj))
(this derives from linearity in CRCs)
d. Superhash(Mi) = Superhash(Mj)
If you replaced the CRC with some other non-cryptographic hash:
- in 2, there would probably be an equivalent method of
producing a large set of messages with the same hash;
- in c, many hashes, including cryptographic ones, have a
prefix property which allows you to derive the same thing.
(See John Kelsey's comments.)
So most obvious modifications will fail as well.
I looked briefly at making the combination of M and SHA1(M)
more complicated (than just concatenation).
Such approaches may frustrate obvious attacks,
probably leaving slightly less obvious ones.
--
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
