Embryonic Plant — HackTheBox

Description

A crypto challenge where a custom PRNG based on LCG (Linear Congruential Generator) is combined with RSA encryption. The server:

1. Generates three 768-bit primes p, q, r (with condition p < r and q < r)
2. Computes RSA modulus n = p * q * r
3. Uses p as multiplier and q as increment in LCG with modulus r
4. Outputs 5 consecutive LCG states
5. Encrypts the flag with AES-ECB using key SHA256(long_to_bytes(d)), where d is the RSA private exponent
6. Outputs n, 5 states, and the encrypted flag

server.py

from Crypto.Util.number import getPrime, long_to_bytes, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256

class RNG:
    def __init__(self, seed):
        self.e = 0x10001
        self.s = seed

        self.r = getPrime(768)
        while True:
            self.p, self.q = getPrime(768), getPrime(768)
            if self.p < self.r and self.q < self.r:
                break

        self.n = self.p * self.q * self.r
        phi = (self.p - 1) * (self.q - 1) * (self.r - 1)
        self.d = inverse(self.e, phi)

    def next(self):
        self.s = (self.s * self.p + self.q) % self.r
        return self.s

def main():
    rng = RNG(getPrime(512))
    rns = [rng.next() for _ in range(5)]

    key = sha256(long_to_bytes(rng.d)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    enc_flag = cipher.encrypt(pad(open("flag.txt", "rb").read(), 16)).hex()

    print(f'n = {rng.n}')
    print(f's = {rns}')
    print(f'enc_flag = {enc_flag}')

if __name__ == "__main__":
    main()

Server Data

n = 1150602878033962579855587435264463985561012991119468384668592829382526932589050290371404229384060543197185078682129439131294791379084500189190231412746161286693154884895141125456931328624900187394941798752850819099764919782782642330580439797482460200468145633885876719222177123707152556442412289759906022614679836201388628305159526565300196360493229419912194500227149338920601332146540404790692796377022404483802701157711406436843618897489140695102107253071354750636710631299814041318603795393293540269551015332763767683913171219245087255659850460905590634163331241697384677357454776163885003393547816995455512951384945606579995325804502583579173867892740439373075319665455440581859481403053903
s = [1194181135724590315929397382099851721253320971527479487532432173501109537761907741713114873723774928650610296973362872696735288562020017463106691286557392826219185288558801536137192654049666478897366710748464296356830733752510988415, 31426380591662426184590447064387998555608291456216952585360896208704737026291205241216599152515584113271024086240872988211180741801389233254535923885617526085612402544232997514857109445672407534854581574060993434437090934539959516, 37584685120235974231837935172129411514430552023472108029276203384894012122983665837737720432802304685439812117915741229535003326333800172880689092862772080496309574091484963943534926427850064533183894201506708279074560566704292759, 1004001166364963680862365509409110302013325687135947580582960207226383134361098786676605936927176573806063127486111911772996510243998842906106067363062350444198723856366258512848370757982044054323128350525984342093530669656581965702, 1103967668262241312837591587456987006921418992697329349746145242232970298143874165739086070439781778793795257242320365423073697045399567727802612172351347216088757962123686104498466416134111880555812483871124434169981201776586041585]
enc_flag = a5897ee8bccce3f9988f35e8af4f6d608127e533e94c293a3fb3c49ae56b7074b8097535d64ca8568b2ff7614abb73f82c9bb88f7eb5419e41bd31f5498c5d8c8210189c9d079da5960f16f3264e27a8

Analysis

Challenge Structure

The challenge combines two cryptographic constructions:

1. LCG (Linear Congruential Generator): s_{i+1} = s_i * p + q (mod r) — parameters p (multiplier), q (increment), r (modulus) are simultaneously the prime factors of RSA modulus n
2. Multi-prime RSA: n = p * q * r with three 768-bit primes

Key Observation: Recovering LCG Modulus via GCD

From consecutive LCG outputs s_0, s_1, s_2, s_3, s_4 we compute differences:

t_i = s_{i+1} - s_i

Since s_{i+1} = p * s_i + q (mod r), the differences satisfy:

t_{i+1} = p * t_i (mod r)

This means t_{i+1} * t_{i-1} - t_i^2 ≡ 0 (mod r) — the product of "outer" terms minus the square of the "middle" term is divisible by modulus r. Computing several such values and taking their GCD recovers r (possibly with small extra factors).

Recovery Chain

5 LCG outputs → r (via GCD) → p (via t₁/t₀ mod r) → q (via s₁ - s₀·p mod r) → d → AES key → flag

Solution

Step 1: Recovering r from LCG Outputs

t = [s[i+1] - s[i] for i in range(len(s) - 1)]

# t_{i+1} * t_{i-1} - t_i^2 ≡ 0 (mod r)
zeros = []
for i in range(1, len(t) - 1):
    val = t[i+1] * t[i-1] - t[i] * t[i]
    zeros.append(abs(val))

r_candidate = gcd(zeros[0], zeros[1])

GCD may contain extra small factors. If r_candidate doesn't divide n, we sequentially divide by small primes and check divisibility of n:

if n % r_candidate != 0:
    temp = r_candidate
    for small_p in range(2, 10000):
        while temp % small_p == 0:
            temp //= small_p
            if n % temp == 0:
                r = temp
                break

Step 2: Recovering p from LCG

From t_{i+1} = p * t_i (mod r):

p = (t[1] * inverse(t[0], r)) % r

Verification: (p * t[1]) % r == t[2] % r

Step 3: Recovering q from LCG

From s_1 = s_0 * p + q (mod r):

q = (s[1] - s[0] * p) % r

Verification: (s[1] * p + q) % r == s[2]

Step 4: Verifying Factorization

assert p * q * r == n  # n = p * q * r

Step 5: Computing RSA Private Key

e = 0x10001
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e, phi)

Step 6: Decrypting the Flag

key = sha256(long_to_bytes(d)).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(bytes.fromhex(enc_flag_hex))
# Remove PKCS7 padding

Full Solve Script

#!/usr/bin/env python3
"""
Crypto solve: Embryonic Plant — HackTheBox
LCG state recovery → multi-prime RSA factorization → AES decryption
"""

from math import gcd
from Crypto.Util.number import long_to_bytes, inverse
from Crypto.Cipher import AES
from hashlib import sha256

# Given data
n = 1150602878033962579855587435264463985561012991119468384668592829382526932589050290371404229384060543197185078682129439131294791379084500189190231412746161286693154884895141125456931328624900187394941798752850819099764919782782642330580439797482460200468145633885876719222177123707152556442412289759906022614679836201388628305159526565300196360493229419912194500227149338920601332146540404790692796377022404483802701157711406436843618897489140695102107253071354750636710631299814041318603795393293540269551015332763767683913171219245087255659850460905590634163331241697384677357454776163885003393547816995455512951384945606579995325804502583579173867892740439373075319665455440581859481403053903
s = [
    1194181135724590315929397382099851721253320971527479487532432173501109537761907741713114873723774928650610296973362872696735288562020017463106691286557392826219185288558801536137192654049666478897366710748464296356830733752510988415,
    31426380591662426184590447064387998555608291456216952585360896208704737026291205241216599152515584113271024086240872988211180741801389233254535923885617526085612402544232997514857109445672407534854581574060993434437090934539959516,
    37584685120235974231837935172129411514430552023472108029276203384894012122983665837737720432802304685439812117915741229535003326333800172880689092862772080496309574091484963943534926427850064533183894201506708279074560566704292759,
    1004001166364963680862365509409110302013325687135947580582960207226383134361098786676605936927176573806063127486111911772996510243998842906106067363062350444198723856366258512848370757982044054323128350525984342093530669656581965702,
    1103967668262241312837591587456987006921418992697329349746145242232970298143874165739086070439781778793795257242320365423073697045399567727802612172351347216088757962123686104498466416134111880555812483871124434169981201776586041585,
]
enc_flag_hex = "a5897ee8bccce3f9988f35e8af4f6d608127e533e94c293a3fb3c49ae56b7074b8097535d64ca8568b2ff7614abb73f82c9bb88f7eb5419e41bd31f5498c5d8c8210189c9d079da5960f16f3264e27a8"

# Step 1: Compute differences t_i = s_{i+1} - s_i
t = [s[i + 1] - s[i] for i in range(len(s) - 1)]

# Step 2: t_{i+1} * t_{i-1} - t_i^2 ≡ 0 (mod r) → GCD recovers r
zeros = []
for i in range(1, len(t) - 1):
    val = t[i + 1] * t[i - 1] - t[i] * t[i]
    zeros.append(abs(val))

r_candidate = zeros[0]
for z in zeros[1:]:
    r_candidate = gcd(r_candidate, z)

# Extract r (remove small factors if needed)
if n % r_candidate == 0:
    r = r_candidate
else:
    temp = r_candidate
    for small_p in range(2, 10000):
        while temp % small_p == 0:
            temp //= small_p
            if n % temp == 0:
                r = temp
                break
        if n % temp == 0:
            r = temp
            break

assert n % r == 0
pq = n // r

# Step 3: Recover p from LCG — p = t[1] / t[0] mod r
p = (t[1] * inverse(t[0], r)) % r
assert (p * t[1]) % r == t[2] % r

# Step 4: Recover q from LCG — q = s[1] - s[0]*p mod r
q = (s[1] - s[0] * p) % r
assert (s[1] * p + q) % r == s[2]

# Step 5: Verify factorization
assert p * q * r == n

# Step 6: Compute RSA private key
e = 0x10001
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e, phi)

# Step 7: Decrypt flag
key = sha256(long_to_bytes(d)).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc_flag = bytes.fromhex(enc_flag_hex)
flag = cipher.decrypt(enc_flag)

# Remove PKCS7 padding
pad_len = flag[-1]
if pad_len <= 16 and all(b == pad_len for b in flag[-pad_len:]):
    flag = flag[:-pad_len]

print(f"Flag: {flag.decode()}")

Notes

• LCG modulus recovery — a classic technique. For LCG s_{i+1} = a*s_i + b (mod m), differences t_i = s_{i+1} - s_i satisfy t_{i+1} = a*t_i (mod m), hence t_{i+1}*t_{i-1} - t_i^2 ≡ 0 (mod m). GCD of several such values yields m (or a multiple of it)
• Multi-prime RSA weakens security: each factor is smaller than in standard RSA with the same n size, and phi(n) is easier to compute once factorization is known
• GCD candidate may contain extra small factors — need to sequentially divide and check divisibility of n
• The challenge elegantly connects two domains: PRNG (LCG) and asymmetric cryptography (RSA), using the same primes in both contexts