Pseudo-Random Number Generators (PRNG)

Often the default random function in whatever language is not cryptographically secure, making it possible to predict values

Python: `import random` = Mersenne Twister

The default Python random module is very fast, but not very secure. If the application allows you to get 624 or more random values from it, you can crack the random seed used by the generator to predict future values. You can also use this to know values that are generated by the application, but not shown to you, like generating a key right after showing you 624 random values.

The mersenne-twister-predictor library is a nice Python implementation of this attack. It can recreate the internal state of Python's random module, after submitting 624 32-bit values. Then the regular python random interface is available to make perfect predictions for the future:

import random
# pip install mersenne-twister-predictor
from mt19937predictor import MT19937Predictor

predictor = MT19937Predictor()

for _ in range(624):
    x = random.getrandbits(32)
    predictor.setrandbits(x, 32)  # Submit samples here

# When enough samples are given, you can start predicting:
assert random.getrandbits(32) == predictor.getrandbits(32)

I made a writeup of a challenge where you had to crack the seed after 624 random values, to generate the same key as the application would encrypt the flag:

Note that this library is not limited to 32-bit numbers, larger numbers divisible by 32 are also possible. These are made up of multiple smaller 32-bit numbers, and thus also require fewer total samples because each one gives more information:

# 512*40 = 20480 > 19968 (required) ✔️
for _ in range(40):
    x = random.getrandbits(512)
    predictor.setrandbits(x, 512)

assert random.getrandbits(32) == predictor.getrandbits(32)

When the code you are trying to break leaks information after the numbers you want to retrieve, we need to predict the past rather than the future. Luckily this is fairly easy by just implementing an algorithm that untwists the internal state so that we can even reach to before the state was leaked. The following functions can be added to mt19937predictor.py MT19937Predictor class to add an interface for offsetting the state by any amount, even backward.

Patch with untwisting

    def untwist(self):
        '''Go back 624 states by undoing the one twist operation.
        Source: https://jazzy.id.au/2010/09/25/cracking_random_number_generators_part_4.html
        '''
        for i in range(N-1, -1, -1):
            result = 0
            # first we calculate the first bit
            tmp = self._mt[i]
            tmp ^= self._mt[(i + M) % N]
            # if the first bit is odd, unapply magic
            if tmp & UPPER_MASK:
                tmp ^= MATRIX_A
            # the second bit of tmp is the first bit of the result
            result = (tmp << 1) & UPPER_MASK
            
            # work out the remaining 31 bits
            tmp = self._mt[(i - 1 + N) % N]
            tmp ^= self._mt[(i + M-1) % N]
            if tmp & UPPER_MASK:
                tmp ^= MATRIX_A
                # since it was odd, the last bit must have been 1
                result |= 1
            # extract the final 30 bits
            result |= (tmp << 1) & (UPPER_MASK - 1)
            self._mt[i] = result

    def offset(self, n):
        '''Advance the internal state by n steps. May be negative to go backwards any amount.
        '''
        if n >= 0:
            [self.genrand_int32() for _ in range(n)]
        else:
            [self.untwist() for _ in range(-n // 624 + 1)]
            [self.genrand_int32() for _ in range(624 - (-n % 624))]

Imagine the following scenario where we want to recover the unknown values:

Recovering previous values

import random
from mt19937predictor import MT19937Predictor

# These are generated before our leak
unknown = [random.getrandbits(32) for _ in range(1000)]

predictor = MT19937Predictor()

for _ in range(624):
    # Sync the random state
    predictor.setrandbits(random.getrandbits(32), 32)

predictor.offset(-624)  # Offset by 624 to get the state before our leak
predictor.offset(-1000)  # Offset by 1000 to get the state right before the unknowns

# Now the predicted values will line up
assert unknown == [predictor.getrandbits(32) for _ in range(1000)]

Truncated samples (symbolic solver)

When samples are smaller than 32 bits, or less than 624 samples, you won't have enough to perfectly recreate the internal state. However, it turns out that statement solvers like Z3 that use symbolic execution can get constraints set to the samples, and then solve for the seed. This process will be a lot slower, but it may be your only option.

The symbolic_mersenne_cracker repository implements an easy-to-use symbolic solver using Z3 where you can feed it partial samples with for example 16 bits instead of 32, which it then solves and gives a synchronized random instance. It works by submitting binary strings with ? question marks for the unknown bits.

from symbolic_mersenne_cracker import Untwister
import random

ut = Untwister()

for _ in range(1337):
    x = random.getrandbits(16)
    ut.submit(bin(x)[2:] + "?"*16)

predictor = ut.get_random()

assert random.getrandbits(32) == predictor.getrandbits(32)

Tip: To solve a scenario where the solution isn't very simple like with getrandbits(), you can view the source code of the random module yourself or for going deeper even the C implementation. Then figure out what parts of getrandbits your function uses.

32-bit seed

As specified in the Initialization of a Mersenne Twister, a single w-bit seed should be used to generate all initial state values, where often w=32. This means there are only 4.294.967.296 possible initial state arrays, and when you have enough samples, this is simply brute forcible.

This problem was highlighted in PHP and make into a tool which cracks the seed of its mt_rand() function outputs, with a lot of flexibility in the samples:

The README explains how to use its arguments, which are pretty specific. With multiple samples, the syntax is essentially as follows repeatedly:

php_mt_seed [output_min] [output_max] [range_min] [range_max] ...

Where the output parameters speak for themselves, and the range is 0 2147483647 by default unless another argument is given to the random function.

For other implementations that also opt for a 32-bit initial seed, and no tool exists yet, you should recreate the algorithm as efficient as possible and then compare the outputs for each seed to the samples you gathered to find when it is correct. See Bash: $RANDOM for a similar example.

Note: Python's implementation is not vulnerable to this attack, because it uses a non-standard way of initializing with 624 individual 32-bit random integers (source). Other programming languages or libraries may do the same.

JavaScript: `Math.random()` = xorshift128+

Javascript has a few variants per browser. Chrome, Firefox, and Safari all do slightly different things when it comes to generating random numbers. But Chrome uses V8 for JavaScript, and so does NodeJS. This makes it the biggest target.

The Math.random() function is not cryptographically secure, and with about 5 random numbers from it, one can crack the random state and predict future values.

PwnFunction made a great video explaining the attack and published a Python script that uses the Z3 solver to solve the random state and predict future numbers.

> Array.from(Array(5), Math.random)
[
  0.8971227301319089,
  0.6209246336108811,
  0.5512987330965515,
  0.4297735084849734,
  0.9373384773813349
]
// Save to 'sequence' in the Python script and run it
> Math.random()
0.446420067790525

Truncated samples (floored)

A more practical example is for situations where the leaked bits are truncated (eg. floored) to some smaller number of bits per sample. This could be for a simple activation code generator:

function generateCode() {
  return Math.floor(Math.random() * 100000);
}
// Examples: [42980, 1827, 17784, 87568, 36298]

This code only leaks some part of the random output as it is a rounded decimal, but with this limited information, we can still efficiently solve the state as found in another piece of research with the tool below. These solutions need more samples, around 15 to be consistent. Then the solver can be run again with these inputs to predict past and future values.

See the README.md for more details, as the 64-wide cache from v8 makes it slightly confusing:

Java: `java.util.Random()` = Linear Congruential Generator

Java's random number generator uses a Linear Congruential Generator (LCG). These generators are really fast but also really insecure. The internal state is only 48 bits long and can be recovered with only a few samples. For example, it doesn't help that the int output values from the generator are simply the first 32 bits of the state, allowing you to brute-force the last 16 bits if you have another sample you can compare with.

This idea is explained here and implemented well for a few functions that give a lot of information:

For attacking general LCGs, see this writeup which shows a few different techniques depending on how much of the constants are known

Truncated samples

The above method is possible because you get a big part of the internal state in one single number (like and int). But in some cases, you can't get all this information, only small numbers that are generated using a range. This is where another more involved method comes in that can analyze the patterns between numbers in order to recover the internal state.

Getting a number from the java.util.Random() generator works by truncating the state (seed) with a number of bits. If you need a 32-bit number, the first 32 bits of the seed are given and the seed rotates for the next time. If you need an 8-bit number the first 8 bits are given and the seed is rotated again. This means that using 8-bit numbers you only get a small part (top 8 bits) of the seed, and then it already rotates to the next seed. That is the problem we are trying to solve.

It turns out this can be done using LLL Reduction, a highly useful algorithm in cryptanalysis. The math of this all is pretty complex, but implementations already exist allowing you to use them. This gist has a few different methods for cracking general LCGs and can be applied to Java specifically by only changing the constants.

I made another gist that is specific to Java's Random() class and has an easy-to-use CLI.

Information & Example

The internal seed has 48 bits, and every sample you give to the program will give some amount of bits of information. In the gist is a table to get an idea of how many samples you should provide per amount of bits in your input number.

It tries to recover the state from numbers generated using the Linear Congruential Generator (LCG) in Java. For example:

Random random = new Random();

int sample = random.nextInt(256);  // Single 8-bit number
int[] samples = random.ints(8, 0, 256).toArray();  // 8x 8-bit numbers

The program is meant for situations where numbers returned from the generator are small, and can recover the state perfectly from only a few samples, cloning the generator and allowing you to generate future values beforehand.

Warning: This script currently only works for numbers generated with an upper bound of a power of 2. This means a number generated like random.nextInt(256) will work, but something like random.nextInt(200) likely won't. This is because, in the case of not having a power of 2, the LCG might generate multiple numbers per call, giving us an unknown amount of missing numbers in the samples.

Example

Random random = new Random(1337);

int[] samples = random.ints(8, 0, 256).toArray();  // Generate 8x 8-bit numbers to give the program
System.out.println(samples);  // { 168, 44, 176, 223, 226, 247, 230, 207 }

int[] secrets = random.ints(8, 0, 256).toArray();  // Generate 8 more secret numbers
System.out.println(secrets);  // { 44, 164, 241, 235, 37, 5, 81, 252 }

Now we will feed the samples into the Python program. The numbers are generated from 0-255, which is 8 bits:

Known bits: 8
Input: 168, 44, 176, 223, 226, 247, 230, 207 
States found: [185753720734415, 48973695446062, 194004564009889, 246107133972888, 248619153362371, 272076196875794, 252907395951029, 228694819430428]
Guesses: [44, 164, 241, 235, 37, 5, 81, 252]

Tip: To get more control over what numbers are guessed after the state has been cracked, you can use the java-random library to clone the generator by setting its internal state to one of the found states, and then calling the function on it to extract the numbers you need.

Python Script (truncated_java_random.py)

truncated_java_random.py

# Source of algorithm: https://gist.github.com/maple3142/c7c31d2e5893d524e71eb5e12b0278f0

from sage.all import *

# Constants for `java.util.Random`
BITS_TOTAL = 48
a = 0x5DEECE66D
c = 0xB

m = 2**BITS_TOTAL


class LCG:
    """Simple Linear Congruential Generator implementation"""

    def __init__(self, a, c, m, seed):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed
        self.counter = 0

    def next_state(self):
        self.state = (self.a * self.state + self.c) % self.m

    def get_bits(self, n):
        return self.state >> (BITS_TOTAL - n)


def get_L(k):
    M = matrix([m])
    A = matrix([a**i for i in range(1, k)]).T
    I = matrix.identity(k - 1) * -1
    Z = matrix([0] * (k - 1))
    L = block_matrix([[M, Z], [A, I]])
    return L


def solve(truncated, bits_known):
    """Solve the truncated states in `truncated`, given `bits_known` known bits"""
    bits_unknown = BITS_TOTAL - bits_known

    K = [c]
    for i in range(1, len(truncated)):
        K.append((K[-1] + c * a**i) % m)
    K = vector(K)
    L = get_L(len(truncated))
    shifted = [(x * 2**bits_unknown - K[i]) % m for i, x in enumerate(truncated)]
    B = L.LLL()
    sys = vector(shifted)
    sby = B * sys
    ks = vector(round(x) for x in sby / m)
    zs = B.solve_right(ks * m - sby)
    tmp = sys + zs
    results = [(tmp[i] + K[i]) % m for i in range(len(tmp))]
    assert (L * vector(results)) % m == (L * K) % m  # Extra checking

    return results


def java_to_python(n):
    """Convert a Java integer to Python integer"""
    return n if n >= 0 else n + 2**32


def python_to_java(n):
    """Convert a Python integer to Java integer"""
    return n if n < 2**31 else n - 2**32


if __name__ == "__main__":
    from colorama import Fore, Style

    n_bits = int(input(f"Known bits: {Fore.LIGHTBLUE_EX}"))
    print(Style.RESET_ALL, end="")

    # Get user input
    truncated = [
        java_to_python(int(n)) for n in input(f"Input: {Fore.LIGHTGREEN_EX}").split(",")
    ]
    print(Style.RESET_ALL, end="")

    # Solve
    results = solve(truncated, n_bits)
    print(f"{Fore.LIGHTBLACK_EX}States found: {results}{Style.RESET_ALL}")

    # Create a clone
    clone = LCG(a, c, m, results[-1])

    guesses = []
    for _ in range(len(truncated)):
        clone.next_state()
        guesses.append(python_to_java(clone.get_bits(n_bits)))

    print(f"Guesses: {Fore.LIGHTRED_EX}{guesses}{Style.RESET_ALL}")

Bash: `$RANDOM`

The bash shell has a dynamic variable called $RANDOM you can access at any time to receive a random 15-bit number:

$ echo $RANDOM $RANDOM $RANDOM
3916 29151 6095

To seed this random number generator, it can be set directly to get the same values every time:

$ RANDOM=1337; echo $RANDOM $RANDOM $RANDOM
24879 21848 15683
$ RANDOM=1337; echo $RANDOM $RANDOM $RANDOM
24879 21848 15683

There are 2 different calculations depending on your bash version, which may make one seed give two different outputs.

The algorithm works by iterating a 32-bit integer internal seed every time you access it. This means that if you can sync up with the seed, you can predict all future values of the variable. Luckily, the calculations the algorithm performs are very fast meaning it is easy to try every possible 32-bit seed and compare the results with your expected values.

I looked at the bash source code to find out how it exactly works, and created a tool that uses the above idea to brute-force every seed in only a few seconds, supporting both bash versions:

PreviousCracking Signatures NextTiming Attacks

Last updated 3 months ago

Python: import random = Mersenne Twister