1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Anecdotal, but I have personally seen UUID collisions in a production web app due to the use of Math.random. Request tracing IDs were being generated client side, and with 40k concurrent users we did see collisions within days of launching the feature. Likely because Math.random is seeded with the system time in many browsers. Switching to crypto.getRandomValues for supporting browsers fixed the issue. $\endgroup$ – rmalayter Jul 30 at 23:32
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.