[16082] in cryptography@c2.net mail archive
Re: ?splints for broken hash functions
daemon@ATHENA.MIT.EDU (John Denker)
Wed Sep 1 21:28:39 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 01 Sep 2004 21:24:34 -0400
From: John Denker <jsd@av8n.com>
To: David Wagner <daw-usenet@taverner.CS.Berkeley.EDU>
Cc: cryptography@metzdowd.com
In-Reply-To: <200409012019.i81KJ9k5024341@taverner.CS.Berkeley.EDU>
I wrote
>> the Bi are the input blocks:
>> (IV) -> B1 -> B2 -> B3 -> ... Bk -> H1
>> (IV) -> B2 -> B3 -> ... Bk -> B1 -> H2
>>then we combine H1 and H2 nonlinearly.
(Note that I have since proposed a couple of improvements,
but I don't think they are relevant to the present remarks.)
David Wagner wrote:
> This does not add any strength against Joux's attack. One can find
> collisions for this in 80*2^80 time with Joux's attack.
>
> First, generate 2^80 collisions for the top line. Find B1,B1* that
> produce a collision, i.e., C(IV,B1)=C(IV,B1*)=V2. Then, find B2,B2*
> that produce a collision, i.e., C(V2,B2)=C(V2,B2*)=V3. Continue to
> find B3,B3*, ..., Bk,Bk*. Note that we can combine this in any way
> we like (e.g., B1, B2*, B3*, B4, .., Bk) to get 2^80 different messages
> that all produce the same output in the top line (same H1).
OK so far. I think this assumes a sufficiently long input string,
but I'm willing to make that assumption.
> Next, look at the bottom line. For each of the 2^80 ways to combine
> the above blocks, compute what output you get in the bottom line.
OK so far.
> By the birthday paradox,
Whoa, lost me there.
I thought H1 was fixed, namely the ordinarly has of the original
message. Two questions:
1) If H1 is fixed, I don't understand how birthday arguments apply.
Why will trying the bottom line 2^80 times find me H@ equal to a
particular fixed H1? There are a whooooole lot more that 2^80
possibilities.
2) If H1 is not fixed, then this seems to be an unnecessarily
difficult way of saying that a 160-bit hash can be broken using
2^80 work. But we knew that already. We didn't need Joux or
anybody else to tell us that.
A proposal that uses 80*2^80 work is particularly confusing, if
H1 is not fixed.
> you will find some pair that produce a
> collision in the bottom line (same H2). But that pair also produces
> a collision in the top line (since all pairs collide in the top line),
> so you have a collision for the whole hash (same H1,H2).
Still lost, for the same reasons. Please explain. Also if possible
please address the improved version, with different IVs and long-range
permutation of a partial block.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
