Apr 19

PlaidCTF 2014 parlor writeup

The Plague is running a betting service to build up funds for his massive empire. Can you figure out a way to beat the house? The service is running at 54.197.195.247:4321.

This challenge was a betting game with a “prove” of fairness. We could choose odds (a power of 2) and a bet, and if a pseudorandom generated number will be divided by that odds, than we’ll get a reward (bigger odds, less chance – biffer reward). If the number will not be divided by odds – we are given the remainder. How PRNG did work?

PRNG was simply md5(server_nonce + client_nonce). After any round, we could ask server for its nonce, so we could easily check whether the PRNG was fair. After that server generated new nonce so we can’t reuse the one we know.

We can apply length extension attack here: we learn hash from given remainder and we also know length of server_nonce. So we can generate lots of length extensions (with different random appended data) and select good hashes (with more zero bits at the end).

But there’s one problem: odds are limited to 2^100. This means we can only learn lower 100 bits of md5 hash, while the whole hash is 128 bits. Therefore, we can’t extend it. 28 bits are not so much, how can we bruteforce it?

We can again apply length extension attack!

  • 1. get 100 bits for hash1 = md5(server_nonce + "x")
  • 2. get 100 bits for hash2 = md5(server_nonce + "x" + padding + "y")
  • 3. for all possible 28bits for hash1 try to extend hash1 with “y” and check if 100 bits of result match hash2

Sadly bruteforcing 28 bits with length extension on each step takes too long in python, so I coded lib in C and attached it to python using ctypes.

C lib:

#include <stdio.h>
#include <string.h>
#include <openssl/md5.h>
 
// gcc fast.c -shared -o fast.so -lssl -lcrypto -fPIC -O3
 
unsigned int extend(unsigned int A, unsigned int B, unsigned int C, unsigned int D, char *testhash2) {
    MD5_CTX ctx;
    unsigned char buffer[MD5_DIGEST_LENGTH];
    int i;
 
    MD5_Init(&ctx);
    MD5_Update(&ctx, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 64);
 
    ctx.A = htonl(A);
    ctx.B = htonl(B);
    ctx.C = htonl(C);
    ctx.D = htonl(D);
 
    MD5_Update(&ctx, "1\n", 2);
    MD5_Final(buffer, &ctx);
 
    char res[40];
    for (i = 0; i < 16; i++) {
      sprintf(&res[2*i], "%02x", buffer[i]);
    }
    if (!memcmp(res + 16, testhash2 + 16, 8)) {
        return A;
    }
    return 0;
}
 
 
unsigned int brute(unsigned int A, unsigned int B, unsigned int C, unsigned int D, char *testhash2) {
    unsigned int i;
    for (i = 0; i < 1 << 28; i++) {
        A = (A & 0xf) | (i << 4);
 
        if ((i & 0xfffff) == 0)
            printf("%08x\n", i);
 
        unsigned int res = extend(A, B, C, D, testhash2);
        if (res != 0) {
            return res;
        }
    }
    return 0;
}

And python exploit:

import os
import ctypes
import subprocess
 
from sock import Sock
from libnum import n2s, s2n
from struct import pack, unpack
 
dll = ctypes.cdll.LoadLibrary("./fast.so")
 
 
def extend(data, hash, append, length=16):
    # when we know hash - we use hash_extender for more flexibility
    s = subprocess.check_output(["hash_extender", "-d", data, "-s", hash, "-a", append, "-l", str(length), "-f", "md5"])
    lines = s.splitlines()
    sig = lines[2].strip().split()[-1]
    s = lines[3].strip().split()[-1].decode("hex")
    return s, sig
 
 
p1 = "x\n"
app = "1\n"
 
f = Sock("54.197.195.247 4321", timeout=1000)
f.read_one()
f.send("1\n")
f.read_one()
f.send("100\n")
f.read_one()
f.send("2\n")
f.read_one()
f.send("0\n")
f.read_one()
f.send("3\n")
f.read_one()
f.send(p1)
n = int(f.read_until_re(r"generated (\d+),").group(1))
lowhash = n2s(n).rjust(16, "\x00").encode("hex")[7:]
print lowhash
 
ext1s, ext1sig = extend(p1, "a" * 32, app)
f.send("3\n")
f.read_until("round!")
f.send(ext1s)
n = int(f.read_until_re(r"generated (\d+),").group(1))
lowhash2 = n2s(n).rjust(16, "\x00").encode("hex")[7:]
print lowhash2
 
A, B, C, D = unpack(">4I", lowhash.rjust(32, "0").decode("hex"))
test_hash2 = lowhash2.rjust(32, "0")
 
A = dll.brute(A, B, C, D, test_hash2)
hash1 = pack(">4I", A, B, C, D).encode("hex")
 
 
cash = 100
for i in xrange(100000):
    r = os.urandom(8).encode("hex")
    fake, hash2 = extend(p1, hash1, r)
    num = int(hash2, 16)
    e = 0
    while num % 2 == 0:
        e += 1
        num >>= 1
 
    if e > 100:
        e = 100
 
    if e == 0:
        continue
 
    print i, e, "checking...", "cash", cash
 
    f.send("1\n")
    f.read_one()
    f.send(str(e) + "\n")
    f.read_one()
 
    f.send("2\n")
    f.read_one()
    f.send("%s\n" % cash)
    f.read_one()
 
    f.send("3\n")
    f.read_one()
    f.send(fake)
    print f.read_one()
 
    f.send("4\n")
    print "CASH?", f.read_one()
    if e > 2:
        cash *= 2

hellman

Leave a Reply

Your email address will not be published.