21

Note that this is not my application, it is an application I am pentesting for a client. I usually ask questions like this on https://security.stackexchange.com/, however as this is more programming related I have asked on here.

Granted, RFC 4122 for UUIDs does not specify that type 4 UUIDs have to be generated by a Cryptographically Secure Pseudo Random Number Generator (CSPRNG). It simply says

Set all the other bits to randomly (or pseudo-randomly) chosen values.

Although, some implementations of the algorithm, such as this one in Java, do use a CSPRNG.

I was trying to dig into whether Microsoft's implementation does or not. Mainly around how .NET or MSSQL Server generates them.

Checking the .NET source we can see this code:

 Marshal.ThrowExceptionForHR(Win32Native.CoCreateGuid(out guid), new IntPtr(-1));
 return guid;

Checking the CoCreateGuid docco, it states

The CoCreateGuid function calls the RPC function UuidCreate

All I can find out about this function is here. I seem to have reached the end of the rabbit hole.

Now, does anyone have any information on how UuidCreate generates its UUIDs?

I've seen many related posts:

The first of which says:

A GUID doesn't make guarantees about randomness, it makes guarantees around uniqueness. If you want randomness, use Random to generate a string.

I agree with this except in my case for random, unpredictable numbers you'd of course use a CSPRNG instead of Random (e.g. RNGCryptoServiceProvider).

And the latter states (actually quoted from Wikipedia):

Cryptanalysis of the WinAPI GUID generator shows that, since the sequence of V4 GUIDs is pseudo-random; given full knowledge of the internal state, it is possible to predict previous and subsequent values

Now, on the other side of the fence this post from Will Dean says

The last time I looked into this (a few years ago, probably XP SP2), I stepped right down into the OS code to see what was actually happening, and it was generating a random number with the secure random number generator.

Of course, even if it was currently using a CSPRNG this would be implementation specific and subject to change at any point (e.g. any update to Windows). Unlikely, but theoretically possible.

My point is that there's no canonical reference for this, the above was to demonstrate that I've done my research and none of the above posts reference anything authoritative.

The reason is that I'm trying to decide whether a system that uses GUIDs for authentication tokens needs to be changed. From a pure design perspective, the answer is a definite yes, however from a practical point of view, if the Windows UuidCreate function does infact use a CSPRNG, then there is no immediate risk to the system. Can anyone shed any light on this?

I'm looking for any answers with a reputable source to back it up.

Community
  • 1
  • 1
SilverlightFox
  • 32,436
  • 11
  • 76
  • 145
  • 1
    Bizarre question. Suppose somebody says "yes". Are you going the base the security of your system on what a stranger on the Internet tells you? Call Microsoft. – Hans Passant Feb 12 '16 at 16:06
  • 2
    No, I'm asking for some evidence one way or the other. e.g. [see my comment here](http://stackoverflow.com/questions/816882/how-to-predict-the-next-guid-from-a-given-guid/817150#comment58381222_817150). – SilverlightFox Feb 12 '16 at 16:08
  • Get Windbg and step into the call and see what it does. Then for at least one os at one point in time you'll know. Guids still won't be suitable for what you're using them for, but you'll have at least scratched this itch. – Will Dean Feb 13 '16 at 19:20
  • The main issue here is your misappropriation of GUIDs for a purpose for which they are not fit. The implementation is a detail and no matter what the current implementation, it may be arbitrarily subjected to change at any moment. – spender Feb 15 '16 at 17:17

1 Answers1

20

Although I'm still just some guy on the Internet, I have just repeated the exercise of stepping into UuidCreate, in a 32-bit app running on a 64-bit version of Windows 10.

Here's a bit of stack from part way through the process:

> 0018f670 7419b886 bcryptPrimitives!SymCryptAesExpandKeyInternal+0x7f
> 0018f884 7419b803 bcryptPrimitives!SymCryptRngAesGenerateSmall+0x68
> 0018f89c 7419ac08 bcryptPrimitives!SymCryptRngAesGenerate+0x3b
> 0018f8fc 7419aaae bcryptPrimitives!AesRNGState_generate+0x132 
> 0018f92c 748346f1 bcryptPrimitives!ProcessPrng+0x4e 
> 0018f93c 748346a1 RPCRT4!GenerateRandomNumber+0x11
> 0018f950 00dd127a RPCRT4!UuidCreate+0x11

It's pretty clear that it's using an AES-based RNG to generate the numbers. GUIDs generated by calling other people's GUID generation functions are still not suitable for use as unguessable auth tokens though, because that's not the purpose of the GUID generation function - you're merely exploiting a side effect.

Your "Unlikely, but theoretically possible." about changes in implementation between OS versions is rather given the lie by this statement in the docs for "UuidCreate":

If you do not need this level of security, your application can use the UuidCreateSequential function, which behaves exactly as the UuidCreate function does on all other versions of the operating system.

i.e. it used to be more predictable, now it's less predictable.

Will Dean
  • 39,055
  • 11
  • 90
  • 118
  • 4
    Thanks for taking this trouble. To back you up with some documentation, 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 say you could call them cryptographically secure -- at least to the extent of the 122 bits of entropy they provide. – Jordan Rieger May 29 '18 at 00:38
  • @JordanRieger I really wish you had put that in an answer. "Microsoft's documentation says they do" seems like an equally good (but more authoritative) answer than "I used a debugger and looked" – Jaykul Nov 20 '18 at 18:09
  • 1
    @Jaykul I actually have written more than one such answer on this topic, just not on this particular question. You can see them if you check the related questions that the OP linked. Since the question is dealing with the concrete risk of treating Microsoft GUIDs as cryptographically random, and the answer is correctly finding that risk to be low, there wasn't any need for an additional answer when a comment would suffice. But on other questions, when the top answered implied that GUIDs were unsafe, I have offered a full answer as a counterpoint. – Jordan Rieger Nov 22 '18 at 17:31