Great point / good question. Here's why we didn't just use UUIDs:
* UUID generation still requires a good (CS)PRNG and should be vetted the same way you'd vet a (CS)PRNG.
* UUIDs are one-size-fits-all 36 character base-16 encoded strings. If you want a short random identifier that you can use in a URL (that people might need to type on a phone or something) they're not ideal. Re-encoding them and/or truncating them is as hard and error prone as just generating the randoms yourself.
* Researching a good UUID library and maintaining a dependency is harder than vetting the 10 lines of code required to do it yourself. Without a trusted standard library solution it's unclear which library to use (maybe not as true today as it was a couple years ago when this happened)
If UUIDs were available in the Javascript standard library we probably would have used them in some of the places that we currently use our own identifiers. We do use UUID4s in our Java services, for instance.
I'm guessing that UUIDs aren't standardized because the standards process is browser-centric and it's low priority in that context... but that's just a guess.
Edit: formatting.
Two questions (not trying to be argumentative or snarky):
> we like using randomly generated identifiers.
Why? Why do your identifiers need to be cryptographically secure at all? Why do they even need to be random? Unless you're using them AS KEYS (your use of Math.random() suggests you aren't), "cryptographically secure" doesn't even have a valid context.
It seems like UNIQUE would suffice, which brings me to:
> Researching a good UUID library and maintaining a dependency is harder than vetting the 10 lines of code required to do it yourself
Well.....except that if you had done the former, you wouldn't have had to analyze collisions because, you know, they wouldn't have happened.
And if you're not using identifiers AS KEYS (which would be horrible practice anyway, since it's apparently output to the logs), why does the library need to be kept "up to date"? Seems as long as its generating unique id's, you're good to go.
Also, I don't understand, if you're using Node.JS and server side javascript, why couldn't you just build a dead simple add-on/module in C++ that makes a direct call to libuuid? (and by using a dylib, that would stay up to date as long as you patch your servers).
I mean the math was definitely an interesting read, but it seems like it was all for naught.
Again, I didn't want to come off as rude or anything, I just happen to agree with the top level comment.
Not rude at all. They're actually all good questions.
> Why? Why do your identifiers need to be cryptographically secure at all?
They don't have to be cryptographically secure. They just need to be unique. Using random identifiers are easier to generate than deterministic/semi-sequential identifiers which would require some form of coordination, which is a pain in the ass and a point of failure. We switched to a cryptographically secure PRNG because it is higher quality than the non-CS alternative.
> Well.....except that if you had done the former, you wouldn't have had to analyze collisions because, you know, they wouldn't have happened.
You're assuming a UUID library that didn't just use Math.random() under the hood. Many libraries at the time of this incident did. Either way it would have been work to find one we could trust, vs. 10 lines. Also, UUIDs are 36 characters and not suitable for some use cases like short identifiers that will appear in URLS (which might need to be typed oh phones, etc).
> why does the library need to be kept "up to date"?
We would have had to update it when someone realized it was using Math.random() under the hood, for instance. In general there's a certain amount of maintenance involved with any dependency.
> why couldn't you just build a dead simple add-on/module in C++
Because 10 lines of Javascript vs. that.
> it was all for naught.
The random identifier generation was relatively irrelevant / just a fun narrative around the real story, which was about the subtleties of PRNGs, doing your homework, and Math.random() being crappy. If you don't think that use case is legitimate, that's fine. There are lots of other use cases where Math.random() is problematic, like shuffling an array (for an unbiased shuffle of a length n array you need a cycle length of n!).
What happens if the client changes his code to always issue requests with the same ID ?
Most solutions inject the HTTP header in the frontend reverse-proxy to avoid that kind of issue.
Well, to ensure uniqueness you always need coordination. If using UUIDv1, you need to ensure your MAC addresses are not cloned. UUIDv4, you need to ensure the generated IDs are not duplicated by ensuring you have not generated each ID before. Sounds like you've missed a critical step here.
UUIDv1 is pretty much your best bet here because it's the least pain in the ass. 36 chars are hardly any less suitable for the use cases you mention than 22 chars. UUIDv1 can survive on a poor PRNG, so your reason for updating library isn't really valid. Sure there's a small amount of maintenance, but I'd expect a developer with solid experience and knowledge to almost immediately understand that (even) a 10 line homebaked solution is likely to cause more issues than a standardised algorithm developed specifically for this purpose.
"10 lines of JavaScript" isn't really what you wrote now, is it?
As for your other use cases, CSPRNG! If you need something to be unbiased, a PRNG just doesn't work. In fact, PRNGs pretty much never work for anything that needs anything. They exist for convenience only.
You don't need to check for duplicates with UUI4s if you have a good source of entropy. I'm not sure where you're getting your information, but here's what Wikipedia has to say, for instance[1]:
"To put these numbers into perspective, the annual risk of a given person being hit by a meteorite is estimated to be one chance in 17 billion,[4] which means the probability is about 0.00000000006 (6 × 10−11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%."
There seems to be some sort of collective delusion that UUIDs magically appear somehow. Most UUID libraries are very small packages that contain code nearly identical to the code we're using. Many of the libraries that existed at the time this problem occurred actually used Math.random() under the hood. Moreover, we need our code to produce variable length identifiers for different use cases. Since we already need it, it's sensible to re-use it for a case where UUIDs might also be used.
In some places (when we're producing much shorter IDs, for instance, or in extremely critical sections of code) we do check the database for duplicates. In our Java-based accounting system we even use UUID1s for transaction IDs. I understand the trade offs. The code in question was being used to generate correlation identifiers for log tracking. The performance hit of checking for dupes would have been a waste.
PRNGs work find for many use cases. Please cite some source or at least give me some reasonable argument to believe otherwise.
[1] https://en.wikipedia.org/wiki/Universally_unique_identifier#...
>Re-encoding them and/or truncating them is as hard and error prone as just generating the randoms yourself.
Feed the whole thing into sha256 and take the last X bytes where X is the amount you need for your shortener. If you can show that the last X bytes of sha256 have a chance for collision due to input, there is a lot of money in it for you. One of the nice things about a cryptographic hash is that all of the output has to be completely unpredictable based on the input.
Exactly, it's as hard and error prone as generating the randoms yourself. The solution you described requires an analysis of the hash function to determine collision probability, diligence to find a sha-256 implementation (circa a few years ago), review of said implementation, another analysis to figure out your truncation, then a proper implementation resulting in ~the same amount of code, except this time slower and with less entropy.
> with less entropy
What makes you believe this is the case?
You're generating a random number (the UUID) then you're hashing it. It can't possibly have more entropy, and there's a chance two inputs to the hash will collide thus reducing entropy.
Hashing a counter is actually a variety of CSPRNG. Basically you're re-seeding a hash-based PRNG with whatever PRNG the UUID code uses at each run. It's well known that an PRNG cannot have more entropy than its seed. Hence, it will at best have the same entropy, and probably have slightly less.
* UUIDs are one-size-fits-all 36 character base-16 encoded strings. If you want a short random identifier that you can use in a URL (that people might need to type on a phone or something) they're not ideal. Re-encoding them and/or truncating them is as hard and error prone as just generating the randoms yourself.
Google's shortener is also not very good in a url ( as implementation of unique short identifier).
Any solution that has it possible to have an I ( capital i) or l ( lowercased l) in the same sentence is flawed due to various fonts in any app where you can use an url ( SMS, facebook, Whatsapp, browsers, nokia 3310 ...)
I like gfycat URLs like DigitalGloomyFrenchbulldog because they're easier to remember and type
I don't know how much has changed in the last 2 years, but there's a `uuid` npm package that uses the `crypt` built in module on Node, but `Math.random` in the browser.