Pwn-la-Chapelle

Pwn-la-Chapelle

Popping Shells and Stealing Flags at RWTH Aachen University

Writeup – GPN CTF 2025: Paranoid

by doriank - - Estimated reading time: 17 minutes

Challenge Overview

  • Name: Paranoid
  • Category: Crypto
  • Points: 383/500
  • Solves: 6
  • Author: Alkalem
  • Challenge Files: paranoid.tar.gz
  • Flag Format: GPNCTF{…}

We are presented with a pseudo-random number generator that implements a linear congruential generator (LCG) with parameters that are themselves randomly generated at program start.

1[...]
2def main():
3[...]
4  MUL = secrets.randbelow(MODULUS)
5  ADD = secrets.randbelow(MODULUS)
6  INITIAL = secrets.randbelow(MODULUS)
7
8  rng = RNG(INITIAL, MODULUS, ADD, MUL)
Click here to expand

Then, a random 128-bit key is generated and the flag is encrypted with AES in counter mode, with the IV being selected by the previously initialized LCG, and the resulting ciphertext is printed to the console.

1  KEY = secrets.token_bytes(16)
2  aes = AES(KEY)
3
4  flag_ct = aes.encrypt_ctr(pad(FLAG), rng.get_iv())
5  print(flag_ct.hex())

Finally, we are prompted to enter a plaintext, which the program will graciously encrypt for us as it did with the flag before, but using the next random value from the LCG as IV. Crucially though, it adds the first byte of the plaintext as a number to the internal state of the LCG. 

1[...]
2    while True:
3      plaintext = bytes.fromhex(input("Give me something to encrypt (hex):"))
4[...]
5      ciphertext = aes.encrypt_ctr(pad(plaintext), rng.get_iv())
6      print(ciphertext.hex())
7      rng.reseed(int.from_bytes(plaintext[:1])) # <--- This is the vulnerability!
8[...]
Click here to expand

The Idea

This is how CTR mode encryption works: CTR-Mode

The IV (called Nonce in the picture above) is encrypted via the block cipher (in this case AES) and then XORed with the plaintext. If we know the plaintext to a particular ciphertext, we can trivially recover the keystream by XORing the two, therefore it is essential that an IV is never reused after a plaintext has been encrypted with it.

In our case, the IV is determined by an LCG. If we can alter its state in such a way that it generates the IV of the flag ciphertext again, we can encrypt our own plaintext with the same IV, recover the keystream via XOR and use it to decrypt the flag ciphertext! 1

Step 1: Reverse engineering the LCG

Before we can alter the LCG state to produce the IV we want, we need to recover its parameters.

Recall that the LCG is created as follows:

1  MUL = secrets.randbelow(MODULUS)
2  ADD = secrets.randbelow(MODULUS)
3  INITIAL = secrets.randbelow(MODULUS)
4
5  rng = RNG(INITIAL, MODULUS, ADD, MUL)

Luckily for us, we can recover all the parameters with just three values of the LCG! The IV is always saved as the first block of a CTR mode ciphertext, so to retrieve our three LCG values, we can use the flag ciphertext IV, and generate two more ciphertexts with a plaintext of zeros as to not modify the internal LCG state with rng.reseed(…).

From the RNG source code we extract the following equations:

\[ \begin{aligned} \text{iv}_0 &:= \text{INITIAL} \\ \text{iv}_{i+1} &:= \text{iv}_i \cdot \text{MUL} + \text{ADD} \text{ (mod MODULUS)} \end{aligned} \]

For simplicity I will abbreviate $N := \text{MODULUS}$, $m := \text{MUL}$ and $a := \text{ADD}$

We arrive at the following system of equations for our three IVs:

\[ \begin{aligned} \text{iv}_0 &= \text{INITIAL} \\ \text{iv}_{1} &= \text{iv}_0 \cdot m + a &\text{ (mod $N$)} \\ \text{iv}_{2} &= (\text{iv}_0 \cdot m + a) \cdot m + a &\text{ (mod $N$)} \\ &= \text{iv}_0 \cdot m^2 + a \cdot m + a &\text{ (mod $N$)} \end{aligned} \]

And after some algebra that is left as an exercise to the reader, we can express $a$ and $m$ in terms of the three IVs:

\[ \begin{aligned} m &= (\text{iv}_2 - \text{iv}_1) \cdot (\text{iv}_1 - \text{iv}_0)^{-1} &\text{ (mod $N$)} \\ a &= \text{iv}_1 - \text{iv}_0 \cdot m &\text{ (mod $N$)} \\ \end{aligned} \]

Because $N$ is prime, we can always uniquely recover the parameters and state of the RNG, and proceed to the next step.

Step 2: Reproducing the IV

Our LCG definition from the previous step had a small omission: the reseed parameter. Recall: the first byte of the plaintext is added to the internal state of the LCG, and we will use this to control the LCG state to produce the IV we want. But let’s first model this additional parameter mathematically:

\[ \begin{aligned} \text{LCG}(x) &:= x\cdot m + a &\text{ (mod $N$)} \\ \text{iv}_0 &:= \text{INITIAL} + d_0 \\ \text{iv}_{i + 1} &:= \text{LCG}(\text{iv}_i) + d_{i+1} \\ \text{with } d_i &\in [0, 255] \text{ for all } i \\ \end{aligned} \]

Here, LCG is the LCG function we derived in the previous step, and the $d_i$ are the reseed values, which are determined by the first byte of the plaintext we encrypt. In our case $d_i = 0$ for $i \in \{0, 1, 2\}$, because we used a plaintext of zeros to retrieve the IVs.

Our goal:

\[ \begin{aligned}\ \text{Find } d_0, d_1, &\dots, d_i \text{ such that }& \\ \text{iv}_i &\equiv \text{flag_iv} &\text{ (mod $N$)} \\ \end{aligned} \]

Note what happens when we simplify multiple iterations of the LCG with reseed values:

\[ \begin{aligned} \text{iv}_1 &= LCG(\text{iv}_0) + d_1 &\text{ (mod $N$)} \\ \text{iv}_2 &= LCG(\text{iv}_1) + d_2 &\text{ (mod $N$)} \\ &= LCG(LCG(\text{iv}_0) + d_1) + d_2 &\text{ (mod $N$)} \\ &= ((\text{iv}_0 \cdot m + a + d_1) \cdot m + a) + d_2 &\text{ (mod $N$)} \\ &= ((\text{iv}_0 \cdot m + a) \cdot m + a) + d_1 \cdot m + d_2 &\text{ (mod $N$)} \\ &= LCG(LCG(\text{iv}_0)) + d_1 \cdot m + d_2 &\text{ (mod $N$)} \\ \vdots \\ \text{iv}_i &= LCG^{(i)}(\text{iv}_0) + \sum_{j=1}^{i} d_j \cdot m^{i-j} &\text{ (mod $N$)} \\ \end{aligned} \]

Now our problem of reproducing the IV is reduced to finding suitable $d_0, d_1, \dots, d_i$ such that the following equation holds:

\[ \begin{aligned} LCG^{(i)}(\text{iv}_0) + \sum_{j=1}^{i} d_j \cdot m^{i-j} \equiv \text{flag_iv} &\text{ (mod $N$)} \end{aligned} \]

This is just a linear equation in the $d_j$ variables!

Step 3: Solving the equation

\[ \begin{aligned} \sum_{j=1}^{i} d_j \cdot m^{i-j} \equiv \text{flag_iv} - LCG^{(i)}(\text{iv}_0) &\text{ (mod $N$)} \end{aligned} \]

Finding a solution to the equation above is quite trivial if the constraints $d_i \in [0, 255]$ are ignored. We could simply set $d_{i} = \text{flag_iv} - LCG^{(i)}(\text{iv}_0)$, and be done. But what we are looking for, is a small solution, one that does not exceed the bounds of $[0, 255]$ for every $d_j$.

There is a general solution to this problem, called the Coppersmith method for multivariate polynomials. With it, one can solve for small roots of modular polynomial equations, with small meaning that the range of the variables is bounded. You can find an implementation of it here. In this case though, the resulting lattice Matrix explodes in size with the high number of variables, and I was only able to solve up to $i = 8$ on my laptop, which is still roughly 64 bits2 away from the flag IV, so I had to use a different approach.

In the following section I will describe how I solved the problem using a Lattice and Babai’s nearest plane algorithm. If these terms are unfamiliar to you, I recommend reading this article and this paper first.

In essence, we construct a lattice in which each vector corresponds to a solution of the equation above. We then apply Babai’s nearest plane algorithm to find a vector whose components satisfy $d_j \in [0, 255]$ for all $j$.

A vector in the lattice will look like this:

\[ \begin{aligned} k &:= \text{flag_iv} - LCG^{(i)}(\text{iv}_0) \\ L &:= \textit{"a large value"} \\ v &= \left(d_1, \dots, d_i, j_1 k - \sum_{j=1}^{i} d_j \cdot m^{i-j} + j_2 N, j_1 L\right) \in \mathbb{Z}^{i+2} \\ &\text{with $j_1$, $j_2$}\in \mathbb{Z} \\ \end{aligned} \]

This vector is constructed such that the first $i$ components correspond to the $d_j$ values we are looking for, the next component is the difference between $\text{iv}_i$ and $\text{flag_iv}$, and the last component is a large value which we will use to control the size of $j_1$. $j_2$ is necessary because our equation is modulo $N$ and not over all the integers.

Note that we do not need $L$ for the solution, but rather we couple it with $k$ to force $j_1$ to be small (ideally equal to 1) when we search for a small vector in the lattice. Also note that the first few $d_j$ will be zero due to our method of reverse engineering the LCG and can thus be omitted, but this is a minor implementation detail.

The first vector of our lattice basis is quite obvious:

\[ \begin{aligned} b_0 &= (0, \dots, 0, k, L) \\ \end{aligned} \]

Intuitively, this vector corresponds to the case $d_j = 0$ for all $j$, which results in $\text{iv}_i \equiv LCG^{(i)}(\text{iv}_0)$.

Then we encode the linear operation of the $d_j$ values:

\[ \begin{aligned} b_1 &= (1, 0, \dots, 0, - m^{i-1}, 0) \\ b_2 &= (0, 1, \dots, 0, - m^{i-2}, 0) \\ &\vdots \\ b_i &= (0, 0, \dots, 1, - m^{i-i}, 0) \\ \end{aligned} \]

These follow immediately from the vector definition above.

The last basis vector is responsible for modular arithmetic:

\[ \begin{aligned} b_{i+1} &= (0, \dots, 0, N, 0) \end{aligned} \]

This encodes the fact that $k \equiv k + j_2 N$ (mod $N$) for any integer $j_2$.

The solution vector that we are looking for will have the form:

\[ \begin{aligned} v &= (d_1, d_2, \dots, d_i, 0, L) \\ \text{with } d_j &\in [0, 255] \text{ for all } j \\ \end{aligned} \]

i.e. we are looking for those $d_j$ that satisfy $1 \cdot k - \sum_{j=1}^{i} d_j \cdot m^{i-j} \equiv 0\text{ (mod $N$)}$.

Because the second to last component is so much larger than all other components (as can be seen by the basis vectors), the shortest non-zero vector in this lattice will almost surely be the solution we are looking for3. Unfortunately, a small vector is not guaranteed to have components in $[0, 255]$ but is more likely to be centered around zero and thus include negative values for some $d_j$. This is why we apply Babai’s nearest plane algorithm to find the closest vector not to the origin $0$, but to $127$ for all the $d_j$ components.

Our final Babai target vector looks like this:

\[ \begin{aligned} t &= (127, 127, \dots, 127, 0, L) \end{aligned} \]

By setting $L = 255^{2}$ and iterating $i = 1,\dots,20$ in the implementation, we can reliably find a solution vector in about a second.

Recovered flag: GPNCTF{iF_YOU_w4nNa_BE_pArAnoid,yOu_G0T_t0_bE_GooD}

The Implementation

This is my solve script implemented in SageMath. It differs slightly from the writeup because it made the explanation here simpler, but the core logic is the same. In the script, the $d_j$ are sorted in reverse order, and there is some additional logic to handle the first few $d_j$ being zero. The order of the basis vectors is also slightly different. If you have any questions about the implementation, feel free to @ me on discord, you can find the invite on the homepage of this blog.

  1[...]
  2def attack():
  3    p = remote("greenwind-of-epic-victory.gpn23.ctf.kitctf.de", "443", ssl=True)
  4    flag_ct = p.recvline().strip().decode()
  5    flag_ct = bytes.fromhex(flag_ct)
  6    print("Flag ciphertext:", flag_ct.hex())
  7    flag_iv = flag_ct[:16]
  8
  9    p.sendlineafter(b"Give me something to encrypt (hex):", b"00")
 10    a2 = bytes.fromhex(p.recvline().strip().decode())[:-16]
 11    print("a2:", a2.hex())
 12    p.sendlineafter(b"Give me something to encrypt (hex):", b"00")
 13    a3 = bytes.fromhex(p.recvline().strip().decode())[:-16]
 14    print("a3:", a3.hex())
 15
 16    # reconstruct the RNG
 17    a1 = int.from_bytes(flag_iv, "big")
 18    a2 = int.from_bytes(a2, "big")
 19    a3 = int.from_bytes(a3, "big")
 20    mul = (a3 - a2) * pow(a2 - a1, -1, MODULUS) % MODULUS
 21    add = (a2 - a1 * mul) % MODULUS
 22    print(f"mul: {mul}, add: {add} reconstructed")
 23
 24    found_valid_sol = False
 25    valid_sol = None
 26
 27    # test different lengths of paths
 28    for iv_num in range(1, 20):
 29        if found_valid_sol:
 30            break
 31        # now we have reconstructed the RNG
 32        local_rng = RNG(a1, MODULUS, add, mul)
 33        assert local_rng.next() == a1
 34        assert local_rng.next() == a2
 35        assert local_rng.next() == a3
 36
 37        # calculate lcg^{iv_num}
 38        ivs = []
 39        for i in range(iv_num + 1):
 40            ivs.append(local_rng.next())
 41
 42        # Construct lattice for modular equation
 43        M = Matrix(ZZ, iv_num + 2, iv_num + 2)
 44        # target vector for babais algorithm, we need this because our solution needs to be strictly positive
 45        # so we search for a solution around 127 (because we need 0-255)
 46        targetVector = vector(ZZ, iv_num + 2)
 47
 48        for i in range(iv_num):
 49            M[i, i] = 1
 50            M[i, -2] = -pow(mul, i, MODULUS)
 51            targetVector[i] = 127
 52
 53        largeVal = 255 ^ 2
 54        M[-2, -2] = (a1 - ivs[-1]) % MODULUS
 55        M[-2, -1] = largeVal
 56        M[-1, -2] = MODULUS
 57        targetVector[-2] = 0
 58        targetVector[-1] = largeVal
 59
 60        def test_sol(row):
 61            # just some helper func to see if our sol is valid
 62            nonlocal valid_sol, found_valid_sol
 63            test_rng = RNG(a1, MODULUS, add, mul)
 64            for i in range(3):
 65                test_rng.next()
 66
 67            for i in range(iv_num):
 68                iv_val = test_rng.next()
 69                test_rng.reseed(row[iv_num - i - 1])
 70            iv_val = test_rng.next()
 71
 72            if iv_val == a1:
 73                print(f"Found m_vals: {row}")
 74
 75                if all(x >= 0 and x <= 255 for x in row[:-2]):
 76                    print("Found a valid solution!")
 77                    valid_sol = row
 78                    found_valid_sol = True
 79
 80        someVec = babai(M, targetVector)
 81        print("Babai vec: ", someVec)
 82        # because the last reseed value has a tiny influence, we brute force its value here
 83        for testval in range(255):
 84            someVec[0] = testval
 85            test_sol(someVec.list())
 86            if found_valid_sol:
 87                break
 88
 89    assert found_valid_sol, "No valid solution found"
 90    print("Valid solution found:", valid_sol)
 91
 92    # Now we send the reseed values to the server
 93    iv_num = len(valid_sol) - 2
 94    for i in range(len(valid_sol) - 2):
 95        print(f"m_{i} = {valid_sol[i]}")
 96        seed_thing = valid_sol[iv_num - i - 1]
 97        print(f"Reseeding with {seed_thing}")
 98        p.sendlineafter(
 99            b"Give me something to encrypt (hex):", bytes([seed_thing]).hex().encode()
100        )
101    # now this is the crucial one, the next encryption will use the flag iv
102    # so we send a plaintext of all zeros, which will give us the keystream for the flag iv
103    p.sendlineafter(b"Give me something to encrypt (hex):", b"00" * len(flag_ct))
104    uncipher_block = p.recvline().strip().decode()
105    uncipher_block = bytes.fromhex(uncipher_block)
106
107    print("Unciphered block:", uncipher_block.hex())
108    if uncipher_block[:16] != flag_iv:
109        print("Failed to uncipher the flag block")
110        return
111
112    all_text = ""
113    for block in range(len(flag_ct) // 16):
114        flag_block = uncipher_block[block * 16 : (block + 1) * 16]
115
116        flag_block = xor_bytes(flag_block, flag_ct[(block) * 16 : (block + 1) * 16])
117        print(
118            f"Flag block {block}: {flag_block.hex()} {flag_block.decode(errors='ignore')}"
119        )
120        all_text += flag_block.decode(errors="ignore")
121    print("Recovered flag:", all_text.strip())
122[...]
Click here to expand

Conclusion

Don’t let the user reseed your PRNG with arbitrary values!

  1. Because CTR mode is symmetric, you could also immediately submit the flag ciphertext to the program, and the “encrypted” output will be the flag plaintext! ↩︎

  2. Intuitively, each $d_j$ approximately increases the space of reachable IVs by a factor of 256, because $d_j$ can take any value in $[0, 255]$. Because $\text{flag_iv} \in [0, N] = [0, 2^{128} + 51]$, we need $i \approx 16$ to be able to reach the flag IV from our state. ↩︎

  3. This is not entirely true; Look again at the basis vector $b_i$. Because its influence on the second to last component is so small, it is possible that the solution we are looking for is the shortest vector in the lattice plus or minus a multiple of $b_i$. For this reason, I simply loop through all possible values of $d_i$ in my implementation as a workaround. ↩︎

rssfacebooktwittergithubyoutubemailspotifylastfminstagramlinkedingooglegoogle-pluspinterestmediumvimeostackoverflowredditquoraquora