The Math.random() in ECMA-262/JavaScript should return
a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudorandomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy.
There's nothing to say that it is cryptographically secure, therefore the only prudent thing is to assume that it is not.
But that's not a concrete attack, much less against "Chrome's V8 implementation" as asked. One first needs to examine how Math.random() is used. Here we get that the application uses Math.floor(Math.random()*9000)+1000.
ECMA-262 specifies IEEE 754-2008 double-precision 64-bit binary format (52 explicit bits of mantissa + 1 implicit) with "round to nearest, ties to even" rounding (causing a relative error at most 2-54)). It follows that Math.random() outputs a value in [0 … 1 - 2-53], and Math.floor(Math.random()*9000)+1000 outputs an integer about uniformly random in the set { 1000, 1001, …, 9999 }, thus with at most about ⌊log2(9000)⌋ ≈ 13.136 bits of entropy per output. The rest is unspecified by ECMA-262 and we need to dig into what implementations do.
My tentative analysis of the Chromium source there (lines 62/63 and what it links to), and that of Firefox 47.0 and Safari's Webkit (which is the clearest), concludes that the next value of Math.random() for these is as if generated by:
uint64_t state0, state1; // the 128-bit state
// update state and produce a double
double MathRandom(void) {
uint64_t s0 = state1; // notice the swap
uint64_t s1 = state0;
s1 = s1 ^ (s1 << 23);
s1 = s1 ^ (s1 >> 17) ^ (s0 >> 26) ^ s0;
state0 = s0;
state1 = s1;
if (Firefox || Webkit) // Firefox v47.0, Webkit 2019-07 thru 2020-02
return (double)( (s0+s1) & (((uint64_t)1<<53)-1) ) / ((uint64_t)1<<53);
else // ChromX V8, 2019-01 thru 2020-02
return (double)( s0 >> 12 ) / ((uint64_t)1<<52);
}
That's significantly different from the Xorshift128+ source linked in the question: the shift constants are different, and for ChromX V8 the 64-bit addition is gone.
In all versions, because 9000 ≥ 213, each output of Math.floor(Math.random()*9000)+1000 lets us be certain of up to 13 bits (of bits 63…51 of s0 for ChromX V8, of bits 52…10 of s0+s1 for Firefox/Webkit). Being certain of the top j bits of that segment has probability more than 1-2j-13.
The ChromX V8 version is entirely linear: each of the 128 bits of the state is a combination by XOR of the bits of the previous state, thus (by induction) of any earlier state¹. 52 bits of the state make it directly to the output of Math.random, thus the above j ≲ 13 bits that we get at each step directly are state bits. With a little more than 10 (computed as ⌈128/13⌉ ) consecutive outputs² from the same thread, the state of the generator can be found by Gaussian elimination and the rest (before/after) predicted. That's a mere technicality. I'll try to link to a code snippet.
The Firefox/Webkit version is harder, because it has the addition modulo 264 of the original Xorshift128+. Still, while the output is non-linear, the state evolves linearly, and an efficient attack is feasible with a little more consecutive outputs², by expressing what's known in the framework of a satisfiability problem and submitting to a state of the art SAT solver. That's essentially what was done in this attack, yet with much more bits of state leaking at each step, making it easier.
In these three comments, Poncho describes an explicit attack strategy for the Firefox/Webkit version. That goes:
- We assume that the values obtained from
Math.floor(Math.random()*9000)+1000 are enough to consistently give us the 9 bits 52…44 of the the fraction of bits 52…40 of s0+s1 that we can observe; if not, we guess a few bits, multiplying our later work by a small factor (no longer considered below).
- We guess the 9 corresponding bits 52…40 of the initial
state1, and of the carry bit that occurs from bit 39 to 40 in the addition s0+s1 for the first output that we can observe. In s0+s1, the operand s0 is that of our guess, thus we can compute the corresponding new s1.
- Each of the 9 bits of that new
s1 is a known linear combination of bits of the initial state, and that gives us 9 equations for a Gaussian elimination aiming at finding the full initial state.
- Moving to the next output, we need to guess only the carry bit that occurs from bit 39 to 40 in the addition
s0+s1 in order to maintain running knowledge of the corresponding new s1, and obtain 9 additional equations for Gaussian elimination.
- With about ⌈(128-9)/9⌉ = 14 outputs of the RNG, we have enough equations to solve the system, allowing to validate our guesses.
- We have to solve in the order of 29+14 systems, which is quite manageable.
Notes:
¹ That's a design feature of Xorshift128+, making it easy to compute an arbitrary portion of the output sequence.
² We could also exploit outputs at known positions in the output, e.g. one out of N values in the set { 1000, 1001, …, 9999 } obtained by a particular player in a game involving a known number N of players.
