문제: DreamHack — Snaky 분류: reversing 난이도: 🥇 Gold 4 FLAG:
DH{zzzzzz222222277779999zzzzzzzssssssss999777777777222222222222zzzzz999zzz999777ssss99999999999777777sssssssz}
문제 설명은 흔한 형태다.
x64 리눅스 환경에서 실행할 수 있는 ELF 파일이 첨부파일로 주어집니다. 해당 ELF 파일은 이용자로부터 문자열을 입력받아 검증을 수행한 후 정답이면
good :)을, 틀리면wrong :(을 출력하는 프로그램입니다. 정답이 되는 문자열이 플래그이며, 플래그 형식은DH{...}입니다.
문제 페이지에 업데이트 기록이 하나 붙어 있다.
2025.03.05:
good :)을 출력하는 입력 값이 여러 개였던 문제를 수정하였습니다.
이 한 줄이 나중에 풀이가 맞았다는 확인이 된다. 답이 정확히 하나여야 한다는 뜻이니까.
문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | Snaky (id 1774) |
| 난이도 | 🥇 Gold 4 |
| 분류 | reversing |
| 제공 파일 | chall (ELF 64-bit, non-PIE, stripped, 30,184바이트) |
| 임포트 | __isoc99_scanf · puts · setvbuf — 그게 전부다 |
| 핵심 | .data 에 숨은 25×25×25 3D 미로 + 자기 몸을 밟을 수 없는 제약 |
| 답 | 106걸음, 단순경로 정확히 1개 |
풀이는 섹션 크기를 본 순간 방향이 잡혔다. 로직은 1.5KB 인데 데이터가 15KB 다. 답이 코드가 아니라 데이터에 있다는 뜻이다.
그다음은 그 데이터가 어떤 모양인지 알아내는 일이었고, 인덱스 계산식 하나가 그걸 다 말해 줬다.
🔬 정찰 — 섹션 크기가 먼저 말한다
file extracted/chall; readelf -SW extracted/chall | grep -E "\.text|\.rodata|\.data|\.bss"
.text 가 0x60c = 1,548바이트. .data 가 0x3d29 = 15,657바이트.
리버싱 문제에서 이 비율은 강한 신호다. 검증 로직이 1.5KB 안에 들어간다면 복잡한 암호 루틴은 아니고, 대신 15KB짜리 표를 참조한다는 뜻이다.
non-PIE 라는 것도 반갑다. 주소가 실행마다 고정이라 나중에 gdb 로 확인할 때 0x404060 같은 값을 그대로 쓸 수 있다.
임포트가 세 개뿐이다
nm -D extracted/chall; strings -a extracted/chall | grep -E "%255s|good|wrong"
scanf("%255s", buf) 로 한 줄 받고, puts 로 둘 중 하나를 찍는다. 암호 라이브러리도 파일 입출력도 없다.
그러니까 이 프로그램은 입력 문자열 하나를 표와 대조하는 것이 전부다.
🧩 배경 — stripped 바이너리를 읽는 순서
심볼이 없으니 함수 이름이 하나도 없다. 그래도 순서를 정해 두면 헤맬 일이 적다.
엔트리에서 main 을 찾는다. _start 가 __libc_start_main 에 넘기는 첫 인자가 main 이다. 여기서는 mov rdi,0x4016a3 이라 main 은 0x4016a3.
호출 그래프를 위에서 아래로 훑는다. main → 0x401482(진짜 로직) → 0x401348(검증) → 그 아래로 0x40127a, 0x4011eb, 0x401196.
리프 함수부터 이름을 붙인다. 가장 작은 함수가 대개 가장 단순하고, 거기서 자료구조가 드러난다. 이 문제에서는 0x401196 과 0x4011eb 이 그 자리였다.
아래에서는 읽어낸 이름으로 부르겠다. 실제 바이너리에는 주소밖에 없다.
| 주소 | 붙인 이름 | 하는 일 |
|---|---|---|
0x401196 | mark(x,y,z) | 격자의 그 칸을 1 로 만든다 |
0x4011eb | can_move(x,y,z) | 범위 안이고 값이 1 이 아니면 1 을 돌려준다 |
0x40127a | check_chars(s) | 입력이 허용된 글자로만 되어 있는지 본다 |
0x401348 | check(s) | 실제 검증 — 아래에서 자세히 |
💣 핵심 — 격자, 여섯 방향, 그리고 뱀
입력에 쓸 수 있는 글자는 여섯 개다
check_chars 는 문자 하나를 여섯 값과 차례로 비교한다. 같은 패턴이 여섯 번 반복되니 판정 줄만 뽑아 본다.
# 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"
0x4b 0x39 0x7a 0x37 0x32 0x73 → K 9 z 7 2 s. 여섯 개다.
플래그 알파벳이 여섯 글자로 제한된다는 건 그 자체로 의미가 있다. 임의의 문자열을 맞히는 게 아니라 여섯 가지 중 하나를 고르는 선택을 반복하는 문제라는 뜻이다.
인덱스 계산식이 자료구조를 드러낸다
can_move 를 보면 범위 검사와 주소 계산이 한자리에 있다.
# 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 + rdx25 = 5², 625 = 25². 그리고 범위 검사가 세 좌표 모두 0..24.
25×25×25 = 15,625바이트 3차원 배열이다. .data 크기 15,657 에서 앞의 32바이트를 빼면 정확히 15,625다. 딱 맞는다.
값이 1 이면 못 가는 칸. 0 이면 통로.
여섯 글자가 여섯 방향이다
check 의 이동 처리 부분을 본다.
# 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
| 글자 | 이동 |
|---|---|
K | x + 1 |
9 | x − 1 |
z | y + 1 |
7 | y − 1 |
2 | z + 1 |
s | z − 1 |
시작은 (24, 12, 12), 즉 큐브의 한쪽 면 한가운데다.
순서가 중요하다 — 목표 판정이 이동 가능 판정보다 먼저
한 걸음마다 하는 일의 순서가 이 문제의 마지막 조각이다.
objdump -d -M intel --no-show-raw-insn --start-address=0x40140f --stop-address=0x401460 extracted/chall | sed -f annot_walk.sed
C 로 옮기면 이렇다.
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;
}세 줄의 순서가 각각 뜻이 있다.
①이 ②보다 먼저라서 목표 칸은 벽이어도 상관없다. 도착 판정이 이동 가능 판정을 앞지른다.
③ 때문에 지나온 칸이 벽이 된다. 되돌아갈 수도, 자기 경로와 교차할 수도 없다. 뱀이 자기 몸을 먹으면 죽는 것과 같다. 문제 이름이 여기서 나왔다.
그러니 답은 단순경로여야 한다. 같은 칸을 두 번 밟는 순간 실패다.
🐛 삽질
▶🕳️ 삽질 1 — 15,657 과 15,625 의 32바이트 차이
인덱스 계산식에서 25×25×25 = 15,625 를 읽고 나서 .data 크기와 맞춰 봤는데 15,657 이었다. 32바이트가 남는다.
계산식을 잘못 읽었나 싶어 시프트 순서를 두 번 다시 따라갔다. 답은 더 단순했다 — 격자가 .data 의 시작이 아니었다.
readelf -SW extracted/chall | grep '\.data'.data 는 가상주소 0x404040 에서 시작하는데, 디스어셈블이 가리키는 격자는 0x404060 이다. 차이가 정확히 0x20 = 32바이트. 앞의 32바이트는 다른 전역 변수 자리다.
그래서 파일에서 격자를 뜰 때 오프셋을 이렇게 잡아야 한다.
GRID_VA, DATA_VA, DATA_OFF = 0x404060, 0x404040, 0x3040
off = DATA_OFF + (GRID_VA - DATA_VA) # 0x3060섹션 크기가 딱 맞지 않는다고 해석이 틀린 게 아니다. 섹션은 여러 변수를 담는 그릇이고, 우리가 찾는 배열은 그 안의 한 조각일 뿐이다. 차이가 32처럼 작고 깔끔한 값이면 오히려 "다른 전역이 앞에 있다"는 신호로 읽는 게 맞다.
▶🕳️ 삽질 2 — sed 주석이 엉뚱한 줄에 붙었다
디스어셈블에 <-- 주석을 얹으려고 sed 스크립트를 썼는데, 처음 것은 세 줄이 아예 안 붙고 한 줄은 잘못된 곳에 세 번 붙었다.
원인이 둘이었다.
첫째, BRE 에서 \+ 는 리터럴 플러스가 아니다. GNU sed 의 기본 정규식에서 \+ 는 "하나 이상"이라는 수량자다. 그래서 이런 패턴이 아무것도 못 잡았다.
s|lea rdx,\[rax\*4\+0x0\]|& <-- rdx = 20y|[+] 처럼 문자 클래스로 감싸면 리터럴이 된다.
둘째, 같은 명령이 여러 번 나온다. add rax,rdx 가 한 함수 안에 세 번 있는데(5y 만들 때, 25y 만들 때, 격자 주소 더할 때) 명령만으로 패턴을 쓰면 셋 다 같은 주석을 달아 버린다. 실제로 "rax = 5y" 가 세 군데에 찍혔다.
주소로 줄을 지정하니 둘 다 해결됐다.
s|^ 401246:.*|& <-- rax = 5y|
s|^ 401251:.*|& <-- rax = 25y|
s|^ 401262:.*|& <-- rax = 격자 + 오프셋|주석을 단 뒤에는 grep '<--' 로 몇 줄에 붙었는지 세어 본다. 의도한 개수와 다르면 패턴이 틀린 것이다. 주석이 틀린 자리에 붙은 캡쳐는 글을 읽는 사람을 잘못된 방향으로 끌고 간다.
🧪 런타임으로 확인
정적 분석은 여기까지고, 읽은 게 맞는지 실행 중에 확인한다. non-PIE 라 주소를 그대로 쓸 수 있어 배치 스크립트 하나면 된다.
# 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
quitprintf 'zzzzzz222222277779999zzzzzzzssssssss999777777777222222222222zzzzz999zzz999777ssss99999999999777777sssssssz\n' | gdb -q -batch -x runtime_check.gdb extracted/chall
[1] 시작 좌표가 (24,12,12) 로 확인된다. [2] 첫 글자 z 에 y 가 12 → 13 으로 늘었다. [3] 방금 지나온 칸의 값이 1 로 바뀌어 있다. 몸통이 남는다는 게 실행 중에도 그대로다.
[4] 는 격자를 메모리에서 직접 훑은 것이다. 값이 0 인 칸이 105개. 이때 이미 두 칸(시작과 첫 걸음)을 칠했으니 원래는 107칸이다.
15,625칸 중 통로가 107칸뿐이라는 게 여기서 처음 드러난다.
🎯 격자를 꺼내 보니 외길이었다
파일에서 격자를 그대로 떠 와 구조를 본다. .data 는 파일 오프셋 0x3040, 가상주소 0x404040 이므로 격자(0x404060)는 파일에서 0x3060 이다.
통로 칸마다 이웃한 통로가 몇 개인지 세면 미로의 성질이 한 번에 나온다. 1이면 끝점, 2면 외길 중간, 3 이상이면 갈림길이다.
#!/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
읽을 것이 세 가지다.
갈림길이 0개다. 통로 107칸이 전부 이웃 2개(끝점만 1개)라 분기가 없다. 하나로 이어진 관이다.
끝점 두 곳이 시작과 목표와 정확히 일치한다. 즉 이 관의 양 끝이 문제의 출발점과 도착점이다.
BFS 경로가 통로 전체와 같다. 106걸음이 밟는 107칸이 열린 칸 전부다. 곁가지도, 막다른 길도 없다.
그래서 답이 하나뿐이다. 문제 페이지의 "정답이 여러 개였던 것을 수정했다"는 기록과 맞아떨어진다.
눈으로도 확인해 두려고 격자를 z 판별로 펼쳐 그렸다. 손으로 그린 도식이 아니라 추출한 데이터를 그대로 렌더한 것이다.

z 판을 오가며 이어지는 게 보인다. 판 하나에 점 하나만 찍힌 z 들(1318, 2022)은 경로가 그 층을 관통해 지나가기만 하는 구간이다.
🚀 Full Exploit
BFS 로 최단경로를 찾는다. 뱀 제약("같은 칸을 두 번 밟으면 실패")은 따로 처리할 필요가 없다 — BFS 가 찾는 최단경로는 애초에 같은 칸을 두 번 지나지 않기 때문이다.
목표 판정이 이동 가능 판정보다 먼저라는 점만 코드에 반영하면 된다.
#!/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
--count-paths 는 DFS 로 단순경로를 전부 세는 옵션이다. 통로가 107칸뿐이라 완전탐색이 순식간에 끝난다. 결과는 1개 — 구조 분석과 일치한다.
실제 바이너리로 확인
계산이 맞아도 프로그램이 good :) 을 뱉는지는 별개다. 대조군을 같이 넣어 돌린다.
#!/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
정답만 good :), 나머지 셋은 전부 wrong :(.
역순이 실패하는 게 재밌다. 통로는 대칭인데 시작과 목표가 정해져 있으니 방향을 뒤집으면 첫 걸음부터 벽이다.
DH{zzzzzz222222277779999zzzzzzzssssssss999777777777222222222222zzzzz999zzz999777ssss99999999999777777sssssssz}🧪 재현
reproduce.sh 하나로 격자 추출부터 실제 바이너리 확인까지 돈다. 외부 서버가 필요 없는 오프라인 문제라 인자도 없다.
./reproduce.sh필요한 건 python3, objdump, 그리고 x86-64 리눅스뿐이다. 바이너리가 동적 링크라 glibc 가 있으면 그대로 돈다.
판정은 이렇게 읽는다.
| 화면 | 뜻 | 대처 |
|---|---|---|
격자를 못 읽었다 | 파일 오프셋이 안 맞음 | readelf -SW 로 .data 오프셋을 다시 확인 |
통로 107 칸 이 아님 | 다른 버전의 배포본 | 2025.03.05 이후 배포본인지 확인 |
단순경로 개수 : 5개 이상 | 미로에 갈림길이 생김 | 위와 같음 — 옛 배포본일 가능성 |
자체 검증 : 실패 | 이동표나 순서 해석이 틀림 | simulate() 를 디스어셈블과 다시 대조 |
wrong :( | 바이너리에 실행 권한이 없거나 다른 파일 | chmod +x extracted/chall |
마지막 줄은 실제로 밟았다. 배포 zip 이 실행 비트를 보존하지 않아서 chmod 없이는 아예 실행이 안 된다.
📝 결론
섹션 크기는 공짜로 얻는 단서다.
readelf -S 한 번이면 로직형인지 데이터형인지 갈린다. .text 가 작고 .data 가 크면 답은 표 안에 있고, 할 일은 그 표의 모양을 알아내는 것이다. 이 문제는 그 판단만으로 방향이 잡혔다.
곱셈 상수가 자료구조를 말한다.
imul rsi,rax,0x271 에서 625 를, 그 위에서 25 를 읽는 순간 3차원 배열이 확정된다. 컴파일러가 곱셈을 시프트와 덧셈으로 쪼개 놔서 한눈에 안 보일 뿐이다. 상수를 인수분해해 보는 습관이 여기서 값을 한다.
연산 순서까지 읽어야 정확한 모델이 된다.
목표 판정이 이동 가능 판정보다 먼저 오는 것, 그리고 칠하기가 맨 마지막인 것 — 둘 중 하나만 잘못 옮겨도 시뮬레이터가 원본과 어긋난다. 디스어셈블에서 분기의 위치는 조건 자체만큼 중요하다.
푼 뒤에 구조를 한 번 더 확인하면 답이 맞았다는 걸 스스로 알 수 있다.
경로를 찾고 끝낼 수도 있었지만, 통로의 차수 분포를 세 보니 갈림길이 0개였다. 그래서 답이 하나뿐이라는 게 탐색 결과가 아니라 구조로 설명된다. 문제 페이지의 수정 기록과도 맞물린다. 이런 확인은 몇 줄이면 되고, 틀린 답을 붙들고 있는 시간을 줄여 준다.
방어 쪽에서 보면, 검증 로직을 데이터 표로 옮기는 건 난독화가 아니다. 표가 크면 오히려 눈에 띄고, 인덱스 계산식 한 줄이 구조를 통째로 알려 준다. 값을 지키고 싶으면 표를 숨길 게 아니라 애초에 클라이언트에 두지 않아야 한다.
Comments
댓글
댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)
댓글 불러오는 중…