[363] in cryptography@c2.net mail archive
Re: Q: security of 2-barreled hashing
daemon@ATHENA.MIT.EDU (Lawrence C. Stewart)
Mon Mar 17 12:11:27 1997
Date: Mon, 17 Mar 1997 11:59:39 -0500
To: hal@rain.org, "Lawrence C. Stewart" <stewart@openmarket.com>
From: "Lawrence C. Stewart" <stewart@openmarket.com>
Cc: Bill Stewart <stewarts@ix.netcom.com>, Munro Saunders <munro@ci.com.au>,
coderpunks@toad.com, cryptography@c2.net,
"Perry E. Metzger" <perry@piermont.com>
I was ambiguous, I think. Here's another try.
Suppose I have a message m and the matching valid signature H(M)
= (SHA(m), CRC(m)). The message is transmitted as (m,H(m)).
By virtue of cleverness, I have located a different message m' such
that SHA(m') = SHA(m), but alas, CRC(m)!= CRC(m').
I create a new hash, H(m') = (SHA(m), CRC(m')), and attach it to
my new message m', giving (m',H(m')) which is accepted by
the recipient.
This works because I can disassemble H(m) into its two parts,
use the SHA part and replace the CRC part. I can replace the CRC
part because it does not depend on anything I don't know.
I think the technical name for this is "splicing".
-Larry
At 08:51 AM 3/17/97 -0800, Hal wrote:
>Lawrence C. Stewart wrote:
>>
>> Bill Stewart (howdy, fellow Stewart!) suggests using
>>
>> H(m) = (SHA(m), CRC(m)) where "," is concatenation.
>>
>> with the objective that it would be very hard to find m' such
>> that H(m) = H(m'), since that would require SHA(m) = SHA(m') and
>> CRC(m) = CRC(m').
>
>The reason being either that you have a signature from someone else on
>H(m), and
>you want to make it appear to be on another message; or you are trying
>to find
>two messages m and m' where you can get someone else to sign H(m) and
>then exhibit
>their signature on H(m'). (Or perhaps you will sign H(m) and later
>claim that you
>meant to sign H(m').)
>
>> That is likely true, but it isn't the attack one cares about.
>> The problem with non-cryptographic hashes like CRC is that the
>> attacker can run the algorithm forwards, rather than attempting
>> inversion. Because the aggregate hash is (SHA(m), CRC(m)), the
>> attacker can create (SHA(m), CRC(m')) trivially, creating a
>> valid-appearing message.
>
>What do you mean by a valid-appearing message? Is CRC(m')=CRC(m) here?
>If not,
>existing signatures on H(m) won't apply to H(m').
>
>> The attacker cannot easily create SHA(m) for arbitrary messages,
>
>You mean, the attacker cannot easily create messages m' for which
>SHA(m') equals
>SHA(m)? It is trivial to create SHA(m) for arbitrary m, of course; just
>run the
>SHA algorithm.
>
>> so she
>> works hard to find an m' for which SHA(m) = SHA(m'), then the CRC
>> part of it is computed forwards as CRC(m').
>
>Again, is this CRC(m') supposed to match CRC(m)? If not, I don't see
>what you
>have gained. H(m) will not be the same as H(m').
>
>Could you clarify what attack you have in mind here?
>
>Hal
>
>
