문제: DreamHack — Control-Flow: mirage 분류: Reversing 난이도: ⭐ Level 1 FLAG:
DH{0p4qu3_pr3d_1s_4_l13_4_y0u!!}
문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | Control-Flow: mirage |
| 난이도 | ⭐ Level 1 |
| 분류 | Reverse Engineering |
| 제공 파일 | ELF 64-bit 바이너리 (mirage) |
| 핵심 기법 | Dispatch Table 기반 State Machine + Opaque Predicate |
| 힌트 | "The switch still works, but not every branch tells the truth." |
제목 그대로 "신기루"다.
흐름을 따라가면 따라갈수록 진짜 로직이 어디 있는지 헷갈리게 설계되어 있다. 근데 결국 state machine을 처음부터 끝까지 추적하고 나면 변환 로직은 단순하다.
풀이 흐름:
- 바이너리 기본 분석 → 보호 기법, 심볼, import 확인
check함수 구조 파악 → dispatch table 추출- 전체 44개 상태 추적 → 변환 순서 확정
- opaque predicate 식별
- 역산 코드 작성 → 플래그 획득
🔬 바이너리 기본 분석
Step 1 — 파일 형식 및 보호 기법
먼저 파일 형식과 ELF 타입을 확인한다.
file mirage
readelf -h mirage | grep Type
| 항목 | 상태 |
|---|---|
| PIE | ❌ 없음 (EXEC 타입, 고정 주소 0x401110) |
| Stack Canary | ❌ 없음 (__stack_chk_fail import 없음) |
| Stripped | ❌ not stripped (check, main 심볼 노출) |
| 의존 라이브러리 | libc.so.6 |
PIE도 없고 심볼도 살아있다. 정적 분석에 최적화된 환경이다.
Step 2 — 심볼 및 import 확인
다음으로 심볼과 import를 확인한다.
nm mirage
objdump -d --section=.plt mirage | grep '@plt'
심볼이 두 개뿐이다. main과 check.
import는 fgets, nanosleep, puts, strlen, strcspn, malloc, printf. nanosleep이 눈에 띈다 — 동적 분석 방해용이다.
Step 3 — 실행 및 주요 문자열 확인
어떤 입력을 받고 무슨 메시지를 출력하는지 먼저 확인한다.
strings -a mirage | grep -E "Flag|Correct|Wrong"
./mirage # 아무 문자열 입력해보기
Flag: 프롬프트가 뜨고 입력을 받아서 Correct! 또는 Wrong.을 출력한다. 전형적인 crackme 구조.
main의 핵심 흐름만 요약하면:
// main (0x401695) 의사코드
int main() {
// 전역 변수 초기화
// PRNG 시드 = 0x48f3b59043397068
// malloc으로 연결 리스트 구조체 3개 생성
printf("Flag: ");
fgets(buf, 0x40, stdin);
buf[strcspn(buf, "\n")] = '\0'; // 개행 제거
int result = check(buf);
puts(result ? "Correct!" : "Wrong.");
}main 뒤에 또 다른 함수(0x4019f8)가 존재하는데, fini_array에 등록되어 프로세스 종료 시 자동 실행된다.
내부는 nanosleep + LCG PRNG 반복 루프 — 동적 분석 타이밍 교란용이다. 무시해도 된다.
🔬 check 함수 분석
Step 1 — 함수 진입부 확인
check 함수 시작 지점부터 본다. -M intel로 Intel 문법으로 출력한다.
objdump -d -M intel mirage | grep -A 20 '<check>:'
진입 직후 핵심 두 줄:
401202: mov [rbp-0x78], rdi ; 입력 포인터 저장
401206: movq $0x14, [rbp-0x28] ; state = 20 (초기값)rbp-0x28에 상태값 0x14(=20)를 세팅하고 바로 dispatch loop로 진입한다.
Step 2 — Dispatch Loop 확인
dispatch loop 전체를 본다.
objdump -d -M intel mirage | grep -A 35 '<check>:'
40120e: cmp qword [rbp-0x28], 0x2b ; state > 43?
401213: ja 40167b ; 범위 초과 → 루프백
401219: mov rax, [rbp-0x28] ; state
40121d: lea rdx, [rax*4]
401225: lea rax, [rip+0xdd8] ; = 0x402004 (jump table)
40122c: mov eax, [rdx+rax] ; 테이블에서 오프셋 로드
40122f: cltq
401231: lea rdx, [rip+0xdcc] ; = 0x402004
401238: add rax, rdx ; 절대 주소 계산
40123b: notrack jmp rax ; 상태 분기전형적인 switch-case → dispatch table 패턴이다.
[rbp-0x28]이 상태 변수, 0x402004가 jump table. 상태는 0x000x2b (043), 총 44개.
notrack이 붙어있어 CFI 분석 도구를 방해한다.
Step 3 — Jump Table 추출
0x402004에 있는 jump table을 Python으로 직접 파싱해 상태별 점프 주소를 뽑는다.
import struct
with open("mirage", "rb") as f:
data = f.read()
# ELF PT_LOAD 세그먼트 파싱 → 가상주소-파일오프셋 매핑
e_phoff = struct.unpack_from("<Q", data, 32)[0]
e_phnum = struct.unpack_from("<H", data, 56)[0]
segments = []
for i in range(e_phnum):
off = e_phoff + i * 56
if struct.unpack_from("<I", data, off)[0] == 1: # PT_LOAD
p_vaddr = struct.unpack_from("<Q", data, off+16)[0]
p_filesz = struct.unpack_from("<Q", data, off+32)[0]
p_offset = struct.unpack_from("<Q", data, off+8)[0]
segments.append((p_vaddr, p_vaddr + p_filesz, p_offset))
def vaddr_to_file(va):
for (s, e, o) in segments:
if s <= va < e:
return o + (va - s)
jt_foff = vaddr_to_file(0x402004)
for state in range(0x2c):
rel = struct.unpack_from("<i", data, jt_foff + state * 4)[0]
target = 0x402004 + rel
print(f"State 0x{state:02x} ({state:2d}) -> 0x{target:06x}")python3 parse_jumptable.py
| 상태 | 주소 | 상태 | 주소 |
|---|---|---|---|
| 0x00 | 0x4014d5 | 0x0f | 0x40159b |
| 0x02 | 0x40135a | 0x10 | 0x40140b |
| 0x03 | 0x4013ad | 0x11 | 0x401349 |
| 0x05 | 0x4014a3 | 0x13 | 0x401626 |
| 0x06 | 0x4014f5 | 0x14 | 0x4012fd |
| 0x07 | 0x401615 | 0x18 | 0x40137a |
| 0x09 | 0x40152c | 0x1b | 0x40162d |
| 0x0a | 0x401572 | 0x1d | 0x401650 |
| 0x0b | 0x4015c5 | 0x22 | 0x40123e |
| 0x0c | 0x40131a | 0x25 | 0x40141f |
| 0x01,0x04,0x0e... | 0x40167b (루프백) | 0x2a | 0x40166a |
| 0x0d | 0x4015bb | 0x2b | 0x4013e0 |
0x40167b는 nop; jmp 0x40120e — 즉 루프백. 여기로 점프하는 상태는 전부 실질적으로 죽은 상태다.
🗺️ 전체 상태 추적
로컬 변수 맵을 먼저 정리하면 이후 분석이 훨씬 편하다.
각 오프셋은 objdump 출력에서 [rbp-0xNN] 형태로 반복 등장하므로 패턴을 잡아두면 된다.
objdump -d -M intel mirage | grep -A 600 '<check>:' | grep 'rbp'| 오프셋 | 변수 | 역할 |
|---|---|---|
| rbp-0x78 | input | 입력 문자열 포인터 |
| rbp-0x28 | state | 현재 상태 |
| rbp-0x08 | len | strlen(input) 결과 |
| rbp-0x70 | working_buf | 변환 버퍼 (28바이트) |
| rbp-0x50 | target_buf | 정답 바이트 (28바이트) |
| rbp-0x10 | i | XOR 루프 카운터 |
| rbp-0x0c | j | 복사 루프 카운터 |
| rbp-0x14 | k | mul17 루프 카운터 |
| rbp-0x18 | m | XOR-neighbor 카운터 |
| rbp-0x1c | n | 비교 루프 카운터 |
각 상태 주소를 jump table에서 확인한 뒤 해당 주소를 objdump 출력에서 찾아가며 추적한다.
# 특정 주소 주변 코드 확인 예시 (state 0x14 = 0x4012fd)
objdump -d -M intel mirage | grep -A 10 '4012fd:'
상태를 처음부터 끝까지 따라가면 아래 흐름이 나온다:
[0x14] strlen(input) → len, 다음: 0x1a
[0x1a] len == 32? → FAIL(0x08) | OK: 0x28
[0x28] input[0] == 'D'? → FAIL(0x19) | OK: 0x18
[0x18] input[1] == 'H'? → FAIL(0x0d) | OK: 0x1b
[0x1b] input[2] == '{'? → FAIL(0x1c) | OK: 0x0a
[0x0a] input[31] == '}'? → FAIL(0x09) | OK: 0x25
[0x25] target 28바이트 초기화, j=0, 다음: 0x06
[0x06/0x0c] ──┐ Copy 루프: working_buf[j] = input[j+3]; j++
└── j > 27 → [0x07]
[0x07] i=0, 다음: 0x1d
[0x1d/0x22] ──┐ XOR 루프: buf[i] ^= (i*0x37 + 0x5a); i++
└── i > 27 → [0x2a]
[0x2a] k=0, 다음: 0x0f
[0x0f/0x2b] ──┐ Mul17 루프: buf[k] = (buf[k] * 17) % 256; k++
└── k > 27 → [0x05]
[0x05] m=1, 다음: 0x00
[0x00/0x03] ──┐ XOR-neighbor 루프: buf[m] ^= buf[m-1]; m++
└── m > 27 → [0x10]
[0x10] n=0, 다음: 0x02
[0x02/0x0b/0x11] ──┐ 비교 루프: buf[n] == target[n]?; n++
└── n > 27 → [0x13] return 1 ✅
실패 → [0x23] return 0 ❌💣 Opaque Predicate — 핵심 트릭
state 0x22 (0x40123e)는 구간이 두 개다. 따로 잘라서 보는 게 낫다.
구간 ① — XOR 변환부 (40123e ~ 401261)
objdump -d -M intel mirage | grep -A 15 '40123e:'![state 0x22 XOR 변환부 — buf[i] ^= (i*0x37+0x5a), i++ 확인](/images/blog/dreamhack-control-flow-mirage-writeup/1777488245038_f546cf7c_image.png "클릭하여 확대")
40123e: mov eax, [rbp-0x10] ; i
401243: movzx edx, [rbp+rax-0x70] ; buf[i]
40124b: mov ecx, 0x37
401250: imul eax, ecx ; i * 0x37
401253: add eax, 0x5a ; + 0x5a
401256: xor edx, eax ; buf[i] ^= key
40125d: mov [rbp+rax-0x70], dl ; 저장
401261: add [rbp-0x10], 1 ; i++여기까지는 평범한 XOR 변환이다. 그런데 i++ 직후부터 전혀 관계없는 연산이 시작된다.
구간 ② — PRNG 조건 + 분기 (401265 ~ 4012f8)
objdump -d -M intel mirage | grep -A 10 '4012dc:'
; 401265 ~ 4012db: PRNG state를 읽어 % 7 계산 (컴파일러 최적화로 30줄)
4012dc: div esi ; edx = PRNG % 7
4012e2: mov eax, [0x4040d4] ; = 5
4012e8: cmp edx, eax ; 나머지 == 5?
4012ea: jne 401681 ; ❌ 불일치 → state 변경 없이 루프백
4012f0: mov [rbp-0x28], 0x1d ; ✅ 일치 → state = 0x1d
4012f8: jmp 401681 ; (jne와 같은 주소로)처음 보면 PRNG 조건에 따라 어떤 바이트는 XOR되고 어떤 바이트는 건너뛰는 것처럼 읽힌다.
실제로는 전혀 그렇지 않다. 두 분기 목적지를 직접 따라가면 증명된다.
① jne / jmp 공통 목적지 0x401681 확인
objdump -d -M intel mirage | grep -A 5 '401681:'
jne 401681과 jmp 401681 모두 이 한 줄짜리 루프백으로 빠진다. state 레지스터를 바꾸지 않은 채로 dispatch loop(0x40120e)로 돌아간다.
② je 분기가 세팅하는 state 0x1d (0x401650) 확인
objdump -d -M intel mirage | grep -A 15 '401650:'
state 0x1d는 cmp [rbp-0x10], 0x1b (i > 27?) 한 줄이 전부다.
- i ≤ 27 → state = 0x22 → 다시 XOR 루프로
- i > 27 → state = 0x2a → 루프 종료
두 분기 경로를 정리하면:
PRNG % 7 ≠ 5 → jne 401681 → state 변경 없음(0x22) → dispatch → XOR buf[i+1]
PRNG % 7 == 5 → state=0x1d, jmp 401681 → dispatch → state 0x1d(경계체크) → state=0x22 → dispatch → XOR buf[i+1]어느 분기를 타도 결과는 같다.
i = 0부터 27까지 모든 바이트에 XOR이 빠짐없이 적용된다.
PRNG 조건은 단지 state 0x1d(종료 확인 상태)를 몇 번 더 거치느냐를 바꿀 뿐이다. 이것이 Opaque Predicate다. 복잡한 연산으로 중요한 분기처럼 보이지만 어느 쪽으로 가든 결과가 동일하다.
문제 힌트 "not every branch tells the truth" 가 정확히 이걸 가리킨다.
▶🐛 삽질 — PRNG 결과에 따라 다른 변환이 적용되는 줄 알았다
state 0x22 안에 보조 jump table(0x4040c0)을 참조하는 코드가 있어서, PRNG % 7 값에 따라 서로 다른 변환이 적용되는 구조인 줄 알았다.
objdump -d -M intel mirage | grep -A 80 '<check>:' | grep -B2 -A5 '4040c0'
4012c7: lea rax, [0x4040c0] ; 보조 테이블
4012ce: mov eax, [rdx+rax] ; 테이블에서 값 로드보조 테이블 값을 전부 뽑아보니 결국 모두 같은 흐름으로 합쳐졌다. PRNG 결과가 무엇이든 XOR이 적용된다는 사실은 불변.
nanosleep 타이밍 노이즈와 함께 동적 분석·정적 분석 모두를 헷갈리게 만드는 이중 장치였다.
🔬 변환 로직 정리
state 추적으로 확인한 변환 순서:
① Copy: buf[j] = input[j+3] (j = 0..27)
② XOR key: buf[i] ^= (i * 0x37 + 0x5a) & 0xff (i = 0..27)
③ Mul17: buf[k] = (buf[k] * 17) % 256 (k = 0..27)
④ XOR-neighbor: buf[m] ^= buf[m-1] (m = 1..27, in-place 좌→우)
⑤ Compare: buf[n] == target[n]? (n = 0..27)target 바이트 28개는 state 0x25(0x40141f)에서 하드코딩으로 초기화된다.
# target 초기화 구간 확인
objdump -d -M intel mirage | grep -A 35 '40141f:'
target = [
0x0a, 0xfb, 0x47, 0x29, 0x5a, 0x64, 0xcf, 0x94,
0xf4, 0xee, 0xca, 0xa2, 0x6d, 0xdb, 0xe8, 0xff,
0x1a, 0x27, 0xbe, 0xa2, 0x2b, 0x52, 0xa9, 0xfb,
0x29, 0xa5, 0x44, 0x22
]🎯 역산
target → input 방향으로 변환을 역순으로 뒤집는다.
역산 ④ — XOR-neighbor
변환 ④는 in-place 누적 XOR (prefix XOR)이다:
final[0] = orig[0]
final[1] = orig[1] ^ orig[0]
final[2] = orig[2] ^ orig[1] ^ orig[0]
...역연산: orig[m] = final[m] ^ final[m-1] (m = 1..27)
뒤에서부터 차례로 XOR하면 된다.
for m in range(27, 0, -1):
buf[m] ^= buf[m-1]역산 ③ — Mul17
(x * 17) % 256의 역원을 구한다. gcd(17, 256) = 1이므로 역원이 존재한다.
# 17 * 241 = 4097 = 16*256 + 1 → 17 * 241 ≡ 1 (mod 256)
buf = [(b * 241) % 256 for b in buf]역산 ② — XOR key
XOR은 자기 역연산이다.
buf = [buf[i] ^ ((i * 0x37 + 0x5a) & 0xff) for i in range(28)]역산 ① — Copy
input[j+3] = buf[j] → buf가 곧 flag 안쪽 28바이트.
🚀 Full Exploit
# solve.py
target = [
0x0a, 0xfb, 0x47, 0x29, 0x5a, 0x64, 0xcf, 0x94,
0xf4, 0xee, 0xca, 0xa2, 0x6d, 0xdb, 0xe8, 0xff,
0x1a, 0x27, 0xbe, 0xa2, 0x2b, 0x52, 0xa9, 0xfb,
0x29, 0xa5, 0x44, 0x22
]
# 역산 ④: prefix XOR inverse
buf = target[:]
for m in range(27, 0, -1):
buf[m] ^= buf[m-1]
# 역산 ③: mul17 inverse (17 * 241 ≡ 1 mod 256)
buf = [(b * 241) % 256 for b in buf]
# 역산 ②: XOR key
buf = [buf[i] ^ ((i * 0x37 + 0x5a) & 0xff) for i in range(28)]
inner = bytes(buf)
flag = b"DH{" + inner + b"}"
print(flag.decode())python3 solve.py
바이너리에 직접 입력해서 검증한다:
# verify.py
import subprocess
flag = "DH{0p4qu3_pr3d_1s_4_l13_4_y0u!!}"
result = subprocess.run(["./mirage"], input=flag + "\n", capture_output=True, text=True)
print(f"Input : {flag}")
print(f"Output: {result.stdout.strip()}")python3 verify.py
📝 결론
State Machine 난독화 — 44개 상태와 dispatch table로 실제 로직(copy → xor → mul17 → xor-neighbor → compare)을 흩뿌려 놓았다. jump table을 파싱하고 각 상태 주소를 objdump에서 직접 추적하면 구조가 드러난다.
Opaque Predicate — PRNG % 7 == 5 조건이 XOR 루프를 제어하는 것처럼 보이지만, 어느 분기로 가든 모든 28바이트에 XOR이 적용된다. 문제 힌트 그대로 "분기는 작동하지만 진실을 말하지 않는다."
역산 — 변환 순서 확인 후 prefix XOR inverse → mul 역원(241) → XOR key를 역순으로 적용하면 플래그가 나온다. 동적 분석 없이 순수 정적 분석으로 해결.
