[💎 Diamond 3] 절반만 보여주고 그마저 절반은 누락 — 그래도 다음 출력을 맞힌다 (Fauna)

문제: Fauna (Diamond 3, Crypto) — fau fau fau 분류: Crypto (truncated LCG / lattice) 난이도: 💎 Diamond 3 FLAG: POKA{someone_keeps_sending_me_this:https://youtu.be/AOwqk3zrw0E}

제공 파일은 chal.py, values(출력 10000줄), enc(IV+암호문) 셋. 서버는 없고 로컬에서 완결되는 순수 크립토 문제다.

이건 솔직히 오래 걸렸다. 알려진 truncated LCG 공격을 다 갖다 붙여봤는데 전부 막혔고, 결국 이 정확한 구조를 다루는 논문 한 편을 찾아서야 풀렸다. 막힌 과정까지 그대로 적는다.

문제 개요

chal.py는 짧다.

class LCG:
    BITS = 1024
    MOD = 2 ** BITS
    TRUNC = 512
 
    def __init__(self):
        self.mult  = int.from_bytes(urandom(self.BITS // 8), 'big') | 1   # 1024비트 홀수, 미지
        self.value = int.from_bytes(urandom(self.BITS // 8), 'big')        # 1024비트, 미지
 
    def next(self):
        self.value = self.mult * self.value % self.MOD     # 곱셈 LCG (증분 b=0)
        return self.value >> self.TRUNC                     # 상위 512비트만 출력
 
def main():
    lcg = LCG()
    with open("values", "w") as f:
        cnt = 0
        while cnt < 10000:
            value = lcg.next()
            if urandom(1)[0] & 1:        # 50% 확률로만 기록
                cnt += 1
                f.write(str(value) + '\n')
 
    key = sha256(lcg.next().to_bytes(512 // 8, 'big')).digest()   # 마지막 기록 직후 출력
    iv = urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    encrypted = cipher.encrypt(pad(open("flag", "rb").read(), 16))
    open("enc", "wb").write(iv + encrypted)

정리하면 이렇다.

• 곱셈 LCG: value = mult * value mod 2^1024. 곱수 mult(1024비트 홀수)와 초기값 모두 미지, 증분은 0.

• 출력은 value >> 512 — 상위 512비트만. 하위 512비트는 버려진다 (정확히 절반 truncation, ℓ/n = 0.5).

• next()는 매 반복 호출되지만 출력은 50% 확률로만 values에 기록된다. 즉 기록값 사이에 랜덤 gap이 생긴다 (gap = g 확률 2^-g).

• AES 키는 마지막 기록 직후의 next() 출력으로 만든다 (마지막 기록값과 gap 1).

목표는 그 다음 출력 한 개를 맞히는 것. 그러려면 LCG의 내부 상태와 곱수를 복원해야 한다.

🧱 왜 안 풀리나 — 막힌 길들

여기서 한참 헤맸다. "truncated LCG 상태 복원"은 워낙 유명한 격자 문제라 기존 공격을 그대로 쓰면 될 줄 알았다. 아니었다.

막힌 길 1 — 표준 Stern 공격은 연속 출력이 너무 많이 필요하다

미지 곱수 truncated LCG 복원의 정석은 jvdsn의 truncated_parameter_recovery(Contini–Shparlinski 버전 Stern). 그런데 이 구현은 α = s/k, t = round(1/α), n = ceil(sqrt(2·α·t·k))로 청크 크기를 잡는다.

우리 파라미터(k=1024, s=512, α=1/2)를 넣으면 t=2, n=46. 연속 출력이 ~48개 필요하다.

문제는 50% 누락. 기록값에서 길이 L짜리 연속(gap 모두 1) 런이 나올 확률은 2^-(L-1)이다. 10000개 중 가장 긴 런이라야 15~17개. 48개 연속은 절대 안 나온다. 표준 Stern은 여기서 끝.

막힌 길 2 — 곱수를 소거하면 Coppersmith가 벽에 부딪힌다

곱수 z를 소거하려고 연속 세 상태의 관계 v_{i+1}^2 = v_i · v_{i+2} (mod 2^1024)를 썼다. v_i = 2^512·Y_i + δ_i(Y_i는 알려진 출력, δ_i는 미지 하위 512비트)를 대입하면 미지수 δ_i에 대한 다항식이 나온다. 작은 근을 찾는 다변수 Coppersmith 문제다. 다항식들을 단항식 기준으로 쌓아 격자를 만들고 LLL을 돌리면 짧은 벡터에서 δ가 나와야 한다.

구체적으로 연속 세 상태면 v_1^2 = v_0 v_2에서 다음 다항식이 나온다.

P(y0,y1,y2) = y1² − y0·y2 + 2·H1·y1 − H0·y2 − H2·y0 + (H1² − H0·H2)   (mod 2^n)

여기서 H_i는 출력에서 복원한 상위부, 작은 미지수는 y_i = δ_i < 2^ℓ. 미지 단항식은 {y0, y1, y2, y1², y0·y2} 다섯 개고, 각 단항식의 bound를 곱하면 (2^ℓ)^{1+1+1+2+2} = (2^ℓ)^7. Coppersmith 성공 조건 ∏(bound) < N은 (2^ℓ)^7 < 2^n, 즉 ℓ/n < 1/7(이론), 실험적으로 ~0.3이다. 연속 상태를 더 쓰고 등합 곱 관계를 보태면 이론 한계가 1/4, 실험 ~0.4까지 오른다. 그래도 0.5에는 못 미친다.

b=0이라는 점 때문에 변형이 여럿 떠오른다.

• 연속 윈도우 안의 등합 곱 관계. v_i v_j = v_k v_l (mod 2^1024)은 인덱스 합이 같을 때(i+j = k+l) 성립한다. 연속 9~10개를 가정하고 이런 쌍을 전부 모으면 다항식 개수를 늘려 단항식 평균 bound를 2^n 아래로 끌어내릴 수 있다 — 이론상으론.

• 전역 인덱스 대칭. b=0이라 v_a·v_{9999-a} = v_b·v_{9999-b} 같이 합이 같은 기록 인덱스 쌍을 10000개 전체에서 뽑아 격자를 세우는 발상도 가능하다.

둘 다 cuso(자동 다변수 Coppersmith)와 손으로 짠 격자 양쪽으로 돌려봤다. 격자 rank를 12 → 16 → ... → 512까지 키우면서 Found 0 integer relations만 반복하고 끝내 수렴하지 않았다. 이론상 bound는 들어오는데 실제로는 해가 안 떨어졌다.

나중에 이 문제를 푼 다른 분의 풀이를 봤는데, 똑같이 등합 곱 관계로 Coppersmith 격자를 직접 만들고 2^n bound까지 손으로 확인했는데도 *"coppersmith가 제대로 작동되지 않는 알 수 없는 문제"*를 겪고 Stern으로 넘어갔더라. 나만 그런 게 아니었다.

처음엔 "mod 2^512에서 vacuous라 비트를 잃나" 의심했는데, 그게 아니었다. 진짜 이유는 더 단순하다. Coppersmith 계열 공격(Martinez Attack 1·2)은 이 구조에서 ℓ/n ≈ 0.4가 한계다. 우리는 ℓ/n = 0.5. degree-2 곱 항(δ_i·δ_j)의 크기가 모듈러스 2^1024와 같아져, 관계를 아무리 늘려도 단항식 하나가 통째로 이득을 갉아먹는다. 바운드를 못 맞추니 격자를 키워도 관계가 안 나오는 게 당연했다.

ℓ/n = 0.5라는 절반 truncation이 정확히 Coppersmith의 사정거리 밖이다. 반대로 Stern은 같은 구조에서 0.55까지 간다. 이 한 칸 차이가 이 문제의 전부다.

정보는 충분한데 알고리즘이 문제였다

작은 스케일(BITS=16)에서 brute-force로 확인해보니 연속 출력 4개면 (곱수, 초기상태)가 유일하게 결정된다. 정보는 차고 넘친다. 알고리즘 선택이 틀렸을 뿐이다.

그래서 방향을 바꿨다. 상태와 곱수를 한꺼번에 풀려는 Coppersmith 대신, Stern의 격자 구성(Λ1/Λ2) 으로 곱수 하나만 따로 뽑아내는 길.

🎯 핵심 — Stern's Attack로 곱수 복원

이 정확한 구조(미지 곱수, b=0, N=2^n, 상위 비트 출력)를 다루는 논문이 있다. Florette Martinez, Attacks on Pseudo Random Number Generators Hiding a Linear Structure (CT-RSA 2022). 논문은 이 LCG를 깨는 공격을 셋 제시한다.

Attack 1·2는 앞서 내가 헤맨 Coppersmith 그 자체다 — 그래서 0.4에서 막힌다. 답은 Attack 3 (Stern 알고리즘). 상태까지 한꺼번에 풀려 하지 않고, 곱수 z 하나만 격자로 끄집어낸다. 그게 절반 truncation을 넘기는 비결이다.

핵심 수치: Stern은 연속 d+r-1개 출력으로 ℓ/n ≤ 0.55까지 간다. k=8(즉 d=r=5, 연속 9개)면 ℓ/n=0.5를 여유 있게 넘고, n=1024에서 1초대다.

Λ1 / Λ2 격자

상태는 v_i = z^i · v_0 mod 2^n. 곱수 z가 근이 되는 작은 다항식 Σ λ_i z^i ≡ 0 (mod N)을 찾는 게 목표다.

곱수 z로 만든 격자 Λ1(행: [N,0,…], [z,-1,0,…], …, [z^{d-1},0,…,-1])의 행렬식은 N이고, 가우스 휴리스틱상 짧은 벡터 (λ_0,…,λ_{d-1})의 성분은 N^{1/d}보다 작다. 이 λ가 Σ λ_i z^i ≡ 0 (mod N)을 만족한다. 하지만 z를 모르니 Λ1은 못 만든다.

여기서 한 번 더 짚자. Σ λ_i z^i ≡ 0 (mod N)이고 v_i = z^i v_0이므로 Σ λ_i v_i = v_0 · Σ λ_i z^i ≡ 0 (mod N)이다. 즉 같은 λ가 (모르는) 상태 v_i들의 영(零)결합도 만든다. 이걸 알려진 Y_i로 옮겨 쓰면:

0 ≡ Σ λ_i v_i = Σ λ_i (2^ℓ Y_i + δ_i) = 2^ℓ·Σ λ_i Y_i + Σ λ_i δ_i   (mod N)
⇒  2^ℓ·Σ λ_i Y_i  ≡  −Σ λ_i δ_i   (mod N)

λ_i는 ~N^{1/d}, δ_i < 2^ℓ라 우변 Σλ_i δ_i는 N보다 한참 작다. 그러니 2^ℓ·Σλ_i Y_i mod N이 비정상적으로 작아지는 λ 가 우리가 찾는 그 λ다. 이걸 잡는 (d+r)차원 격자가 Λ2 — 위쪽 d행은 2^ℓ 대각 + 2^ℓ·(Y_i…Y_{i+r-1}), 아래쪽 r행은 N 대각으로, 전부 알려진 값만으로 구성된다.

LLL로 줄인 짧은 벡터의 앞 d성분을 2^ℓ로 나누면 λ. 다항식 Σ λ_i x^i의 mod 2^n 근이 곱수 z다. 성공 조건은 이 특별한 짧은 벡터(노름 ≈ d + r·d·2^ℓ·N^{1/d})가 Λ2의 일반적인 짧은 벡터(≈ (2^{ℓd}·N^r)^{1/(r+d)})보다 더 짧아야 한다는 것 — 이 부등식이 r=d를 키울수록 더 큰 ℓ/n을 허용한다.

2^n은 합성수(2의 거듭제곱)라 다항식 Σλ_i x^i의 근이 여럿 나올 수 있다. 그래서 여러 짧은 벡터가 공통으로 내놓는 근에 표를 몰아주고 최다 득표를 z로 골랐다. (근 자체는 Sage .roots()로 찾거나, 정석대로 mod 2부터 비트를 올리는 Hensel lifting으로 찾는다.)

def stern_z(Y, d=5, r=5):
    twol = Integer(1) << ELL
    M = matrix(ZZ, d + r, d + r)
    for i in range(d):
        M[i, i] = twol
        for j in range(r):
            M[i, d + j] = twol * Y[i + j]
    for j in range(r):
        M[d + j, d + j] = N
    B = M.LLL()
    R =

이 stern_z가 실제로 무슨 일을 하는지, 작은 LCG(N=2^24, 하위 6비트 절단)로 SageMath에서 직접 돌려 보면 추상이 손에 잡힌다. Λ2는 위 d행이 2^ℓ 대각 + 2^ℓ·Y 블록, 아래 r행이 N 대각 — 전부 알려진 값으로 짜인다. .LLL() 한 줄이 짧은 벡터들을 내놓고, 그 앞 d성분을 2^ℓ로 나눈 λ가 만든 다항식의 근에서 곱수가 그대로 떨어진다.

d와 r을 얼마로 잡을지는 논문의 실험 표가 알려준다. ℓ/n이 클수록 더 큰 r=d가 필요하다. (n=1024 기준)

ℓ/n = 0.5니 굵게 표시한 k=8(d=r=5, 연속 9개) 행이면 충분하다 — 0.55 ≥ 0.5. 더 키우면(k=10) 0.60까지 여유가 생기지만 그만큼 긴 런이 필요해진다. 데이터에 맞춰 9가 최적이다.

작은 스케일(BITS=64, TRUNC=32, 같은 ℓ/n=0.5)에서 먼저 검증했다. 연속 9개를 넣으니 진짜 곱수가 가장 많은 다항식(5개)에서 공통 근으로 떠서 1순위로 잡혔다.

docker exec fauna-sage bash -c "cd /work && sage stern.sage dev_64_32_200_0_1337.json 0 5 5 2>/dev/null"

곱수를 알면 나머지는 쉽다

곱수 z만 알면 known-multiplier truncated state recovery는 선형이다 (jvdsn truncated_state_recovery, 깔끔한 LLL 한 방). truncation 비율과 무관하게 동작한다. 복원한 상태가 v_{i+1} = z·v_i와 출력에 모두 맞으면, 그 윈도우가 진짜 gap-1 런이었다는 검증까지 동시에 된다.

gap은 어떻게 넘었나

표준 Stern이 막힌 건 연속 48개가 필요해서였다. Attack 3은 9개면 된다 — 그래서 gap이 갑자기 별것 아니게 된다. 기록쌍의 50%는 stream에서 바로 옆(gap 1)이고, 길이 9짜리 gap-1 런은 10000개 중 10000 · 2^-8 ≈ 39개나 된다.

문제는 어느 윈도우가 진짜 연속인지 미리 알 수 없다는 것. 하지만 굳이 알 필요도 없다. 연속 9개 윈도우를 옮겨가며 Stern → 상태복원 → 마지막 기록까지 walk 검증을 돌린다. 윈도우가 진짜 gap-1 런이 아니면 곱수가 안 맞아 walk가 깨지고, 맞으면 끝까지 걸어간다. 곱수와 상태 하나만 잡으면 그때부턴 전체 스트림을 재구성할 수 있다. 실제 데이터에선 윈도우 18번에서 바로 걸렸다.

더 견고한 변형 — 전체 윈도우 투표 + Hensel

위 코드는 "첫 유효 런에서 멈추기"라 빠르지만, 더 안정적인 방식은 투표다. 9900개 윈도우 전부에 대해 Stern을 돌려 나온 근들을 누적하고, 가장 많이 등장한 근을 곱수로 채택한다. 진짜 곱수는 모든 gap-1 런에서 근으로 떨어지니 표가 압도적으로 몰린다. (다른 분의 풀이가 이 방식이었다.)

한 가지 더. 다항식의 mod 2^1024 근을 찾을 때 2^n은 합성수라 근이 여럿일 수 있다. Sage의 .roots()도 동작하지만, 정석은 Hensel lifting으로 mod 2부터 비트를 한 칸씩 올려가며 근을 추적하는 것이다.

def hensel_roots(f, p, k):
    f_ = f.change_ring(Zmod(p))
    roots = list(range(p)) if f_ == 0 else \
            [] if f_.is_constant() else [int(r) for r in f_.roots(multiplicities=False)]
    f = f.change_ring(ZZ)
    for i in range(1, k):                       # mod p^i → mod p^{i+1}
        nxt = []
        for root in roots:
            for

곱수만 정확히 잡히면 그 뒤는 어느 방식이든 같다.

🚀 Full Solve

SageMath에서 돈다 (crypto-attacks의 truncated_state_recovery만 임포트).

import sys, hashlib
sys.path.insert(1, "crypto-attacks")
from sage.all import matrix, ZZ, Zmod, PolynomialRing, Integer
from attacks.lcg import truncated_state_recovery as tsr
from Crypto.Cipher import AES
 
N_BITS, ELL = 1024, 512
N = Integer(1) << N_BITS
rec = [Integer(l) for l in open("values")]
enc = open("enc", "rb").read(); iv, ct = enc[:16], enc[16:]
 
def

[+] gap-1 run at window 18
[+] multiplier z = 1789265279697753864238963326793294274346257287516935168388...
[+] FLAG = POKA{someone_keeps_sending_me_this:https://youtu.be/AOwqk3zrw0E}

POKA{someone_keeps_sending_me_this:https://youtu.be/AOwqk3zrw0E}

비용은 거의 안 든다. Stern은 10차원 격자 LLL이라 윈도우당 수 밀리초고, 격자가 작아 flatter 없이 Sage 기본 LLL로 충분하다. 진짜 gap-1 런이 나올 때까지 윈도우를 옮기는데 평균 ~수백 번이면 걸린다(이번엔 18번째). 곱수를 잡은 뒤 끝까지 walk하는 건 O(기록 수 × 평균 gap)로 선형. 전체가 1초 안쪽이다.

📝 결론

Coppersmith가 만능은 아니다.

truncated LCG는 격자로 푼다는 감각만 믿고 곱수 소거 + Coppersmith를 붙였는데, ℓ/n = 0.5라는 절반 truncation에선 그 계열이 원리적으로 한계(~0.4)에 걸린다. 정보가 충분해도(연속 4개면 유일) 알고리즘 선택이 틀리면 격자를 아무리 키워도 안 나온다.

Stern은 곱수만 따로 뽑는다.

상태와 곱수를 한꺼번에 풀려던 게 패착이었다. Stern의 진짜 묘는 쌍대성이다 — 모르는 곱수 z로 만들 격자 Λ1의 짧은 벡터(Σλ_i z^i ≡ 0)를, 그 벡터가 만족하는 성질을 통해 알려진 출력만으로 짠 Λ2에서 비정상적으로 짧은 벡터로 되찾는다. 곱수를 근으로 갖는 작은 다항식 하나만 노리니 단항식이 폭발하지 않고, 그래서 절반 truncation을 넘긴다. 곱수만 손에 쥐면 상태 복원은 선형이라 순식간이고, truncation 비율도 더는 상관없다.

랜덤 누락은 생각보다 약한 방어다.

50% skip이 길게 연속을 못 만들게 막는 것처럼 보이지만, 기록쌍의 절반은 어차피 stream-인접이고 연속 9개 런도 수십 개 나온다. 짧게만 필요하면 gap은 윈도우를 옮겨가며 검증으로 식별하면 그만이다.

플래그 속 유튜브 링크는 직접 확인하시길.

참고

• Florette Martinez, Attacks on Pseudo Random Number Generators Hiding a Linear Structure (CT-RSA 2022) — eprint 2021/1204. Section 3.2가 Stern's Attack(Attack 3).

• jvdsn/crypto-attacks — truncated_state_recovery(known-z), hensel.py(근 lifting).

• 빠른 격자 환원 flatter, 자동 Coppersmith cuso.