I. DESCRIPTION

Easily exploitable Pseudo Random Number generator in phpbb version 2.0.19 and under.


II. DETAILS

Due to poor design the gen_rand_string() can only generate upto 1 million hashes or random strings. This allow an attacker to reset any account through the lost password request form by "predicting" the validation id and the new password for the account. Worst case scenario (for the attacker) is that he will have to send 1 million requests to reset the password and 1 million requests to get the new password.


For more info visit http://www.r-security.net/tutorials/view/readtutorial.php?id=4

Exploiting Pseudo Random Number Generators in PHP

"Anyone who considers arithmetical methods of producing random digits is, of course, 
in a state of sin". - John von Neumann

[abstract]

This paper talks about the misuses of generating random numbers and how easily (or hardly) they can be exploited to an attacker's advantage. I focus on the 2 most popular BBSs in use, IPB which is in version 2.1.4 at time of writing this article and phpbb which is in version 2.0.19. Both rely on a PRNG to generate pseudo-random strings when a client requests a password change. This paper is a publicity stunt to get people to join r-security's irc. (check out the irc page)

[phpbb - overview]

Resetting a password in phpbb is a 2 step process. A client would go to the lost password form, enter in their username and email. Phpbb would than generate a validation id 

/includes/usercp_sendpasswd.php line 51
"$user_actkey = gen_rand_string(true);"

and than generate a password. 

/includes/usercp_sendpasswd.php line 55
"$user_password = gen_rand_string(false);"

The validation ID is emailed to the user in the form of a link which he must visit in order for the generated password to replace his original password. The length of the validation ID depends on the server name, but this does not affect the actual attack much. If we take a look at the gen_rand_string() function

/profile.php line 61
function gen_rand_string($hash)
{
$chars = array( 'a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H', 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P', 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X', 'y', 'Y', 'z', 'Z', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0');

$max_chars = count($chars) - 1;
srand( (double) microtime()*1000000);

$rand_str = '';
for($i = 0; $i < 8; $i++)
{
$rand_str = ( $i == 0 ) ? $chars[rand(0, $max_chars)] : $rand_str . $chars[rand(0, $max_chars)];
}

return ( $hash ) ? md5($rand_str) : $rand_str;
}

knowing that PRNG's aren't truly random, and that given the same seed, the PRNG will generate the same random numbers, we can safely assume that because of "srand( (double) microtime()*1000000); " the seed will always be a number from 1-999,999. Also knowing that the password is generated right after the validation ID, once we get the validation ID, the index microtime used to seed the password generation won't be too far off than the microtime used to seed the validation ID. Worst case scenario in this attack is that you will have to send the full 1mil requests to reset the password, an attacker can however knock that down to a 100k range if he manages to synchronize when the request is sent with the server time displayed on the main page of every phpbb forum. 

[phpbb - the attack]

I coded 3 programs, one which generated the password and validation ID tables, one which continuously sent GET requests in order to activate the password change and the last one which used a list of passwords to do a dictionary attack on a phpbb account. The test site I decided to use will remain anonymous (I was banned!) After generating the validation IDs and passwords, I decided to try to reset my own account. I requested a password change for my own account. I immediately began my second program to send validation id's which were truncated to have only 6 characters (the length the server used). 

After 40 minutes the program flagged that it had managed to reset the password, and it output the validation ID which activated the password change. I took the validation ID, opened up my table and found out that the validation ID was at index 117312 (I got lucky, could've been higher). I than went to the password table, deleted everything before index 117312 and everything after index 120000, I was down to a list of 2688 passwords. I began my final program, using the list of passwords. I got the new password within 10 seconds, it was at index 117490, which means the seeds used to generate the validation ID had a difference of 178. 

Total elapsed time since start of attack - Under 50 minutes. 

[IPB - overview]

Wow, I'm pleased to say that IPB has changed their code since last time I saw it, it's more "complicated" but exploiting the PRNG is still feasible, don't underestimate a person's hatred for someone (hating is what humans are good at). Ok, lets take a look at IPB's function that generates a password.

\uploads\sources\ipsclass.php line 2800

function make_password()
{
$pass = "";

// Want it random you say, eh?
// (enter evil laugh)

$unique_id = uniqid( mt_rand(), TRUE );
$prefix = $this->converge->generate_password_salt();
$unique_id .= md5( $prefix );

usleep( mt_rand(15000,1000000) );
// Hmm, wonder how long we slept for

mt_srand( (double)microtime()*1000000 );
$new_uniqueid = uniqid( mt_rand(), TRUE );

$final_rand = md5( $unique_id.$new_uniqueid );

mt_srand(); // Wipe out the seed

for($i = 0; $i < 15; $i++)
{
$pass .= $final_rand{ mt_rand(0, 31) };
}

return $pass;
}

Note the evil laugh. I had to sift through php's code to see the code for uniqid and how srand() and mt_srand() generate seeds when an argument isn't passed. First, mt_srand() is seeded with a (microtime() * 1000000) in the page that calls make_password(), therefore we can predict all mt_rand() calls assuming we bruteforce the seed. 

uniqid() generates an ID by concatenating the prefix (the first argument), unixtime, microtime and the result from "php_combined_lcg(TSRMLS_C) * 10". We can assume the microtime hadn't changed much, maybe several milliseconds since the original seeding of mt_rand().

php_combined_lcg(TSRMLS_D) is also predictable, because it uses 2 values to generate the number, unixtime ^ (-(microtime)) or 1 and the result from getpid(). We can once again assume the microtime didn't change much, and we should know the unixtime of when we sent the request. A problem occurs when trying to figure out the PID, because it can be a number of things, this however can be bruteforced offline. Most webserver run PHP as a module, so the PID would never change, if we get a password generated by make_password, and we know the unixtime, AND we assume that the microtime between each calls differs only slightly, we can bruteforce the PID. 

mt_srand(), when not passed an argument, generates a seed using a mersenne twister along with the result from GENERATE_SEED()

Note: I'm not sure about a variable used in the mersenne twister, BG(state), I'm assuming it's predictable. =\

GENERATE_SEED is defined as ((long)(time(0) * getpid() * 1000000 * php_combined_lcg(TSRMLS_C))), once again there are variables we can predict.

Finally, srand() is just the result from GENERATE_SEED(). 

A good attacker would be able to knock down the original mt_rand seed to a 10k range. Assuming he is attacking a fast server in which the difference between each microtime() used is no greater than 5 ms we can get a rough idea of how many possible passwords would need to be used to bruteforce the server.

10,000 * 5 * 5 * 5 * 5 * 5 = 31,250,000 total requests need to be made. each 5 is for everytime GENERATE_SEED and uniqid() is called along with the seeding of srand() in the function generate_password_salt(). The 5 represents a maximum of 5 ms difference between each call, of course it could be less, on a server where the difference would only be 2 ms there would be about 10,000 * 2 * 2 * 2 * 2 * 2 = 320,000 requests. All this assumes you have the PID.

[IPB - the attack]

I didn't do an attack on IPB, would've taken too long to organize everything and do the actual attack :P. (One would also need to find a way around image verification)

[conclusion]

Both are possible to exploit, but IPB is harder to exploit, ALOT harder. I hope this paper will serve developers who use PRNG's as a security measure, both in PHP as well as in other languages.