Re: Whirlpool 512-bit collisions?

Gregory G Rose wrote:
> >Gregory G Rose wrote
> >> Assuming that the hash function acts as a perfect
> >> random function, about 1/e ~= 0.37 of the
> >> possible outputs won't appear.
>
>I'm sure there's actually a known
>theoretical value, too, but it's beyond me to get
>that.

Here is something I've posted previously on the subject:

  Suppose we've got a random function F : {0,1}^n -> {0,1}^n.
  Let f_j denote the fraction of n-bit values which can appear as the
  result of iterating F j times. Then f_1 ~ 1 - 1/e, and
    f_{j+1} ~ 1 - e^{-f_j}.
  The first few numbers in the sequence are .632, .469, .374, .312,
  .268, .235, .210, etc. Asymptotically, f_j ~ 2/(j + log j) is a
  pretty good approximation.

  Moreover, I'd guess that the lost entropy is going to be on the
  order of lg f_j bits, which is not too large as long as j isn't too
  big. Even asymptotically, this is lg f_j ~ 1 - lg(j + log j), so
  if you hash it 2^k times, you'll only lose about k-1 bits of entropy
  (just a guess -- I have no proof).

http://www.cs.berkeley.edu/~daw/my-posts/hash-iteration

Note that this talks only about information-theoretic entropy.
If you're a computationally bounded attacker, you can't tell that
there has been any loss of entropy. For a random oracle F,
F(X) is pseudorandom if X is.
Received on Thu Sep 29 21:44:43 2005