Cracking Random Number Generators - Part 2

In Part 1 of this series, we saw how simple it is to predict future values generated by a linear congruential PRNG. In this part, we will look at how to calculate past values generated by a linear congruential PRNG.

Undoing three simple operations

As we saw before, going forward on a pseudo random number generator involves multiplying by the multiplier, adding the addend, and then trimming the result back down to 48 bits. Surely this can be solved by a simple subtraction and divide?

It's not that simple. Let's have a look at it in binary:

Seed 1:     110011111101000111101001010011010100010001001111
Multiplier:              10111011110111011001110011001101101 *
------------------------------------------------------------
             11111011111111000111100000110010000111110100011
Addend:                                                 1011 +
------------------------------------------------------------
Seed 2:      11111011111111000111100000110010000111110101110
Addend:                                                 1011 -
------------------------------------------------------------
             11111011111111000111100000110010000111110100011
Multiplier:              10111011110111011001110011001101101 \
------------------------------------------------------------
                                               1010101110110

As you can see, we've done the multiply, the add, then subtracted the addend, and divided by the multiplier, and the result is nothing like the original seed. Why not? The problem is the bitmask we applied. When we applied the multiplier originally, it overflowed beyond 48 bits. The most significant bits were discarded, meaning that a simple divide can not get us the result. So how can we find the result?

The solution comes in going back to primary school. In primary school we learnt how to do long multiplication. Let's look at what multiplying two small binary numbers looks like, using long multiplication:

     101101
     001011 *
-----------
     101101
    101101
   000000
  101101
 000000
000000
-----------
00111110111 
     111111 &
-----------
     110111

Let's say that the first number is our multiplier, it is the known, and the second number is the unknown that we want to determine. The final number is the seed that we have, trimmed down to the number of bits, it is known, but the excess bits are not.

It should be clear from the above that there is a pattern, for each 1 in the second number, there is a corresponding first number on the line below. We can also see that if the last digit of the original number was 0, then the last digit of the new number will be 0, if it was 1, then the new number will be 1. In the above example we can determine therefore that the last digit in the original number was 1. Because we know that, subtract the multiplier from our seed, and reverse the effects of the value of the last number in the original number. Here is the result:

Result: -----1

     101101
     00101- *
-----------
    101101
   000000
  101101
 000000
000000
-----------
00111000010 
     111111 &
-----------
     000010

Result: ----11

     101101
     0010-- *
-----------
   000000
  101101
 000000
000000
-----------
00101101000 
     111111 &
-----------
     101000

Continuing this process, of scanning from right to left, taking the next digit in the seed, and subtracting the effect that that digit would have had on the seed, we can determine the end result.

This only works if our multiplier is odd, which it is. If it weren't, we would only have to bitshift the seed to the left by the number of 0's on the end of the multiplier, and every bit that we shifted across would be one less bit of the final result that we could determine. So our algorithm for determining the previous seed looks like this:

long seed = currentSeed;
// reverse the addend from the seed
seed -= addend; // reverse the addend
long result = 0;
// iterate through the seeds bits
for (int i = 0; i < 48; i++)
{
    long mask = 1L << i;
    // find the next bit
    long bit = seed & mask;
    // add it to the result
    result |= bit;
    if (bit == mask)
    {
        // if the bit was 1, subtract its effects from the seed
        seed -= multiplier << i;
    }
}
System.out.println("Previous seed: " + result);

And there we have it, we can now predict all previous values from java.util.Random given the current seed.

That covers everything you need to know about hacking a linear congruential PRNG. However, most common platforms don't use such a simple PRNG as their default random number generator. In Part 3 we will look at how to hack a very popular PRNG, the Mersenne Twister.

• prng