[Crypto] Linear congruential generator(LCG) Recovery

이 글에서는 LCG의 동작 원리와 수학적 성질을 간단히 정리한 뒤, 보안적 취약점을 다룹니다. 이어서 실제 CTF 문제에서 LCG 기반 PRNG의 매개변수를 복구하고 출력을 예측하는 과정을 포스팅했습니다.

 

---

LCG(Linear Congruential Generator)

• 재귀식: $ x_n +1 \equiv Ax_n + C (mod M) $
• 변수:  모듈러스 $M$, 승수 $A$, 상수항 $C$, 시드 $x_0$
• Mixed LCG: $C \neq 0$
• Multiplicative LCG: $C=0$

Hull-Dobell 정리(Full-period, Mixed LCG)

$C \neq 0$일 때, 전 상태공간 크기 $M$의 최대 주기를 가지려면 다음과 같은 조건이 만족해야 한다.

1. $gcd(C, M) = 1$

2. $ A-1$이 $M$의 모든 소인으로 나누어 떨어짐

3. $M$이 4의 배수면 $A-1$도 4의 배수

 

Full-Period 예시: $M = 9, A = 4, C = 1, x_0 = 0 \rightarrow 1, 5, 3, 4, 8, 6, 7, 2, 0 $ 길이로 9로 전체 순환

 

Bit 레벨 특성

Full-Period가 되려면 $A$와 $C$는 보통 홀수가 된다.

LSB는 $x_n+1 \equiv Ax_n + C (mod 2) \rightarrow x_n+1 \equiv x_n + 1 (mod 2) $ 처럼 0/1 토글이 되어 주기가 2로 매우 짧아짐

 

Jump-Ahead 닫힌식

1. k-step 건너뛰기

$x_n+k \equiv A^k x_n + \frac{(A^k - 1)}{(A-1)} C (mod M)$

(단, $A=1$이면, $x_n+k \equiv x_n + kC (mod M)$)

2. 행렬 형태

$\begin{bmatrix} x_n+1 \\ 1 \end{bmatrix} \equiv \begin{bmatrix} A & C \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_n \\ 1 \end{bmatrix} (mod M) $

 

선형성으로 $t$-차원에서 lattice위에 놓이는 경향, 매개변수 선택이 나쁠 경우 저차원에서 패턴이 드러남

 

---

보안 관점에서의 LCG

선형 구조인 만큼 연속 출력 값들로 M, A, C 또는 상태가 복구된다.

$M$이 알려져 있으면 $x_0, x_1, x_2$만으로 $A \equiv (x_2 - x_1 )(x_1 - x_0 )^-1 (mod M), C \equiv x_1 - Ax_0 (mod M) $로 바로 계산 가능(역원 존재 가정)

$M$이 미지여도 차분을 이용한 GCD 기법으로 $M$ 회복 가능(이후 $A, C$ 복구)

 

 

결론: LCG는 암호학적 용도로 부적합하며, 시뮬레이션/표본 추출 등 비보안 용도에서 제한적 사용이 된다.

 

조금이라도 해결

1. Mixed에선 Hull-Dobell 충족으로 Full-Period 확보
2. $M$은 가능하면 크고, $A$는 스펙트럴 테스트 품질이 좋은 값 사용
3. 하위 비트 사용 지양
4. 결합 LCG(복수 LCG 합성) 또는 비선형 후처리 고려

---

CTF에서의 LCG

LCG가 사용된 크립토 CTF 문제 예시

#!/usr/bin/env python3
from Crypto.Util.number import *
import random

class PRNG:
    def __init__(self):
        self.M = getPrime(128)
        self.A = getPrime(128)
        self.C = getPrime(128)
    
        self.state = random.getrandbits(100)

    def next(self):
        self.state = (self.A * self.state + self.C) % self.M
        return self.state

class Game:
    def __init__(self):
        self.prng = PRNG()
        self.get_hint()

    def get_hint(self):
        for i in range(10):
            print(f"hint[{i}] : {self.prng.next()}")
    
    def start(self):
        for _ in range(100):
            answer = self.prng.next()
            num = int(input("answer > "))

            if num != answer:
                exit(0)

        with open("./flag", "rb") as f:
            print(f.read().decode())
    
if __name__ == "__main__":
    game = Game()
    game.start()

 

PRNG 함수는 전형적인 Mixed LCG

 

$$x_n+1 = (Ax_n + C) mod M

M, A, C는 각각 128비트 소수이다.

초기 상태는 Mersenne Twister 기반 랜덤값을 받는다.

 

1. get_hint() 함수를 통해 연속 출력 10개를 그대로 노출한다.
2. 이후 100회 라운드마다 다음 출력을 맞추면 flag가 출력된다.

 

출력

[*] hint[0] : 138470481618274890360239770256007765593
[*] hint[1] : 169453013577106222244869772475637995443
[*] hint[2] : 49758251231798165826312806985023726346
[*] hint[3] : 159795007959623572289951205394504353103
[*] hint[4] : 23771571119988917745397476856267443296
[*] hint[5] : 124086612535022052379191807985524552330
[*] hint[6] : 111399185485688182206439356203733932720
[*] hint[7] : 81278771847753699009131294501091293477
[*] hint[8] : 32640406005333507234349689917343987865
[*] hint[9] : 22109054296871064271239787107936084169
[+] M = 170419916113683136400144594870588798987
    A = 69294058042770348738396483177075520584
    C = 53920691625998404479320457602877575660

근본 취약점

1. 선형성 + 연속 출력 노출
2. 차분 정수 GCD 트릭으로 $M$을 구하고 역원 계산으로 $A, C$ 복구
3. 10개의 충분한 힌트

 

1. 모듈러스 $M$ 복구

1. 1차 차분 정의: $d_i = h_n+1 - h_n $
2. LCG 식을 두 번 써서 제거하면 $u_n = d_{n+1} d_{n-1} - d_{n}^2 \equiv 0 (mod M)$이 항상 $M$의 배수가 된다.

2번에서 세 연속 점($d_{n-1} , d_n , d_{n+1} $)가 소거된다. 그러면 모든 $u_n$ 은 $M$의 배수이므로, 여러 $u_n$들의 gcd를 취하면 $M$ 혹은 $M$의 배수가 나온다. $\rightarrow gcd(u_1,u_2,...)= kM$ 형태가 된다.

 

d = [h[i+1] - h[i] for i in range(len(h)-1)]
u = [d[i+1]*d[i-1] - d[i]*d[i] for i in range(1, len(d)-1)]
M_guess = abs(reduce(gcd, u))

 

2. $A$와 $C$의 닫힌형 복구

$M$을 알면 $A, C$를 바로 계산할 수 있다.

$$ h_1 \equiv Ah_0 + C (mod M) $$

$$h_2 \equiv Ah_1 + C (mod M) $$

두 식을 빼면

$$ h_2 - h_1 \equiv A(h_1 - h_0 ) (Mod M) $$

따라서

$$ A \equiv (h_2 - x_1 )(h_1 - h_0 )^{-1} (Mod M) $$

 

여기서 $(h_1 - h_0 )^{-1} $은 모듈러 역원 $M$이 소수이므로 $h_1 \neq h_0 (Mod M) $인 한 거의 항상 역원이 존재한다.

 

이어서 $C$를 보면

$$ C \equiv h_1 - Ah_0 (mod M) $$

A = ((h[2] - h[1]) * pow(h[1] - h[0], -1, M)) % M
C = (h[1] - A * h[0]) % M

 

3. 예측

마지막 hint를 상태로 잡고

$$ x_{n+1} = (An_x + C) mod M $$

를 100번 반복하여 그대로 제출한다. 

 

 

전체 익스 코드

from pwn import *
from math import gcd
from functools import reduce

context.log_level = 'debug'

def recover(h):
    d = [h[i+1] - h[i] for i in range(len(h)-1)]
    u = [d[i+1]*d[i-1] - d[i]*d[i] for i in range(1, len(d)-1)]
    M = abs(reduce(gcd, u))
    A = ((h[2] - h[1]) * pow(h[1] - h[0], -1, M)) % M
    C = (h[1] - A * h[0]) % M
    return M, A, C

p = remote('andsopwn', 10000)

hints = []
for _ in range(10):
    line = p.recvline().decode()
    hints.append(int(line.split(':')[1].strip()))
    log.info(line.strip())

M, A, C = recover(hints)
log.success(f"M = {M}\nA = {A}\nC = {C}")

state = hints[-1]
for _ in range(100):
    state = (A * state + C) % M
    p.recvuntil(b'answer > ')
    p.sendline(str(state).encode())

p.interactive()

 

 

---

또한 LCG를 LLL로 솔브할 수 있다. 추후 포스팅하겠다.