Skip to content

Instantly share code, notes, and snippets.

@hellman
Last active October 9, 2019 13:33
Show Gist options
  • Save hellman/aafa4d20952c5a02ef4a22abecc5a0dd to your computer and use it in GitHub Desktop.
Save hellman/aafa4d20952c5a02ef4a22abecc5a0dd to your computer and use it in GitHub Desktop.
Balsn CTF 2019 - harc4

In this challenge we have an RC4-based hash function. It uses the Merkle-Damgard structure with Davis-Meyer feed-forward and the RC4 stream generation from the key as the block cipher (of course it is not).

The state and the output is 32 bytes, and message blocks have size 224. Each input (i.e., the key) for the RC4 function consists of 224-byte message block concatenated with the previous output (or IV for the first block). The 32-byte IV is secret.

We can query up to 8 hash function values on our inputs and we are given the admin password's hash. Our goal is to find a preimage for it.

During the competition, I missed the obviously trivial way to recover the "secret" IV (the challenge author told me about it afterwards): send an empty password to hash! Then no blocks are processed and the output is exactly the IV. However, I used all 8 queries with 1-block password to recover the IV.

Another possibility would be to query an arbitrary password, and use it's hash as the IV for the second block compression in a two-block forgery! I am embarassed to have missed this trivial tricks.

RC4 Toolkit

The key scheduling part of RC4 is very simple:

def KS(key, steps=256):
    x = 0
    box = list(range(256))
    for i in range(steps):
        x = (x + int(box[i]) + int(key[i % len(key)])) % 256
        box[i], box[x] = box[x], box[i]
    return box

When we fully control the key, we can easily forge any desirable permutation as the output box: we simply use 256-byte key and iteratively adjust key[i] to correct the value of x to the index of the desired value for the position i. In the challenge, the last 32 bytes of the key are "secret"/fixed. However, we still can control the first 224 bytes and we can arbitrarily permute the first 224 bytes of box before the fixed part of the key is reached.

def forgebox(wantbox):
    x, iv = 0, []
    box = list(range(256))
    for i, wanty in enumerate(tab):
        wantx = box.index(wanty)
        k = (wantx - x - box[i]) % 256
        x = (x + box[i] + k) % 256
        box[i], box[x] = box[x], box[i]
        iv.append(k)
    return bytes(iv)

A more difficult part is to forge any particular keystream. The idea is similar: we follow the stream generation and try to modify untouched values to produce the desired value at each step.

def STREAM(box, n=32):
    x = y = 0
    out = []
    for i in range(n):
        x = (x + 1) % 256
        y = (y + box[x]) % 256
        box[x], box[y] = box[y], box[x]
        out.append(box[(box[x] + box[y]) % 256])
    return bytes(out)

Solution

TODO: writeup unfinished...

The final solution script: requires < 10 attempts (connections) due to stupid IV recovery, otherwise works in 1 connection; takes 10-60 seconds to forge.

import os, sys
sys.setrecursionlimit(100000)
import binascii

from Crypto.Cipher import ARC4
from collections import Counter, defaultdict

import hashlib
from random import randint, shuffle, choice

def KS(key, steps=256):
    x = 0
    box = list(range(256))
    for i in range(steps):
        x = (x + int(box[i]) + int(key[i % len(key)])) % 256
        box[i], box[x] = box[x], box[i]
    return box

def STREAM(box, n=32):
    x = y = 0
    out = []
    for i in range(n):
        x = (x + 1) % 256
        y = (y + box[x]) % 256
        box[x], box[y] = box[y], box[x]
        out.append(box[(box[x] + box[y]) % 256])
    return bytes(out)

def harc4(x, IV):
    ksz = ARC4.key_size[-1]
    csz = ksz - len(IV)

    state = IV
    for i in range(0, len(x), csz):
        key = x[i:i+csz] + state
        cipher = ARC4.new(key)
        state = cipher.encrypt(state)
    return state

def forgebox(wantbox):
    x = 0
    iv = []
    box = list(range(256))
    assert len(set(wantbox)) == len(wantbox)
    for i, wanty in enumerate(wantbox):
        wantx = box.index(wanty)
        assert wantx >= i
        k = (wantx - x - box[i]) % 256
        x = (x + box[i] + k) % 256
        box[i], box[x] = box[x], box[i]
        assert box[i] == wanty
        iv.append(k)
    return bytes(iv)

def forgeleak_box(ids, avoid={}):
    ids = list(ids)
    x = y = 0
    box = [None] * 256
    for wantleak in ids:
        x = (x + 1) % 256
        off = randint(0, 255)
        for wanty in range(256):
            wanty = (wanty + off) % 256

            bx = (wanty - y) % 256
            yy = (y + bx) % 256
            by = (wantleak - bx) % 256

            if x >= 224 or yy >= 224: continue
            if bx >= 224 or by >= 224: continue

            if box[x] is not None: continue
            if bx in box: continue
            if box[yy] is not None: continue
            if by in box: continue
            if bx == by: continue
            if x == yy: continue

            if x in avoid: continue
            if yy in avoid: continue
            if bx in avoid.values(): continue
            if by in avoid.values(): continue

            assert box[x] is None
            box[x] = bx
            assert box.count(box[x]) == 1

            assert yy == wanty

            assert box[yy] in (None, by)
            box[yy] = by
            assert box.count(box[yy]) == 1, box.count(box[yy])
            break
        else:
            # fail.. try again
            return forgeleak_box(ids, avoid)
        y = (y + box[x]) % 256

        assert (box[x] + box[y]) % 256 == wantleak
    return box


def forgefull(toleak, extra={}):
    box = forgeleak_box(toleak, avoid=extra)
    free = list(range(224))
    shuffle(free)
    box = box[:224]
    free = [v for v in free if v not in box and v not in extra.values()]
    for v in extra.values():
        assert v not in box
    freeids = set()
    for i, v in enumerate(box):
        if i in extra:
            assert v is None
            box[i] = extra[i]
        elif v is None:
            box[i] = free.pop()
            freeids.add(i)
    freeids = list(freeids)
    iv = forgebox(box[:224])
    return iv

def forgestream(wantstream, secret):
    while True:
        alphabet = list(set(wantstream))
        shuffle(alphabet)
        extra = {64+i: alphabet[i] for i in range(len(alphabet))}
        inds = [64+alphabet.index(v) for v in wantstream]

        box0 = forgeleak_box(inds, avoid=extra)
        assert box0[224:] == [None] * 32
        box0 = box0[:224]
        free0 = [v for v in range(224) if v not in box0 and v not in extra.values()]
        for itr1 in range(10):
            free = list(free0)
            box = list(box0)
            shuffle(free)
            for v in extra.values():
                assert v not in box

            freeids = set()
            for i, v in enumerate(box):
                if i in extra:
                    assert v is None
                    box[i] = extra[i]
                elif v is None:
                    box[i] = free.pop()
                    freeids.add(i)
            freeids = list(freeids)
            assert 223 in freeids

            prev_badi = -1
            prev_box = list(box)

            for jtr in range(1000):
                tt = randint(1, 2)
                iv = bytes(forgebox(box))
                ivkey = iv + secret

                x = 0
                tab = list(range(256))
                badi = None
                for i in range(256):
                    x = (x + int(tab[i]) + int(ivkey[i])) % 256
                    if i >= 224 and x not in freeids:
                        badi = i
                        break
                    tab[i], tab[x] = tab[x], tab[i]
                if badi is None:
                    break

                if badi >= prev_badi:
                    # swap to improve further
                    prev_box = list(box)
                    prev_badi = badi
                else:
                    # rollback and swap
                    box = list(prev_box)
                    badi = prev_badi

                for i in reversed(range(badi+1)):
                    if randint(0, tt) == 0 and i not in box:
                        j = choice(freeids)
                        box[j] = i
                        assert len(set(box)) == len(box) == 224, len(set(box))
                        break
                else:
                    break

            if badi is None:
                ks = KS(ivkey)
                stream = STREAM(ks)
                assert stream == wantstream
                return iv

def recover_iv(pos, known=b""):
    if pos == 32:
        cands.append(known)
        return
    best = Counter()
    for iv, out in zip(ivs, outs):
        prebox = KS(iv + known, steps=224 + pos)
        stream = STREAM(prebox, 32)
        k = stream[pos] ^ out[pos]
        best[k] += 1
    for k, cnt in best.most_common():
        # to be sure and to reduce bruteforce,
        # consider only when we have
        # at least two evidences for the key byte
        if cnt <= 1: continue
        known2 = known + bytes([k])
        recover_iv(pos+1, known2)

ivs = []
for _ in range(8):
    inds = list(range(224))
    shuffle(inds)
    iv = bytes(forgefull(inds[:32]))
    ivs.append(iv)

import ast

def getcon():
    f = Sock("harc4.balsnctf.com 5450")
    id = 0
    prf = os.urandom(5).hex().encode("ascii")
    for iv in ivs:
        f.read_until(b"> ")
        f.send_line(b"register")
        f.send_line(b"%b%d" % (prf, id))
        f.send_line(iv.hex().encode("ascii"))
        id += 1
    f.read_until(b"> ")
    f.send_line(b"_debug")
    res = ast.literal_eval(f.read_line().decode())
    return f, res

from sock import Sock
for chk in range(10000):
    print("attempt %d" % chk)
    f, res = getcon()

    hash_admin = bytes.fromhex(res["admin"])
    del res["admin"]

    outs = []
    for k in sorted(res):
        outs.append(bytes.fromhex(res[k]))

    cands = []
    recover_iv(0)

    print(len(cands), "iv candidates")
    for key in cands:
        for iv, out in zip(ivs, outs):
            test = harc4(iv, key)
            if bytes(test) != bytes(out):
                break
        else:
            print("Recovered IV!", key)
            test = bytes(a ^ b for a, b in zip(hash_admin, key))
            pw = forgestream(test, key)

            f.read_until(b"> ")
            f.send_line(b"login")
            f.send_line(b"admin")
            f.send_line(pw.hex().encode("ascii"))
            f.shut_wr()
            print(f.read_all())
            quit()
    f.close()

Balsn{f0rG1ng_7He_w0Rld}

import os
import binascii
from Crypto.Cipher import ARC4
db = {}
IV = os.urandom(32)
def harc4(x):
ksz = ARC4.key_size[-1]
csz = ksz - len(IV)
state = IV
for i in range(0, len(x), csz):
key = x[i:i+csz] + state
cipher = ARC4.new(key)
state = cipher.encrypt(state)
return state.hex()
def main():
# Generate the ultimate password
db['admin'] = harc4(os.urandom(42))
for _ in range(10):
cmd = input('> ')
if cmd == 'register' or cmd == 'login':
username = input('Username: ')
password = input('Password: ')
try:
password = harc4(binascii.a2b_hex(password))
except binascii.Error:
print('[!] Nope')
continue
if cmd == 'register':
if username in db:
print('[!] Nope')
else:
db[username] = password
elif cmd == 'login':
if db.get(username, None) != password:
print('[!] Nope')
elif username == 'admin':
with open('../flag.txt') as f:
print('[+] ' + f.read())
else:
print('[+] Welcome %s' % username)
elif cmd == '_debug':
print(db)
else:
print('[!] Unknown command %s, Available commands: register, login' % cmd)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment