?splints for broken hash functions

[John Denker]

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 at metzdowd.com