Are Java random UUID's predictable?

Question

I would like to use a cryptographically secure primary key for sensitive data in a database - this cannot be guessable/predictable and it cannot be generated by the database (I need the key before the object is persisted).

I understand Java uses a type 4 UUID with a cryptographically secure random number generator, however I know the UUID isn't completely random so my question is how safe is it to assume that uuids cannot be predicted from a set of existing ones?

Solution 1

Well if you want to know how random a UUID is you have to look onto the source.

The following code section is taken from OpenJDK7 (and it is identical in OpenJDK6):

public static UUID randomUUID() {
        SecureRandom ng = numberGenerator;
        if (ng == null) {
            numberGenerator = ng = new SecureRandom();
        }

        byte[] randomBytes = new byte[16];
        ng.nextBytes(randomBytes);
        randomBytes[6]  &= 0x0f;  /* clear version (set highest 4 bits to zero)       */
        randomBytes[6]  |= 0x40;  /* set to version 4     */
        randomBytes[8]  &= 0x3f;  /* clear variant (set highest 2 bits to zero)       */
        randomBytes[8]  |= 0x80;  /* set to IETF variant  */
        return new UUID(randomBytes);
    }

As you can see only 2 of 16 bytes are not completely random. In the sixth byte you lose 4 of 8 bits and on byte 8 you loose 2 bits of randomness.

Therefore you will get an 128 bit value with 122 bit randomness.

The only problem that may arise from the manipulation is that with a high chance your data can be identified as an UUID. Therefore if you want to hide it in other random data this will not work...

Solution 2

If you want to generate a secure random key, I suggest you use SecureRandom. This can generate a key of any number of bits you require. Its slower than Random, but much more secure.

Solution 3

I have always thought that the 'cryptographically secure random number generator', (actually 'cryptographically strong pseudo random number generator') Javadoc note answers this.

http://download.oracle.com/javase/1,5.0/docs/api/java/util/UUID.html#randomUUID()

From What Wikipedia says http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator such prediction would be a non-polynomial algorithm.

If you need something 'truely' not just 'pseudo' random, you need to use something external, a hardware noise generator, random points generated after moving a mouse,...

EntropyPool seems to be helping with that, have not tried it yet http://random.hd.org/ The way I understand it, it let's you download some real world noise and use it in your Java app. It is not connected to java.util.UUID api, however, could probably be plugged in using the nameUUIDFromBytes (or other?) method.

Would be cool if you let us know which way you decided to go.

Comments

[wkl]

see: How good is Java's UUID Random UUID?

[Vineet Reynolds]

however I know the UUID isn't completely random - there is no such thing as completely randomm, and I don't know how you have come to this conclusion (certainly looks unfounded). All UUID generators have to work on the output of a PRNG that has it's own source of randomness. And the PRNG used by most JVMs (SHA1PRNG) is certainly good enough to be used in the SSL protocol stack.

[Ishtar]

@VineetReynolds - I think OP meant true randomness. Also, there are more sources of randomness than just PRNG's.

[ant-depalma]

I've taken a look at that other post, but it doesn't matter much about uniqueness across other applications. Any random number generator can generate the same number for two apps coincidentally but that doesn't speak much about its predictability within one domain.

[Vineet Reynolds]

@Ishtar, there is no such thing as true randomness when discussing real random number generators. That's why they're referred to as pseudo RNGs, because the number can always be traced back to a definite instant in time. Besides, a PRNG can use several sources of randomness (I think you're confusing PRNGs with sources of randomness). SHA1PRNG is not restricted to a few or one source.

[ant-depalma]

Thanks for interpreting the source, I think this is sufficient for my purposes in terms of its randomness. One less thing to worry about!

[ant-depalma]

Take a look at the source code for UUID a few posts up, its already using a secureRandom.

[Jason Dean]

It is using SecureRandom, but it is removing some of the randomness. Just sayin...

[Vishy]

@user842800, UUID uses 121 bit of randomness, this may be exact what you wanted. However if you want more or less you can use SecureRandom directly.

[alwinc]

@Robert This is great, but I don't understand the statement The only problem that may arise from the manipulation is that with a high chance your data can be identified as an UUID. Therefore if you want to hide it in other random data this will not work.... Can you please elaborate?

[Robert]

@alwinc It is difficult to answer your question because it depends on how you want to use the UUID. If someone e.g. use a UUID for whatever reason as AES-128 key he would loose 6 bit of key-length without noticing it. That might simplify further crypto attacks. The possibility to distinguish between true random data and an UUID as you mentioned is also a topic but I can not imagine a case where this is a problem.