# im lagging

## Problem

bro im lagging\
IM LAGGING\
bro this game sucks

Connect at `nc litctf.org 31784`

{% file src="/files/RX154xYehk39UYbUd42D" %}

## 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.

2. 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
$$

3. **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".

4. **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](https://factordb.com/index.php?query=576460752303423487)), 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 🎉

{% file src="/files/0v3U09WbFW6KjJ7fXTW6" %}

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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/im-lagging.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.