[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index]

To: | Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx> |

From: | Maxim Sobolev <sobomax@xxxxxxxxxxx> |

Date: | Wed, 06 Aug 2008 17:54:15 -0700 |

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.

[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index]