# ?splints for broken hash functions

John Denker jsd at av8n.com
Wed Sep 1 21:24:34 EDT 2004

```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.

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