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 [EMAIL PROTECTED]