August 17th, 2008 by Stefan Esser
PHP comes with two random number generators named rand() and mt_rand(). The first is just a wrapper around the libc rand() function and the second one is an implementation of the Mersenne Twister pseudo random number generator. Both of these algorithms are seeded by a single 32 bit dword when they are first used in a process or one of the seeding functions srand() or mt_srand() is called.
Because of such a short seed it should be obvious to everyone that neither rand() nor mt_rand() are random enough for cryptographic usages. However web application programmers tend to use rand() or mt_rand() to create cryptographic secrets like passwords, activation keys, autologin cookies or session identifiers. In many situations this seems secure enough, because not only a 32 bit seed needs to be guessed but also the amount of previously generated random numbers. Therefore bruteforcing seems impractical.
There are however several situations and conditions that make bruteforcing feasible or not required at all.
The Implementation
When mt_rand() is seeded internally or by a call to mt_srand() PHP 4 and PHP 5 <= 5.2.0 force the lowest bit to 1. Therefore the strength of the seed is only 31 and not 32 bits. In PHP 5.2.1 and above the implementation of the Mersenne Twister was changed and the forced bit removed.
Implementation Bugs
In PHP 4 and PHP <= 5.2.5 the automatic seed of rand() and mt_srand() is buggy. Whenever the lowest 26 bits of the timestamp are zero the internal seed will become zero (or 1 due to the forced bit) on 32 bit systems because of an overflow of the 32 bit register. On 64 bit systems there is a precision loss when the seed is casted from a double to int that results in a seed about 24 bit strong.
Weak seeding
Although PHP 4.2.0 and above internally seeds the random number generators many PHP applications still call srand() and mt_srand() themself to seed the random number generators. Popular seedings look like one of the following examples.
mt_srand(time());
mt_srand((double) microtime() * 100000);
mt_srand((double) microtime() * 1000000);
mt_srand((double) microtime() * 10000000);
These seedings are all bad because
- time() is not random. It is known by the attacker(). Even a wrongly set clock on the server side does not protect because time leaks through the Date HTTP Header.
- The first factor is between 0 and 1 and the second factor is 100000. Therefore there are only 100000 possible seeds which is a strength of about 17 bits. On older PHP versions the forced seed bit results in only 16 bit strength. (Due to rounding issues there might be less)
- The first factor is between 0 and 1 and the second factor is 1000000. Therefore there are only 1000000 possible seeds which is a strength of about 20 bits. On older PHP versions the forced seed bit results in only 19 bit strength. (Due to rounding issues there are less)
- The first factor is between 0 and 1 and the second factor is 10000000. However because microtime() depends on the current microsecond() there are only 1 million possible results, which again results in a seed with a strength of about 20 bit. (Due to rounding issues there are less)
CGI seeds once per request
Because in a CGI environment every request is handled by a fresh process the random number generators are always freshly seeded. Therefore an attacker only needs to bruteforce 32/31 bits and does not need to guess how many random numbers where already generated. In case of information leaks generated during the same request using the same random number generator it is possible to use precalculated attack tables.
Crashing PHP for fresh random numbers
Whenever a process is reused for random numbers attacking becomes more difficult, because the internal state of the random number generator is unknown. Therefore any crash bug in PHP is welcome. In older PHP versions crashing PHP is just a matter of sending deeply nested arrays in GET, POST or COOKIE variables. Whenever a crashed PHP process is replaced by a fresh one, a new seed is generated and the internal state of the random number generator just depends on the 32 bit seed. Here precalculated tables can also be used in case of information leaks.
Keep-Alive is your friend
When some information is known about the internal state of the random number generator Keep-Alive HTTP request can make exploits very easy. Because follow request during a Keep-Alive HTTP connection are handled by the same process (same random number generator) the state of the random number generator stays the same and random numbers can be precalculated from the outside. While this is always true for mod_php, it is not true for CGI and only sometimes true for fastcgi setups.
Shared Ressource Problem
Both random number generators are a shared ressource, because the state is stored in process memory and future request in the same process will continue with the previous random number state. Because of this in shared hosting environments that do not use a CGI setup a malicious customer on one VHOST can set the random number generators in a known state by calling srand(0) or mt_srand(0). With the help of Keep-Alive requests it is then possible to predict the random numbers used on other VHOSTs. This of course allows the prediction of newly generated passwords, activation keys or session identifiers.
Information Leaks
Sometimes applications initialize the random number generator and at the same time they generate a random number that is then sent to the user. An example is the search function of phpBB2, where the search_id is generated with mt_rand() and then written to the HTML.
mt_srand ((double) microtime() * 1000000);
$search_id = mt_rand();
The problem with this is that in the example above the search function does not only set the random number to a 20 bit wide state but it also leaks the state through the search_id output. In this example there are only 0,003% collisions. Therefore in 99,997% of the calls knowing the search_id means knowing the seed, too. An attacker can simply create a lookup table with one millon entries to determine the seed by search_id. In case one of the collisions is hit (which is quite unlikely) he can just search again.
For PHP versions that force the lowest bit to be 1 like PHP 4 and PHP 5 <= 5.2.0 the numbers above are incorrect. These versions use only 19 bits, which also causes fewer collisions.
The Art of Cross Application Attacks
It is not so obvious why the phpBB2 search_id information leak is a problem, because it is not used in a cryptographic manner. The previous paragraphs however contained enough information to explain why this is a problem after all.
- Initializing the random number generator affects not only the PHP script doing it, but also every other script executed by the same process
- When the state of the random number generator is leaked all future random numbers are predictable
- Several applications create passwords, session identifiers, activation links or other cryptographic tokens with mt_rand()
In addition to that you must stop to consider your application (phpBB 2) to be the only one. In the real world multiple applications that perform different tasks are installed on the same server, most probably even in the same VHOST. Imagine for example a company running a support forum (phpBB 2) and a blog (Wordpress).
In such a situation touching the random number seeding becomes a threat. Especially when the seed leaks. A real world attacks against the combination phpBB2 and Wordpress would look like.
- Use a Keep-Alive HTTP Request to search in the phpBB2 forum for the string ‘a’
- The search should return enough results so that multiple pages are returned which leaks the search_id
- A simple table lookup is performed by the attacker to determine the random number seed
- The attacker initializes his random number generator and throws away one random number. (the search_id)
- The attacker then uses the still active Keep-Alive HTTP request to send an admin password reset request to the Wordpress blog.
- The blog uses mt_rand() to generate the activation link and sends it to the admin by email.
- The attacker can calculate the activation link because his random number generator has the same state.
- The exploit triggers the activation link (over the still active Keep-Alive Request) which results in the new admin password beeing sent to the admin.
- Because the new password is generated by mt_rand() the attacker can also calculate it on his side.
- After that the attacker knows the admin password of the Wordpress blog an can take it over.
This shows that installing two independent applications that both use PHP’s random number generators can result in new cross application security vulnerablities that are as serious and dangerous as every vulnerability contained in a single application.
In order to fight this class of cross application vulnerabilities in the next days a generic protection will be added to the Suhosin extension that increases the strength of the mt_rand() seed from a single dword to a multi-dword width. In addition to that an option will be added to ignore the mt_srand() which will be activated by default. This closes the problem of the cross application attack without requiring any changes in the applications.
On the other hand it is strongly recommended for the PHP developers to add more secure random number functions to the PHP core and it is strongly recommended for PHP application developers to keep their fingers away from srand() or mt_srand() and to never ever use rand() or mt_rand() for cryptographic secrets.
Posted in PHP, Security | 122 Comments »
