More problems with hash functions

[bear]

On Wed, 25 Aug 2004, Hal Finney wrote:

>Dan Carosone writes:
>> My immediate (and not yet further considered) reaction to the
>> description of Joux' method was that it might be defeated by something
>> as simple as adding a block counter to the input each time.
>
>Right after the talk, Scott Fluhrer (I think it was) spoke up with
>several quick ideas for avoiding the attacks, some along these lines,
>some involving overlapping blocks, and so on.  There was some rapid
>back-and-forth between him and Joux which I could not follow, Joux
>saying that these things could be dealt with, and Fluhrer finally seemed
>to agree.  Nobody I spoke with afterwards had a simple fix.

It seems like, for every "obvious" thing you can do to get around
it, it can be rearranged and applied in a different way.  And the
less obvious things, which actually do work, are all CPU-expensive.

One interesting idea which I came up with and haven't seen a way
past yet is to XOR each block with a value computed from its
sequence number, then compute the hash function on the blocks in
a nonsequential order based on the plaintext of the blocks.

In concrete terms, you have a message of n blocks, p1 through pn.
you xor each block with a value computed by a nonlinear function
from its sequence number to get q1 through qn.  Now rearrange
q1 through qn by imposing a total ordering on p1 through pn: for
example if p4 sorted before p7, you put q4 in front of q7.
Finally, you compute the hash value on the blocks q1 through qn
in their new order.

Now the attack doesn't work; collisions against individual blocks
don't combine to produce a collision on the sequence because the
colliding values wouldn't have been fed into the hash function
in the same order as the actual blocks.

				Bear

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