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