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 [EMAIL PROTECTED]
