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

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

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

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

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

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

심볼이 전부 제거된 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 안을 열어보면 다음과 같은 루프가 나온다(의사코드로 정리).

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

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

세 함수 다 인자 두 개(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을 실제로 파싱해보면 구조가 아주 명확하다.

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라고 하면:

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)가 처음 호출되는 지점에 브레이크포인트를 걸고, 인자값과 반환값이 계산한 대로 나오는지 봤다.

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

🚀 Full Exploit

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

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

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

📝 결론

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

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

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

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