Hello, I asked a coworker (she's a cryptographer) about this, and she said that output of SHA-1 is random enough that it should not exhibit any noticeable trait in its result even if we fed it with inputs that all exhibit a common trait (e.g. domain names).
Assuming this uniformity, the probability of no 40-bit hash values colliding out of 2^25 ones is: (1 - 0 / 2^40)(1 - 1 / 2^40)(1 - 2 / 2^40)(1 - 3/2^40)...(1 - (2^25 - 1) / 2^40) So the probability of *any* collision is one minus this probability (this is the formula she gave me): 1 - (1 - 1 / 2^40)(1 - 2 / 2^40)(1 - 3/2^40)...(1 - (2^25 - 1) / 2^40) Because even (2^25 - 1) / 2^40 is really close to 0, the dominant term would be 1, and the probabilty of collision in turn will be really close to 0. Eugene On Fri, Sep 12, 2003 at 06:52:41PM +0200, Iljitsch van Beijnum wrote: > On vrijdag, sep 12, 2003, at 11:07 Europe/Amsterdam, George Gross wrote: > > > At the risk of triggering another firestorm of pro/con debate, is > >there any reason why the centrally assigned Global ID defined by > >hinden-ipv6-global-local-addr-02.txt could not be simply the low-order > >40 > >bits of a SHA hash of a domain name? i.e. if you own the domain name, > >you > >get the IP-v6 global ID for "free"? This would side step the angst of > >setting up yet another global registry... > > Hm, with 2^40 possible prefixes and already something in the order of > 2^25 domains in use, I expect collisions will be a definite factor. I > would also be interested in seeing how the SHA-1 algorithm holds up. > Anyone care to get a suitably large list of domain names (a million or > so) and do some statistics on the lower 40 bits of the associated SHA-1 > hash? > > It did occur to me that the domain name sellers are in a better > position to give out these prefixes than the traditional IP address > registries, though. Especially if you consider that they'd just be > selling domain names under c.f.ip6.arpa. :-) > > > -------------------------------------------------------------------- > IETF IPv6 working group mailing list > [EMAIL PROTECTED] > Administrative Requests: https://www1.ietf.org/mailman/listinfo/ipv6 > -------------------------------------------------------------------- -------------------------------------------------------------------- IETF IPv6 working group mailing list [EMAIL PROTECTED] Administrative Requests: https://www1.ietf.org/mailman/listinfo/ipv6 --------------------------------------------------------------------
