[UNIX] PHP GENERATE_SEED() Weak Random Number Seed Vulnerability

The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com
- - promotion

The SecuriTeam alerts list - Free, Accurate, Independent.

Get your security news from a reliable source.
http://www.securiteam.com/mailinglist.html

- - - - - - - - -



PHP GENERATE_SEED() Weak Random Number Seed Vulnerability
------------------------------------------------------------------------


SUMMARY

" <http://www.php.net> PHP is a widely-used general-purpose scripting
language that is especially suited for Web development and can be embedded
into HTML." Weak random number seed might lead to security problems in PHP
applications using random numbers.

DETAILS

Vulnerable Systems:
* PHP 5 version 5.2.5
* PHP 4 version 4.4.8

Immune Systems:
* PHP 5 version 5.2.6

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.

Disclosure Timeline:
15. February 2008 - Notified security@xxxxxxx
01. May 2008 - PHP developers released PHP 5.2.6
06. May 2008 - Public Disclosure

Recommendation:
It is recommended to upgrade to the latest version of PHP which also fixes
additional vulnerabilities reported by third parties.

Grab your copy at: <http://www.php.net/downloads.php>
http://www.php.net/downloads.php


ADDITIONAL INFORMATION

The information has been provided by <mailto:stefan.esser@xxxxxxxxxxxxxx>
Stefan Esser.
The original article can be found at:
<http://www.sektioneins.de/advisories/SE-2008-02.txt>
http://www.sektioneins.de/advisories/SE-2008-02.txt



========================================


This bulletin is sent to members of the SecuriTeam mailing list.
To unsubscribe from the list, send mail with an empty subject line and body to: list-unsubscribe@xxxxxxxxxxxxxx
In order to subscribe to the mailing list, simply forward this email to: list-subscribe@xxxxxxxxxxxxxx


====================
====================

DISCLAIMER:
The information in this bulletin is provided "AS IS" without warranty of any kind.
In no event shall we be liable for any damages whatsoever including direct, indirect, incidental, consequential, loss of business profits or special damages.