Randomness Restored In Chrome 49
Written by MIke James
Monday, 21 December 2015

When you use a random number generator that is part of a language you tend to take it for granted that it will be random. Not so in Google's V8 engine, until now that is.

Random numbers are used a lot in programs ranging from games to serious simulations of the real world. Many languages, including JavaScript, provide a built-in function like Math.Random() to generate random numbers. This has the advantage over relying on add-on function libraries that the implementation can be optimized - in general you want a lot of random numbers in a very short time so speed is important. The big problem with including the function within the language is that you just have to accept what you are given.

Of course, random number generators aren't generally truly random; they are pseudo random. That is, the numbers are generated by an algorithm so that they cover the range evenly and given n samples it is difficult to predict future values. Notice that in principle it is always very easy to predict the future value of a random number generator - simply run it one more time.

Different pseudo-random number generators, or PRNGs, have different characteristics. Generally you trade good statistical properties in return for speed and low memory use.

Until Chrome 49 the V8 JavaScript engine made use of the  MWC1616 (multiply with carry, combining two 16-bit parts) PRNG, which has been known to have some serious problems - put simply it fails many of the standard tests.

One graphical way of acessing the quality of a PRNG is to generate pairs of random x,y values and plot them. In an ideal PRNG the points would be evenly distributed and show no clumping or tendency to form bands.

You can see just such a plot for MWC1616 in the left of the two diagrams below:

You can see that it has a tendency to form horizontal lines and short dashes. These are statistical dependencies that a user could take advantage of to beat the system in a game of simulated poker, say.

Don't get too worried. In most cases the quality of the random numbers is enough to convince an innocent player that there is no way to predict the next card. Not every user is a statistical wiz or an aggressive hacker. The suitability of a PRNG depends on what you plan to do with it.

The V8 team now reports that it has "fixed" its PRNG by replacing MWC1616 by xorshift128+, an alternative algorithm which passes all of the standard tests and has a repeat period of 2128-1. So as of V8 4.9.41.0, i.e. Chrome 49, you can have good quality random numbers as indicated by the right hand plot labeled "After" above. You can see that this looks a look more random.

However "looks" random isn't enough for a lot of applications and as the team points out the new PRNG isn't of cryptographic quality. A crypto-PRNG, or CPRNG, has to satisfy a number of additional tests. If you want to generate a random number to use in secure hashing, signature generator or encryption you need a CPRNG. The solution in this case is to make use of the Web Cryptography API and the getRandomValues method, which promises cryptographically good random numbers, but only at an extra cost in time.

You can find out more about the random number generator used in V8 in the blog post announcing the change.

It does raise an interesting question of expertise. When a language includes such specialized functions such as random, it certainly stretches the skills of the language implementer. JavaScript defines the random function but it doesn't provide any specification for how the random numbers are generated - this seems a little unfair.

Perhaps it would be better if all implementations of JavaScript used the same PRNG?

Until such a time, don't take JavaScript randomness for granted.

There's Math.random(), and then there's Math.random()

#### Related Articles

Microsoft JavaScript Cryptography Library

Cryptol Version 2 Released

Stick Figure Guide To AES Encryption

First Draft Of Web Cryptography API

Web Crypto APIs Work In Progress

Inside Random Numbers

The Monte Carlo method

How not to shuffle - the Knuth Fisher-Yates algorithm

The Programmer's Guide to Chaos

ERNIE - A Random Number Generator

 Remembering Robert Dennard, Inventor of DRAM19/05/2024Robert Dennard, the IBM engineer who invented the key memory technology DRAM that we now rely on in our computers smartphones and tablets,  passed away on April 23rd, 2024, at age 91. + Full Story Akka Adds Database Sharding Support23/05/2024Lightbend, the company behind Akka, has released Akka version 24.05. Lightbend produces cloud-native microservices frameworks while Akka allows for building distributed applications. + Full Story More News