?splints for broken hash functions

[David Wagner]

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

>[...] how about this simpler construction?
>  (IV1) -> B1 -> B2 -> B3 -> ... Bk -> H1
>  (IV2) -> B1 -> B2 -> B3 -> ... Bk -> H2
>and again combine H1 and H2.

The same attack applies.  This construction is not secure against
Joux's attack, either.

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