<< Facebook OpenID integration in Pebble | Home | Cracking Random Number Generators - Part 2 >>

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.

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.

Tags : ,


Avatar: Derrick

Re: Cracking Random Number Generators - Part 1

I'm unable to get the code to work that calculates the seed from two random integers. The if statement is never true. Can anyone see what I'm going wrong?


    private static long multiplier = 0x5DEECE66DL;
    private static long addend = 0xBL;
    private static long mask = (1L << 48) - 1;


    public static void test()
    {
        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;
            }
        }
    }

Avatar: James Roper

Re: Cracking Random Number Generators - Part 1

Hi Derrick,

If you run it a few times (so it runs with different seeds), you should find sometimes it will be true, and sometimes it won't.  Do it enough times, you should find it works 1 in 4 times.  The reason for this is that the seed is 48 bits, but when the bitshifted seed is converted to an int, if the first bit is 1, then it becomes a completely different negative number to the original long (if you don't understand why, read up on two's compliment numbers).  Then you're casting it back to a long, but when you do that, java ensures that the long number is the same number as the int number, which from a binary perspective means it's completely different to the original value that was in the seed.

I didn't include this conversion in my pseudo code so that I could keep it simple.  To convert the int back to a long, you need to use an if statement, to see if the original number is negative, and then handle it slightly differently in that case.  I'll let you work out how.

Cheers,

James

Avatar: Igor Terzic

Re: Cracking Random Number Generators - Part 1

You actually do not need an if statement. This should work:

<span class="Apple-tab-span" style="white-space:pre"> </span>int x1 = random.nextInt();

<span class="Apple-tab-span" style="white-space:pre"> </span>int x2 = random.nextInt();

<span class="Apple-tab-span" style="white-space:pre"> </span>long v1 = x1 & 0x00000000ffffffffL;

<span class="Apple-tab-span" style="white-space: pre; "> </span>long v2 = x2 & 0x00000000ffffffffL; 

Thanks for the awesome article btw, it helped me a lot.

Avatar: Nikita Arykov

Re: Cracking Random Number Generators - Part 1

This problem arise because of incorrect operation with the types int and long, You can replace line for bits shift

long seed = v1 * 65536 + i;

to

seed = (((long) v1) << 16) + i;

Join us, a very good collection of articles!

Avatar: John

Re: Cracking Random Number Generators - Part 1

Hello, James, my name is John.  I find the topic of PRNGs fascinating and came across your page.  I'm currently learning about the guts of computers myself and had some questions regarding Linear Feedback Shift Registers (LFSRs) around the era of the early 1990s.  Take for example a 16-bit LFSR which generates not just single random numbers, but sequences of say 10 to 20 numbers.  As far as the period (2^16 = 65,536) is concerned, would you expect it to repeat after 65,536 consecutive sequences of 10 to 20 #s?  Or, would the individual #s within the sequence repeat after 65,536 individual numbers.  Example: If a sequence of 20 numbers, would it repeat after 3,276.8 (65,536/20) sequences of 20, counting only the individual #s within the period? I thought about this while playing an old Nintendo Entertainment System video game the other day called Vegas Dream.  They have a Keno game in it and my buddy and I were wondering if we could crack it.  Haha.  Thanks for any help or feedback.  I really enjoyed reading this page...

-John

Avatar: James Roper

Re: Cracking Random Number Generators - Part 1

Let's make the numbers smaller.  Let's say the period of the LFSR is P, and the length of the subsequences is S.  Now let P = 8, this might be a sequence you get out of it:

3, 2, 5, 7, 1, 0, 4, 6

This sequence will repeat itself indefinitely.  Now if we say S = 3, you will get this out of it:

(3, 2, 5), (7, 1, 0), (4, 6, 3), (2, 5, 7), (1, 0, 4), (6, 3, 2), (5, 7, 1), (0, 4, 6)

And that will repeat indefinitely, it has a period of 8 too.  Now remove the paranthesis, and you'll see that the sequence above is just the first sequence repeated 3 times.  So although it is a period of 8 distinct sequences, there is a pattern within those sequences.  But it won't always be a period of 8.  The period will be LCM(P, S) / S, where LCM is the lowest common multiple function.  So, take subsequences of 6 as an example:

(3, 2, 5, 7, 1, 0), (4, 6, 3, 2, 5, 7), (1, 0, 4, 6, 3, 2), (5, 7, 1, 0, 4, 6)

<div>It has a period of 4 before it starts repeating, since LCM(6, 8) is 24, s.  Subsequences of 4 will have a period of 2, and subsequences of 8 will have a period of 1.</div> <div> </div> <div>So to answer your original question, a 16 bit LFSR, taking sequences of 20 out, LCM(65536, 20) is 327680, divide that by 20, and you get a period of 16384.</div>

 


Add a comment Send a TrackBack