[16064] in cryptography@c2.net mail archive
More problems with hash functions
daemon@ATHENA.MIT.EDU (David Wagner)
Wed Sep 1 08:53:09 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: Tue, 31 Aug 2004 21:10:32 -0700 (PDT)
Reply-To: daw-usenet@taverner.CS.Berkeley.EDU (David Wagner)
Jerrold Leichter wrote:
>Joux's attack says: Find single block messages M1 and M1' that collide on
>the "blank initial state". Now find messages M2 amd M2' that collide with
>the (common) final state from M1 and M1'. Then you hav four 2-block
>collisions for the cost of two: M1|M2, M1'|M2, and so on.
>
>But even a simple XOR breaks this. M1 and M1' have the same hash H, but the
>state being passed is now very different: <H,M1> in one case, <H,M1'> in the
>other. So M1|M2 and M1'|M2 are completely different: Both started the second
>step with the compression function in state H, but the first compressed
>M1 XOR M2, and the second M1' XOR M2.
Doesn't work, alas. A trivial adjustment to Joux's attack also defeats
your proposal.
Suppose M1 and M1' collide on the "blank initial state". Let M2 be
arbitrary. Then M1|M2 and M1'|M2 collide, and the final state after
processing them is <H,M2> in both cases. Now find messages M3 and
M3' that collide if processed starting from the common state <H,M2>.
Then you have four 3-block collisions for the cost of two: M1|M2|M3,
M1'|M2|M3, etc.
With this small tweak, Joux's attack will go through. So, your scheme
offers little or no additional resistance to Joux's attack.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
