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.

[画像:randomicon]

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:

[画像:random1]

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 2¹²⁸-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.

[画像:V8icon]

More Information

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

Comments

or email your comment to: comments@i-programmer.info

Last Updated ( Monday, 21 December 2015 )

Randomness Restored In Chrome 49

More Information

Related Articles

Comments