Re: [PATCH] Implement fast hash-collision detection

On Tue, Nov 29, 2011 at 09:08:27AM -0800, Shawn O. Pearce wrote:

Minor nit: it's actually way less than that. You have to do on the order of 2^80 operations to get a 50% chance of a collision. But that's not the probability for a collision given a particular number of operations[1].

The probability for a SHA-1 collision on 10 million hashes (where linux-2.6 will be in a decade or two) is about 1/(2^115).

That doesn't change the validity of any of your points, of course. 1 in 2^80 and 1 in 2^115 are both in the range of "impossibly small enough not to care about".

To continue our astronomy analogies, NASA estimates[2] the impact probability of most tracked asteroids in the 10^6 range (around 2^20). So getting a collision in linux-2.6 in the next decade has roughly the same odds as the Earth being hit by 5 or 6 large asteroids.

-Peff

[1] http://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem

[2] http://neo.jpl.nasa.gov/risk/