More problems with hash functions

[Hal Finney]

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.

Recall that the attack is to first find a collision in the first block.
Then you take the output of that block and use it as the input to
the second block, and starting from that value find a collision in
the second block.  Repeat for k blocks and you have a pair of values
for each block that take the input value from the previous block and
produce matching outputs.  Now you can choose any path among these
pairs of values, of which there are 2^k, and get a collision.  Presto,
you have a 2^k multicollision for the cost of k single-block collisions,
which departs from the ideal of a random function.

Adding a block counter doesn't help because it will still take only
2^(n/2) at worst to find a collision in the second block, even though
the block counter value is "2".  It's true that collisions from the first
block won't work in the second block, but that won't make it any harder
to find second-block collisions.

Hal

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