XorShift128+ Backward

Recovering Previous States from the Xor Shift 128 Plus Algorithm

This article is a follow up to our previous post, Hacking the JavaScript Lottery. In that post we wrote a Python Z3 implementation which utilized symbolic execution in order to recover the state of the XorShift128Plus pseudo-random number generator (PRNG) used by most major browsers. Shortly after publishing, Chrome (specifically V8, Chrome’s JavaScript engine), updated and the SAT solver was no longer able to find valid solutions.

A few users reported this issue but time did not allow for digging into the source code and tracking down what was wrong. Thankfully, Github user psrok1 discovered the source of the problem in NodeJS’s source code. V8 generates many pseudo-random numbers and stores them in a buffer for fast retrieval by later calls Math.Random(). The issue was that this buffer was being read back to front, instead of in the order that the numbers were generated.

There is a statistical test for uniformly distributed random numbers called Big Crush. The reason all the browsers switched to the XorShift family of algorithms was that the old PRNGs used failed to pass statistical tests, like Big Crush. While there was some discussion about a predecessor algorithm, Xsadd, failing statistical tests when the values were bit reversed, no one was talking about the XorShift buffer being read backward.

A visual representation of randomly generated numbers from jandemooij.nl.

Given that information, it was time to fix the XorShift prediction code. The XorShift128Plus algorithm uses two state variables to generate pseudo-random values. We’ll refer to these as state0 and state1. Each round, state0 gets the value that state1 had, and state1 is updated through a series of mathematical operations. Let’s look at it in code.

The issue we faced was that once we recovered the state variables using Z3, we could go forward, that is, predict future values of the algorithm. The update made it necessary for us to also go backward, finding previous states from the current state. My first thought was that I would need Z3 for this, since I assumed some of the data was lost in the shift operations. However, when looking for shortcuts to save the symbolic executor some work, I found that the algorithm was entirely reversible.

Sign up to get our latest blogs

Recovering the previous state1 is easy as that variable is stored entirely in the current state0 variable (line 8).

prev_state1 = state0

Recovering the previous state0 will require a little more work. The four operations that need to be reversed are on lines 4 through 7. Lines 6 and 7 are easily reversed, as s0 is simply the previous state1 which is unmodified. So we can xor the current state1 with the current state0 shifted right 26 bits (line 7). Then we can xor that result with the current state0 again (line 6).

prev_state0 = state1 ^ (state0 >> 26)
prev_state0 = prev_state0 ^ state0

Next, on line 5, we can reverse that operation 17 bits at a time. Let’s keep in mind the properties of xor.

• It is commutative meaning that the order of inputs doesn’t matter A^B = B^A. A counter example to this is division, where the order does matter (5/2 is different from 2/5).
• It is associative, meaning that changing the grouping does not change the outcome. Again, using division as a counter example, (10/5)/3 is different from 10/(5/3).
• It is a self-inverse operation, meaning it is to itself what subtraction is to addition.
• Its identity element is zero, meaning that any number xord with zero is unchanged.

Using all this, we know that A^B^A = B, since A^A is zero, B^0 = B. Since the high 17 bits are unmodified due to the right shift we can use those high bits to recover the next 17 bits. Once those bits are recovered we can use them to recover the next 17, and so on.

Visually, if we have a 64 bit value whose original bits are the repeating 4 bits 1110, and we xor that original value with itself, right shifted 17 bits.

 11101110111011101 11011101110111011101110111011101110111011101110
^                  11101110111011101110111011101110111011101110111
-----------------------------------------------------------------_
 11101110111011101 00110011001100110011001100110011001100110011001

You can see the original bit pattern 1110 is preserved in the high 17 bits of the result, and the lower 47 bits (17–63) are changed due to the xor operation.

To reverse the operation we can then take those upper 17 bits and xor the next 17 bits against them, recovering part of the original number.

 11101110111011101 00110011001100110 011001100110011001100110011001
^        └-------> 11101110111011101 000000000000000000000000000000
-------------------------------------------------------------------
 11101110111011101 11011101110111011 011001100110011001100110011001

We repeat this operation twice more, with consecutive sets of 17 bits (until the last one, which only needs 13 bits, because 64 - 17*3 = 13) until we have recovered the complete original number.

 11101110111011101 11011101110111011 01100110011001100 1100110011001
^                          └-------> 11011101110111011 0000000000000
-------------------------------------------------------------------
 11101110111011101 11011101110111011 10111011101110111 1100110011001
...
 11101110111011101 11011101110111011 10111011101110111 1100110011001
^                                    └-----------┘---> 1011101110111
-------------------------------------------------------------------
 11101110111011101 11011101110111011 10111011101110111 0111011101110

In Python we can write a quick function to recover this number. We start with the top 17 bits, then we recover the top 34, then the top 51, then the original number, just as we did above.

def reverse17(val):
    top34 = (val ^ (val >> 17)) & 0xFFFFFFFFC0000000
    top51 = (val ^ (top34 >> 17)) & 0xFFFFFFFFFFFFE000
    original = (val ^ (top51 >> 17))
    return original

That operation takes care of line 5 of our original algorithm s1 ^= (s1 >> 17). With this newly gained knowledge, we can quickly write a function to undo line 4 as well s1 ^= (s1 << 23). Instead of working from the high bits downward, we start with the low 23 bits and work upward.

def reverse23(val):
    bot46 = (val ^ (val << 23)) & 0x3fffffffffff
    original = (val ^ (bot46 <<  23)) & 0xFFFFFFFFFFFFFFFF
    return original

Putting all that together, we can now do the XorShift128Plus algorithm backward! We can rewrite the reverse17 and reverse23 functions a little more succinctly.

Now once we recover the two state variables from Z3, if our target browser is Chrome we can feed the state values into this algorithm to predict the backward values from Math.Random(). This allowed me to get the lottery predictor script working in Chrome again.

There is a theoretical limitation on matching the values generated in V8. Values in V8 are generated ‘forward’ into a buffer then read in reverse. If you were predicting values near the low end of the buffer, exhausted the values and required that a new buffer be generated, your values would no longer match up as this algorithm goes strictly backward. The frequency of this occurring depends on the size of their random number buffer.

The original issue in which this solution was developed can be found here. The updated code is on Github. Thanks again to user psrok1 for finding the root cause.

Authored by Douglas Goddard, an Analyst at Independent Security Evaluators.

Twitters: @ISESecurity

Sign up to get our latest blogs