[💎 Platinum 3] 다항식 안에 숨은 RSA — DreamHack multipoint2 풀이

file extracted/multipoint2
readelf -h extracted/multipoint2 | grep -E "Type:|Entry"
objdump -T extracted/multipoint2 | grep UND | awk '{print $NF}'

strings -n 4 extracted/multipoint2 | grep -nE "Input|Correct|Wrong"

objdump -d -M intel --start-address=0x11ec --stop-address=0x1253 extracted/multipoint2

objdump -d -M intel --start-address=0x129a --stop-address=0x1314 extracted/multipoint2

TMP[b0] = ( TMP[b0] + STATE[b1] * STATE[b2] * b3 ) mod 251

#!/usr/bin/env python3
# multipoint2 - .data 의 COEF 곱셈표와 TARGET(정답 암호문) 추출
import struct, os
BIN = 'extracted/multipoint2' if os.path.exists('extracted/multipoint2') else 'multipoint2'
data = open(BIN, 'rb').read()
def off(v): return v - 0x1000          # .data: vaddr - 0x1000 = 파일 오프셋
 
# COEF 테이블 @0x4050 : dword=0 센티넬까지. dword 1개 = (b0,b1,b2,b3)
base = off(0x4050); coefs = []; p = base
while True:
    dw = struct.unpack_from('<I', data, p)[0]
    if dw == 0:
        break
    coefs.append((dw & 0xff, (dw >> 8) & 0xff, (dw >> 16) & 0xff, (dw >> 24) & 0xff))
    p += 4
 
print("[COEF] 항목 수 =", len(coefs))
print("[COEF] 처음 6개 (b0=출력idx, b1,b2=입력idx, b3=계수):")
for c in coefs[:6]:
    print("        out[%2d] += s[%2d]*s[%2d]*%3d" % c)
b0 = [c[0] for c in coefs]; b1 = [c[1] for c in coefs]
b2 = [c[2] for c in coefs]; b3 = [c[3] for c in coefs]
print("[COEF] b0 범위 %d..%d / b1 %d..%d / b2 %d..%d / 계수 %d..%d"
      % (min(b0), max(b0), min(b1), max(b1), min(b2), max(b2), min(b3), max(b3)))
 
# TARGET 38바이트 @0x1ed50 (memcmp 비교 대상 = FLAG^65537 의 바이트열)
TARGET = list(data[off(0x1ed50):off(0x1ed50) + 38])
print("[TARGET] 38바이트 =", TARGET)
print("[TARGET] hex =", bytes(TARGET).hex())
print("[MOD] idiv 상수 0xfb =", 0xfb, "(= 251, 소수)")

#!/usr/bin/env python3
# multipoint2 - COEF 가 정의하는 곱셈 MUL 이 F_251[x]/(p(x)) 환(ring)인지 실증한다.
#   MUL(u,v)[k] = sum over (k,i,j,c) in COEF  u[i]*v[j]*c   (mod 251)
import struct, os, random
BIN = 'extracted/multipoint2' if os.path.exists('extracted/multipoint2') else 'multipoint2'
data = open(BIN, 'rb').read()
def off(v): return v - 0x1000
MOD, N = 251, 38
 
base = off(0x4050); coefs = []; p = base
while True:
    dw = struct.unpack_from('<I', data, p)[0]
    if dw == 0: break
    coefs.append((dw & 0xff, (dw >> 8) & 0xff, (dw >> 16) & 0xff, (dw >> 24) & 0xff)); p += 4
from collections import defaultdict
T = defaultdict(list)
for (k, i, j, c) in coefs:
    T[k].append((i, j, c))
def MUL(u, v):
    r = [0] * N
    for k in range(N):
        s = 0
        for (i, j, c) in T[k]:
            s += u[i] * v[j] * c
        r[k] = s % MOD
    return r
 
rnd = lambda: [random.randrange(MOD) for _ in range(N)]
# 1) 가환성
comm = all(MUL(a, b) == MUL(b, a) for a, b in [(rnd(), rnd()) for _ in range(5)])
print("[1] 가환(commutative)      :", comm)
# 2) 결합성
assoc = all(MUL(MUL(a, b), c) == MUL(a, MUL(b, c))
            for a, b, c in [(rnd(), rnd(), rnd()) for _ in range(3)])
print("[2] 결합(associative)      :", assoc)
# 3) 항등원 e = [1,0,0,...]
e = [0] * N; e[0] = 1
ident = all(MUL(e, a) == a for a in [rnd() for _ in range(5)])
print("[3] e=[1,0,..] 가 항등원    :", ident)
# 4) x=[0,1,0,..] 의 거듭제곱이 단항식 기저와 일치 (표준 다항식 표현)
x = [0] * N; x[1] = 1
cur = e[:]; mono = True
for k in range(N):
    ek = [0] * N; ek[k] = 1
    if cur != ek: mono = False; break
    cur = MUL(cur, x)
print("[4] x^k == 기저 e_k (k<38) :", mono)
# 5) x^38 의 환원 => 모듈러스 다항식 p(x) = x^38 - (x^38 환원식)
print("[5] x^38 환원 계수(= p의 상수부분들) =", cur)

objdump -d -M intel --start-address=0x13ac --stop-address=0x1409 extracted/multipoint2

objdump -d -M intel --start-address=0x144b --stop-address=0x149d extracted/multipoint2

STATE16 = IN^(2^16)       # 제곱 16회
OUT     = IN · STATE16     # 마지막 곱
OUT     = IN^65537         # 즉 입력의 65537제곱
Correct ⟺ OUT == TARGET

#!/usr/bin/env python3
# multipoint2 (DreamHack, Platinum 3, reversing+crypto) solver
#
# 바이너리 분석 결과:
#   - 입력 39바이트(0x27)를 읽고, 앞 38바이트(0x26)를 상태 STATE 로 복사한다.
#   - COEF 테이블(.data@0x4050)은 F_251[x]/(p(x)) 위의 곱셈 MUL 을 정의한다:
#         MUL(u,v)[k] = sum over (k,i,j,c) in COEF  u[i]*v[j]*c   (mod 251)
#   - loop1: STATE <- MUL(STATE,STATE) 를 16회 => STATE16 = IN^(2^16)
#   - loop2: OUT = MUL(IN, STATE16) = IN^(2^16+1) = IN^65537
#   - memcmp(OUT, TARGET@0x1ed50, 38) => "Correct"
#   즉 TARGET = FLAG^65537  (GF(251^38) 위의 RSA 구조).
#
# 복호: p(x) 가 F_251 위에서 기약 => R = GF(q), q = 251^38.
#       d = 65537^{-1} mod (q-1),  FLAG = TARGET^d.
import struct, sys
 
MOD = 251
N = 38
E = 65537
 
data = open('extracted/multipoint2', 'rb').read() if __import__('os').path.exists('extracted/multipoint2') else open('multipoint2','rb').read()
def off(v): return v - 0x1000            # .data: vaddr - 0x1000 = file offset
 
# --- COEF 테이블 파싱 (dword=0 센티넬까지) ---
base = off(0x4050); coefs = []; p = base
while True:
    dw = struct.unpack_from('<I', data, p)[0]
    if dw == 0: break
    coefs.append((dw & 0xff, (dw >> 8) & 0xff, (dw >> 16) & 0xff, (dw >> 24) & 0xff)); p += 4
 
from collections import defaultdict
T = defaultdict(list)
for (k, i, j, c) in coefs:
    T[k].append((i, j, c))
 
def MUL(u, v):
    r = [0] * N
    for k in range(N):
        s = 0
        for (i, j, c) in T[k]:
            s += u[i] * v[j] * c
        r[k] = s % MOD
    return r
 
# TARGET 38바이트
TARGET = list(data[off(0x1ed50):off(0x1ed50) + 38])
 
# --- 이진 모델 정확 재현(검증용): OUT = IN^65537 via 16 squarings + 1 mul ---
def encrypt(IN):
    st = IN[:]
    for _ in range(16):
        st = MUL(st, st)          # STATE <- STATE^2  => IN^(2^16)
    return MUL(IN, st)            # IN * IN^(2^16) = IN^(2^16+1)
 
# --- 모듈러스 다항식 p(x): x^38 의 환원 ---
e = [0]*N; e[0] = 1
x = [0]*N; x[1] = 1
cur = e[:]
for _ in range(N):
    cur = MUL(cur, x)
x38 = cur                         # x^38 = sum x38[i] x^i
# p(x) = x^38 - sum x38[i] x^i  (monic)
from sympy import Poly, symbols, GF
X = symbols('X')
pcoeffs = [1] + [(-x38[N-1-i]) % MOD for i in range(N)]  # 최고차부터
ppoly = Poly(pcoeffs, X, modulus=MOD)
print("p(x) monic deg", ppoly.degree())
print("p(x) irreducible over F_251:", ppoly.is_irreducible)
 
q = MOD ** N
order = q - 1
from math import gcd
print("gcd(65537, q-1) == 1 :", gcd(E, order) == 1)
d = pow(E, -1, order)
 
# --- 환(=체) 거듭제곱: square-and-multiply (MUL 이 이미 환원 포함) ---
def ring_pow(base_v, exp):
    result = e[:]              # identity
    b = base_v[:]
    while exp > 0:
        if exp & 1:
            result = MUL(result, b)
        b = MUL(b, b)
        exp >>= 1
    return result
 
FLAG_vec = ring_pow(TARGET, d)
# vec -> bytes (단항식 계수가 곧 바이트)
flag_bytes = bytes(FLAG_vec)
print("recovered 38 bytes:", FLAG_vec)
print("as ascii:", flag_bytes)
 
# --- 검증: 복원값을 정방향 암호화하면 TARGET 과 일치해야 함 ---
chk = encrypt(FLAG_vec)
print("forward(FLAG) == TARGET :", chk == TARGET)
 
# 39번째 바이트는 개행(read 0x27=39, 사용 38). 플래그 출력
try:
    print("FLAG =", flag_bytes.decode())
except Exception as ex:
    print("decode err", ex)

# cmds.gdb
set pagination off
set disable-randomization on
break *0x555555555060       # memcmp@plt = 0x1060 + PIE base
run
printf "길이 rdx = %d\n", $rdx
x/38bx $rdi                 # 입력으로 계산한 OUT
x/38bx $rsi                 # 바이너리 내장 TARGET
finish
printf "memcmp 반환 eax = %d\n", $eax
continue

gdb -q -batch -x cmds.gdb --args extracted/multipoint2 < flag_input.txt

printf '%s\n' 'POKA{Poly_c0w_R1vest-Sham1r-Adl3man~!}' | ./multipoint2
printf '%s\n' 'POKA{wrong_flag_123456789012345678}'    | ./multipoint2