Practical `java.util.Random` LCG attack using LLL reduction

truncated_java_random.md

Practical java.util.Random LCG attack using LLL reduction

An easy-to-use Python script to sync up with the state of a java.util.Random generator after supplying a few samples. The internal seed has 48 bits, and every sample you give to the program will give some amount of bits of information. Here is a table to get an idea of how many samples you should provide per amount of bits in your input number:

bits	bound	samples (±)
4	16	25
6	64	12
8	256	8
16	65536	4
32	4294967296	2

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

Recovering the state from nextInt() or nextLong() calls without arguments is trivial, as they give 32 bits of information in one number, while the whole seed is only 48 bits. Then only 16 bits have to be brute-forced.

It gets harder when numbers are truncated meaning only 8 bits are shown per number for example (0-255). The program is meant for these types of situations and can recover the state perfectly from only a few samples, cloning the generator and allowing you to generate the 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:

$ python3 truncated_java_random.py
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.

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}")