SektionEins GmbH
www.sektioneins.de
-= Security Advisory =-
Advisory: PHP GENERATE_SEED() Weak Random Number Seed Vulnerability
Release Date: 2008/05/06
Last Modified: 2008/05/06
Author: Stefan Esser [stefan.esser[at]sektioneins.de]
Application: PHP 5 <= 5.2.5
PHP 4 <= 4.4.8
Severity: Weak random number seed might lead to security
problems in PHP applications using random numbers
Risk: Low
Vendor Status: Vendor has released PHP 5.2.6 which uses a different seed
Reference: http://www.sektioneins.de/advisories/advisory-022008-php-generate_seed-weak-random-number-seed-vulnerability.html
Overview:
Quote from 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."
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.
Proof of Concept:
SektionEins GmbH is not going to release a proof of concept
exploit for this vulnerability.
Disclosure Timeline:
15. February 2008 - Notified security@php.net
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
CVE Information:
The Common Vulnerabilities and Exposures project (cve.mitre.org) has
not assigned a name to this vulnerability yet.
GPG-Key:
pub 1024D/15ABDA78 2004-10-17 Stefan Esser
Key fingerprint = 7806 58C8 CFA8 CE4A 1C2C 57DD 4AE1 795E 15AB DA78
Copyright 2008 SektionEins GmbH. All rights reserved.