Cyberleague 2025

Baby LCG

Crypto | Pre-CTF

I just started learning about LCG!

Unfortunately, it seems that LCG is quite weak, given how there are so many papers showing how easily you can crack LCG parameters.

Findings from the given source file:

• An AES-CBC encrypted ciphertext with its IV

• The modulus and three terms (19th, 38th, and 57th) from a Linear Congruential Generator (LCG)

• The 1st term of the LCG serves as the AES encryption key

The solution approach is to reverse the given LCG numbers to get the initial term for the decryption key. Here is a good read on LCG Attack : https://msm.lt/posts/cracking-rngs-lcgs/

The LCG generator is defined by the recurrence relation:

$$X_{n+1} = aX_n + c \: mod \: p$$

What makes this challenge unique is that instead of consecutive terms, we're given values at fixed intervals of 19. However, this property can still be exploited to recover the initial seed.

For any LCG sequence, we can express terms with fixed intervals using the same coefficient structure. Consider the following relations:

$$X_6 = a^2 X_4 + c \cdot \frac{a^2 - 1}{a - 1} \mod p$$

$$X_4 = a^2 X_2 + c \cdot \frac{a^2 - 1}{a - 1} \mod p$$

Notice that despite the gaps between terms, the coefficient patterns remain consistent at equal intervals. We can apply this principle to our given terms $X_{19}$, $X_{38}$ and $X_{57}$ to determine the coefficients needed to calculate the initial term $X_0$.

Here is the solution script:

from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from sympy import mod_inverse
import functools
import binascii
import math

R19 = 101273243801089515795834486273327091034
R38 = 142935056647570887854437422902380586165
R57 = 63472453299747839124695261376587470430
mod = 206448685018571863403655106945756783931

# https://ctftime.org/writeup/12046
reduce = functools.reduce
gcd = math.gcd

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return multiplier, increment

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * mod_inverse(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

# Getting the (a) coefficent & (c) coefficient
mult, inc = crack_unknown_multiplier([R19, R38, R57], mod)

# Calculate the key and decrypt the ciphertext
key = (mod_inverse(mult, mod) * (R19 - inc)) % mod
ct = binascii.unhexlify(b'6e573d15e915e7d9a321b77bec1f21ebcbfddd1755b216f6971ac5382f6d787836dd1397fea445ed453fd6a12bd610b103affdc17334e923b0f4d6856c716488')
iv = binascii.unhexlify(b'e1735ebc3148a450327887b2186ffa61')
cipher = AES.new(long_to_bytes(key), AES.MODE_CBC, iv)
decrypted_data = cipher.decrypt(ct)
print(decrypted_data.decode())

└─$ CYBERLEAGUE{LCG_W1th_N0n-C0n53cu71v3_0u7pu7_15_57111_W34k!}