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.

I've taken a shot at implementing Facebook OpenID integration into Pebble. To see the results, at the bottom of this page, click "Add Comment", and then click the Facebook Login link.

Implementing this has been pretty simple. All the magic happens on the client side, at no point does Pebble make a request on Facebook, and the user is, as far as Pebble is concerned on the server side, never authenticated or trusted in any way. All this integration does is puts the users name, profile picture and profile link in the author, avatar and website fields of the Pebble comment form.

The bulk of the work has been in modifying pebble to handle profile pictures with comments, and adding a plugin point for this type of plugin. What follows is a quick tutorial of how to implement a similar OpenID authentication on your site.

1. Create an application on Facebook

Facebook provides some simple instructions on how to do this here. You will need to create a new application for every different website that you want to integrate with, as Facebook will validate the base URL that it forwards to.

2. Add the login button to your page

There are a number of ways to do this, but the simplest way is to use the Facebook Markup Language (FML). In the next step we'll configure Facebook to render FML tags, for now, the only thing you need to do is put the following code where you want the login button to appear:

<fb:login-button/>

3. Initialise the Facebook API

The Facebook client side libraries require that they be initialised. This is also the stage where Facebook will render any FML tags you've included in the page. Initialising the Facebook client side API is best done at the bottom of the page, so that it doesn't slow down the loading of the rest of the page. At this stage you'll need the Facebook application ID from the application you created in step one:

<div id="fb-root"></div>
<script src="http://connect.facebook.net/en_US/all.js"></script>
<script>
    FB.init({appId: "YOUAPPIDHERE", status: false, cookie: true, xfbml: true});
</script>

4. Write a function to handle a logged in user

This is where we do most of the work. The Facebook javascript API provides an event library, and we can use this to update our page with the users details after they log in to Facebook. This event will only fire when the user logs in or logs out, if a user comes back to your site, and they are already logged in, the event won't fire, even if they click log in, hence we also need to check if the user is already logged in when the page loads. So we're going to write a function that will handle both of these situations. The function accepts a Facebook response object, and checks if the response has a session. This indicates that the user is logged in. If they are logged in, we make a call on the /me resource of the Facebook Graph API, which will return the users name, link to their profile, and other things. This function can go anywhere in your code, preferably in a Javascript file along with the rest of your scripts:

  function updateFacebookCommentAuthor(response) {
    if (response.session) {
      FB.api("/me", function(response) {
        var avatar = "http://graph.facebook.com/" + response.id + "/picture?type=square";
        document.forms["commentForm"].elements["author"].value = response.name;
        document.forms["commentForm"].elements["website"].value = response.link;
        document.forms["commentForm"].elements["avatar"].value = avatar;
      });
    }
  }

5. Subscribe to login events

Lastly, we want the above function to be called when a page loads if the user is already logged in, and if a user logs in clicking the login function. This can either be done at the bottom of the page after the Facebook API is initialised, or it can be done in in the window on load event. Pebble uses prototype, so I bind it to the window on load event using that:

  Event.observe(window, "load", function() {
    FB.Event.subscribe("auth.sessionChange", updateFacebookCommentAuthor);
    FB.getLoginStatus(updateFacebookCommentAuthor);
  });

This is all you need for basic OpenID authentication using Facebook. Of course, you might want to, instead of just populating the form, actually render the username and profile picture in the page, as has been done in Pebble. Another thing you may want to provide is the ability for the user to log out, in case they are using someone else's computer and that person is logged in.

If you've been following my Facebook, Twitter or Google Buzz updates, you may have noticed I've asked for feedback from beta testers to check that a website I've been developing displays in all browsers. This has been a project I've done in my spare time, and I thought I'd blog about it, to increase both public awareness and Google ranking :)

The website is Cocoa Petition, a petition to the Australian Government to set a date by which importing of cocoa products that involve unacceptable forms of child labour in the production process must be ended.

The problem

The use of child labour in cocoa production is a little known but massive problem. It is estimated that nearly 300 000 children work on the cocoa farms of the Ivory Coast in West Africa, working long hours in dangerous conditions such as spraying pesticides and wielding machetes with no protection, without the opportunity to go to school. In many cases, the children are working on their family farms, but there are also a significant proportion that are working as slaves. It is estimated that over 10 000 child slaves are trafficked into the Ivory Coast each year to work on the cocoa farms.

Evidence for this unacceptable child labour can be found on the Cocoa Petition website, but perhaps the most compelling evidence is that in 2001, an voluntary agreement called the Harkin-Engel Protocol was signed by many of the major chocolate producers, including Nestlé and Mars/M&M, acknowledging the existence of unacceptable child labour in cocoa production. Since then, little has been done by these companies about the problem.

The solution

There is however at least one solution to the problem, that is the Fairtrade branding. Fairtrade products guarantee that the farmers and farm workers are paid fairly for their work, and ensures that no unacceptable child labour is used in the production process. In 2009, Cadbury announced that from Easter 2010, all Cadbury Dairy Milk chocolate sold in Australia and New Zealand will be Fairtrade. This is great progress, but as a first step to eradicating the use of unacceptable child labour in cocoa production, we need to make sure that no such cocoa is imported into Australia by any company.

Hence, this petition. Australian laws are clear that importing products that are produced by slaves is illegal, however, the Australian government has so far remained ignorant to the problem.

My involvement

So, why would I donate my time and efforts to this cause? The reason is simple. As a Christian, I believe that one of the most important things to God is justice. In the book of Isaiah, which my Bible study group is looking at at the moment, God pleads with Israel to turn from doing wrong, so that he doesn't have to judge them, saying

Stop doing wrong,
learn to do right!
Seek justice,
encourage the oppressed.
Defend the cause of the fatherless,
plead the case of the widow.
Isaiah 1:17-18 (NIV)

African children working as slaves to produce chocolate so that Australian children can satisfy their sweet teeth is as far from just as I can think. So, this is a cause that I really believe I should be fighting for. If you feel the same way as I do over this injustice, then please, visit the Cocoa Petition site, and get involved.

In a typical SSL configuration for a Tomcat web server, Apache sits in front of Tomcat as a reverse proxy, and does the SSL. This was the configuration of some systems I work with. There are a number of reasons why this configuration is used, the primary one being that Apache's SSL implementation is much faster than Tomcat's. So it's not often that you would go from using this configuration to switching to a Tomcat only configuration, but that's exactly what I just did.

The reason for doing this is that we wanted to use Tomcat's NIO connector, in order to use Tomcat's comet capabilities. Setting up SSL with Tomcat is something that I had never done before, I had heard though that it was not easy. After trying to do it without really understanding what I was doing, I found that it really wasn't easy. The problem was that everything I looked at on the web talked about using the Java keytool to generate a key, so you could send a certificate signing request to your trusted authority to sign. The thing is, I already had a key, and a certificate, and the Java keytool utility that does all this key manipulation has no way of importing an existing key.

Eventually I found this utility, and was able to get things working. But, as often happens when solving these problems, I then read back over the Tomcat SSL HowTo, and now with more of an understanding of what I was doing I found a much simpler and easier way of getting Tomcat to use my existing certificate.

The trick is, rather than use a JKS repository, which is the native Java SSL certificate store, and what most of the documentation on the web talks about, is use a PKCS12 repository, which is an internet standard, and can be manipulated using standard tools such as openssl. This tool requires three files, which are easy to find from your Apache SSL configuration, one is the private key file, another is the certificate, and finally the certificate signer chain. The command to run is:

openssl pkcs12 -export -in mycert.crt -inkey mykey.key \
                        -out mycert.p12 -name tomcat -CAfile myCA.crt \
                        -caname root -chain

The name and caname arguments can be anything, they're just convenient aliases to allow later manipulation of the file. The command will prompt you for a password, this password gets set as the keystorePass in the Tomcat connector configuration. The keystoreType must be set to PKCS12. Here is my Tomcat configuration:

    <Connector port="8443" maxHttpHeaderSize="8192"
               maxThreads="150" enableLookups="false" acceptCount="100"
               connectionTimeout="20000" disableUploadTimeout="true"
               protocol="org.apache.coyote.http11.Http11NioProtocol"
               SSLEnabled="true" scheme="https" secure="true" clientAuth="false" sslProtocol="TLS"
               keystoreFile="/path/to/mycert.p12"
               keystoreType="PKCS12" keystorePass="tomcat"/>

The volatile keyword is a keyword that very few Java developers know the meaning of, let alone when they should use it. The reason for this, I believe, is that the reason why it's needed is such a complex topic that unless you've studied in detail the way CPUs use registers, cache, and the way the JVM uses stack frames, it's impossible to understand why it's needed. The other reason I think, is that it is difficult to demonstrate the consequences of not using it. That is why I came up with this little puzzle, to highlight how important the volatile keyword is.

For this demonstration, you will need a multi processor Linux 2.6 or OpenSolaris system, with Java 5 or above. It will not work on Mac or Windows. If you know why it doesn't work on Mac or Windows, please leave a comment explaining, I'd really like to know. What this does highlight though is just how complex Java concurrency issues are.

So on to the puzzle. Without executing it, try and work out what will happen when you run the following code:

public class ConcurrencyFun implements Runnable
{
    private String str;
    void setStr(String str)
    {
        this.str = str;
    }
    public void run()
    {
        while (str == null);
        System.out.println(str);
    }
    public static void main(String[] args) throws Exception
    {
        ConcurrencyFun fun = new ConcurrencyFun();
        new Thread(fun).start();
        Thread.sleep(1000);
        fun.setStr("Hello world!!");
    }
}

Most people would guess that the above code would wait for about one second, print the text "Hello world!!", and then exit. The spawned thread busy waits for str to not be null, and then prints it. The main thread, after starting the spawned thread, waits for one second, and then sets str to be "Hello world!!". Simple, right?

Now try running it (remember, only on a multi processor Linux 2.6 or Solaris system). What actually happens? On my machine, the program never exits. Why is this?

The reason is that the JVM is free to make its own copy of the str pointer available to each thread that uses it. This could come in many forms. It could be that the pointer is loaded into a register and is continually read from that register. This is what is most likely happening in our case. It could be that the pointer is loaded into the CPU cache, and never expired, even after update. Or, it is also possible that the JVM will make a copy of the pointer in the threads stack frame, to allow for more efficient memory access. Whether you understand anything I've just said or not, the point is that changes to the str field may not necessarily be seen by all threads accessing it, in our case, it will never be seen by the spawned thread.

This is where the volatile keyword comes in. The volatile keyword tells the JVM that any writes to that field must be viewable by all threads. This means that the compiled machine code may not read the variable into a register and use that multiple times, it must read it from memory every time. It also must not read it from the CPU cache, it must make sure that every read comes straight from memory. And finally, it stops the JVM from creating a local copy of the field in the threads stack frame.

So, adding the volatile keyword, like so:

public class ConcurrencyFun implements Runnable
{
    private volatile String str;
    void setStr(String str)
    {
        this.str = str;
    }
    public void run()
    {
        while (str == null);
        System.out.println(str);
    }
    public static void main(String[] args) throws Exception
    {
        ConcurrencyFun fun = new ConcurrencyFun();
        new Thread(fun).start();
        Thread.sleep(1000);
        fun.setStr("Hello world!!");
    }
}

results in the expected behaviour happening, the program waits one second, prints out "Hello world!!" and then exists.

The complexity of concurrency

There are other ways to make the above code work. For example, if in the while loop, you add some code that prints something out, you will find that it works. My guess at the reason for this is that the register storing str ends up getting used for something else, and so on each iteration, str gets read from memory. Note that this is not a real fix, it is still possible for problems to occur, and indeed on some architectures the program still will not exit. Another thing that will work is to invoke Java with the -Xint argument. This disables machine code compilation, and hence makes concurrency issues arising from registers and CPU caches much less likely. But again, it's not a solution. Using the volatile keyword is the only solution that guarantees that it will work, every time, on every platform.