LCG Baby

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: lcg_parameter_recovery, modular_inverse

Summary

Walkthrough of the CUSTOM Crypto LCG Baby. Task: Recover LCG parameters m and c when only modulus n is known. Solution: Use 3 consecutive outputs to derive m via modular inverse, then compute c from the first equation.

Description

Task on recovering LCG parameters m and c when only the modulus n is known.

Analysis

Linear Congruential Generator (LCG)

x_{n+1} = (m * x_n + c) mod n

Vulnerability

If only the modulus n is known and 3 consecutive outputs x0, x1, x2 are given:

x1 = m * x0 + c (mod n)
x2 = m * x1 + c (mod n)

Subtracting the first from the second:

x2 - x1 = m * (x1 - x0) (mod n)
m = (x2 - x1) * (x1 - x0)^(-1) (mod n)

Then c is found from the first equation:

c = x1 - m * x0 (mod n)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from pwn import *

def modinv(a, n):
    """Modular inverse via extended Euclidean algorithm"""
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a % n, n)
    if gcd != 1:
        raise ValueError(f"Inverse doesn't exist: gcd({a}, {n}) = {gcd}")
    return x % n

def solve_lcg_level2(x0, x1, x2, n):
    """
    Recover m and c from LCG when only n is known.
    Requires 3 consecutive outputs.
    """
    # m = (x2 - x1) * inv(x1 - x0) mod n
    diff1 = (x1 - x0) % n
    diff2 = (x2 - x1) % n
    
    m = (diff2 * modinv(diff1, n)) % n
    
    # c = x1 - m * x0 mod n
    c = (x1 - m * x0) % n
    
    return m, c
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def predict_next(x, m, c, n):
    """Predict next LCG value"""
    return (m * x + c) % n

# Connect to server
r = remote('crypto-kids20.forkbomb.ru', PORT)

# Get modulus
n = int(r.recvline().decode().split('=')[1].strip())

# Get 3 outputs
x0 = int(r.recvline().decode().split(':')[1].strip())
x1 = int(r.recvline().decode().split(':')[1].strip())
x2 = int(r.recvline().decode().split(':')[1].strip())

# Recover m and c
m, c = solve_lcg_level2(x0, x1, x2, n)
print(f"[+] Recovered m = {m}")
print(f"[+] Recovered c = {c}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Predict next value
x3 = predict_next(x2, m, c, n)
print(f"[+] Predicted x3 = {x3}")

# Send answer
r.sendline(str(x3))
print(r.recvall().decode())

Math

System of equations:
x1 = m * x0 + c (mod n)   ... (1)
x2 = m * x1 + c (mod n)   ... (2)

Subtract (1) from (2):
x2 - x1 = m * (x1 - x0) (mod n)

Solve for m:
m = (x2 - x1) * (x1 - x0)^(-1) (mod n)

Substitute m into (1):
c = x1 - m * x0 (mod n)

Concepts

Modular Inverse

To find m, we need to compute (x1 - x0)^(-1) mod n.

The inverse exists only if gcd(x1 - x0, n) = 1. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

If n is prime, the inverse always exists for non-zero values.

Why 3 Outputs Are Sufficient

We have 2 unknowns (m and c) and 2 equations:

• x1 = m * x0 + c
• x2 = m * x1 + c

A system of 2 equations with 2 unknowns has a unique solution.

Alternative Method (via matrices)

 python read-only • copy allowed Copy
# Can also solve as a system of linear equations
# [x0, 1] * [m]   [x1]
# [x1, 1]   [c] = [x2]  (mod n)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering lcg_parameter_recovery, modular_inverse was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-03-09 • CUSTOM • LCG Baby • Difficulty: Medium