?splints for broken hash functions

[bear]

On Wed, 1 Sep 2004, David Wagner wrote:

>Hal Finney writes:
>>[John Denker proposes:] 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.
>
>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).
>
>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.
>By the birthday paradox, 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).

The birthday paradox does not apply in this case because H1 is fixed.
The above construction is in fact secure against the Joux attack as
stated.  2^80 work will find, on average, one collision.

				Bear

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com