On Jun 12, 8:53 am, "Edward K. Ream" <[email protected]> wrote:
> Folks, this is too important a question for hand waving. Or hope. I asked the folks at #git and got a good answer. The probability of a collision is related to the so-called "birthday attack": http://en.wikipedia.org/wiki/Birthday_attack QQQ Specifically, if a function f(x) yields any of H different outputs with equal probability and H is sufficiently large, then we expect to obtain a pair of different arguments x1 and x2 with f(x1) = f(x2) after evaluating the function for about 1.25 \cdot \sqrt H different arguments on average. QQQ The sha-1 key has 160 bits so the probabilities will fall between the 128-bit and 256-bit entries in the table. As you can see from the table, with a 128-bit key, it would take 4.8 × 10**29 hashes before the probability of a collision rises above 10**-18. The odds are even better (that is lower) for a 160 bit key. It appears that this is a complete answer to my question. Any comments? Corrections? Edward --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "leo-editor" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/leo-editor?hl=en -~----------~----~----~----~------~----~------~--~---
