0CTF 2016 Quals - rand 2 Writeup

Published at 16th March, 2016

Challenge

<?php
include('config.php');
session_start();

if($_SESSION['time'] && time() - $_SESSION['time'] > 60) {
    session_destroy();
    die('timeout');
} else {
    $_SESSION['time'] = time();
}

echo rand();
if (isset($_GET['go'])) {
    $_SESSION['rand'] = array();
    $i = 5;
    $d = '';
    while($i--){
        $r = (string)rand();
        $_SESSION['rand'][] = $r;
        $d .= $r;
    }
    echo md5($d);
} else if (isset($_GET['check'])) {
    if ($_GET['check'] === $_SESSION['rand']) {
        echo $flag;
    } else {
        echo 'die';
        session_destroy();
    }
} else {
    show_source(__FILE__);
}

Solve

Obviously, we need to predict the 5 random number generated in ?go and submit it via ?check[]=num1&check[]=num2&check[]=num3&check[]=num4&check[]=num5 to get the flag.

We know that rand() is a PRNG and for a fixed seed it will generate exactly the same random number sequence. In other words, the number from rand() is decided if we give the seed and know how much rand() calls has been made before this call (the index in the sequence).

Thus in order to predict the random number, we seperate the challenge into two parts:

  1. Assume that the outputed rand() is the first number in the sequence and we search the seed so that the first number of the sequence is the number we got from the page.

  2. Enforce the creation of PHP process so that the outputed rand() we got is indeed the first number in the sequence.

Search The Seed

From PHP source code we could find that PHP rand() function just wraps glibc rand():

ext/standard/rand.c

PHPAPI long php_rand(TSRMLS_D)
{
    long ret;

    if (!BG(rand_is_seeded)) {
        php_srand(GENERATE_SEED() TSRMLS_CC);
    }

#ifdef ZTS
    ret = php_rand_r(&BG(rand_seed));
#else
# if defined(HAVE_RANDOM)
    ret = random();
# elif defined(HAVE_LRAND48)
    ret = lrand48();
# else
    ret = rand();
# endif
#endif

    return ret;
}

Besides, it shows that the seed is generated at the first call of PHP rand() if srand() is not called before.

The GENERATE_SEED function is defined as follows:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

It seems that that we can predict the seed as well, as suggested in this
StackOverflow answer. However, I decided to exhaustively find the seed because the seed is just an unsigned int and the program should be extremely simple.

Since PHP uses glibc rand(), I wrote a C program to search the seed to improve performance.

The distributed seed searcher crack_seed_distributed.c accepts the following parameters:

  • worker id

  • the target random number to match

  • the seed to start search

  • how much seed to search

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

int target_rand;
int worker_id, start_from, calc_times;

int main(int argc, char *argv[]) {

  if (argc != 5) {
    printf("Incorrect parameters\n");
    return 1;
  }

  target_rand = atoi(argv[1]);
  worker_id = atoi(argv[2]);
  start_from = atoi(argv[3]);
  calc_times = atoi(argv[4]);

  for (unsigned int seed = start_from, i_max = start_from + calc_times, n_times = 0; seed < i_max; ++seed, ++n_times) {
    if ((n_times & 0xFFFFFF) == 0x0) {
      printf("[#%d] %d%% seed ~= %d\n", worker_id, int(float(n_times) / calc_times * 100), seed);
      fflush(stdout);
    }
    srand(seed);
    if (rand() == target_rand) {
      printf("[#%d] seed = %d\n", worker_id, seed);
      printf("http://202.120.7.202:8888/?");
      for (int k = 0; k < 4; ++k) {
          printf("check[]=%d&", rand());
      }
      printf("check[]=%d\n", rand());
      fflush(stdout);
      return 3;
      break;
    }
  }

  return 0;
}

And here is a simple dispatcher runner.js written in Node.js:

if (process.argv.length !== 3) {
  console.log('Incorrect parameters');
  return;
}

var os = require('os');
var spawn = require('child_process').spawn;

var PHP_RAND_MAX = 2147483647;

var number_of_cores = os.cpus().length - 1;
var target_rand = process.argv[2];

var worker_works = Math.ceil(PHP_RAND_MAX / number_of_cores);

var c_start_from = [0], c_start_from_last = 0;
for (var i = 1; i < number_of_cores; ++i) {
  var c_current = c_start_from_last + worker_works;
  c_start_from.push(c_current);
  c_start_from_last = c_current;
}

console.log('Number of workers: %d', number_of_cores);
console.log(c_start_from);

for (var i = 0; i < number_of_cores; ++i) {
  spawn('./crack_seed_distributed', [
    target_rand,
    i,
    c_start_from[i],
    worker_works
  ], {
    stdio: 'inherit'
  });
}

To find the seed given the output of first rand():

node runner.js 1000412889

Three notes:

  1. There might be multiple matched seed for a given random number.

  2. glibc RNG algorithm is different from LLVM libc++. Do not run seed searcher in Mac OS X.

  3. glibc rand() uses locks. Thus multi-thread is useless.

In a 40-core server, we can find the seed in one minute.

Enforce Fresh PHP Process

We can learn that the server is running Apache + mod_php by looking at the response header. This paper suggests that we can establish many keep-alive connections to enforce Apache to spawn new worker process to handle the new connection. Thus we only need to start many (e.g. 300) parallels requests and we may assume that the last of the request is handled in a fresh process with high confidence.

Notice that the session will be destroyed in 60 seconds so we also need a session-keeper.

var request = require('request');
var async = require('async');
var http = require('http');

var completed_request = 0;

var sessionsToKeep = [];

var q = async.queue(function (task, callback) {
  request.get({
    url: 'http://202.120.7.202:8888/?go=1',
    agent: task.agent,
  }, function (err, res, body) {
    var resp = res.body.trim();
    var meta = {
      cookie: res.headers['set-cookie'][0],
      response: resp,
      rand: resp.slice(0, resp.length - 32),
      hash: resp.slice(resp.length - 32),
    };
    completed_request++;
    if (completed_request >= 100) {
      sessionsToKeep.push(meta);
      meta.keep = true;
    }
    console.log('#%d', completed_request);
    console.log('set cookie = %s', meta.cookie);
    console.log('response = %s', meta.response);
    console.log('rand = %s', meta.rand);
    console.log('hash = %s', meta.hash);
    console.log('keep = %s', meta.keep ? 'Yes!' : 'no');
    console.log('-------------');
    callback();
  });
}, 10);

for (var i = 0; i < 120; ++i) {
  var agent = new http.Agent({
    keepAlive: true
  });
  q.push({
    idx: i,
    agent: agent
  });
}

setInterval(function () {
  var sessionKept = 0;
  var kq = async.queue(function (task, callback) {
    var cookie = task.cookie.split(';')[0];
    request.get({
      url: 'http://202.120.7.202:8888/',
      headers: {
        cookie: cookie,
      }
    }, function (err, res, body) {
      console.log('maintaining cookie: %s', cookie);
      setTimeout(function () {
        callback();
      }, 300);
    });
  }, 2);
  kq.drain = function () {
    console.log('%d sessions maintained, sessionsToKeep.length = %d', sessionKept, sessionsToKeep.length);
  };
  sessionsToKeep.forEach(function (sess) {
    sessionKept++;
    kq.push(sess);
  });
}, 20000);

The above Node.js program establishes 120 parallel keep-alive requests and keep session alive for the last 20 requests. We only need to use seed-searcher to crack the seed of the random number of the last request. After finding the seed and guessing the five unknown random numbers, we can verify its correctness by comparing their md5 hash to the server response.

Comments