On 7/19/12, Mark Andrews <marka@isc.org> wrote:
Actually you can't. fdaa:aaaa:aaaa has 20/20 0/1 bits but is entirely non random. fdf0:f0f0:f0f0 has 20/20 0/1 bits but is entirely non random. [snip] The ratio of the number of bits doesn't tell you anything about whether the number was random or not. [snip]
Sure it does. A ratio of 1s to 0s of a sufficient deviation, is a sufficient but not a necessarily condition, for establishing that a sequence of binary numbers shown almost certainly was not chosen randomly. As for whether "fdf0:f0f0:f0f0" is a random number or not, I cannot say, not without a valid test for randomness on the sequence of bits that were chosen, and there are multiple appropriate tests available; use any reasonable test you like, they do exist, and 40 random bits is an amply large sample size. Despite that it is also definitely possible to manually construct strings that are not produced randomly, which nevertheless by design pass any specific test for randomness; intentional 'malice' cannot really be eliminated. However, there _are_ many non-random strings that exist which a 'lazy' or broken ULA ID generator might pick, that can be very easily detected as non-random with sufficient confidence, to tell the user "Hey, sorry, you can't use that. Please generate a new ULA ID".
improbable != impossible
Improbable with a sufficiently small probability is equal to impossible intents and purposes. The probability of generating any specific decimal number you pick a priori, constructed out of 40 bits, is essentially zero, no matter what number you pick; there are _a very large number_ of possible ULA IDs you can exclude, before you have excluded enough that it actually matters.. Rejecting ULA IDs on equipment that have less than a 10^-11 chance of being a random sequence of bits; is less likely to reject a valid ID, than there is to be a collision on a ULA ID, and it would have a high probability of preventing future collisions caused by accident, misconfiguration, etc. Which means that it may be a large improvement on the "honor system" for picking ULA IDs with no verification. "The collision doesn't happen" is a better scenario than "I know who to blame.... the guy before me who just picked zero.. and some former employee in the other company that just picked a ULA ID of zero." -- -JH