bg-wall

What's New

Inside the industry and inside the agency

31 Mar 2010

Under the hood

by Robert King

PHP 5.2.13 was released last month and right at the top of the security fixes for this release was "Improved LCG entropy. (Rasmus, Samy Kamkar)". This rather brief note caught my eye so I thought I would take a look under the hood to see what had changed.

LCG stands for Linear Congruential Generator, which is basically an algorithm for generating pseudorandom numbers. PHP uses the LCG algorithm in a few places, the most obvious being the lcg_value() function. It is also used in the uniqid() function if you pass a value of true as the second parameter.

The code for the LCG is located in ext/standard/lcg.c within the PHP source. From the PHP version control we can see the changes have been made to the lcg_seed() function, this is the 5.2.12 code:

static void lcg_seed(TSRMLS_D)
{
	struct timeval tv;

	if (gettimeofday(&tv, NULL) == 0) {
		LCG(s1) = tv.tv_sec ^ (~tv.tv_usec);
	} else {
		LCG(s1) = 1;
	}
#ifdef ZTS
	LCG(s2) = (long) tsrm_thread_id();
#else
	LCG(s2) = (long) getpid();
#endif

	LCG(seeded) = 1;
}

As you can see the PHP LCG is actually a combination of two LCG's which are being seeded in different ways. In version 5.2.13 the code is now (I have highlighted the changes):

static void lcg_seed(TSRMLS_D)
{
	struct timeval tv;

	if (gettimeofday(&tv, NULL) == 0) {
		LCG(s1) = tv.tv_sec ^ (tv.tv_usec<<11);
	} else {
		LCG(s1) = 1;
	}
#ifdef ZTS
	LCG(s2) = (long) tsrm_thread_id();
#else
	LCG(s2) = (long) getpid();
#endif

	/* Add entropy to s2 by calling gettimeofday() again */
	if (gettimeofday(&tv, NULL) == 0) {
		LCG(s2) ^= (tv.tv_usec<<11);
	}

	LCG(seeded) = 1;
}

So the seeding of both LCG's has been changed, but how has this improved the entropy? Previously the second LCG was just being seeded with getpid(), which returns the process id of the PHP process ( which if your running mod_php will be the Apache process ). If you lookup the PHP equivalent function getmypid() you will see an interesting warning in the notes: "Process IDs are not unique, thus they are a weak entropy source. We recommend against relying on pids in security-dependent contexts." Indeed in the most common Apache configurations repeat calls to a script in a short period will return the same process id. To improve the seeding of this LCG then the current microsecond value from gettimeofday has been or'ed in. Why shift the microsecond value left 11 places ? The maximum value of microseconds is 999999 which is 0xF423F, shifted we get 0x7A11F800. So shifting 11 places just fits the microsecond value into 31 bits. The process id from getpid() will typically be up to 0xFFFF so combined in this way they make a seed with a greater range. Lets see what values we get if we write an equivalent PHP script to compare the old and new seed values:

$old = getmypid();
$tv = gettimeofday();
$new = getmypid() ^ ($tv['usec']<<11);
echo "Old value: $old
"; echo "New value: $new
";

Reloading this script with a couple of seconds between I see:

Old value: 14025
New value: 1644429001

Old value: 14025
New value: 2031015625

Old value: 14025
New value: 1393229513

There is clearly, with this change, considerably less chance of seeding the same value to the second LCG and thereby having it generate the same pseudorandom sequence on each run, i.e. improved LCG entropy.

Back to blog posts

Leave a comment

Contact us to discuss your digital requirements
Tel. +44 (0)20 7183 4999

Enquiry Form
Subscribe
  • Twitter feed unable to load