Hacking the JavaScript Lottery

January 2016 boasted a Powerball jackpot of 1.5 billion dollars. This generated a lot of interest in the lottery and the Los Angeles Times released a simulator where you start with 100 dollars and play until that is gone. I had seen previous work for predicting Java’s Math.random() and thought it would be a fun project to replicate for the browser.

The first step is to find the algorithm used in the browser’s pseudo random number generator. Since I use Chrome I began searching through the source code of Chrome’s Javascript engine, V8. During this search I came across a V8 blog post stating that they would be switching to XorShift128+ as it offers a higher quality random distribution. The blog post also stated that Firefox and Safari were in the process of switching over to this algorithm as well. One target, how convenient!

XorShift128+

Knowing that I had to wait for a few months for those versions of the browsers to be released, I got to work on the algorithm. The algorithm has two state variables ( stateZero and stateOne ). Each iteration, stateOne is updated by a combination of XORs and shifts of the two state variables. StateZero gets the previous value of stateOne . Everything in the following Python code is ANDed with ((1<<64)-1) in order to simulate 64 bit integers.

`def xs128p(state0, state1, browser):    # save states to temp variables for operating    s1 = state0 & ((1<<64)-1)    s0 = state1 & ((1<<64)-1)        # generate next state1    s1 ^= (s1 << 23) & ((1<<64)-1)    s1 ^= (s1 >> 17) & ((1<<64)-1)    s1 ^= s0 & ((1<<64)-1)    s1 ^= (s0 >> 26) & ((1<<64)-1)        # update state0    state0 = state1 & ((1<<64)-1)    # update state1    state1 = s1 & ((1<<64)-1)        # return updated state and the pseudo random number    generated = (state0 + state1) & ((1<<64)-1))    return state0, state1, generated`

Symbolic Execution

Now that I understood the algorithm, I could attack it. Being particularly fond of symbolic execution I turned to my good friend Z3 . Z3 is an SMT solver developed by Microsoft Research. SMT solvers take in logical formula and will resolve whether the constraints you place on that formula are satisfiable. For example, the formula (A & B) is satisfiable (will resolve True) if the variables A and B are both True. If we add the constraint (A & B & A == False) then the formula is no longer satisfiable.

What is even cooler is that you can also represent arithmetic and bitwise operations in Z3. This provides a lot of room for emulating code and solving for inputs that create certain outputs. I’ve used this a few times with success in c apture the flag style competitions . With this I set out to create a symbolically executed XorShift128+ algorithm in Python. The goal being to recover the state of the browser’s random number generator given random numbers generated from the browser.

The code starts by declaring two 64 bit symbolic variables in Z3 to represent the two state variables. These initial variables are saved for later use in the ostate (original state) variables and then assigned to sym_state (symbolic state) variables. The sym_state variables will be updated throughout the symbolic execution. Also declared are a Z3 Solver and a list for storing conditions.

`ostate0, ostate1 = BitVecs(‘ostate0 ostate1’, 64)sym_state0 = ostate0sym_state1 = ostate1slvr = Solver()conditions = []`

JavaScript’s Math.random() generates pseudo-random decimal values between zero (inclusive) and one (exclusive). Given three of these numbers generated (consecutively) we can recover the state of the random number generator and predict future values.

The following is a quick JavaScript snippet to be run in the browser’s console that will print 5 random numbers.

`nums = []; for(var i=0; i<5; ++i) {     nums.push(Math.random()) }; console.log(nums);`

Now our sharp readers are probably wondering, “the algorithm gives back 64 bit unsigned integers, where are these decimal values coming from?” That’s a great question and the answer is that it varies by browser. The 64 bit integers are converted to doubles . Glossing over some intricacies, doubles consist of a sign, mantissa, and exponent and evaluate to sign * mantissa * 2^exponent. The mantissa is stored in 52 bits of the number, the exponent gets 11 bits, and the sign gets 1 bit as usual. This adds up to a nice round 64 bits.

In Chrome’s JavaScript engine (V8) the 64 bit uint is treated as the mantissa by ANDing the value with hex 0xFFFFFFFFFFFFF ((1<<52)-1). That value is then ORed with 0x3FF0000000000000 to get a value between one and two. Then 1.0 is subtracted from that value to get a value between zero and one.

In Firefox the 64 bit uint is ANDed with 0x1FFFFFFFFFFFFF ((1<<53)-1) then divided by 0x20000000000000 (1<<53) to get a value between zero and one.

In Safari’s JavaScript engine (WebKit’s JavaScriptCore) the 64 bit uint is similarly ANDed with 0x1FFFFFFFFFFFFF ((1<<53)-1), however, it is then multiplied by (1.0 / (1 << 53)) to produce a value between zero and one.

For each double we retrieve from the browser we can then recover part of the unsigned integer that was generated. Given the simplicity of the Firefox code, we will use that from here on out in the examples. Here we take the doubles (in the list dubs) and multiply them by (1 << 53) in order to recover the the lower 53 bits of the randomly generated number.

`for idx in xrange(3):    generated.append(dubs[idx] * (0x1 << 53))`

Next we run three iterations of the symbolic XorShift128+ algorithm. The function returns the updated symbolic state variables and also the conditionals generated in that iteration.

`for ea in xrange(3):    state = sym_xs128p(slvr, sym_state0, sym_state1, generated[ea], browser)    sym_state0, sym_state1, ret_conditions = state    conditions += ret_conditions`

The symbolic XorShift128+ algorithm is pretty similar to the non-symbolic one. It follows the same algorithm except it uses the symbolic variables created earlier.

As a note, Z3 has two right shifts. It has a arithmetic right shift and a logical right shift. It uses the arithmetic shift when shifting with the >> operator. So the code must use the logical shift LShR or you will spend hours being confused, yea…

Following the normal algorithm operation, the code creates a condition and associates an implication with this condition. The implication or constraint being that the symbolically generated random number ANDed with (1<<53) is equivalent to our recovered number.

`# Symbolic execution of xs128pdef sym_xs128p(slvr, sym_state0, sym_state1, generated, browser):    s1 = sym_state0     s0 = sym_state1     s1 ^= (s1 << 23)    s1 ^= LShR(s1, 17)    s1 ^= s0    s1 ^= LShR(s0, 26)     sym_state0 = sym_state1    sym_state1 = s1    calc = (sym_state0 + sym_state1)     condition = Bool(‘c%d’ % int(generated * random.random()))    # Firefox number    impl = Implies(condition, (calc & 0x1FFFFFFFFFFFFF) == int(generated))`
`slvr.add(impl)    return sym_state0, sym_state1, [condition]`

With the returned conditions we can then ask the solver whether the execution is satisfiable. If it is then we can recover the initial values of our XorShift128+ state and then use the non-symbolic algorithm to confirm and predict future values.

`if slvr.check(conditions) == sat:    m = slvr.model()    state0 = m[ostate0].as_long()    state1 = m[ostate1].as_long()`

Winning the Lottery

Fast forward a few months to when Firefox and Chrome have both been updated to include the new pseudo random number generator. Time to revisit the lottery page . On the page you can “Quick Pick”, letting the page choose your lotto numbers or you can enter your own numbers. We’ll go ahead and enter our own.

I started by getting five values from Math.random() using the console (three to generate, two to confirm). Entering those numbers into the Python script we can recover the state of the browser.

Now we need to look at how the LA Time’s application generates the winning numbers. I was very pleased to find clearly named functions and commented code, a luxury I often work without.

In short, it generates an array of possible values for the lottery numbers (1–69 inclusive). Using Math.random() it selects 5 of those values, removing each selected value from the array so it can not be chosen twice. It does the same for the mega number which can have a value between (1–26 inclusive).

`function getWinning(max) {    // Create possible user numbers array     var possUserNumbs = [];     for (var i=1; i<(max+1); i++) {        possUserNumbs.push(i);    }    // Quick pick winning user numbers array     var userWinningNumbs = [];    for (var j = 0; j<5; j++) {        userWinningNumbs.push(getRandomWinningNumbers());    }    // Gets random numbers and removes them after use    function getRandomWinningNumbers() {        var randomIndex = Math.floor(Math.random()*possUserNumbs.length);        return possUserNumbs.splice(randomIndex, 1)[0];    }    // Reorder from smallest to largest    userWinningNumbs.sort(function(a,b) {return a-b; });    return userWinningNumbs;} function getMega(megaMax) {    // Create possible user mega numbers array    var possMegaUserNumbs = [];    for (var i=1; i<(megaMax+1); i++) {        possMegaUserNumbs.push(i);    }            var randomIndex = Math.floor(Math.random()*possMegaUserNumbs.length);    return possMegaUserNumbs.splice(randomIndex, 1)[0];}// view-source:http://graphics.latimes.com/powerball-simulator/`

So with the recovered state the code generates the five random numbers that were generated in the console. Then it will generate six more following the same procedure to generate the winning numbers and the mega number.

Using that I went to the webpage and didn’t win the lottery… Huh? The code checked out in the console. What if other things were calling Math.random()? Digging into the other code running on the page I saw quite a few places where Math.random() was called. For reproducibility I installed uBlock to simplify the number of scripts running on the page.

This left an LA Times’ analytics script as the only thing calling Math.random(). In Chrome, Math.random() was called twice for each click on the page and in Firefox it was called once for each click.

With that information I got the result of five Math.random() calls from the console. I then pasted those into the Python script and ran it. Once that spit out the winning numbers I used one click to put focus on the number entry fields and then navigated between them using Tab to minimize calls to Math.random(). Then one more click to hit the Play button. So for Firefox the script needs to simulate seven calls to Math.random() before generating the winning lottery numbers and in Chrome the script needs to simulate nine. Knowing this I added a convenient arrow to point out the winning numbers in the script’s output.

`\$ time python xs128p.py BROWSER: chrome [0.8817331322829662, 0.31765120036119443, 0.3301985901101909]0.842479503507     [9, 29, 55, 58, 66] 90.783537328316     [9, 23, 29, 58, 65] 230.126154072006     [22, 28, 58, 60, 65] 110.827757042877     [22, 29, 30, 59, 65] 200.410168206899---> [23, 29, 52, 59, 65] 22`
`real 0m41.021suser 0m40.920ssys 0m0.084s`