Re: Whirlpool 512-bit collisions?

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. Some other outputs
> appear more than once. The loss of entropy is a
> small fraction of a bit, pretty much independent
> of the size of the hash.
>
> (Note that the probability of a collision is also
> not 2^-512 (or whatever) for exactly the same
> reason. But it's a perfectly good approximation.)

So entropy is reduced by 1/e (a little less than half, which is a little
less than one bit of entropy) due to the fact that certain 512-bit values
never occur.

Entropy is further reduced because the 512 bit values which DO occur are not
all equally probable, since some of them result from more than one of the
possible inputs. Perhaps some even occur from more than two of the possible
inputs, etc.

My intuition tells me we are probably talking about losing on the order of
one bit of entropy, bottom line. But I'm not quite ready to trust my
intuition....

Alan
Received on Thu Sep 29 21:44:25 2005