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