Randomness in the web browser

Developers today may associate random-number generation most closely with security issues—and understandably so, given what we hear in the news about attempts to undermine the encryption that protects our communication online. But randomness is important in many other tasks, from games to data sampling to scientific simulation. Recently, several developers decided to explore the properties of the JavaScript Math.random() implementations provided in major web browsers, and found most to be wanting.

For context, JavaScript's Math.random() returns a floating-point pseudo-random number from the interval [0,1). It is specifically not aimed at secure or cryptographic usage; for cryptography, there is the RandomSource.getRandomValues() from the W3C Web Crypto API.

V8

On November 19, Mike Malone from Betable, a company that produces software for online gaming, posted a look at the Math.random() implementation in the V8 JavaScript engine (used by Chrome/Chromium and by several server-side projects, like Node.js). Malone noted that Betable used Math.random() to generate API request identifiers, and had calculated that 22-character identifiers would be enough to avoid collisions—at around one collision in six billion requests. But, much to the team's surprise, an employee discovered that the code in question was generating colliding identifiers regularly—and fairly often.

As it happened, the culprit was V8's Math.random(). The ECMAScript specification (the official standard defining what is known as JavaScript) offers no guidance as to what algorithm should be used to generate the numbers, nor does it even mandate with what precision the function should return its floats. Thus, each implementer has essentially gone its own direction. The V8 implementation, perhaps like a lot of code, was not thoroughly vetted when it was originally committed, and it used a mediocre pseudo-random number generator (PRNG) called MWC1616. Worse, though, the V8 code included a bug that drastically shortened the cycle length of the number sequence it generated—from 2⁶⁰ to 2¹⁵ (on 64-bit architectures). The difference meant that collisions in Betable's code would happen about once in every 30,000 identifiers.

In short, the V8 code uses two fast sub-generators, each with a cycle length of around 2³⁰, then combines their results to produce its final output. But rather than XORing the output of the two sub-generators (or combining them in some more complex manner), it simply concatenates them. In practice, this produces terrible results, because the recommended method for scaling the floats produced by Math.random() into an integer range involves a floor function, which essentially chops off the low-order bits. That, in turn, means the bits contributed by the second sub-generator gets chopped off, too. If the two sub-generators were more thoroughly mixed, this would not be the case.

Betable eventually switched over to using a cryptographic PRNG instead, but Malone's post notes that there are a variety of algorithms available that not only produce higher-quality pseudo-random outputs than the one used in V8, but they also run faster. Interestingly enough, the V8 Math.random() code was updated shortly after Malone's post, fixing the MWC1616 implementation to better mix the outputs of the two sub-generators. There has been no public discussion of the patch, though; the project's code-review site records no information as to why the patch in question was committed, and Malone offered a comment on how V8's MWC1616 could be further improved, but there has been no reply.

Firefox

Mozilla's Jan de Mooij was among the many who saw Malone's post, and decided to investigate the real-world performance of Firefox's Math.random() for comparison. He discovered that Firefox, too, uses a weak PRNG implementation. On November 30, he posted a follow-up to the original post that included pass/fail results from running the TestU01 randomness test suite against both Firefox and V8.

The algorithm used by Firefox, he said, was a linear congruential generator (LCG) that was "imported from Java decades ago". It fails 12 of the 96 tests in TestU01's medium-sized "Crush" test battery, and one of the ten tests in the "SmallCrush" battery (interestingly enough, the SmallCrush test that Firefox fails is the "BirthdaySpacings" test, which looks for the frequency of collisions: the same weakness discovered by Betable). In both cases, Firefox did perform considerably better than the pre-patch version of Chrome.

De Mooij also worried that Firefox's PRNG should be able to produce 53-bit precision (i.e., the default precision of floats as defined in the ECMAScript specification), but the implementation only returned a 32-bit result. "This means the result of the RNG is always one of about 4.2 billion different numbers, instead of 9007199 billion (2^53). In other words, it can generate 0.00005% of all numbers an ideal RNG can generate."

Thus, he set out to replace the PRNG with XorShift128+, which is both regarded as high-quality (passing, for example, TestU01's "BigCrush" battery) and is known to be fast. The resulting patch was subsequently accepted, so it should make its way into a Firefox stable release within a few months.

The rest

De Mooij did not limit his experiments to V8 and Firefox, however. He also ran the TestU01 test batteries against Safari 9, Internet Explorer (IE) 11, and Microsoft's new Edge browser. This revealed some surprises. For one thing, although Safari and Chrome formerly shared the same codebase (WebKit), they have diverged on Math.random(). Safari was using a different PRNG named GameRand, although it exhibited similarly poor numbers against TestU01. De Mooij filed a bug against WebKit, and on November 30, WebKit was patched to also use XorShift128+ for Math.random().

The tests also suggest that IE 11 was using the same PRNG as Firefox, since it produced essentially the same pass/fail results. Finally, De Mooij noted that the Edge browser seems to be using the same PRNG as IE 11, although so far he has not been able to make Edge run the complete Crush test battery without crashing, so those results should be taken with a grain of salt.

Moving forward, it will be interesting to see whether or not the attention that this story has attracted will persuade the V8 team to switch over to XorShift128+ for its Math.random() PRNG as well. While the newly patched versions of Firefox and Chrome both pass the SmallCrush test battery, Chrome (using MWC1616) still fails several Crush tests. Regardless of what happens, though, the response to this incident has been remarkably fast: in less than two weeks since Malone's first post, three major browser engines have updated their code.

Perhaps that speed stems from the knowledge that, right or wrong, software developers will be tempted to use Math.random() for critical functionality. After all, the mere fact that a separate, cryptographically secure API is available did not prevent Betable from encountering a potentially serious bug in its software. And the LCG that Firefox imported from Java is weak enough that predicting its output is trivial; anyone relying on that code for robust randomness should expect disappointment.

Still, the root cause of these widespread weaknesses found in Math.random() was copying in code without thoroughly vetting it. One hopes that it is better to copy in XorShift128+ than it was to copy in the last PRNGs, but better still would be a renewed emphasis on putting these functions to the test regularly.