So I’ve seen this post linked in a few places recently, and I thought to myself, “This sounds interesting…and familiar.”
For those of you who don’t quite have the technical know-how to understand what it means, here’s a quick summary. Basically, the whole thing is a flaw in the V8 JavaScript engine’s random number generator. V8, if you don’t know, is what makes JavaScript possible for Chrome, Node, and plenty of others. (Firefox uses a different engine, and Microsoft’s browsers already have far bigger problems.) In JavaScript, the RNG is accessed through the function Math.random(). That function is far from perfect as it is. There’s no need to make it worse.
But V8, until one of the newest versions (4.9.40), actually did make it worse. An outline of their code is in the post above, but the main problems with it are easy to explain. First, Math.random() returns JavaScript numbers—i.e., 64-bit floating-point numbers—between 0 and 1. The way those numbers work leaves the algorithm 52 bits to play with, but V8’s code worked by converting a 32-bit integer into a floating-point number. That’s a pretty common operation, and there’s nothing really wrong on the face of it. Well, except for the part where you’re throwing away 20 out of your 52 random bits.
Because of the way V8’s RNG algorithm (MWC1616), this gets even better. MWC stands for “multiply with carry”, an apt description of what we’re dealing with. Internally, the code has two state variables, each a 32-bit unsigned integer, or uint32_t. These start off as seeded values (JavaScript programmers have no way of influencing this part, unfortunately), and each one undergoes a simple transformation: the low 16 bits are multiplied by one of two “magic” constants, then added to the high 16 bits. The function then creates its result in two parts, with the upper half of the result coming from one state variable’s lower half, while the lower 16 bits are taken from the other state’s upper half.
The whole thing, despite its shell-game shifting of bits, is not much more than a pair of linear congruential generators welded together. LCGs have a long history as random generators, because they’re easy to code, they’re fast, and they can give okay randomness for simple applications. But now that JavaScript is being used everywhere, the cracks are starting to appear.
Since V8’s Math.random() implementation uses 32-bit numbers and none of the “extra” state found in more involved RNGs, you’re never getting more than 2^32^ random numbers before they start repeating. And I do mean repeating, as linear congruential generators are periodic functions. Given the same state, they’ll produce the same result; generate enough random numbers, and you’ll repeat a state, which restarts the cycle. But that 2^32^ is a maximum, and you need some planning to get it. The magic numbers that make an LCG work have to be chosen carefully, or you can sabotage the whole thing. All the bit-shifting tricks are little more than a distraction.
So what can you do? Obviously, you, as a user of Chrome/Node/V8/whatever, can upgrade. The new algorithm they’re using is xorshift128+, which is highly regarded as a solid RNG for non-cryptographic work. (If you’re interested in how it works, but you don’t think you can read C++, check out the second link above, where I roll my own version in JavaScript.) Naturally, this doesn’t fix all the other problems with Math.random(), only the one that caused V8’s version of it to fail a bunch of the statistical tests used to quantify how “good” a specific RNG is. (The linked blog post has a great visualization to illustrate these.) Seeded, repeatable randomness, for example, you’ll still have to handle yourself. But what we’ve got is good enough for a lot of purposes, and it’s now a better foundation to build upon.