How are .NET 4 GUIDs generated?

Question

I am aware of the multitude of questions here as well as Raymond's excellent (as usual) post. However, since the algorithm to create GUIDs was changed apparently, I found it hard to get my hands on any up-to-date information. The MSDN seems to try and provide as few information as possible.

What is known about how GUIDs are generated in .NET 4? What was changed, and how does it affect the security ("randomness") and integrity ("uniqueness")?

One specific aspect I'm interested in: In v1, it seems to be about impossible to generate the same GUID on a single machine again since there was a timestamp and counter involved. In v4, this is no longer the case (I was told), so the chance to get the same GUID on a single machine ... increased?

Kilmer

Answer 1

Since Windows 2000 Microsoft uses a version 4 algorithm:

With Windows 2000, Microsoft switched to version 4 GUIDs, since embedding the MAC address was viewed as a security risk. ¹

You can see that as well from a GUID generated in .NET (from Wikipedia):

Version 4 UUIDs have the form xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx with any hexadecimal digits for x but only one of 8, 9, A, or B for y. e.g. f47ac10b-58cc-4372-a567-0e02b2c3d479.

A version 4 UUID consist of 122 significant bits, giving 2^122 distinct values which is a very large number. Given a set of H values, the expected number of values we have to choose before finding the first random collision with a 50% chance can be calculated as follows (see Birthday Attack on Wikipedia):

The result (birthday bound) for 2^122 different values is approximately 2,89e+18. This assumes that the generated values are randomly distributed. Obviously, if the values are distributed unevenly, a random collision can be found faster. For further details also see Collisions.

^{1_{As a matter of fact, the author of the Melissa worm could be tracked down due to a GUID generated using a version 1 algorithm.}}

Mandatory

+1 - GUIDs are generated by the underlying OS - not .NET. The .NET classes just wrap the underlying OS APIs. – Hausa

Thanks for the answer and the additional link, that clarified the bulk of my questions. Do you know if the assumption I'm making in the last paragraph is correct? – Kilmer

Dirk, can you address whether this applies to .NET core as well? Do we need to look into the OS APIs for whatever is running .NET core in order to find out the GUID generation version? – Indemnify

According to msdn.microsoft.com/en-us/library/…, since Windows 2000 back in 1999, "the random bits for all version 4 GUIDs built in Windows are obtained via the Windows CryptGenRandom cryptographic API or the equivalent, the same source that is used for generation of cryptographic keys". So I'd say you could call them cryptographically secure -- at least to the extent of the 122 bits of entropy they provide. – Papilionaceous

@JordanRieger: Your statement may be correct, but you should not forget that section 6 of RFC4122 is pretty clear about what you should assume about the randomness of UUID values (including version 4): tools.ietf.org/html/rfc4122#section-6 "Do not assume that UUIDs are hard to guess; they should not be used as security capabilities" — so the specification clearly says you should not consider UUIDs cryptographically secure (even if the actual implementation would guarantee that). – Mandatory

@DirkVollmar yes, I've seen that advice from the RFC quoted in other similar discussions, but I'd say MS's specification overrides the RFC in this case, especially as the question specifies MS .NET v4. If the question was asking about the security of GUID/UUID v4 in general, then only the RFC's advice would be relevant. – Papilionaceous

Why only 8, 9, A, or B for y? – Rufe

It’s because the highest bits of that part of the UUID are 0 and 1 according to the spec tools.ietf.org/html/rfc4122#section-4.4 – Mandatory

Answer 2

Yes, there was a change in .NET 4.0, Guid.NewGuid() directly calls CoCreateGuid(), a small wrapper around UuidCreate(). Previous versions of .NET called a helper function in the CLR, GuidNative::CompleteGuid(). Which calls CoCreateGuid. Not sure why this change was made, smells like nothing more than a minor optimization.

At any rate, the exact same Windows function generates the Guid, the algorithm has been the same for the past 10 years, it is as reliable as it ever was.

Babyblueeyes

Answer 3

The GUID generation algorithm is recorded in the GUID itself, checking the variant and (optionally) the version. Wikipedia gives a good rundown: first, GUID Variants.

Variant is indicated by the initial bits of the 9th octet, "pinned" to 0, 10, 110 or 111. Using

string show(Guid g) => $"{g}: fam {Convert.ToString(g.ToByteArray()[8], 2)}";
show(Guid.NewGuid())

we might get "1b579ecd-b72c-4550-b10b-f8dd41699ac1: fam 10110001". The family is pinned to 10, OSF DCE UUID or variant 2. This variant defines a version, held in the more significant "nibble" of the 7th octet.

BUT, variant 2, being an MS format is little-endian. Let's take a look with another quick method:

void SeeOrder(Guid g) => Console.WriteLine($"{g}\n{g:N}\n{string.Join("", g.ToByteArray().Select(b => $"{b:x2}"))}"); 

shows something like

dd3f9bdf-ba47-4411-84c8-6cfcc5d39bb5
dd3f9bdfba47441184c86cfcc5d39bb5
df9b3fdd47ba114484c86cfcc5d39bb5

The first three integer groups are transposed—two for time, one reserved; 32, 16 and 16 bits respectively. The last two groups are not, because the last 8 octets are a "string": 1 reserved octet (where the "family" is represented) and 7 "node" octets. So the 7th version octet is actually encoded as the 8th (index 7).

Expanding show to highlight the version:

string show(Guid g) => $"{g}: fam {Convert.ToString(g.ToByteArray()[8], 2)}, ver {g.ToByteArray()[7].ToString("x")}";

We'll get "154573de-d420-433b-bb25-aff50590038b: fam 10111011, ver 43". The nibble in question is the 4, thus version 4: pseudo-random generation.

Bandeen