[💠 Platinum 4] 한 프로세스에서 32비트와 64비트가 번갈아 돈다 — DreamHack conquergent 풀이

문제: DreamHack — conquergent 분류: reversing 난이도: 💠 Platinum 4 FLAG: DH{conquerer_of_x86_and_convergent_evolution_to_x64_with_cs_reg}

문제 설명은 한 줄이다.

return everything, return everywhere.

Dreamhack Invitational Quals 2026 에서 넘어온 문제고, 힌트는 없다. return 이 두 번 나오니 ROP 냄새를 풍기는데, 배포된 건 서버도 소스도 아닌 바이너리 하나뿐이라 리턴할 스택도 우리 손에 없다. 결론부터 적으면 여기서 말하는 return 은 ret 이 아니라 retf, 즉 far return 이다.

먼저 무엇을 받았는지 본다.

file extracted/deploy/prob && readelf -h extracted/deploy/prob | grep -E "Class|Machine|Type:|Entry" && readelf --dyn-syms extracted/deploy/prob

file 과 readelf 로 본 배포 바이너리 - ELF 32-bit LSB executable, Intel i386, dynamically linked, stripped 이고 Type 이 EXEC 이라 PIE 가 아니다. 동적 심볼은 memcpy, fread, puts, stdin 네 개뿐이다

32비트 i386, stripped, PIE 도 아니다. 임포트는 memcpy · fread · puts · stdin 네 개가 전부라 입력을 읽어서 뭔가 계산하고 문자열 하나를 찍는 프로그램이라는 것까지는 바로 보인다.

문제 개요

항목	내용
문제명	conquergent
난이도	💠 Platinum 4
분류	reversing
출처	Dreamhack Invitational Quals 2026
제공 파일	`deploy/prob` (17,772바이트, ELF 32-bit i386, stripped)
임포트	`memcpy` · `fread` · `puts` · `stdin`
핵심 기법	Heaven's Gate — `retf` 로 CS 를 0x23 ↔ 0x33 오가며 32비트 프로세스 안에서 64비트 코드를 실행
되돌리는 열쇠	곱셈 상수가 전부 홀수 → mod 2^64 곱셈 역원

fread 로 64바이트를 받아 qword 8개로 쪼갠 뒤, 세 단계를 거친 결과를 바이너리에 박힌 정답 테이블과 비교한다. 맞으면 Correct, 아니면 Nope. 정적으로는 평범한 체커인데, 그 "세 단계"가 32비트 코드가 아니라 64비트 코드로 돌아간다는 게 이 문제의 전부다.

🧩 정찰 — 읽을 문자열이 없다

.rodata 가 21바이트다. 통째로 떠 보면 뭐가 들어 있는지 한눈에 들어온다.

objdump -s -j .rodata extracted/deploy/prob && objdump -s -j .data extracted/deploy/prob

objdump -s 로 덤프한 .rodata 와 .data 섹션 - .rodata 는 0x804b000 부터 21바이트뿐이고 Correct 와 Nope 두 문자열만 들어 있다. .data 는 8바이트가 전부 0 이라 상수 테이블이 정적 데이터로 존재하지 않는다

Correct 와 Nope. 그게 전부다. .data 는 8바이트가 전부 0 이라 상수 테이블도 데이터 섹션에 없다. 그러니까 검증에 쓰이는 값은 전부 코드 안에 즉치값으로 박혀 있다는 뜻이고, 실제로 main 은 mov DWORD PTR [ebp-0x300],0x89abcdef 같은 줄을 줄줄이 늘어놓아 스택에 테이블을 깐다. dword 즉치값을 스택에 쓰는 자리만 세도 177곳이다.

여기까지는 흔한 stripped 체커다. 이상한 건 .text 를 통째로 디스어셈했을 때 나온다.

objdump -d -M intel extracted/deploy/prob | grep -c retf; objdump -d -M intel extracted/deploy/prob | grep -n retf | sed -n "1,6p"

objdump 출력에서 retf 를 세어 본 결과 - 32개가 나오고 첫 여섯 개의 위치는 0x8049cc8, 0x8049cff, 0x8049e01, 0x8049e38, 0x8049f06, 0x8049f3d 로 규칙적인 간격을 두고 짝을 이룬다

retf 가 32개다. 컴파일러가 만든 유저랜드 코드에는 far return 이 나올 이유가 없다. 이건 손으로 넣은 것이고, 주소를 보면 두 개씩 짝을 이룬다(0x8049cc8 / 0x8049cff, 0x8049e01 / 0x8049e38 …). 나가는 문과 들어오는 문이 한 쌍이라는 뜻이다.

🚪 배경 — Heaven's Gate

x86-64 리눅스 커널은 32비트 프로세스도 그대로 돌린다. 이때 GDT 에는 두 개의 코드 세그먼트가 같이 올라가 있다.

셀렉터	세그먼트	모드
`0x23`	`__USER32_CS`	32비트 compat mode
`0x33`	`__USER_CS`	64비트 long mode

CS 는 mov 로 바꿀 수 없다. 바꾸려면 far branch — ljmp · lcall · retf 를 써야 한다. retf 는 스택에서 [esp] 를 EIP 로, [esp+4] 를 CS 로 꺼내 간다. 그러니까 32비트 코드가 [esp+4] 에 0x33 을 깔고 retf 하면, 같은 프로세스·같은 주소공간에서 CPU 모드만 64비트로 바뀐다. 윈도우의 WoW64 구현에서 이름이 붙어 Heaven's Gate 라고 부른다.

이 문제는 그걸 연산 하나마다 왕복으로 쓴다.

Heaven's Gate 왕복 구조도 - 왼쪽 32비트 구간에서 main 이 포인터를 준비하고 셀렉터 0x33 을 계산으로 만들어 retf 로 나가면, 오른쪽 64비트 구간에서 가젯이 qword 연산을 수행하고 jmp rdi 로 복귀 트램폴린에 들어가 다시 retf 로 32비트로 돌아온다

💣 핵심 — 같은 바이트, 두 가지 해석

objdump 는 ELF 헤더의 e_machine 을 믿는다. 이 파일은 EM_386 이라고 적혀 있으니 무조건 32비트로 푼다. 그래서 64비트 구간을 보여 줄 때 이런 화면이 나온다.

문제 폴더에 잘라내기 헬퍼를 하나 만들어 뒀다. 해당 구간만 통짜 바이너리로 떼어 -m i386:x86-64 로 다시 읽힌다.

cat disasm64.sh

#!/usr/bin/env bash
# prob 의 임의 구간을 x86-64 로 디스어셈한다.
#   사용법: ./disasm64.sh <시작주소> <끝주소> [주석용 sed 파일]
# objdump 는 ELF 헤더(EM_386)를 믿고 32비트로만 풀어 주므로, 해당 구간을
# 통짜 바이너리로 잘라내 -m i386:x86-64 로 다시 읽혀야 진짜 명령이 보인다.
set -euo pipefail
BIN=extracted/deploy/prob
LOAD=0x8048000                      # 이 ELF 는 파일 오프셋 = vaddr - 0x8048000
START=$1; END=$2; SED=${3:-}
python3 -c "
d = open('$BIN','rb').read()
open('/tmp/carve.bin','wb').write(d[$START-$LOAD:$END-$LOAD])"
if [ -n "$SED" ]; then
  objdump -D -b binary -m i386:x86-64 -M intel --adjust-vma=$START /tmp/carve.bin | sed -f "$SED"
else
  objdump -D -b binary -m i386:x86-64 -M intel --adjust-vma=$START /tmp/carve.bin
fi

두 해석을 나란히 찍어 보는 스크립트다.

cat two_views.sh

#!/usr/bin/env bash
# 같은 바이트 20개를 두 가지 모드로 읽어 본다 — 이 문제의 핵심 착시.
set -euo pipefail
echo "### objdump 가 ELF 헤더(EM_386)를 믿고 32비트로 읽으면"
objdump -d -M intel --start-address=0x8049190 --stop-address=0x80491b2 \
        extracted/deploy/prob | sed -n '/^ 804/p'
echo
echo "### 같은 바이트를 x86-64 로 읽으면 (0x48 은 dec eax 가 아니라 REX.W 였다)"
./disasm64.sh 0x8049190 0x80491b2 | sed -n '/^ 804/p'

./two_views.sh

two_views.sh 로 같은 바이트 20개를 두 모드로 읽은 화면 - 위쪽 32비트 해석은 0x48 을 dec eax 로 떼어내 sub esp 0x60 을 내고, 아래쪽 x86-64 해석은 같은 0x48 을 REX.W 로 붙여 sub rsp 0x60 을 낸다

위쪽에서 48 이 dec eax 로 홀로 떨어져 나온다. 아래쪽에서는 같은 48 이 다음 명령에 붙어 REX.W 접두사가 되고, sub esp,0x60 은 sub rsp,0x60 으로, mov eax,[edx] 는 mov rax,[rdx] 로 읽힌다. 바이트는 한 글자도 다르지 않다. 읽는 모드만 다르다.

나가는 문

셀렉터를 만드는 코드는 일부러 즉치값을 피한다. 0x33 이라는 상수를 grep 으로 못 찾게 하려는 것이다.

objdump -d -M intel --start-address=0x8049ca3 --stop-address=0x8049cc9 extracted/deploy/prob | sed -f annot_gate.sed

32비트 쪽 게이트 코드에 sed 로 주석을 얹은 objdump 출력 - mov bl 0x3 에서 시작해 shl 두 번과 add 0x1a, inc 로 51 즉 0x33 을 만들고, esp+4 에 셀렉터를, esp 에 64비트 가젯 주소를 넣은 뒤 retf 로 CS 를 0x23 에서 0x33 으로 바꾼다

mov bl,3 → shl ebx,1 → shl ebx,2 → add ebx,0x1a → inc ebx = 3×2×4 + 26 + 1 = 51 = 0x33. 그 사이에 or ebx,0x0 · test ebx,ebx · nop 같은 무의미한 줄이 섞여 있는데, 값에는 영향이 없고 패턴 매칭만 방해한다.

edi 에 미리 넣어 두는 0x8049cc9 가 복귀 지점이다. 64비트 쪽 가젯은 전부 jmp rdi 로 끝난다.

들어오는 문

복귀 트램폴린 자체도 64비트 코드다. r9 로 0x23 을 만들어 스택에 깔고 다시 retf.

./disasm64.sh 0x8049cc9 0x8049d00 annot_tramp.sed

64비트 복귀 트램폴린을 x86-64 로 디스어셈한 결과 - mov r9b 0x23 으로 32비트 코드 셀렉터를 만들고 lea r8 rsp+4 로 자리를 잡아 mov DWORD PTR r8 r9d 로 깐 다음, rsp 에 복귀 주소 0x8049d00 을 넣고 retf 로 CS 를 0x33 에서 0x23 으로 되돌린다

shl r10,1 · shr r10,1 · inc r11 · dec r11 · xchg r12,r12 처럼 아무 일도 안 하는 줄이 또 섞여 있다. 32비트로 읽었을 때 그럴듯한 코드처럼 보이게 하려는 장식이다.

🧰 가젯 14종

64비트 구간은 0x8049186 부터 0x80494e6 까지다. 각 가젯은 ud2 로 구분되고 jmp rdi 로 끝난다. 덧셈 가젯을 통째로 보면 규약이 드러난다.

./disasm64.sh 0x8049186 0x80491d8 annot_add.sed

objdump 로 덤프한 덧셈 가젯에 sed 주석을 얹은 화면 - rdx 와 rcx 가 가리키는 qword 를 스택에 옮겨 lea rdx rax+rbx 로 더하고 rsi 에 써 넣은 뒤 jmp rdi 로 돌아간다

rsi = 목적지, rdx = 원본, rcx = 피연산자 포인터. 이 규약은 호출부에서 확인했다. 32비트 쪽은 포인터 세 개를 ecx → esi → edx 순서로 세팅한 뒤, 스택 슬롯을 두 번 갈아타며 섞어서 esi ← 목적지, edx ← 원본, ecx ← 피연산자로 재배치한다. 이 셔플을 대충 읽으면 목적지와 원본이 뒤바뀐 모델을 만들게 되고, 그러면 뒤에서 아무리 계산해도 답이 안 나온다.

가젯을 하나하나 눈으로 읽는 대신 스크립트로 뽑았다.

#!/usr/bin/env python3
"""prob 의 .text 안에 박힌 64비트 가젯 구간을 잘라 x86-64 로 디스어셈하고,
가젯마다 실제 연산을 한 줄로 요약한다.
 
가젯 규약(호출부에서 확인): rsi=목적지, rdx=원본, rcx=피연산자 포인터.
모든 가젯은 'jmp rdi'(32비트 복귀 트램폴린)로 끝나고 'ud2'로 서로 구분된다.
"""
import re
import subprocess
 
BIN = "extracted/deploy/prob"
LOAD = 0x8048000          # ELF 가 통째로 이 주소에 매핑된다(파일 오프셋 = vaddr - LOAD)
LO, HI = 0x8049186, 0x80494E7
 
blob = open(BIN, "rb").read()[LO - LOAD:HI - LOAD]
open("/tmp/g64.bin", "wb").write(blob)
asm = subprocess.run(
    ["objdump", "-D", "-b", "binary", "-m", "i386:x86-64", "-M", "intel",
     f"--adjust-vma={LO:#x}", "/tmp/g64.bin"],
    capture_output=True, text=True).stdout
 
CORE = re.compile(r"^(add|imul|xor|and|or|not|shl|shr|rol|ror|div|sub|lea)\s")
SKIP = re.compile(r"rsp|rax,rax$|rcx,rcx$|rdx,rdx$|,0x0$"
                  r"|^add\s+eax,"          # PIC 베이스 재계산(연산과 무관)
                  r"|^lea\s+r..,\[r..\]$")  # lea r,[r] = 단순 복사
 
gadgets, cur, addr = [], [], None
for line in asm.splitlines():
    m = re.match(r"^\s+([0-9a-f]+):\t[0-9a-f ]+\t(.*)$", line)
    if not m:
        continue
    a, ins = int(m.group(1), 16), m.group(2).strip()
    if ins == "ud2":
        cur, addr = [], None
        continue
    if addr is None:
        addr = a
    cur.append((a, ins))
    if ins == "jmp    rdi":
        gadgets.append((addr, cur))
        cur, addr = [], None
 
for addr, body in gadgets:
    core = [i for _, i in body if CORE.match(i) and not SKIP.search(i)]
    dest = [i for _, i in body if i.startswith("mov    QWORD PTR [rsp")]
    if any(i.startswith("div") for i in core):          # div 는 몫(rax)·나머지(rdx)를 함께 낸다
        core.append("→ 저장: " + ("rdx(나머지)" if dest and dest[-1].endswith("rdx") else "rax(몫)"))
    print(f"0x{addr:08x}  {len(body):>2}개 명령  |  {'; '.join(core) or 'mov 만 — 단순 복사'}")

python3 dump_gadgets.py

dump_gadgets.py 실행 결과 - 0x8049186 부터 0x80494a0 까지 가젯 14개의 시작 주소와 명령 개수, 그리고 각각의 정체가 lea 덧셈, imul, xor, and, or, 단순 복사, not, shl, shr, rol, ror, div 몫, div 나머지, not 후 add 로 나열된다

주소	연산	주소	연산
`0x8049186`	`dst = src + op`	`0x804933a`	`dst = src << op`
`0x80491db`	`dst = src * op`	`0x8049376`	`dst = src >> op`
`0x8049223`	`dst = src ^ op`	`0x80493b2`	`dst = rol(src, op)`
`0x8049267`	`dst = src & op`	`0x80493ee`	`dst = ror(src, op)`
`0x80492a8`	`dst = src \| op`	`0x804942a`	`dst = src / op`
`0x80492e9`	`dst = src`	`0x804946a`	`dst = src % op`
`0x8049310`	`dst = ~src`	`0x80494a0`	`dst = src - op`

SUB 가젯이 재밌다. sub 명령을 안 쓰고 not rbx → add rax,rbx → inc rax 로 2의 보수를 손으로 만든다. SHL 과 SHR 은 정의만 되어 있고 실제 호출부에서는 쓰이지 않는다.

🧪 gdb 로 못 박기

정적 분석만으로 "CS 가 바뀐다"고 단정하고 싶지 않아서 런타임으로 확인했다. retf 직전에 멈춰 세우고 stepi 두 번으로 문을 통과시킨 뒤 $cs 를 읽는다.

cat gate_cs.gdb

set confirm off
set pagination off
set disassembly-flavor intel
break *0x8049cc3
run < flag.bin
printf "\n[1] 32비트 구간 - retf 직전\n"
printf "    cs = 0x%x   eip = 0x%x\n", $cs, $eip
x/2i $eip
printf "    스택: [esp]=점프할 코드주소  [esp+4]=코드 셀렉터\n"
x/2wx $esp
stepi
stepi
printf "\n[2] retf 통과 직후 - 같은 프로세스, 다른 모드\n"
printf "    cs = 0x%x   pc = 0x%x\n", $cs, $pc
printf "\n[3] gdb 는 여전히 32비트로 디스어셈한다(0x48 = dec eax)\n"
x/4i $pc
quit

gdb -q -batch -x gate_cs.gdb --args extracted/deploy/prob

gdb 배치 실행 결과 - retf 직전 cs 가 0x23 이고 스택에 0x08049186 과 0x00000033 이 놓여 있다가, stepi 두 번 뒤 같은 프로세스에서 cs 가 0x33 으로 바뀐다

cs = 0x23 → cs = 0x33. 프로세스는 하나고 주소도 그대로다.

마지막 x/4i 를 일부러 남겨 뒀다. gdb 도 타겟 아키텍처를 i386 으로 잡고 있어서, 64비트 모드로 넘어간 뒤에도 0x48 을 dec eax 로 보여 준다. set architecture i386:x86-64 를 시도하면 Selected architecture is not compatible with reported target architecture i386 이라며 거부한다. 디버거를 켜도 그 자리에서 자동으로 답이 나오지 않는다는 뜻이라, 결국 바이트를 손으로 잘라 다시 읽히는 수밖에 없었다.

🐛 여기서 두 번 헤맸다

▶🐛 삽질 1 — dec eax 를 진짜 명령으로 믿고 읽었다

처음 objdump -d 출력을 봤을 때 0x8049186 부터가 이렇게 보였다.

8049190:  48              dec    eax
8049191:  83 ec 60        sub    esp,0x60
8049194:  48              dec    eax
8049195:  8b 02           mov    eax,DWORD PTR [edx]

dec eax 가 명령 사이사이에 규칙적으로 끼어 있는 게 난독화 패딩처럼 보였다. 그런데 그대로 따라가면 덧셈 가젯이 이상해진다.

mov eax,[esp+8]      ; eax = a
dec eax              ; a-1
mov ebx,[esp+0x10]
dec eax              ; a-2
lea edx,[eax+ebx]    ; a-2+b   <- 왜 2를 빼지?

"난독화라기엔 값을 망가뜨리는데" 하는 위화감이 시작점이었다. 그리고 더 결정적인 게 있다. 32비트 해석이면 결과를 쓰는 mov [esi],eax 가 4바이트만 쓴다. 그런데 마지막 비교 루프는 [ebp+i*8-0x800] 과 [ebp+i*8-0x7fc] 를 함께 읽어 8바이트를 본다. 상위 4바이트를 아무도 안 쓰는데 정답 테이블의 상위 워드는 0 이 아니다 — 그 해석으로는 애초에 Correct 가 나올 수 없다.

#!/usr/bin/env python3
"""0x48 을 REX.W 가 아니라 'dec eax' 로 읽었을 때 덧셈 가젯이 무엇을 계산하는지 재현한다.
 
32비트 해석:            64비트 해석(정답):
  mov eax,[esp+8]         mov rax,[rsp+8]
  dec eax        <-- 0x48   (0x48 은 다음 명령의 REX.W 접두사)
  mov ebx,[esp+0x10]      mov rbx,[rsp+0x10]
  dec eax        <-- 0x48
  lea edx,[eax+ebx]       lea rdx,[rax+rbx]
  ...
  mov [esi],eax  (4바이트)  mov [rsi],rax  (8바이트)
"""
M32 = (1 << 32) - 1
M64 = (1 << 64) - 1
 
a = 0x75716e6f637b4844          # 복원된 입력 in[0]
b = 0x0123456789abcdef          # K1[0]
 
wrong = ((a & M32) - 2 + (b & M32)) & M32       # dec 두 번이 eax 를 갉아먹는다
right = (a + b) & M64
 
print(f"in[0]        = 0x{a:016x}")
print(f"K1[0]        = 0x{b:016x}")
print(f"32비트 해석  = 0x{wrong:08x}          <- dword 4바이트, 게다가 -2")
print(f"64비트 해석  = 0x{right:016x}  <- qword 8바이트")
print()
print("비교 루프는 [ebp+i*8-0x800] 과 [ebp+i*8-0x7fc] 를 함께 읽어 qword 를 본다.")
print("32비트 해석이면 상위 4바이트를 아무도 안 쓰는데, EXP 의 상위 워드는 0 이 아니다:")
for i, e in enumerate([0x35ee0f56e5b71ca4, 0x3ffd40a16a1056fd, 0xca5272e52c5ba31a, 0x6bc3120b92a71b25]):
    print(f"  EXP[{i}] = 0x{e:016x}   상위 dword = 0x{e >> 32:08x}")

python3 wrong32.py

wrong32.py 실행 결과 - 같은 입력에 대해 32비트 해석은 0xed271631 이라는 dword 를 내고 64비트 해석은 0x7694b3d6ed271633 이라는 qword 를 낸다. 아래에 정답 테이블 네 개의 상위 dword 가 전부 0 이 아님을 나열해 32비트 해석이 성립할 수 없음을 보인다

retf 를 세어 본 게 그 다음이었다. 32개가 나오는 순간 방향이 잡혔다.

▶🐛 삽질 2 — div 와 mod 를 보고 비가역이라고 판단했다

세 번째 단계에서 DIV 가젯과 MOD 가젯이 연달아 나온다. 나눗셈은 나머지를 버리니 되돌릴 수 없다. "입력을 역산하는 문제가 아니라 브루트포스로 맞춰야 하는 문제인가" 싶어서 잠깐 멈췄다.

그런데 두 가젯 다음에 MUL 이 하나 더 있고, 그 뒤에 32비트 인라인 코드가 붙는다.

objdump -d -M intel --start-address=0x804a9c7 --stop-address=0x804a9fe extracted/deploy/prob | sed -f annot_divmod.sed

div 와 mod 결과를 다시 합치는 32비트 인라인 코드에 sed 주석을 얹은 objdump 출력 - 몫 곱하기 제수를 담은 배열과 나머지 배열을 add 와 adc 로 64비트 덧셈해 원래 값을 복원한 뒤 ebp-0x7c0 배열에 다시 써 넣는다

몫 × 제수 + 나머지 = 원래 값. 네 개 연산이 통째로 항등식이었다. 값은 하나도 안 변한다. 되돌릴 수 없는 연산을 넣어 둔 게 아니라, 되돌릴 수 없어 보이게 넣어 둔 것이다.

정직하게 말하면 이건 함정이라기보다 시간 도둑이었다. 계산 그래프를 끝까지 그리기 전에 "여기서 정보가 날아간다"고 결론을 내린 게 문제였다.

🔎 상수 테이블 뽑기

main 은 상수를 전부 mov DWORD PTR [ebp-0xNNN], imm32 로 한 줄씩 깐다. 그런 자리가 177곳이라 손으로 옮겨 적으면 반드시 틀린다. 디스어셈에서 기계적으로 긁었다. 베이스 주소는 각 가젯 호출부의 lea eax,[ebp-0xNNN] 에서 읽었다.

#!/usr/bin/env python3
"""main 이 스택에 깔아 두는 상수 테이블을 디스어셈에서 기계적으로 뽑는다.
 
main 은 모든 상수를 `mov DWORD PTR [ebp-0xNNN], imm32` 로 한 줄씩 깐다.
그래서 dword 를 offset 으로 모아 두 개씩 리틀엔디언으로 붙이면 qword 테이블이 나온다.
베이스 주소(-0x300 등)는 각 연산 호출부의 `lea eax,[ebp-0xNNN]` 에서 읽은 것이다.
"""
import re
import subprocess
 
BIN = "extracted/deploy/prob"
BASES = [                       # (베이스, 이름, 원소크기, 설명)
    (0x300, "K1  ", 8, "stage1 덧셈 상수"),
    (0x340, "K2  ", 8, "stage1 XOR 상수"),
    (0x380, "K4  ", 8, "stage3 덧셈 상수"),
    (0x3c0, "K3  ", 8, "stage1 곱셈 상수(홀수)"),
    (0x400, "K7  ", 8, "stage3 곱셈 상수(홀수)"),
    (0x420, "ROT1", 4, "stage1 rol 자리수"),
    (0x440, "ROT2", 4, "stage3 ror 자리수"),
    (0x480, "K5  ", 8, "div/mod 제수"),
    (0x4c0, "K8  ", 8, "stage3 뺄셈 상수"),
    (0x500, "K6  ", 8, "stage3 XOR 상수"),
    (0x540, "EXP ", 8, "정답 비교 테이블"),
]
 
asm = subprocess.run(["objdump", "-d", "-M", "intel", BIN],
                     capture_output=True, text=True).stdout
dwords = {}
for m in re.finditer(r"mov\s+DWORD PTR \[ebp-0x([0-9a-f]+)\],0x([0-9a-f]+)", asm):
    dwords[int(m.group(1), 16)] = int(m.group(2), 16)
print(f"[i] main 이 스택에 깐 dword 상수 {len(dwords)}개를 수집했다\n")
 
for base, name, esz, why in BASES:
    vals = []
    for i in range(8):
        off = base - i * esz                       # 스택은 아래로 자라니 인덱스가 커질수록 오프셋이 준다
        if esz == 8:
            lo, hi = dwords.get(off, 0), dwords.get(off - 4, 0)
            vals.append(f"0x{(hi << 32) | lo:016x}")
        else:
            vals.append(f"0x{dwords.get(off, 0):02x}")
    print(f"{name} (ebp-0x{base:03x}) {why}")
    print("      " + ", ".join(vals))

python3 dump_keys.py

dump_keys.py 실행 결과 - main 이 스택에 깐 dword 상수 177개를 수집해 K1 부터 EXP 까지 열한 개 테이블을 qword 로 재조립해 출력한다. K3 와 K7 은 전부 홀수이고 K4 와 K8 은 같은 값이며 EXP 는 정답 비교 테이블 여덟 개다

여기서 두 가지가 눈에 들어온다.

K3 와 K7 이 전부 홀수다. 0x13, 0x15, …, 0x21 과 0x31, 0x33, …, 0x3f. 홀수는 2의 거듭제곱과 서로소라 mod 2^64 에서 곱셈 역원이 존재한다. 곱셈을 되돌릴 수 있다는 뜻이다.

K4 와 K8 이 같은 값이다. 출제자가 상수 테이블을 재사용했다. 역산에는 영향이 없지만, 두 테이블을 따로 적어 두면 나중에 헷갈린다.

이제 파이프라인 전체가 그려진다.

입력 64바이트를 qword 8개로 태우는 세 단계 파이프라인 구조도 - stage 1 은 K1 덧셈부터 비트 반전까지, stage 2 는 인접 레인의 홀짝 비트 교환, stage 3 은 K4 덧셈부터 K8 뺄셈까지다

가운데 단계가 유일하게 레인을 섞는다.

R'[i]   = (R[i] & 0xAAAA…AA) | (R[i+1] & 0x5555…55)
R'[i+1] = (R[i] & 0x5555…55) | (R[i+1] & 0xAAAA…AA)

홀수 자리 비트와 짝수 자리 비트를 두 레인 사이에서 맞바꾼다. 한 번 더 걸면 원래대로 돌아오는 대합(involution)이라, 역산할 때 똑같은 식을 그대로 한 번 더 쓰면 된다.

여기서 실수하기 쉬운 지점이 하나 있다. 32비트 코드는 R[i] 를 먼저 덮어쓴 다음 R[i+1] 을 계산하는데, 이때 R[i+1] 쪽은 이미 덮인 R[i] 가 아니라 이전 단계 배열(ebp-0x680)의 원본을 읽는다. MOV 가젯이 만들어 둔 사본이 여기서 쓰인다. 그걸 놓치고 갱신된 값으로 계산하면 결과가 달라진다.

🎯 역산

각 단계를 거꾸로 밟는다. 어려운 부분은 곱셈뿐이다.

mod 2^64 곱셈 역원. 홀수 a 에 대해 a·x ≡ 1 (mod 2^64) 인 x 는 뉴턴 반복으로 구한다. x ← x·(2 − a·x) 를 돌리면 정확한 비트 수가 매 회 두 배가 되므로, 1비트에서 시작해 7회면 64비트를 넘는다.

def minv(a):
    x = 1
    for _ in range(7):
        x = (x * (2 - a * x)) & M
    return x

나머지는 짝을 맞추기만 하면 된다.

순방향	역방향
`+ K`	`− K`
`^ K`	`^ K`
`rol n`	`ror n`
`× K` (K 홀수)	`× minv(K)`
`~`	`~`
비트 레인 교환	같은 식 한 번 더
`÷ K`, `% K`, `× K`, `+`	통째로 항등 — 건드릴 것 없음

그래서 정답 테이블 EXP 에서 출발해 stage 3 → stage 2 → stage 1 순으로 되감으면 입력 qword 8개가 나온다. 리틀엔디언으로 이어 붙이면 그게 64바이트 플래그다.

🚀 Full Exploit

solve.py 전문이다. 순방향 함수도 같이 넣어 뒀는데, 역산 결과를 다시 순방향으로 돌려 EXP 와 일치하는지 assert 로 확인하기 위해서다. 이걸 안 넣으면 "숫자가 나왔다"와 "맞는 숫자가 나왔다"를 구분할 수 없다.

#!/usr/bin/env python3
"""conquergent (Dreamhack Platinum 4, reversing) — Heaven's Gate 체커 역산.
 
32비트 프로세스가 retf 로 CS=0x33 에 들어가 64비트 가젯을 돌리는 구조라,
연산 자체는 전부 64비트 qword 단위다. 입력 64바이트를 qword 8개로 보고
아래 3단계를 거친 결과가 EXP 와 같아야 "Correct" 가 나온다.
 
  stage1  R[i]  = ~( rol64( (in[i] + K1[i]) ^ K2[i], rot1[i] ) * K3[i] )
  stage2  (i=0,2,4,6 짝끼리 비트레인 교환)
          R'[i]   = (R[i] & 0xAAAA..) | (R[i+1] & 0x5555..)
          R'[i+1] = (R[i] & 0x5555..) | (R[i+1] & 0xAAAA..)
  stage3  Z[i]  = ( (rol64( ror64(R'[i]+K4[i], rot2[i]) ... ) ) ) 아래 코드 참조
"""
import pathlib
 
M = (1 << 64) - 1
 
K1 = [0x0123456789abcdef, 0x0f0e0d0c0b0a0908, 0x1111111111111111, 0x2222222222222222,
      0x3333333333333333, 0x4444444444444444, 0x5555555555555555, 0x6666666666666666]
K2 = [0xfedcba0987654321, 0x89abcdef01234567, 0xcafebabedeadbeef, 0x0badf00ddeadc0de,
      0x13579bdf2468ace0, 0xcafeface12345678, 0x0f0f0f0f0f0f0f0f, 0xf0f0f0f0f0f0f0f0]
K3 = [0x13, 0x15, 0x17, 0x19, 0x1b, 0x1d, 0x1f, 0x21]          # 전부 홀수 → mod 2^64 가역
K4 = [0x0a0a0a0a0a0a0a0a, 0x1b1b1b1b1b1b1b1b, 0x2c2c2c2c2c2c2c2c, 0x3d3d3d3d3d3d3d3d,
      0x4e4e4e4e4e4e4e4e, 0x5f5f5f5f5f5f5f5f, 0x6060606060606060, 0x7171717171717171]
K6 = [0x0f0f0f0f0f0f0f0f, 0xf0f0f0f0f0f0f0f0, 0xaaaaaaaa55555555, 0x55555555aaaaaaaa,
      0x1234567890abcdef, 0xfedcba9876543210, 0x0f1e2d3c4b5a6978, 0x89abcdef01234567]
K7 = [0x31, 0x33, 0x35, 0x37, 0x39, 0x3b, 0x3d, 0x3f]          # 전부 홀수
K8 = K4[:]                                                      # 같은 상수 테이블을 재사용한다
ROT1 = [5, 11, 17, 23, 29, 3, 7, 13]
ROT2 = [8, 16, 24, 32, 4, 12, 20, 28]
 
EXP = [0x35ee0f56e5b71ca4, 0x3ffd40a16a1056fd, 0xca5272e52c5ba31a, 0x6bc3120b92a71b25,
       0x104fd2f6c2b935a3, 0xf1b5ca3663b1b1d6, 0xcae30b30dad2aa08, 0x7586bb8dc13d6ebe]
 
A_MASK = 0xAAAAAAAAAAAAAAAA
F_MASK = 0x5555555555555555
 
 
def rol(v, n):
    n &= 63
    return ((v << n) | (v >> (64 - n))) & M if n else v
 
 
def ror(v, n):
    n &= 63
    return ((v >> n) | (v << (64 - n))) & M if n else v
 
 
def minv(a):
    """홀수 a 의 mod 2^64 곱셈 역원 (뉴턴 반복)."""
    x = 1
    for _ in range(7):
        x = (x * (2 - a * x)) & M
    return x
 
 
def forward(qs):
    """바이너리가 하는 계산 그대로 — 역산 결과를 자체 검증하는 데 쓴다."""
    r = []
    for i, v in enumerate(qs):
        a = (v + K1[i]) & M
        b = a ^ K2[i]
        c = rol(b, ROT1[i])
        d = (c * K3[i]) & M
        r.append((~d) & M)
    orig = r[:]
    for i in range(0, 8, 2):
        r[i] = (orig[i] & A_MASK) | (orig[i + 1] & F_MASK)
        r[i + 1] = (orig[i] & F_MASK) | (orig[i + 1] & A_MASK)
    out = []
    for i in range(8):
        v = (r[i] + K4[i]) & M
        w = ror(v, ROT2[i])
        x = w ^ K6[i]
        y = (x * K7[i]) & M
        out.append((y - K8[i]) & M)
    return out
 
 
def backward(exp):
    rp = []
    for i in range(8):
        y = (exp[i] + K8[i]) & M
        x = (y * minv(K7[i])) & M
        w = x ^ K6[i]
        v = rol(w, ROT2[i])
        rp.append((v - K4[i]) & M)
    r = rp[:]
    for i in range(0, 8, 2):                       # stage2 는 대합(involution)이라 그대로 한 번 더
        r[i] = (rp[i] & A_MASK) | (rp[i + 1] & F_MASK)
        r[i + 1] = (rp[i] & F_MASK) | (rp[i + 1] & A_MASK)
    qs = []
    for i in range(8):
        d = (~r[i]) & M
        c = (d * minv(K3[i])) & M
        b = ror(c, ROT1[i])
        a = b ^ K2[i]
        qs.append((a - K1[i]) & M)
    return qs
 
 
if __name__ == "__main__":
    qs = backward(EXP)
    assert forward(qs) == EXP, "역산 검증 실패"        # 되감은 값을 다시 순방향으로 돌려 대조
    flag = b"".join(q.to_bytes(8, "little") for q in qs)
    print("qwords:", " ".join(hex(q) for q in qs))
    print("flag  :", flag.decode(errors="replace"))
    (pathlib.Path(__file__).parent / "flag.bin").write_bytes(flag)

python3 solve.py

solve.py 실행 결과 - 역산으로 복원한 qword 여덟 개를 16진수로 출력한 뒤 리틀엔디언으로 이어 붙여 DH 로 시작하는 64바이트 플래그 문자열을 찍는다. 순방향 재계산 assert 를 통과했기 때문에 예외 없이 끝났다

DH{conquerer_of_x86_and_convergent_evolution_to_x64_with_cs_reg} — 정확히 64바이트다. fread 가 0x40 을 요구하니 길이도 처음부터 정해져 있었던 셈이다.

✅ 검증

파이썬 안에서만 맞는 건 의미가 없다. 복원한 바이트를 문제 바이너리에 그대로 먹인다.

xxd flag.bin | sed -n "1,2p"; extracted/deploy/prob < flag.bin; head -c 64 /dev/zero | extracted/deploy/prob

복원한 flag.bin 을 문제 바이너리에 먹인 결과 - xxd 로 앞 32바이트를 확인하면 DH 로 시작하는 아스키가 보이고, 바이너리는 Correct 를 출력한다. 대조군으로 64바이트 0 을 넣으면 Nope 가 나온다

Correct. 대조군으로 0 을 64바이트 넣으면 Nope 이 나오니 출력이 입력에 반응한다는 것도 같이 확인된다.

한 걸음 더 들어가서, 비교 직전에 멈춰 세우고 계산 결과와 정답 테이블을 나란히 떠 봤다.

cat check_state.gdb

set confirm off
set pagination off
break *0x804adde
run < flag.bin
printf "\n== 입력으로 계산해 낸 Z[0..7]  (ebp-0x800) ==\n"
x/8gx $ebp-0x800
printf "\n== 바이너리가 들고 있는 정답 EXP[0..7]  (ebp-0x540) ==\n"
x/8gx $ebp-0x540
printf "\n== 이후 실행 결과 ==\n"
continue
quit

gdb -q -batch -x check_state.gdb --args extracted/deploy/prob

gdb 로 비교 직전에 멈춰 계산 결과와 정답 테이블을 함께 덤프한 화면 - ebp-0x800 의 qword 여덟 개와 ebp-0x540 의 qword 여덟 개가 0x35ee0f56e5b71ca4 부터 0x7586bb8dc13d6ebe 까지 완전히 같은 값으로 찍히고 계속 실행하면 Correct 가 출력된다

여덟 개가 전부 같다. 우연히 맞은 게 아니라 파이프라인 모델이 실제 바이너리와 같다는 뜻이다.

재현은 문제 폴더의 reproduce.sh 하나로 끝난다.

#!/usr/bin/env bash
# conquergent (Dreamhack Platinum 4, reversing) — 한 방 재현
#   분석 → 역산 → 문제 바이너리로 검증까지.
# 필요 환경: i386 실행 지원(ld-linux.so.2, lib32 libc), objdump, gdb, python3
set -euo pipefail
cd "$(dirname "$0")"
 
echo "== [1] 바이너리 기본 정보 =="
file extracted/deploy/prob
 
echo
echo "== [2] Heaven's Gate 흔적: .text 안의 retf 개수 =="
objdump -d -M intel extracted/deploy/prob | grep -c 'retf'
 
echo
echo "== [3] 64비트 가젯 14종 =="
python3 dump_gadgets.py
 
echo
echo "== [4] main 이 깔아 두는 상수 테이블 =="
python3 dump_keys.py
 
echo
echo "== [5] 역산으로 플래그 복원 =="
python3 solve.py
 
echo
echo "== [6] 문제 바이너리로 검증 =="
extracted/deploy/prob < flag.bin

로컬 환경은 Ubuntu 25.10 / x86-64 커널 6.17 이고, 32비트 실행을 위해 libc6-i386 이 필요하다. objdump 는 binutils 2.45, gdb 는 16.3 을 썼다.

📝 결론

ELF 헤더는 디스어셈블러에게 주는 힌트일 뿐이다.

e_machine 이 EM_386 이어도 CPU 는 그 필드를 실행 중에 참조하지 않는다. 실제로 명령을 어떻게 해석할지는 CS 세그먼트 디스크립터의 L 비트가 정한다. 그래서 32비트로 로드된 프로세스가 retf 한 번으로 64비트 코드를 돌릴 수 있고, 정적 도구는 그걸 따라가지 못한다. objdump 도 gdb 도 이 파일 앞에서는 절반만 맞는 답을 준다.

의미 없어 보이는 명령이 왜 거기 있는지 물어야 한다.

dec eax 가 규칙적으로 끼어 있는 걸 "난독화 패딩"으로 넘겼으면 끝까지 못 풀었다. 그 명령이 값을 망가뜨린다는 위화감, 그리고 4바이트만 쓰는데 8바이트를 비교한다는 모순이 방향을 바꿔 줬다. 난독화는 보통 무해한 걸 끼워 넣는데 이건 유해했고, 그 유해함이 곧 "잘못 읽고 있다"는 신호였다.

되돌릴 수 없어 보이는 연산은 그래프를 끝까지 그린 다음 판단한다.

div 와 mod 를 보고 비가역이라고 멈춘 게 이번 풀이에서 가장 오래 잡아먹은 지점이었다. 네 줄 뒤에 몫 × 제수 + 나머지 로 되돌리는 코드가 있었다. 중간 단계 하나만 보고 정보 손실을 단정하면 이런 미끼에 걸린다.

곱셈 상수가 홀수인지 먼저 본다.

리버싱에서 mod 2^n 곱셈은 상수가 홀수이기만 하면 뉴턴 반복 일곱 줄로 되돌릴 수 있다. 이 문제는 곱셈을 두 군데 넣어 두고 상수 열여섯 개를 전부 홀수로 골랐다. 짝수가 하나라도 섞였으면 그 레인은 정보가 날아가 역산이 아니라 탐색이 됐을 것이다.

방어 관점에서는 이런 코드가 정상 프로그램에 있을 이유가 없다. 32비트 프로세스의 .text 에 retf 가 있거나 [esp+4] 에 0x33 을 쓰는 패턴이 보이면, 그건 정적 분석기와 EDR 의 명령 디코더를 동시에 우회하려는 시도로 보는 게 맞다. 실제로 이 기법은 32비트 후킹 엔진을 피하는 용도로 악성코드에서 쓰여 왔다. 탐지 규칙을 쓴다면 명령 시퀀스보다 0x33 이 스택에 실리는 순간과 far branch 를 함께 보는 쪽이 견고하다.

[💠 Platinum 4] 한 프로세스에서 32비트와 64비트가 번갈아 돈다 — DreamHack conquergent 풀이

댓글

관련 글

[💠 Platinum 4] 0의 런렝스를 감마 코드로 되감기 — DreamHack Run 풀이

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

[🥇 Gold 4] 지그재그로 접힌 플래그 — DreamHack quilt 풀이