I suspect the culprit is https://codereview.chromium.org/7250005, where state[0]’s contribution to random_base’s output gets left-shifted 14 bits instead of the 16 that was there before.  It seems to me that this leaves not enough entropy in the two high bits of random output.

Suppose one call to Math.random() is < 1/1024, i.e. the top ten bits returned by a call to random_base are all 0’s.  Those are basically bits 14 to 27 of state[0].  (There might be carry-up from the low 18 bits of state[1], but usually not.)

On the next call to random_base, we set state[0] = 18273 * (state[0] & 0xFFFF) + (state[0] >> 16).  With out constrained bits, that becomes 18273 times a low-entropy value <256, plus the high-entropy 16 bits of state[0] shifted down.  That covers state[0] bits 16-31, but poor bits 14-15 are left out of the high-entropy high-bit goodness.

Marsaglia's original implementation shifts state[0] << 16, so those suspect bits go back into the mix but are not part of the output.  We shift state[0] << 14, so the two suspect bits end up the high-order bits of the next output value.

The change to << 14 and & 0x3FFFF was to avoid a more subtle problem, that bits
14 and 15 of  (Math.random() * 36969) ^ Math.random() are biased, because the top few bits of the 32-bit number (x & 0xFFFF) * 36969 are biased.

Bits 14 and 15 are biased similarly in ((Math.random() >> 16) * 18273) ^ (Math.random() >> 16)

But someone really needs to use the multiplier 36969 or 18273 to create this problem, so I think it is fine to go back to << 16 and & 0xFFFF, to avoid the more serious problem found here, in this bug.

Just to be sure:

  * The "original" RNG we talk about is this: http://www.ms.uky.edu/~mai/RandomNumber

  * The consensus now is to change back the "<< 14" to "<< 16". I still don't get what this was supposed to fix.

  * We ignore stuff like http://dl.packetstormsecurity.net/papers/general/Google_Chrome_3.0_Beta_Math.random_vulnerability.pdf

IMHO programs which use Math.random() for anything serious are flawed, the spec is very vague about it, and it is basically something fast-and-not-too-embarrassing. The use cases are far too diverse to fit into a single API entry, e.g. somebody just wants something fast to control the ghosts in a pacman clone or a nice graphical explosion, while other people want to have something cryptographically secure and basically don't care about performance. In JavaScript, you are in the pacman world. :-)

Sven: In addition to changing "<< 14" back to "<< 16", the mask used to extract bits from state[1] should change from 0x3FFFF back to 0xFFFF.  The www.ms.uky.edu link is indeed the correct reference.

The fact that the internal state can be reconstructed from a few consecutive outputs is, as you say, not the sort of thing we should worry about.  Someone who wants randomness with some measure of security attached should forsake Math.random() and use crypto.getRandomValues(), which is designed to withstand such attacks.

Note that crypto.getRandomValues() also provides a work-around for the behavior in this bug: one can check whether Math.random() < 1000 and then do a coin flip using a crypto.getRandomValues() bit, and outcomes will be uncorrelated again.

Fixed in https://code.google.com/p/v8/source/detail?r=17955 (reduce the number of Math.random() implementations from 9 to 1) and https://code.google.com/p/v8/source/detail?r=17963 (use Marsaglia's original generator).

Note that there is still some correlation, so we get 50.723% vs. 49.276% after 10 billion runs, but this is an inherent problem in this kind of generator. One can easily "fix" this by sneaking in another Math.random() call between the first one choosing to do a test and the one picking foo or bar, basically de-correlating things. ;-) With that hack you get 49.933% vs. 50.0669%.

FireFox uses Java's pseudo RNG, which seems to behave a little bit nicer in this example, but is known to have other problems.