Joux attack against multipreimages

[Hal Finney]

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 majordomo at metzdowd.com