Cracking Random Number Generators - Part 1

This is the first in a series of posts I'm going to give on how to crack common random number generators. Since first posting this series, I have lost count of how many people have contacted me asking if I'll help them crack random number generators, particularly for gambling systems such as lotto and betting. The answer is no, I prefer to spend my time being useful to society. Please don't contact me, your idea is not original, and even if I wanted to make money by cheating gambling systems, why would I work with you? Why wouldn't I just do it myself and take all the winnings for myself? No, I will not help you.

Random number generators are a key part of web security. They are used all over the place, from session tokens to tokens to sent to an email address to verify its owner made a particular request, to CAPTCHA tokens and so on. In all these applications, if the token can be predicted, then the security mechanism can be broken, and a malicious user will be able to identify themselves as someone who they are not.

There are obvious concerns with publishing instructions explaining how to exploit security vulnerabilities. However, I have some good reasons for doing so:

1. There is nothing new about the vulnerabilities associated with random number generation, nothing that I'm publishing here is new to hackers either.
2. Hacking random number generators is actually very easy to do, and hackers know this.
3. Many developers that I have come across are of the belief that hacking random number generators is a hard to exploit avenue of attack. Even when they know that there are dangers in random number generation, their understanding is often incomplete, leading them to make serious mistakes.
4. None of the algorithms I supply here can be used as is, they require an attacker to know exactly what algorithm is being used on a system, how to extract numbers out of it, and having then cracked the number generator, how to exploit it. Knowing all this I believe is harder than working out for yourself how to crack the random number generators themselves, so if they couldn't work out what I am saying for themselves, they likely won't be able to use it to hack into a real system.

Hence I believe that there is nothing a hacker will learn from this series that they can't work out for themselves. Meanwhile, many developers live in ignorance, and would never bother to see if their understanding of random number generators is flawed. My hope therefore is to give developers an understanding of just how dangerous their ignorance can be.

What I won't talk about in this series is anything about the maths of random number generators, beyond explaining how the algorithms are implmented. Why a particular algorithm makes a good PRNG is beyond the scope of this series.

Linear Congruential PRNG

The first PRNG we will focus on is the linear congruential PRNG. Rather than talk theoretically, we'll look at a particularly common one, Java's default random number generator, java.util.Random.

The idea behind a linear congruential PRNG is that you store a single number as the internal state. This state is usually called the seed, because the two numbers are usually one in the same thing. In Java's case, this is not quite true, but to keep our explanation simple, we will assume that it is. The seed has a precision, in Java's case, the precision is 48 bits.

The seed changes each time a number is generated, by applying a simple formula. That formula is:

seed = (seed * multiplier + addend) mod (2 ^ precision)

The key to this being a good random number generator is the choice of multiplier and addend. In Java's case, the multiplier is 25214903917, and the addend is 11. As I said earlier, what makes these two numbers good is beyond the scope of this series. The mod operation is implemented using a bitmask, 48 1's.

java.util.Random never gives out its full 48 bits of state, it gives out at most 32 on each call to nextInt(). Other calls that return more bits, for example, nextLong(), generate multiple 32 bit numbers and combine them together. To convert the 48 bit seed to a 32 bit int, the seed is bitshifted to the right by 16 bits.

Determining the seed from a Linear Congruential PRNG's output

It is not possible, from one int generated by java.util.Random, to determine the seed, because 16 bits were discarded by the bitshift. However, if we obtain a second int from it, we can quite easily guess what those remaining 16 bits were, by brute forcing all possible values, and seeing if the next value from that matches the second value we obtained. 16 bits is only 65536 possible values, and calculating the next int is only a few instructions, so this can be computed in a fraction of a second.

The code in Java looks like this:

Random random = new Random();
long v1 = random.nextInt();
long v2 = random.nextInt();
for (int i = 0; i < 65536; i++) {
    long seed = v1 * 65536 + i;
    if (((seed * multiplier + addend) & mask) >>> 16) == v2) {
        System.out.println("Seed found: " + seed);
        break;
    }
}

As can be seen, given two integers from java.util.Random, we can predict all future generated integers. In Part 2 we'll get a little more involved in the maths, and learn how to calculate the previous seeds.

• prng