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/SE-2008-02.txt

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.

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 (at) php (dot) net [email concealed]
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.

Hash: SHA1

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/SE-2008-02.txt

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 (at) php (dot) net [email concealed]

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 <stefan.esser (at) sektioneins (dot) de [email concealed]>

Key fingerprint = 7806 58C8 CFA8 CE4A 1C2C 57DD 4AE1 795E 15AB DA78

Copyright 2008 SektionEins GmbH. All rights reserved.

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.4.8

iEYEARECAAYFAkggLjkACgkQSuF5XhWr2nj3LQCeMaGz86kl+/EygBX7FEOhU/hC

0woAoJKuQc3EW23v0l32rBZf/aguGuri

=aqwd

-----END PGP SIGNATURE-----

[ reply ]