[🥉 Bronze 4] 곱셈 치환을 모듈러 역원으로 되돌리기 — DreamHack rev-basic-8 풀이

문제: DreamHack — rev-basic-8 (Reversing Basic Challenge #8) 분류: Reversing 난이도: 🥉 Bronze 4 FLAG: DH{Did_y0u_brute_force?}

문제 개요

rev-basic 시리즈 여덟 번째. 이번에도 문자열을 입력받아 Correct / Wrong을 출력하는 단순한 콘솔 프로그램이다. 앞선 문제들(strcmp, 글자별 cmp, 정수 배열, XOR, 니블 스왑, 인접합, AES S-box)과 결이 비슷한데, 이번엔 검증에 쓰는 연산이 곱셈이다. 상수 하나만 곱하고 하위 바이트만 남기는 연산이라, 그 상수의 모듈러 역원만 구하면 곧바로 역산이 끝난다.

file chall8.exe
strings -a chall8.exe | grep -E "Input|Correct|Wrong"

이전 문제들과 마찬가지로 심볼은 stripped 상태다. Input : 을 출력하고 입력을 받은 뒤 Correct나 Wrong 중 하나를 찍는 구조라는 것만 문자열로 먼저 확인했다.

🔬 정찰 — check 함수 찾기

심볼이 없으니 PE 헤더의 AddressOfEntryPoint부터 따라간다.

objdump -f chall8.exe | grep "start address"

엔트리는 0x140001584. 거기서부터 몇 단계 내려가면 main 격인 함수(0x140001120)가 나오는데, 스택 버퍼를 0으로 채우고 "Input : "을 출력한 다음 scanf("%256s", buf)로 입력을 받고, 그 버퍼 포인터를 인자로 0x140001000의 함수를 호출한다. 반환값이 0이 아니면 Correct, 0이면 Wrong을 출력하고 종료한다. 이 0x140001000 함수가 검증 로직 전체다.

objdump -M intel -d --start-address=0x140001000 --stop-address=0x140001060 chall8.exe

루프 하나에 곱셈 한 번, 비교 한 번. 핵심만 남기면 이렇게 읽힌다.

; rcx = 입력 버퍼, (%rsp) = 카운터 i, 시작값 0
loop:
  cmp    rax, 0x15              ; i >= 21 이면
  jae    correct                ;   → 루프 종료, return 1
  movzx  eax, BYTE PTR [rcx+rax*1]   ; al = buf[i]
  imul   eax, eax, 0xfb          ; eax = al * 0xfb  (251)
  and    eax, 0xff               ; 하위 1바이트만 남김 (mod 256)
  movzx  ecx, BYTE PTR [rdx+rcx*1]   ; cl = table[i]   (VA 0x140003000)
  cmp    eax, ecx
  jne    wrong                   ; 다르면 return 0
  inc    i; jmp loop
correct:
  mov    eax, 0x1
  ret

C로 옮기면 한 줄이다.

for (int i = 0; i < 21; i++)
    if ((buf[i] * 0xfb) & 0xff != TABLE[i])
        return 0;   // Wrong
return 1;            // Correct

0x15(21)까지 도는데 scanf("%256s", ...)로 받은 문자열의 실제 글자 수는 그보다 적을 것이다 — 마지막 한 칸은 뒤에서 보듯 NUL 종결자 검증이다.

💣 핵심 — 0xfb 곱셈을 거꾸로

비교 대상 테이블은 .data 섹션, VA 0x140003000에 21바이트로 박혀 있다.

objdump -s -j .data chall8.exe | sed -n '1,6p'

ac f3 0c 25 a3 10 b7 25 16 c6 b7 bc 07 25 02 d5 c6 11 07 c5 00 — 21바이트, 마지막이 00이다.

검증식은 (buf[i] * 0xfb) & 0xff == table[i]. & 0xff는 결국 mod 256과 같으니 정수론 관점에서 보면 buf[i] * 251 ≡ table[i] (mod 256)이다. 251은 홀수라 256과 서로소(gcd(251, 256) = 1)이고, 그래서 mod 256에서 곱셈의 역원이 존재한다. 역원을 inv라 하면 양변에 곱해서 buf[i] ≡ table[i] * inv (mod 256)로 바로 넘어간다.

곱셈 역원을 구하는 방법은 확장 유클리드 알고리즘인데, 파이썬 pow(a, -1, m)이 그대로 계산해준다.

🎯 역산 — solve.py

테이블을 바이너리에서 그대로 옮겨 적고, pow(0xfb, -1, 256)으로 역원을 구해 곱하기만 하면 된다.

#!/usr/bin/env python3
"""rev-basic-8: check()가 buf[i]*0xfb & 0xff == table[i] 를 21바이트(0..20) 검증한다.
0xfb(=251)는 mod 256에서 홀수라 역원이 존재하므로 곱셈을 그대로 역산한다.
"""
 
TABLE = bytes.fromhex("acf30c25a310b72516c6b7bc072502d5c61107c500")
 
MUL = 0xfb
INV = pow(MUL, -1, 256)  # 51
 
flag_bytes = bytes((b * INV) & 0xff for b in TABLE)
print("inverse of 0xfb mod 256 :", INV)
print("recovered bytes         :", flag_bytes)
print("flag                    :", "DH{" + flag_bytes.rstrip(b"\x00").decode() + "}")

복원된 바이트는 Did_y0u_brute_force?\x00. 앞서 짐작한 대로 마지막 바이트가 NUL이고, 실제로 타이핑할 입력은 20글자 Did_y0u_brute_force?다. 이름 그 자체가 놀리는 문구인 게 재밌다 — 21바이트짜리 좁은 탐색 공간이라 브루트포스도 사실 가능한 범위지만, 역원 한 번이면 즉시 끝난다.

🚀 검증 — wine으로 Correct 확인

파이프(echo | wine chall8.exe)는 환경에 따라 오동작할 수 있어 쓰지 않는다. subprocess로 입력을 직접 넣고 출력을 받는다.

#!/usr/bin/env python3
"""복원한 입력을 chall8.exe에 실제로 먹여 Correct 확인 (wine, subprocess)"""
import subprocess, os
 
flag_input = "Did_y0u_brute_force?"
env = dict(os.environ)
env["WINEPREFIX"] = os.path.expanduser("~/.wine_revbasic8")
env["WINEDEBUG"] = "-all"
 
res = subprocess.run(["wine", "chall8.exe"], input=flag_input + "\n",
                      capture_output=True, text=True, env=env, timeout=120)
print("Input :", flag_input)
print("Output:", (res.stdout + res.stderr).strip())

Input : Correct. 바이너리가 직접 답을 인정했다. 이 값을 드림핵 제출창에 DH{}로 감싸 넣으니 정답 처리됐고 VM 크레딧도 그대로 유지됐다(이 문제는 서버 없이 파일만 받는 유형이라 크레딧을 애초에 쓰지 않는다). 최종 플래그는 DH{Did_y0u_brute_force?}.

📝 결론

상수를 곱하는 변환도 그 상수가 모듈러 환에서 가역이면 XOR이나 치환표와 똑같이 뚫린다.

이번 문제가 실제로 한 일은 세 가지뿐이다. (1) 검증 함수가 (buf[i] * 0xfb) & 0xff == table[i] 형태의 21회 루프임을 읽고, (2) 0xfb가 mod 256에서 서로소라 역원이 존재한다는 걸 확인하고, (3) pow(0xfb, -1, 256)으로 역원을 구해 테이블에 그대로 곱했다. 21번째 비교가 사실은 길이 체크(NUL 종결자)라는 걸 알아채는 것 정도가 유일한 삽질이었다.

• 곱셈 인코딩은 나눗셈이 아니라 역원 곱셈으로 풀린다. 모듈러 산술에서 나눗셈은 정의되지 않지만, 법과 서로소인 곱수는 항상 역원을 갖는다. & 0xff로 잘라내는 연산을 보면 mod 256 곱셈임을 의심하는 게 먼저다.
• 짝수 상수를 곱했다면 이 트릭이 안 통했을 것이다. 짝수는 256과 공약수 2를 가지므로 역원이 없고, 여러 입력이 같은 출력에 몰리는 다대일 함수가 된다 — 그러면 역산이 아니라 후보 집합을 좁히는 문제로 바뀐다. 이번엔 0xfb가 홀수였던 게 검증을 정확히 한 번에 뒤집을 수 있었던 이유다.
• 길이 검사를 종결자 비교로 숨겨도 정적 분석 앞에선 큰 의미가 없다. 테이블 마지막 바이트를 보는 순간 바로 드러난다.

시리즈를 관통하는 방법은 똑같다 — 검증 함수가 입력에 무슨 연산을 하는지 읽고, 그 연산의 역함수를 찾아 거꾸로 돌린다. 이번엔 그 역함수가 모듈러 곱셈의 역원이었을 뿐이다.