More problems with hash functions

[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 at metzdowd.com