16 ms·

Math.random in V8 is broken

310 points by r0muald 11y ago

mmalone 11y ago
tl;dr: the algorithm powering V8's Math.random() is very poor quality. For many use cases you can't safely pretend its output is actually random. Don't use it for anything non-trivial that you care about. It should probably be fixed. In the meantime, use crypto.randomBytes() or crypto.getRandomValues() instead.
- kayamon 11y ago
  I think the real lesson here is that if your application is dependent on the exact behavior of an undefined algorithm, you probably should fix your application.
  - mmalone 11y ago
    It wasn't dependent on exact behavior. It was dependent on a sensible general contract. We rely on sensible implementations of general contracts all over the place in software development. We did make an incorrect assumption that the PRNG (created by Google, who has a good reputation, and in what is probably the most popular software in the world) was high quality. That was a mistake, and we should have done more homework. However, there's no reason why the Math.random() implementation in V8 should _not_ be good enough to not have to worry about.
    - asdfaoeu 11y ago
      It was dependent on it being a CSPRNG which it wasn't. Math.random is designed for things like games and animations where randomness isn't critical and performance is important.
      - johncolanduoni 11y ago
        Actually CSPRNGs are slightly worse if you are more worried about distribution than predictability (he mentions this in the article). If you are using it in a context where a hostile attacker cannot gain anything via predicting or manipulating the generated numbers, then for birthday-paradox type resistance an alternate non-CS PRNG, like those typically used for simulations, is more appropriate. However when you're using JavaScript, it's likely the natively implemented CSPRNG will be faster than a custom "faster" PRNG implemented in JavaScript.
      - seba_dos1 11y ago
        No, it wasn't. Read the article again. Assumption made was on Math.random being high quality PRNG. Being cryptographically secure is completely unrelated.
        Dylan16807 11y ago
        Medium quality, really. But it was neglected and bad for no reason, no tradeoffs.
    - deleted 11y ago
      [deleted]
    - pacaro 11y ago
      This is a tricky answer. The default random function in many environments is poor (see other examples given above and below), if you are generating a unique id using a PRNG and think in terms of the birthday paradox, then you should also be concerning yourselves with the quality of the random generator. While it is unreasonable to expect every developer to know the ins and outs of a deeply technical issue, defaulting to using a known good (enough) algorithm like MT over making an assumption about the quality of an unknown algorithm (unknown at least until you looked into the source code) just because it came from google is poor engineering (IMHO) The analysis in this article was great engineering - something that in my experience often happens after poor engineering... YMMV
  - deleted 11y ago
    [deleted]
swang 11y ago
Curious why they aren't using hardware RNGs?
- pcwalton 11y ago
  Too slow.
netheril96 11y ago
Given that browser JS has no way to interface with /dev/urandom, I think it is a mistake for V8 not to make the only random number generator available to browser JS secure by default. Of course, on Node.js that is a different issue.
- asdfaoeu 11y ago
  What about https://developer.mozilla.org/en-US/docs/Web/API/RandomSource/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/RandomSourc... ?
  - netheril96 11y ago
    Learned a new thing today. Thanks.
nodesocket 11y ago
The challenge of "randomness" is overlooked and leads to security issues more than most people realize. For example in php, the `rand()` function documentation (to their credit) has a big warning that the function is not cryptographically secure. When in doubt, use unix, and <updated>/dev/urandom</updated> Also, here is a command (to my knowledge secure) which generates a nice random 20 length alphanumeric: LC_CTYPE=C < /dev/urandom tr -dc A-Za-z0-9 | head -c20
- admax88q 11y ago
  Use /dev/urandom, not /dev/random. There are no security concerns with /dev/urandom
  - jzd 11y ago
    this. also /dev/random blocks and it can be really slow
  - rst 11y ago
    Here's a writeup of a serious security flaw traced directly to the use of /dev/urandom instead of /dev/random: https://factorable.net/ https://factorable.net/ In brief, wifi routers need to generate unique crypto keys. The programmers started off using /dev/random, observed that blocking, and switched to /dev/urandom. The problem was that they were generating the keys at first boot, before any entropy had accumulated, with the result that many, many devices wound up with similar or identical keys.
    - derefr 11y ago
      Pedantic version, then: use /dev/urandom unless your software is itself part of the OS's boot sequence.
      - comex 11y ago
        What is the definition of "part of the OS's boot sequence"? In the factorable.net paper[1], a test system didn't generate 192 bits of entropy until 66 seconds(!) after boot. The problem was apparently exacerbated by Linux not mixing the entropy into the /dev/urandom pool at all until that threshold was reached, but even if it started doing so immediately, standard server processes like ssh would still start up long before there was enough entropy to make urandom sufficiently unpredictable. Sure, this is something of an extreme case... and as mentioned in the paper, there are various tools used on Linux to save a random seed to disk, so maybe the OS should ensure that happens before it starts any other services... but software that responds to an easy-to-make configuration mistake by silently behaving insecurely is the polar opposite of good security design. The right answer is Linux's new getrandom syscall, whose default mode "blocks if the entropy pool has not yet been initialized", but thereafter acts like /dev/urandom. But on systems where that syscall is not available, I'm skeptical that using /dev/urandom is sane design. [1] https://factorable.net/weakkeys12.conference.pdf https://factorable.net/weakkeys12.conference.pdf
admax88q 11y ago
No platform in 2015 should even have a poor PRNG. It's pretty sad really. rand() in C, rand() in PHP, Math.random() in JS. Any use case where you want a poor random number generator is a niche use case and you can write your own. We should be secure by default.
- baudehlo 11y ago
  If you want a random entry from an array, Math.random is fine. Anyone who doesn't know that prng's are broken for things like uuids shouldn't be in charge.
  - seanwilson 11y ago
    There's something to be said about having sensible defaults that prevent common mistakes though. Everyone makes mistakes.
    - baudehlo 11y ago
      True. But every language has gone through this issue. Node is particularly vulnerable to weak prng seeding due to relying on forking to support multiple processes. Am I that old and grumpy to expect people to be aware of the history here?
      - seanwilson 11y ago
        I think the size of this thread as well as the existence of blog posts like this means it's a mistake that's always going to be repeated. There's way too many programming gotchas to expect people to keep track of them all. Language support to avoid classes of mistakes is a great idea to me e.g. such as having a good random algorithm by default and a UUID library.
  - johncolanduoni 11y ago
    > Anyone who doesn't know that prng's are broken for things like uuids shouldn't be in charge. Depends on how you're using them. If you only care about collisions, and you're not worried about an attacker trying to manipulate your system, then using a PRNG whose output is well-distributed (read: not necessarily a language's random function) is fine. The problem is most language's default PRNGs are complete crap :( edit: grammar
pygy_ 11y ago
The v8 Math.random() code was changed yesterday[0], maybe in response to this. However, the update appears to be misguided[1]... 0. https://github.com/v8/v8/commit/623cbdc5432713badc9fe1d605c585aabb25876c https://github.com/v8/v8/commit/623cbdc5432713badc9fe1d605c5... 1. https://codereview.chromium.org/1462293002/#msg12 https://codereview.chromium.org/1462293002/#msg12
- je42 11y ago
  I don't understand why they don't go for mersenne twister ?!
  - acqq 11y ago
    MT is "on average" maybe "as fast" but the key is "on average:" depending on the usage pattern it can cost much more. This specific RNG follows a traditional approach (that is, like in C or Java standard libraries) to have one algorithm in the standard library that is "as fast as possible, as bad as possible." Which meant even "just multiply with constant, add another constant, return. Bad? Yes we know." So it's still on the level "it's two multiplies and two-three adds." Traditionally, those who expect some specific properties, like the author of the article, should have actually used the implementation they added to their code (for example MT if it fits) if they ultimately cared about the speed and wanted exactly the properties they know they needed, or if they just didn't care about the speed used some much "slower" but "much better" library. Maybe the tradition can be broken in this specific case, I really don't know which benchmarks define what's acceptable here. Note also that the implementation must be verified, just the fact that there is somewhere some implementation available doesn't even mean that it does what is expected to do. The devil is in the details here.
  - bhickey 11y ago
    I haven't looked closely enough at their choice to evaluate it, but there's a good reason not to use Mersenne Twister. MT is a bad generator. * The state size is 2kb * It fails some rudimentary statistical tests * The output is trivially predicted * It isn't particularly fast * It lacks multi-stream support If you need a CSPRNG use ChaCha20 or AES. For simulation use PCG.
pcwalton 11y ago
My experience with compiler development is that the incentives all align toward making the "default RNG that people go to" as fast as possible to the exclusion of all else, including the quality of the generated numbers. That's because people frequently write benchmarks gated on the speed of random number generation, and those benchmarks usually don't care about the quality of the random numbers. Sometimes those benchmarks get popular, which encourages a race to the bottom in RNG quality. (Similar incentives exist for hash functions, by the way.) Popular RNG-bound benchmarks: * "fasta" from the Benchmarks Game [1] (thankfully, this one mandates use of its own RNG, though it's vulnerable to fast-forwarding as demonstrated in [2]) * "Perlin noise" [3] (almost entirely RNG performance bound) * From SunSpider (this one being particularly relevant to V8): string-validate-input [4], string-base64 [5] [1]: http://benchmarksgame.alioth.debian.org/u64q/fasta-description.html#fasta http://benchmarksgame.alioth.debian.org/u64q/fasta-descripti... [2]: https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src/fasta.rs#L121 https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src... [3]: https://github.com/nsf/pnoise https://github.com/nsf/pnoise [4]: https://www.webkit.org/perf/sunspider-0.9/string-validate-input.html https://www.webkit.org/perf/sunspider-0.9/string-validate-in... [5]: https://www.webkit.org/perf/sunspider-0.9/string-base64.html https://www.webkit.org/perf/sunspider-0.9/string-base64.html
- hajile 11y ago
  The author makes a reasonable point that there are algorithms that are both faster AND higher quality than the one v8 uses. I think not understanding random number generators and the resulting voodoo programming is the real culprit.
- im2w1l 11y ago
  Fast hash functions can be really important for performance of hash sets and maps. In my experience high speed is more important than a low collision rate. That was for primitive types, it may well be different for types where comparison is more costly. And of course if you need protection from algorithmic complexity attacks, then you will need to take that into account.
  - Gankro 11y ago
serge2k 11y ago
> Good PRNGs are designed so that their cycle length is close to this upper bound. Otherwise you’re wasting memory. Why? Good article. I do have a question for the author, why after a huge amount of time writing this post don't you submit a patch to V8?
- tzs 11y ago
  > Why? Good question. As they author noted, k bits of state can support a cycle length of 2^k. You can look at that from the other direction and state it as a cycle length of L requires at least log2(L) bits of state. If your cycle length is L and you are using k bits of state, and k > log2(L), then in theory with a cleverer encoding of state you could save k - log2(L) bits of memory. Whether or not I'd characterize k - log2(L) excess bits as "wasted" memory depends on just how big it is. For instance, suppose someone implemented Mersenne Twister and used twice as many bits as theoretically needed for the cycle length. Typical MT has a cycle length of around 2^20000, so needs 20000 bits of state. Someone doubling that is using an excess of 2500 bytes. On the other hand, the generator the article is about has a cycle length of around 2^60, and so need in theory 60 bits of state. If an implementation doubled that they have an excess of less of 8 bytes. 2500 bytes is enough that if I were implementing I'd probably take a good look at seeing if I could eliminate it, even if it meant making the implementation a little more obtuse. I'd be inclined to consider that 2500 bytes as wasted memory. 8 bytes? That's small enough that even on most embedded systems I'd probably consider clean and clear code to be more important than saving that memory. I'd not be inclined to consider it wasted memory.
  - Gibbon1 11y ago
    I have another reason based on some mucking with simple PNG's a long time ago. Might not apply to more complicated ones[1]. Maximal cycle length generators don't produce degenerate sequences. Meaning I seem to remember ones where they'd have say a sequence of 2^k - 349 and a sequence of 340 and a sequence of 7. Which means they fail badly if seeded incorrectly. [1] Noting an old article I read on FPGA design that said, 'helps to design your state machines so that that illegal states transition to legal ones' So I assume sub 2^k generators exist that don't have sub-sequences.
PhantomGremlin 11y ago
I can't believe you're defending "an incorrect assumption" regarding your previous generator, especially after you wrote a very good article showing how badly wrong you were. Wait, let me restate that. You're Engineering the Disruption of Real Money Gaming and yet you say of some PRNG "no reason the ... implementation ... should not be good enough to not have to worry about"? You're not just wrong, in fact you're "not even wrong", that's how wrong you are. Plus that sentence has three negatives! Jules Winnfield said it better than I could. Riffing from him, what you were doing was, compared to what you should have been doing: ain't the same fuckin' ballpark, it ain't the same league, it ain't even the same fuckin' sport. Here's something I came up with in 60 seconds. It's far better than what you didn't want to worry about: ID Quantique hardware RNG [1] mixed with Intel RdRand [2] Yes, you're right. That's not seed-able, so you can't create a reproducible sequence of values (e.g., for testing). That's an advantage. You want to test, you replace hardware with software. But if you want to disrupt real money gaming you don't use some crappy software in some random library that wasn't designed for the purpose. Once again, I can't believe your defense of how badly you failed was the "reputation" that Google has. Real money is involved and you thought it was OK to rely on some crappy PRNG created by Google? For something that is at the heart of, the quintessence of what you are attempting to accomplish? EPIC FAIL!!! [1] http://www.idquantique.com/random-number-generation/ http://www.idquantique.com/random-number-generation/ [2] https://en.wikipedia.org/wiki/RdRand https://en.wikipedia.org/wiki/RdRand
- PhantomGremlin 11y ago
  Oh, yeah, downvote the messenger instead of respecting the message, which is that a third-rate amateur approach to random number generation just doesn't cut it. This was known as far back as 1999, when similar flaws bedeviled online poker sites.[4][5] Anyone going into the business should have known that from the start, instead of stumbling into it. And definitely shouldn't be trying to retroactively justify such gross incompetence. It's not Google's fault that these guys designed a crappy PRNG into a real money application. There is always the potential for cheating when real money is involved: 1980 Pennsylvania Lottery scandal[1] people added weight to supposedly random ping pong balls scratch lottery tickets weren't random[2] a "trick worked about 90 percent of the time" American Coin Machine Company[3] video poker machines were programmed to cheat players out of jackpots people were cheating online poker as far back as 1999, due to a flawed PRNG[4][5] Those are just a few cases that I could recall. I'm sure there have been many many more. True randomness is just the start in what it takes to prevent this. People who want to "disrupt real money gaming" shouldn't be making amateur mistakes like this. [1] https://en.wikipedia.org/wiki/1980_Pennsylvania_Lottery_scandal https://en.wikipedia.org/wiki/1980_Pennsylvania_Lottery_scan... [2] http://www.wired.com/2011/01/ff_lottery/ http://www.wired.com/2011/01/ff_lottery/ [3] https://www.google.com/search?q=American+Coin+machine+company&ie=utf-8&oe=utf-8 https://www.google.com/search?q=American+Coin+machine+compan... [4] http://www.nytimes.com/1999/09/13/business/compressed-data-e-gambling-software-gave-players-an-edge.html http://www.nytimes.com/1999/09/13/business/compressed-data-e... [5] https://www.cigital.com/papers/download/developer_gambling.php https://www.cigital.com/papers/download/developer_gambling.p...
tlrobinson 11y ago
JavaScript's Math.random (and most languages' default RNGs) is not intended to be cryptographically secure, so I'm not sure "broken" is correct. It's probably random enough for most uses that don't require a CSPRNG. Are there any scenarios where this isn't the case? On the other hand, enough people make this mistake that APIs should just use a CSPRNG for "random()" and offer a "fastRandom()" for those who need speed but not "secure" random.
- panic 11y ago
  Statistical simulations require good randomness (or your simulation might give a wrong result) and high speed but not cryptographic security. See, for example, xorshift* (http://xorshift.di.unimi.it http://xorshift.di.unimi.it), which is efficient and high-quality but not cryptographically secure.
- dahart 11y ago
  My personal definition of random includes the requirement that plotting the bits must look random, and have no visible signs of pattern. The OP did that and you can see patterns. If plotting a picture of a PRNG's bits has visible patterns, I definitely call it completely broken.
emmelaich 11y ago
I you want ids without collisions you should use a monotonically increasing number instead (or as well). I would concatenate utc time in ms to the random number.
- marcus_holmes 11y ago
  or just use UUIDs which are designed for this exact use case
  - vcarl 11y ago
    Exactly, my biggest takeaway is "don't write your own unique ID algorithm." At best it does the same as existing methods, at worst you screw it up and end up here.
  - dap 11y ago
    What kind of UUID? Standard UUIDs of versions 1, 2, and 3 are not really unique enough[1]. Version 4 is basically a random number, so it doesn't help to say "just use that". [1] https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier
    - marcus_holmes 11y ago
      well, I use uuidgen[1]. If I have to generate uuids for multiple servers, then I create a microservice to handle uuid generation, and get it to generate a few held in a buffer so the rest of the system doesn't have to wait for one. [1] http://man7.org/linux/man-pages/man1/uuidgen.1.html http://man7.org/linux/man-pages/man1/uuidgen.1.html
- deleted 11y ago
  [deleted]
- dap 11y ago
  You can't use monotonically increasing numbers from multiple threads (or servers) without either synchronizing (which is terrible for scalability) or using separate prefixes for different threads or servers (in which case you have problems related to sizing and allocating the prefixes). Right? The UTC time + random number idea is interesting, but I'm not sure it's any better than totally random. Say you want a 64-bit unique id. It would take about 42 bits to store a millisecond Unix timestamp, leaving 22 bits for randomness. If you consider the probability that a given id will collide with a previously-generated one: with this scheme, you only need to consider ids generated in the same millisecond, but you only have 22 bits of randomness that can be used to avoid a collision. If you use 64 random bits, you can theoretically collide with ids generated across all of time, but the odds of collision are many orders of magnitude lower. By constraining the first 42 bits to store a millisecond timestamp, every millisecond that goes by removes 2^22 values from the possible id space (regardless of whether they're used). (Besides that, this scheme removes from the space of possible ids all of the millisecond values from before the system was created, which seems like about 2/3 of them, assuming about a 68-year span of values for Unix times, which started 45 years ago.) That's kind of handwavy, so let's do the math. With 22 bits of randomness, the odds of any randomly selected pair of ids generated in the same millisecond colliding is 1/4194304. Assuming independently generated ids, the expected number of collisions after 4194304 milliseconds is 1. So if you have just two threads generating ids once per millisecond, you'd expect a collision in just 70 minutes. That's not great. It's late, though. Maybe my math is wrong?
omarforgotpwd 11y ago
I can't b3liwv3 I just read that entire thing drunk on a Friday night
- mmalone 11y ago
  Hahahahaha. I can't believe that either.
bytesandbots 11y ago
Default PRNGs primary use case is generating session ids for websites with upto 1000s of simultaneous users, not for assigning UUIDs. One should use a combo of a sequential component and a random component. When you have multiple servers, make them combine a sequential component, a unique system identifier and a random number. In this case, you can now use the faster PRNGs which will also give you speed while ensuring uniqueness. Another takeaway from this problem is that the usual method of Multiply-and-floor has a serious flaw of using only the highest bits which may not be good enough for the default fast PRNGs. A better method is to carry forward the remaining bits from the floor using a modulo function. The default fast PRNGs rely on all of their bits and simply throwing away a big chunk is not going to help. Multiply and floor might be more useful in a scenario where you are using better PRNGs. Even then, they are slower and it is not wise to simply throw the hard earned randomness.
- mmalone 11y ago
  Using node IDs and timestamps is just an additional safety factor. Statistically it's not necessary if you have a good generator. Even without those things our target collision probability is less than the expected uncorrectable error bit rate of a HDD. Good PRNGs have equivalent entropy at each bit. With a good PRNG (even a non-CS PRNG) you shouldn't need to mix entropy to do scaling. You should still do rejection sampling[1] if you care about bias. It looks like a good scaling method might be added to the ECMA spec as part of the standard library thanks to some awesome people at Google.[2] [1] https://gist.github.com/mmalone/d710793137ed0d6b8cb4 https://gist.github.com/mmalone/d710793137ed0d6b8cb4 [2] https://twitter.com/mjmalone/status/667806963976134656 https://twitter.com/mjmalone/status/667806963976134656
  - jorangreef 11y ago
    "Using node IDs and timestamps is just an additional safety factor. Statistically it's not necessary if you have a good generator." Sorry, that's just not sensible. You always want to add node IDs and timestamps (provided you hash the final output so as not to leak details about your system) in case your generator fails. Why would you not want another layer of safety? It also helps protect against the case where an attacker might gain something by being able to predict the next ID in the sequence.
bytesandbots 11y ago
For those wondering why not use UUID, most uuid implementation are guaranteed to be unique only when running a single machine. When working on loads of servers without putting any load on a central resource, you can not rely on either uuid or sequential.
- tolmasky 11y ago
  UUID v4 seems to be based on random numbers, so should be "as good" as whatever scheme they were trying to hand roll here. Additionally, the uuid npm library uses crypto.randomBytes, which is cryptographically secure. https://github.com/broofa/node-uuid https://github.com/broofa/node-uuid
  - mmalone 11y ago
    The biggest problem is that they take up a lot of space. Plus you have to find a good library and vet it (there's nothing in the standard library). Or just write 10 lines of straightforward code. If you go and look at node-uuid commit history it, too, used Math.random() back in the day.
- mrighele 11y ago
  This is true for UUID version 4, which is completely random. There are variant that use host-specific information in the process (in fact version 4 is the only one not doing it). [1] This said, I see that often only v4 is implemented, so maybe there are issue with the other variants. [1] https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier
UnoriginalGuy 11y ago
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.
Drdrdrq 11y ago
I think the whole idea of generating random ids is flawed. Why take a chance when there is no need? Just take some machine id (seq. number, MAC), timestamp and a big enough per-machine counter and there can be no collision, guaranteed. No need to use random.voodoo().
- sgk284 11y ago
  Hardware companies have definitely been lazy and reused MAC addresses. But what's worse is that the total space is as low as 48 bits. The probability of a collision is orders of magnitude higher than if you just grab some random bytes out of /dev/urandom and generate a type-4 UUID. For a discussion on the benefits of your approach (a type-1 UUID) vs a random id (a type-4 UUID), check out the wikipedia article: https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier Randomness is great because it doesn't require any synchronization or access to some special token.
  - michaelmior 11y ago
    If you get identical MAC addresses on machines operating the same service, presumably on the same network, you have bigger problems than ID generation.
  - Drdrdrq 11y ago
    Mac addresses should be unique; at least for network cards. The address space of 48bits is not that small. Also, see the warning about entropy in your linked article. There is a difference between mathematical random() and CS random().
- mmalone 11y ago
  It's easier to generate a random identifier and if the generator is good the probability of a collision is lower than the probability that you HDD will fuck up in an uncorrectable way while storing the identifier (as I've pointed out elsewhere in thread). So the answer is that random identifiers are easier to do in a distributed system and, in reality, have the same guarantees.
mckoss 11y ago
Why no mention of window.crypto.getRandomValues?
- Too 11y ago
  Read more carefully...
  - mckoss 11y ago
    Skimming on phone and I missed it-thanks!
- mmalone 11y ago
  It is mentioned! Without the `window.` part though ;).
- anilgulecha 11y ago
  It is mentioned.
NicoJuicy 11y ago
I understand why they want unique generated id's, i don't understand why they just didn't use UUID/Guid, which are way more performant ( string vs int) and less big in size ( 22 bytes vs 16 bytes). Both are created for the same purpose and Guid's are even possible as keys in MS SQL Server (next to the standard autoincremented integer). So it's safe to say that it's pretty reliable.
- cowsandmilk 11y ago
  UUID : 128 bits Bitable's scheme : 132 bits Essentially the same size. They ended up with 132 bits because they use a 6 bit alphabet; 128 is not divisible by 6, so you would need 22 characters of a 6 bit alphabet to represent a UUID, exactly the same as them. (note, the 6 bit alphabet is so identifiers can go in urls; the commonly used uuid hexadecimal representation is a 4-bit alphabet, so there are 32 characters and usually 4 hyphens; so 36 characters in the URL vs. only 22)
gmac 11y ago
I have to say I'm surprised — I thought better of V8 than this. Arguably it's usually going to be preferable to know you're getting the same kind of random numbers across platforms anyway, so a BYO Mersenne Twister is a decent remedy. One is linked in the post, and I have a CoffeeScript one here: https://github.com/jawj/mtwist/blob/master/mtwist.coffee https://github.com/jawj/mtwist/blob/master/mtwist.coffee
deleted 11y ago
[deleted]
jorangreef 11y ago
If you need good quality random IDs cheaply, you can do the following: 1. Generate a pool of 2048 bytes or so of entropy at startup using window.crypto.getRandomValues or crypto.pseudoRandomBytes. To this, append Date.now() and Math.random().toString() just in case your crypto method fails badly. Then call SHA256 on this to get your starting entropy distilled into 32 bytes. If some of the 2048 bytes of entropy are not high quality, it won't matter as much since you compress it into 32 bytes (i.e. it's worse if you just ask for 32 bytes from getRandomValues). 2. Initialize a counter to 0. 3. Each time you need an ID, increment the counter (handle wrap-around if necessary), and take a SHA256 hash of (counter, 32 bytes entropy hash obtained in 1. above, Date.now(), Math.random().toString()). Then truncate and encode this using whatever character set as needed. This way you don't drain out your cryptographic entropy pool every time you generate an ID. You also don't leak any details as to your system time, startup time, or your current position in Math.random() (which would allow someone to predict the next Math.random() result) since the final ID is hashed.
- tptacek 11y ago
  Since what you're proposing is pretty close to just running SHA2 in counter mode, you could simplify this by generating 128 bits of random data, using it as an AES key, and just using your crypto library's AES-CTR function to generate a keystream. If you need a predictable stream of uncorrelated bits, this has the benefits of being simple and trivially seedable.
  - jorangreef 11y ago
    Thanks, that's an elegant solution. In case the entropy pool is drained, one would still want to get more than 128 bits from urandom and then hash this with SHA2 to get the 128 bit key, right? I had in mind something portable to the browser without requiring AES there, but will try it out on the server.
    - tptacek 11y ago
      In a practical sense, there is no such thing as draining an entropy pool. The period for AES-CTR is 2^128. The primary reason CSPRNGs rekey themselves periodically is for forward security, so that if your machine gets hacked, an attacker can't snarf the RNG state and predict all future numbers the machine generates.
dzhiurgis 11y ago
Hey, does anyone tried to Google for CSPRNG? What Google return for wikipedia's article title is totally off: https://www.google.com/search?q=CSPRNG Random are numbers - Wikipedia https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
- cooper12 11y ago
  I got the same result. Usually google gives a different title than the Wikipedia title when it's closer to the search term used. However, these titles are taken from redirects to the article and "Random are numbers" wasn't ever an article or a redirect. The phrase also doesn't appear anywhere in the wikitext or the generated html. Searching for the exact string also yields only two other results, one from a reddit thread, and another from a paper. Very strange.
andreapaiola 11y ago
If you need to identify, to name, something uniquely and dynamically: 1) Do NOT use a non-deterministic generator, you'll thank me when debugging 2) find what uniquely identifies the object and generated deterministically string from those values For example to identify a request to a service on the internet you can use microtime, IP and a counter and so on.
andreapaiola 11y ago
If you need to identify, to name, something uniquely and dynamically: 1) Do NOT use a non-deterministic generator, you'll thank me when debugging 2) find what uniquely identifies the object and generated deterministically string from those values For example to identify a request to a service on the internet you can use microtime, IP and a counter and so on.
lolo_ 11y ago
META: Maybe the mods need to look into how certain popular sites treat #, as medium seems to generate a new #<hash> on each refresh. I submitted this 1 day ago, intentionally removing the #<hash> - https://news.ycombinator.com/item?id=10598335 https://news.ycombinator.com/item?id=10598335 - r0muald clearly caught a better timing for this article but frustrating that an exact duplicate submitted in very close proximity becomes a totally separate submission!
- dang 11y ago
  HN's dupe detector deliberately allows reposts if an article hasn't had significant attention yet, so the added hash didn't make a difference in this case. That said, there are definitely too many duplicates right now and we're working on a new approach that will (as a side effect) privilege the original submitter more often. It's frustrating when you get there first and someone else hits the jackpot, but it evens out in the long run if you submit enough good stories.
  - lolo_ 11y ago
    Thanks for the quick and reasonable reply! I am only a little frustrated that I missed out on so much karma love (I am in my 30's now and find that these things matter less as I get older :), it was more the fact that Medium naturally appends this, so literally all submissions of a Medium article will result in reposts. It's not a simple problem as some URLs will rely on the hash to work correctly, e.g. hxxp://www.example.com/#!/foo/bar, so you can't just strip it. I think it requires some special cases for sites known to do this kind of thing (not sure why Medium do it.) Glad to hear duplicates is an issue you're looking at, has certainly been a problem, though I agree it makes sense to allow it in certain cases. For example I love the XV6 OS and like to see it periodically submitted again from time-to-time to see new discussion. It might even be nice to have an auto-generated list of previous submissions in this case? As an amusing aside, this whole issue has a relationship to the story - perhaps the generated hash uses Math.random() and therefore might actually result in duplicate URLs after not so many resubmissions? ;)
adrae5df 11y ago
Can someone explain how the following calculation was done? With 2¹³² possible values, if identifiers were randomly generated at the rate of one million per second for the next 300 years the chance of a collision would be roughly 1 in six billion. I tries using the formula for the Birthday problem, but the values are too large.
- dmit 11y ago
  Which formula did you use? There are various approximations. Although I got ~43 years using the one from https://en.wikipedia.org/wiki/Birthday_attack#Source_code_example https://en.wikipedia.org/wiki/Birthday_attack#Source_code_ex... julia> birthday(prob, vals) = sqrt(2 * vals * -log1p(-prob)) birthday (generic function with 1 method) julia> iters = birthday(1/6e9, 2.0^132) 1.3471597122821932e15 julia> iters / 1e6 / 60 / 60 / 24 / 365 42.718154245376496
  - adrae5df 11y ago
    I found an approximation (x^2/2m) and got the result that is on the same magnitude as 1 in a billion.
- emcq 11y ago
  I'm not sure about their numbers, but with a little trick it can be estimated as 1-e^(-2^(n-x-1)), where x is the number of bits and n is log_2 of the number of random draws. When n and x are relatively close, you should be able to calculate this without numbers getting too big or too small.
erikpukinskis 11y ago
Huh. I always check for collisions if I'm using a random number as a unique key. I guess it's faster to just not check, but it's just a single seek to check for existence. It's pretty fast, and you almost never have to do it twice. As a side benefit you can get by with shorter (more human readable, typeable, fits-in-a-tweet) keys because you correct the few collisions you get. If the extra keyspace seek were ever a serious performance bottleneck I would just skip the collision check in that one spot and use a proper RNG as OP is suggesting. But how often does that really happen? Very few systems need to generate millions of unique keys a second.
- hawkice 11y ago
  If he was actually hitting a cycle in the numbers generated, check/retry won't help -- eventually your entire network will bottleneck on DB reads without making any writes.
- anyfoo 11y ago
  Checking for collisions becomes hardly possible in distributed systems pretty quickly (take git as an extreme example), and provides virtually no benefit if you can trust your RNG. At those astronomical possibilities, there are many things that can go wrong before collisions become viable. Think about it: Why bother checking, when you have a somewhat similarly egregious probability that a random bit flip occurs right after your check? In the situations you encountered, it's probably simple and cheap, but in the cases where it's not (the situation in the article being a probable example), it can be expensive, error-prone complexity without gain.
altern8 11y ago
Again..?
nilknarf 11y ago
I have previously written about how to predict the next Math.random in Java (and hence Firefox also): http://franklinta.com/2014/08/31/predicting-the-next-math-random-in-java/ http://franklinta.com/2014/08/31/predicting-the-next-math-ra... The TL;DR; is that it is easy since you only have to brute force around 2^22 possibilities (which runs in < 1 second). Someone then asked whether it is also possible in Chrome and Node: https://github.com/fta2012/ReplicatedRandom/issues/2 https://github.com/fta2012/ReplicatedRandom/issues/2. After examining the MWC1616 code I saw the same “two concatenated sub-generators” problem explained in this post. The implication of it is that you can brute force the top and bottom 16 bits independently. So it is also easy since that’s just doing 2^16 possibilities twice! Code: https://gist.github.com/fta2012/57f2c48702ac1e6fe99b https://gist.github.com/fta2012/57f2c48702ac1e6fe99b
elcct 11y ago
func rand() float64 { return 0; } FTFY
antirez 11y ago
Great post. I wrote this after reading it where a simple and reliable solution to the ID generation problem is described: https://news.ycombinator.com/item?id=10606910 https://news.ycombinator.com/item?id=10606910
- mmalone 11y ago
  Good idea! But it looks like you re-invented a SHA/counter based CSPRNG :). That's not necessarily a bad thing, but there are probably library CSPRNGs that work as well and hide some details. Also, it's not generally any more or less likely to produce collisions than the method we're using. The probability of collision is dependent on the hash function / PRNG being used.
crabasa 11y ago
npm install node-uuid As a programmer, I quite enjoyed reading this post. But I can't believe the amount of time the author wasted learning what many crypto library authors already know: Math.random isn't any good. I mean this sincerely. You'd think they have so many more pressing problems to solve for their users.
- blahedo 11y ago
  Perhaps, but the mindset here is fundamentally academic: here is an interesting problem, I wonder what I can learn about its properties? And having looked into those properties, the author decides to write them up and disseminate them. (Very well, I might add. I filed the link in a bookmark folder I keep for "articles I'd like to assign my students to read, next time I teach a relevant class. This one is well-written and well-referenced.)
  - crabasa 11y ago
    Sure, but I still see two problems: 1. Math.random, despite his insistence, isn't broken. There are different degrees of randomness that a programmer might need for their program and Math.random simply didn't suit his. 2. Their initial implementation of a critical portion of their infrastructure was so naïve, I almost couldn't couldn't believe it. I just seemed like such an anti-pattern to try to build your own UUIDs, discover (in production!) that they're not so good and then spend days figuring out why a built-in random number generator that ships in every browser isn't so great.
    - mmalone 11y ago
      1. In this case we're arguing semantics. Fine, it's not broken, but it's still bad and there are better alternatives with no drawbacks. Arguing to keep it is sort of like arguing to keep an O(n) algorithm that has an O(log n) alternative that's also more intuitive and easier to code. If you still don't believe me, here's what Brendan Eich thinks[1]. 2. I've addressed the standard solution / UUID question elsewhere[2]. The way we were generating identifiers is not an anti-pattern. It's a pattern. It's the standard way to produce a random string from an alphabet. If you look at the source code of any website, from HN to Google, I guarantee you will find an almost identical piece of code somewhere. The code is simple, but that doesn't make it bad. [1] https://twitter.com/BrendanEich/status/667735502691373056 https://twitter.com/BrendanEich/status/667735502691373056 [2] https://news.ycombinator.com/item?id=10605977 https://news.ycombinator.com/item?id=10605977

310 points by r0muald 11y ago

tl;dr: the algorithm powering V8's Math.random() is very poor quality. For many use cases you can't safely pretend its output is actually random. Don't use it for anything non-trivial that you care about. It should probably be fixed. In the meantime, use crypto.randomBytes() or crypto.getRandomValues() instead.

kayamon 11y ago
I think the real lesson here is that if your application is dependent on the exact behavior of an undefined algorithm, you probably should fix your application.
- mmalone 11y ago
  It wasn't dependent on exact behavior. It was dependent on a sensible general contract. We rely on sensible implementations of general contracts all over the place in software development. We did make an incorrect assumption that the PRNG (created by Google, who has a good reputation, and in what is probably the most popular software in the world) was high quality. That was a mistake, and we should have done more homework. However, there's no reason why the Math.random() implementation in V8 should _not_ be good enough to not have to worry about.
  - asdfaoeu 11y ago
    It was dependent on it being a CSPRNG which it wasn't. Math.random is designed for things like games and animations where randomness isn't critical and performance is important.
    - johncolanduoni 11y ago
      Actually CSPRNGs are slightly worse if you are more worried about distribution than predictability (he mentions this in the article). If you are using it in a context where a hostile attacker cannot gain anything via predicting or manipulating the generated numbers, then for birthday-paradox type resistance an alternate non-CS PRNG, like those typically used for simulations, is more appropriate. However when you're using JavaScript, it's likely the natively implemented CSPRNG will be faster than a custom "faster" PRNG implemented in JavaScript.
    - seba_dos1 11y ago
      No, it wasn't. Read the article again. Assumption made was on Math.random being high quality PRNG. Being cryptographically secure is completely unrelated.
      - Dylan16807 11y ago
        Medium quality, really. But it was neglected and bad for no reason, no tradeoffs.
  - deleted 11y ago
    [deleted]
  - pacaro 11y ago
    This is a tricky answer. The default random function in many environments is poor (see other examples given above and below), if you are generating a unique id using a PRNG and think in terms of the birthday paradox, then you should also be concerning yourselves with the quality of the random generator. While it is unreasonable to expect every developer to know the ins and outs of a deeply technical issue, defaulting to using a known good (enough) algorithm like MT over making an assumption about the quality of an unknown algorithm (unknown at least until you looked into the source code) just because it came from google is poor engineering (IMHO) The analysis in this article was great engineering - something that in my experience often happens after poor engineering... YMMV
- deleted 11y ago
  [deleted]

swang 11y ago

Curious why they aren't using hardware RNGs?

pcwalton 11y ago
Too slow.

netheril96 11y ago

Given that browser JS has no way to interface with /dev/urandom, I think it is a mistake for V8 not to make the only random number generator available to browser JS secure by default. Of course, on Node.js that is a different issue.

asdfaoeu 11y ago
What about https://developer.mozilla.org/en-US/docs/Web/API/RandomSource/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/RandomSourc... ?
- netheril96 11y ago
  Learned a new thing today. Thanks.

nodesocket 11y ago

The challenge of "randomness" is overlooked and leads to security issues more than most people realize. For example in php, the `rand()` function documentation (to their credit) has a big warning that the function is not cryptographically secure. When in doubt, use unix, and <updated>/dev/urandom</updated> Also, here is a command (to my knowledge secure) which generates a nice random 20 length alphanumeric: LC_CTYPE=C < /dev/urandom tr -dc A-Za-z0-9 | head -c20

admax88q 11y ago
Use /dev/urandom, not /dev/random. There are no security concerns with /dev/urandom
- jzd 11y ago
  this. also /dev/random blocks and it can be really slow
- rst 11y ago
  Here's a writeup of a serious security flaw traced directly to the use of /dev/urandom instead of /dev/random: https://factorable.net/ https://factorable.net/ In brief, wifi routers need to generate unique crypto keys. The programmers started off using /dev/random, observed that blocking, and switched to /dev/urandom. The problem was that they were generating the keys at first boot, before any entropy had accumulated, with the result that many, many devices wound up with similar or identical keys.
  - derefr 11y ago
    Pedantic version, then: use /dev/urandom unless your software is itself part of the OS's boot sequence.
    - comex 11y ago
      What is the definition of "part of the OS's boot sequence"? In the factorable.net paper[1], a test system didn't generate 192 bits of entropy until 66 seconds(!) after boot. The problem was apparently exacerbated by Linux not mixing the entropy into the /dev/urandom pool at all until that threshold was reached, but even if it started doing so immediately, standard server processes like ssh would still start up long before there was enough entropy to make urandom sufficiently unpredictable. Sure, this is something of an extreme case... and as mentioned in the paper, there are various tools used on Linux to save a random seed to disk, so maybe the OS should ensure that happens before it starts any other services... but software that responds to an easy-to-make configuration mistake by silently behaving insecurely is the polar opposite of good security design. The right answer is Linux's new getrandom syscall, whose default mode "blocks if the entropy pool has not yet been initialized", but thereafter acts like /dev/urandom. But on systems where that syscall is not available, I'm skeptical that using /dev/urandom is sane design. [1] https://factorable.net/weakkeys12.conference.pdf https://factorable.net/weakkeys12.conference.pdf

admax88q 11y ago

No platform in 2015 should even have a poor PRNG. It's pretty sad really. rand() in C, rand() in PHP, Math.random() in JS. Any use case where you want a poor random number generator is a niche use case and you can write your own. We should be secure by default.

baudehlo 11y ago
If you want a random entry from an array, Math.random is fine. Anyone who doesn't know that prng's are broken for things like uuids shouldn't be in charge.
- seanwilson 11y ago
  There's something to be said about having sensible defaults that prevent common mistakes though. Everyone makes mistakes.
  - baudehlo 11y ago
    True. But every language has gone through this issue. Node is particularly vulnerable to weak prng seeding due to relying on forking to support multiple processes. Am I that old and grumpy to expect people to be aware of the history here?
    - seanwilson 11y ago
      I think the size of this thread as well as the existence of blog posts like this means it's a mistake that's always going to be repeated. There's way too many programming gotchas to expect people to keep track of them all. Language support to avoid classes of mistakes is a great idea to me e.g. such as having a good random algorithm by default and a UUID library.
- johncolanduoni 11y ago
  > Anyone who doesn't know that prng's are broken for things like uuids shouldn't be in charge. Depends on how you're using them. If you only care about collisions, and you're not worried about an attacker trying to manipulate your system, then using a PRNG whose output is well-distributed (read: not necessarily a language's random function) is fine. The problem is most language's default PRNGs are complete crap :( edit: grammar

pygy_ 11y ago

The v8 Math.random() code was changed yesterday[0], maybe in response to this. However, the update appears to be misguided[1]... 0. https://github.com/v8/v8/commit/623cbdc5432713badc9fe1d605c585aabb25876c https://github.com/v8/v8/commit/623cbdc5432713badc9fe1d605c5... 1. https://codereview.chromium.org/1462293002/#msg12 https://codereview.chromium.org/1462293002/#msg12

je42 11y ago
I don't understand why they don't go for mersenne twister ?!
- acqq 11y ago
  MT is "on average" maybe "as fast" but the key is "on average:" depending on the usage pattern it can cost much more. This specific RNG follows a traditional approach (that is, like in C or Java standard libraries) to have one algorithm in the standard library that is "as fast as possible, as bad as possible." Which meant even "just multiply with constant, add another constant, return. Bad? Yes we know." So it's still on the level "it's two multiplies and two-three adds." Traditionally, those who expect some specific properties, like the author of the article, should have actually used the implementation they added to their code (for example MT if it fits) if they ultimately cared about the speed and wanted exactly the properties they know they needed, or if they just didn't care about the speed used some much "slower" but "much better" library. Maybe the tradition can be broken in this specific case, I really don't know which benchmarks define what's acceptable here. Note also that the implementation must be verified, just the fact that there is somewhere some implementation available doesn't even mean that it does what is expected to do. The devil is in the details here.
- bhickey 11y ago
  I haven't looked closely enough at their choice to evaluate it, but there's a good reason not to use Mersenne Twister. MT is a bad generator. * The state size is 2kb * It fails some rudimentary statistical tests * The output is trivially predicted * It isn't particularly fast * It lacks multi-stream support If you need a CSPRNG use ChaCha20 or AES. For simulation use PCG.

pcwalton 11y ago

My experience with compiler development is that the incentives all align toward making the "default RNG that people go to" as fast as possible to the exclusion of all else, including the quality of the generated numbers. That's because people frequently write benchmarks gated on the speed of random number generation, and those benchmarks usually don't care about the quality of the random numbers. Sometimes those benchmarks get popular, which encourages a race to the bottom in RNG quality. (Similar incentives exist for hash functions, by the way.) Popular RNG-bound benchmarks: * "fasta" from the Benchmarks Game [1] (thankfully, this one mandates use of its own RNG, though it's vulnerable to fast-forwarding as demonstrated in [2]) * "Perlin noise" [3] (almost entirely RNG performance bound) * From SunSpider (this one being particularly relevant to V8): string-validate-input [4], string-base64 [5] [1]: http://benchmarksgame.alioth.debian.org/u64q/fasta-description.html#fasta http://benchmarksgame.alioth.debian.org/u64q/fasta-descripti... [2]: https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src/fasta.rs#L121 https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src... [3]: https://github.com/nsf/pnoise https://github.com/nsf/pnoise [4]: https://www.webkit.org/perf/sunspider-0.9/string-validate-input.html https://www.webkit.org/perf/sunspider-0.9/string-validate-in... [5]: https://www.webkit.org/perf/sunspider-0.9/string-base64.html https://www.webkit.org/perf/sunspider-0.9/string-base64.html

hajile 11y ago
The author makes a reasonable point that there are algorithms that are both faster AND higher quality than the one v8 uses. I think not understanding random number generators and the resulting voodoo programming is the real culprit.
im2w1l 11y ago
Fast hash functions can be really important for performance of hash sets and maps. In my experience high speed is more important than a low collision rate. That was for primitive types, it may well be different for types where comparison is more costly. And of course if you need protection from algorithmic complexity attacks, then you will need to take that into account.
- Gankro 11y ago

serge2k 11y ago

> Good PRNGs are designed so that their cycle length is close to this upper bound. Otherwise you’re wasting memory. Why? Good article. I do have a question for the author, why after a huge amount of time writing this post don't you submit a patch to V8?

tzs 11y ago
> Why? Good question. As they author noted, k bits of state can support a cycle length of 2^k. You can look at that from the other direction and state it as a cycle length of L requires at least log2(L) bits of state. If your cycle length is L and you are using k bits of state, and k > log2(L), then in theory with a cleverer encoding of state you could save k - log2(L) bits of memory. Whether or not I'd characterize k - log2(L) excess bits as "wasted" memory depends on just how big it is. For instance, suppose someone implemented Mersenne Twister and used twice as many bits as theoretically needed for the cycle length. Typical MT has a cycle length of around 2^20000, so needs 20000 bits of state. Someone doubling that is using an excess of 2500 bytes. On the other hand, the generator the article is about has a cycle length of around 2^60, and so need in theory 60 bits of state. If an implementation doubled that they have an excess of less of 8 bytes. 2500 bytes is enough that if I were implementing I'd probably take a good look at seeing if I could eliminate it, even if it meant making the implementation a little more obtuse. I'd be inclined to consider that 2500 bytes as wasted memory. 8 bytes? That's small enough that even on most embedded systems I'd probably consider clean and clear code to be more important than saving that memory. I'd not be inclined to consider it wasted memory.
- Gibbon1 11y ago
  I have another reason based on some mucking with simple PNG's a long time ago. Might not apply to more complicated ones[1]. Maximal cycle length generators don't produce degenerate sequences. Meaning I seem to remember ones where they'd have say a sequence of 2^k - 349 and a sequence of 340 and a sequence of 7. Which means they fail badly if seeded incorrectly. [1] Noting an old article I read on FPGA design that said, 'helps to design your state machines so that that illegal states transition to legal ones' So I assume sub 2^k generators exist that don't have sub-sequences.

PhantomGremlin 11y ago

I can't believe you're defending "an incorrect assumption" regarding your previous generator, especially after you wrote a very good article showing how badly wrong you were. Wait, let me restate that. You're Engineering the Disruption of Real Money Gaming and yet you say of some PRNG "no reason the ... implementation ... should not be good enough to not have to worry about"? You're not just wrong, in fact you're "not even wrong", that's how wrong you are. Plus that sentence has three negatives! Jules Winnfield said it better than I could. Riffing from him, what you were doing was, compared to what you should have been doing: ain't the same fuckin' ballpark, it ain't the same league, it ain't even the same fuckin' sport. Here's something I came up with in 60 seconds. It's far better than what you didn't want to worry about: ID Quantique hardware RNG [1] mixed with Intel RdRand [2] Yes, you're right. That's not seed-able, so you can't create a reproducible sequence of values (e.g., for testing). That's an advantage. You want to test, you replace hardware with software. But if you want to disrupt real money gaming you don't use some crappy software in some random library that wasn't designed for the purpose. Once again, I can't believe your defense of how badly you failed was the "reputation" that Google has. Real money is involved and you thought it was OK to rely on some crappy PRNG created by Google? For something that is at the heart of, the quintessence of what you are attempting to accomplish? EPIC FAIL!!! [1] http://www.idquantique.com/random-number-generation/ http://www.idquantique.com/random-number-generation/ [2] https://en.wikipedia.org/wiki/RdRand https://en.wikipedia.org/wiki/RdRand

PhantomGremlin 11y ago
Oh, yeah, downvote the messenger instead of respecting the message, which is that a third-rate amateur approach to random number generation just doesn't cut it. This was known as far back as 1999, when similar flaws bedeviled online poker sites.[4][5] Anyone going into the business should have known that from the start, instead of stumbling into it. And definitely shouldn't be trying to retroactively justify such gross incompetence. It's not Google's fault that these guys designed a crappy PRNG into a real money application. There is always the potential for cheating when real money is involved: 1980 Pennsylvania Lottery scandal[1] people added weight to supposedly random ping pong balls scratch lottery tickets weren't random[2] a "trick worked about 90 percent of the time" American Coin Machine Company[3] video poker machines were programmed to cheat players out of jackpots people were cheating online poker as far back as 1999, due to a flawed PRNG[4][5] Those are just a few cases that I could recall. I'm sure there have been many many more. True randomness is just the start in what it takes to prevent this. People who want to "disrupt real money gaming" shouldn't be making amateur mistakes like this. [1] https://en.wikipedia.org/wiki/1980_Pennsylvania_Lottery_scandal https://en.wikipedia.org/wiki/1980_Pennsylvania_Lottery_scan... [2] http://www.wired.com/2011/01/ff_lottery/ http://www.wired.com/2011/01/ff_lottery/ [3] https://www.google.com/search?q=American+Coin+machine+company&ie=utf-8&oe=utf-8 https://www.google.com/search?q=American+Coin+machine+compan... [4] http://www.nytimes.com/1999/09/13/business/compressed-data-e-gambling-software-gave-players-an-edge.html http://www.nytimes.com/1999/09/13/business/compressed-data-e... [5] https://www.cigital.com/papers/download/developer_gambling.php https://www.cigital.com/papers/download/developer_gambling.p...

tlrobinson 11y ago

JavaScript's Math.random (and most languages' default RNGs) is not intended to be cryptographically secure, so I'm not sure "broken" is correct. It's probably random enough for most uses that don't require a CSPRNG. Are there any scenarios where this isn't the case? On the other hand, enough people make this mistake that APIs should just use a CSPRNG for "random()" and offer a "fastRandom()" for those who need speed but not "secure" random.

panic 11y ago
Statistical simulations require good randomness (or your simulation might give a wrong result) and high speed but not cryptographic security. See, for example, xorshift* (http://xorshift.di.unimi.it http://xorshift.di.unimi.it), which is efficient and high-quality but not cryptographically secure.
dahart 11y ago
My personal definition of random includes the requirement that plotting the bits must look random, and have no visible signs of pattern. The OP did that and you can see patterns. If plotting a picture of a PRNG's bits has visible patterns, I definitely call it completely broken.

emmelaich 11y ago

I you want ids without collisions you should use a monotonically increasing number instead (or as well). I would concatenate utc time in ms to the random number.

marcus_holmes 11y ago
or just use UUIDs which are designed for this exact use case
- vcarl 11y ago
  Exactly, my biggest takeaway is "don't write your own unique ID algorithm." At best it does the same as existing methods, at worst you screw it up and end up here.
- dap 11y ago
  What kind of UUID? Standard UUIDs of versions 1, 2, and 3 are not really unique enough[1]. Version 4 is basically a random number, so it doesn't help to say "just use that". [1] https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier
  - marcus_holmes 11y ago
    well, I use uuidgen[1]. If I have to generate uuids for multiple servers, then I create a microservice to handle uuid generation, and get it to generate a few held in a buffer so the rest of the system doesn't have to wait for one. [1] http://man7.org/linux/man-pages/man1/uuidgen.1.html http://man7.org/linux/man-pages/man1/uuidgen.1.html
deleted 11y ago
[deleted]
dap 11y ago
You can't use monotonically increasing numbers from multiple threads (or servers) without either synchronizing (which is terrible for scalability) or using separate prefixes for different threads or servers (in which case you have problems related to sizing and allocating the prefixes). Right? The UTC time + random number idea is interesting, but I'm not sure it's any better than totally random. Say you want a 64-bit unique id. It would take about 42 bits to store a millisecond Unix timestamp, leaving 22 bits for randomness. If you consider the probability that a given id will collide with a previously-generated one: with this scheme, you only need to consider ids generated in the same millisecond, but you only have 22 bits of randomness that can be used to avoid a collision. If you use 64 random bits, you can theoretically collide with ids generated across all of time, but the odds of collision are many orders of magnitude lower. By constraining the first 42 bits to store a millisecond timestamp, every millisecond that goes by removes 2^22 values from the possible id space (regardless of whether they're used). (Besides that, this scheme removes from the space of possible ids all of the millisecond values from before the system was created, which seems like about 2/3 of them, assuming about a 68-year span of values for Unix times, which started 45 years ago.) That's kind of handwavy, so let's do the math. With 22 bits of randomness, the odds of any randomly selected pair of ids generated in the same millisecond colliding is 1/4194304. Assuming independently generated ids, the expected number of collisions after 4194304 milliseconds is 1. So if you have just two threads generating ids once per millisecond, you'd expect a collision in just 70 minutes. That's not great. It's late, though. Maybe my math is wrong?

omarforgotpwd 11y ago

I can't b3liwv3 I just read that entire thing drunk on a Friday night

mmalone 11y ago
Hahahahaha. I can't believe that either.

bytesandbots 11y ago

Default PRNGs primary use case is generating session ids for websites with upto 1000s of simultaneous users, not for assigning UUIDs. One should use a combo of a sequential component and a random component. When you have multiple servers, make them combine a sequential component, a unique system identifier and a random number. In this case, you can now use the faster PRNGs which will also give you speed while ensuring uniqueness. Another takeaway from this problem is that the usual method of Multiply-and-floor has a serious flaw of using only the highest bits which may not be good enough for the default fast PRNGs. A better method is to carry forward the remaining bits from the floor using a modulo function. The default fast PRNGs rely on all of their bits and simply throwing away a big chunk is not going to help. Multiply and floor might be more useful in a scenario where you are using better PRNGs. Even then, they are slower and it is not wise to simply throw the hard earned randomness.

mmalone 11y ago
Using node IDs and timestamps is just an additional safety factor. Statistically it's not necessary if you have a good generator. Even without those things our target collision probability is less than the expected uncorrectable error bit rate of a HDD. Good PRNGs have equivalent entropy at each bit. With a good PRNG (even a non-CS PRNG) you shouldn't need to mix entropy to do scaling. You should still do rejection sampling[1] if you care about bias. It looks like a good scaling method might be added to the ECMA spec as part of the standard library thanks to some awesome people at Google.[2] [1] https://gist.github.com/mmalone/d710793137ed0d6b8cb4 https://gist.github.com/mmalone/d710793137ed0d6b8cb4 [2] https://twitter.com/mjmalone/status/667806963976134656 https://twitter.com/mjmalone/status/667806963976134656
- jorangreef 11y ago
  "Using node IDs and timestamps is just an additional safety factor. Statistically it's not necessary if you have a good generator." Sorry, that's just not sensible. You always want to add node IDs and timestamps (provided you hash the final output so as not to leak details about your system) in case your generator fails. Why would you not want another layer of safety? It also helps protect against the case where an attacker might gain something by being able to predict the next ID in the sequence.

bytesandbots 11y ago

For those wondering why not use UUID, most uuid implementation are guaranteed to be unique only when running a single machine. When working on loads of servers without putting any load on a central resource, you can not rely on either uuid or sequential.

tolmasky 11y ago
UUID v4 seems to be based on random numbers, so should be "as good" as whatever scheme they were trying to hand roll here. Additionally, the uuid npm library uses crypto.randomBytes, which is cryptographically secure. https://github.com/broofa/node-uuid https://github.com/broofa/node-uuid
- mmalone 11y ago
  The biggest problem is that they take up a lot of space. Plus you have to find a good library and vet it (there's nothing in the standard library). Or just write 10 lines of straightforward code. If you go and look at node-uuid commit history it, too, used Math.random() back in the day.
mrighele 11y ago
This is true for UUID version 4, which is completely random. There are variant that use host-specific information in the process (in fact version 4 is the only one not doing it). [1] This said, I see that often only v4 is implemented, so maybe there are issue with the other variants. [1] https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier

UnoriginalGuy 11y ago

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.

Drdrdrq 11y ago

I think the whole idea of generating random ids is flawed. Why take a chance when there is no need? Just take some machine id (seq. number, MAC), timestamp and a big enough per-machine counter and there can be no collision, guaranteed. No need to use random.voodoo().

sgk284 11y ago
Hardware companies have definitely been lazy and reused MAC addresses. But what's worse is that the total space is as low as 48 bits. The probability of a collision is orders of magnitude higher than if you just grab some random bytes out of /dev/urandom and generate a type-4 UUID. For a discussion on the benefits of your approach (a type-1 UUID) vs a random id (a type-4 UUID), check out the wikipedia article: https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier Randomness is great because it doesn't require any synchronization or access to some special token.
- michaelmior 11y ago
  If you get identical MAC addresses on machines operating the same service, presumably on the same network, you have bigger problems than ID generation.
- Drdrdrq 11y ago
  Mac addresses should be unique; at least for network cards. The address space of 48bits is not that small. Also, see the warning about entropy in your linked article. There is a difference between mathematical random() and CS random().
mmalone 11y ago
It's easier to generate a random identifier and if the generator is good the probability of a collision is lower than the probability that you HDD will fuck up in an uncorrectable way while storing the identifier (as I've pointed out elsewhere in thread). So the answer is that random identifiers are easier to do in a distributed system and, in reality, have the same guarantees.

mckoss 11y ago

Why no mention of window.crypto.getRandomValues?

Too 11y ago
Read more carefully...
- mckoss 11y ago
  Skimming on phone and I missed it-thanks!
mmalone 11y ago
It is mentioned! Without the `window.` part though ;).
anilgulecha 11y ago
It is mentioned.

NicoJuicy 11y ago

I understand why they want unique generated id's, i don't understand why they just didn't use UUID/Guid, which are way more performant ( string vs int) and less big in size ( 22 bytes vs 16 bytes). Both are created for the same purpose and Guid's are even possible as keys in MS SQL Server (next to the standard autoincremented integer). So it's safe to say that it's pretty reliable.

cowsandmilk 11y ago
UUID : 128 bits Bitable's scheme : 132 bits Essentially the same size. They ended up with 132 bits because they use a 6 bit alphabet; 128 is not divisible by 6, so you would need 22 characters of a 6 bit alphabet to represent a UUID, exactly the same as them. (note, the 6 bit alphabet is so identifiers can go in urls; the commonly used uuid hexadecimal representation is a 4-bit alphabet, so there are 32 characters and usually 4 hyphens; so 36 characters in the URL vs. only 22)

gmac 11y ago

I have to say I'm surprised — I thought better of V8 than this. Arguably it's usually going to be preferable to know you're getting the same kind of random numbers across platforms anyway, so a BYO Mersenne Twister is a decent remedy. One is linked in the post, and I have a CoffeeScript one here: https://github.com/jawj/mtwist/blob/master/mtwist.coffee https://github.com/jawj/mtwist/blob/master/mtwist.coffee

deleted 11y ago

[deleted]

jorangreef 11y ago

If you need good quality random IDs cheaply, you can do the following: 1. Generate a pool of 2048 bytes or so of entropy at startup using window.crypto.getRandomValues or crypto.pseudoRandomBytes. To this, append Date.now() and Math.random().toString() just in case your crypto method fails badly. Then call SHA256 on this to get your starting entropy distilled into 32 bytes. If some of the 2048 bytes of entropy are not high quality, it won't matter as much since you compress it into 32 bytes (i.e. it's worse if you just ask for 32 bytes from getRandomValues). 2. Initialize a counter to 0. 3. Each time you need an ID, increment the counter (handle wrap-around if necessary), and take a SHA256 hash of (counter, 32 bytes entropy hash obtained in 1. above, Date.now(), Math.random().toString()). Then truncate and encode this using whatever character set as needed. This way you don't drain out your cryptographic entropy pool every time you generate an ID. You also don't leak any details as to your system time, startup time, or your current position in Math.random() (which would allow someone to predict the next Math.random() result) since the final ID is hashed.

tptacek 11y ago
Since what you're proposing is pretty close to just running SHA2 in counter mode, you could simplify this by generating 128 bits of random data, using it as an AES key, and just using your crypto library's AES-CTR function to generate a keystream. If you need a predictable stream of uncorrelated bits, this has the benefits of being simple and trivially seedable.
- jorangreef 11y ago
  Thanks, that's an elegant solution. In case the entropy pool is drained, one would still want to get more than 128 bits from urandom and then hash this with SHA2 to get the 128 bit key, right? I had in mind something portable to the browser without requiring AES there, but will try it out on the server.
  - tptacek 11y ago
    In a practical sense, there is no such thing as draining an entropy pool. The period for AES-CTR is 2^128. The primary reason CSPRNGs rekey themselves periodically is for forward security, so that if your machine gets hacked, an attacker can't snarf the RNG state and predict all future numbers the machine generates.

dzhiurgis 11y ago

Hey, does anyone tried to Google for CSPRNG? What Google return for wikipedia's article title is totally off: https://www.google.com/search?q=CSPRNG Random are numbers - Wikipedia https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

cooper12 11y ago
I got the same result. Usually google gives a different title than the Wikipedia title when it's closer to the search term used. However, these titles are taken from redirects to the article and "Random are numbers" wasn't ever an article or a redirect. The phrase also doesn't appear anywhere in the wikitext or the generated html. Searching for the exact string also yields only two other results, one from a reddit thread, and another from a paper. Very strange.

andreapaiola 11y ago

If you need to identify, to name, something uniquely and dynamically: 1) Do NOT use a non-deterministic generator, you'll thank me when debugging 2) find what uniquely identifies the object and generated deterministically string from those values For example to identify a request to a service on the internet you can use microtime, IP and a counter and so on.

andreapaiola 11y ago

lolo_ 11y ago

META: Maybe the mods need to look into how certain popular sites treat #, as medium seems to generate a new #<hash> on each refresh. I submitted this 1 day ago, intentionally removing the #<hash> - https://news.ycombinator.com/item?id=10598335 https://news.ycombinator.com/item?id=10598335 - r0muald clearly caught a better timing for this article but frustrating that an exact duplicate submitted in very close proximity becomes a totally separate submission!

dang 11y ago
HN's dupe detector deliberately allows reposts if an article hasn't had significant attention yet, so the added hash didn't make a difference in this case. That said, there are definitely too many duplicates right now and we're working on a new approach that will (as a side effect) privilege the original submitter more often. It's frustrating when you get there first and someone else hits the jackpot, but it evens out in the long run if you submit enough good stories.
- lolo_ 11y ago
  Thanks for the quick and reasonable reply! I am only a little frustrated that I missed out on so much karma love (I am in my 30's now and find that these things matter less as I get older :), it was more the fact that Medium naturally appends this, so literally all submissions of a Medium article will result in reposts. It's not a simple problem as some URLs will rely on the hash to work correctly, e.g. hxxp://www.example.com/#!/foo/bar, so you can't just strip it. I think it requires some special cases for sites known to do this kind of thing (not sure why Medium do it.) Glad to hear duplicates is an issue you're looking at, has certainly been a problem, though I agree it makes sense to allow it in certain cases. For example I love the XV6 OS and like to see it periodically submitted again from time-to-time to see new discussion. It might even be nice to have an auto-generated list of previous submissions in this case? As an amusing aside, this whole issue has a relationship to the story - perhaps the generated hash uses Math.random() and therefore might actually result in duplicate URLs after not so many resubmissions? ;)

adrae5df 11y ago

Can someone explain how the following calculation was done? With 2¹³² possible values, if identifiers were randomly generated at the rate of one million per second for the next 300 years the chance of a collision would be roughly 1 in six billion. I tries using the formula for the Birthday problem, but the values are too large.

dmit 11y ago
Which formula did you use? There are various approximations. Although I got ~43 years using the one from https://en.wikipedia.org/wiki/Birthday_attack#Source_code_example https://en.wikipedia.org/wiki/Birthday_attack#Source_code_ex... julia> birthday(prob, vals) = sqrt(2 * vals * -log1p(-prob)) birthday (generic function with 1 method) julia> iters = birthday(1/6e9, 2.0^132) 1.3471597122821932e15 julia> iters / 1e6 / 60 / 60 / 24 / 365 42.718154245376496
- adrae5df 11y ago
  I found an approximation (x^2/2m) and got the result that is on the same magnitude as 1 in a billion.
emcq 11y ago
I'm not sure about their numbers, but with a little trick it can be estimated as 1-e^(-2^(n-x-1)), where x is the number of bits and n is log_2 of the number of random draws. When n and x are relatively close, you should be able to calculate this without numbers getting too big or too small.

erikpukinskis 11y ago

Huh. I always check for collisions if I'm using a random number as a unique key. I guess it's faster to just not check, but it's just a single seek to check for existence. It's pretty fast, and you almost never have to do it twice. As a side benefit you can get by with shorter (more human readable, typeable, fits-in-a-tweet) keys because you correct the few collisions you get. If the extra keyspace seek were ever a serious performance bottleneck I would just skip the collision check in that one spot and use a proper RNG as OP is suggesting. But how often does that really happen? Very few systems need to generate millions of unique keys a second.

hawkice 11y ago
If he was actually hitting a cycle in the numbers generated, check/retry won't help -- eventually your entire network will bottleneck on DB reads without making any writes.
anyfoo 11y ago
Checking for collisions becomes hardly possible in distributed systems pretty quickly (take git as an extreme example), and provides virtually no benefit if you can trust your RNG. At those astronomical possibilities, there are many things that can go wrong before collisions become viable. Think about it: Why bother checking, when you have a somewhat similarly egregious probability that a random bit flip occurs right after your check? In the situations you encountered, it's probably simple and cheap, but in the cases where it's not (the situation in the article being a probable example), it can be expensive, error-prone complexity without gain.

altern8 11y ago

Again..?

nilknarf 11y ago

I have previously written about how to predict the next Math.random in Java (and hence Firefox also): http://franklinta.com/2014/08/31/predicting-the-next-math-random-in-java/ http://franklinta.com/2014/08/31/predicting-the-next-math-ra... The TL;DR; is that it is easy since you only have to brute force around 2^22 possibilities (which runs in < 1 second). Someone then asked whether it is also possible in Chrome and Node: https://github.com/fta2012/ReplicatedRandom/issues/2 https://github.com/fta2012/ReplicatedRandom/issues/2. After examining the MWC1616 code I saw the same “two concatenated sub-generators” problem explained in this post. The implication of it is that you can brute force the top and bottom 16 bits independently. So it is also easy since that’s just doing 2^16 possibilities twice! Code: https://gist.github.com/fta2012/57f2c48702ac1e6fe99b https://gist.github.com/fta2012/57f2c48702ac1e6fe99b

elcct 11y ago

func rand() float64 { return 0; } FTFY

antirez 11y ago

Great post. I wrote this after reading it where a simple and reliable solution to the ID generation problem is described: https://news.ycombinator.com/item?id=10606910 https://news.ycombinator.com/item?id=10606910

mmalone 11y ago
Good idea! But it looks like you re-invented a SHA/counter based CSPRNG :). That's not necessarily a bad thing, but there are probably library CSPRNGs that work as well and hide some details. Also, it's not generally any more or less likely to produce collisions than the method we're using. The probability of collision is dependent on the hash function / PRNG being used.

crabasa 11y ago

npm install node-uuid As a programmer, I quite enjoyed reading this post. But I can't believe the amount of time the author wasted learning what many crypto library authors already know: Math.random isn't any good. I mean this sincerely. You'd think they have so many more pressing problems to solve for their users.

blahedo 11y ago
Perhaps, but the mindset here is fundamentally academic: here is an interesting problem, I wonder what I can learn about its properties? And having looked into those properties, the author decides to write them up and disseminate them. (Very well, I might add. I filed the link in a bookmark folder I keep for "articles I'd like to assign my students to read, next time I teach a relevant class. This one is well-written and well-referenced.)
- crabasa 11y ago
  Sure, but I still see two problems: 1. Math.random, despite his insistence, isn't broken. There are different degrees of randomness that a programmer might need for their program and Math.random simply didn't suit his. 2. Their initial implementation of a critical portion of their infrastructure was so naïve, I almost couldn't couldn't believe it. I just seemed like such an anti-pattern to try to build your own UUIDs, discover (in production!) that they're not so good and then spend days figuring out why a built-in random number generator that ships in every browser isn't so great.
  - mmalone 11y ago
    1. In this case we're arguing semantics. Fine, it's not broken, but it's still bad and there are better alternatives with no drawbacks. Arguing to keep it is sort of like arguing to keep an O(n) algorithm that has an O(log n) alternative that's also more intuitive and easier to code. If you still don't believe me, here's what Brendan Eich thinks[1]. 2. I've addressed the standard solution / UUID question elsewhere[2]. The way we were generating identifiers is not an anti-pattern. It's a pattern. It's the standard way to produce a random string from an alphabet. If you look at the source code of any website, from HN to Google, I guarantee you will find an almost identical piece of code somewhere. The code is simple, but that doesn't make it bad. [1] https://twitter.com/BrendanEich/status/667735502691373056 https://twitter.com/BrendanEich/status/667735502691373056 [2] https://news.ycombinator.com/item?id=10605977 https://news.ycombinator.com/item?id=10605977