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 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.

V8icon

 

More Information

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

Advanced Hashing

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, FacebookGoogle+ or Linkedin

Banner


Google Comics Factory Makes ML Easy
06/10/2019

A comic strip approach to machine learning? Could it possibly work? The hero is a cat, so of course it can.



Microsoft Open Sources C++ Standard Library
20/09/2019

The C++ Standard Library (STL) which ships as part of the MSVC toolset and the Visual Studio IDE is being released as open source by Microsoft. The Microsoft Visual C++ compiler and libraries toolset  [ ... ]


More News

graphics

 



 

Comments




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

 

 

 

Last Updated ( Monday, 21 December 2015 )