Seed Racing

SeedRacing

The Art of Exploiting Race Conditions in Random Number Generators

Craig Smith, Patrick Toomey, Cris Necker

© 2008 Neohapsis

Overview

SeedRacing is an attack against standard pseudorandom number generators. A pseudorandom number generator (PRNG) is designed to generate a sequence of numbers that lack any predictable pattern. Attacks against non-cryptographically strong pseduorandom number generators are well known[1], but our often considered “good enough” for use in non-cryptographic systems. Most languages have a default method for generating pseudorandom numbers. These default methods rarely use a cryptographically sound random number generation routine, and by default rely on insecure seeding mechanisms. When initializing your random number generator the most important step is to “seed” the random number generator. Because, once seeded, all outputs from the PRNG are the result of a completely deterministic algorithm. Thus, seeding is the only step that differentiates one instantiation of a given PRNG from another. Stated more simply, a pseudorandom number generator that is seeded with identical values will produce the same sequence of outputs. Often times these default PRNGs implicitly seed themselves using a call to a system time or tick count function. This paper will focus on attacks against these default methods of producing random numbers when the initial seed value is based on time.

An Example in .NET

Most languages are susceptible to this attack to one degree or another. A list of other languages and there susceptibility is listed at the end of this document. We have chosen .NET because the default method is widely used and is more susceptible to this attack than most other languages that we have checked. Here is an example code in .NET that grabs a random number:

private static int GetDice(int min, int max)

{

Random rand = new Random();

return rand.Next(min, max + 1);

}

This code takes a min and max values that specify the range to return for the random number. For instance a call to GetDice(1,6) would return a standard 6-sided die roll. The fact that this is very simple to code and to read coupled with the fact that MSDN[2] does not seem to stress the dangers of using this method is probably why you see this done so much. We will go into more details as to why this is dangerous next.

Now lets modify the GetDice method to allow it to pick random characters in an array that holds letters a-z. It will pick 8 characters to add to a string to generate a random password.

private static string GetRandomPassword()

{

StringBuilder password = new StringBuilder();

char[] lCase = new char[] { ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’, ‘m’, ‘n’, ‘o’, ‘p’, ‘q’, ‘r’, ‘s’, ‘t’, ‘u’, ‘v’, ‘w’, ‘x’, ‘y’, ‘z’, };

int lCaseIndex = 0;

Random rand = new Random();

for(int cnt = 0; cnt < 8; cnt++ ) {

lCaseIndex = rand.Next(0, lCase.Length – 1);

password.Append(lCase[lCaseIndex]);

}

password.Append(0);

return password.ToString();

}

Now we will create a basic Web Application that has a login box. With a login box we will include a Forgot Password link that will reset the users password to a randomly generated password and email that password to the user. The Forgot Password link is called http://localhost/ForgotPassword.aspx and it takes one argument userid.

The Vulnerability

The problem comes from the call to initialize a new Random object. This line:

Random rand = new Random();

Implicitly calls:

Random rand = new Random(Environment.TickCount());

Where Environment.TickCount()[3] returns the number of milliseconds elapsed since the system startup. The problem is simple. If you call this random function in quick succession (in the same millisecond) you will get the EXACT same random value. This is because our application initializes every time before picking the next random number. This is very common in a web application because each time you connect the web server will likely create a new thread.

So how hard is it to call this function in the same millisecond? Its not too hard at all. A modern computer on a decent network can easily get out hundreds of requests in a millisecond. For our attack all we need is two.

In a localhost experiment Neohapsis sent 67,000 requests to a server with a random password generation routine similar to the one in our example. We only received 208 unique responses from the server. That is approximately 322 duplicate passwords. Again, that is under a rather ideal situation, you probably will not have that many duplicates in a real world scenario.


The Exploit

This is how the exploit would work. The attacker has an account on the target system with a valid email that they can check. Then the attacker locates a victims ID they want to target for the attack. The attacker needs to perform the following to successfully exploit this vulnerability:

1. Send two simultaneous (or close to it) web requests to the target system. One request with the attacks ID and one with the victims ID. Example: http://localhost/ForgotPassword.aspx?userid=attackerid and http://localhost/ForgotPassword.aspx?userid=victimid

2. That will reset both of their passwords and send both accounts an email. The attacker checks their email and users their generated password on the victims account.

3. If that fails, repeat.

Now that could be tedious, especially with a system that randomizes with microseconds instead of milliseconds like .NET does. However, luckily for the attacker, this is not very hard to automate. It is not only trivial to write a script to send out two simultaneous requests but also to have it check the mail and attempt to login.

This attack can potentially take several hours to execute and generate a LOT of email during that time. Won’t the users see hundreds of emails informing them that there password was reset? Sure, but by that time the attacker is already in and if the system was the mail system then the attacker can simply delete those messages. The truth of the matter is that the damage is already done and the only way to stop the attacker from breaking in is to fix the underlying code.

Remediation

Luckily this isn’t too difficult to fix. The best method of remediation is to use a more cryptographically sound Pseudo Random Number Generator (PRNG). For .NET this is the RandomNumberGenerator class[4]. For Java based systems this involves using SecureRandom[5] although as of Version 1.5 the default Random class seems greatly improved in this area. With PHP, rand and mt_rand are the same (mt_rand is faster), as the vulnerability is strictly based on what you seed mt_srand with. If the seed is set by the developer as microseconds you greatly reduce the window of exploit.

It should be noted that Microsoft’s documentation on MSDN[2] does state that Random is not a cryptographically secure class. That fact that Random has been insecure has been known for a long time but traditional attacks have been against cryptography. This paper shows that non-cryptographically sound pseudo random number generators should not be used in methods involving security or privacy.

References

[1] http://en.wikipedia.org/wiki/Random_number_generator_attack
[2] http://msdn2.microsoft.com/en-us/library/system.random.aspx
[3] http://msdn2.microsoft.com/en-us/library/system.environment.tickcount.aspx
[4] http://msdn2.microsoft.com/en-us/library/system.security.cryptography.randomnumbergenerator.aspx
[5] http://java.sun.com/j2se/1.4.2/docs/api/java/security/SecureRandom.html

4 thoughts on “Seed Racing

  1. Pingback: Infosec Ramblings

  2. Pingback: Interesting Bits - April 30th, 2008 « Infosec Ramblings

  3. Pingback: Crypto Pet Peeves: Hashing…Encoding…It’s All The Same, Right? « Neohapsis Labs

  4. this was an interesting post, i’ll be sure to implement some fo what i read.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s