52

Before you start marking this as a duplicate, read me out. The other question has a (most likely) incorrect accepted answer.

I do not know how .NET generates its GUIDs, probably only Microsoft does, but there's a high chance it simply calls CoCreateGuid(). That function however is documented to be calling UuidCreate(). And the algorithms for creating an UUID are pretty well documented.

Long story short, be as it may, it seems that System.Guid.NewGuid() indeed uses version 4 UUID generation algorithm, because all the GUIDs it generates matches the criteria (see for yourself, I tried a couple million GUIDs, they all matched).

In other words, these GUIDs are almost random, except for a few known bits.

This then again raises the question - how random IS this random? As every good little programmer knows, a pseudo-random number algorithm is only as random as its seed (aka entropy). So what is the seed for UuidCreate()? How ofter is the PRNG re-seeded? Is it cryptographically strong, or can I expect the same GUIDs to start pouring out if two computers accidentally call System.Guid.NewGuid() at the same time? And can the state of the PRNG be guessed if sufficiently many sequentially generated GUIDs are gathered?

Added: To clarify, I'd like to find out how random can I trust it to be and thus - where can I use it. So, let's establish a rough "randomness" scale here:

  1. Basic randomness, taking current time as the seed. Usable for shuffling cards in Solitaire but little else as collisions are too easy to come by even without trying.
  2. More advanced randomness, using not only the time but other machine-specific factors for seed. Perhaps also seeded only once on system startup. This can be used for generating IDs in a DB because duplicates are unlikely. Still, it's not good for security because the results can be predicted with sufficient effort.
  3. Cryptograhpically random, using device noise or other advanced sources of randomness for seed. Re-seeded on every invocation or at least pretty often. Can be used for session IDs, handed out to untrusted parties, etc.

I arrived at this question while thinking if it would be OK to use them as DB IDs, and whether the Guid.comb algorithm implementation together with System.Guid.NewGuid() (like NHibernate does it) would be flawed or not.

6
  • 3
    You may want to clarify whether your goal is to: (a) generate pseudo-random values, or (b) generate a zillion GUIDs and have some idea of the probability of collision. Apr 12, 2010 at 11:17
  • 2
    If randomness is critical to you then I'm sure you're better of using something that has been designed for randomness instead of using a GUID. Apr 12, 2010 at 11:17
  • 8
    @George. Wow! Looks like you read it really thoroughly, especially the first sentence...
    – Vilx-
    Apr 12, 2010 at 13:51
  • 2
    It doesn't matter if the accepted answer is wrong, the question is still the same. And yes, I did read both questions. Apr 12, 2010 at 14:56
  • 1
    Under the covers Guid.NewGuid() calls Win32Native.CoCreateGuid.
    – Steven
    Aug 25, 2015 at 9:17

9 Answers 9

40

The answer is: You should not need to know this. As stated in the accepted answer to a related question:

A GUID doesn't make guarantees about randomness, it makes guarantees around uniqueness.

An even stronger statement on security and randomness is made in RFC4122, which speficies the UUID format:

Do not assume that UUIDs are hard to guess; they should not be used as security capabilities (identifiers whose mere possession grants access), for example. A predictable random number source will exacerbate the situation.

Anything else is an implementation detail (and might be subject change).

Windows specifics

Often, people claim that the behavior on Windows is documented and that it is therefore guaranteed that GUIDs are cryptographically secure.

The now archived [MS-SECO] Windows Security Overview document mentions in Appendix A:

Although only a small minority of version 4 GUIDs require cryptographic randomness, 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.

Moreover, section 2.5.5 of the same document explicitly mentions the use of "secret GUID" values as nonce or authenticator.

BUT: This piece of product behavior documentation is not a specification you can generally base the security of your product on (in particular in the context of .NET).

In fact, the document above describes an implementation detail of a particular product. Even if the current Windows and .NET Framework 4.x implementations produce truly random version 4 UUID values on Windows, there is no guarantee that System.Guid.NewGuid will do so in the future or on other .NET platforms (e.g. Mono, Silverlight, CF, .NET Core, etc).

Just as an example, the UUID algorithm used in earlier versions of .NET Core depends on the platform and you might get a version 1 UUID (on BSD).

9
  • Good answer on the security view. I trust GUID's to be unique, for record identifiers, but do not rely on them for determining application security.
    – invert
    Apr 16, 2010 at 7:42
  • 3
    Its funny you refer to the RFC but miss section 4.4 and 4.5. It here states that V4 UUIDs (which Windows 2000 and later uses) are based on truly-random or pseudo-random numbers. Jan 27, 2011 at 16:37
  • 2
    @Pauli - the RFC just says that you can generate UUIDs from random sources, not that all V4 UUIDs are truly-random. If the source used to generate your V4 UUIDs is pseudo-random and is predictable, you still have the problem that random v4 UUIDs may not be hard to guess.
    – bacar
    Aug 3, 2012 at 15:13
  • @bacar: If there is no requirement regarding the random distribution of UUID sequences, how can one make any meaningful statements about the probability that sequences of UUIDs generated by entirely independent entities will not contain some shared members? To be sure, one probably doesn't need a full 120+ bits of entropy per GUID to avoid collisions in realistic scenarios, but one needs some.
    – supercat
    Nov 15, 2013 at 19:23
  • 1
    @SilverlightFox: It's rather the other way around. The documentation doesn't make any guarantees about the randomness of the produced value so we can't claim that it produces a "truly random" output. Even is the output would fulfill some well-defined randomness criteria, this would be an implementation detail not backed by the docs / RFC. Feb 14, 2016 at 15:11
19

Some people have already hinted at that but I want to repeat it since there appears to be a misconception there:

Randomness and uniqueness are orthogonal concepts.

Random data can be unique or redundant, and likewise unique data can use a random source or a deterministic source (think a global counter that is locked and incremented for every GUID ever created).

GUIDs were designed to be unique, not random. If the .NET generator appears to use random input, fine. But don’t rely on it as a source of randomness, neither for cryptographical nor for any other purposes (in particular, what distribution function do you expect to get?). On the other hand, you can be reasonably sure that GUIDs created by .NET, even in large volumes, will be unique.

7
  • 2
    Sorry, I disagree. If independent machines on the world create GUIDs, the smallest chance for collision you can achieve is if each machine creates a truly random GUID (and they are big enough, to make the chance for collisions astronomically small) - any deviation from complete randomness will decrease entropy and increase the chance for two machines in the exact same starting conditions to produce the same GUID
    – Falco
    Aug 1, 2019 at 16:28
  • @Falco This is only true if the machine-specific parts of the UUID have a higher chance of collision than the entropy of truly random data of the same bit length. — This is an important caveat. In practice you may well be right, and AFAIK most UUID implementations are therefore using a specification that’s purely based on random data (version 4). But this is an implementation detail as far as UUIDs are concerned. That’s what my answer is pointing out. Aug 1, 2019 at 16:57
  • @KonradRudolph and I just cannot think of a machine dependent parameter which could even theoretically provide less collisions than true randomness for mass creation of ids on the same system as well as on different systems. It just seems impossible.
    – Falco
    Aug 1, 2019 at 20:26
  • @Falco ISBNs (for books) are one such example (in fact there are duplicate ISBNs because producers are idiots, but they can be made unique with an additional note, totalling at less than a GUID’s length). Other examples are addresses: both virtual (IPs, URIs), and physical (postal). Aug 2, 2019 at 13:41
  • 1
    @KonradRudolph all these need either a central register, or synchronization of information across different systems, or are hinged on highly limited parameters (postal position). Any number of systems (including identical copies of virtual machines) should be able to generate an arbitrary number of GUIDs without collisions worldwide. None of your examples comes even close to providing this. - Which means I should be able to create a million GUIDs on two identical, but disconnected servers in the same location.
    – Falco
    Aug 2, 2019 at 13:55
9

APIs that produce random bytes but which are not explicitly documented to produce cryptographically strong random bytes cannot be trusted to produce cryptographically strong random bytes.

If you need cryptographically strong random bytes, then you should be using an API which is explicitly documented to produce them.

public Guid CreateCryptographicallyStrongGuid() {
    var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
    var data = new byte[16];
    rng.GetBytes(data);
    return new Guid(data);
}

These GUIDs are simply 128 bits of cryptographic randomness. They are not structured, and they will not collide.

See this article for some of the math. Using "The General Birthday Formula", rearranging gives

n = sqrt(-2T * ln(p))

where n is the number of chosen elements, T is the total number of elements (2^128), and p is the target probability that all n chosen elements will be different. With p = .99, this gives *n = 2.61532104 * 10^18*. This means that we can generate a billion truly random GUIDs per second within a system for a billion seconds (32 years), and have better than 99% chance at the end that each one is unique within the system.

12
  • 3
    This might produce pseude-random values, but you loose the guarantee that the generated guid is unique (although the likeliness of a collision has a low probability if you only generate few values). Apr 12, 2010 at 11:29
  • 1
    @Vilx: Even if you generate really many GUIDs on many networked machines the values are guaranteed to be unique, see Raymond Chen's post: blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx (although if you create sufficient many GUIDs you will eventually get a collision, but I guess the universe will no longer exist at that point in time). Apr 12, 2010 at 12:33
  • 4
    Does this code snippet generate valid GUIDs? I can't see where you set the bits that indicate the GUID type.
    – user9876
    Apr 12, 2010 at 12:46
  • 3
    @Vilx: According to RFC4122 (tools.ietf.org/html/rfc4122) even UUID version 4 should set version bits and 2 other reserved bit. Apr 12, 2010 at 15:46
  • 5
    @Vilx: Yes, it absolutely is wrong to set the reserved bits incorrectly. Jul 26, 2013 at 15:16
6

The definition of Random in no way relates to the definition of Globally Unique.

Flipping a coin twice and getting HH, HT, TH, TT are all random. HH is just as random as HT.

Flipping a "special" coin twice and guaranteeing that you will only get HT or TH is uniqueness.

0
2

According to https://msdn.microsoft.com/en-us/library/bb417a2c-7a58-404f-84dd-6b494ecf0d13#id11, 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 consider them cryptographically secure -- at least to the extent of the 122 bits of entropy they provide.

Also see https://stackoverflow.com/a/35384818/284704, where Will Dean verified through a debug-step that the CLR is calling the proper secure OS random generator.

2
  • Very interesting to read this. My concern is that you cannot guarantee the implementation will remain this way, nor will it be derived consistently across platforms and versions of the framework. Best to stick to an explicit CSPRNG. Jun 26, 2018 at 19:44
  • @JamesWestgate But can we ever guarantee that an implementation will not change? Suppose .NET 9.5 (or whatever) comes out in the year 2030, and its GUID generation (or Windows') becomes insecure -- in that case, they would certainly update the documentation to reflect the new behavior. You can never really guarantee anything about future versions of a library/API, but the fact that MS has kept GUID generation cryptographically secure for nearly 20 years should be a strong indication that GUIDs will always be that way. Jun 26, 2018 at 22:49
1

They are random so that it is mathematcially provable that collisions should not occur for a very long time, so that you can assume that they are unique globally. However, they are not cryptographically strong, since this would require a true randomness, which isn't really possible in computers without dedicated hardware.

4
  • True, but I think that device noise makes a pretty good source of entropy.
    – Vilx-
    Apr 12, 2010 at 11:19
  • Errr..... cryptographically strong random number generators do exist. They can be done in 100% software. (Although hardware support does make it much easier to write them, and much easier to prove security). On Windows PCs, CryptGenRandom() is the normal one.
    – user9876
    Apr 12, 2010 at 11:21
  • Well, just the fact there were known problems with it until Windows Vista and that the algorithm is not published and just takes into account a very long list of specific information to make it as random as possible doesn't mean that a replay is impossible, at least in a virtualized lab environment (which doesn't mean that it is unsafe to use in the wild). en.wikipedia.org/wiki/CryptGenRandom
    – Lucero
    Apr 12, 2010 at 11:26
  • 3
    If it is mathematically provable that collisions should not occur then by definition it is NOT random at all! That's like saying a roulette table is only random if a number doesn't come up a second time until all the others have.
    – Robin Day
    Apr 12, 2010 at 11:34
1

GUIDs are designed to be at number 2 on your scale, i.e. "can be used for generating IDs in a DB because duplicates are unlikely*."

As for security, the problem isn't "it's not good for security because the results can be predicted with sufficient effort.". The problem is that no-one gives you a documented security guarantee.

In practise, according to this comment and this one, the GUID generation is implemented in terms of a cryptographically secure RNG (CryptGenRandom). But that appears to be an undocumented implementation detail. (And I haven't verified this - it's random comments on the Internet, take with a truckload of salt).

(* Where "unlikely" means something like "the chances of anyone finding a duplicate GUID before the end of the universe are less than the chances of you personally winning the lottery." Implementation bugs excepted, of course.)

1
  • "In practise, according to this comment and this one, the GUID generation is implemented in terms of a cryptographically secure RNG " -- no way. That's conflating uniqueness (protecting against accidental duplicates) with randomness (protecting against prediction). There's a difference between finding a duplicate GUID and looking for a duplicate GUID
    – Mark Sowul
    Feb 27, 2017 at 17:48
0

Focussing on your question of using GUID's as row identifiers:

GUID's are for databases geared towards replication, or generating rows ahead of time before adding them to the DB. If you do not need GUID's to solve a particular problem, try stick to incremental numbering. GUID's complicate debugging and testing a little bit.

The COMB method in the article you mention seems pretty great, actually. I never realized, thanks for that one! (p.s. the printer friendly version of that article reads much better)

So if you don't need to generate a GUID ahead of time, you can let the database handle the GUID generation for you. The speed differences you'll only notice if you start adding 10,000's of records in one go, which you shouldn't do anyway, that's what bulk-importing is for.

Also have a look at Jeff on ID's vs GUID's

create table #temp ([id] uniqueidentifier primary key default(newid()), [name] varchar(20))
insert into #temp (name) values ('apple')
insert into #temp (name) values ('orange')
insert into #temp (name) values ('banana')
select * from #temp
drop table #temp

id                                   name
------------------------------------ --------------------
911B0CBD-4EED-4EB0-8488-1B2CDD915C02 banana
56CF3A80-A2DE-4949-9C9B-5F890824EA9C orange
5990B9FD-143D-41B0-89D1-957B2C57AB94 apple
1
  • The need for GUIDs in my case is complex. First of all I'm using NHIbernate ORM, and secondly I'd like to create objects in my app and then let the user decide whether or not to save them (eg. whether the user presses OK or Cancel). If I used IDENTITY NHibernate would need to insert the record as soon as it was created to get the ID (which is what I don't want). GUIDs allow me to create IDs without touching the DB, and COMB takes care of performance problems. But it can fail if duplicate GUIDs are generated because of subtleties in implementation not known by the original authors.
    – Vilx-
    Apr 15, 2010 at 8:55
-1

I read somewhere that the chances of winning the lottery would be equivalent to 2 4-byte "GUIDs" colliding. The standard 16-byte GUIDs would offer much less chance of collision.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.