[🥇 Gold 4] 코드보다 데이터가 열 배 큰 이유 — DreamHack Snaky 풀이

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

nm -D extracted/chall; strings -a extracted/chall | grep -E "%255s|good|wrong"

# annot_charset.sed
s|cmp    al,0x4b|&               <-- 'K'|
s|cmp    al,0x39|&               <-- '9'|
s|cmp    al,0x7a|&               <-- 'z'|
s|cmp    al,0x37|&               <-- '7'|
s|cmp    al,0x32|&               <-- '2'|
s|cmp    al,0x73|&               <-- 's'  여섯 글자만 허용한다|
s|test   al,al|&                <-- NUL 이면 검사 끝|
s|cmp    DWORD PTR \[rbp-0x4\],0xff|&    <-- 최대 256글자|

objdump -d -M intel --no-show-raw-insn --start-address=0x40127a --stop-address=0x401348 extracted/chall | sed -f annot_charset.sed | grep -E "cmp|test|jle"

# annot_index.sed — 주소로 줄을 지정해야 같은 명령이 여러 번 나올 때 안 헷갈린다
s|^  401202:.*|&    <-- x <= 24|
s|^  40120e:.*|&    <-- y <= 24|
s|^  40121a:.*|&    <-- z <= 24|
s|^  401238:.*|&           <-- rsi = z * 625|
s|^  401242:.*|&                 <-- rax = 4y|
s|^  401246:.*|&                 <-- rax = 5y|
s|^  401249:.*|&            <-- rdx = 20y|
s|^  401251:.*|&                 <-- rax = 25y|
s|^  401254:.*|&                 <-- rax = 25y + 625z|
s|^  401257:.*|&            <-- rdx = x + 25y + 625z|
s|^  40125b:.*|&   <-- 격자 시작 0x404060|
s|^  401262:.*|&                 <-- rax = 격자 + 오프셋|
s|^  401268:.*|&                 <-- 값이 1 이면 못 간다|

objdump -d -M intel --no-show-raw-insn --start-address=0x4011eb --stop-address=0x40127a extracted/chall | sed -f annot_index.sed

rsi = z * 0x271        ; 0x271 = 625
rax = y
rax = y << 2           ; 4y
rax = 4y + y           ; 5y
rdx = rax * 4          ; 20y
rax = 5y + 20y         ; 25y
rax = 25y + 625z
rdx = rax + x          ; x + 25y + 625z
rax = 0x404060 + rdx

# annot_walk.sed
s|^  401372:.*|&    <-- 시작 x = 24|
s|^  401379:.*|&    <-- 시작 y = 12|
s|^  401380:.*|&    <-- 시작 z = 12|
s|^  401394:.*|&      <-- mark(24,12,12)|
s|^  4013e4:.*|&        <-- 'K' : x + 1|
s|^  4013ea:.*|&        <-- '9' : x - 1|
s|^  4013f0:.*|&        <-- 'z' : y + 1|
s|^  4013f6:.*|&        <-- '7' : y - 1|
s|^  4013fc:.*|&        <-- '2' : z + 1|
s|^  401402:.*|&        <-- 's' : z - 1|
s|^  40140f:.*|&    <-- 목표 판정이 먼저다 : x == 0|
s|^  401415:.*|&    <-- y == 12|
s|^  40141b:.*|&    <-- z == 12  → good :)|
s|^  401435:.*|&      <-- 그 다음에 이동 가능 판정|
s|^  401452:.*|&      <-- 마지막에 이 칸을 칠한다 (뱀 몸통)|

objdump -d -M intel --no-show-raw-insn --start-address=0x401372 --stop-address=0x40140f extracted/chall | sed -f annot_walk.sed

objdump -d -M intel --no-show-raw-insn --start-address=0x40140f --stop-address=0x401460 extracted/chall | sed -f annot_walk.sed

int check(char *s)
{
    if (!check_chars(s)) return 0;          // K 9 z 7 2 s 만 허용
 
    int x = 24, y = 12, z = 12;
    mark(x, y, z);                          // 시작 칸도 몸통이다
 
    for (char *p = s; *p && p < s + 0x100; p++) {
        switch (*p) {
            case 'K': x++; break;  case '9': x--; break;
            case 'z': y++; break;  case '7': y--; break;
            case '2': z++; break;  case 's': z--; break;
            default: return 0;
        }
        if (x == 0 && y == 12 && z == 12) return 1;   // ① 도착이면 그 자리에서 성공
        if (!can_move(x, y, z))            return 0;   // ② 벽이거나 이미 밟은 칸이면 실패
        mark(x, y, z);                                 // ③ 지나온 칸을 벽으로 만든다
    }
    return 0;
}

# runtime_check.gdb
set pagination off
set confirm off
 
# 0x401394 = check() 안의 첫 mark(x,y,z) 호출 직전
break *0x401394
# 0x401452 = 걸음마다 도는 mark(x,y,z) 호출 직전
break *0x401452
 
run
 
printf "\n[1] 시작 좌표 (mark 인자: rdi=x, rsi=y, rdx=z)\n"
printf "    x=%d  y=%d  z=%d\n", $edi, $esi, $edx
printf "    격자 주소 0x404060, 인덱스 x+25*y+625*z\n"
printf "    시작 칸 값 = %d   (0 이면 통로)\n", *(unsigned char *)(0x404060 + $edi + 25*$esi + 625*$edx)
 
continue
 
printf "\n[2] 첫 걸음 뒤 — 입력 첫 글자는 'z' 이므로 y 가 1 늘어야 한다\n"
printf "    x=%d  y=%d  z=%d\n", $edi, $esi, $edx
printf "    이 칸의 값 = %d   (아직 0 이라 통과)\n", *(unsigned char *)(0x404060 + $edi + 25*$esi + 625*$edx)
 
# 다음 걸음의 mark 호출까지 진행 — 그 사이에 앞 칸이 칠해졌어야 한다
continue
printf "\n[3] 한 걸음 더 간 뒤 — 방금 지나온 칸을 확인한다\n"
printf "    (24,13,12) 값 = %d   (1 이면 다시 못 밟는다)\n", *(unsigned char *)(0x404060 + 24 + 25*13 + 625*12)
 
printf "\n[4] 통로 칸 수를 실행 중 메모리에서 직접 센다\n"
set $n = 0
set $i = 0
while $i < 15625
  if *(unsigned char *)(0x404060 + $i) == 0
    set $n = $n + 1
  end
  set $i = $i + 1
end
printf "    값이 0 인 칸 = %d 개  (원래 107 칸, 지나온 2칸이 이미 칠해졌다)\n", $n
 
quit

printf 'zzzzzz222222277779999zzzzzzzssssssss999777777777222222222222zzzzz999zzz999777ssss99999999999777777sssssssz\n' | gdb -q -batch -x runtime_check.gdb extracted/chall

#!/usr/bin/env python3
"""격자가 왜 답을 하나만 갖는지 구조로 확인한다."""
import collections
 
from solve import MOVES, START, GOAL, load_grid, bfs
 
g = load_grid("extracted/chall")
 
opens = {(x, y, z)
         for z in range(25) for y in range(25) for x in range(25)
         if g[x + 25 * y + 625 * z] == 0}
 
deg = collections.Counter(
    sum(1 for d in MOVES.values() if (x + d[0], y + d[1], z + d[2]) in opens)
    for (x, y, z) in opens
)
 
print(f"통로 칸        : {len(opens)} / 15625")
print(f"이웃 통로 수 분포 : {dict(sorted(deg.items()))}")
print(f"  끝점(1개)     : {deg[1]}")
print(f"  외길(2개)     : {deg[2]}")
print(f"  갈림길(3개+)  : {sum(v for k, v in deg.items() if k >= 3)}")
print()
 
ends = sorted(p for p in opens
              if sum(1 for d in MOVES.values() if (p[0] + d[0], p[1] + d[1], p[2] + d[2]) in opens) == 1)
print(f"끝점 좌표      : {ends}")
print(f"시작 {START} / 목표 {GOAL} 와 일치? {set(ends) == {START, GOAL}}")
print()
 
path = bfs(g)
pts, cur = [START], START
for ch in path:
    d = MOVES[ch]
    cur = (cur[0] + d[0], cur[1] + d[1], cur[2] + d[2])
    pts.append(cur)
 
print(f"BFS 경로 걸음   : {len(path)}")
print(f"경로가 밟는 칸  : {len(set(pts))}")
print(f"통로 전체와 같나 : {set(pts) == opens}   ← 같으면 곁가지가 하나도 없다는 뜻")

python3 analyze_grid.py

#!/usr/bin/env python3
"""Snaky (DreamHack, Gold 4 / reversing) — solver
 
바이너리가 하는 일:
  .data 0x404060 에 25x25x25 바이트 배열이 있다. 인덱스는 x + 25*y + 625*z.
  값 1 = 막힌 칸. 시작 (24,12,12) 에서 출발해 입력 문자열을 한 글자씩 방향으로 읽는다.
 
      K: x+1    9: x-1    z: y+1    7: y-1    2: z+1    s: z-1
 
  각 걸음마다
    ① (0,12,12) 에 도달했으면 그 자리에서 성공(good :)
    ② 0..24 범위를 벗어나거나 값이 1 인 칸이면 실패
    ③ 아니면 그 칸을 1 로 칠하고 계속    ← 지나온 칸을 벽으로 만든다(뱀)
 
  ③ 때문에 경로는 자기 자신과 만날 수 없다. 그래서 단순경로만 답이 된다.
  BFS 최단경로는 애초에 같은 칸을 두 번 밟지 않으므로 이 제약을 자동으로 만족한다.
 
  flag = DH{<찾은 경로 문자열>}
"""
import argparse
import collections
import sys
 
N = 25
START = (24, 12, 12)
GOAL = (0, 12, 12)
 
# 문자 → (dx, dy, dz).  디스어셈블 0x4013a6~0x401406 그대로.
MOVES = {
    "K": (1, 0, 0),
    "9": (-1, 0, 0),
    "z": (0, 1, 0),
    "7": (0, -1, 0),
    "2": (0, 0, 1),
    "s": (0, 0, -1),
}
 
GRID_VA, DATA_VA, DATA_OFF = 0x404060, 0x404040, 0x3040
 
 
def load_grid(path: str) -> bytes:
    """ELF 에서 25^3 격자를 그대로 떠 온다 (섹션 헤더 없이 고정 오프셋)."""
    blob = open(path, "rb").read()
    off = DATA_OFF + (GRID_VA - DATA_VA)
    g = blob[off:off + N * N * N]
    if len(g) != N * N * N:
        sys.exit(f"격자를 못 읽었다: {len(g)} 바이트")
    return g
 
 
def blocked(g: bytes, x: int, y: int, z: int) -> bool:
    """can_move() 와 같은 판정 — 범위 밖이거나 값이 1 이면 못 간다."""
    if not (0 <= x <= 24 and 0 <= y <= 24 and 0 <= z <= 24):
        return True
    return g[x + 25 * y + 625 * z] == 1
 
 
def bfs(g: bytes) -> str | None:
    """START → GOAL 최단 경로를 이동 문자열로 돌려준다."""
    prev: dict = {START: None}
    q = collections.deque([START])
    while q:
        cur = q.popleft()
        for ch, (dx, dy, dz) in MOVES.items():
            nxt = (cur[0] + dx, cur[1] + dy, cur[2] + dz)
            if nxt == GOAL:                      # 목표 판정이 이동 가능 판정보다 먼저다
                path, node = [ch], cur
                while prev[node] is not None:
                    pch, pnode = prev[node]
                    path.append(pch)
                    node = pnode
                return "".join(reversed(path))
            if nxt in prev or blocked(g, *nxt):
                continue
            prev[nxt] = (ch, cur)
            q.append(nxt)
    return None
 
 
def count_simple_paths(g: bytes, limit: int = 5) -> int:
    """단순경로가 정말 하나뿐인지 센다 (열린 칸이 107개라 완전탐색이 된다)."""
    found = 0
    seen = {START}
 
    def dfs(cur):
        nonlocal found
        if found >= limit:
            return
        for ch, (dx, dy, dz) in MOVES.items():
            nxt = (cur[0] + dx, cur[1] + dy, cur[2] + dz)
            if nxt == GOAL:
                found += 1
                if found >= limit:
                    return
                continue
            if nxt in seen or blocked(g, *nxt):
                continue
            seen.add(nxt)
            dfs(nxt)
            seen.discard(nxt)
 
    dfs(START)
    return found
 
 
def simulate(g: bytes, s: str) -> bool:
    """바이너리의 check() 를 그대로 흉내내 검증한다."""
    if any(c not in MOVES for c in s):
        return False
    grid = bytearray(g)
    x, y, z = START
    grid[x + 25 * y + 625 * z] = 1
    for c in s:
        dx, dy, dz = MOVES[c]
        x, y, z = x + dx, y + dy, z + dz
        if (x, y, z) == GOAL:
            return True
        if not (0 <= x <= 24 and 0 <= y <= 24 and 0 <= z <= 24):
            return False
        if grid[x + 25 * y + 625 * z] == 1:
            return False
        grid[x + 25 * y + 625 * z] = 1
    return False
 
 
def main() -> int:
    ap = argparse.ArgumentParser()
    ap.add_argument("binary", nargs="?", default="extracted/chall")
    ap.add_argument("--count-paths", action="store_true", help="단순경로 개수도 센다")
    a = ap.parse_args()
 
    g = load_grid(a.binary)
    opens = sum(1 for b in g if b == 0)
    print(f"[*] 격자 25x25x25 = {len(g)} 칸,  통로 {opens} 칸 / 벽 {len(g) - opens} 칸")
    print(f"[*] 시작 {START} → 목표 {GOAL}")
 
    path = bfs(g)
    if path is None:
        print("[-] 경로 없음")
        return 1
 
    print(f"[+] 경로 길이 {len(path)}")
    print(f"[+] 경로     {path}")
    print(f"[+] 자체 검증(check 재현) : {'통과' if simulate(g, path) else '실패'}")
 
    if a.count_paths:
        n = count_simple_paths(g)
        print(f"[*] 단순경로 개수 : {'5개 이상' if n >= 5 else n}개")
 
    print(f"[+] FLAG: DH{{{path}}}")
    return 0
 
 
if __name__ == "__main__":
    sys.exit(main())

python3 solve.py --count-paths

#!/usr/bin/env python3
"""찾은 경로를 실제 바이너리에 먹여 good :) 이 나오는지 확인한다."""
import subprocess
 
BIN = "./extracted/chall"
ANSWER = ("zzzzzz222222277779999zzzzzzzssssssss999777777777222222222222"
          "zzzzz999zzz999777ssss99999999999777777sssssssz")
 
 
def run(s: str) -> str:
    p = subprocess.run([BIN], input=s + "\n", capture_output=True, text=True, timeout=20)
    return p.stdout.strip()
 
 
cases = [
    ("정답 경로", ANSWER),
    ("마지막 글자만 바꿈", ANSWER[:-1] + "7"),
    ("한 걸음 짧게", ANSWER[:-1]),
    ("역순", ANSWER[::-1]),
]
 
for label, s in cases:
    out = run(s)
    print(f"{label:20s} len={len(s):3d}  →  {out}")
 
print()
print(f"FLAG: DH{{{ANSWER}}}")

python3 verify.py

DH{zzzzzz222222277779999zzzzzzzssssssss999777777777222222222222zzzzz999zzz999777ssss99999999999777777sssssssz}

./reproduce.sh