1
$\begingroup$

I heard that one can predict the output from Math.Random() of JavaScript, but another day I had an idea to combine Math.random() with Math.floor() to make it harder to predict, but a week ago I saw one user claimed that he can predict even if I used Math.floor() and that only takes 14 sample values to do that.

How is it possible mathematically?


The concrete construction in question is Math.floor(Math.random()*9000)+1000.

Various API specifications are here and there. Per this answer most browsers use Xorshift128+, possibly derived from this C source code.

In this comment the OP suggests that the question is about "Chrome's V8 implementation" and links to a Chromium commit.

New contributor
sqlbie is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ One is this Why is Math.random() not designed to be cryptographically secure? $\endgroup$ – kelalaka Mar 24 at 19:43
  • $\begingroup$ Do you understand why Math.random() is not secure and how you would go about determining the internal state? Can you adapt that process for the case where you only see the output of your transform? $\endgroup$ – bmm6o Mar 25 at 15:32
  • $\begingroup$ @fgrieu I removed a bunch of comment discussion on this question, but edited in the gist of it which refers to this answer as the algorithmic source which claims Xorshift128+ for all / most implementations, so it's reasonable to assume Xorshift128+ here I suppose (I also edited this info into the question). $\endgroup$ – SEJPM Mar 26 at 13:29
  • 1
    $\begingroup$ @fgrieu My question is related to Chrome's V8 implementation. They had changed the Xorshift128+ to something else, github.com/v8/v8/commit/… $\endgroup$ – sqlbie Mar 26 at 17:26
  • $\begingroup$ "Math.floor() function returns the largest integer less than or equal to a given number" - Maybe, I see a possibility of occurrences where Math.floor() output original Math.rand() output $\endgroup$ – sqlbie Mar 26 at 17:32
2
$\begingroup$

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, since 9000≥213, each output of Math.floor(Math.random()*9000)+1000 lets us be certain of up to 13 bits of s0+s1 (bits 63…51 for ChromX V8, bits 52…10 for Firefox/Webkit), and not being certain of the low-order j bits of that segment has probability less than 2-j.

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 13-j bits 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 described an 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 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.

$\endgroup$
  • 1
    $\begingroup$ Actually, in the comments to my answer, I outlined an attack (brief to fit within the allowed space of a comment) that allowed an attacker to get enough internal bits of the Firefox version to allow Gaussian elimination to recover the state... $\endgroup$ – poncho 2 days ago
  • $\begingroup$ @poncho: Won't challenge you on being first to post a solution! I linked to your nice comment. $\endgroup$ – fgrieu 2 days ago
  • $\begingroup$ @fgrieu This is a excellent write up. $\endgroup$ – sqlbie 2 days ago
  • $\begingroup$ @fgrieu Would love to see the stuff unspecified by ECMA-262 $\endgroup$ – sqlbie 2 days ago
  • $\begingroup$ @fgrieu I've downloaded it. You may remove now. $\endgroup$ – sqlbie 2 days ago
3
$\begingroup$

According to this answer, math.random uses a Linear Congruential Generator (although it is not clear to me if that's on one specific browser, or on all JavaScript implementations).

In any case, a Linear Congruential Generator is known not to be secure, in the sense that, given partial output (which the Math.floor( 9000 * Math.random() ) operation allows), someone is able to reconstruct the initial seed, and from that, reconstruct the entire sequence.

In particular, if the browser uses the popular XORSHIFT128+ RNG, and you are able to deduce 128 lsbits from the underlying 32 bit outputs, you can reconstruct the initial state (by solving some binary linear equations).

$\endgroup$
  • $\begingroup$ Question is how one can construct seed if one used Math.Floor? $\endgroup$ – sqlbie Mar 25 at 23:31
  • $\begingroup$ Math.floor() create different decimals to the original Math.rand() output $\endgroup$ – sqlbie Mar 25 at 23:32
  • $\begingroup$ The question is about Math.float combined with Math.random. It's my understanding that you need original outputs of Math.random to predict seed. With Math.float the original output get changed. $\endgroup$ – sqlbie Mar 26 at 17:21
  • 1
    $\begingroup$ @sqlbie: as for how you attack it, first of all, XORSHIFT128 is internally bitwise linear, and so if we get 128 (or a few more) linear equations, we can derive the seed. The output gives the high 13 bits or so (with some ambiguity at times) of the value s0+s1. So, we guess the top 10 bits of the initial s0; that gives us the top 10 bits of initial s1. then, the next 9 bits high output is a function of the top 9 bits of s0, top 9 bits of s1, and the bottom 9 bits of s1 - that allows us to deduce the bottom 9 bits of s1 (and so, 9 more linear equations). Each output gives us 9 more bits. $\endgroup$ – poncho 2 days ago
  • 1
    $\begingroup$ @fgrieu: "and from earlier s0 on bits 52..44, 29..21 (thru <<23), 40..38 (thru <<23 >>17), and 63..61 (thru >>17)."; that is, it's a linear function of those bits (and hence we can form a linear equation relating the bit we see and the bits they're a linear function of. The only bit that acts nonlinearly is the carry bit; we need to assume that. $\endgroup$ – poncho 5 hours ago

Your Answer

sqlbie is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.