[🥉 Bronze 1] 위치 무관 바이트 변환은 256개짜리 표 하나로 뒤집힌다 — DreamHack ezmix 풀이

문제: DreamHack — ezmix 분류: Reversing 난이도: 🥉 Bronze 1 FLAG: DH{4DD_X0R_R07473_34S1LY_R3V3RS1BL3}

제공되는 건 딱 세 파일이다. stripped ELF main, 그리고 program.bin·output.bin이라는 정체불명의 바이너리 두 개. 실행해보면 Insert your string: 한 줄만 띄우고 입력을 받은 뒤 조용히 끝난다 — 어디에도 정답 여부를 알려주는 출력이 없다. program.bin을 해석해서 실행하는 초소형 바이트코드 VM이라는 걸 파악하고 나면, 풀이는 오히려 산수에 가까워진다.

문제 개요

main은 Usage: %s [program] [output] 형태로 실행되며, program.bin을 읽어 그 안의 명령대로 우리 입력을 변형한 뒤 output 파일에 쓴다. 목표는 반대로 가는 것 — output.bin이 이미 주어졌으니, 그걸 만들어낸 원본 입력(flag)을 거꾸로 찾아내면 된다.

🧩 배경 — 아주 작은 스택 기반 VM

CTF의 리버싱 문제에서 "커스텀 VM"은 흔한 장치다. 실제 로직을 어셈블리 대신 자체 바이트코드로 표현해두고, 인터프리터가 그걸 한 줄씩 해석해서 실행한다. 바이트코드 자체는 데이터라서 정적 분석 도구로 함수 흐름을 못 잡아내니, 분석하려면 인터프리터의 "명령어 하나를 어떻게 처리하는가"부터 읽어야 한다.

이 문제의 바이트코드는 극단적으로 단순하다. program.bin을 2바이트씩 끊어서 (opcode, arg) 쌍으로 읽고, opcode에 따라 정해진 함수 하나를 버퍼 전체에 적용한다. 명령어가 몇 개 없다는 게 오히려 힌트다 — 복잡한 VM일수록 상태가 많아 역산이 어렵지만, 명령어가 산술 연산 몇 개뿐이면 역함수도 산술 연산 몇 개로 끝난다.

🔬 정찰 — stripped 바이너리에서 인터프리터 읽기

먼저 보호기법과 파일 형태를 본다.

file main
pwn checksec main

심볼이 전부 제거된 stripped 바이너리다. 함수 경계도 이름도 없으니 objdump -d로 코드를 처음부터 훑어 흐름을 잡아야 한다. strings로 뽑아보면 Insert your string:, Usage: %s [program] [output], Error! 세 문자열이 나오는데, 이 중 Usage가 가장 중요한 단서다 — main(argc, argv)가 argv[1]을 프로그램 파일로, argv[2]를 출력 파일로 받는다는 뜻이다.

main을 디스어셈블해서 파일 두 개를 어떻게 다루는지 따라가 보면, argv[1]을 열어 최대 0x400바이트를 읽고 그 버퍼(progbuf)와 길이(proglen), 그리고 또 다른 빈 버퍼(outbuf)를 인자로 어떤 함수 하나(주소 0x136c, 이하 vm_run)를 부른다. vm_run 안을 열어보면 다음과 같은 루프가 나온다(의사코드로 정리).

// vm_run(progbuf, proglen, outbuf)
int pc = 0, count = 0;
while (pc < proglen) {
    uint8_t opcode = progbuf[pc];
    uint8_t arg    = progbuf[pc + 1];
    switch (opcode) {
        case 1: apply(add,  arg, outbuf, count); break;  // outbuf[i] += arg  (전부)
        case 2: apply(xor_, arg, outbuf, count); break;  // outbuf[i] ^= arg  (전부)
        case 3: apply(rotr, arg, outbuf, count); break;  // outbuf[i] = ROR8(outbuf[i], arg&7)
        case 4:
            printf("Insert your string: ");
            fgets(outbuf, 0x100, stdin);          // outbuf를 입력으로 통째 교체
            outbuf[strcspn(outbuf, "\n")] = 0;
            count = strlen(outbuf);
            break;
        default:
            puts("Error!"); exit(1);
    }
    pc += 2;
}

여기서 apply(func, arg, buf, count)는 buf의 count바이트 전부에 대해 buf[i] = func(buf[i], arg)를 적용하는 헬퍼다 — 함수 포인터를 받아 콜백처럼 호출하는 게 눈에 띈다.

add/xor_/rotr 세 함수도 각각 objdump로 확인했다.

objdump -d -M intel --start-address=0x1289 --stop-address=0x1301 main | sed -f annotate_ops.sed

세 함수 다 인자 두 개(a, b)를 받아 바이트 하나를 돌려준다.

• op1 = ADD: a + b (mod 256)
• op2 = XOR: a ^ b
• op3 = ROTATE: b를 & 0x7로 마스킹(0~7)한 뒤 (a >> b) | (a << (8-b)) — 바이트 단위 오른쪽 회전(ROR8)

opcode 4는 변환 함수가 아니라 "Insert your string:" 프롬프트로 stdin을 읽어 작업 버퍼 전체를 우리 입력으로 갈아끼우는" 특수 명령이다. 이 순간 버퍼 길이(count)도 우리가 입력한 문자열의 길이로 새로 설정된다.

program.bin을 실제로 파싱해보면 구조가 아주 명확하다.

xxd program.bin | head -3   # 맨 앞 (04 90) = opcode 4, "Insert your string" 트리거
xxd output.bin              # 최종 결과 36바이트

program.bin은 514바이트 = 257쌍인데, 맨 앞 한 쌍만 opcode 4(입력을 받아 버퍼를 초기화)고 나머지 256쌍은 전부 add/xor/rotate 중 하나다. 즉 실행 순서는 "문자열을 입력받는다 → 그 문자열 전체에 256번의 산술 변환을 순서대로 적용한다"가 전부다.

💣 핵심 — 같은 함수가 모든 바이트에 똑같이 적용된다

여기서 눈여겨볼 성질이 하나 있다. apply(func, arg, buf, count)는 buf[i]를 갱신할 때 오직 buf[i] 자기 자신의 현재 값과 고정된 arg만 본다 — 인덱스 i나 다른 바이트의 값은 전혀 참조하지 않는다. 그리고 256개의 변환 단계 전부가 이런 식으로 순서대로 버퍼 전체를 훑는다.

그 말은, 어떤 위치의 바이트든 최종적으로 겪는 변환 과정은 완전히 동일하다는 뜻이다. 입력 문자열의 각 글자는 서로 영향을 주고받지 않고, 오직 "256단계 변환의 합성 함수" 하나만 통과한다.

이 관찰이 풀이의 전부다. 합성 함수를 F라고 하면:

output[i] = F(input[i])       (모든 i에 대해 동일한 F)

F는 8비트 입력을 8비트 출력으로 보내는 함수이므로, 가능한 입력은 0~255, 256가지뿐이다. 그 256가지 전부에 대해 F(x)를 한 번씩 미리 계산해두면(순방향 표), 그 표를 뒤집는 것만으로 역함수 F⁻¹가 그냥 나온다 — add/xor/rotate 세 연산 모두 전단사(bijective, 서로 다른 입력이 서로 다른 출력으로 감)라 역표가 항상 존재한다는 것도 코드를 보면 자명하다(ADD와 XOR는 mod 256에서 자명한 전단사, ROR도 순열일 뿐이다).

즉 입력 길이나 각 글자의 의미를 전혀 몰라도, 표 하나만 만들면 output.bin의 모든 바이트를 즉시 원래 값으로 되돌릴 수 있다.

실행 중에 실제로 그런지 gdb로 직접 확인했다. op3_rotr(ROTATE)가 처음 호출되는 지점에 브레이크포인트를 걸고, 인자값과 반환값이 계산한 대로 나오는지 봤다.

gdb -q -batch -x cmds.gdb --args ./main program.bin /tmp/gdb_verify_out.bin

# cmds.gdb
break *0x555555554000+0x12c2
run program.bin /tmp/gdb_verify_out.bin < flag_input.txt
printf "op3_rotr() call #1 args -- a=0x%x  b=0x%x  (b&7=%d)\n", $edi, $esi, $esi & 7
finish
printf "returned al = 0x%x\n", $eax & 0xff

a=0x92, b&7=3일 때 반환값이 0x52 — 손으로 계산한 (0x92>>3)|(0x92<<5) = 0x12|0x40 = 0x52와 정확히 일치한다. PIE라 로드 주소는 매번 바뀌지만, gdb는 기본적으로 ASLR을 끄고 실행하므로 0x555555554000이 고정 베이스로 잡힌다는 점을 이용했다.

🚀 Full Exploit

program.bin의 첫 쌍(opcode 4)을 건너뛰고, 나머지 256쌍을 순서대로 합성해 정방향 표를 만든 뒤 뒤집는다.

prog = open('program.bin', 'rb').read()
output = open('output.bin', 'rb').read()
 
pairs = [(prog[i], prog[i + 1]) for i in range(0, len(prog) - 1, 2)]
assert pairs[0][0] == 4, "first op must be the input-read trigger"
 
def add(a, b):  return (a + b) & 0xff
def xorf(a, b): return (a ^ b) & 0xff
def rotr(a, b):
    b &= 7
    return ((a >> b) | (a << (8 - b))) & 0xff
 
ops = {1: add, 2: xorf, 3: rotr}
 
def forward(x):
    for op, arg in pairs[1:]:
        x = ops[op](x, arg)
    return x
 
table = [forward(x) for x in range(256)]
inv = [0] * 256
for x in range(256):
    inv[table[x]] = x
 
flag = bytes(inv[b] for b in output)
print(f"[+] FLAG: {flag.decode()}")

복원된 문자열이 정말 원본 입력이었는지는, 그 문자열을 다시 실제 바이너리에 넣어 output.bin과 바이트 단위로 같은 결과가 나오는지 재실행해서 확인했다 — 이게 가장 확실한 검증이다.

./main program.bin /tmp/verify_out.bin < flag_input.txt
cmp /tmp/verify_out.bin output.bin && echo MATCH

MATCH — 정방향 표를 뒤집어 얻은 문자열을 다시 프로그램에 넣었더니 output.bin과 완전히 같은 결과가 나왔다. 이걸로 역산이 맞았다는 게 최종 확정된다.

📝 결론

"복잡해 보이는 변환"과 "실제로 복잡한 변환"은 다르다.

256번이라는 반복 횟수만 보면 겁먹기 쉽지만, 매 단계가 버퍼의 모든 바이트에 완전히 동일한 함수를 적용한다는 걸 알아채는 순간 문제는 "8비트 정의역을 가진 함수의 역함수 찾기"로 축소된다. 정의역이 256개뿐이니 아예 전수조사로 표를 만들면 되고, 역함수가 존재하는지 고민할 필요도 없다 — ADD/XOR/순환이동은 전부 자명하게 가역이다.

바이트코드 인터프리터를 읽을 땐 "무엇이 상태를 넘나드는가"부터 본다. 이 문제에서 핵심은 각 연산의 산술식 자체가 아니라, apply() 헬퍼가 인덱스나 이웃 바이트를 전혀 참조하지 않는다는 구조적 사실이었다. 그 사실 하나가 "위치별로 따로 풀어야 하는 문제"를 "표 하나로 끝나는 문제"로 바꿔놓는다.

방어 관점에서 보면 이 커스텀 암호화(라기보단 인코딩)의 근본적인 약점은 명확하다 — 각 바이트가 서로 독립적으로 변환되는 한, 그 변환이 몇 단계든 결국 하나의 256-엔트리 치환표로 붕괴한다. 진짜 확산(diffusion)을 원한다면 인접 바이트끼리 서로 영향을 주고받는 단계(예: 블록 암호의 믹스 컬럼, 혹은 최소한 순서를 뒤섞는 치환)가 반드시 있어야 한다.