[🥇 Gold 4] 5바이트 스텁 97개로 부순 건 코드가 아니라 디스어셈블러였다 — DreamHack Vernichtet 풀이

#!/usr/bin/env bash
# cap_recon.sh — 배포 바이너리 정찰: 포맷 / 보호기법 / 눈에 띄는 문자열
file extracted/main
readelf -h extracted/main | grep -E 'Type:|Entry point|Number of section headers'
readelf -d extracted/main | grep -E 'NEEDED|BIND_NOW|PIE'
strings -a extracted/main | grep -E 'Usage|Correct|Wrong answer|Fread|sha256sum'

./cap_recon.sh

bash -c "echo DH{$(sha256sum '%s' | awk '{print $1}')}"

objdump -d -M intel --start-address=0x1269 --stop-address=0x12b7 extracted/main

#!/usr/bin/env bash
# cap_decode.sh — 같은 5바이트를 두 가지로 디코딩해 본다.
#   objdump 는 0x1271 부터 선형으로 읽고, CPU 는 jmp 를 따라 0x1272 부터 읽는다.
echo '# 원본 바이트 (파일 오프셋 = 가상주소, .text 는 1:1 매핑)'
xxd -s 0x1271 -l 5 extracted/main
echo
echo '# objdump 선형 스윕이 본 것 (0x1271 부터)'
objdump -d -M intel --start-address=0x1271 --stop-address=0x1276 extracted/main | tail -3
echo
echo '# CPU 가 실제로 실행하는 것 (jmp 목적지 0x1272 부터)'
objdump -d -M intel --start-address=0x1272 --stop-address=0x1276 extracted/main | tail -3

./cap_decode.sh

set pagination off
set confirm off
set disassembly-flavor intel
starti
python
import gdb
 
base = None
for line in gdb.execute("info proc mappings", to_string=True).splitlines():
    f = line.split()
    if len(f) >= 5 and f[-1].endswith("/main"):
        base = int(f[0], 16)
        break
print("PIE base (info proc mappings) = %#x" % base)
 
stub = base + 0x1271
print("\n[objdump 가 본 것] 0x1271 부터 선형 해석")
gdb.execute("x/2i %#x" % stub)
 
gdb.execute("break *%#x" % stub)
gdb.execute("continue")
 
print("\n[CPU 가 실제로 밟는 것] stepi 로 따라간다")
for _ in range(3):
    pc = int(gdb.parse_and_eval("$pc"))
    ins = gdb.execute("x/i $pc", to_string=True).strip().replace("=> ", "")
    rcx = int(gdb.parse_and_eval("$rcx")) & 0xFFFFFFFF
    print("  +%#06x  ecx=%#010x  %s" % (pc - base, rcx, ins.split(":", 1)[1].strip()))
    gdb.execute("stepi", to_string=True)
pc = int(gdb.parse_and_eval("$pc"))
ins = gdb.execute("x/i $pc", to_string=True).strip().replace("=> ", "")
print("  +%#06x  %s   <- 스텁을 빠져나온 첫 진짜 명령" % (pc - base, ins.split(":", 1)[1].strip()))
end
kill
quit

gdb -q -batch -x stub.gdb --args ./extracted/main answer.bin

#!/usr/bin/env bash
# cap_r2.sh — radare2 는 jmp 를 따라가는 재귀 하강이라 스텁을 "맞게" 읽는다.
# 대신 5바이트마다 기본블록이 갈라져 CFG 가 잘게 부서진다. 그 차이를 수치로 본다.
echo '### 원본 (스텁 살아 있음) — 0x1269 함수'
r2 -qq -e scr.color=0 -e log.level=0 -c 'aaa; s 0x1269; af; afi~num-bbs,edges,num-instrs' extracted/main
echo
echo '### deobf.py 로 NOP 패치한 뒤 같은 함수'
r2 -qq -e scr.color=0 -e log.level=0 -c 'aaa; s 0x1269; af; afi~num-bbs,edges,num-instrs' extracted/main_clean
echo
echo '### 원본 앞머리 — r2 가 표시한 겹침 표식(~)과 CODE XREF'
r2 -qq -e scr.color=0 -e log.level=0 -c 'aaa; s 0x1269; af; pd 12' extracted/main

./cap_r2.sh

#!/usr/bin/env python3
"""Vernichtet — anti-disassembly 스텁 제거.
 
main 의 .text 전체에 5바이트 잡음 `eb ff c1 ff c9` 가 박혀 있다.
  eb ff        jmp $+1        ; 자기 자신의 다음 바이트(=오퍼랜드 0xff)로 점프
  ff c1        inc ecx        ; 점프해서 들어온 뒤 실제로 실행되는 명령
  ff c9        dec ecx        ; 되돌린다 -> 실행 결과는 no-op
선형 스윕 디스어셈블러(objdump)는 0xeb 0xff 를 하나의 명령으로 읽어 버려
그 뒤 3바이트를 엉뚱한 명령(`sar edi,0xc9`)으로 해석하고, 그 오정렬이
바로 뒤 실제 명령까지 갉아먹는다.
 
길이를 유지한 채 NOP 5개로 덮으면 상대 분기 오프셋이 전부 그대로 살아 있어
그냥 다시 objdump 하면 원래 코드가 나온다.
"""
import sys
from pathlib import Path
 
STUB = bytes.fromhex("ebffc1ffc9")   # jmp $+1 ; inc ecx ; dec ecx
NOPS = b"\x90" * len(STUB)
 
src = Path(sys.argv[1] if len(sys.argv) > 1 else "extracted/main")
dst = Path(sys.argv[2] if len(sys.argv) > 2 else "extracted/main_clean")
 
data = bytearray(src.read_bytes())
count = 0
i = 0
while True:
    i = data.find(STUB, i)
    if i < 0:
        break
    data[i:i + len(STUB)] = NOPS
    count += 1
    i += len(STUB)
 
dst.write_bytes(bytes(data))
dst.chmod(0o755)
print(f"patched {count} stubs ({count * len(STUB)} bytes) -> {dst}")

python3 deobf.py && objdump -d -M intel --start-address=0x1269 --stop-address=0x12b6 extracted/main_clean | grep -v nop$

s|.*2d7c.*|&    <-- 힌트 테이블 0x4022 = i번째 엔트리의 "값"|
s|.*2d45.*|&    <-- 0x4021 = "행"|
s|.*2d0a.*|&    <-- 0x4020 = "열"|
s|.*je     136b.*|&    <-- 값이 0 이면 힌트 없음, 다음 엔트리로|
s|.*shl    eax,0x4.*|&              <-- 행 * 16|
s|.*sub    eax,edx.*|&              <-- ... - 행 = 행 * 15|
s|.*add    eax,esi.*|&              <-- 열 + 행*15 = 격자 인덱스|
s|.*cmp    sil,al.*|&               <-- buf 의 그 칸이 힌트 값과 같은가|
s|.*mov    eax,0x0.*|&      <-- 하나라도 틀리면 즉시 0 반환|
s|.*,0xe0.*|&        <-- i <= 224, 즉 엔트리 225개|

objdump -d -M intel --start-address=0x1269 --stop-address=0x138e extracted/main_clean | grep -v nop$ | sed -f annot_clues.sed

// 0x1269 — .data 0x4020 부터 (열, 행, 값) 3바이트 × 225 엔트리
int check_clues(unsigned char *buf)
{
    for (int i = 0; i <= 224; i++) {
        unsigned char val = TBL[3*i + 2];
        if (val == 0)                    // 값 0 = 힌트 없는 자리
            continue;
        unsigned char row = TBL[3*i + 1];
        unsigned char col = TBL[3*i + 0];
        if (buf[col + 15*row] != val)
            return 0;
    }
    return 1;
}

s|.*QWORD PTR \[rbp-0x28\],rdi.*|&    <-- 답안 버퍼 225바이트|
s|.*BYTE PTR \[rbp-0x1b\],0x0.*|&    <-- cx = 0 (현재 열)|
s|.*BYTE PTR \[rbp-0x1a\],0x0.*|&    <-- cy = 0 (현재 행)|
s|.*DWORD PTR \[rbp-0x14\],0x0.*|&    <-- row = 0|
s|.*shl    eax,0x4.*|&              <-- row * 16|
s|.*sub    eax,edx.*|&              <-- ... - row = row * 15|
s|.*add    eax,esi.*|&              <-- row*15 + col|
s|.*cmp    al,0x1.*|&               <-- 이 칸의 값이 1 인가|
s|.*BYTE PTR \[rbp-0x1b\],al.*|&    <-- cx = col|
s|.*BYTE PTR \[rbp-0x1a\],al.*|&    <-- cy = row|
s|.*\[rbp-0x10\],0xe$|&      <-- col <= 14|
s|.*\[rbp-0x14\],0xe$|&      <-- row <= 14|
s|.*\[rbp-0xc\],0x1$|&   <-- k = 1 부터 시작|

objdump -d -M intel --start-address=0x138e --stop-address=0x1443 extracted/main_clean | grep -v nop$ | sed -f annot_path_find.sed

s|.*cmp    BYTE PTR \[rbp-0x1b\],0x0.*|&    <-- cx > 0 인가|
s|.*cmp    BYTE PTR \[rbp-0x1b\],0xd.*|&    <-- cx <= 13 인가|
s|.*cmp    BYTE PTR \[rbp-0x1a\],0x0.*|&    <-- cy > 0 인가|
s|.*cmp    BYTE PTR \[rbp-0x1a\],0xd.*|&    <-- cy <= 13 인가|
s|.*BYTE PTR \[rbp-0x19\],al.*|&    <-- x0 = 왼쪽 경계|
s|.*BYTE PTR \[rbp-0x18\],al.*|&    <-- x1 = 오른쪽 경계|
s|.*BYTE PTR \[rbp-0x17\],al.*|&    <-- y0 = 위쪽 경계|
s|.*BYTE PTR \[rbp-0x16\],al.*|&    <-- y1 = 아래쪽 경계|
s|.*BYTE PTR \[rbp-0x15\],0x0.*|&    <-- found = 0|
s|.*\[rbp-0xc\],0x1$|&   <-- k = 1 부터 시작|

objdump -d -M intel --start-address=0x1443 --stop-address=0x14fd extracted/main_clean | grep -v nop$ | sed -f annot_path_clamp.sed

s|.*movsx  eax,BYTE PTR \[rbp-0x17\].*|&    <-- r = y0 부터|
s|.*movsx  eax,BYTE PTR \[rbp-0x19\].*|&    <-- c = x0 부터|
s|.*movsx  eax,BYTE PTR \[rbp-0x1a\].*|&    <-- cy 와 비교|
s|.*movsx  eax,BYTE PTR \[rbp-0x1b\].*|&    <-- cx 와 비교 (자기 자신 칸은 건너뛴다)|
s|.*shl    eax,0x4.*|&              <-- r * 16|
s|.*sub    eax,edx.*|&              <-- ... - r = r * 15|
s|.*add    eax,esi.*|&              <-- r*15 + c|
s|.*add    eax,0x1$|&               <-- 찾는 값 = k + 1|
s|.*cmp    edx,eax$|&               <-- 이 이웃 칸이 k+1 인가|
s|.*BYTE PTR \[rbp-0x15\],0x1.*|&    <-- found = 1, 여기로 이동|
s|.*movsx  eax,BYTE PTR \[rbp-0x18\].*|&    <-- c <= x1|
s|.*movsx  eax,BYTE PTR \[rbp-0x16\].*|&    <-- r <= y1|
s|.*xor    eax,0x1.*|&              <-- 못 찾았으면|
s|.*mov    eax,0x0.*|&      <-- 0 반환 (경로 끊김)|
s|.*,0xe0$|&        <-- k <= 224, 즉 225 까지 이어져야 한다|
s|.*mov    eax,0x1.*|&      <-- 끝까지 이어졌다|

objdump -d -M intel --start-address=0x14fd --stop-address=0x15f5 extracted/main_clean | grep -v nop$ | sed -f annot_path_scan.sed

// 0x138e
int check_path(unsigned char *buf)
{
    signed char cx = 0, cy = 0;
 
    for (int row = 0; row <= 14; row++)          // 값 1 이 있는 칸을 찾는다
        for (int col = 0; col <= 14; col++)
            if (buf[row*15 + col] == 1) { cx = col; cy = row; }
 
    for (int k = 1; k <= 224; k++) {
        signed char x0 = (cx >  0) ? cx - 1 : cx;   // 8방향 이웃 범위
        signed char x1 = (cx <= 13) ? cx + 1 : cx;
        signed char y0 = (cy >  0) ? cy - 1 : cy;
        signed char y1 = (cy <= 13) ? cy + 1 : cy;
        char found = 0;
 
        for (int r = y0; r <= y1; r++)
            for (int c = x0; c <= x1; c++) {
                if (r == cy && c == cx) continue;   // 자기 칸은 제외
                if (buf[r*15 + c] == k + 1) { found = 1; cx = c; cy = r; }
            }
 
        if (!found) return 0;                       // 경로가 끊기면 실패
    }
    return 1;
}

// 0x15f5
int main(int argc, char **argv)
{
    if (argc <= 1) { puts("Usage ./main <answer file>"); return 0; }
 
    FILE *f = fopen(argv[1], "rb");
    if (!f) { puts("File Not Found"); return 0; }
 
    fseek(f, 0, SEEK_END);
    long size = ftell(f);
    rewind(f);
    if (size != 0xe1) { puts("Wrong answer."); return 0; }   // 정확히 225 바이트
 
    unsigned char *buf = malloc(size);
    if (fread(buf, 1, size, f) != size) { puts("Fread failed"); return 0; }
 
    if (!check_clues(buf)) { puts("Wrong answer."); return 0; }
    if (!check_path(buf))  { puts("Wrong answer."); return 0; }
 
    char cmd[0x110];
    sprintf(cmd, "bash -c \"echo DH{$(sha256sum '%s' | awk '{print $1}')}\"", argv[1]);
    puts("Correct!");
    system(cmd);
    return 0;
}

#!/usr/bin/env python3
"""Vernichtet — .data 에 박힌 힌트 테이블을 15x15 격자로 복원한다.
 
check_clues(0x1269) 가 읽는 배열은 0x4020 부터 3바이트씩 225엔트리:
    b0 = data[0x4020 + 3*i]   -> 열(column)
    b1 = data[0x4021 + 3*i]   -> 행(row)
    b2 = data[0x4022 + 3*i]   -> 그 칸에 들어가야 하는 값 (0 이면 힌트 없음)
검사식은 buf[b0 + 15*b1] == b2.
 
.data 는 vaddr 0x4000 = 파일 오프셋 0x3000 이므로 0x4020 -> 0x3020.
"""
from pathlib import Path
 
BIN = Path(__file__).with_name("extracted") / "main"
DATA_VADDR, DATA_OFF = 0x4000, 0x3000
TABLE = 0x4020
N = 15
 
raw = BIN.read_bytes()
tbl = raw[TABLE - DATA_VADDR + DATA_OFF: TABLE - DATA_VADDR + DATA_OFF + 3 * N * N]
assert len(tbl) == 675, len(tbl)
 
grid = [[0] * N for _ in range(N)]
clues = []
for i in range(N * N):
    c, r, v = tbl[3 * i], tbl[3 * i + 1], tbl[3 * i + 2]
    if v == 0:
        continue
    assert 0 <= c < N and 0 <= r < N, (i, c, r, v)
    grid[r][c] = v
    clues.append((r, c, v))
 
print(f"clue entries: {len(clues)} / {N*N}")
print(f"values: min={min(v for _,_,v in clues)} max={max(v for _,_,v in clues)}")
print()
for r in range(N):
    print(" ".join(f"{grid[r][c]:3d}" if grid[r][c] else "  ." for c in range(N)))

python3 parse_clues.py

#!/usr/bin/env python3
"""Vernichtet (DreamHack, Gold 4 / reversing) — 자체 완결 솔버.
 
바이너리가 요구하는 것:
  1. 답안 파일 크기가 정확히 0xe1 = 225 바이트
  2. check_clues(0x1269): .data 0x4020 부터의 (열,행,값) 3바이트 엔트리 225개 중
     값이 0 이 아닌 150개에 대해 buf[열 + 15*행] == 값
  3. check_path(0x138e): 값 1 이 있는 칸에서 출발해 k = 1..224 에 대해
     값 k+1 이 현재 칸의 8방향 이웃(킹 무브)에 있어야 한다
=> 15x15 격자에 1..225 를 킹 무브로 이어지게 채우는 Hidato 퍼즐.
 
flag 는 바이너리가 `sha256sum <답안파일>` 로 계산해 출력하므로
답안 파일의 바이트 배열이 정확히 일치해야 한다.
"""
import hashlib
import sys
from pathlib import Path
 
N = 15
HERE = Path(__file__).resolve().parent
BIN = HERE / "extracted" / "main"
OUT = HERE / "answer.bin"
 
DATA_VADDR, DATA_OFF, TABLE = 0x4000, 0x3000, 0x4020
 
 
def load_clues(path=BIN):
    """바이너리 .data 에서 힌트 테이블을 직접 읽는다 (하드코딩하지 않는다)."""
    raw = path.read_bytes()
    base = TABLE - DATA_VADDR + DATA_OFF
    tbl = raw[base:base + 3 * N * N]
    grid = [[0] * N for _ in range(N)]
    for i in range(N * N):
        col, row, val = tbl[3 * i], tbl[3 * i + 1], tbl[3 * i + 2]
        if val:
            grid[row][col] = val
    return grid
 
 
NB = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if (dr, dc) != (0, 0)]
 
 
def solve(grid):
    fixed = {}                      # 값 -> (행,열)
    for r in range(N):
        for c in range(N):
            if grid[r][c]:
                fixed[grid[r][c]] = (r, c)
 
    board = [row[:] for row in grid]
    start = fixed[1]
 
    neigh = [[[] for _ in range(N)] for _ in range(N)]
    for r in range(N):
        for c in range(N):
            for dr, dc in NB:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N:
                    neigh[r][c].append((nr, nc))
 
    def reachable(r, c, k):
        """k..225 를 채울 빈 칸이 현재 위치에서 전부 닿는지 (flood fill 가지치기)."""
        need = sum(1 for rr in range(N) for cc in range(N) if board[rr][cc] == 0)
        if need == 0:
            return True
        seen = set()
        stack = [(r, c)]
        got = 0
        while stack:
            cr, cc = stack.pop()
            for nr, nc in neigh[cr][cc]:
                if (nr, nc) in seen:
                    continue
                v = board[nr][nc]
                if v == 0:
                    seen.add((nr, nc))
                    got += 1
                    stack.append((nr, nc))
                elif v > k:
                    seen.add((nr, nc))
                    stack.append((nr, nc))
        return got == need
 
    sys.setrecursionlimit(10000)
 
    def dfs(k, r, c):
        if k == N * N:
            return True
        nxt = k + 1
        if nxt in fixed:
            fr, fc = fixed[nxt]
            if max(abs(fr - r), abs(fc - c)) != 1:
                return False
            return dfs(nxt, fr, fc)
        cands = [(nr, nc) for nr, nc in neigh[r][c] if board[nr][nc] == 0]
        for nr, nc in cands:
            board[nr][nc] = nxt
            if reachable(nr, nc, nxt) and dfs(nxt, nr, nc):
                return True
            board[nr][nc] = 0
        return False
 
    if not dfs(1, *start):
        raise SystemExit("no solution")
    return board
 
 
def verify(board, clues):
    for r in range(N):
        for c in range(N):
            if clues[r][c] and board[r][c] != clues[r][c]:
                return f"힌트 불일치 ({r},{c})"
    if sorted(v for row in board for v in row) != list(range(1, N * N + 1)):
        return "1..225 순열이 아니다"
    pos = {}
    for r in range(N):
        for c in range(N):
            pos[board[r][c]] = (r, c)
    for k in range(1, N * N):
        (r1, c1), (r2, c2) = pos[k], pos[k + 1]
        if max(abs(r1 - r2), abs(c1 - c2)) != 1:
            return f"{k} -> {k+1} 이 킹 무브가 아니다"
    return None
 
 
def main():
    clues = load_clues()
    given = sum(1 for row in clues for v in row if v)
    print(f"[*] .data 0x4020 힌트 {given}개 / {N*N}칸")
 
    board = solve(clues)
    err = verify(board, clues)
    if err:
        raise SystemExit(f"[!] 검증 실패: {err}")
    print("[*] 검증 통과: 힌트 일치 + 1..225 순열 + 전 구간 킹 무브")
    print()
    for r in range(N):
        print(" ".join(f"{board[r][c]:3d}" for c in range(N)))
    print()
 
    blob = bytes(board[r][c] for r in range(N) for c in range(N))
    assert len(blob) == 0xE1
    OUT.write_bytes(blob)
    digest = hashlib.sha256(blob).hexdigest()
    print(f"[*] {OUT.name} ({len(blob)} bytes) 저장")
    print(f"[*] sha256 = {digest}")
    print(f"FLAG: DH{{{digest}}}")
 
 
if __name__ == "__main__":
    main()

python3 solve.py

#!/usr/bin/env python3
"""answer.bin 을 15x15 격자로 그려 1 -> 225 경로를 시각화한다.
 
.data 힌트로 이미 정해져 있던 칸(150개)과 우리가 채운 칸(75개)을 색으로 구분한다.
SVG 를 만든 뒤 rsvg-convert 로 PNG 로 굽는다.
"""
import subprocess
import sys
from pathlib import Path
 
from solve import N, load_clues
 
HERE = Path(__file__).resolve().parent
ANS = HERE / "answer.bin"
SVG = HERE / "hidato_path.svg"
PNG = Path(sys.argv[1]) if len(sys.argv) > 1 else HERE / "hidato_path.png"
 
CELL, PAD = 62, 34
W = H = CELL * N + PAD * 2
 
board = list(ANS.read_bytes())
clues = load_clues()
pos = {board[r * N + c]: (r, c) for r in range(N) for c in range(N)}
 
 
def cx(c):
    return PAD + c * CELL + CELL / 2
 
 
def cy(r):
    return PAD + r * CELL + CELL / 2
 
 
out = [
    f'<?xml version="1.0" encoding="UTF-8"?>',
    f'<svg xmlns="http://www.w3.org/2000/svg" width="{W}" height="{H}" viewBox="0 0 {W} {H}">',
    f'<rect width="{W}" height="{H}" fill="#0d1117"/>',
]
 
# 칸 배경: 힌트로 주어진 칸은 짙은 파랑, 우리가 채운 칸은 짙은 주황
for r in range(N):
    for c in range(N):
        given = clues[r][c] != 0
        fill = "#132033" if given else "#2a1a0d"
        stroke = "#30363d"
        out.append(f'<rect x="{PAD + c*CELL}" y="{PAD + r*CELL}" width="{CELL}" height="{CELL}" '
                   f'fill="{fill}" stroke="{stroke}" stroke-width="1"/>')
 
# 1 -> 225 경로: 진행도에 따라 파랑 -> 주황
for k in range(1, N * N):
    (r1, c1), (r2, c2) = pos[k], pos[k + 1]
    t = (k - 1) / (N * N - 2)
    red = int(0x79 + (0xF0 - 0x79) * t)
    green = int(0xC0 + (0x88 - 0xC0) * t)
    blue = int(0xFF + (0x3E - 0xFF) * t)
    out.append(f'<line x1="{cx(c1):.1f}" y1="{cy(r1):.1f}" x2="{cx(c2):.1f}" y2="{cy(r2):.1f}" '
               f'stroke="rgb({red},{green},{blue})" stroke-width="5" stroke-linecap="round" opacity="0.85"/>')
 
# 숫자
for r in range(N):
    for c in range(N):
        v = board[r * N + c]
        given = clues[r][c] != 0
        color = "#e6edf3" if given else "#f0883e"
        weight = "normal" if given else "bold"
        out.append(f'<text x="{cx(c):.1f}" y="{cy(r)+6:.1f}" font-family="DejaVu Sans Mono, monospace" '
                   f'font-size="19" fill="{color}" font-weight="{weight}" text-anchor="middle">{v}</text>')
 
# 시작·끝 표시
for v, col in ((1, "#7ee787"), (N * N, "#f97583")):
    r, c = pos[v]
    out.append(f'<circle cx="{cx(c):.1f}" cy="{cy(r):.1f}" r="26" fill="none" stroke="{col}" stroke-width="3"/>')
 
out.append("</svg>")
SVG.write_text("\n".join(out), encoding="utf-8")
subprocess.run(["rsvg-convert", "-w", str(W), "-h", str(H), str(SVG), "-o", str(PNG)], check=True)
print(f"{SVG.name} -> {PNG}  ({W}x{H})")
print(f"힌트로 주어진 칸 {sum(1 for row in clues for v in row if v)}개(흰 글씨) / "
      f"우리가 채운 칸 {sum(1 for row in clues for v in row if not v)}개(주황 글씨)")

python3 draw_path.py /home/jinho/homepage/public/images/blog/dreamhack-vernichtet-writeup/15_hidato_path.png

sha256sum answer.bin && ./extracted/main answer.bin

DH{e309147b588c517bb4100064d6185e5430ebad23d83e601327c4907bb0232292}

#!/usr/bin/env python3
"""힌트 150개로 Hidato 해가 유일한지 전수 확인.
 
flag 가 답안 파일의 sha256 이므로, 해가 둘 이상이면 flag 도 여러 개가 되어 버린다.
(실제로는 유일해야 정상) 백트래킹으로 해를 끝까지 세어 본다.
"""
import sys
from solve import N, NB, load_clues
 
 
def count(grid, limit=5):
    fixed = {}
    for r in range(N):
        for c in range(N):
            if grid[r][c]:
                fixed[grid[r][c]] = (r, c)
    board = [row[:] for row in grid]
    neigh = [[[(r + dr, c + dc) for dr, dc in NB
               if 0 <= r + dr < N and 0 <= c + dc < N] for c in range(N)] for r in range(N)]
    found = 0
    nodes = 0
 
    def reachable(r, c, k):
        need = sum(1 for rr in range(N) for cc in range(N) if board[rr][cc] == 0)
        if need == 0:
            return True
        seen, stack, got = set(), [(r, c)], 0
        while stack:
            cr, cc = stack.pop()
            for nr, nc in neigh[cr][cc]:
                if (nr, nc) in seen:
                    continue
                v = board[nr][nc]
                if v == 0:
                    seen.add((nr, nc)); got += 1; stack.append((nr, nc))
                elif v > k:
                    seen.add((nr, nc)); stack.append((nr, nc))
        return got == need
 
    def dfs(k, r, c):
        nonlocal found, nodes
        nodes += 1
        if k == N * N:
            found += 1
            return found >= limit
        nxt = k + 1
        if nxt in fixed:
            fr, fc = fixed[nxt]
            if max(abs(fr - r), abs(fc - c)) != 1:
                return False
            return dfs(nxt, fr, fc)
        for nr, nc in neigh[r][c]:
            if board[nr][nc]:
                continue
            board[nr][nc] = nxt
            if reachable(nr, nc, nxt) and dfs(nxt, nr, nc):
                board[nr][nc] = 0
                return True
            board[nr][nc] = 0
        return False
 
    sys.setrecursionlimit(10000)
    dfs(1, *fixed[1])
    return found, nodes
 
 
if __name__ == "__main__":
    n, nodes = count(load_clues())
    print(f"탐색 노드 {nodes}개, 완성해 {n}개")
    print("=> 해가 유일하다" if n == 1 else "=> 해가 여러 개다(!)")

python3 count_solutions.py

#!/usr/bin/env bash
# Vernichtet (DreamHack Gold 4 / reversing) — 한 방 재현.
#   anti-disassembly 스텁 제거 -> 힌트 테이블 파싱 -> Hidato 풀이 -> 답안 파일 -> flag 대조
# 필요한 것: python3, objdump(선택), 문제 배포본 extracted/main
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null || echo '')
 
[ -f extracted/main ] || { echo "❌ extracted/main 이 없다 (challenge_2343.zip 을 풀어라)"; exit 1; }
chmod +x extracted/main
 
# 1) 안티디스어셈블리 스텁 97개를 NOP 으로 덮은 사본 (분석용, 풀이에는 없어도 된다)
python3 deobf.py
 
# 2) 힌트 테이블(.data 0x4020) 파싱 + Hidato 풀이 + answer.bin 생성
OUT=$(timeout 300 python3 solve.py 2>&1) || true
echo "$OUT" | tail -12
 
FLAG=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
 
# 3) 문제 바이너리로 직접 재확인 — Correct! 와 flag 를 바이너리가 스스로 출력한다
echo
echo "--- ./extracted/main answer.bin ---"
BINOUT=$(./extracted/main answer.bin 2>&1 || true)
echo "$BINOUT"
BINFLAG=$(printf '%s' "$BINOUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
 
echo
if [ -z "$FLAG" ] || [ "$FLAG" != "$BINFLAG" ]; then
  echo "❌ FAIL  solve.py='$FLAG' / binary='$BINFLAG'"; exit 1
fi
if [ -n "$EXPECT" ] && [ "$FLAG" != "$EXPECT" ]; then
  echo "❌ FAIL  기대 '$EXPECT' / 얻은 값 '$FLAG'"; exit 1
fi
echo "✅ PASS  $FLAG"

sprintf(cmd, "bash -c \"echo DH{$(sha256sum '%s' | awk '{print $1}')}\"", argv[1]);
system(cmd);

ls injtest/ && ./extracted/main "injtest/x'; id -un; echo '"