# “Power of Two” LCG Cracker

This program can accurately predict the output of `java.util.Random`

‘s `nextInt(int bound)`

method, when `bound`

is a power of two and you have at least three samples.

If you want a more generic cracker, please use Randcrack by fransla.

## Usage

```
$ go run main.go
Usage of main:
-bound int
Bound value (argument passed to nextInt())
-continue
Find all possible matches (only do this if the output was wrong the first time)
-gen int
How many values to predict (default 5)
-samples string
List of known outputs (comma or space separated)
```

Example with sample values `53399, 58914, 24327`

and a bound of `65536`

. This only takes a few seconds to run.

```
$ go run main.go -bound 65536 -samples "53399, 58914, 24327"
======
Success! Found starting state 229349101478606 (1749794781<<17 + -56626)
Generating next 5 outputs:
0: 29132
1: 29127
2: 44688
3: 49749
4: 52045
======
```

These values were generated with `jshell`

as seen below. You can confirm the predicted values match :).

```
jshell> Random rand = new java.util.Random();
...>
rand ==> [email protected]
jshell> rand.nextInt(65536);
$2 ==> 53399
jshell> rand.nextInt(65536);
$3 ==> 58914
jshell> rand.nextInt(65536);
$4 ==> 24327
jshell> rand.nextInt(65536);
$5 ==> 29132
jshell> rand.nextInt(65536);
$6 ==> 29127
jshell> rand.nextInt(65536);
$7 ==> 44688
jshell> rand.nextInt(65536);
$8 ==> 49749
```

# How does it work?

`java.util.Random`

is not cryptographically secure, nor does it claim to be. There are a range of tools across the internet that allow you to predict future outputs, given a few input samples.
However, `java.util.Random`

has a special case for when `bound`

is a power of two that most of these tools don’t cover. My tool is designed specifically for this.

## Why it sucks

The special case is seen below:

```
public int nextInt(int n) {
if (n <= 0)
throw new IllegalArgumentException("n must be positive");
if ((n & -n) == n) // i.e., n is a power of 2
return (int)((n * (long)next(31)) >> 31);
int bits, val;
do {
bits = next(31);
val = bits % n;
} while (bits - val + (n-1) < 0);
return val;
}
```

The specific line in question is `return (int)((n * (long)next(31)) >> 31);`

.

`next(n)`

will take the current internal state (or “seed”), perform an LCG iteration, and output `n`

pseudo-random bits, as seen below:

```
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
```

At the end, the final `(48 - n)`

bits are dropped. In this case, that’s `(48 - 31) = 17`

bits. The state itself is only 48 bits in size, leaving us with 31 bits remaining.

## How we actually break it

So, given a sample value, only the first 31 bits influenced the output. Because of this, we can brute-force the first 31 bits independently of the rest. On a modern computer, `2^31`

is a miniscule search space.

Then, once we’ve found the first 31 bits, we need more output samples to find the remaining 17 bits. So, we can simply guess from `(firstBits << 31)`

to `(firsBits << 31) + 2**17`

until we find a state that outputs the rest of our samples when iterated. Once we’ve reconstructed the state/seed, we can simply start predicting future values :).

Is there a better way of doing this? Almost certainly. But, the search space for a straight brute-force is tiny and only takes a few seconds on a modern CPU.

# Credits

Randcrack by fransla for the inspiration and Go re-implementation of Java’s LCG ðŸ™‚