Is it possible to create a 128-bit UUID from a weak entropy source?

Question

I am looking at a seemingly popular piece of JavaScript code to generate a UUID which is supposed to be a 128-bit number:

function uuidv4() {
  return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random() * 16 | 0, v = c == 'x' ? r : (r & 0x3 | 0x8);
    return v.toString(16);
  });
}

This uses the browser's Math.random(). To dissect this further, it seems to be mostly replacing each x character in the string with a separate call to the Math.random API to create a hex digit (4 bits) e.g.:

function getRandomHexChar() {
    let randomChar = Math.random();       // 0.6429364007765519
    randomChar = randomChar * 16;         // 10.28698241242483
    randomChar = randomChar | 0;          // 10
    randomChar = randomChar.toString(16); // a

    return randomChar;
}

For our application I assume we absolutely need the UUID to be unique or probably bad things could happen if it is repeated. However the thing I would like to know is if it needs to use a cryptographically secure PRNG to guarantee it to be unique?

Apparently Math.random once returned random numbers limited to $2^{32}$. It is a bit better in Chrome, Firefox and Safari now though, they are able to return numbers limited to $2^{128}$ (but it now uses xorshift128+ algorithm which is not cryptographically secure). Also this is certainly not 'all' browsers so maybe it's safe to estimate Math.random only gives $2^{32}$ bits of entropy.

So I guess my question really boils down to this: With repeated calls to Math.random (i.e. a non-cryptographically secure 128 bit RNG or with perhaps $2^{32}$ bits of entropy) like this e.g. getRandomHexChar() + getRandomHexChar() + ... to concatenate 4 bits of pseudo randomness at a time until you get a 128 bit number, will this really give a safe unique UUID of 128 bits? Or is the entropy in that resulting UUID much lower?

Answer 1

The entropy will never go higher than the amount you put in. So if you require 128 - 4 = 124 bits and you input 32 bits, you can rest assured that the amount left is at most 32 bits. It's really that simple. And in that case, there is a high likelihood of collisions due to the birthday bound.

Now generally you will likely not find dupes during regular use, but an adversary may simply try and see if a collision can be made. In that case all bets are off, because in the end the RNG is simply not cryptographically secure.

I'd also be concerned about the entropy source. If it is 32 bits taken from the system clock then it is really not entropy at all, to name just one common option.

---

Try and avoid generating UID's at the client side entirely.

If this is really something you require then there is subtle crypto now for JavaScript in browsers, use that cryptographically secure random number generator instead. Beware of dragons though: "There is no minimum degree of entropy mandated by the Web Cryptography specification." ... this might especially be an issue on non-standard / embedded browsers.

Answer 2

First off UUIDs do not have 128 bits of entropy. There are 128 bits in a UUID, but in a "variant 1 version 4" UUID, six of those bits are fixed, so you have at best 122 bits of entropy. Still that is sufficient to make accidental collisions unlikely unles youhave a ridiculous number of items.

IMO you have a few issues here.

1. If the random number generator only has 32 bits of entropy, then the probability of collision is non-negligable even for relatively small numbers of UUIDs. OTOH if the random number generator has 128 bits of state and is well seeded this is not really an issue.
2. Since the UUIDs are being generated client side, you have to consider the possibility that a malicious client may deliberately modify the generator to generate colliding UUIDs.
3. If your user uses a non-secure PRNG, then an attacker given a couple of UUIDs generated by a user may be able to reverse engineer the PRNG state, and hence predict other random numbers generated by that user. This may be an issue if you for-example use UUIDs as record IDs and use secrecy of the record ID as a means of controlling access (see for example "unlisted" videos on youtube).