I was looking at Joux's paper again and I noticed that he also had some comments regarding preimage resistance. I believe these imply a weakness even in the construction I proposed of using a double width hash and then collapsing the output down to single width at the end.
My argument was that if the hash output size was n bits, so the internal width is 2n, then it would take 2^n work to find a collision on an internal block, but that was more work than it would take to break the hash function by brute force, hence it was not an attack. However I forgot that there are some problems which an n-bit hash should resist with even stronger than 2^n force. Specifically, the problem of finding multiple preimages, say 2^k preimages of some fixed value, should take about 2^k * 2^n work for an ideal hash function. There is no shortcut beyond trying random values and seeing if you get lucky, and for each value the chance of success is 1 in 2^n. However, Joux shows how to do better than this. He uses his trick of setting up k blocks and finding a collision in each. Even with my double width construction that takes k*2^n work. This gives us a 2^k multicollision. Now comes the new idea. Add one more block. Do an exhaustive search on that block to map the output from the multicollision to the desired hash function output, the one we are trying to find preimages of. That should take about 2^n work because the chance of success for any input is 1 in 2^n, since the actual hash output size is n bits after folding. Now this gives us 2^k preimages. For each of the 2^k possible choices in the multicollision, the extra block maps us to the desired output. We did (k+1)*2^n work and got 2^k preimages, but it should have taken us 2^k * 2^n work. This means that even the double-width hash construction is not as secure as an ideal hash. It is safe against multicollisions but not against multipreimages. Hal Finney --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]