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

2026-08-07·1분 읽기·

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

main 은 64자 hex 를 받아 dlopen 과 dlsym 만으로 검사한다. .so 하나가 상태이고 f_d 가 라벨 d 인 전이라, 파일 1,257개가 통째로 결정적 오토마타다. 전이표를 objdump 로 뽑아 길이 63 경로를 찾으면 간선 19,792개 중 성공 경로가 정확히 하나 나온다.

문제: DreamHack — .so what? 분류: reversing 난이도: 🥇 Gold 3 FLAG: DH{20654ccdb7c43bd1ab398283f9895ac285e8c419c4c157db2f3f50de92599bd8}

문제 설명은 한 줄이다.

... .so... wait, what???

압축을 풀면 왜 저렇게 썼는지 바로 알게 된다.

file extracted/main; ls extracted/lib | wc -l; find extracted/lib -name "*.so" -printf "%s\n" | sort -n | uniq -c
file 과 크기 분포 확인 — main 은 PIE 실행 파일이고 lib 아래 so 파일이 1257개이며 크기가 15560이 20개, 16192가 1개, 16200이 1236개로 세 종류뿐이다
file 과 크기 분포 확인 — main 은 PIE 실행 파일이고 lib 아래 so 파일이 1257개이며 크기가 15560이 20개, 16192가 1개, 16200이 1236개로 세 종류뿐이다

.so 파일이 1,257개다.


문제 개요

항목내용
문제명.so what? (id 1347)
난이도🥇 Gold 3
분류reversing
제공 파일main (PIE, not stripped) + lib/*.so 1,257개 (20MB)
임포트read · printf · puts · dlopen · dlsym · exit
핵심.so = 상태, f_d = 라벨 d 인 전이 → 1,257상태 결정적 오토마타
답64자 hex, 간선 19,792개 중 성공 경로 1개

크기가 세 종류뿐이라는 게 첫 단서다. 16,200바이트가 1,236개, 15,560바이트가 20개, 그리고 16,192바이트가 하나. 소수파를 먼저 보면 된다.

풀이 흐름은 이렇게 흘러갔다. main 이 dlopen/dlsym 만 쓴다는 걸 보고 라이브러리를 타고 가는 구조라고 짐작했다. .so 하나를 열어 보니 함수가 f_0~f_f 열여섯 개였고, 각각 다음 라이브러리를 여는 것까지 확인하면서 오토마타라는 게 확정됐다.

거기서부터는 리버싱이 아니라 그래프 문제다. 전이표를 뽑고 경로를 찾으면 끝난다.



🧩 배경 — dlopen 과 dlsym

두 함수만 알면 이 문제의 골격이 보인다.

dlopen(경로, 플래그) 는 공유 라이브러리를 실행 중에 메모리로 올린다. 컴파일할 때 링크해 두는 게 아니라, 프로그램이 도는 도중에 파일 이름을 정해서 부를 수 있다. 플러그인 구조가 대표적인 용도다.

dlsym(핸들, 이름) 은 그렇게 올린 라이브러리에서 이름으로 심볼을 찾아 주소를 돌려준다. 이름이 문자열이니, 그 문자열을 실행 중에 조립할 수 있다.

둘을 합치면 "어떤 파일을 열지"도 "어떤 함수를 부를지"도 런타임에 정해진다. 정적 분석기가 호출 그래프를 그릴 수 없다는 뜻이기도 하다.

이 문제는 그 성질을 그대로 무기로 쓴다. 파일 이름과 심볼 이름을 입력 글자로 결정하게 만들어, 코드가 아니라 파일 배치 자체에 정답을 숨겨 뒀다.

무엇이 들어 있나

nm -D extracted/main | grep " U "; strings -a extracted/main | grep -E "lib/|Flag|input|Wrong"
nm 으로 본 main 의 임포트와 주요 문자열 — dlopen 과 dlsym 이 들어 있고 lib 슬래시 start 점 so 경로와 Flag is DH 서식 문자열, 두 종류의 실패 메시지가 보인다
nm 으로 본 main 의 임포트와 주요 문자열 — dlopen 과 dlsym 이 들어 있고 lib 슬래시 start 점 so 경로와 Flag is DH 서식 문자열, 두 종류의 실패 메시지가 보인다

임포트에 dlopen·dlsym, 문자열에 lib/start.so 와 Flag is DH{%s}. %s 로 찍는다는 건 우리 입력이 그대로 플래그라는 뜻이다.


🔬 main 읽기

입력을 받는 곳

# 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 로 뽑은 main 앞부분 — read 로 0x41 바이트를 받고 buf 64번째를 0 으로 만든 뒤 verify 를 부르고, 통과하면 lib 슬래시 start 점 so 를 dlopen 한다
objdump 로 뽑은 main 앞부분 — read 로 0x41 바이트를 받고 buf 64번째를 0 으로 만든 뒤 verify 를 부르고, 통과하면 lib 슬래시 start 점 so 를 dlopen 한다

read(0, buf, 0x41) 로 65바이트를 받고 buf[64] = 0. 그리고 verify(buf) 로 검사한 뒤 dlopen("lib/start.so", 0x101).

0x101 은 RTLD_LAZY | RTLD_GLOBAL 이다. RTLD_GLOBAL 이 붙어 있어 나중에 열리는 라이브러리들이 서로의 심볼을 볼 수 있다.

심볼 이름을 만들어 부르는 곳

objdump -d -M intel --no-show-raw-insn --start-address=0x13ee --stop-address=0x1494 extracted/main | sed -f annot_main.sed
objdump 로 뽑은 main 뒷부분 — 스택에 f 와 밑줄과 입력 첫 글자를 넣어 f_X 라는 심볼 이름을 만들고 dlsym 으로 찾아 buf+1 을 넘겨 호출한 뒤 반환값이 0 이 아니면 플래그를 출력한다
objdump 로 뽑은 main 뒷부분 — 스택에 f 와 밑줄과 입력 첫 글자를 넣어 f_X 라는 심볼 이름을 만들고 dlsym 으로 찾아 buf+1 을 넘겨 호출한 뒤 반환값이 0 이 아니면 플래그를 출력한다

여기가 핵심이다. 스택에 'f', '_', buf[0], '\0' 을 차례로 넣어 "f_<첫 글자>" 라는 문자열을 만들고, 그 이름으로 dlsym 한다. 그리고 찾은 함수를 buf+1 로 호출한다.

C 로 옮기면 이렇다.

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!");
}

입력이 곧 플래그이므로, 우리가 할 일은 fn 이 0 아닌 값을 돌려주게 만드는 64자를 찾는 것이다.

입력 알파벳

# 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
objdump 로 뽑은 verify 함수 — 인덱스 0 부터 0x3f 까지 돌면서 각 글자가 0 에서 9 사이이거나 a 에서 f 사이인지 검사하고 아니면 Wrong input 을 찍고 종료한다
objdump 로 뽑은 verify 함수 — 인덱스 0 부터 0x3f 까지 돌면서 각 글자가 0 에서 9 사이이거나 a 에서 f 사이인지 검사하고 아니면 Wrong input 을 찍고 종료한다

0x30~0x39(0-9)와 0x61~0x66(a-f), 그리고 i <= 0x3f 라 정확히 64글자.

64자 소문자 hex — 탐색 공간은 16⁶⁴ 이다. 무차별 대입은 애초에 논외고, 구조를 봐야 한다.



💣 핵심 — .so 가 상태, f_d 가 전이

라이브러리 하나를 열어 본다

nm -D --defined-only extracted/lib/start.so; echo ---; strings -a extracted/lib/start.so | grep -c "^lib/"
nm 으로 본 start.so 의 내보내기 심볼 — f_0 부터 f_f 까지 열여섯 개가 정확히 있고 lib 로 시작하는 경로 문자열도 열여섯 개다
nm 으로 본 start.so 의 내보내기 심볼 — f_0 부터 f_f 까지 열여섯 개가 정확히 있고 lib 로 시작하는 경로 문자열도 열여섯 개다

내보내는 함수가 f_0 ~ f_f 정확히 16개. 그리고 lib/... 경로 문자열도 16개.

hex 숫자 하나당 함수 하나, 함수 하나당 다음 라이브러리 하나. 여기서 모양이 잡힌다.

f_d 안을 본다

# 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
objdump 로 뽑은 start.so 의 f_0 함수 — 정해진 다음 so 파일을 dlopen 하고 인자 첫 글자로 f_ 심볼 이름을 만들어 dlsym 한 뒤 인자를 하나 앞으로 밀어 재귀 호출하고 반환값을 그대로 넘긴다
objdump 로 뽑은 start.so 의 f_0 함수 — 정해진 다음 so 파일을 dlopen 하고 인자 첫 글자로 f_ 심볼 이름을 만들어 dlsym 한 뒤 인자를 하나 앞으로 밀어 재귀 호출하고 반환값을 그대로 넘긴다

main 과 똑같은 짓을 한다.

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);                                                // 반환값을 그대로 올려보낸다
}

정리하면 이렇다.

dlopen 대상은 "지금 함수의 이름"이 결정한다. f_0 안에서는 항상 같은 파일을 연다. 즉 직전에 소비한 글자가 다음 라이브러리를 고른다.

dlsym 이름은 "다음 글자"가 결정한다. 그리고 인자를 한 칸 밀어 재귀한다.

반환값은 그대로 위로 전달된다. 중간에서 값을 바꾸지 않는다.

이게 정확히 결정적 유한 오토마타다. 라이브러리 = 상태, f_d = 라벨 d 인 전이, 입력 문자열 = 전이 열.

.so 파일 하나가 상태이고 f_d 가 라벨 d 인 전이임을 보인 도식 — 정답 경로 위 상태들이 세로로 이어지고 각 단계에서 나머지 열다섯 전이는 다른 곳으로 흩어진다
.so 파일 하나가 상태이고 f_d 가 라벨 d 인 전이임을 보인 도식 — 정답 경로 위 상태들이 세로로 이어지고 각 단계에서 나머지 열다섯 전이는 다른 곳으로 흩어진다

끝은 어디인가

전이 상태는 dlopen 을 하지만, 어딘가에는 그냥 답을 돌려주는 상태가 있어야 한다. 크기가 작은 20개(15,560바이트)가 그 후보다. 크기에 기대지 말고 코드로 판별한다 — dlopen@plt 를 안 부르는 .so 를 고르면 된다.

#!/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
종료 상태 스캔 결과 — 1257개 중 dlopen 을 하지 않는 so 가 20개이고 그중 219f2e3164 의 f_8 만 1 을 돌려주며 나머지 319개 함수는 전부 0 이다
종료 상태 스캔 결과 — 1257개 중 dlopen 을 하지 않는 so 가 20개이고 그중 219f2e3164 의 f_8 만 1 을 돌려주며 나머지 319개 함수는 전부 0 이다

종료 상태 20개 × 16함수 = 320개 중 1 을 돌려주는 건 딱 하나, 219f2e3164.so 의 f_8.

수락 상태와 마지막 글자가 동시에 확정됐다.


🐛 삽질

▶🕳️ 삽질 1 — 파일 크기로 종류를 갈랐다가 근거를 바꿨다

크기가 세 종류라는 걸 보고 처음엔 그걸 그대로 판별 기준으로 썼다.

for f in $(ls -l lib/*.so | awk '{if ($5==15560) print $NF}'); do ... done

답은 맞았다. 15,560바이트 20개가 정말로 종료 상태였다. 그런데 근거가 약하다.

크기가 다른 이유는 "dlopen 을 안 해서 코드와 문자열이 줄었다" 인데, 그건 결과지 정의가 아니다. 다른 배포본이나 다른 컴파일 옵션이면 숫자가 달라지고, 하필 크기가 같은 전이 상태가 하나라도 있으면 조용히 틀린다.

그래서 scan_terminals.py 는 크기를 아예 안 본다. objdump 출력에 <dlopen@plt> 가 있는가로 가른다.

if "<dlopen@plt>" in out:
    return None                      # 전이 상태

결과는 같았지만(20개), 이제는 "왜 20개인지"가 설명된다. 분류 기준은 관찰된 상관관계가 아니라 정의를 써야 한다 — 여기서는 그 차이가 결과를 안 바꿨을 뿐이다.

▶🕳️ 삽질 2 — sed 주석 한 줄이 조용히 사라졌다

디스어셈블에 <-- 주석을 얹는 규칙을 16개 썼는데, 붙은 건 15개였다.

에러도 안 나고 경고도 없다. sed 는 매칭이 안 되면 그냥 넘어간다. 개수를 세지 않았으면 못 알아챘을 것이다.

objdump ... | sed -f annot_main.sed | grep -c '<--'

빠진 건 이 줄이었다.

s|^    13b6:.*|&           <-- RTLD_LAZY \| RTLD_GLOBAL|

s|...|...| 에서 구분자가 | 인데 치환문 안에 | 를 그대로 썼다. sed 는 거기서 치환문이 끝난 줄 알고 뒤를 옵션으로 읽다가 규칙을 버린다.

dlopen 플래그를 설명하려니 RTLD_LAZY | RTLD_GLOBAL 이라고 쓰는 게 자연스러워서 생긴 일이다. 문구를 RTLD_LAZY + RTLD_GLOBAL 로 바꿔 해결했다(구분자를 # 등으로 바꿔도 된다).

주석을 얹었으면 grep -c '<--' 로 개수를 확인한다. 안 그러면 글에 실리는 캡쳐에서 설명 한 줄이 조용히 빠진다.

🎯 전이표를 뽑는다

f_d 안의 dlopen 인자 문자열을 읽으면 전이 대상이 나온다. 디스어셈블에서 call ...<dlopen@plt> 바로 앞의 lea rax,[rip+...] 가 가리키는 주소의 C 문자열이 그것이다.

#!/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
전이표 추출 결과 — so 파일 1257개를 파싱해 전이 상태 1237개와 종료 상태 20개로 나뉘고 전이가 16개가 아닌 상태는 하나도 없으며 수락 상태는 219f2e3164 의 f_8 하나다
전이표 추출 결과 — so 파일 1257개를 파싱해 전이 상태 1237개와 종료 상태 20개로 나뉘고 전이가 16개가 아닌 상태는 하나도 없으며 수락 상태는 219f2e3164 의 f_8 하나다

전이 상태 1,237개 × 16 = 간선 19,792개. 전이가 16개가 아닌 상태는 하나도 없다 — 파싱이 빠짐없이 됐다는 뜻이다.





🚀 Full Exploit

verify 가 정확히 64글자를 요구하므로 경로 길이가 정확히 63이어야 한다. 마지막 64번째 글자는 종료 상태의 함수를 고를 뿐 전이를 하지 않기 때문이다.

여기서 "최단 경로를 찾으면 되지 않나" 싶은데, 전이 그래프에는 사이클이 있어서 최단 경로가 63보다 짧게 나올 수 있다. 그러면 verify 에서 걸린다. 그래서 길이별 도달 가능 집합을 뒤에서부터 계산했다. reach[k] 를 "k번 더 전이하면 수락 상태에 닿을 수 있는 상태들"로 두고, 앞으로 걸을 때 reach[k-1] 안에 있는 전이만 고르면 길이가 정확히 맞는다.

실제로 이 그래프가 어땠는지는 세어 보면 나온다.

# 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
경로 길이 통계 — BFS 최단 전이 수가 63 으로 verify 가 요구하는 값과 같고, 길이 80 이하에서 수락 상태로 가는 경로는 63짜리 하나뿐이라 성공 경로 위에는 사이클도 갈림길도 없다
경로 길이 통계 — BFS 최단 전이 수가 63 으로 verify 가 요구하는 값과 같고, 길이 80 이하에서 수락 상태로 가는 경로는 63짜리 하나뿐이라 성공 경로 위에는 사이클도 갈림길도 없다

BFS 최단이 마침 63이었고, 길이 80 이하에서 수락 상태로 가는 경로는 63짜리 하나뿐이다. 성공 경로 위에는 사이클도 갈림길도 없다는 뜻이라, 이 문제에 한해서는 최단 경로로 풀어도 같은 답이 나왔을 것이다.

그래도 길이를 고정해 찾는 쪽을 택했다. 그래야 "운 좋게 최단이 63이었다"에 기대지 않는다.

#!/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
solve.py 실행 결과 — 전이 상태 1237개와 종료 상태 20개를 읽어 수락 상태 219f2e3164 의 f_8 을 찾고 길이 63 경로가 정확히 1개임을 세어 64자 플래그를 출력한다
solve.py 실행 결과 — 전이 상태 1237개와 종료 상태 20개를 읽어 수락 상태 219f2e3164 의 f_8 을 찾고 길이 63 경로가 정확히 1개임을 세어 64자 플래그를 출력한다

--count 는 길이 63 경로가 몇 개인지 동적계획법으로 세는 옵션이다. 결과는 1개 — 답이 유일하다.

정적 전이표가 런타임과 같은가

objdump 로 읽은 표가 실제 실행과 어긋나면 답도 틀린다. strace 로 main 이 여는 .so 순서를 받아 예측과 한 칸씩 대조했다.

#!/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
strace 로 잡은 실제 dlopen 순서와 정적 전이표 예측을 대조한 결과 — 64개 라이브러리가 한 칸도 어긋나지 않고 마지막이 수락 상태 219f2e3164 로 끝난다
strace 로 잡은 실제 dlopen 순서와 정적 전이표 예측을 대조한 결과 — 64개 라이브러리가 한 칸도 어긋나지 않고 마지막이 수락 상태 219f2e3164 로 끝난다

start.so 하나 + 전이 63번 = 64개. 순서가 한 칸도 어긋나지 않는다.

실제 바이너리로

#!/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
verify.py 실행 결과 — 정답만 Flag is DH 로 시작하는 플래그를 출력하고 마지막 글자, 첫 글자, 가운데 한 글자를 각각 바꾼 세 대조군은 모두 Wrong 이 나온다
verify.py 실행 결과 — 정답만 Flag is DH 로 시작하는 플래그를 출력하고 마지막 글자, 첫 글자, 가운데 한 글자를 각각 바꾼 세 대조군은 모두 Wrong 이 나온다
DH{20654ccdb7c43bd1ab398283f9895ac285e8c419c4c157db2f3f50de92599bd8}

한 글자만 바꿔도 전부 Wrong!. 어느 위치를 건드리든 그 지점에서 경로가 갈라져 다른 종료 상태로 떨어진다.




🧪 재현

./reproduce.sh

오프라인 문제라 인자가 없다. 필요한 건 python3(+pyelftools), objdump, strace 셋이다.

reproduce.sh 가 하는 일은 이 글의 순서와 같다. 종료 상태를 찾고 → 전이표를 뽑고 → 길이 63 경로를 세어 유일한지 확인하고 → strace 로 런타임과 대조하고 → 실제 main 으로 플래그를 받는다.

판정은 이렇게 읽는다.

화면뜻대처
전이 16개가 아닌 상태: N (N>0)lea/dlopen 짝짓기가 실패objdump 버전 확인
수락 상태가 0개다종료 상태 판별이 어긋남다른 배포본인지 확인
길이가 맞는 경로가 없다길이 상수가 틀림verify 의 0x3f 를 다시 확인
경로 수 : 2개 이상답이 여럿 — 해석 오류 가능전이표를 trace_check 로 대조
strace 대조에서 불일치정적 표가 틀림그 인덱스의 .so 를 직접 디스어셈블
Wrong!실행 권한 없음chmod +x extracted/main

extract_dfa.py 는 .so 1,257개를 objdump 로 전부 파싱하지만 프로세스 풀을 써서 7초면 끝난다. 파일이 많다고 겁먹을 규모는 아니다.



📝 결론

런타임에 이름으로 부르면 정적 호출 그래프가 사라진다.

dlopen 의 인자도 dlsym 의 심볼 이름도 실행 중에 만들어지니, 디스어셈블러가 "이 함수가 저 함수를 부른다"를 그려 줄 수 없다. 이 문제는 그 성질을 이용해 로직이 아니라 파일 배치에 정답을 숨겼다. main 과 .so 하나만 읽으면 코드는 30줄도 안 되는데, 답은 20MB 어치 파일 이름 속에 있다.

구조가 보이면 리버싱이 아니라 그래프 문제가 된다.

.so = 상태, f_d = 전이라는 걸 알아차린 뒤로는 디스어셈블이 필요 없다. 필요한 건 전이표 하나고, 그건 기계적으로 뽑힌다. 1,257개를 하나씩 읽을 일이 아니라 1,257개에서 같은 값을 뽑아내는 스크립트를 쓸 일이다.

"최단"이 아니라 "정확히 그 길이"를 찾아야 한다.

사이클이 있는 그래프에서 길이를 맞추는 건 최단경로와 다른 문제다. 뒤에서부터 reach[k] 를 채워 두고 앞으로 걸으면 간단히 해결되는데, BFS 를 그대로 쓰면 짧은 답이 나와 verify 에서 막힌다. 제약이 "도달"이 아니라 "도달 + 길이"일 때 늘 나오는 함정이다.

정적으로 읽은 모델은 런타임과 대조해 두면 마음이 편하다.

strace -e trace=openat 한 줄로 실제 dlopen 순서를 받아 예측과 맞춰 봤다. 64칸이 전부 일치하니 전이표가 맞다는 게 확인됐고, 만약 어긋났다면 어느 인덱스에서 갈리는지까지 바로 나왔을 것이다. 파싱으로 만든 모델은 이렇게 한 번 대조해 두는 값이 크다.

방어 쪽에서 보면, 이런 구조는 분석을 귀찮게 만들 뿐 막지는 못한다. 파일 1,257개가 위압적으로 보여도 규칙이 하나로 통일돼 있으면 스크립트 한 편에 무너진다. 오히려 규칙이 균일하다는 점 — 모든 .so 가 정확히 16개 함수를 갖고 전부 같은 모양이라는 점 — 이 자동 추출을 쉽게 만들어 줬다.

이 글이 도움이 됐나요?

Comments

댓글

0개

댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)

댓글 불러오는 중…

Related

관련 글

3개
[🥇 Gold 1] 세그폴트가 곧 정답이다 — DreamHack Nonsense 풀이
blog

[🥇 Gold 1] 세그폴트가 곧 정답이다 — DreamHack Nonsense 풀이

main 은 해시 결과인 32비트 값을 포인터로 역참조해 매번 SIGSEGV 를 낸다. .init_array 가 걸어 둔 핸들러가 폴트 주소를 정답표와 대조하고 레지스터를 고쳐 재개하므로, 판정은 main 이 아니라 폴트 24번의 주소열이 한다. 해시는 입력이 2바이트뿐이라 바이너리 자체를 dlopen 해 오라클로 쓰고 전수조사로 48글자를 복원했다.
#dreamhack#ctf#reversing+7
2026-08-19#dreamhack +4
[🥈 Silver 4] 화면에 아무것도 안 뜨는 바이너리에서 flag 뽑아내기 — DreamHack fake 풀이
blog

[🥈 Silver 4] 화면에 아무것도 안 뜨는 바이너리에서 flag 뽑아내기 — DreamHack fake 풀이

실행해도 아무것도 출력하지 않는 ELF 바이너리 하나. strace로 확인해보니 read/write 계열 syscall이 단 한 번도 없다 — 임포트된 함수조차 malloc/free뿐이다. objdump로 뜯어보니 main()은 스택에 movabs 즉시값으로 23바이트 시드 버퍼를 조립해 malloc한 뒤, reverse → 인접 바이트 교환 → XOR라는 세 단계 변환만 거쳐 곧바로 free해버린다. 화면에 찍히는 건 없지만, 그 변환 결과를 파이썬으로 그대로 재현하고 gdb로 free() 직전 힙 버퍼를 직접 들여다보는 것으로 flag를 확인했다.
#dreamhack#ctf#reversing+4
2026-07-21#dreamhack +4
[🥇 Gold 3] 창 하나로 슬롯 열 개를 읽고 CRT 로 잭팟 맞추기 — DreamHack Casino-777 풀이
blog

[🥇 Gold 3] 창 하나로 슬롯 열 개를 읽고 CRT 로 잭팟 맞추기 — DreamHack Casino-777 풀이

슬롯 열 개의 0번 칸만 보여주는 슬롯머신이다. 회전 결과가 버퍼에 되쓰여 상태가 누적된다는 점을 이용해 슬롯 전체를 읽어내고, 길이가 전부 서로 다른 소수라는 걸 이용해 CRT 로 잭팟이 되는 회전량을 계산한다. 마지막 관문은 그 회전량이 64비트 밖이라는 것이었다.
#dreamhack#ctf#reversing+6
2026-10-22#dreamhack +3