9 ms·

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 GU

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.

dtf 11y ago
Because they leak details about the user's machine?
- mmalone 11y ago
  True of UUID1s, unless you bastardize them and use something other than MAC address. You could do UUID4s without leaking info.
  - fulafel 11y ago
    Those are just random numbers, back to square 1.
  - masklinn 11y ago
    Then you loop back to needing a quality PRNG, which is exactly TFA's issue.
  - dbenhur 11y ago
    UUID4 requires a good CSPRNG. Random isn't magic, you have to do the work.
- michaelmior 11y ago
  It seems as though these IDs are generated on the server. Leaking the MAC address of the server seems inconsequential to me.
  - asuffield 11y ago
    Leaking the MAC address of the user's machine is also inconsequential.
mmalone 11y ago
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.
- rnovak 11y ago
  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.
the_mitsuhiko 11y ago
> 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.
- darrhiggs 11y ago
  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 http://www.postgresql.org/docs/9.4/static/uuid-ossp.html
xnyhps 11y ago
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.
ricardobeat 11y ago
It is also a solved problem in javascript, there are plenty of UUID (and other types of id) generators available, plus native csprng functions.
svckr 11y ago
> 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.

dtf 11y ago

Because they leak details about the user's machine?

mmalone 11y ago
True of UUID1s, unless you bastardize them and use something other than MAC address. You could do UUID4s without leaking info.
- fulafel 11y ago
  Those are just random numbers, back to square 1.
- masklinn 11y ago
  Then you loop back to needing a quality PRNG, which is exactly TFA's issue.
- dbenhur 11y ago
  UUID4 requires a good CSPRNG. Random isn't magic, you have to do the work.
michaelmior 11y ago
It seems as though these IDs are generated on the server. Leaking the MAC address of the server seems inconsequential to me.
- asuffield 11y ago
  Leaking the MAC address of the user's machine is also inconsequential.

mmalone 11y ago

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.

rnovak 11y ago
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.

the_mitsuhiko 11y ago

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

darrhiggs 11y ago
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 http://www.postgresql.org/docs/9.4/static/uuid-ossp.html

xnyhps 11y ago

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.

ricardobeat 11y ago

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

svckr 11y ago

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