More problems with hash functions

[Hal Finney]

Jerry Leichter writes:
> 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.  The attacker would
still have full control of the output of the xor, since he has full
control of one of its two inputs.  So I think it is more appropriate to
merely think of the compression function block as taking a wider state
input from the previous stage, and not specify how the input data block
is mixed with the previous state.

This might lead to a construction in which the state passed from block
to block is, say, 512 bits, rather than 160.  The compression function
still takes two inputs, the state and the input block, and now produces
a 512 bit output.

IV  ===>  COMP   ===>   COMP   ===>   COMP   --->  Output
           ^             ^             ^
           |             |             |
           |             |             |
         Block 1       Block 2       Block 3

(Here, the ==> are meant to depict wide paths.)

For the final output of the hash, we would presumably "derate" the
output of the last stage down to 160 bits and not claim the full 512
bits of security.  If we didn't do this step, then the construction is
precisely SHA-512 and Joux's attack still applies.

This approach does appear to defeat the Joux attack.  Finding a collision
in a sub-block which takes a 512 bit input to a 512 bit output will take
2^256 work rather than the 2^80 in the SHA-1 compression function.
So you will never find a multicollision in less work than this.  And the
most strength SHA-1 can provide against anything is 2^160 since that
it what it takes to invert it.  Since 2^256 is greater than 2^160,
the construction is strong against this attack.

We can also see from this analysis that making the paths 512 bits wide is
overkill; they only need to be twice the claimed hash strength, or 320
bits wide in this case.  Or in other words, if we took SHA-512 and only
claimed it to have 256 bits of strength, it would avoid the Joux attack.

However, the problem with this construction is that the inner blocks
now genuinely need to have 512 bits of strength, and that may not be
that easy to provide.  SHA-512's compression function does claim to have
that amount of collision resistance, but it is difficult to analyze such
strong claims, and adding this much strength may make for a slow hash.

Plus, given that we have managed to create a block with 512 bits of
security, it seems a shame to throw away half of the strength to produce
an output that avoids the Joux attack.  I think cryptographers will look
harder to try to find a way of combining sub-blocks which will retain the
strength of the individual pieces rather than throwing half of it away.

Hal Finney

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