4 ms·

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

by 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.
- mmalone 11y ago
  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!).
  - zimbatm 11y ago
    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.
  - spronkey 11y ago
    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.
hueving 11y ago
>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.
- deleted 11y ago
  [deleted]
- mmalone 11y ago
  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.
  - michaelmior 11y ago
    > with less entropy What makes you believe this is the case?
    - mmalone 11y ago
      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.
NicoJuicy 11y ago
* 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 ...)
- iopq 11y ago
  I like gfycat URLs like DigitalGloomyFrenchbulldog because they're easier to remember and type
geon 11y ago
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.

by mmalone 11y ago

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.

mmalone 11y ago
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!).
- zimbatm 11y ago
  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.
- spronkey 11y ago
  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.

hueving 11y ago

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

deleted 11y ago
[deleted]
mmalone 11y ago
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.
- michaelmior 11y ago
  > with less entropy What makes you believe this is the case?
  - mmalone 11y ago
    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.

NicoJuicy 11y ago

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

iopq 11y ago
I like gfycat URLs like DigitalGloomyFrenchbulldog because they're easier to remember and type

geon 11y ago

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.