[🥈 Silver 3] 2MB 바이너리에서 코드는 509바이트뿐이었다 — DreamHack Branches and Leaves 풀이

file extracted/main; readelf -W --dyn-syms extracted/main

ls -l extracted/main; readelf -S -W extracted/main | grep -E "\[Nr\]|\.text|\.rodata|\.data|\.bss"

objdump -s -j .rodata extracted/main; strings -a -n 8 extracted/main | grep -aE "use|DH"

s|\(cmp    rax,0x40\)|\1                 <-- 입력은 정확히 64글자|
s|\(lea    r10,\[rip+0x2e14\]\).*|\1        <-- 0x4020  expected[16]|
s|\(lea    rdi,\[rip+0x2e5b\]\).*|\1        <-- 0x4060  tree[524288]|
s|\(shl    edx,0x4\)|\1                   <-- 니블을 위에서부터 쌓는다|
s|\(cmp    sil,0x9\)|\1                   <-- '0'-'9' 인가|
s|\(cmp    sil,0x5\)|\1                   <-- 'a'-'f' 인가 (대문자 불가)|
s|\(mov    ecx,0x10\)|\1                  <-- 트리를 16번 내려간다|
s|\(sar    edx,1\)|\1                     <-- 다음 비트로 (LSB 부터)|
s|\(and    esi,0x1\)|\1                   <-- 이번 비트|
s|\(lea    rax,\[rsi+rax\*2\]\)|\1          <-- 자식 위치 = 2*node + bit|
s|\(movsxd rax,DWORD PTR \[rdi+rax\*4\]\)|\1  <-- node = tree[...]|
s|\(cmp    eax,0xffffffff\)|\1            <-- -1 은 막다른 가지|
s|\(cmp    eax,0x3ffff\)|\1               <-- 내부노드 상한 262143|
s|\(cmp    eax,DWORD PTR \[r10+rdx\*4\]\)|\1  <-- 16스텝 뒤 값 == expected[i] ?|
s|\(cmp    r9d,0x40\)|\1                  <-- 16덩어리를 다 봤나|

objdump -d --start-address=0x11e0 --stop-address=0x1240 -M intel extracted/main | sed -f annot.sed

unsigned edx = 0;
for (char *c = chunk; c < chunk + 4; c++) {
    edx <<= 4;
    if      ((unsigned char)(*c - '0') <= 9) edx += *c - '0';
    else if ((unsigned char)(*c - 'a') <= 5) edx += *c - 'a' + 10;
    else exit(1);
}

objdump -d --start-address=0x1240 --stop-address=0x129d -M intel extracted/main | sed -f annot.sed

mov    esi,edx              ; esi = 지금 값
sar    edx,1                ; 값은 오른쪽으로 한 칸
and    esi,0x1              ; 방금 밀려난 자리의 비트
lea    rax,[rsi+rax*2]      ; 색인 = 2 * node + bit
movsxd rax,[rdi+rax*4]      ; node = tree[색인]

for (int i = 0; i < 16; i++) {
    unsigned v = parse4(input + i * 4);
    int node = 0;
    for (int s = 0; s < 16; s++) {
        if (s && (node == -1 || node > 0x3ffff)) exit(1);
        node = tree[2 * node + (v & 1)];
        v >>= 1;
    }
    if (node != expected[i]) exit(1);
}

#!/usr/bin/env python3
"""main 의 .data 에서 두 표를 꺼내 본다: expected[16] 과 tree[524288] 의 앞머리."""
import struct
from pathlib import Path
 
blob = (Path(__file__).with_name("extracted") / "main").read_bytes()
off = lambda va: va - 0x4000 + 0x3000          # .data vaddr 0x4000 -> file 0x3000
 
expected = struct.unpack("<16i", blob[off(0x4020):off(0x4020) + 64])
print("expected[16] @ .data+0x20")
for i in range(0, 16, 4):
    print("  [%2d..%2d]  %s" % (i, i + 3, "  ".join("0x%08x" % (x & 0xFFFFFFFF) for x in expected[i:i + 4])))
 
head = struct.unpack("<32i", blob[off(0x4060):off(0x4060) + 128])
print("\ntree[0..31] @ .data+0x60   (2*node+bit 로 색인, -1 은 빈 슬롯)")
for i in range(0, 32, 8):
    print("  [%2d..%2d]  %s" % (i, i + 7, " ".join("%9d" % x for x in head[i:i + 8])))
 
print("\n루트의 두 자식 = tree[0]=%d, tree[1]=%d" % (head[0], head[1]))
print("파일 전체에서 0xff 바이트 비율 = %.1f%%  (빈 슬롯 -1 이 그만큼 많다)"
      % (100 * blob.count(0xFF) / len(blob)))

python3 dump_tables.py

#!/usr/bin/env python3
"""Branches and Leaves — .data 에 박힌 표가 정말 '트리'인지 세어 본다."""
import struct
from collections import Counter
from pathlib import Path
 
BIN = Path(__file__).with_name("extracted") / "main"
DATA_VADDR, DATA_OFF = 0x4000, 0x3000
TREE_VA, TREE_N = 0x4060, (0x204060 - 0x4060) // 4
NODE_MAX = 0x3FFFF
 
blob = BIN.read_bytes()
o = TREE_VA - DATA_VADDR + DATA_OFF
tree = struct.unpack("<%di" % TREE_N, blob[o:o + TREE_N * 4])
 
print("[table] 엔트리 %d개 = %.1f MB" % (TREE_N, TREE_N * 4 / 1048576))
print("[table] 값 범위 min=%d max=%d" % (min(tree), max(tree)))
print("[table] 음수 엔트리 %d개, 그중 -1 이 %d개"
      % (sum(1 for x in tree if x < 0), sum(1 for x in tree if x == -1)))
print("[table] 내부노드로 쓸 수 있는 값(0..0x3ffff) %d개" % sum(1 for x in tree if 0 <= x <= NODE_MAX))
 
# 루트 0 에서 실제로 닿는 노드만 깊이별로 센다
level, reach, leaves = {0}, set(), []
for depth in range(16):
    nxt = set()
    for n in level:
        reach.add(n)
        for bit in (0, 1):
            child = tree[2 * n + bit]
            if depth == 15:
                leaves.append(child)
            else:
                nxt.add(child)
    print("[walk ] depth %2d: 노드 %6d개 -> 자식 %6d개" % (depth, len(level), len(nxt)))
    level = nxt
 
used = len(reach) * 2
print("[reach] 실제로 읽히는 내부노드 %d개 (엔트리 %d개)" % (len(reach), used))
print("[reach] 한 번도 안 읽히는 엔트리 %d개 = %.1f%% 가 미끼" % (TREE_N - used, 100 * (TREE_N - used) / TREE_N))
print("[reach] 쓰인 노드 인덱스 min=%d max=%d (0x3ffff 까지 흩어놓았다)" % (min(reach), max(reach)))
print("[leaf ] 리프 %d개 중 서로 다른 값 %d개" % (len(leaves), len(set(leaves))))
print("[leaf ] 리프 최소 0x%08x / 최대 0x%08x — 전부 0x3ffff 초과라 경계검사에 걸린다"
      % (min(leaves) & 0xFFFFFFFF, max(leaves) & 0xFFFFFFFF))
dup = [v for v, c in Counter(leaves).items() if c > 1]
print("[leaf ] 중복 리프 %d개 -> 전단사이므로 각 기대값의 역상은 유일하다" % len(dup))

python3 analyze_tree.py

#!/usr/bin/env python3
"""Branches and Leaves (DreamHack, Silver 3, reversing) — solver.
 
check() at 0x11e0 splits the 64-char argv[1] into 16 chunks of 4 hex digits,
turns each chunk into a 16-bit integer v, then walks an array-encoded binary
tree stored in .data: node = tree[2*node + bit], consuming the bits of v from
LSB to MSB, exactly 16 times.  The node reached after the 16th step must equal
expected[chunk] (16 int32 at .data+0x20).
 
Since every chunk is independent and only 16 bits wide, we replay all 65536
paths forward and index them by the leaf they reach.
"""
import struct
import sys
from pathlib import Path
 
BIN = Path(__file__).with_name("extracted") / "main"
 
DATA_VADDR = 0x4000     # .data virtual address
DATA_OFF = 0x3000       # .data file offset
EXPECT_VA = 0x4020      # int32 expected[16]
TREE_VA = 0x4060        # int32 tree[524288]
TREE_N = (0x204060 - 0x4060) // 4
DEPTH = 16              # bits consumed per chunk == loop counter in ecx
NODE_MAX = 0x3FFFF      # `cmp eax,0x3ffff; jg fail` bound on internal nodes
 
 
def load():
    blob = BIN.read_bytes()
    off = lambda va: va - DATA_VADDR + DATA_OFF
    expected = struct.unpack("<16i", blob[off(EXPECT_VA):off(EXPECT_VA) + 64])
    tree = struct.unpack("<%di" % TREE_N, blob[off(TREE_VA):off(TREE_VA) + TREE_N * 4])
    return expected, tree
 
 
def walk(tree, v):
    """Replay the 0x124c loop: 16 x  node = tree[2*node + (v & 1)], v >>= 1."""
    node = 0
    for step in range(DEPTH):
        if step and not (-1 < node <= NODE_MAX):   # bounds check at 0x1240
            return None
        node = tree[2 * node + (v & 1)]
        v >>= 1
    return node
 
 
def main():
    expected, tree = load()
 
    leaves = {}
    for v in range(1 << DEPTH):
        leaf = walk(tree, v)
        if leaf is None:
            continue
        leaves.setdefault(leaf, []).append(v)
 
    print("[*] tree entries      : %d" % TREE_N)
    print("[*] distinct leaves   : %d reached out of 65536 paths" % len(leaves))
 
    chunks = []
    for i, want in enumerate(expected):
        cands = leaves.get(want, [])
        print("[%2d] expected=0x%08x  candidates=%d  ->  %s"
              % (i, want & 0xFFFFFFFF, len(cands),
                 " ".join("%04x" % c for c in cands) or "NONE"))
        if len(cands) != 1:
            sys.exit("chunk %d is not uniquely determined" % i)
        chunks.append("%04x" % cands[0])
 
    key = "".join(chunks)
    print("[+] input : %s" % key)
    print("[+] flag  : DH{%s}" % key)
 
 
if __name__ == "__main__":
    main()

python3 solve.py

set pagination off
set confirm off
starti
python
import gdb
base = None
for line in gdb.execute("info proc mappings", to_string=True).splitlines():
    if line.rstrip().endswith("/main"):
        base = int(line.split()[0], 16)
        break
gdb.execute("set $base = %d" % base)
print("[gdb] PIE base = 0x%x  (info proc mappings 로 실측)" % base)
end
break *($base + 0x1269)
commands
silent
printf "chunk %2d: 16스텝 뒤 node=0x%08x   expected[%d]=0x%08x   %s\n", $r9d/4, $eax, $r9d/4, *(int*)($r10 + ($r9d>>2)*4), ($eax == *(int*)($r10 + ($r9d>>2)*4)) ? "일치" : "불일치"
continue
end
continue

gdb -q -batch -x cmds.gdb --args ./extracted/main d8f794325872bab95cfaa117545c6c0b77059a74f4dd31d8c2bf130a59745d77

#!/usr/bin/env python3
"""solve.py 가 뽑은 입력을 문제 바이너리에 그대로 넣어 본다."""
import subprocess
from pathlib import Path
 
BIN = Path(__file__).with_name("extracted") / "main"
KEY = "d8f794325872bab95cfaa117545c6c0b77059a74f4dd31d8c2bf130a59745d77"
 
for label, arg in (("정답", KEY),
                   ("한 글자 바꿈", KEY[:-1] + ("0" if KEY[-1] != "0" else "1")),
                   ("대문자로", KEY.upper()),
                   ("63글자", KEY[:-1])):
    r = subprocess.run([str(BIN), arg], capture_output=True, text=True)
    print("%-12s exit=%d  stdout=%s" % (label, r.returncode, r.stdout.strip() or "(없음)"))

python3 verify.py

#!/usr/bin/env bash
# Branches and Leaves (DreamHack Silver 3, reversing) — 한 방 재현.
# 배포 바이너리의 .data 에서 트리를 읽어 입력을 복원하고, 그 입력을 바이너리에 다시 먹여 flag 를 받는다.
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/main
KEY=$(timeout 300 python3 solve.py | sed -n 's/^\[+\] input : //p')
if [ -z "$KEY" ]; then
  echo "❌ FAIL (solve.py 가 입력을 못 뽑았다)"; exit 1
fi
echo "복원한 입력: $KEY"
 
OUT=$(./extracted/main "$KEY" || true)
echo "$OUT"
FLAG=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
 
if [ -n "$FLAG" ] && { [ -z "$EXPECT" ] || [ "$FLAG" = "$EXPECT" ]; }; then
  echo; echo "✅ PASS  $FLAG"; exit 0
fi
echo; echo "❌ FAIL (얻은 값: '${FLAG:-없음}' / 기대: '$EXPECT')"; exit 1

./reproduce.sh

DH{d8f794325872bab95cfaa117545c6c0b77059a74f4dd31d8c2bf130a59745d77}