How securely unguessable are GUIDs?

A while ago I worked on a web application where users could buy tickets. Due to the way our client's processes worked, what you effectively got as a result of your purchase was a URL with the ticket number in it.

These were tickets to buy property in the Middle East, and each ticket was potentially worth around $3,000,000. Clearly dishing out sequential integers would have been a bad idea. We used GUIDs as they're basically unguessable, but my question is: are they secure enough?

As I understand it, the GUIDs .NET produces are totally pseudo-random (except for a few non-varying bits). However, I don't know what algorithm is used to generate them.

The MSDN documentation tells us that Random is fast and insecure, and RNGCryptoServiceProvider is slow and secure. That is, it's reasonable to assume someone could put in enough effort to predict the outcome of Random, but not of RNGCryptoServiceProvider.

If you saw a long enough sequence of GUIDs, would it be possible to predict futures ones? If so, how many would you need to see?

[In our particular case there were physical security checks later on - you had to present the passport you used to buy your ticket - so it wouldn't have been too bad if someone had guessed someone else's GUID, so we didn't sweat it at the time. The convenience of using the GUID as a database key made it a useful datatype to use.]

---

Edit:

So the answer is "not enough".

Using 0xA3's answer below, and following links from the question he linked to, the following code will generate a cryptographically random GUID that's valid by Section 4.4 of RFC 4122:

static Guid MakeCryptoGuid()
{
    // Get 16 cryptographically random bytes
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    byte[] data = new byte[16];
    rng.GetBytes(data);

    // Mark it as a version 4 GUID
    data[7] = (byte)((data[7] | (byte)0x40) & (byte)0x4f);
    data[8] = (byte)((data[8] | (byte)0x80) & (byte)0xbf);

    return new Guid(data);
}

This produces GUIDs much more slowly than Guid.NewGuid(), but with 122 bits of "very random" data, they are safely unpredictable.

Of course, any cryptographically random text would have done for a ticket number, but GUIDs are pretty handy. :-)

As with other version 4 GUIDs there's no absolute guarantee of uniqueness, but the odds are impressive. So long as you have fewer than 326,915,130,069,135,865 (i.e. sqrt(-22^122ln(0.99))) GUIDs in play simultaneously, you can be more than 99% sure there are no collisions. Put another way: if like mine your application will have overflow errors all over the place if you have more than int.MaxValue of pretty much anything, you can be more than 99.9999999999999999% sure of no collisions (i.e. e^-(((2^31-1)^2)/(2*2^122))). This is about a thousand times more sure than you can be that a meteorite won't wipe out most of life on Earth within one second of the application going live (i.e. one per 100 million years).

UUIDs/GUIDs are specified by RFC4122. Although Version 4 UUIDs are created from random numbers Section 6 makes an explicit statement on security:

> 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.

A good discussion of the randomness of GUIDs can also be found in this question:

> How Random is System.Guid.NewGuid()? (Take two)

This is a perfect example of how not to think about a security issue. Unfortunately it is how a majority of developers think about security...

> ...potentially worth around > $3,000,000...are they secure enough > ?...

No. A lot of resources can be brought to bear on a problem that has a possible payout of $3M per ticket. That kind of money could attract people with a lot of resources...some very serious people. Using anything that relies on a general purpose random number generator is not very random...thus not very secure. It is more obfuscation than cryptography.

> ...physical security checks...had to > present the passport used...

Again, with that amount of cheddar on the line... I can get you any passport you'd like.

> ...possible to predict futures > ones?...

Yes. The question is...How long would it take ? ...per some unit of processing work.

> ...If so, how many would you need to > see ?...

That depends on what I know about their creation...OS, CPU, etc...and I'm sure I can find somebody at your firm that would be interested in providing some information in exchange for say...$100,000 or, more likely, less.

-- This may all seem a bit overly dramatic, but you are talking about a serious amount of money and it should be protected with a serious amount security. You need a security consulting firm that can help you choose the encryption package you buy for this. Your client should be able to help via their risk management department or their insurer....If not, get your own lawyer...the one you should already have.

Of course, there is very little chance that anything would go wrong with the GUID scheme but if did go all pear shaped...How are you going to tell all those lawyers that your security plan was top notch and they should look elsewhere ?...Trust me, you do not want to be holding the bag if something goes wrong. That would really suck for you.

Edit: On teedyay's comment...

Obtaining a "Get Out of Jail Free" card from the client is always a good idea. If you tell them "We can make it secure in the case of trivial attacks...but we are not a security or cryptography firm." then your job is done and the client is left holding the bag.

GUIDs are generated by a very well known algorithm. There is no randomness built-in as well known values such as network card ID's and timestamps are used to generate them.

They should never be used as a means of security.

EDIT

It appears newer version of the GUID/UUID algorithm no longer use hardware address for parts of their values and instead use pseudo-random numbers. But these are not truly random and still should not be used for security critical applications.

Functionally speaking

People say that GUID / UUID is not safe. Is it true?

C#'s GUID is a 128-bit integer and it means a lot of combinations: 170,141,183,460,469,231,731,687,303,715,884,105,727

But let's say our attacker uses force brute and each attempt takes 0.1 seconds, you know that we are talking a lot of time, so nobody will even dare to do that.

But let's say GUID is not "safe", so the entropy is reduced to, let's say to 32-bits ( 2,147,483,647) it means a force brute attack could last

2,147,483,647 x 0.1 second / 60 / 60 /24 = 2400 days. So, even a 32-bit GUID is safe (but it could generates collisions).

We could argue that a GPU or a super-computer could generate that number of combinations in a snap of seconds. Yes, but generating a list of values means nothing if they can't be tested.

Also, a force brute attack is easily identifiable, it's what we call a DDOS and there are several ways to mitigate it.

Mathematically, GUID is safe but the mathematical world and the real world are too different.