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

2026-08-07·1분 읽기·

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

.text 는 1.5KB 인데 .data 가 15KB 다. 그 데이터가 25×25×25 격자였고, 입력 문자 여섯 개는 ±x ±y ±z 여섯 방향이었다. 지나온 칸이 벽으로 바뀌어 자기 몸을 밟을 수 없는 3D 뱀 미로 — 통로 107칸이 통째로 외길이라 답은 하나뿐이다.

문제: 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"
file 과 readelf 로 본 chall — non-PIE stripped x86-64 이고 text 는 0x60c 바이트인데 data 가 0x3d29 바이트라 코드보다 데이터가 열 배 크다
file 과 readelf 로 본 chall — non-PIE stripped x86-64 이고 text 는 0x60c 바이트인데 data 가 0x3d29 바이트라 코드보다 데이터가 열 배 크다

.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"
nm 으로 본 임포트와 주요 문자열 — scanf puts setvbuf 세 개뿐이고 포맷 문자열은 %255s 이며 출력은 good 과 wrong 두 가지다
nm 으로 본 임포트와 주요 문자열 — scanf puts setvbuf 세 개뿐이고 포맷 문자열은 %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 이 그 자리였다.

아래에서는 읽어낸 이름으로 부르겠다. 실제 바이너리에는 주소밖에 없다.

주소붙인 이름하는 일
0x401196mark(x,y,z)격자의 그 칸을 1 로 만든다
0x4011ebcan_move(x,y,z)범위 안이고 값이 1 이 아니면 1 을 돌려준다
0x40127acheck_chars(s)입력이 허용된 글자로만 되어 있는지 본다
0x401348check(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"
objdump 로 뽑은 문자 검사 부분의 판정 줄 — 0x4b 0x39 0x7a 0x37 0x32 0x73 여섯 값과만 비교하고 NUL 을 만나면 통과, 최대 256글자까지 본다
objdump 로 뽑은 문자 검사 부분의 판정 줄 — 0x4b 0x39 0x7a 0x37 0x32 0x73 여섯 값과만 비교하고 NUL 을 만나면 통과, 최대 256글자까지 본다

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
objdump 로 뽑은 can_move 함수 — 세 좌표를 모두 0 이상 24 이하로 검사한 뒤 x + 25y + 625z 로 오프셋을 만들어 0x404060 에서 읽고 값이 1 이면 실패를 돌려준다
objdump 로 뽑은 can_move 함수 — 세 좌표를 모두 0 이상 24 이하로 검사한 뒤 x + 25y + 625z 로 오프셋을 만들어 0x404060 에서 읽고 값이 1 이면 실패를 돌려준다

컴파일러가 곱셈을 시프트와 덧셈으로 쪼개 놔서 처음엔 눈에 안 들어온다. 순서대로 따라가면 이렇다.

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

25 = 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
objdump 로 뽑은 이동 분기 — 시작 좌표를 24,12,12 로 두고 K 9 z 7 2 s 여섯 글자를 각각 x y z 의 증감으로 연결하는 점프 테이블 형태의 비교 사슬이 보인다
objdump 로 뽑은 이동 분기 — 시작 좌표를 24,12,12 로 두고 K 9 z 7 2 s 여섯 글자를 각각 x y z 의 증감으로 연결하는 점프 테이블 형태의 비교 사슬이 보인다
글자이동
Kx + 1
9x − 1
zy + 1
7y − 1
2z + 1
sz − 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
objdump 로 뽑은 한 걸음 처리 순서 — 좌표를 옮긴 뒤 먼저 0,12,12 도달을 확인하고 그다음에 이동 가능 여부를 보며 마지막에 그 칸을 1 로 칠한다
objdump 로 뽑은 한 걸음 처리 순서 — 좌표를 옮긴 뒤 먼저 0,12,12 도달을 확인하고 그다음에 이동 가능 여부를 보며 마지막에 그 칸을 1 로 칠한다

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
 
quit
printf 'zzzzzz222222277779999zzzzzzzssssssss999777777777222222222222zzzzz999zzz999777ssss99999999999777777sssssssz\n' | gdb -q -batch -x runtime_check.gdb extracted/chall
gdb 배치 실행 결과 — 시작 좌표가 24,12,12 로 확인되고 첫 글자 z 에 따라 y 가 13 으로 늘며, 지나온 칸의 값이 1 로 바뀌고 실행 중 메모리에서 통로 칸이 105개로 세어진다
gdb 배치 실행 결과 — 시작 좌표가 24,12,12 로 확인되고 첫 글자 z 에 따라 y 가 13 으로 늘며, 지나온 칸의 값이 1 로 바뀌고 실행 중 메모리에서 통로 칸이 105개로 세어진다

[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
격자 구조 분석 출력 — 통로 107칸 중 이웃이 1개인 끝점이 2개, 이웃이 2개인 외길이 105개이고 갈림길은 0개이며 끝점 두 곳이 시작과 목표와 정확히 일치한다
격자 구조 분석 출력 — 통로 107칸 중 이웃이 1개인 끝점이 2개, 이웃이 2개인 외길이 105개이고 갈림길은 0개이며 끝점 두 곳이 시작과 목표와 정확히 일치한다

읽을 것이 세 가지다.

갈림길이 0개다. 통로 107칸이 전부 이웃 2개(끝점만 1개)라 분기가 없다. 하나로 이어진 관이다.

끝점 두 곳이 시작과 목표와 정확히 일치한다. 즉 이 관의 양 끝이 문제의 출발점과 도착점이다.

BFS 경로가 통로 전체와 같다. 106걸음이 밟는 107칸이 열린 칸 전부다. 곁가지도, 막다른 길도 없다.

그래서 답이 하나뿐이다. 문제 페이지의 "정답이 여러 개였던 것을 수정했다"는 기록과 맞아떨어진다.

눈으로도 확인해 두려고 격자를 z 판별로 펼쳐 그렸다. 손으로 그린 도식이 아니라 추출한 데이터를 그대로 렌더한 것이다.

격자를 z 판별로 펼친 그림 — 통로 107칸이 z 11 부터 23 까지 흩어져 있고 전부 정답 경로 색으로 칠해져 있어 경로 밖 통로가 하나도 없다는 게 눈으로 보인다
격자를 z 판별로 펼친 그림 — 통로 107칸이 z 11 부터 23 까지 흩어져 있고 전부 정답 경로 색으로 칠해져 있어 경로 밖 통로가 하나도 없다는 게 눈으로 보인다

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
solve.py 실행 결과 — 통로 107칸을 확인하고 106걸음 경로를 찾은 뒤 자체 검증을 통과하며 단순경로 완전탐색 결과가 1개로 나와 플래그가 출력된다
solve.py 실행 결과 — 통로 107칸을 확인하고 106걸음 경로를 찾은 뒤 자체 검증을 통과하며 단순경로 완전탐색 결과가 1개로 나와 플래그가 출력된다

--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
verify.py 실행 결과 — 정답 경로만 good 이 나오고 마지막 글자를 바꾸거나 한 걸음 짧게 하거나 역순으로 넣은 세 대조군은 모두 wrong 이 나온다
verify.py 실행 결과 — 정답 경로만 good 이 나오고 마지막 글자를 바꾸거나 한 걸음 짧게 하거나 역순으로 넣은 세 대조군은 모두 wrong 이 나온다

정답만 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

댓글

0개

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

댓글 불러오는 중…

Related

관련 글

3개
[🥉 Bronze 3] 미로를 풀지 않고 미로를 깨다 — DreamHack Tiny Maze 풀이
blog

[🥉 Bronze 3] 미로를 풀지 않고 미로를 깨다 — DreamHack Tiny Maze 풀이

WASD로 미로를 움직여 goal에 닿으면 플래그를 찍어 주는 작은 리버싱 문제다. 미로를 실제로 풀 수도 있지만, 플래그는 이미 바이너리 안에 encoded_flag로 들어 있고 print_flag가 그걸 0x5a로 XOR해 출력할 뿐이다. 그래서 .rodata에서 바이트를 꺼내 한 줄로 복원했고, 재미 삼아 미로도 BFS로 풀었다. 이때 move_from_key의 점프 테이블을 읽어 보면 WASD 키가 회전돼 있다는 함정이 드러난다.
#dreamhack#ctf#reversing+4
2026-10-08#dreamhack +5
[🥉 Bronze 2] 분기 미로 뒤에 숨은 상수 한 줄 — DreamHack Labyrinth 풀이
blog

[🥉 Bronze 2] 분기 미로 뒤에 숨은 상수 한 줄 — DreamHack Labyrinth 풀이

14KB 짜리 stripped PIE 하나가 전부인 리버싱 문제. ptrace 안티디버깅과 시드 %7 로 갈라지는 분기 미로가 겹겹이 깔려 있지만, 정답 입력은 .rodata 의 32바이트를 0x30 으로 XOR 한 것이 전부였다. flag 생성기까지 파이썬으로 재구현해 바이너리 출력과 바이트 단위로 대조했다.
#dreamhack#ctf#reversing+6
2026-08-20#dreamhack +5
[🥈 Bronze 2] 미끼인 줄 알았던 디코드가 사실 정답이었다 — DreamHack 아 문제 이름 뭘로하지 풀이
blog

[🥈 Bronze 2] 미끼인 줄 알았던 디코드가 사실 정답이었다 — DreamHack 아 문제 이름 뭘로하지 풀이

39바이트 암호문을 XOR 0xAA로 풀면 그럴듯한 DH{} 문자열이 바로 나온다. 너무 쉬워서 미끼라고 판단하고, 사용자 입력을 변형하는 복잡한 커스텀 인코딩 함수를 통째로 역산했다. GDB로 대조하다 32비트 시프트 카운트 마스킹 때문에 특정 자리가 항상 0이 되는 버그를 발견했고, 그 버그를 쫓아가다 결국 처음 봤던 그 디코드 문자열이 진짜 정답이었다는 걸 알게 됐다.
#dreamhack#ctf#reversing+4
2026-07-19#dreamhack +5