Date: Tue, 6 May 2008 10:16:01 +0200
From: Stefan Esser <stefan.esser@...tioneins.de>
To: bugtraq@...urityfocus.com, full-disclosure@...ts.grok.org.uk
Subject: Advisory SE-2008-02: PHP GENERATE_SEED() Weak Random Number Seed Vulnerability

-----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@....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 <stefan.esser@...tioneins.de>
   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-----

Powered by blists - more mailing lists