Fabulous Adventures In Coding
Eric Lippert is a principal developer on the C# compiler team. Learn more about Eric.
Let's recap: a GUID is a 128 bit integer that is used as a globally unique identifier. GUIDs are not a security system; they do not guarantee uniqueness in a world where hostile parties are deliberately attempting to cause collisions; rather, they provide a cheap and easy way for mutually benign parties to generate identifiers without collisions. One mechanism for ensuring global uniqueness is to generate the GUID so that its bits describe a unique position in spacetime: a machine with a specific network card at a specific time. The downside of this mechanism is that code artifacts with GUIDs embedded in them contain easily-decoded information about the machine used to generate the GUID. This naturally raises a privacy concern.
To address this concern, there is a second common method for generating GUIDs, and that is to choose the bits at random. Such GUIDs have a 4 as the first hex digit of the third section.
First off, what bits are we talking about when we say "the bits"? We already know that in a "random" GUID the first hex digit of the third section is always 4. Something I did not mention in the last episode was that there is additional version information stored in the GUID in the bits in the fourth section as well; you'll note that a GUID almost always has 8, 9, a or b as the first hex digit of the fourth section. So in total we have six bits reserved for version information, leaving 122 bits that can be chosen at random.
Second, why should we suppose that choosing a number at random produces uniqueness? Flipping a coin is random, but it certain does not produce a unique result! What we rely on here is probabilistic uniqueness. Flipping a single coin does not produce a unique result, but flipping the same coin 122 times in a row almost certainly produces a sequence of heads and tails that has never been seen before and will never be seen again.
Let's talk a bit about those probabilities. Suppose you have a particular randomly-generated GUID in hand. What is the probability that a specific time that you randomly generate another GUID will produce a collision with your particular GUID? If the bits are chosen randomly and uniformly, clearly the probability of collision is one in 2122. Now, what is the probability that over n generations of GUIDs, you produce a collision with your particular GUID? Those are independent rare events, so the probabilities add (*); the probability of a collision is n in 2122. This 2122 is an astonishingly large number.
There are on the order 230 personal computers in the world (and of course lots of hand-held devices or non-PC computing devices that have more or less the same levels of computing power, but lets ignore those). Let's assume that we put all those PCs in the world to the task of generating GUIDs; if each one can generate, say, 220 GUIDs per second then after only about 272 seconds -- one hundred and fifty trillion years -- you'll have a very high chance of generating a collision with your specific GUID. And the odds of collision get pretty good after only thirty trillion years.
But that's looking for a collision with a specific GUID. Clearly the chances are a lot better of generating a collision somewhere else along the way. Recall that a couple of years ago I analyzed how often you get any collision when generating random 32 bit numbers; it turns out that the probability of getting any collision gets extremely high when you get to around 216 numbers generated. This generalizes; as a rule of thumb, the probability of getting a collision when generating a random n bit number gets large when you've generated around 2n/2 numbers. So if we put those billion PCs to work generating 122-bits-of-randomness GUIDs, the probability that two of them somewhere in there would collide gets really high after about 261 GUIDs are generated. Since we're assuming that about 230 machines are doing 220 GUIDs per second, we'd expect a collision after about 211 seconds, which is about an hour.
So clearly this system is not utterly foolproof; if we really, really wanted to, we could with high probability generate a GUID collision in only an hour, provided that we got every PC on the planet to dedicate an hour of time to doing so.
But of course we are not going to do that. The number of GUIDs generated per second worldwide is not anywhere even close to 250! I would be surprised if it were more than 220 GUIDs generated per second, worldwide, and therefore we could expect to wait about 241 seconds, for there to be a reasonable chance of collision, which is about seventy thousand years. And if we are looking for a collision with a specific GUID, then again, it will take about a billion times longer than our initial estimate if we assume that a relatively small number of GUIDs are being generated worldwide per second.
So, in short: you should expect that any particular random GUID will have a collision some time in the next thirty billion trillion years, and that there should be a collision between any two GUIDs some time in the next seventy thousand years.
Those are pretty good odds.
Now, this is assuming that the GUIDs are chosen by a perfectly uniform random process. They are not. GUIDs are in practice generated by a high-quality pseudo-random number generator, not by a crypto-strength random number generator. Here are some questions that I do not know the answers to:
I do not know the answers to any of these questions, and therefore it is wise for me to assume that the answers to the bottom four questions is "yes". Clearly it is far, far more difficult for someone to work out where and when a version-four GUID was create than a version-one GUID, which has that information directly in the GUID itself. But I do not know that it is impossible.
There are yet other techniques for generating GUIDs. If there is a 2 in the first hex digit of the third section then it is a version 1 GUID with some of the timestamp bits have slightly different meanings. If there is a 3 or 5 then the bits are created by running a cryptographic hash function over a unique string; the uniqueness of the string is then derived from the fact that it is typically a URL. But rather than go into the details of those more exotic GUIDs, I think I will leave off here.
(*) As the comments point out, this is an approximation that only holds if the probability is small and n is relatively small compared to the total number of possible outcomes.
It should also be taken into account that really collisions are a problem only if they happen in the same domain.
For example, if you use a GUID as an ID in a database, a conflict with a COM component identifier has no effect whatsoever. This reduces the space for the accidental conflict to a point where a collision is practically impossible.
I said *accidental* because maliciousness/stupidity/lazyness/ignorance/naivety/whateverelse may raise this probability to 100%. For example there are COM components shipped (!) with the GUID which was contained in the sources for some sample component.
At least in Java random GUIDs are generated using the default crypto-rng. I wouldn't be surprised if that was the case in Windows API (and .Net which just uses the WinAPI) as well.
Since you usually make pop- (and sub-pop-) culture references that I expect, I was surprised that you talked about the probability of 122 coin tosses producing non-unique results without mentioning the possibility of being "within un-, sub- or supernatural forces" (see en.wikipedia.org/.../Rosencrantz_and_Guildenstern_Are_Dead).
That "rule of thumb" is called Birthday paradox: en.wikipedia.org/.../Birthday_paradox
My colleague wrote a C# implementation of the algorithm for generating version 3 or 5 GUIDs, linked at the bottom of this post: code.logos.com/.../generating_a_deterministic_guid.html
Yes, if you flip a coin just 20 times, and write down the sequence of heads and tails that you got, you can then calculate the odds that you would have gotten that sequence.
You'll conclude that a miracle just occurred.
Indeed, a miracle occurs (something that is extremely unlikely) every time you generate a GUID. Or do any daily activity, if you take into account your specific muscle movements....
@Eugene Good that you mentioned it, because in the original article that Eric linked there's only halve the article about exactly that phenomenon ;)
Personally I've never seen anything but Type1 and 4 GUIDs, which means I'd actually be quite interested where those are used in practice (the URL example makes sense and I think as soon as someone invents a timemachine I'll have to go back in time and rewrite some code.. )
I have an understanding of entropy as it applies in thermodynamics (okay, a weak understanding). But I do not see how it cross-applies to pseudo-random number generation. Is it a direct correlation, or is it a convenient term that works well to get a handle on the concept in numerics? Eric, if you don't mind, can you explain or link to a good explanation?
Entropy is by definition the amount of randomness or disorderliness in a system. When building a deterministic device that generates random or pseudo-random numbers, there have got to be some random, unpredictable inputs to the system for the outputs to be unpredictable. Weak random number generators use bad sources of entropy, like the current time. Crypto strength random number generators use good sources of entropy, like keystroke timings. Exceptionally good random number generators use exceptionally entropic inputs, like the outputs of geiger counters or cosmic background radio signal receivers. Getting good entropy is expensive.
To be a bit more rigorous, I'm using "entropy" here like this: suppose there are 256 possible inputs to our pseudo-random number generator, and the seed is chosen by some random process that really does choose each one of the 256 possibilities with equal likelihood. Such a system is said to have "eight bits of entropy". If some of those 256 possibilities are more likely than others then we have less than eight bits of entropy. You might make a buffer that contains one thousand bits worth of timing data about keystroes. But keystroke timings are not entirely random; there are patterns. Therefore there could be less than a thousand bits of entropy in those thousand bits of seed, depending on how the bits were actually captured. -- Eric
Entropy is simply used as a term for the amount of randomness.
@Aaron Eshbach: "used as a term for the amount of randomness." I disagree, at least with respect to how Eric is using it. What you describe is the non-rigourous definition for entropy in thermodynamics. The way Eric has used it, it has a source (what source of entropy is used), and it has a number of bits (how many bits of entropy are used). I bet he is talking about Information Theory Entropy (en.wikipedia.org/.../Entropy_(information_theory). So it looks like I have answered my own question. (Sorry, this is not my field, but I still want to learn a little about it.)
@Paul As someone with only the most basic understanding of entropy in physics, I must say I still do think that there are quite some parallels. There's actually an - well I'd say interesting but that'd be a lie - article on this topic on wiki: en.wikipedia.org/.../Entropy_in_thermodynamics_and_information_theory
But I think it's much simpler to think of entropy in our case as the amount of information some message has instead of drawing parallels to physics. A perfectly random generated 128bit number has 128bits of entropy since there are 128bits of useful information to it. If there was some pattern in the key (say 1s and 0s always have to alternate) we get less entropy (in the alternating example, the entropy is suddenly just 1bit..)
The other thing you need to include is this assumes that the GUIDs are all being used for exactly the same purpose.
To once again be a pedant, I'll note that the number of bits used for version information could be 5 or 7 in rare cases.
@voo - .NET uses a type 3 GUID für types which don't have an explicit GUID assigned. Type 3 and 5 GUIDs are really useful if you need a unique identifier regenerated consistently.
If I remember correctly they use a hash of
- a seed GUID
- the strong name key (if the assembly has one)
- the fully qualified type name
I think the source for this was in the rotor shared source implementation, but I also accidentally stumbled upon it during a native debug session involving some COM interop.
The seed GUID makes it unlikely to conflict with anyone else, I think it's a quite clever interpretation of Type 3 GUIDs (which normally use domain names to avoid conflicts).
To produce real good Guids, PC's should be equiped with a proper Lava lamp.