HITCON CTF Quals 2017 - Secret Server Revenge

secret_server_revenge.py

from sock import Sock
# from Crypto.Hash import SHA256
from hashlib import sha256, md5
import string
import os, base64, time, random, string
from pprint import pprint

local = 1

if local:
    f = Sock("127.1 3030")
else:
    # f = Sock("52.193.157.19 9999")
    f = Sock("52.192.29.52 9999")

suf, res = f.read_until_re(r"SHA256\(XXXX\+(.*?)\) == (\w+)").groups()
print suf, res

alpha = string.ascii_letters+string.digits

from itertools import product

print "pow"
for pref in product(alpha, repeat=4):
    pref = "".join(pref)
    if local or sha256(pref + suf).hexdigest() == res:
        print "FOUND", pref
        break
else:
    print "FAIL"
    quit()

f.send_line(pref)
print `f.read_until("XXXX:")`

def recv():
    s = f.read_line()
    assert s[-1] == "\n"
    s = s[:-1].decode("base64")
    return s

def xor(a, b):
    return "".join(chr(ord(a) ^ ord(b)) for a, b in zip(a, b))

def modify(ct, msg1, msg2):
    assert len(ct) == 32
    msg1 = pad(msg1)
    msg2 = pad(msg2)
    return xor(xor(ct[:16], msg1), msg2) + ct[16:]

def pad(msg):
    pad_length = 16-len(msg)%16
    return msg+chr(pad_length)*pad_length

def unpad(msg):
    return msg[:-ord(msg[-1])]

QCNT = 0
def sendct(ct):
    global QCNT
    QCNT += 1
    if QCNT == 340:
        print "INTERCEPT! TRY", len(candidates)

        lst = list(candidates)
        for c in lst:
            print `c`
        test = lst.pop()
        assert test.startswith("token: ")
        test = test[7:].ljust(56, "\x41")

        print "CHECK", test.encode("hex")
        ct = modify(welcome, WEL, "check-token")
        ct = base64.b64encode(ct).replace("\n", "")
        f.send_line(ct.strip())

        tok = base64.b64encode(test).replace("\n", "")
        f.send_line(tok)
        with open("log", "a") as fd:
            res = f.read_all()
            print `res`
            fd.write(`res` + "\n")
        quit()

    ct = base64.b64encode(ct).replace("\n", "")
    f.send_line(ct.strip())
    return recv()

def send(cmd):
    ct = modify(welcome, WEL, cmd)
    return sendct(ct)

def get_md5(ct, preflen, data=None):
    if data is None:
        data = data1
    ct1 = modify(welcome, WEL, data)
    ct2 = ct
    skip = 32 + len(ct) - preflen
    ct3 = modify(welcome, WEL,  "X" * 15 + chr(skip))
    return sendct(ct1 + ct2 + ct3)

WEL = "Welcome!!"

welcome = recv()
iv = welcome[:16]
print "welcome ", `welcome`

token_enc = send("get-token")

print "get token", `token_enc`

data1 = "get-md5".ljust(15, "X") + "\x01"

def _cycle(ch):
    seen = {ch}
    known = ch

    while True:
        predicted_md5 = md5(data1[7:] + xor(known, welcome[16])).digest()
        known = xor(predicted_md5[0], iv[0])
        if known in seen:
            return seen
        seen.add(known)

cycles = {}
for ch in xrange(256):
    ch = chr(ch)
    cycles[ch] = _cycle(ch)
    print `ch`, len(cycles[ch]), cycles[ch]

known_pairs = [
    (welcome[16:], xor(iv, pad(WEL)), 16),
    (token_enc[16:], xor(iv, pad("token: ")), 7),
]
known_pts = {
    pt for ct, pt, num in known_pairs
}

CNTR = 1
db = {}
while len(db) < 128:
    print "STAT:", len(db), CNTR
    found = 0
    for ct, pt, num in known_pairs:
        known = pt[0]
        if known in db:
            continue
        found = 1

        CNTR += 1
        ct = get_md5(ct, 1)
        db[known] = ct
        print `known`, ct.encode("hex")

        predicted_md5 = md5(data1[7:] + xor(known, welcome[16])).digest()
        print "predicted", predicted_md5.encode("hex")
        # known_pairs.append((ct[16:], xor(iv + "\x00" * 16, pad(predicted_md5)), 32))
        known_pairs.append((ct[16:32], xor(iv, pad(predicted_md5))[:16], 16))
        known_pts.add(known_pairs[-1][1])
        print
    if found:
        continue

    best = -1, None
    for ct, pt, num in known_pairs:
        for l in xrange(1, num):
            if l >= 16:
                break
            known = pt[:l]
            predicted_md5 = md5(data1[7:] + xor(known, welcome[16:16+l])).digest()
            pred_pt = xor(iv, predicted_md5)
            if pred_pt in known_pts:
                continue
            cycle = cycles[pred_pt[0]]
            improve = len(cycle - set(db))
            best = max(best, (improve, (ct, pt, l)))

    assert best[0] != -1

    ct, pt, l = best[1]
    known = pt[:l]
    predicted_md5 = md5(data1[7:] + xor(known, welcome[16:16+l])).digest()

    pred_pt = xor(iv, predicted_md5)
    assert pred_pt not in known_pts

    CNTR += 1
    ct = get_md5(ct, l)
    known_pairs.append((ct[16:32], pred_pt, 16))
    known_pts.add(pred_pt)
    print "ADD NEW", best[0]


print "LEFT", 340 - CNTR

dbrev = {v: k for k, v in db.items()}

trick = {}
for i in (32, 48, 64):
    CT = token_enc[i:i+16]
    IV = token_enc[i-16:i]

    ct = get_md5(CT, 1)
    if ct not in dbrev:
        print "ABORT"
        continue
        # quit()
    trick[i-16] = xor(IV, dbrev[ct])
    print i, `trick[i-16]`


candidates = {"token: "}
num_known = 7
for l in xrange(num_known + 1, 7 + 56 + 1):
    print l, "candidates:", len(candidates), "CNTR", CNTR, "KNOWN", num_known, "/", 56 + 7
    # for c in candidates:
    #     print `c`
    if not candidates:
        print "EMPTY :("
        quit()

    if num_known in trick:
        candidates = {c + trick[num_known] for c in candidates}
        num_known += 1
        continue

    CNTR += 1
    ct0 = ct = get_md5(token_enc[16:], l)
    CNTR += 1
    ct = get_md5(ct[16:], 1)
    cyclen = 1
    print l, ct.encode("hex")

    while ct not in dbrev:
        CNTR += 1
        ct = get_md5(ct[16:], 1)
        cyclen += 1

    def decbc(civ, pt, ct):
        cbc = ""
        for j in xrange(0, len(pt), 16):
            cbc += xor(pt[j:j+16], civ)
            civ = ct[j:16+j]
        return cbc

    md5char = xor(iv[0], dbrev[ct])
    print "match", `md5char`, "cyclen", cyclen
    candidates2 = set()
    for pt in candidates:
        for ch in map(chr, range(256)):
            # if trick.get(num_known, ch) != ch:
            #     # print len(pt), `pt`, `ch`
            #     continue
            test = pt + ch
            # ^ token_enc[l-1])
            known = decbc(civ=token_enc[:16], pt=test, ct=token_enc[16:])
            good = 1
            for i in xrange(cyclen):
                predicted_md5 = md5(data1[7:] + xor(known, welcome[16:])).digest()
                if i == 0 and l > 16:
                    cbc = decbc(civ=welcome[16:32], pt=known, ct=token_enc[16:])
                    predicted_md5 = md5(data1[7:] + cbc).digest()

                if i != cyclen - 1:
                    if predicted_md5[0] == md5char:
                        good = 0
                        break
                else:
                    if predicted_md5[0] == md5char:
                        break
                    else:
                        good = 0
                        break
                known = xor(predicted_md5[0], iv[0])
            if good:
                # print "mmmatch", `ch`
                candidates2.add(test)
    candidates = candidates2
    num_known += 1
    print

    LIM = 10

    if len(candidates) < LIM and num_known != 63:
        continue
    print "TOO MUCH", len(candidates)

    while True:
        data = "get-md5" + os.urandom(8) + "\x01"
        chars = set()
        notinside = set()
        for test in candidates:
            known = decbc(civ=token_enc[:16], pt=test, ct=token_enc[16:])
            cbc = decbc(civ=welcome[16:32], pt=known, ct=token_enc[16:])
            predicted_md5 = md5(data[7:] + cbc).digest()
            c = xor(iv[0], predicted_md5[0])
            if c not in db:
                notinside.add(c)
            chars.add(c)
        # else:
        #     break
        if len(chars) >= min(len(candidates), 10):
            break

    print "FOUND DATA", `data`
    for c in candidates:
        print len(c), l
        break
    CNTR += 1
    ct0 = ct = get_md5(token_enc[16:], l, data=data)
    CNTR += 1
    ct = get_md5(ct0[16:], 1)
    if ct not in dbrev:
        md5char = None
    else:
        md5char = xor(iv[0], dbrev[ct])
    candidates2 = set()
    for test in candidates:
        known = decbc(civ=token_enc[:16], pt=test, ct=token_enc[16:])
        cbc = decbc(civ=welcome[16:32], pt=known, ct=token_enc[16:])
        predicted_md5 = md5(data[7:] + cbc).digest()
        # known = xor(predicted_md5[:seclen], iv[:seclen])
        if md5char is None:
            if xor(iv[0], predicted_md5[0]) not in db:
                candidates2.add(test)
        elif predicted_md5[0] == md5char :
            candidates2.add(test)
    candidates = candidates2

print "FINISH", l, "CNTR", QCNT, CNTR, num_known
print len(candidates)

for i in xrange(1000):
    sendct(welcome)