개요
이 문제는 Google Capture The Flag 2025에 출제된 리버싱 문제입니다.
분석
제공되는 파일은 playme 라는 이름의 리눅스 바이너리입니다.
playme: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=a17151d587e7f1c211531244fe4cbe2f33f0da97, for GNU/Linux 3.2.0, stripped바이너리를 실행시키면 다음과 같은 슈팅 게임이 나타납니다. 챌린지 제목인 Asteroids Redux 에서 알 수 있듯이, 이 바이너리는 Atari, Inc. 에서 1979년에 발매한 아케이드 게임인 Asteroids를 유사하게 구현한 것으로 보입니다.
방향키 또는 WASD 키를 사용해 우주선을 조작할 수 있으며, 스페이스바를 눌러 레이저를 발사할 수 있습니다. 레이저가 소행성(불규칙한 다각형 형태)을 맞추면 일정량의 데미지를 입히며, 큰 소행성은 중간 크기 소행성 2개로, 중간 크기 소행성은 작은 소행성 2개로 분해됩니다. 작은 소행성은 맞히면 완전히 파괴됩니다.
소행성의 색은 하늘색, 초록색, 보라색, 핑크색 4종류입니다.
게임에는 약 40초짜리 타이머가 있으며, 시간이 모두 지나면 게임이 종료됩니다. 또는 소행성에 우주선이 충돌하면 GAME OVER 메시지와 함께 게임이 종료됩니다.
게임 로직 찾기
IDA에서 게임 로직을 찾기 위해 GAME OVER 텍스트를 검색해보면 다음과 같은 함수(sub_9B60)가 나옵니다.
__int64 __fastcall sub_9B60(__int64 a1)
{
const char *v2; // rdi
int v3; // edx
__int64 v4; // rax
float v5; // xmm0_4
unsigned __int64 v7; // rdx
__m128i v8; // xmm0
int v9; // eax
_OWORD v10[3]; // [rsp+0h] [rbp-58h] BYREF
__int16 v11; // [rsp+30h] [rbp-28h]
if ( *(_BYTE *)a1 )
{
if ( *(_QWORD *)(a1 + 8) <= 0x95Fu )
{
v2 = "GAME OVER";
v3 = sub_7BBCC("GAME OVER", 30);
}
else
{
v2 = "TIME'S UP";
v3 = sub_7BBCC("TIME'S UP", 30);
}
sub_7B73A(v2, (unsigned int)(int)(float)(400.0 - (float)(v3 / 2)), 300, 30, 4278231551LL);
// ---------- Important: 0x7B465443 == "CTF{"
if ( *(_DWORD *)(a1 + 872) == 0x7B465443 && *(_BYTE *)(a1 + 903) == 125 )
{
v10[2] = 0;
v8 = _mm_loadu_si128((const __m128i *)(a1 + 872));
v11 = 0;
v10[0] = v8;
v10[1] = _mm_loadu_si128((const __m128i *)(a1 + 888));
v9 = sub_7BBCC(v10, 16);
sub_7B73A(v10, (unsigned int)(int)(float)(400.0 - (float)(v9 / 2)), 330, 16, 4281805286LL);
}
}
v4 = 2400LL - *(_QWORD *)(a1 + 8);
if ( v4 < 0 )
{
v7 = v4 & 1 | ((unsigned __int64)(2400LL - *(_QWORD *)(a1 + 8)) >> 1);
v5 = (float)(int)v7 + (float)(int)v7;
}
else
{
v5 = (float)(int)v4;
}
return sub_34850(0, 0, (unsigned int)(int)(float)(v5 / 3.0), 6, 4281805286LL);
}이 함수는 게임 오버, 타임 아웃 등을 처리하는 것으로 보이는데, 중간에서 *(_DWORD *)(a1 + 872)를 0x7B465443과 비교하는 흥미로운 부분을 찾을 수 있습니다. 이는 문자열로 "CTF{"에 해당합니다. 또 *(_BYTE *)(a1 + 903)을 125('}')와 비교하는 것도 알 수 있습니다.
따라서, 이는 a1 + 872에서 a1 + 903까지의 32 Bytes 데이터가 플래그인지 검사하는 로직이라고 추측할 수 있습니다. 또한 이 프로그램은 게임 플레이 중 특정 조건이 충족되었을 때, 해당 공간에 플래그를 쓰는 로직을 어딘가에 가지고 있다고 추측할 수 있습니다.
메인 함수 분석
xref를 통해 sub_9B60은 main 함수에서 호출된다는 것을 알 수 있습니다. 호출 부분을 확인해 보면 sub_9B60의 첫번째 매개변수인 a1에 해당하는 값은 main 함수에서 _QWORD v56[115]; 라는 것을 알 수 있습니다.
__int64 __fastcall main(int a1, char **a2, char **a3)
{
unsigned int v3; // eax
__int64 v4; // rax
char *v5; // rsi
int v6; // edx
int v7; // ecx
int v8; // r8d
int v9; // r9d
int v10; // edx
int v11; // ecx
int v12; // r8d
int v13; // r9d
int v14; // edx
int v15; // ecx
int v16; // r8d
int v17; // r9d
int v18; // edx
int v19; // ecx
int v20; // r8d
int v21; // r9d
__m128i v22; // xmm0
_QWORD *v23; // rdi
__int64 v24; // rdx
__int64 v25; // rcx
__int64 v26; // r8
__int64 v27; // rdx
__int64 v28; // rcx
__int64 v29; // r8
__int64 v30; // rdx
__int64 v31; // rcx
__int64 v32; // r8
__int64 v33; // rdx
__int64 v34; // rcx
__int64 v35; // r8
__int64 v36; // rdx
__int64 v37; // rcx
int v38; // r8d
int v39; // r9d
int v40; // edx
int v41; // ecx
int v42; // r8d
int v43; // r9d
__m128i v45; // [rsp+0h] [rbp-448h]
__m128i v46; // [rsp+0h] [rbp-448h]
__m128i v47; // [rsp+0h] [rbp-448h]
__int128 v48; // [rsp+20h] [rbp-428h] BYREF
__int128 v49; // [rsp+30h] [rbp-418h] BYREF
int v50; // [rsp+40h] [rbp-408h]
__m128i v51; // [rsp+50h] [rbp-3F8h] BYREF
int v52; // [rsp+60h] [rbp-3E8h]
_BYTE v53[32]; // [rsp+70h] [rbp-3D8h] BYREF
__m128i v54; // [rsp+90h] [rbp-3B8h] BYREF
__int64 v55; // [rsp+A0h] [rbp-3A8h]
_QWORD v56[115]; // [rsp+B0h] [rbp-398h] BYREF
v3 = time(0);
srand(v3);
v49 = 0;
memset(v56, 0, 0x388u);
v48 = 0;
v50 = 0;
v56[2] = sub_8CC0(v53, a2);
v4 = sub_8D50(0.0);
v56[5] = &v48;
v56[3] = v4;
v56[4] = &v49;
sub_9DD0((__int64)v56);
sub_2CDD0(32);
sub_319CE(800, 600, "Asteroids Redux");
v5 = ".png";
sub_6227A(&v54, ".png", &unk_DB4E0, (unsigned int)dword_DB4C4);
v45 = _mm_load_si128(&v54);
if ( !(unsigned __int8)sub_629CA(
(unsigned int)&v54,
(unsigned int)".png",
v6,
v7,
v8,
v9,
v45.m128i_i64[0],
v45.m128i_i64[1],
v55) )
{
v5 = (_BYTE *)(&dword_0 + 1);
fwrite("Image is not valid\n", 1u, 0x13u, stderr);
}
v46 = _mm_load_si128(&v54);
sub_66E56((unsigned int)&v51, (_DWORD)v5, v10, v11, v12, v13, v46.m128i_i64[0], v46.m128i_i64[1], v55);
v47 = _mm_load_si128(&v51);
if ( !(unsigned __int8)sub_6708B(
(unsigned int)&v51,
(_DWORD)v5,
v14,
v15,
v16,
v17,
v47.m128i_i64[0],
v47.m128i_i64[1],
v52) )
{
fwrite("Spritesheet texture is not valid\n", 1u, 0x21u, stderr);
exit(1);
}
v22 = _mm_load_si128(&v51);
sub_671E8(1, (_DWORD)v5, v18, v19, v20, v21, v22.m128i_i32[0], v22.m128i_i32[2]);
v23 = (_QWORD *)&word_3C;
sub_2CB51(60);
while ( !(unsigned __int8)sub_278D7(v23, v5, v24, v25, v26) )
{
sub_29C63(v23, v5, v30, v31, v32);
sub_29C3A(4278190080LL);
v56[6] = sub_28249(4278190080LL, v5, v33, v34, v35);
if ( !LOBYTE(v56[0]) )
{
if ( ++v56[1] > 0x960u )
{
LOBYTE(v56[0]) = 1;
*(_BYTE *)(v56[4] + 16LL) = 1;
}
sub_9CE0((__int64)v56, (__int64)v5, v36, v37, v38, v39);
if ( *(double *)&v56[6] - *(double *)&v56[7] > 5.0 )
{
sub_9000(v56);
v56[7] = v56[6];
}
sub_9370(v56);
}
sub_9230((__int64)v56);
sub_9710(v56);
if ( LOBYTE(v56[0]) )
{
sub_98D0(v56);
if ( (unsigned __int8)sub_2F4F3(82) )
sub_9DD0((__int64)v56);
}
sub_99E0((__int64)v56, (__int64)v5, v40, v41, v42, v43, _mm_load_si128(&v51));
v23 = v56;
sub_9B60((__int64)v56);
sub_2F8B3(v56, v5, v27, v28, v29);
}
return 0;
}플래그 설정 로직 찾기
main 함수가 v56을 인자로 넣어서 호출하는 다른 함수를 조사해보면 a1 + 872에 플래그를 쓰는 로직을 찾을 수 있을 것이라는 가정하에 main 함수를 조사해보면 sub_9CE0 함수를 발견할 수 있습니다. 이 함수에서도 마찬가지로 첫번째 매개변수 a1이 main 함수의 v56에 해당합니다.
unsigned __int64 __fastcall sub_9CE0(__int64 a1, __int64 a2, __int64 a3, __int64 a4, int a5, int a6)
{
unsigned __int64 result; // rax
__int64 *v7; // rax
char v8; // dl
__int64 v9; // rax
__int16 v10; // [rsp+0h] [rbp-100h] BYREF
char v11; // [rsp+2h] [rbp-FEh]
int v12; // [rsp+3h] [rbp-FDh]
__m128i v13; // [rsp+8h] [rbp-F8h] BYREF
__int128 v14; // [rsp+18h] [rbp-E8h] BYREF
_BYTE v15[216]; // [rsp+28h] [rbp-D8h] BYREF
result = __ROR8__(0x2FC962FC962FC963LL * *(_QWORD *)(a1 + 8), 2);
if ( result <= 0xDA740DA740DA74LL )
{
v7 = *(__int64 **)(a1 + 40);
v10 = *((_WORD *)v7 + 4);
v8 = *((_BYTE *)v7 + 10);
v9 = *v7;
v13 = 0;
v11 = v8;
v14 = 0;
v12 = v9;
sub_A6A0((unsigned __int8 *)&v10, 7, &v13, a4, a5, a6);
*(__m128i *)(a1 + 872) = _mm_load_si128((const __m128i *)&xmmword_DB4A0);
*(__m128i *)(a1 + 888) = _mm_load_si128(&xmmword_DB4B0);
sub_B270((__int64)v15, (__int64)&v13);
sub_B2D0((__int64)v15, a1 + 872);
sub_B270((__int64)v15, (__int64)&v14);
return sub_B2D0((__int64)v15, a1 + 888);
}
return result;
}main 함수에서 호출하는 부분을 보면, 호출 전에 ++v56[1] > 0x960을 체크하고, 어떤 플래그(상태)를 설정하고 있습니다.
if ( !LOBYTE(v56[0]) )
{
if ( ++v56[1] > 0x960u )
{
LOBYTE(v56[0]) = 1;
*(_BYTE *)(v56[4] + 16LL) = 1;
}
sub_9CE0((__int64)v56, (__int64)v5, v36, v37, v38, v39);
if ( *(double *)&v56[6] - *(double *)&v56[7] > 5.0 )
{
sub_9000(v56);
v56[7] = v56[6];
}
sub_9370(v56);
}v56[1]에 해당하는 값은 sub_9EC0에서 동작 여부를 결정하는 것으로 보입니다.
result = __ROR8__(0x2FC962FC962FC963LL * *(_QWORD *)(a1 + 8), 2);
if ( result <= 0xDA740DA740DA74LL )
{
// ...
}앞서 본 ++v56[1] > 0x960을 근거로 0x960 = 2400을 최댓값으로, 1을 최소값으로 간주하여 모든 정수를 대입해보면 해당 조건을 충족하는 값은 300, 600, 900, 1200, 1500, 1800, 2100, 2400 입니다.
이 값의 의미를 알아보기 위해 GDB로 main 함수가 sub_9CE0을 호출하는 부분에 breakpoint를 걸어 보면, 1부터 시작하여 매번 1씩 증가한다는 것을 확인할 수 있습니다. 여기서 떠오르는 것은 게임의 Tick 인데, 해당 조건문 안에 breakpoint를 걸고 게임을 실행하면서 멈추는 타이밍을 관찰해 보면 대략적으로 맞는 것 같다는 느낌이 듭니다. 그러므로 sub_9CE0은 300, 600, 900, ... tick에서 특정 동작을 수행하는 루틴입니다.
sub_9CE0에서 사용하는 main 함수의 v56(이하 v56)내부의 또 다른 값은 다음과 같습니다.
*(__int64*)(v56[40])(8바이트)*((_WORD *)(v56[40]) + 4)(2바이트)*((_BYTE *)(v56[40]) + 10)(1바이트)
간단하게 생각해 보면 (void*)v56[40] 부터 11바이트입니다. 이 값에 watchpoint를 걸어서 실시간 메모리 변화를 추적해보면 다음과 같은 사실을 알 수 있습니다.
*(__int64*)(v56[40])는 가장 작은 소행성을 소멸시켰을 때 증가하며, 각 색깔별로 점수가 다릅니다. 하늘색은0x37faf5, 초록색은0x4bfa37, 보라색은0x6455ff, 핑크색은0xc855ff입니다.*((_WORD *)(v56[40]) + 4)와*((_BYTE *)(v56[40]) + 10)는 사실 하나의 4바이트 정수의 하위 3바이트로 보이며, 의미는 레이저를 발사했을 때 그 결과에 따라 얻는 점수입니다.- 가장 작은 크기가 아닌 소행성을 맞춤:
+0x10000 - 소행성을 맞추지 못했음:
+0x100 - 가장 작은 소행성을 맞춤(=소멸):
+0x1
- 가장 작은 크기가 아닌 소행성을 맞춤:
sub_9CE0은 해당 11바이트 값(소행성 소멸 점수 + 레이저 점수)을 처리하여 a1 + 872에 플래그를 설정하는 것으로 보이는데, GDB로 확인해보면 같은 11바이트 값은 sub_9CE0의 호출 시점이나 기타 상태에 관계없이 항상 같은 플래그를 생성합니다.
풀이
이제 모든 것이 명확합니다. 올바른 소행성 소멸 점수와 레이저 점수는 CTF{로 시작하여 }로 끝나는 올바른 플래그를 생성하고, 처음에 본 sub_9B60 함수에서 이 포맷을 검사하여 플래그를 출력하고 종료하는 것이 핵심으로 보입니다. 이를 이용하여 Brute-force 기반으로 풀이하기로 결정했습니다.
경험적으로 추측해본 결과, 매우 열심히 플레이한다면 타임아웃 전에 소행성을 최대 36개 정도 소멸시킬 수 있을 것으로 보였습니다. 각각 하늘색, 초록색, 보라색, 핑크색의 소행성을 소멸시킨 횟수를 N, M, O, P로 정의한다면 수식은 다음과 같습니다.
(0x37faf5 * N + 0x4bfa37 * M + 0x6455ff * O + 0xc855ff * P) & 0xffffffff = score
1 <= N + M + O + P <= 36마찬가지로 경험적으로 추측해본 결과, 매우 열심히 레이저를 발사하면 제한시간 동안 256번 정도 발사 가능해 보였습니다. 가장 작은 소행성을 제외한 소행성에 맞은 레이저의 개수를 Q, 소행성에 맞지 않은 레이저의 개수를 R로 정의한다면 수식은 다음과 같습니다. (가장 작은 소행성에 맞은 레이저의 개수는 (N + M + O + P) * 0x1과 같기 때문에 따로 정의하지 않습니다)
(0x10000 * Q) + (0x100 * R) + (N + M + O + P) = laser_score
1 <= Q + R <= 256지금까지의 정보를 ChatGPT에게 주고 경우의 수를 계산해 본 결과 약 3,029,852,670회의 대입이 필요하다는 결론이 나왔습니다. GDB Script나 기타 후킹 방법은 너무 느리기 때문에 사용할 수 없으며, sub_9CE0을 호출하기 직전의 메모리 상태에서 프로세스가 직접 기계어 코드를 실행하여 sub_9CE0에 대한 Brute-force를 수행하는 것이 가장 효율적인 방법이라고 판단했습니다.
우선 간단히 tick을 300(sub_9CE0의 동작 조건을 통과하는 최소 tick)으로 만들어서 프로세스를 Brute-force를 실행할 준비가 된 상태로 만들어주는 GDB Script를 작성하였습니다.
# ready.py
gdb.execute('set pagination off')
gdb.execute('file playme')
gdb.execute('starti')
gdb.execute('b* 0x555555554000 + 0x89F6')
cnt = 0
while True:
gdb.execute('c')
cnt += 1
if cnt == 300:
break
gdb.execute('del 1')그 다음 mmap 시스템 호출로 실행 가능한 페이지를 프로세스에 할당하고 바이너리 코드를 복사해주는 GDB Script를 LLM에게 요청하여 빠르게 생성하였습니다.
# injectcode.py
import gdb
import os
import struct
class InjectCodeCommand(gdb.Command):
"""Inject a binary file into the debugged process's memory using mmap.
Usage: injectcode <binary_filename>
"""
def __init__(self):
super(InjectCodeCommand, self).__init__("injectcode", gdb.COMMAND_USER)
def invoke(self, arg, from_tty):
args = gdb.string_to_argv(arg)
if len(args) != 1:
print("Usage: injectcode <binary_filename>")
return
filename = args[0]
try:
with open(filename, "rb") as f:
data = f.read()
except IOError as e:
print(f"Could not read file '{filename}': {e}")
return
length = len(data)
print(f"[+] Read {length} bytes from {filename}")
mmap_call = ("mmap(0, {}, 7, 0x22, -1, 0)".format(length))
try:
result = gdb.parse_and_eval(f"(void *){mmap_call}")
addr = int(result)
except Exception as e:
print(f"[-] mmap failed: {e}")
return
if addr == 0:
print("[-] mmap returned NULL")
return
print(f"[+] Allocated memory at 0x{addr:x}")
inferior = gdb.selected_inferior()
try:
inferior.write_memory(addr, data)
except Exception as e:
print(f"[-] Failed to write to memory: {e}")
return
print(f"[+] Injected code into 0x{addr:x}")
print(f"[+] Use 'x/{length}xb 0x{addr:x}' to examine memory")
InjectCodeCommand()그 다음 Brute-force를 수행하는 PIC 어셈블리 코드를 Gemini를 이용하여 빠르게 생성하였습니다.
bits 64
%define MAX_NMOP 36
%define MAX_QR 256
%define TARGET_FUNC 0x55555555dce0
%define STDOUT 1
%define SYS_WRITE 1
%define SYS_EXIT 60
%define SUCCESS_STR 0x7b465443
section .text
global bruteforce_entry
bruteforce_entry:
push rbp
push rbx
push r12
push r13
push r14
push r15
mov rbp, rdi
mov rbx, [rbp + 40]
xor r12, r12
q_loop:
xor r13, r13
r_loop:
xor r8, r8
n_loop:
xor r9, r9
m_loop:
xor r10, r10
o_loop:
xor r11, r11
p_loop:
mov rax, 0x37faf5
imul rax, r8
mov rcx, 0x4bfa37
imul rcx, r9
add rax, rcx
mov rcx, 0x6455ff
imul rcx, r10
add rax, rcx
mov rcx, 0xc855ff
imul rcx, r11
add rax, rcx
mov qword [rbx], rax
mov rax, r12
shl rax, 16
mov rcx, r13
shl rcx, 8
add rax, rcx
mov rcx, r8
add rcx, r9
add rcx, r10
add rcx, r11
add rax, rcx
mov dword [rbx + 8], eax
push r8
push r9
push r10
push r11
mov rdi, rbp
mov rax, TARGET_FUNC
call rax
pop r11
pop r10
pop r9
pop r8
cmp dword [rbp + 872], SUCCESS_STR
jne p_loop_continue
mov rax, SYS_WRITE
mov rdi, STDOUT
lea rsi, [rbp + 872]
mov rdx, 32
syscall
p_loop_continue:
inc r11
mov rax, MAX_NMOP
sub rax, r8
sub rax, r9
sub rax, r10
cmp r11, rax
jle p_loop
o_loop_continue:
inc r10
mov rax, MAX_NMOP
sub rax, r8
sub rax, r9
cmp r10, rax
jle o_loop
m_loop_continue:
inc r9
mov rax, MAX_NMOP
sub rax, r8
cmp r9, rax
jle m_loop
n_loop_continue:
inc r8
cmp r8, MAX_NMOP
jle n_loop
r_loop_continue:
inc r13
mov rax, MAX_QR
sub rax, r12
cmp r13, rax
jle r_loop
q_loop_continue:
inc r12
cmp r12, MAX_QR
jle q_loop
exit_program:
mov rax, SYS_EXIT
xor rdi, rdi
syscall이제 준비는 끝났습니다. GDB에서 ready.py를 실행한 후 injectcode.py를 실행하여 injectcode 명령을 등록시키고 injectcode bruteforce.bin으로 Brute-force 코드를 메모리에 할당하고, set $rip = <addr>로 RIP 레지스터를 설정하고 continue를 하면 자동으로 Brute-force가 실행되고 플래그가 약 30분 안으로 나오게 됩니다.
플래그
CTF{upDN_B_a_im_ur_pRoOf_0f_p1y}Authored by @liberty_rapid
