[🥇 Gold 3] 공유 라이브러리 1,257개로 만든 오토마타 — DreamHack .so what? 풀이

file extracted/main; ls extracted/lib | wc -l; find extracted/lib -name "*.so" -printf "%s\n" | sort -n | uniq -c

nm -D extracted/main | grep " U "; strings -a extracted/main | grep -E "lib/|Flag|input|Wrong"

# annot_main.sed — 주소로 줄을 지정해 주석을 얹는다
s|^    1368:.*|&      <-- setvbuf 3종|
s|^    1394:.*|&                 <-- 0x41 = 65바이트 읽는다|
s|^    13a1:.*|&        <-- read(0, buf, 0x41)|
s|^    13a6:.*|&        <-- buf[64] = 0|
s|^    13b1:.*|&        <-- verify(buf) : 64글자가 0-9a-f 인가|
s|^    13b6:.*|&           <-- 0x101 = RTLD_LAZY + RTLD_GLOBAL|
s|^    13c5:.*|&       <-- dlopen("lib/start.so")|
s|^    13ee:.*|&      <-- 심볼 이름 만들기 : 'f'|
s|^    13f2:.*|&      <-- '_'|
s|^    13f6:.*|&    <-- buf[0]  → "f_<첫 글자>"|
s|^    140f:.*|&        <-- dlsym(handle, "f_X")|
s|^    143c:.*|&                 <-- 인자는 buf+1 (한 글자 소비)|
s|^    1447:.*|&                <-- 찾은 함수를 호출|
s|^    144b:.*|&    <-- 0 이면 Wrong!|
s|^    1463:.*|&       <-- printf("Flag is DH{%s}", buf)|

objdump -d -M intel --no-show-raw-insn --start-address=0x1304 --stop-address=0x13ee extracted/main | sed -f annot_main.sed

objdump -d -M intel --no-show-raw-insn --start-address=0x13ee --stop-address=0x1494 extracted/main | sed -f annot_main.sed

int main(void)
{
    char buf[0x41] = {0};
    initialize();
    puts("Please give me your input!");
    printf("> ");
    read(0, buf, 0x41);
    buf[0x40] = 0;
 
    verify(buf);                                   // 64글자가 0-9a-f 인지
 
    void *h = dlopen("lib/start.so", RTLD_LAZY | RTLD_GLOBAL);
    if (!h) { puts("Failed to load a library."); exit(1); }
 
    char name[4] = { 'f', '_', buf[0], 0 };         // ← 심볼 이름을 입력으로 만든다
    int (*fn)(char *) = dlsym(h, name);
    if (!fn) { puts("Failed to load a function."); exit(1); }
 
    if (fn(buf + 1))                                // ← 한 글자 소비하고 넘김
        printf("Flag is DH{%s}\n", buf);
    else
        puts("Wrong!");
}

# annot_verify.sed
s|^    1299:.*|&                 <-- c <= '/' 이면 hex 문자 검사로|
s|^    12ad:.*|&                 <-- c <= '9' 이면 통과 (0-9)|
s|^    12c1:.*|&                 <-- c <= '`' 이면 실패|
s|^    12d5:.*|&                 <-- c <= 'f' 이면 통과 (a-f)|
s|^    12e3:.*|&        <-- 아니면 "Wrong input." 후 exit|
s|^    12fa:.*|&    <-- i <= 0x3f : 정확히 64글자|

objdump -d -M intel --no-show-raw-insn --start-address=0x1270 --stop-address=0x1304 extracted/main | sed -f annot_verify.sed

nm -D --defined-only extracted/lib/start.so; echo ---; strings -a extracted/lib/start.so | grep -c "^lib/"

# annot_fd.sed
s|^    11b8:.*|&           <-- 0x101 = RTLD_LAZY + RTLD_GLOBAL|
s|^    11c7:.*|&       <-- dlopen("lib/<이 글자에 정해진 다음>.so")|
s|^    11f0:.*|&      <-- 'f'|
s|^    11f4:.*|&      <-- '_'|
s|^    11fc:.*|&      <-- p[0] = 다음 글자|
s|^    1214:.*|&       <-- dlsym(handle, "f_<다음 글자>")|
s|^    1241:.*|&            <-- 인자는 p+1|
s|^    124c:.*|&                 <-- 재귀 호출. 반환값을 그대로 넘긴다|

objdump -d -M intel --no-show-raw-insn extracted/lib/start.so | sed -n "/<f_0>:/,/<f_1>:/p" | sed -f annot_fd.sed

int f_0(char *p)
{
    void *h = dlopen("lib/6fb3f5f2b4.so", RTLD_LAZY | RTLD_GLOBAL);  // ← 이 글자에 고정된 다음 파일
    char name[4] = { 'f', '_', p[0], 0 };
    int (*fn)(char *) = dlsym(h, name);
    return fn(p + 1);                                                // 반환값을 그대로 올려보낸다
}

#!/usr/bin/env python3
"""dlopen 을 하지 않는 .so(= 종료 상태)를 찾아, 16개 함수가 뭘 돌려주는지 본다."""
import pathlib
import re
import subprocess
from concurrent.futures import ProcessPoolExecutor
 
HERE = pathlib.Path(__file__).resolve().parent
LIB = HERE / "extracted" / "lib"
DIGITS = "0123456789abcdef"
FUNC_RE = re.compile(r"^[0-9a-f]+ <f_([0-9a-f])>:$")
RET_RE = re.compile(r"mov\s+eax,0x([0-9a-f]+)\b")
 
 
def scan(path_str: str):
    path = pathlib.Path(path_str)
    out = subprocess.run(["objdump", "-d", "-M", "intel", "--no-show-raw-insn", str(path)],
                         capture_output=True, text=True, check=True).stdout
    if "<dlopen@plt>" in out:
        return None                      # 전이 상태
    rets, cur = {}, None
    for line in out.splitlines():
        m = FUNC_RE.match(line.strip())
        if m:
            cur = m.group(1)
            continue
        if cur is None:
            continue
        m = RET_RE.search(line)
        if m and cur not in rets:
            rets[cur] = int(m.group(1), 16)
    return path.name, rets
 
 
def main():
    libs = sorted(str(p) for p in LIB.glob("*.so"))
    with ProcessPoolExecutor() as ex:
        found = [r for r in ex.map(scan, libs, chunksize=16) if r]
 
    print(f"[*] 전체 {len(libs)}개 중 dlopen 없는 .so = {len(found)}개 (종료 상태)")
    total_one = 0
    for name, rets in sorted(found):
        ones = [d for d in DIGITS if rets.get(d) == 1]
        total_one += len(ones)
        if ones:
            print(f"    ★ {name}  →  f_{','.join(ones)} 가 1 을 돌려준다")
    print(f"[+] 종료 상태의 함수 {len(found) * 16}개 중 1 을 돌려주는 것 : {total_one}개")
    print("    나머지는 전부 0 — 즉 성공으로 가는 길은 하나뿐이다")
 
 
if __name__ == "__main__":
    main()

python3 scan_terminals.py

#!/usr/bin/env python3
"""1257개 .so 에서 전이표를 뽑아 DFA 로 만든다."""
import json
import pathlib
import re
import subprocess
from concurrent.futures import ProcessPoolExecutor
 
from elftools.elf.elffile import ELFFile
 
HERE = pathlib.Path(__file__).resolve().parent
LIB = HERE / "extracted" / "lib"
 
FUNC_RE = re.compile(r"^[0-9a-f]+ <f_([0-9a-f])>:$")
LEA_RE = re.compile(r"lea\s+rax,\[rip\+0x[0-9a-f]+\]\s+#\s+([0-9a-f]+)")
RET0_RE = re.compile(r"mov\s+eax,0x([01])\b")
 
 
def read_cstring(elf_path: pathlib.Path, vaddr: int) -> str:
    """가상주소 vaddr 에 있는 NUL 종료 문자열을 파일에서 읽는다."""
    with open(elf_path, "rb") as fh:
        elf = ELFFile(fh)
        for seg in elf.iter_segments():
            if seg["p_type"] != "PT_LOAD":
                continue
            lo, hi = seg["p_vaddr"], seg["p_vaddr"] + seg["p_filesz"]
            if lo <= vaddr < hi:
                fh.seek(seg["p_offset"] + (vaddr - lo))
                raw = fh.read(256)
                return raw.split(b"\x00", 1)[0].decode()
    raise ValueError(f"{elf_path.name}: vaddr {vaddr:#x} 를 못 찾음")
 
 
def parse_one(path_str: str):
    path = pathlib.Path(path_str)
    out = subprocess.run(
        ["objdump", "-d", "-M", "intel", "--no-show-raw-insn", str(path)],
        capture_output=True, text=True, check=True).stdout
 
    edges, rets, cur, pending_lea = {}, {}, None, None
    for line in out.splitlines():
        line = line.strip()
        m = FUNC_RE.match(line)
        if m:
            cur, pending_lea = m.group(1), None
            continue
        if cur is None:
            continue
        m = LEA_RE.search(line)
        if m:
            pending_lea = int(m.group(1), 16)
            continue
        if "<dlopen@plt>" in line and pending_lea is not None:
            s = read_cstring(path, pending_lea)
            if s.startswith("lib/"):
                edges[cur] = s[len("lib/"):]
            pending_lea = None
            continue
        m = RET0_RE.search(line)
        if m and cur not in edges:
            rets[cur] = int(m.group(1))
    return path.name, edges, rets
 
 
def main():
    libs = sorted(str(p) for p in LIB.glob("*.so"))
    print(f"[*] .so {len(libs)}개 파싱")
    dfa, terminal = {}, {}
    with ProcessPoolExecutor() as ex:
        for name, edges, rets in ex.map(parse_one, libs, chunksize=16):
            if edges:
                dfa[name] = edges
            else:
                terminal[name] = rets
 
    (HERE / "dfa.json").write_text(json.dumps(dfa, indent=0, sort_keys=True))
    (HERE / "terminal.json").write_text(json.dumps(terminal, indent=0, sort_keys=True))
 
    print(f"[+] 전이 상태 {len(dfa)}개 / 종료 상태 {len(terminal)}개")
    bad = [k for k, v in dfa.items() if len(v) != 16]
    print(f"[*] 전이 16개가 아닌 상태: {len(bad)}  {bad[:3]}")
    accept = {k: [d for d, v in r.items() if v == 1] for k, r in terminal.items()}
    accept = {k: v for k, v in accept.items() if v}
    print(f"[+] 1 을 돌려주는 종료 상태: {accept}")
 
 
if __name__ == "__main__":
    main()

python3 extract_dfa.py

# path_stats.py — 수락 상태까지 가는 경로가 길이별로 몇 개인지 센다
cnt, per_len = {goal: 1}, {}
for k in range(1, MAXLEN + 1):
    nxt = {}
    for src, e in dfa.items():
        t = sum(cnt.get(e[d], 0) for d in DIGITS)
        if t:
            nxt[src] = t
    cnt = nxt
    if cnt.get(START):
        per_len[k] = cnt[START]

python3 path_stats.py

#!/usr/bin/env python3
""".so what? (DreamHack, Gold 3 / reversing) — solver
 
구조:
  main 이 64자 hex 를 받아 verify() 로 0-9a-f 인지 확인한 뒤
    dlopen("lib/start.so") → dlsym("f_" + s[0]) → 그 함수를 s+1 로 호출
  한다. 각 .so 의 f_d 는 다시
    dlopen("lib/<정해진 다음>.so") → dlsym("f_" + p[0]) → f(p+1)
  이므로 **.so = 상태, f_d = 라벨 d 인 전이**를 갖는 결정적 오토마타다.
 
  종료 상태(dlopen 없이 상수만 돌려주는 .so) 20개 중
  `219f2e3164.so` 의 `f_8` 만 1 을 돌려준다. 나머지는 전부 0.
 
  따라서 정답은
    start.so 에서 출발해 63번 전이해 219f2e3164.so 에 닿고
    마지막 64번째 글자가 8
  인 64자 hex 문자열이다.  flag = DH{그 문자열}
 
  ★ 주의: 전이 그래프에 사이클이 있어 "최단 경로"가 아니라
     "길이가 정확히 63" 인 경로를 찾아야 한다. 길이별 도달 가능 집합을
     뒤에서부터 계산(역방향 BFS)해 그 안에서만 앞으로 걸어가면 된다.
"""
import argparse
import json
import pathlib
import sys
 
HERE = pathlib.Path(__file__).resolve().parent
DIGITS = "0123456789abcdef"
START = "start.so"
LENGTH = 64          # verify() 가 검사하는 글자 수
 
 
def load():
    dfa = json.loads((HERE / "dfa.json").read_text())
    terminal = json.loads((HERE / "terminal.json").read_text())
    return dfa, terminal
 
 
def accepting(terminal: dict) -> tuple[str, str]:
    """1 을 돌려주는 (종료상태, 마지막글자) 를 찾는다."""
    hits = [(lib, d) for lib, rets in terminal.items()
            for d, v in rets.items() if v == 1]
    if len(hits) != 1:
        sys.exit(f"수락 상태가 {len(hits)}개다: {hits}")
    return hits[0]
 
 
def solve(dfa: dict, goal: str, steps: int) -> str | None:
    """start 에서 goal 까지 정확히 steps 번 전이하는 경로의 라벨 문자열."""
    # reach[k] = k 번 더 전이하면 goal 에 닿을 수 있는 상태 집합
    reach = [set() for _ in range(steps + 1)]
    reach[0] = {goal}
    back: dict[str, list[str]] = {}
    for src, edges in dfa.items():
        for d in DIGITS:
            back.setdefault(edges[d], []).append(src)
    for k in range(1, steps + 1):
        nxt = set()
        for st in reach[k - 1]:
            nxt.update(back.get(st, ()))
        reach[k] = nxt
    if START not in reach[steps]:
        return None
 
    out, cur = [], START
    for k in range(steps, 0, -1):
        for d in DIGITS:                      # 사전순으로 첫 번째를 고른다
            if dfa[cur][d] in reach[k - 1]:
                out.append(d)
                cur = dfa[cur][d]
                break
        else:
            sys.exit("경로 재구성 실패")
    return "".join(out)
 
 
def count_paths(dfa: dict, goal: str, steps: int) -> int:
    """길이가 정확히 steps 인 경로가 몇 개인지 센다 (유일성 확인)."""
    cnt = {goal: 1}
    for _ in range(steps):
        nxt: dict[str, int] = {}
        for src, edges in dfa.items():
            t = sum(cnt.get(edges[d], 0) for d in DIGITS)
            if t:
                nxt[src] = t
        cnt = nxt
    return cnt.get(START, 0)
 
 
def main() -> int:
    ap = argparse.ArgumentParser()
    ap.add_argument("--count", action="store_true", help="경로 개수도 센다")
    a = ap.parse_args()
 
    dfa, terminal = load()
    goal, last = accepting(terminal)
    print(f"[*] 상태 {len(dfa)}개(전이) + {len(terminal)}개(종료)")
    print(f"[+] 수락 상태 : {goal}  의  f_{last}")
 
    prefix = solve(dfa, goal, LENGTH - 1)
    if prefix is None:
        print("[-] 길이가 맞는 경로가 없다")
        return 1
 
    flag_body = prefix + last
    print(f"[+] 경로 길이 : {len(flag_body)}자")
    if a.count:
        n = count_paths(dfa, goal, LENGTH - 1)
        print(f"[*] 길이 {LENGTH - 1} 경로 수 : {n}개")
    print(f"[+] FLAG: DH{{{flag_body}}}")
    return 0
 
 
if __name__ == "__main__":
    sys.exit(main())

python3 solve.py --count

#!/usr/bin/env python3
"""정적으로 뽑은 전이표가 실제 실행과 맞는지 대조한다."""
import json
import pathlib
import re
import subprocess
import sys
 
HERE = pathlib.Path(__file__).resolve().parent
ANSWER = "20654ccdb7c43bd1ab398283f9895ac285e8c419c4c157db2f3f50de92599bd8"
OPEN_RE = re.compile(r'"lib/([0-9a-z]+\.so)"')
 
 
def traced_order() -> list[str]:
    p = subprocess.run(
        ["strace", "-f", "-e", "trace=openat", "./main"],
        input=ANSWER + "\n", cwd=HERE / "extracted",
        capture_output=True, text=True, timeout=120)
    return OPEN_RE.findall(p.stderr)
 
 
def predicted_order() -> list[str]:
    dfa = json.loads((HERE / "dfa.json").read_text())
    order, cur = ["start.so"], "start.so"
    for d in ANSWER[:-1]:          # 마지막 글자는 종료 상태의 함수를 고를 뿐 dlopen 을 안 한다
        cur = dfa[cur][d]
        order.append(cur)
    return order
 
 
def main() -> int:
    got, want = traced_order(), predicted_order()
    print(f"[*] 입력      : {ANSWER[:16]}... (64자)")
    print(f"[*] strace 가 연 .so : {len(got)}개")
    print(f"[*] 전이표 예측      : {len(want)}개")
    print()
    for i in (0, 1, 2, 31, 61, 62, 63):
        if i < min(len(got), len(want)):
            mark = "일치" if got[i] == want[i] else "★불일치"
            print(f"    [{i:2d}] 실행={got[i]:<16} 예측={want[i]:<16} {mark}")
    print()
    if got == want:
        print("[+] 64개가 한 칸도 어긋나지 않는다 — 정적 전이표가 런타임과 같다")
        return 0
    bad = next(i for i, (a, b) in enumerate(zip(got, want)) if a != b)
    print(f"[-] {bad}번째에서 갈린다: 실행={got[bad]} / 예측={want[bad]}")
    return 1
 
 
if __name__ == "__main__":
    sys.exit(main())

python3 trace_check.py

#!/usr/bin/env python3
"""찾은 문자열을 실제 main 에 먹여 Flag is DH{...} 가 나오는지 확인한다."""
import subprocess
 
ANSWER = "20654ccdb7c43bd1ab398283f9895ac285e8c419c4c157db2f3f50de92599bd8"
CWD = "extracted"
 
 
def run(s: str) -> str:
    p = subprocess.run(["./main"], input=s + "\n", cwd=CWD,
                       capture_output=True, text=True, timeout=30)
    return p.stdout.strip().splitlines()[-1] if p.stdout.strip() else "(출력 없음)"
 
 
cases = [
    ("정답", ANSWER),
    ("마지막 글자만 바꿈", ANSWER[:-1] + "9"),
    ("첫 글자만 바꿈", "3" + ANSWER[1:]),
    ("가운데 한 글자 바꿈", ANSWER[:32] + ("0" if ANSWER[32] != "0" else "1") + ANSWER[33:]),
]
 
for label, s in cases:
    print(f"{label:20s} len={len(s):3d}  →  {run(s)}")

python3 verify.py

DH{20654ccdb7c43bd1ab398283f9895ac285e8c419c4c157db2f3f50de92599bd8}

./reproduce.sh