A while back a friend of mine hosted a programming competition where you were given 9 random numbers one at a time and you had to guess the rank (the sorted position amongst the 9) of each as they are coming in. The goal was to submit a strategy in Java that will maximize the number of these games won. The best solution can guess right about 3.3% of the time but I figured if he was going to let me execute arbitrary code I might as well cheat and guess correctly 100% of the time. So I set out to see if I can predict the rest of the numbers in the stream after seeing just one.

So I started digging through `java.util.Random`

's source and found that it is just a linear congruential generator which can be easily to cracked to obtain the original seed. The rest of this post will show how (if you just want to get the code, you can find it here.

A quick refresher on how LCGs work: starting with a seed `x`

, the next pseudorandom number generated is given by _{0}`x`

, for some fixed constants _{1} = a * x_{0} + c mod m`a`

, `c`

, and `m`

. So for example let's say `a = 3`

, `c = 5`

, `m = 7`

and we start with the seed `x`

, then the next few random numbers generated will be: _{0} = 0`5 = 3 * 0 + 5 mod 7`

, `6 = 3 * 5 + 5 mod 7`

, `2 = 3 * 6 + 5 mod 7`

, `4 = 3 * 2 + 5 mod 7`

, etc.

It should be clear that if I gave you a "random" number generated from this process (e.g., `x`

), you can predict the next number by applying the formula yourself (e.g, _{i} = 2`x`

)._{i+1} = 3 * 2 + 5 mod 7 = 4

The relevant method in `java.util.Random`

looks like this (where `m=2`

or in other words, a 48-bit number is generated with each iteration):^{48}

```
public
class Random implements java.io.Serializable {
private final AtomicLong seed;
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
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));
}
/* ... */
}
```

Unlike our toy example, each call to `next`

only returns `bits`

number of the top bits instead of the whole 48-bit number generated so there's a bit more work to do.

Now going back to the post title, how is `next(bits)`

used for `Math.random()`

? If you dig into the java source code you will find that `Math.random()`

is just a call to `nextDouble()`

on a static instance of `Random`

. And `nextDouble`

calls `next(bits)`

like this:

```
public double nextDouble() {
return (((long)(next(26)) << 27) + next(27))
/ (double)(1L << 53);
}
```

Which means it is concatenating the top 26 and 27 bits of two iterations of `next()`

to make a 53 bit number which it normalizes back into a double with a value between 0 and 1.

We are interested in the original values returned by `next(26)`

and `next(27)`

which can be recovered by reversing the operations done above. So assuming we have a value that we know was generated from calling `nextDouble()`

, we can do the following:

```
long numerator = (long)(nextDoubleValue * (1L << 53));
int next26 = (int)(numerator >>> 27);
int next27 = (int)(numerator & ((1L << 27) - 1));
```

Now we have the top 26 and 27 bits of two previous seeds used by `next()`

. But only having the top bits is not sufficient for generating future values. Fortunately, it is fairly quick to brute force the unknown remaining lower 48-26=22 bits (2^{22} possibilities). You can do this by trying all 48-bit seeds that has the same top 26 bits as `next26`

and apply the LCG formula to see if the next seed has the same top 27 bits as `next27`

. Like so:

```
long upper27Of48Mask = ((1L << 27) - 1) << (48 - 27);
long oldSeedUpper26 = ((long)next26 << (48 - 26)) & mask;
long newSeedUpper27 = ((long)next27 << (48 - 27)) & mask;
ArrayList<Long> possibleSeeds = new ArrayList<Long>();
for (long oldSeed = oldSeedUpper26;
oldSeed <= (oldSeedUpper26 + ((1L << (48 - 26)) - 1));
oldSeed++) {
long newSeed = (oldSeed * multiplier + addend) & mask;
if ((newSeed & upper27Of48Mask) == newSeedUpper27) {
possibleSeeds.add(newSeed);
}
}
```

It is possible that out of the 2^{22} seeds brute-forced there is a next value with the same top 27 bits purely by chance. Though if we make the (questionable) assumption that each `newSeed`

is a random independent number, this probability is fairly small: 1 - (1 - 2 ^{-27})^{222} = 0.03076676574.

So it is likely that we will find exactly one seed with the brute force. Using that seed we can now simulate the return value for all future calls to `next()`

and thus `nextDouble()`

and `Math.random()`

also. So we just managed to predict all future values of this generator!

It is well known that `Math.random()`

is insecure so none of this is news to anyone. I just didn't expect it to be this easy and that you can do it by just observing a single previous value!

Complete code for this can be found here.

As for the original competition this was written for, I actually ended up losing anyway. This only managed to guess a couple thousand out of 100000 correctly before exceeding the time limit. The other cheaters did a much better job by using java reflection to modify local variables to win.