45

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?

ant-depalma
  • 2,006
  • 4
  • 26
  • 34
  • 2
    see: [How good is Java's UUID Random UUID?](http://stackoverflow.com/questions/2513573/how-good-is-javas-uuid-randomuuid) – wkl Sep 23 '11 at 17:40
  • `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. – Vineet Reynolds Sep 23 '11 at 17:52
  • @VineetReynolds - I think OP meant true randomness. Also, there are more sources of randomness than just PRNG's. – Ishtar Sep 23 '11 at 18:10
  • 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. – ant-depalma Sep 23 '11 at 18:12
  • @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. – Vineet Reynolds Sep 23 '11 at 18:18

3 Answers3

35

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

Robert
  • 39,162
  • 17
  • 99
  • 152
  • 1
    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 Sep 23 '11 at 18:14
  • 3
    @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? – alwinc Dec 21 '12 at 12:48
  • 2
    @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. – Robert Dec 22 '12 at 09:09
3

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.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
2

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.

MarianP
  • 2,719
  • 18
  • 17