More problems with hash functions

Hal Finney hal at finney.org
Sat Aug 28 14:56:51 EDT 2004


Jerry Leichter writes:
> It all depends on how you define an attack, and how you choose to define your
> security.  I explored the "outer edge":  Distinguishability from a random
> function.  For a random function from {0,1}*->{0,1}^k, we expect to have to do
> 2^k work (where the unit of work is an evaluation of the function) per
> collision.  The collisions are all "independent" - if you've found N, you have
> ... N.  The next one you want still costs you 2^k work.

I don't believe this correct.  Joux said that for a true random function,
finding a multicollision of degree j, i.e. j distinct values which hash
to the same thing, takes 2^((j-1)*k/j) for a k-bit hash.  He mentioned
a Crypto paper by David Wagner from a few years ago which showed how
to do this.  See http://www.cs.berkeley.edu/~daw/papers/genbday.html .
This means that the work for a (j+1)-collision is about 2^(k/j^2) times
harder than for a j-collision, not 2^k times harder.

Now, this is not done by first finding a j-collision and then looking
for a new value that matches; that would, as you say, take 2^k times
the work.  Rather, one collects enough hashes and then matches them up
in an efficient way to find the (j+1)-collision.

The wide-internal-path proposal will therefore satisfy the constraints
about multicollisions.  With a 2k bit wide internal path for a k bit hash,
it will take 2^k work to find an internal collision.  With some multiple
of this, Joux's attack finds large multicollisions.  But as the paper by
Wagner shows, you can find arbitrarily large multicollisions in a true
random k-bit function with less than 2^k work.  Since Joux's attack
takes more than this, it does not distinguish this hash construction
from a random function.

Hal

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



More information about the cryptography mailing list