Hacker News Reader

Comment by UnoriginalGuy | Hacker News Reader

This is actually a solved problem already on most underlying operating systems, it just hasn't filtered down into the Javascript-world. On Windows you want a GUID and on UNIX-like OSs you want a UUID.

GUIDs and UUIDs are guaranteed to be unique not simply because of their length, but also how they're constructed (MAC address, timestamp, and a random element).

So even if the random number generator does loop back around, it still won't ever generate the same GUID/UUID even on the same hardware, and on other hardware it is more unlikely yet still (due to MAC address).

So the question is: Why isn't GUID/UUID generation not available to Javascript? It works extremely well and is used for exactly this type of scenario.

View on HN

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.

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.

Using UUIDs does not magically solve your problem of using a bad PRNG. RFC 4122 imposes no guarantees on how random the V4 UUIDs really are. You'll still need to verify yourself if the method you use to generate them is good enough for your application. Especially if you need your UUIDs to be unpredictable. It even says so explicitly:

   Do not assume that UUIDs are hard to guess; they should not be used
   as security capabilities (identifiers whose mere possession grants
   access), for example.  A predictable random number source will
   exacerbate the situation.

So many people use UUIDs for session cookies, where the unpredictability is vital.

> but also how they're constructed (MAC address, timestamp, and a random element).

Who uses UUID1? The vast majority are UUID4 and they are pure random.

I do. V1 UUIDs, due to the generation via timestamps makes them sortable. This is a obvious boon for DB indexing.

Specifically with Postgres I use the v1mc version as it provides the added benefit of using "a random multicast MAC address instead of the real MAC address of the computer"[0].

[0] http://www.postgresql.org/docs/9.4/static/uuid-ossp.html

Because they leak details about the user's machine?

True of UUID1s, unless you bastardize them and use something other than MAC address. You could do UUID4s without leaking info.

Those are just random numbers, back to square 1.

Then you loop back to needing a quality PRNG, which is exactly TFA's issue.

UUID4 requires a good CSPRNG. Random isn't magic, you have to do the work.

It seems as though these IDs are generated on the server. Leaking the MAC address of the server seems inconsequential to me.

Leaking the MAC address of the user's machine is also inconsequential.

> So even if the random number generator does loop back around, it still won't ever generate the same GUID/UUID even on the same hardware, and on other hardware it is more unlikely yet still (due to MAC address).

True, but in crypto that's not the only thing you care about. Usually you want random numbers that are both hard to replicate and, and this was missing, hard to predict. MAC & and timestamp do nothing to reduce the predictability of the RNG.

Also, going back to the speed debate: There are usecases where you don't care about these aspects at all and the cited perlin noise, often used in graphics, is one of them. If anything I probably want the noise to be predictable so my preview in Cinema 4D or whatever looks exactly like the rendered result.

Stuff gets dangerous when implementors ignore the tradeoffs and want to make things go fast without knowing the implications.

It is also a solved problem in javascript, there are plenty of UUID (and other types of id) generators available, plus native csprng functions.

Reply on news.ycombinator.com