SHA Collisions / 2010-09-11

I once saw a talk on git where the presenter casually mentioned that the probability of a SHA-1 collision is less than that of being struck by lightning. This certainly sounds plausible for two arbitrary values (where the probability should be one in 2160), but in a situation like a git repository with thousands of objects each identified by its own hash, I have to wonder how significant the effects of the birthday paradox are. So I pulled out the old Ruby interpreter to find out.

I decided to go with the assumption that a good sized git repository has 100,000 objects it it. I have one at work with over 50,000, so this seems reasonable. Given 100,000 objects, and the assumption that all hashes are equally likely, the probability of a collision is one in 2923295604222228059227973022624136543197. That’s less likely than flipping a coin 131 times and seeing all heads. I’m not worried about SHA collisions anymore.