Embryonic_Plant | T4QI-Blog

This challenge involves a custom Linear Congruential Generator (LCG) where the parameters of the RNG are tied to the factors of an RSA modulus.

Analysis of the RNG

The RNG class uses three primes: $p$, $q$, and $r$. The modulus $n$ is the product of these three:

$n = p \cdot q \cdot r$

The state of the RNG updates as follows:

$s_{i} = (s_{i-1} \cdot p + q) \pmod{r}$

We are given five consecutive outputs: $s_0, s_1, s_2, s_3, s_4$.

The Vulnerability

In a standard LCG ($s_{i+1} = a \cdot s_i + b \pmod{m}$), we can eliminate the constant $b$ by taking differences of consecutive terms:

$k_0 = s_1 - s_0 = (s_0 \cdot p + q) - s_0 \equiv (p-1)s_0 + q \pmod{r}$ (This isn’t quite right, let’s look at the sequence)

Actually, the standard way to solve for LCG parameters when the modulus is unknown (or a factor) is to use the property:

$k_i = s_{i+1} - s_i$

$k_1 = s_2 - s_1 \equiv p(s_1 - s_0) \equiv p \cdot k_0 \pmod{r}$ $k_2 = s_3 - s_2 \equiv p(s_2 - s_1) \equiv p \cdot k_1 \pmod{r}$

This implies:

$k_1^2 \equiv (p \cdot k_0)^2 \equiv p^2 \cdot k_0^2 \pmod{r}$

$k_2 \cdot k_0 \equiv (p^2 \cdot k_0) \cdot k_0 \equiv p^2 \cdot k_0^2 \pmod{r}$

Therefore:

$k_1^2 - k_2 \cdot k_0 \equiv 0 \pmod{r}$

This means that $r$ must be a common divisor of $n$ and the value $(k_1^2 - k_2 \cdot k_0)$.

Exploitation Steps

Recover $r$: Calculate $GCD(n, k_1^2 - k_2 \cdot k_0)$. Since $r$ is a large prime factor of $n$, this GCD will reveal $r$.
Recover $p$: Using the relation $k_1 \equiv p \cdot k_0 \pmod{r}$, we find $p = k_1 \cdot k_0^{-1} \pmod{r}$.
Recover $q$: Since $n = p \cdot q \cdot r$, we simply calculate $q = n / (p \cdot r)$.
Decrypt the Flag: With $p, q,$ and $r$ known, we calculate $\phi(n) = (p-1)(q-1)(r-1)$, derive the RSA private key $d$, and use its SHA256 hash as the AES key to decrypt the flag.

Solution

PYTHON

from Crypto.Util.number import GCD, inverse, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256

n = 517495531141413882619785629484073434334367374182425267832518928407090063228723780412707721134861704719046954060059519679044663362858039921326489634825074603137032497271990025361391019003853503655025773302574708586971339746175840486659372645050955030026562982540004381854193579383875586674576993334205627371394374175238089813479224550063267698552818981347863336705499123438535907072400999074105076872842922134632004525330943583893719811825964068870078476237254105191183175431815161806521309468291623594849405204251850057925238694969421092423608012736887311225866565727354867400387505854644025536146885666270169524014384999244678334643449618513882867624014754844721482636856663752713120622809209
s = [
    784218152416394405091964333052058791313859525150215968158667010620927852758462291022800955249222370074393328561762878930414694707920591658431974119310670333794867606006795899780363674768972994799569229309801063823717053583499300222,
    117844651397666849809258682128673914306177443815374652906886025265114752321815110890186970583580475821924619361762677026769047698813079218364902722849184274195414754785619739564959255224997078907488139425647648408247154825061716309,
    61493148556640923069669308478684643760453844796631149909998916055995969830079591336005848473905026088451064847063880787258045070363359478597469452194254550973763127419036031037505421050223740876723920669420589492475793536817752179,
    385226573805950622034434256055680934318291330051514311585010364332881865675585231530632546612059411877376139482924838615065334915075901680603748606342007947170890951993914739012558552417988581119289931292019725974545209615603031339,
    784431720042683594850895884434968054900304420502856912529544483628362060694160095173569455027892192687604844742111377055558499818308721461221742196792453489683151795374989702609801983203785226494247429342826031503288026649229931492,
]
enc_flag = "bf78c07aee8194ffea6b4029887d22cf0aa17ada6d9b091589f7248c4b64a292d77912e95fe992cdd096baa360042fa67eba1c71cf7ad92ad8fab3c5398f6e87b825f14d015a8021669138d85f7b11b5"

k = []

for i in range(1, len(s)):
    k.append(s[i] - s[i - 1])

mult_r = k[1] ** 2 - k[2] * k[0]

r = GCD(n, mult_r)
k_inv = inverse(k[0], r)
p = (k_inv * k[1]) % r

q = n // (p * r)

assert n == p * q * r

phi = (p - 1) * (q - 1) * (r - 1)

d = inverse(65537, phi)

key = sha256(long_to_bytes(d)).digest()
cipher = AES.new(key, AES.MODE_ECB)

flag = cipher.decrypt(bytes.fromhex(enc_flag))

print(unpad(flag, 16))