Matthew Dillon wrote:
Well, you've described both sides of the debate quite well. I for
one am in the 0-risk camp. ReiserFS got into trouble depending on
a collision space (albeit a small one). I did extensive testing of
64 bit collision spaces when I wrote Diablo (A USENET news system
contemporary with INN, over 10 years ago) and even with a 64 bit space
collisions could occur quite often simply due to the volume of article
traffic.
This is due well-known mathematical property, called birthday problem or
birthday paradox. As a result of that property for ideal hash function
of size N bits you only need 2^(N/2) random inputs to generate a
collision with sufficient probability. Therefore, for 64 bit hash
function you will get one collision for approximately every 2^32 inputs.
http://en.wikipedia.org/wiki/Birthday_attack
-Maxim
