.net – 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).