Re: What about SHA-1 collisions?

[Andrew Ardill <andrew.ardill@gmail.com>]

 A recent article [1] did an analysis on the number of items needed
from a given range to have a 50% chance of a collision. The famous
birthday paradox scenario was used, where you only need 23 people
before the chance of two of them having the same birthday is over 50%.
In this scenario there are ~366 options available to be picked from,
and 23 is significantly small in comparison.

The mathematics behind these statistics was extended to account for
any sized range (call it N) and it turns out that the number of items
(k) that can be picked before you have exceeded a given percentage
chance (T) of _not_ having a collision is roughly

k ~= sqrt(-2N.ln(T))

As pedrocr pointed out on Hacker News [2]

"Applying the formula for 160bit SHA-1 you need 1.7e23 objects to get
a 1% chance of collision. The current Linus kernel repository has 2.7
million objects. So to get a collision you'd need a repository that's
6e16 times larger. That should be plenty.

For some wacky perspective that's 10 million kernel sized
contributions for every man woman and child on earth together in a
single repository. It would seem git will reach plenty of other
bottlenecks before SHA-1 becomes a problem..."

An interesting analysis, even given that the OP presumes a collision
in their question.

Regards,

Andrew Ardill

[1] http://www.solipsys.co.uk/new/TheBirthdayParadox.html
[2] http://news.ycombinator.com/item?id=4753198