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; 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.strip().split()[-1] s = lines.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