[🥇 Gold 2] .rela.tivity — 재배치 테이블이 곧 암호문이었다, DreamHack Theori of Relativity 풀이 (2번 보류 끝에 해결)

문제: DreamHack — Theori of Relativity 분류: Reversing 난이도: 🥇 Gold 2 FLAG: DH{1d459fbdd85803e8223c2a11604dac728aceaffbc454aedce56b1a8d4e063360}

이 문제는 세 번째 시도에서 풀렸다. 지난 두 세션은 검증에 쓰이는 104바이트짜리 메모리 블록이 파일에 저장된 값과 실행 중 값이 완전히 다르다는 것까지는 확인했지만, "그 값을 대체 어디서 바꾸는지" 찾지 못하고 두 번 다 보류했다. 오늘 다시 붙어서 알게 된 사실은, 애초에 그걸 바꾸는 함수 자체가 없다는 것이었다 — 범인은 코드가 아니라 ELF를 로드하는 과정 그 자체였다.

문제 개요

file/checksec로 기본 정보부터 확인했다. PIE, Full RELRO, 카나리, NX가 켜진 흔한 조합의 작은 바이너리다. 실행하면 키를 입력받고 맞았는지 틀렸는지만 알려준다.

objdump로 흐름을 따라가면 구조는 단순하다. main이 fgets로 최대 100바이트를 입력받고 개행을 제거한 뒤, 검증 함수 하나를 rdi=&0x6020(어떤 104바이트 메모리 블록의 시작), rsi=사용자 입력으로 호출한다. 반환값이 참이면 "Congrats! Flag is DH{%s} ...if you didn't cheat!"를 출력한다.

문제는 0x6020이라는 주소다. 이 주소는 .data 섹션 안에 있는데, 파일에 저장된 원본 바이트와 실제 실행 중인 값이 전혀 다르다. 지난번에는 이 차이를 만드는 코드를 .init_array에 등록된 생성자 두 개(뒤에서 다시 나온다) 안에서 찾으려고 했지만 끝내 못 찾았다.

▶🕳️ 삽질 — 지난 두 세션, '바꾸는 함수'를 찾다가 못 찾고 보류했다

지난번 기록을 다시 읽어보면, 두 가지를 이미 정확히 알아낸 상태였다.

1. .init_array에 등록된 함수 하나가 ptrace(PTRACE_TRACEME, 0, 0, 0)을 호출해서, 실패(디버거가 붙어있거나 이 샌드박스의 알 수 없는 제약으로 EPERM)하면 0x6020 주소의 1바이트에 +1을, 성공하면 -1을 한다.
2. 또 다른 생성자가 세 함수(자기 자신 포함)의 코드를 바이트 단위로 훑어서 0xCC(소프트웨어 브레이크포인트)가 있는지 찾고, 있으면 그 1바이트에 +2, 깨끗하면 -2를 한다.

여기까지는 정확했다. 문제는 그다음이었다 — gdb로 0x6020부터 32바이트를 파일 원본과 대조해보니, 1바이트가 아니라 블록 전체가 완전히 다른 값으로 바뀌어 있었다. 두 생성자는 분명 딱 1바이트만 ±1/±2 하는 코드인데, 104바이트 전체가 스크램블돼 있다는 건 이 두 함수 말고 제3의 로직이 있다는 뜻이었다. .init_array를 다시 훑고, objdump 전체를 다시 읽고, 검증 함수 내부에 복호화 스텝이 섞여 있는지도 확인했지만 끝내 그런 코드를 찾지 못했다. "네트 조정값이 0일 것"이라는 추측으로 만든 후보 flag(with_LOVE_from_Dreamhack_:))도 그럴듯한 영어 문구였지만 실제로는 오답이었다.

이번에 다시 파일을 열어보고 나서야 놓쳤던 부분을 찾았다. readelf -S로 섹션 목록을 쭉 훑다가 낯선 이름 하나가 눈에 띄었다 — .rela.tivity. "Theori of Relativity"라는 문제 제목의 말장난이 섹션 이름에도 그대로 박혀 있었다.

정상적인 ELF라면 재배치 테이블(RELA 타입)은 읽기 전용이고, 실행에 필요한 개수만큼만 있어야 한다. .rela.tivity는 400개(!)의 항목을 담고 있고 WA(쓰기 가능+로드됨) 플래그까지 붙어 있다 — 전형적이지 않다. 그리고 결정적인 단서는 .dynamic 세그먼트의 DT_RELASZ 값이었다. 9864바이트 — 이건 .rela.dyn(264바이트, 진짜 재배치 11개)과 .rela.tivity(9600바이트, 400개)를 더한 값과 정확히 일치한다. 즉 동적 링커(ld.so)는 이 둘을 하나로 이어진 재배치 테이블로 인식하고, .rela.tivity의 400개 항목까지 전부 실제로 처리한다는 뜻이다.

지난 두 세션이 찾아 헤맸던 "104바이트를 바꾸는 코드"는 애초에 존재하지 않았다 — 바꾸는 주체는 함수가 아니라 프로그램이 시작되기도 전에 동작하는 동적 링커 자신이었다.

💣 핵심 1 — 로더가 실행되기도 전에 이미 "암호화"가 끝나 있다

이 가설을 직접 확인해봤다. gdb로 프로그램의 진입점(.init_array 생성자들이 실행되기 전, 사실상 프로그램에서 가장 먼저 실행 가능한 지점)에 브레이크포인트를 걸고, 그 시점의 0x6020 메모리를 파일 원본과 나란히 비교했다.

이 시점엔 .init_array의 어떤 함수도 아직 실행되지 않았는데도 값이 이미 바뀌어 있다. 지난번엔 아무리 코드를 뒤져도 "바꾸는 함수"를 못 찾은 게 당연했다 — ld.so가 프로그램 자신의 코드를 실행시키기 전에, 재배치 처리 단계에서 이미 이 블록을 자신의 알고리즘(각 항목의 r_offset, r_addend를 이용한 위치 계산)으로 덮어써버린 것이다. 저 400개의 "가짜 재배치 항목"이 바로 이 104바이트를 만들어내는 암호문/키 스트림이었던 셈이다.

이 트릭 자체를 처음부터 역산해서 완전히 재현하는 건 상당히 손이 많이 가지만(각 R_X86_64_PC32 항목의 S+A-P 계산을 항목별로 되짚어야 한다), 다행히 그럴 필요가 없다 — ld.so가 이미 정확하게 계산해준 최종 결과값을 그대로 읽으면 된다. 우리가 할 일은 그 완성된 104바이트를 gdb로 확보하는 것뿐이다.

💣 핵심 2 — 검증 알고리즘은 사실 "input[i] == b1[i]"로 요약된다

검증 함수(main이 호출하는 곳)를 처음부터 다시 정독했다.

핵심은 세 가지다.

1. b1 = (i*i + key[i]) & 0xff — key[i]는 방금 확보한 104바이트 블록의 i번째 바이트다.
2. 매 반복마다 i가 짝수면 (b1 - input[i]) & 0xff를, 홀수면 b1 ^ input[i]를 128비트 누산합에 더한다. 두 연산 다 결과가 0이 되는 조건은 똑같다 — input[i] == b1[i]. (뺄셈이 0이려면 두 값이 같아야 하고, XOR이 0이려도 두 값이 같아야 한다.)
3. popcnt(b1) == 0(즉 b1이 정확히 0)이 되는 순간 루프가 종료된다. 이때는 input[i]를 비교하는 대신 popcnt(input[i])를 그대로 더한다 — 이게 0이 되려면 input[i]가 정확히 0x00이어야 한다.

누산합에 들어가는 모든 항이 음수가 될 수 없는 바이트값이라는 게 결정적이다. 최종 판정은 "누산합이 정확히 0인가"이므로, 더해진 모든 항이 예외 없이 0이어야만 통과한다. 정리하면: b1이 0이 아닌 모든 위치에서는 입력 문자가 b1과 정확히 같아야 하고, b1이 처음으로 0이 되는 위치에서는 입력이 정확히 널 바이트여야 한다 — 이건 fgets + strcspn으로 개행을 제거한 문자열의 **자연스러운 끝(널 종단자)**과 정확히 같은 자리다. 즉 flag의 길이 자체가 키 스트림에 의해 결정되고, flag 내용은 그 길이만큼 b1 값을 그대로 나열한 것이다.

🎯 자체 완결 solve

gdb로 확보한 104바이트를 그대로 파이썬에 넣고, 알고리즘을 그대로 재현했다.

key = open('/tmp/keyblock.bin', 'rb').read()   # gdb dump binary memory 로 확보한 104바이트
flag = bytearray()
for i in range(len(key)):
    b1 = (i * i + key[i]) & 0xff
    if b1 == 0:
        break                     # 여기가 곧 flag 길이
    flag.append(b1)

이 값을 검증 함수 안에서 한 스텝씩 실측하며 정확히 맞는지 직접 확인했다 — i마다 key[i]로 계산한 b1과 실제로 main이 읽어들인 입력 바이트가 매 순간 일치하는지, 루프가 정말 i=64에서 끝나는지까지.

여기까지는 문제없이 맞아떨어졌다. 그런데 이 흐름으로 만든 flag를 gdb 없이 그냥 터미널에서 직접 실행했더니 통과하지 못했다.

원인은 바로 그 1바이트짜리 카운터(0x6020)였다 — ptrace(PTRACE_TRACEME)의 성공/실패에 따라 ±1이 갈리는 그 값이다. gdb로 실행하면 gdb 자신이 이미 이 프로세스의 tracer이기 때문에, 자식 프로세스가 다시 PTRACE_TRACEME를 호출하면 "이미 추적 중"이라는 이유로 실패(EPERM)한다 — 디버거 유무와 무관하게 이 샌드박스에서 관찰됐던 "정체불명의 ptrace 실패"가, 사실은 gdb 자신이 만들어낸 현상이었을 가능성이 높다. 반면 아무 도구도 없이 순수하게 실행하면 PTRACE_TRACEME가 정상적으로 성공한다 — gdb로 관찰한 값과 실제 "야생"의 값이 다르다는 뜻이다.

문제는 이 1바이트를 ptrace를 건드리지 않고 확인할 방법이 필요하다는 것이었다. strace도 결국 ptrace 기반 트레이서라 gdb와 같은 문제를 일으킨다. 대신 LD_PRELOAD로 fgets만 살짝 가로채는 작은 훅을 만들었다 — 이건 동적 링커의 심볼 바인딩을 이용하는 것일 뿐, ptrace 관계를 전혀 만들지 않는다.

static char *(*real_fgets)(char*, int, FILE*) = NULL;
 
char *fgets(char *s, int n, FILE *stream) {
    if (!real_fgets) real_fgets = dlsym(RTLD_NEXT, "fgets");
    if (stream != stdin) return real_fgets(s, n, stream);
 
    FILE *maps = fopen("/proc/self/maps", "r");
    unsigned long base = 0;
    char line[512];
    while (real_fgets(line, sizeof(line), maps)) {
        if (strstr(line, "relativity") && base == 0) {
            sscanf(line, "%lx-", &base);
            break;
        }
    }
    fclose(maps);
    unsigned char *p = (unsigned char*)(base + 0x6020);
    fprintf(stderr, "[peek] base=%p byte0=0x%02x\n", (void*)base, p[0]);
    return real_fgets(s, n, stream);
}

main이 사용자 입력을 받으려고 fgets(stdin, ...)을 호출하는 순간(이미 두 생성자가 다 실행되고 난 뒤) 이 훅이 끼어들어, /proc/self/maps로 자기 자신의 로드 베이스를 알아낸 뒤 0x6020의 1바이트를 출력하고 원래 fgets로 넘어간다.

0x31. gdb로 관찰했을 때의 0x33과 정확히 2만큼 다르다 — +1(ptrace 실패, gdb 환경) 대 -1(ptrace 성공, 순수 환경)의 차이가 그대로 드러난 것이다. 이 값으로 key[0]만 갈아끼워 flag를 다시 계산했다.

DH{1d459fbdd85803e8223c2a11604dac728aceaffbc454aedce56b1a8d4e063360}

이번엔 어떤 도구도 없이, 순수하게 파일을 리다이렉트해서 실행했다.

세 번을 반복 실행해도 동일하게 통과하는 걸 확인한 뒤 드림핵에 제출해 "정답! 해결 처리됨"으로 확정됐다.

📝 결론

이 문제가 남긴 교훈은 두 층위 모두에서 흥미로웠다.

• 재배치 테이블은 "안전한 메타데이터"가 아니라 프로그램이 시작되기도 전에 임의의 메모리를 채워 넣을 수 있는 강력한 실행 지점이다. .dynamic의 DT_RELASZ가 어디까지를 "진짜" 재배치 범위로 잡는지 확인하지 않으면, 이런 식으로 정상 섹션 옆에 이어붙인 가짜 재배치 데이터가 실제로 처리되고 있다는 걸 놓치기 쉽다. 코드에서 "이 메모리를 바꾸는 함수"를 아무리 찾아도 안 나온다면, 애초에 함수가 아니라 로더 단계를 의심해봐야 한다.
• "코드 자체를 실행하지 않고 값을 관찰하는" 우회는 파일 정적 분석만으로는 부족할 때가 있다 — 이번엔 ld.so가 계산을 대신 해주는 게 가장 빠른 방법이었다. 손으로 400개 재배치 항목의 위치 연산을 전부 재현하는 대신, gdb로 "이미 계산이 끝난 시점"의 메모리를 그대로 읽는 게 훨씬 안전하고 빨랐다.
• ptrace 기반 안티디버그를 관찰할 때, 관찰 도구 자신이 이미 하나의 ptrace 관계를 만든다는 사실을 잊기 쉽다. gdb도 strace도 전부 대상 프로세스의 tracer가 되기 때문에, 대상이 스스로 PTRACE_TRACEME를 호출하면 "이미 추적되고 있다"는 이유로 실패한다 — 이건 코드에 명시된 "디버거 탐지" 로직이 실제로 작동한 결과이지, 관찰 방법의 버그가 아니다. 이 문제처럼 그 성공/실패가 최종 결과값에 직접 반영되는 구조라면, LD_PRELOAD처럼 ptrace 관계를 만들지 않는 관찰 수단으로 바꿔야 "진짜" 값을 볼 수 있다.
• 누산합 검증에서 "모든 항이 non-negative"라는 조건 하나가 문제를 통째로 단순화시켰다. i의 홀짝에 따라 뺄셈과 XOR을 섞어 써서 언뜻 복잡해 보이지만, 두 연산 모두 "0이 되는 조건이 같다"는 사실과 "누산합이 0이려면 모든 항이 0이어야 한다"는 사실을 겹치면 결국 input[i] == b1[i]라는 단순한 문자열 비교로 귀결된다. 복잡해 보이는 산술식을 만나면, 그 식이 최종적으로 "0인지 아닌지"만 따지는 문맥에 놓여 있는지부터 확인하는 게 지름길이 될 때가 많다.

방어자 관점에서 보면, 재배치 테이블을 이용한 이 데이터 은닉 기법은 상당히 창의적이면서도 견고했다 — 파일 정적 분석으로는 "무슨 함수가 이 값을 만드는지" 찾을 방법이 아예 없고, 로더 동작까지 이해해야 발견할 수 있다. 다만 ptrace 기반 안티디버그와 조합하면서 생긴 "관찰 도구가 결과를 바꾼다"는 부작용은, 역으로 문제 풀이자에게 LD_PRELOAD 같은 비-ptrace 관찰 수단을 쓰도록 강제하는 재미있는 곁가지 퍼즐이 되어 있었다.