im lagging

crypto · LIT 2025 · hihitherethere

Problem

bro im lagging IM LAGGING bro this game sucks

Connect at nc litctf.org 31784

1KB

main.py

Analysis

This script creates a challenge based on two types of pseudo-random number generators:

1. LCG (Linear Congruential Generator)

2. LFG (Lagged Fibonacci Generator)

It generates a sequence of numbers using these, gives you part of the sequence, and then asks you to predict the next number If you guess correctly, you get the "flag" (like in a CTF challenge).

Step by step

1. LCG generation (lcg_generate)

Uses the formula:

$$x_{n+1} = (a * x_{n} + c) mod \space m$$

• Needs a seed (starting number), multiplier a, increment c, and modulus m.

• Produces a sequence of total numbers.

1. LFG generation (lfg_from_lcg)

• Starts with the LCG numbers.

• Then, for each new number, it sums certain previous outputs (chosen by "lags") and takes it modulo m.

• This makes it harder to predict than plain LCG.

Formula looks like:

$$y_n = \left( \sum_{\text{lag} \in \text{lags}} y_{n - \text{lag}} \right) \bmod m$$

1. Challenge creation (generate_challenge)

• Picks random lags (positions to look back from).

• Picks random seed, a, c, and m.

• Generates an LCG sequence, then turns it into an LFG sequence.

• Returns:

  • A list of recent LFG outputs (lfg_outputs)

  • The next LFG output (next_lfg_output), which is the "secret answer".

1. Main program flow

   • Waits for you to press Enter.

   • Prints the LFG outputs (the sequence).

   • Asks you to guess the next number.

   • If your guess is correct → prints "Correct" and shows the contents of flag.txt.

   • Otherwise → prints "Wrong".

🔎 The Vulnerability

The challenge uses an LFG (Lagged Fibonacci Generator) built on top of an LCG (Linear Congruential Generator).

• You get 10,000 outputs and must predict the next one.

• Normally hard, but the modulus $m=2^{59}-1$ is composite.

• By factoring it into two primes (using FactorDB), we can apply the Chinese Remainder Theorem (CRT) to work modulo smaller primes and recover the hidden parameters.

🔧 How the Exploit Works

1. Recover a and c:

   • Look at differences between outputs.

   • Solve equations mod PRIME1 and PRIME2, then recombine with CRT.

2. Rewind the LCG:

   • Once a and c are known, back-calculate the internal LCG states.

3. Find the 50 lags:

   • Compare expected vs real differences to detect which past positions (lags) are used.

4. Predict next output:

   • With LCG states + lags, compute the next LFG number exactly.

📜 Script Flow

• Connects to the server.

• Reads 10,000 outputs.

• Runs the recovery steps above.

• Sends the predicted number.

• If correct → prints the flag 🎉

5KB

solved.py

✅ In short, the challenge looks unbreakable at first, but by exploiting the composite modulus and carefully reversing the generator’s internals, we can fully recover its state and predict the future output.

Thank you 👏