-----BEGIN PGP SIGNED MESSAGE----- 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-----