[🥇 Gold 1] 함수 125개짜리 4진 트라이를 되감다 — DreamHack Function Network 풀이

file extracted/chal; readelf -SW extracted/chal | grep -E "Name|\.text|\.rodata|\.data|\.bss"

strings -n 5 extracted/chal | grep -nE "Give me|Wrong|flag is|memcmp|strlen"

objdump -d -M intel --start-address=0x7133 --stop-address=0x71b2 extracted/chal | sed -f annot_main.sed

objdump -d -M intel --start-address=0x7207 --stop-address=0x72cb extracted/chal | sed -f annot_loop.sed

char *buf = rbp - 0x90;              // 입력 64바이트 사본
 
for (int i = 0; i <= 0x270f; i++) {  // 10000회
    long key   = *(long *)(0xb020 + i * 24);
    long off_a = *(long *)(0xb028 + i * 24);
    long off_b = *(long *)(0xb030 + i * 24);
    dispatch(key, buf + off_a, buf + off_b);   // 0x1209 — 고정 주소
}
 
if (memcmp((void *)0x459a0, buf, 0x40) == 0)
    printf("Yes, the flag is DH{%s}\n", rbp - 0x50);

objdump -d -M intel --start-address=0x1209 --stop-address=0x127a extracted/chal | sed -f annot_disp.sed

void dispatch(long key, char *p, char *q) {
    switch (key & 3) {
        case 0: f_a(key >> 2, p, q); break;
        case 1: f_b(key >> 2, p, q); break;
        case 2: f_c(key >> 2, p, q); break;
        default: f_d(key >> 2, p, q); break;
    }
}

# verify_graph.py 발췌 — 계층 구조 확인
level, frontier, seen = {0x1209: 0}, [0x1209], {0x1209}
while frontier:
    nxt = []
    for u in frontier:
        for v in children.get(u, []):
            if v not in seen:
                seen.add(v); level[v] = level[u] + 1; nxt.append(v)
            assert level[v] == level[u] + 1, (hex(u), hex(v))
    frontier = nxt

python3 verify_graph.py

objdump -d -M intel --start-address=0x6f4c --stop-address=0x6fd0 extracted/chal | grep -vE "endbr64|push   rbp|mov    rbp,rsp|QWORD PTR \[rbp-0x(18|20|28)\],r|pop    rbp|nop|file format|Disassembly" | sed -f annot_leaf.sed

objdump -d -M intel --start-address=0x6fd0 --stop-address=0x704f extracted/chal | grep -vE "endbr64|push   rbp|mov    rbp,rsp|QWORD PTR \[rbp-0x(18|20|28)\],r|pop    rbp|nop|file format|Disassembly" | sed -f annot_leaf.sed

a = nb                      # 옛 buf[off_a] — 그냥 읽으면 된다
b = {                       # 옛 buf[off_b] — 연산만 뒤집는다
    "add":  (na - a) & 0xff,
    "sub":  (a - na) & 0xff,
    "xor":  na ^ a,
    "swap": na,
}[op]

#!/usr/bin/env python3
"""Function Network - 디스패처 그래프 + 연산 테이블 추출
 
chal 은 stripped PIE 다. 함수 심볼이 없으므로
  1) objdump 출력에서 `endbr64; push rbp` 로 함수 시작을 찾고
  2) 191바이트짜리 디스패처 125개의 call 타겟 4개를 순서대로 뽑아 4진 트라이를 복원하고
  3) .data 의 (key, off_a, off_b) 10000개를 읽어 각 key 를 그래프로 걸어 리프(연산)를 확정한다.
"""
import re, subprocess, json, sys
from pathlib import Path
 
BASE = Path(__file__).resolve().parent
BIN  = BASE / "extracted" / "chal"
 
# --- 1. 디스어셈블 ---------------------------------------------------------
asm = subprocess.run(["objdump", "-d", "-M", "intel", str(BIN)],
                     capture_output=True, text=True, check=True).stdout.split("\n")
 
starts = []
for i, l in enumerate(asm):
    m = re.match(r"^\s+([0-9a-f]+):\s+f3 0f 1e fa\s+endbr64", l)
    if m and i + 1 < len(asm) and "push" in asm[i + 1] and "rbp" in asm[i + 1]:
        starts.append(int(m.group(1), 16))
starts.sort()
 
# 리프 4개(연산)와 main 은 크기로 구분된다 — 디스패처만 정확히 0xbf 바이트
LEAF = {0x6f4c: "add", 0x6f8f: "xor", 0x6fd0: "sub", 0x7017: "swap"}
MAIN = 0x704f
 
# --- 2. 디스패처의 자식 4개 --------------------------------------------------
addr_of = {}
for i, l in enumerate(asm):
    m = re.match(r"^\s+([0-9a-f]+):", l)
    if m:
        addr_of.setdefault(int(m.group(1), 16), i)
 
children = {}
for idx, a in enumerate(starts):
    if a in LEAF or a == MAIN:
        continue
    end = starts[idx + 1]
    tgts = []
    for l in asm[addr_of[a]:addr_of[end]]:
        m = re.search(r"call\s+([0-9a-f]+)", l)
        if m:
            tgts.append(int(m.group(1), 16))
    assert len(tgts) == 4, (hex(a), [hex(t) for t in tgts])
    children[a] = tgts          # [case0, case1, case2, case3(default)]
 
print(f"[+] 디스패처 {len(children)}개 · 리프 {len(LEAF)}개")
 
# --- 3. key -> 연산 --------------------------------------------------------
ROOT = 0x1209
cache = {}
def op_of(key):
    if key in cache:
        return cache[key]
    node, k, hops = ROOT, key, 0
    while node not in LEAF:
        node = children[node][k & 3]
        k >>= 2
        hops += 1
        if hops > 64:
            raise RuntimeError(f"key={key} 순환")
    cache[key] = (LEAF[node], hops)
    return cache[key]
 
# --- 4. .data 의 연산 테이블 ------------------------------------------------
raw = BIN.read_bytes()
# .data: addr 0xb000, off 0xa000
DATA_ADDR, DATA_OFF = 0xB000, 0xA000
def rd(addr, n):
    o = DATA_OFF + (addr - DATA_ADDR)
    return raw[o:o + n]
 
TBL, N = 0xB020, 10000
ops = []
for i in range(N):
    key, oa, ob = [int.from_bytes(rd(TBL + i * 24 + j * 8, 8), "little") for j in range(3)]
    name, hops = op_of(key)
    ops.append((name, oa, ob, key, hops))
 
target = rd(0x459A0, 64)
 
from collections import Counter
print("[+] 연산 분포:", Counter(o[0] for o in ops))
print("[+] 오프셋 범위:", min(min(o[1], o[2]) for o in ops), "~", max(max(o[1], o[2]) for o in ops))
print("[+] 경로 깊이:", Counter(o[4] for o in ops))
print("[+] target[0:16] =", target[:16].hex())
 
json.dump({"ops": [(o[0], o[1], o[2]) for o in ops], "target": target.hex()},
          open(BASE / "network.json", "w"))
print("[+] network.json 저장")

python3 extract.py

#!/usr/bin/env python3
"""연산 테이블 앞부분과 목표 버퍼를 사람이 읽을 수 있게 찍는다."""
import json
from pathlib import Path
 
BASE = Path(__file__).resolve().parent
raw = (BASE / "extracted" / "chal").read_bytes()
DATA_ADDR, DATA_OFF, TBL = 0xB000, 0xA000, 0xB020
 
 
def rd(addr, n):
    o = DATA_OFF + (addr - DATA_ADDR)
    return raw[o:o + n]
 
 
net = json.load(open(BASE / "network.json"))
ops = net["ops"]
keys = [int.from_bytes(rd(TBL + i * 24, 8), "little") for i in range(10000)]
 
print("idx  key(64bit)           base4(하위->상위, 앞 8자리)  op    off_a off_b")
for i in range(8):
    k = keys[i]
    b4 = "".join(str((k >> (2 * j)) & 3) for j in range(8))
    name, oa, ob = ops[i]
    print(f"{i:<4} 0x{k:016x}   {b4}...                     {name:<5} {oa:<5} {ob}")
 
print()
print(f"서로 다른 key: {len(set(keys))}개 / 전체 {len(keys)}개")
print(f"key 최소 0x{min(keys):016x}  최대 0x{max(keys):016x}")
print()
print("목표 버퍼 0x459a0 (64바이트):")
tgt = bytes.fromhex(net["target"])
for r in range(0, 64, 16):
    print(f"  +0x{r:02x}  " + " ".join(f"{c:02x}" for c in tgt[r:r + 16]))

python3 show_table.py

# Function Network — 런타임 검증 (gdb -q -batch -x runtime.gdb --args ./extracted/chal)
#  1) PIE 베이스는 관례로 가정하지 않고 `info files` 의 재배치된 .text 에서 역산한다
#  2) main 의 dispatch 호출 지점에서 0번 엔트리의 key / off_a / off_b 를 실물로 확인
#  3) 그 key 가 실제로 어느 리프로 떨어지는지 리프 4곳에 브레이크포인트를 걸어 잡는다
#  4) memcmp 직전 작업버퍼와 목표버퍼가 실제로 같은지 64바이트 통째로 비교
set pagination off
set confirm off
starti
python
import re, gdb
q = lambda c: gdb.execute(c, to_string=True)
u64 = lambda r: int(gdb.parse_and_eval(r)) & 0xFFFFFFFFFFFFFFFF
byte = lambda p: int(gdb.parse_and_eval("*(unsigned char*)%d" % p))
 
base = int(re.search(r"0x([0-9a-f]+) - 0x[0-9a-f]+ is \.text$",
                     q("info files"), re.M).group(1), 16) - 0x1120
gdb.write("PIE base          = 0x%x   (.text 재배치값에서 역산)\n" % base)
 
LEAF = {0x6f4c: "add", 0x6f8f: "xor", 0x6fd0: "sub", 0x7017: "swap"}
q("break *0x%x" % (base + 0x728d))                 # main 의 dispatch 호출
q("run < input.txt")
 
key, pa, pb = u64("$rdi"), u64("$rsi"), u64("$rdx")
buf = u64("$rbp") - 0x90
gdb.write("work buffer       = 0x%x  (rbp-0x90)\n" % buf)
gdb.write("entry[0] key      = 0x%016x  base4 하위8자리 %s\n"
          % (key, "".join(str((key >> (2 * j)) & 3) for j in range(8))))
gdb.write("entry[0] off_a/b  = %d / %d\n" % (pa - buf, pb - buf))
a, b = byte(pa), byte(pb)
gdb.write("호출 전           : buf[%d]=0x%02x  buf[%d]=0x%02x\n" % (pa - buf, a, pb - buf, b))
 
q("delete")
for off in LEAF:
    q("break *0x%x" % (base + off))
q("continue")
hit = u64("$pc") - base
gdb.write("도달한 리프       = 0x%x -> %s   (extract.py 예측: sub)\n" % (hit, LEAF[hit]))
q("finish")
gdb.write("호출 후           : buf[%d]=0x%02x  buf[%d]=0x%02x   (0x%02x-0x%02x=0x%02x, 옛 a 가 b 자리로)\n"
          % (pa - buf, byte(pa), pb - buf, byte(pb), a, b, (a - b) & 0xFF))
 
q("delete")
q("break *0x%x" % (base + 0x72c2))                 # memcmp 호출 직전
q("continue")
tgt, wrk = u64("$rdi"), u64("$rsi")
inf = gdb.selected_inferior()
tb, wb = bytes(inf.read_memory(tgt, 64)), bytes(inf.read_memory(wrk, 64))
gdb.write("memcmp target[:16]= %s\n" % tb[:16].hex())
gdb.write("memcmp work  [:16]= %s\n" % wb[:16].hex())
gdb.write("64바이트 전체 일치 = %s\n" % (tb == wb))
end

gdb -q -batch -x runtime.gdb --args ./extracted/chal

#!/usr/bin/env python3
"""Function Network (Dreamhack, Gold 1 / reversing) — solver
 
main 은 64바이트 입력을 작업버퍼로 복사한 뒤, .data 의 (key, off_a, off_b) 10000개를
순서대로 dispatch(key, &buf[off_a], &buf[off_b]) 로 흘려보내고 결과를 0x459a0 의
64바이트와 memcmp 한다.
 
key 는 4진 트라이(디스패처 125개)를 32단계 타고 내려가 리프 연산 4개 중 하나로 떨어진다.
리프는 전부 (a,b) -> (f(a,b), a) 꼴이라 **전단사**다. 그래서 목표값에서 역순으로
10000번 되돌리면 입력이 그대로 나온다.
 
  a = buf[off_a], b = buf[off_b] 일 때 순방향은
    add : buf[off_a], buf[off_b] = (a+b)&0xff, a
    sub : buf[off_a], buf[off_b] = (a-b)&0xff, a
    xor : buf[off_a], buf[off_b] = a^b,        a
    swap: buf[off_a], buf[off_b] = b,          a
 
  역방향은 새 b 가 곧 옛 a 이므로
    a = new_b,  b = {add: new_a-a, sub: a-new_a, xor: new_a^a, swap: new_a}
 
network.json 은 extract.py 가 바이너리에서 뽑아 둔 것이다(디스패처 그래프 + 테이블 + 목표값).
"""
import json
from pathlib import Path
 
BASE = Path(__file__).resolve().parent
net = json.load(open(BASE / "network.json"))
ops = [(n, a, b) for n, a, b in net["ops"]]
target = bytearray(bytes.fromhex(net["target"]))
 
 
def forward(buf, ops):
    buf = bytearray(buf)
    for name, oa, ob in ops:
        a, b = buf[oa], buf[ob]
        if   name == "add":  t = (a + b) & 0xFF
        elif name == "sub":  t = (a - b) & 0xFF
        elif name == "xor":  t = a ^ b
        else:                t = b            # swap
        buf[ob] = a
        buf[oa] = t
    return bytes(buf)
 
 
def backward(buf, ops):
    buf = bytearray(buf)
    for name, oa, ob in reversed(ops):
        na, nb = buf[oa], buf[ob]
        a = nb                                 # 옛 buf[off_a]
        if   name == "add":  b = (na - a) & 0xFF
        elif name == "sub":  b = (a - na) & 0xFF
        elif name == "xor":  b = na ^ a
        else:                b = na            # swap
        buf[oa] = a
        buf[ob] = b
    return bytes(buf)
 
 
flag_body = backward(target, ops)
print("recovered :", flag_body)
print("printable :", all(0x20 <= c < 0x7F for c in flag_body))
 
check = forward(flag_body, ops)
print("forward   :", check.hex())
print("target    :", bytes(target).hex())
print("MATCH" if check == bytes(target) else "MISMATCH")
print()
print("FLAG: DH{%s}" % flag_body.decode())

python3 solve.py

#!/usr/bin/env python3
"""복원한 입력을 실제 바이너리에 먹여 flag 가 나오는지 확인한다."""
import subprocess
from pathlib import Path
 
BASE = Path(__file__).resolve().parent
BODY = "b510ce2d7599e75f79b6bf613384dda282bcedea47184155e55d1d22139afaab"
 
r = subprocess.run([str(BASE / "extracted" / "chal")], input=BODY + "\n",
                   capture_output=True, text=True, timeout=60)
print("Input  :", BODY, f"({len(BODY)} chars)")
print("Output :", r.stdout.strip())
print("Verdict:", "OK" if "Yes, the flag is" in r.stdout else "FAIL")

python3 verify.py

DH{b510ce2d7599e75f79b6bf613384dda282bcedea47184155e55d1d22139afaab}

#!/usr/bin/env bash
# Function Network (Dreamhack 1082, Gold 1 / reversing) — 한 방 재현.
#   디스패처 그래프·연산 테이블 추출 → 10000 스텝 역산 → 실제 바이너리로 대조.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null || echo '')
 
chmod +x extracted/chal
python3 extract.py
OUT=$(timeout 300 python3 solve.py 2>&1) || true
echo "$OUT" | tail -8
 
BODY=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1 | sed 's/^DH{//;s/}$//')
REAL=$(printf '%s\n' "$BODY" | ./extracted/chal 2>&1 | grep -aoE 'DH\{[^}]+\}' | head -1)
 
echo
if [ -n "$REAL" ] && { [ -z "$EXPECT" ] || [ "$REAL" = "$EXPECT" ]; }; then
  echo "✅ PASS  $REAL"; exit 0
fi
echo "❌ FAIL (바이너리가 낸 값: '${REAL:-없음}' / 기대: '$EXPECT')"; exit 1

./reproduce.sh