More problems with hash functions

[Jerrold Leichter]

| > It strikes me that Joux's attack relies on *two* features of current
| > constructions:  The block-at-a-time structure, and the fact that the state
| > passed from block to block is the same size as the output state.  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.
|
| Here's how I understand what you are suggesting.  Presently the hash
| compression function takes two inputs: a state, and an input data block.
| For SHA-1 the state is 160 bits and the input data block is 512 bits.
| It outputs a state-size block of 160 bits, which gets fed into the
| next block:
|
| IV  --->  COMP   --->   COMP   --->   COMP   --->  Output
|            ^             ^             ^
|            |             |             |
|            |             |             |
|          Block 1       Block 2       Block 3
|
| I think you are proposing to increase the output of each block by 512
| bits in this case, so as to provide some data that can be xored into
| the input data block of the next stage, a la CBC:
|
| IV  --->  COMP   --->   COMP   --->   COMP   --->  Output
|            ^  \          ^  \          ^
|            |    \------> X    \------> X
|            |             |             |
|          Block 1       Block 2       Block 3
|
| By itself, adding an xor step doesn't do anything....
Not true.

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.

All I'm left with, unless there's some cleverer attack I'm missing, is:

	- Find M1 and M1' that collide;
	- Find M2 and M2' such that M1 XOR M2 collides with M1' XOR M2',
		on the common initial state.

Then for the cost of finding two block-level collisions, I have a collision
between two-block messages (M1|M2 and M1'|M2').  But why bother?  It's always
been sufficient to find a collision on the *last* block, with an arbitrary
initial state.  (It would be nice to eliminate *this* generic weakness, but
it's not clear you can and still have an on-line algorithm.)

							-- Jerry

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