More problems with hash functions

[Hal Finney]

Jerry Leichter writes:
> 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.

Okay, I misunderstood your earlier suggestion.  Sorry.  Rereading it:

> Suppose we
> did ciphertext chaining:  For block i, the input to the compression function
> is the compressed previous state and the xor of block i and block i-1.  Then
> I can no longer mix-and-match pairs of collisions to find new ones.

It sounds like you're saying that that the input to the second compression
function should be M1 XOR M2 instead of just M2.  Like this:

IV  --->  COMP   --->   COMP   --->   COMP   --->  Output
           ^             ^             ^
           |    /------> X    /------> X
           |  /          |  /          |
         Block 1       Block 2       Block 3

But this is easily compensated for: if you wanted the input to the
2nd compression stage to be M2, you'd just input M1 XOR M2 instead.
Then when this gets XOR'd with M1, M1 will will cancel out in the XOR
and you'll have a nice clean M2 going into COMP, just as you wanted.

So if you found a compression-function collision starting with IV on M1
and M1', and you found a collision starting with the common output of
that stage on M2 and M2', your four collisions would be:

M1 || (M1 xor M2)
M1 || (M1 xor M2')
M1' || (M1' xor M2)
M1' || (M1' xor M2')

In each case the actual input to the 2nd block compression function
(after xoring with the first block input) would be M2 or M2', as desired.

Hal Finney

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