|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.
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.
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 126.96.36.199, 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.
There's Math.random(), and then there's Math.random()
Stick Figure Guide To AES Encryption
First Draft Of Web Cryptography API
Web Crypto APIs Work In Progress
How not to shuffle - the Knuth Fisher-Yates algorithm
The Programmer's Guide to Chaos
ERNIE - A Random Number Generator
To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook, Google+ or Linkedin.
or email your comment to: email@example.com
|Last Updated ( Monday, 21 December 2015 )|