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 x0, the next pseudorandom number generated is given by x1 = a * x0 + c mod m, for some fixed constants a, c, and m. So for example let's say a = 3, c = 5, m = 7 and we start with the seed x0 = 0, then the next few random numbers generated will be: 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., xi = 2), you can predict the next number by applying the formula yourself (e.g, xi+1 = 3 * 2 + 5 mod 7 = 4).

The relevant method in java.util.Random looks like this (where m=248 or in other words, a 48-bit number is generated with each iteration):

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 (222 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 222 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.