PHP Weak Random Number Seed Vulnerability

May 7, 2008 – 4:38 AM

Since version 4.2.0 PHP automatically seeds the random number generators on the first usage of rand() and mt_rand(). This is done with the help of the GENERATE_SEED() macro.

Unfortunately it was discovered that the GENERATE_SEED() macro contains several problems that can lead to a weaker seed than expected. In the worst case the seed is directly predictable, which allows to predict all random numbers from the outside.

NOTICE: Neither rand() nor mt_rand() produce cryptographically secure random numbers and should therefore never be used for such applications.

ATTENTION: This vulnerability was not mentioned in the security changelog of PHP 5.2.6

Details:
PHP uses the following macro on the first usage of rand() or mt_rand() within a PHP process to seed the different random number generators.

#ifdef PHP_WIN32
#define GENERATE_SEED() ((long) (time(0) * GetCurrentProcessId() \
* 1000000 * php_combined_lcg(TSRMLS_C)))
#else
#define GENERATE_SEED() ((long) (time(0) * getpid() * 1000000 \
* php_combined_lcg(TSRMLS_C)))
#endif

This produces a seed that depends on the unix timestamp, the process identifier the factor 1000000 and a value between 0 and 1 that itself depends on the current microsecond and the process identifier.

It should be obvious that this not cryptographically strong because the current unix timestamp is known to the attacker and only a part of the process identifier and the microsecond can be considered as entropy. However this macro contains two problems that weakens the produced seed. One affects 32 bit systems and the other only affects 64 bit systems.

zero factor problem
When you have a look on the code generated by the compiler you will see that it first multiplies the timestamp, process identifier and the numerical factor. This is performed in modular integer arithmetic. It was therefore evaluated how likely it is that the multiplication will result in a zero, because then the seed will be zero, too. (on older PHP versions the seed will be 1 for mt_rand() because the lowest bit will be forced to be 1)

1000000 is a number with its lowest 6 bits set to zero. Therefore the multiplication will result in zero if the timestamp and process identifier contain together 26 lower zero bits.

Because the process identifier cannot be influenced directly the timestamp is the easier part to influence. The timestamp has its 26 lower bits all zero once every 2.1 years. This means every 2.1 years there is a second in which the random number generator will be seeded with a seed of zero. An attack happening during this second on a freshly seeded random number generator (very easy to trigger on CGI installations) will therefore allow to predict all generated random numbers.

To overcome the “only once every 2.1 years” problem it is possible to use the lower bits of the process identifier in the multiplication. On some platforms (windows) the process identifier is for example always even which means on these platforms the attack is possible every 1.05 years. This can be further improved by sending more requests at the same time. They all will be handled by different process identifiers and by triggering enough requests the probability of for example 3 lower bits being zero is high. With 3 lower zero bits the attack is feasible every 3 months.

precision problem
On 64 bit systems a different problem arises from the multiplication. Because the multiplication is performed in 64 bit the result of the multiplication usually contains too many digits to be converted to a double without loss of precision. Therefore several lower bits of the results are usually lost during the conversion which results in a seed with zeroes in the lower bits. During our tests the lower 8 bits were most of the time zero.

This means the seed generated by GENERATE_SEED() is in the majority of invocations only 24 bit strong. This means that bruteforcing the seed on a 64 bit system should be done by first populating the higher bits to ensure the result is found faster.

Read the rest of the story…