[🥇 Gold 4] 점프도 비교도 없는 VM 에서 flag 를 되뽑기 — DreamHack bitvm 풀이

문제: DreamHack 워게임 — bitvm 분류: reversing 난이도: 🥇 Gold 4 FLAG: DH{bc42e3abb217fa4fd8b8991bc5a378d7dd4421fd887feb797eb759ca2d0d0e95}

문제 설명이 한 줄이다.

간단한 VM입니다! 점프, 비교연산자, 심지어는 덧셈 뺄셈도 존재하지 않습니다!

보통 이런 문장은 겁을 주려고 쓴다. 여기서는 반대다. 없는 것들을 하나씩 지워 나가면 남는 게 너무 적어서, 오히려 답이 한 줄 수식으로 떨어진다.

문제 개요

항목	내용
문제명	bitvm
난이도	🥇 Gold 4
분류	reversing
출처	Dreamhack CTF Season 4 Round #10 (Div2)
제공 파일	`chall` (ELF 64-bit PIE, stripped) · `command` (2,472바이트 바이트코드)
서버	없음 — 오프라인 문제
핵심 취약점 / 기법	비트연산만 가진 VM 의 검사식을 비트 단위로 분해해 역산

풀이 흐름은 셋으로 나뉜다.

chall 의 디스패치 루프를 읽어 명령 집합 열 개를 복원한다.
그 명령 집합으로 command 를 디스어셈블해 검사 블록 68개를 찾는다.
블록이 거는 제약 두 줄을 비트별로 풀어 글자를 하나씩 결정한다.

🧩 배경 — 바이트코드 VM 문제가 요구하는 것

리버싱 문제에서 VM 이 나오면 분석 대상이 두 겹이 된다.

바깥은 네이티브 x86-64 바이너리다. 이 안에는 "명령을 하나 읽어서 종류에 따라 갈라진다"는 루프 하나만 들어 있다. 진짜 로직은 그 루프가 해석하는 데이터 파일 쪽에 있다.

그래서 순서가 정해져 있다. 바깥 루프를 읽어 명령 집합(ISA)을 확정하지 못하면 안쪽 데이터는 그냥 무의미한 바이트 덩어리다. 반대로 ISA 만 확정되면 안쪽은 디스어셈블러 30줄로 읽힌다.

이 문제가 재미있는 지점은 ISA 가 의도적으로 빈약하다는 것이다. 문제 설명이 없다고 자랑한 것들 — 분기·비교·덧셈 — 은 보통 "검사"를 짤 때 제일 먼저 쓰는 도구들이다. 그걸 다 빼고도 68글자를 검사하려면 방법이 하나로 좁혀진다. 그 좁혀진 방법이 곧 역산 공식이 된다.

🔬 정찰 — 파일 두 개, 그리고 인사말이 데이터에 박혀 있다

배포본을 풀면 파일이 둘이다. 실행 가능한 chall 과, file 이 그냥 data 라고 답하는 command.

ls -l extracted/ && file extracted/* && checksec --file=extracted/chall

ls / file / checksec — chall 은 stripped PIE, command 는 정체불명의 data

보호 기법은 Full RELRO · Canary · NX · PIE 로 다 켜져 있다. 하지만 이건 pwn 문제가 아니라 메모리를 깨뜨릴 일이 없다. 여기서 의미 있는 건 stripped 하나다. 심볼이 없으니 main 도 run 도 이름으로는 못 찾는다.

먼저 알아둘 것 하나. chall 은 인자 없이 실행하면 아무것도 안 한다.

// 0x1671 — main
if (argc != 2) { puts("Usage: ./chall command_file"); return 0; }

바이트코드 파일 경로를 반드시 넘겨야 한다. 그냥 ./chall 만 치고 "실행이 안 되네" 하고 넘어가기 딱 좋은 지점이라, 실행은 늘 이 꼴이어야 한다.

cd extracted && chmod +x chall && ./chall command

command 를 먼저 들여다봤다.

xxd extracted/command | sed -n "1,6p;10,18p"

xxd — 앞머리에 0x21 이 글자 사이에 끼어 있고, 뒤로 갈수록 0x23/0x25/0x26/0x27 이 반복된다

여기서 이미 절반은 보인다.

앞머리 ASCII 열이 !T!h!i!s! !i!s! 다. 원본 문자열은 This is a mini VM to check the flag! 인데 글자마다 앞에 0x21(!)이 하나씩 끼어 있다. 즉 0x21 은 "다음 바이트를 출력하라"는 1바이트 오퍼랜드 명령이다. 인사말이 코드가 아니라 명령 시퀀스로 박혀 있는 것이다.

그 다음 Input: 뒤로는 0x22(")가 길게 이어진다. 출력 다음에 오는 것이니 입력을 받는 명령일 가능성이 높다. 그리고 그 뒤부터 파일 끝까지는 0x23 0x25 0x26 0x27 0x28 이 일정한 리듬으로 반복된다. 검사 루틴이 여기 있다.

추측은 여기까지다. 나머지는 바깥 바이너리가 확정해 준다.

🧠 명령 집합 복원 — 디스패치 체인을 그대로 읽는다

objdump -d 로 전체를 떠 놓으면 490줄쯤 나온다. stripped 라 함수 이름이 없지만 PLT 호출은 그대로 보이니, 어떤 라이브러리 함수를 부르는지로 역할을 짐작할 수 있다.

.text 안에서 의미 있는 덩어리는 다섯이다. 앞쪽 셋은 __cxa_finalize 를 만지는 컴파일러 생성 코드(frame_dummy 류)라 건너뛴다. 남은 것 중 fopen / getc / feof 를 부르며 바이트를 .bss 로 퍼 나르는 게 파일 로더고, putchar / getchar 를 부르며 되돌아오는 점프가 있는 게 VM 본체다. 마지막 하나는 puts 두 번으로 판정을 찍는 main 이다.

로더부터 보자.

// 0x1229 — command 파일을 .bss 0x4040 으로 통째 복사
FILE *f = fopen(path, "rb");
if (!f) { printf("No file named %s\n", path); return 1; }
for (int i = 0; !feof(f); i++) {
    if (i > 0x1387) { puts("Command too large"); return 1; }   // 최대 5000바이트
    code[i] = getc(f);
}

feof 를 getc 앞에서 검사하는 구조라, 마지막 한 번은 EOF(-1)를 그대로 0xff 로 저장하고 끝난다. command 는 2,472바이트이고 마지막 바이트가 마침 HALT 라 아무 영향이 없다. 읽다가 갸웃했지만 함정은 아니었다.

그 다음 함수가 본체다. 0x1341 에서 시작해 0x1364 로 되돌아오는 루프 하나가 전부다.

// 0x1341 — 이게 VM 이다
unsigned char regs[8] = {0};      // [rbp-0x10]
for (;;) {
    unsigned char op = code[pc];  // pc = .bss 0x6768
    pc++;
    if      (op == 0x20) return regs[0];
    else if (op == 0x21) { putchar(code[pc]); pc++; }
    ...
}

분기 구조가 if-else 10단이라 cmp BYTE PTR [rbp-0x11], <상수> 만 뽑으면 오퍼코드 목록이 그대로 나온다. 각 줄에 무슨 일을 하는지 주석을 얹어 찍었다. 주석은 sed 로 내가 붙인 것이고 objdump 원래 출력에는 없다.

# annot_dispatch.sed — 실제 출력에 설명만 얹는다
s/cmp    BYTE PTR \[rbp-0x11\],0x20/&      <-- 0x20 HALT : r0 을 반환값으로/
s/cmp    BYTE PTR \[rbp-0x11\],0x21/&      <-- 0x21 PUTC : 다음 바이트를 putchar/
s/cmp    BYTE PTR \[rbp-0x11\],0x22/&      <-- 0x22 READ : getchar 결과를 스택에 push/
s/cmp    BYTE PTR \[rbp-0x11\],0x23/&      <-- 0x23 SETI : r[a] = imm/
s/cmp    BYTE PTR \[rbp-0x11\],0x24/&      <-- 0x24 MOV  : r[a] = r[b]/
s/cmp    BYTE PTR \[rbp-0x11\],0x25/&      <-- 0x25 AND/
s/cmp    BYTE PTR \[rbp-0x11\],0x26/&      <-- 0x26 OR/
s/cmp    BYTE PTR \[rbp-0x11\],0x27/&      <-- 0x27 XOR/
s/cmp    BYTE PTR \[rbp-0x11\],0x28/&      <-- 0x28 POP  : r0 = pop()/
s/cmp    BYTE PTR \[rbp-0x11\],0x29/&      <-- 0x29 PUSH : push(r[a])/

objdump -d -M intel --start-address=0x1364 --stop-address=0x1670 extracted/chall | grep -E "cmp +BYTE PTR .rbp-0x11." | sed -f annot_dispatch.sed

objdump 정적 분석 — 디스패치 체인이 0x20 부터 0x29 까지 정확히 열 단

열 개다. 0x20 부터 0x29 까지 빈틈없이 이어지고 그 밖의 값은 아무 분기에도 안 걸려 조용히 무시된다(루프 맨 끝으로 떨어져 다시 fetch 로 간다).

ALU 쪽은 따로 봐야 한다. 0x25 0x26 0x27 세 핸들러는 코드가 거의 똑같고, 딱 한 명령만 다르다. 두 피연산자를 esi 와 ecx 에 각각 실은 다음 그 둘을 합치는 자리다.

# annot_alu.sed — 레지스터 파일 접근과 연산 자리에 설명을 얹는다
s/and    esi,ecx/&        <-- 0x25 AND : r[a] \& r[b]/
s/or     esi,ecx/&        <-- 0x26 OR  : r[a] | r[b]/
s/xor    esi,ecx/&        <-- 0x27 XOR : r[a] ^ r[b]/
s/add    esi,ecx/&        <-- (없음)/
s/sub    esi,ecx/&        <-- (없음)/
s/movzx  esi,BYTE PTR \[rbp+rax\*1-0x10\]/&   <-- 첫째 피연산자 r[a] 읽기/
s/movzx  ecx,BYTE PTR \[rbp+rax\*1-0x10\]/&   <-- 둘째 피연산자 r[b] 읽기/
s/mov    BYTE PTR \[rbp+rax\*1-0x10\],dl/&      <-- 결과를 r[d] 에 쓰기/

objdump -d -M intel --start-address=0x149f --stop-address=0x1610 extracted/chall | grep -E "(and|or|xor|add|sub) +esi,ecx|rbp.rax.1-0x10" | sed -f annot_alu.sed

objdump — 두 레지스터가 만나는 자리는 and·or·xor 세 개뿐, add/sub 패턴은 한 줄도 안 걸린다

and·or·xor 셋만 걸린다. 같은 grep 에 add·sub 를 같이 넣었는데 매치가 없다. 문제 설명이 자랑한 그대로다.

정리하면 이렇다.

op	이름	오퍼랜드	동작
`0x20`	HALT	—	`r0` 을 반환값으로 종료
`0x21`	PUTC	imm	`putchar(imm)`
`0x22`	READ	—	`push(getchar())`
`0x23`	SETI	d, imm	`r[d] = imm`
`0x24`	MOV	d, s	`r[d] = r[s]`
`0x25`	AND	d, a, b	`r[d] = r[a] & r[b]`
`0x26`	OR	d, a, b	`r[d] = r[a] \| r[b]`
`0x27`	XOR	d, a, b	`r[d] = r[a] ^ r[b]`
`0x28`	POP	—	`r0 = pop()`
`0x29`	PUSH	s	`push(r[s])`

상태는 전부 전역이다. 코드 버퍼가 .bss 0x4040, pc 가 0x6768, 데이터 스택이 0x53e0, 스택 포인터가 0x676c. 레지스터만 예외로 run() 의 스택 지역변수 [rbp-0x10] 8바이트다.

레지스터 인덱스는 바이트코드에서 그대로 오는데 경계 검사가 없다. 8 이상을 주면 바로 뒤 카나리를 밟는다. 실제 command 가 쓰는 최대 인덱스는 7 이라 이번엔 아무 일도 안 일어난다.

여기서 중요한 건 없는 쪽이다. pc 를 되돌리는 명령이 없으니 루프도 조건 분기도 못 만든다. 프로그램은 앞에서 뒤로 한 번 흐르고 끝난다. 68글자를 검사하려면 검사 코드를 68벌 펼쳐 놓는 수밖에 없고, 실제로 그렇게 돼 있다.

🛠 디스어셈블러 — 30줄이면 안쪽이 다 보인다

ISA 가 확정됐으니 command 를 읽는 건 기계적이다. 각 명령의 오퍼랜드 길이만 알면 되니까.

#!/usr/bin/env python3
"""bitvm - command 파일(VM 바이트코드) 디스어셈블러."""
import sys
 
code = open(sys.argv[1] if len(sys.argv) > 1 else "extracted/command", "rb").read()
 
pc = 0
out = []
while pc < len(code):
    at = pc
    op = code[pc]
    pc += 1
    if op == 0x20:
        out.append((at, "HALT", ()))
        break
    elif op == 0x21:
        out.append((at, "PUTC", (code[pc],)))
        pc += 1
    elif op == 0x22:
        out.append((at, "READ", ()))
    elif op == 0x23:
        out.append((at, "SETI", (code[pc], code[pc + 1])))
        pc += 2
    elif op == 0x24:
        out.append((at, "MOV", (code[pc], code[pc + 1])))
        pc += 2
    elif op in (0x25, 0x26, 0x27):
        name = {0x25: "AND", 0x26: "OR", 0x27: "XOR"}[op]
        out.append((at, name, (code[pc], code[pc + 1], code[pc + 2])))
        pc += 3
    elif op == 0x28:
        out.append((at, "POP", ()))
    elif op == 0x29:
        out.append((at, "PUSH", (code[pc],)))
        pc += 1
    else:
        out.append((at, "??? 0x%02x" % op, ()))
 
for at, name, args in out:
    if name == "PUTC":
        print("%04x  PUTC  0x%02x   ; %r" % (at, args[0], chr(args[0])))
    elif name == "SETI":
        print("%04x  SETI  r%d, 0x%02x" % (at, args[0], args[1]))
    elif name == "MOV":
        print("%04x  MOV   r%d, r%d" % (at, args[0], args[1]))
    elif name in ("AND", "OR", "XOR"):
        sym = {"AND": "&", "OR": "|", "XOR": "^"}[name]
        print("%04x  %-5s r%d, r%d, r%d   ; r%d = r%d %s r%d"
              % (at, name, args[0], args[1], args[2], args[0], args[1], sym, args[2]))
    elif name == "PUSH":
        print("%04x  PUSH  r%d" % (at, args[0]))
    else:
        print("%04x  %s" % (at, name))
 
print("\n총 %d 명령, READ %d 개, POP %d 개"
      % (len(out),
         sum(1 for _, n, _ in out if n == "READ"),
         sum(1 for _, n, _ in out if n == "POP")))

돌려서 앞뒤를 잘라 봤다.

python3 disasm.py extracted/command | sed -n "41,50p;110,112p" && python3 disasm.py extracted/command | tail -4

disasm.py 출력 — 인사말 PUTC 뒤로 READ 가 68번, 끝은 MOV r0, r7 과 HALT

총 794명령. READ 68개, POP 68개. 입력을 68글자 받아서 68번 꺼내 쓴다는 뜻이다. DH{ 와 } 를 빼면 64자 — 딱 SHA-256 헥사 길이다.

그리고 마지막 두 줄이 결론을 미리 알려 준다.

09a4  MOV   r0, r7
09a7  HALT

r7 을 r0 에 옮기고 끝낸다. main 은 이 반환값을 이렇게 쓴다.

// 0x16bf — run() 의 반환값이 0 이어야 Correct
if (run() == 0) puts("Correct!!!");
else            puts("Wrong.");

즉 r7 을 0 으로 만드는 입력이 flag 다. r7 이 무엇을 모으는지만 보면 된다.

그 전에 명령이 각각 몇 번 쓰이는지 세어 봤다. 반복 구조라면 횟수가 68의 배수로 딱 떨어질 것이고, 안 떨어지면 내가 오퍼랜드 길이를 잘못 읽었다는 뜻이다. 값싼 자가 진단이다.

#!/usr/bin/env python3
"""command 바이트코드가 각 명령을 몇 번 쓰는지 센다."""
from collections import Counter
 
NAMES = {0x20: "HALT", 0x21: "PUTC", 0x22: "READ", 0x23: "SETI", 0x24: "MOV",
         0x25: "AND", 0x26: "OR", 0x27: "XOR", 0x28: "POP", 0x29: "PUSH"}
WIDTH = {0x20: 0, 0x21: 1, 0x22: 0, 0x23: 2, 0x24: 2,
         0x25: 3, 0x26: 3, 0x27: 3, 0x28: 0, 0x29: 1}
 
code = open("extracted/command", "rb").read()
cnt = Counter()
pc = 0
while pc < len(code):
    op = code[pc]
    cnt[op] += 1
    pc += 1 + WIDTH[op]
    if op == 0x20:
        break
 
WHY = {
    "HALT": "프로그램 끝 한 번",
    "PUTC": "인사말 44글자",
    "READ": "입력 68글자",
    "SETI": "블록당 A,B,C  = 68 x 3",
    "MOV": "마지막 r0 = r7 한 번",
    "AND": "블록당 c & A  = 68 x 1",
    "OR": "c | A 와 r7 누적 2회 = 68 x 3",
    "XOR": "B/C 와 비교 2회 = 68 x 2",
    "POP": "블록당 글자 하나 = 68 x 1",
    "PUSH": "이 바이트코드는 안 쓴다",
}
 
print("op    이름   횟수   설명")
for op in sorted(NAMES):
    n = NAMES[op]
    print("0x%02x  %-5s %4d   %s" % (op, n, cnt[op], WHY[n]))
print("\n합계 %d 명령 / 파일 %d 바이트" % (sum(cnt.values()), len(code)))

오른쪽 설명 열은 내가 붙인 것이다. 숫자만 스크립트가 센다.

python3 opcount.py

opcount.py 실행 — SETI 204, OR 204, XOR 136 이 전부 68의 배수로 떨어진다

전부 68의 배수다. SETI 204 = 68 × 3, XOR 136 = 68 × 2, OR 204 = 68 × 3. 파싱이 어긋났다면 이 숫자들이 지저분하게 나왔을 텐데 깨끗하다.

두 가지가 눈에 걸린다.

MOV 가 딱 한 번뿐이다. 마지막 MOV r0, r7 이 그 하나다. 레지스터 사이 값을 옮길 일이 없다는 건 블록들이 서로 데이터를 주고받지 않는다는 뜻 — 글자마다 완전히 독립이다.

PUSH 는 아예 0 이다. ISA 에는 있는데 이 바이트코드는 한 번도 안 쓴다. 스택에 값이 올라가는 경로가 READ 하나뿐이라는 뜻이고, 그래서 스택 내용은 처음부터 끝까지 "입력 68글자" 그대로다. 이 사실이 뒤에서 순서를 확정할 때 쓰인다.

PUTC 44 도 맞다. This is a mini VM to check the flag! 36자 + 개행 + Input: 7자.

검사 블록을 두 개 나란히 찍었다.

python3 disasm.py extracted/command | sed -n "113,132p"

disasm.py — 검사 블록은 SETI 3개 + POP + 여섯 줄 연산이 한 세트로 68번 반복된다

블록 하나가 열 줄이고, 상수 셋만 바뀌면서 68번 되풀이된다. 한 벌을 옮겨 적으면 이렇다.

SETI r1, A          ; 블록마다 다른 상수 셋
SETI r2, B
SETI r3, C
POP                 ; r0 = 입력 한 글자 c
AND  r4, r0, r1     ; r4 = c & A
XOR  r5, r2, r4     ; r5 = B ^ (c & A)
OR   r7, r5, r7     ; r7 |= r5
OR   r4, r0, r1     ; r4 = c | A
XOR  r5, r3, r4     ; r5 = C ^ (c | A)
OR   r7, r5, r7     ; r7 |= r5

XOR 로 차이를 만들고 OR 로 모은다. 비교 명령이 없으니 이게 "같다"를 표현하는 유일한 방법이다. 차이가 0 이면 XOR 결과가 0 이고, 하나라도 다르면 그 비트가 켜져서 r7 에 눌어붙는다. 한 번 켜진 비트는 OR 로만 쌓이니 절대 안 꺼진다.

그러니 r7 == 0 은 68개 블록이 전부 아래 둘을 만족한다는 뜻이다.

(c & A) == B     그리고     (c | A) == C

🐛 삽질

▶🐛 삽질 1 — AND 제약만 보고 글자를 정하려 했다

블록을 처음 읽었을 때 (c & A) == B 가 눈에 먼저 들어왔다. AND 마스크에 상수를 맞추는 전형적인 꼴이라 여기서 답이 나올 줄 알았다.

안 나온다. A 가 0 인 비트에서는 (c & A) 가 c 와 무관하게 0 이라, 그 자리 c 는 아무 값이어도 제약을 통과한다. 첫 블록만 봐도 A = 0xf3 이니 0 인 비트가 둘, 후보가 넷이다.

얼마나 퍼지는지 실제로 세어 봤다.

#!/usr/bin/env python3
"""삽질 재현 — AND 제약 하나만 보면 글자가 안 정해진다."""
from solve import consts
 
total = 1
for i, (A, B, C) in enumerate(consts):
    free = bin((~A) & 0xFF).count("1")     # A 가 0 인 비트 = 미정 비트
    total *= 1 << free
    if i < 6:
        print("블록 %2d: A=0x%02x B=0x%02x C=0x%02x  미정 비트 %d개 -> 후보 %3d 개"
              % (i, A, B, C, free, 1 << free))
 
print("...")
print("AND 제약만 쓰면 전체 후보 수 = 2^%d" % (total.bit_length() - 1))
print("OR 제약까지 걸어야 c = (A & B) | (~A & C) 로 유일해진다")

python3 naive_and_only.py

naive_and_only.py 실행 — AND 제약만으로는 후보가 2^272 개로 퍼진다

2^272. 브루트포스로 갈 길이 아니다.

여기서 방향을 잘못 잡으면 SMT 솔버를 꺼내게 된다. 실제로 z3 에 두 제약을 다 넣으면 풀리기는 한다. 하지만 그건 필요 없는 도구다. 뒤의 OR 제약이 정확히 이 빈칸만 메우도록 짜여 있다는 걸 알아채면 산술 두 번으로 끝난다.

▶🐛 삽질 2 — 블록 순서대로 이어붙였더니 flag 가 뒤집혀 나왔다

0x28 POP 을 "입력 한 글자를 가져온다" 정도로 읽고 넘어가면 걸린다. 핸들러를 다시 보면 분명히 스택이다.

// 0x1315 — pop()
sp--;
return stack[sp];

0x22 READ 가 68글자를 순서대로 push 하고, 0x28 POP 은 그 반대쪽 끝부터 꺼낸다. 첫 번째 검사 블록이 상대하는 건 입력의 마지막 글자다.

블록 순서 그대로 이어붙이면 어떻게 되는지 찍어 봤다.

#!/usr/bin/env python3
"""삽질 재현 — POP 이 스택이라는 걸 놓치면 어떻게 되나."""
from solve import consts          # solve.py 의 파싱 결과를 그대로 재사용
 
chars = [(A & B) | (~A & C) & 0xFF for A, B, C in consts]
 
print("블록 순서 그대로 :", bytes(chars).decode())
print("뒤집은 것        :", bytes(reversed(chars)).decode())

python3 naive_order.py

naive_order.py 실행 — 뒤집지 않으면 }59e0... 로 시작하는 거울상이 나온다

}59e0d0d2...cb{HD. 다행히 이건 티가 확 난다. flag 가 DH{ 로 시작한다는 걸 알고 있으니 거울상이 나오면 바로 알아챈다. 첫 블록의 상수 셋(A=0xf3 B=0x71 C=0xff)을 손으로 풀어 0x7d = } 가 나오는 걸 확인하는 게 더 빠른 확신이었다.

flag 포맷을 모르는 문제였다면 여기서 한참 헤맸을 것이다.

💣 핵심 — 두 제약이 서로의 사각지대를 정확히 메운다

(c & A) == B 와 (c | A) == C 를 비트 단위로 쪼개면 경우가 둘뿐이다.

A 의 그 비트가 1 인 경우. AND 는 c 를 그대로 통과시킨다. (c & A) 의 그 자리는 c 이므로 c 비트 = B 비트로 못 박힌다. 반면 OR 은 무조건 1 을 만들어 c 에 대해 아무것도 안 알려 준다. (그래서 A 가 1 인 자리에서 C 가 0 이면 그 블록은 애초에 만족 불가능이다.)

A 의 그 비트가 0 인 경우. 이번엔 반대다. AND 는 무조건 0 이라 c 와 무관하고, OR 이 c 를 그대로 통과시켜 c 비트 = C 비트가 된다. (마찬가지로 A 가 0 인 자리에서 B 가 1 이면 만족 불가능이다.)

표로 정리하면 사각지대가 어떻게 엇갈리는지가 한눈에 보인다.

`A` 비트	`(c & A)` 가 알려 주는 것	`(c \| A)` 가 알려 주는 것	`c` 비트 결정
1	`c` 그대로 → `B` 비트와 같아야 함	항상 1 (정보 없음)	`B` 에서
0	항상 0 (정보 없음)	`c` 그대로 → `C` 비트와 같아야 함	`C` 에서

어느 비트를 잡아도 둘 중 정확히 하나가 값을 확정한다. 겹치지도 않고 비지도 않는다.

c = (A & B) | (~A & C)

첫 블록의 상수로 그려 보면 이렇게 된다.

비트 제약 역산 — A=1 자리는 B 에서, A=0 자리는 C 에서 가져와 c 가 하나로 정해진다

A = 0xf3 은 1111 0011. 1 인 여섯 자리는 B = 0x71 에서, 0 인 두 자리는 C = 0xff 에서 가져온다. 조립하면 0111 1101 = 0x7d = }. 첫 블록이 마지막 글자를 검사한다는 것과 정확히 맞아떨어진다.

출제자 입장에서 보면 이 구조는 자연스럽다. 비교 명령이 없는 VM 에서 "이 글자가 정확히 이 값인가"를 물으려면, 한 방향 마스크 하나로는 부족하고 정보를 잃는 방향이 서로 반대인 연산 두 개를 겹쳐야 한다. AND 와 OR 이 딱 그 짝이다. 그리고 그 짝은 역산도 대칭으로 열린다. 막으려고 넣은 구조가 그대로 여는 열쇠가 됐다.

이래서 브루트포스도 솔버도 필요 없다. 68글자 × 산술 두 번, 끝이다.

🎯 런타임 검증 — gdb 로 r7 을 직접 본다

정적 분석만으로 "r7 이 누적기고 0 이어야 한다"까지 왔다. 실제로 그런지는 실행 중에 그 바이트를 눈으로 봐야 확실하다.

바이너리가 stripped PIE 라 브레이크포인트 주소를 손으로 쓸 수 없다. 로드 베이스를 관례로 가정하는 것도 위험해서(환경에 따라 어긋난다), starti 로 한 번 띄운 뒤 info proc mappings 에서 실제 주소를 읽어 계산했다.

set confirm off
set pagination off
set disable-randomization on
 
# stripped + PIE 라 로드 베이스를 관례로 가정하지 않는다.
# starti 로 한 번 띄운 뒤 info proc mappings 에서 실제 주소를 읽어 브레이크포인트를 건다.
starti extracted/command
python
import gdb
maps = gdb.execute("info proc mappings", to_string=True)
base = next(int(l.split()[0], 16) for l in maps.splitlines() if l.rstrip().endswith("/chall"))
print("PIE base           = 0x%x" % base)
print("run() 디스패치 루프 = 0x%x" % (base + 0x1364))
# 0x138f = 0x20(HALT) 분기 안, r0 를 반환값으로 읽어들이는 자리
gdb.execute("break *0x%x" % (base + 0x138f))
end
 
printf "\n===== [1] 복원한 flag 를 넣었을 때 =====\n"
run extracted/command < flag.txt
x/8xb $rbp-0x10
printf "r7(누적 불일치) = 0x%02x  ->  r0(반환값) = 0x%02x\n", *(unsigned char*)($rbp-0x9), *(unsigned char*)($rbp-0x10)
continue
 
printf "\n===== [2] 대조군: DH{aaa...a} 를 넣었을 때 =====\n"
run extracted/command < wrong.txt
x/8xb $rbp-0x10
printf "r7(누적 불일치) = 0x%02x  ->  r0(반환값) = 0x%02x\n", *(unsigned char*)($rbp-0x9), *(unsigned char*)($rbp-0x10)
printf "main 은 이 반환값이 0 일 때만 Correct!!! 를 출력한다\n"

flag.txt 는 복원한 flag, wrong.txt 는 같은 길이의 DH{aaa...a} 를 개행 없이 담은 파일이다.

gdb -q -batch -x verify.gdb ./extracted/chall 2>&1 | grep -v "Thread debugging\|libthread_db"

gdb 런타임 검증 — 정답이면 레지스터 파일 8바이트 중 r7 이 0x00, 오답이면 0x5f

레지스터 파일 8바이트가 그대로 찍힌다. 정답 입력에서는 r0 부터 r7 까지 00 14 04 54 54 00 00 00 — 맨 끝 r7 이 0x00 이고, 그게 r0 에 복사돼 반환된다. 대조군에서는 5f 14 04 54 54 00 00 5f 로 r7 이 0x5f 다.

0x5f = 0101 1111. 68글자를 훑는 동안 여섯 개 비트 자리에서 불일치가 났다는 뜻이다. 누적기가 진짜 OR 로만 쌓인다는 것도 이 값으로 확인된다 — 개별 블록의 차이가 겹쳐 눌어붙은 합집합이다.

중간의 r1~r4 에 남은 값(14 04 54 54)은 마지막 블록의 잔여물이다. 디스어셈블 결과 맨 끝 블록이 SETI r1, 0x14 / SETI r2, 0x04 / SETI r3, 0x54 였으니 정확히 일치한다. 정적으로 읽은 것과 실제 실행이 어긋나지 않았다는 교차 확인이 하나 더 붙은 셈이다.

🚀 Full Exploit

디스어셈블러와 같은 방식으로 command 를 훑되, 이번엔 SETI r1/r2/r3 세 개가 모일 때마다 상수 묶음을 하나씩 뽑는다. 그리고 공식을 적용한 뒤 뒤집는다.

#!/usr/bin/env python3
"""bitvm (Dreamhack, Gold 4 / reversing) - flag 역산.
 
command 바이트코드는 검사 블록 하나를 이렇게 만든다.
 
    SETI r1, A ; SETI r2, B ; SETI r3, C
    POP                       ; r0 = 입력 한 글자 c (스택이라 LIFO)
    AND r4,r0,r1 ; XOR r5,r2,r4 ; OR r7,r5,r7    ; (c & A) ^ B 를 r7 에 누적
    OR  r4,r0,r1 ; XOR r5,r3,r4 ; OR r7,r5,r7    ; (c | A) ^ C 를 r7 에 누적
 
마지막에 MOV r0, r7 / HALT 이고 main 은 r0 == 0 일 때만 "Correct!!!" 를 출력한다.
즉 모든 블록이 아래 둘을 동시에 만족해야 한다.
 
    (c & A) == B     and     (c | A) == C
 
비트별로 보면
    A_i = 1 -> (c&A)_i = c_i = B_i,  (c|A)_i = 1 = C_i
    A_i = 0 -> (c&A)_i = 0 = B_i,    (c|A)_i = c_i = C_i
따라서 c = (A & B) | (~A & C) 로 유일하게 결정된다.
"""
import sys
 
PATH = sys.argv[1] if len(sys.argv) > 1 else "extracted/command"
code = open(PATH, "rb").read()
 
# --- 1) 바이트코드에서 (A, B, C) 3개짜리 SETI 묶음을 순서대로 뽑는다 ---
consts = []
pc = 0
pending = {}
while pc < len(code):
    op = code[pc]
    if op == 0x20:                      # HALT
        break
    elif op == 0x21:                    # PUTC imm
        pc += 2
    elif op == 0x22 or op == 0x28:      # READ / POP
        pc += 1
    elif op == 0x23:                    # SETI r, imm
        pending[code[pc + 1]] = code[pc + 2]
        pc += 3
    elif op == 0x24:                    # MOV d, s
        pc += 3
    elif op in (0x25, 0x26, 0x27):      # AND / OR / XOR  d, a, b
        pc += 4
    elif op == 0x29:                    # PUSH r
        pc += 2
    else:
        raise SystemExit("unknown opcode 0x%02x at 0x%x" % (op, pc))
 
    # r1,r2,r3 이 다 채워지면 한 블록의 상수 세트가 완성된 것
    if {1, 2, 3} <= pending.keys():
        consts.append((pending.pop(1), pending.pop(2), pending.pop(3)))
 
# --- 2) 비트 제약을 풀어 글자를 복원한다 ---
chars = []
for i, (A, B, C) in enumerate(consts):
    if B & ~A & 0xFF:                   # A=0 인 비트에서 B 는 반드시 0
        raise SystemExit("블록 %d 모순: B 에 A=0 비트가 켜져 있음" % i)
    if (~C & A) & 0xFF:                 # A=1 인 비트에서 C 는 반드시 1
        raise SystemExit("블록 %d 모순: C 에 A=1 비트가 꺼져 있음" % i)
    c = (A & B) | (~A & C) & 0xFF
    assert (c & A) == B and (c | A) == C, i
    chars.append(c)
 
# POP 은 LIFO — 첫 블록이 마지막 입력 글자를 검사한다
flag = bytes(reversed(chars))
 
if __name__ == "__main__":
    print("검사 블록 %d 개" % len(consts))
    print("FLAG:", flag.decode())

두 군데를 일부러 방어적으로 짰다.

모순 검사 두 줄은 "이 구조가 정말 내가 읽은 그 구조인가"를 스스로 확인하는 장치다. A 가 0 인 자리에 B 비트가 켜져 있거나 A 가 1 인 자리에 C 비트가 꺼져 있으면 그 블록은 어떤 c 로도 만족될 수 없다. 68블록 전부 안 걸렸으니 해석이 맞은 것이다.

assert 는 복원한 글자를 원래 제약에 도로 넣어 본다. 공식을 옮겨 적다 틀리면 여기서 죽는다.

python3 solve.py extracted/command

solve.py 실행 — 검사 블록 68개에서 flag 68글자가 한 번에 복원된다

DH{bc42e3abb217fa4fd8b8991bc5a378d7dd4421fd887feb797eb759ca2d0d0e95}.

마지막은 배포된 바이너리에 직접 먹여 판정을 받는다. 오답 대조군을 같이 돌려야 "뭘 넣어도 Correct 가 나오는 것 아닌가"라는 의심이 정리된다.

#!/usr/bin/env python3
"""복원한 flag 를 실제 chall + command 에 먹여 판정을 확인한다."""
import subprocess
 
FLAG = "DH{bc42e3abb217fa4fd8b8991bc5a378d7dd4421fd887feb797eb759ca2d0d0e95}"
WRONG = "DH{" + "a" * 64 + "}"
 
for label, s in (("복원한 flag", FLAG), ("대조군(전부 a)", WRONG)):
    r = subprocess.run(["./chall", "command"], input=s,
                       capture_output=True, text=True, cwd="extracted")
    print("[%s] %s" % (label, s))
    print("    -> %s" % r.stdout.strip().splitlines()[-1])

python3 verify.py

verify.py 실행 — 복원한 flag 는 Correct!!!, 대조군은 Wrong.

🔁 재현

문제 폴더에 넣어 둔 한 방 스크립트다. 역산 → flag 출력 → 바이너리 판정까지 스스로 대조하고 ✅ PASS / ❌ FAIL 로 끝난다. 오프라인 문제라 서버가 필요 없고, 결정론적이라 한 번이면 된다.

#!/usr/bin/env bash
# bitvm (DreamHack Gold 4 / reversing) — 한 방 재현.
#   command 바이트코드 역산 -> flag 출력 -> 실제 chall 바이너리로 판정까지 확인.
# 오프라인 문제라 라이브 서버가 필요 없다. 결정론적이라 1회 실행이면 끝난다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
 
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null || cat flag.txt 2>/dev/null || echo '')
 
chmod +x extracted/chall
 
OUT=$(timeout 120 python3 solve.py extracted/command 2>&1) || true
echo "$OUT"
 
FLAG=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
if [ -z "$FLAG" ]; then
  echo; echo "❌ FAIL (solve.py 가 flag 를 뽑지 못했다)"; exit 1
fi
 
# 바이너리에 직접 먹여 Correct!!! 가 나오는지 독립 검증
JUDGE=$(printf '%s' "$FLAG" | (cd extracted && ./chall command) | tail -1)
echo "판정: $JUDGE"
 
if echo "$JUDGE" | grep -q 'Correct!!!' && { [ -z "$EXPECT" ] || [ "$FLAG" = "$EXPECT" ]; }; then
  echo; echo "✅ PASS  $FLAG"; exit 0
fi
echo; echo "❌ FAIL (얻은 값: '${FLAG:-없음}' / 기대: '$EXPECT' / 판정: '$JUDGE')"; exit 1

로컬 환경은 특별한 게 없다. python3 와 objdump(binutils), 런타임 검증용 gdb 면 된다. chall 은 평범한 동적 링크 x86-64 ELF 라 요즘 배포판에서 그대로 돈다.

📝 결론

없는 명령이 곧 설계도다.

VM 문제를 만나면 보통 "무슨 명령이 있나"부터 센다. 이번엔 반대쪽이 훨씬 많은 걸 알려 줬다. 분기가 없다는 건 코드가 직선이라는 뜻이고, 직선이면 68글자 검사는 68벌 펼쳐진 반복 패턴일 수밖에 없다. 비교가 없다는 건 "같다"를 XOR 로 표현했다는 뜻이고, XOR 결과를 모으려면 OR 누적기 말고 쓸 게 없다. 명령 표를 다 뽑기도 전에 안쪽 구조가 절반은 예측됐다.

정보를 잃는 연산도 짝을 지으면 정보를 잃지 않는다.

c & A 는 A 가 0 인 비트를 버리고, c | A 는 A 가 1 인 비트를 버린다. 각각은 되돌릴 수 없지만 버리는 자리가 정확히 반대라서, 둘을 겹치면 원본이 그대로 복원된다. 검사를 튼튼하게 만들려고 제약을 하나 더 얹은 것이 오히려 답을 유일하게 만들어 버렸다. 난독화에서 자주 보는 역설이다.

만들 때는 이런 검사를 쓰지 말 것.

방어 관점에서 보면 이건 클라이언트에 정답을 그대로 들고 있는 구조다. 검사식 상수가 command 파일에 평문으로 68벌 나열돼 있고, 검사가 글자 단위로 독립적이라 서로 섞이지도 않는다. 실무에서 입력 검증을 이렇게 짜면 안 된다. 최소한 검사값은 원본이 아니라 해시로 두고, 글자별로 쪼개지 말고 전체를 한 덩어리로 묶어야 한 글자씩 떼어내는 공격이 막힌다.

stripped PIE 를 gdb 로 붙일 때는 베이스를 읽어서 쓴다.

0x555555554000 은 관례일 뿐 보장이 아니다. starti 로 띄운 다음 info proc mappings 에서 실제 값을 뽑아 오프셋을 더하는 몇 줄이면, 환경이 바뀌어도 같은 스크립트가 그대로 돈다. 이번 검증 스크립트가 그렇게 돼 있고, 덕분에 브레이크포인트를 손으로 고칠 일이 없었다.

[🥇 Gold 4] 점프도 비교도 없는 VM 에서 flag 를 되뽑기 — DreamHack bitvm 풀이

댓글

관련 글

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

[🥉 Bronze 2] .rodata 247바이트가 스택 VM 바이트코드였다 — DreamHack SelfStatus 풀이

[🥇 Gold 4] 파일 커서를 656번 흩뿌린 검증기 되감기 — DreamHack fverify 풀이