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.
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 boxWhen 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)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}