mathrandomcrack

Cracking JavaScript V8 Math.random() and xs128 from arbitrary bit leaks.

This is largely inspired by https://imp.ress.me/blog/2023-04-17/plaidctf-2023#fastrology.

Disclaimer: This tool is made for educational purposes only. Please don't use it to break into stuff.

Archived tool

This tool is now archived and will no longer receive updates. V8 implementation of Math.random() was updated with this commit. It changes the internal PRNG from XorShift128 to the nonlinear XorShift128+, effectively breaking the attack implemented here.

Note that seed-recovery attacks based on symbolic execution and SMT solvers should still work with minor tweaks.

What is this?

This tool can be used to recover the internal state of the V8 implementation of Math.random() knowing enough bits of randomly generated values. The values don't have to be successive and the position of the known bits can vary.

You can use the CLI to recover all the possibles internal states of Math.random() in one of the following situations:

• You know more than 4 values generated by Math.random().
• You know enough integer values generated by Math.floor(Math.random() * k + b). The larger k, the less values you need.
• You know enough approximation of values generated by Math.random(), meaning you know bounds for each value and therefore know a few bits of each value. The better the bounds, the less values you need.

After the internal state is recovered, this tool is also able to predict all the next and previous returned values of Math.random().

How do I protect my applications against this?

Never use Math.random() for anything related to security. If someone recovering randomly generated values is bad for your application, use the cryptographically secure Crypto.getRandomValues() method instead.

I just want to run it

You should have Python3 and Sage installed.

Example usages:

$ # Generate the 10 next values from known consecutive outputs of Math.random()
$ python3 -m mathrandomcrack --method doubles --next 10 ./samples/doubles.txt
Found a possible Math.random internal state
Predicted next 10 values: [0.3826651187438035, 0.7375710819016986, 0.21863364189462264, 0.8093784172561101, 0.6964292873208223, 0.6272218068697356, 0.6100738714256938, 0.25258737620214433, 0.3696190724647912, 0.5292798994490209]

$ # Generate the 5 previous and 5 next integers from known consecutive values of Math.floor(Math.random() * 36)
$ python3 -m mathrandomcrack --method scaled --next 5 --previous 5 --factor 36 --output-fmt scaled ./samples/scaled_values.txt
Found a possible Math.random internal state
Predicted previous 5 values: [21, 1, 22, 4, 5]
Predicted next 5 values: [20, 29, 1, 22, 20]

The samples directory contains example files for various use cases. There should be one leaked value of Math.random() per line and it is possible to use an empty line to represent an unknown output of Math.random().

For more information about the CLI, you can run python3 -m mathrandomcrack --help.

I have a more complex use case

If you manage to leak enough bits (> 120) from multiple Math.random() outputs, you can directly use the recover_state_from_math_random_known_bits function in mathrandomcrack.py to recover the initial internal state of Math.random().

You can also try to use recover_seed_from_known_bits in xs128crack.py if you just want the XorShift128 state and don't care about Math.random() stuff.

How does it work?

Math.random() is defined as a function that returns pseudo-random numbers between 0 and 1 and does not provide cryptographically secure random numbers. Under the hood, in V8 (the JavaScript engine used by Chrome and NodeJS), random numbers are generated using the fast, reversible, seed-based, deterministic PRNG called XorShift128.

Cracking XorShift128 initial state

XorShift128 is a simple PRNG with a 128-bit internal state. It uses only XOR and shift operations and the transition from a state to the next is linear. Each bit of a XorShift128 state can be expressed as a linear combination of pre-determined bits of the initial state. Knowing enough total bits from arbitrary states, the initial state can be recovered through basic linear algebra in GF(2).

Initial XorShift128 state recovery from known bits is implemented in xs128crack.py.

Note: many other projects like v8_rand_buster use symbolic execution with z3 to recover the initial state but this is not viable if your known bits are scattered over too many states.

Recovering Math.random() internal state

Math.random() doesn't directly output XorShift128 random values. It generates a cache of 64 values at a time and returns them one by one in reverse order. This makes the internal state recovery a little tricky because we have to account for the initial position of the cache index for the first known state. If only a few outputs are known (< 64), there will be up to 64 possible internal states due to the unknown position of the cache index.

Internal state recovery is implemented in mathrandomcrack.py.

Tests

You can run the tests to make sure everything works using unittest.

$ python3 -m unittest discover -s tests

References

• https://blog.securityevaluators.com/hacking-the-javascript-lottery-80cc437e3b7f - "Hacking the JavaScript Lottery" article from 2016.
• https://security.stackexchange.com/a/123554 - "Predicting Math.random() numbers?" question on StackExchange.
• https://github.com/d0nutptr/v8_rand_buster/tree/master - Another implementation to crack XorShift128 using z3.
• https://imp.ress.me/blog/2023-04-17/plaidctf-2023#fastrology - The writeups of 2023 PlaidCTF challenges by @y4n that inspired me to make this tool.