[16080] in cryptography@c2.net mail archive
?splints for broken hash functions
daemon@ATHENA.MIT.EDU (David Wagner)
Wed Sep 1 17:49:32 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: David Wagner <daw@cs.berkeley.edu>
To: cryptography@metzdowd.com
Date: Wed, 1 Sep 2004 13:19:09 -0700 (PDT)
Reply-To: daw-usenet@taverner.CS.Berkeley.EDU (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@metzdowd.com
