LIT CTF 2023: Polypoint

Author	Max Niederman
Published	2023-08-08
Tags	hacking ctf ctf/lit
Description	Writeup of the crypto/polypoint challenge from the LIT CTF 2023.

This encryption scheme is mathematically unbreakable if you don’t have all the keys! You learnt so in grade school, right?

We are given two files: encode.py and encoded.txt.

encode.py:

from secrets import SystemRandom

gen = SystemRandom()

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

assert len(flag) == 76
c = int.from_bytes(flag)

poly = [c]
for _ in range(10):
    poly.append(gen.randrange(pow(10, 11), pow(10, 12)))

for _ in range(10):
    x = gen.randrange(pow(10, 11), pow(10, 12))
    v = 1
    y = 0
    for i in range(11):
        y += poly[i] * v
        v *= x
    print(f"({x},{y})")

Let’s analyze this in pieces.

from secrets import SystemRandom

gen = SystemRandom()

This is a cryptographic PRNG, so it should probably be treated as truly random for the purposes of the solution.

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

assert len(flag) == 76
c = int.from_bytes(flag)

This is pretty standard for crypto challenges: read the flag and encode it as an integer. We are also given the extra piece of information that the flag is 76 bytes long, which turns out to be useful later.

poly = [c]
for _ in range(10):
    poly.append(gen.randrange(pow(10, 11), pow(10, 12)))

So it creates a list of eleven numbers, the first being the integer representation of the flag, and the rest being random integers between $1 0^{11}$ and $1 0^{12}$ . I’m going to refer to each of these numbers as $p_{1}$ , $p_{2}$ , and so on up to $p_{11}$ , and the whole list as the eleven-dimensional vector $p$ .

for _ in range(10):
    x = gen.randrange(pow(10, 11), pow(10, 12))
    v = 1
    y = 0
    for i in range(11):
        y += poly[i] * v
        v *= x
    print(f"({x},{y})")

One important thing to notice is that nothing is mutated inbetween iterations of the outer loop. This means that we essentially have ten independent trials relating x to y.

Now, let’s look at what each iteration actually does. First, it initializes the variable x to a random integer between $1 0^{11}$ and $1 0^{12}$ (like $p_{2} ... p_{11}$ ); the variable v to one; and the variable y to zero.

Then, it runs a nested loop for eleven iterations. Each iteration first adds $p_{i}$ times the current value of v to y, then multiplies v by x.

The first thing to notice is that we know the value of v at every iteration of the inner loop. I’ll denote the value of v in the $k$ -th outer loop iteration (trial) and $i$ -th inner loop iteration as $v_{k, i}$ , and the value of x as $x_{k}$ . Then we have:

v_{k, i} = x_{k}^{i}

y starts at zero, so its final value will just be the sum of poly[i] * v over the whole inner loop. Written in math notation (with $y_{k}$ being the final value of y for the $k$ -th trial):

y_{k} = i = 1 \sum 11 p_{i} v_{k, i}

The key realization is that this is also the dot product between $p$ and $v_{k}$ :

y_{k} = p \cdot v_{k}

Now we can write this out for all ten trials:

v_{1} \cdot p v_{2} \cdot p v_{10} \cdot p = y_{1} = y_{2} ⋮ = y_{10}

This is just a linear system of equations! Let’s rewrite it as a matrix equation:

⎣ ⎡ v_{1, 1} v_{2, 1} ⋮ v_{10, 1} v_{1, 2} v_{2, 2} ⋮ v_{10, 2} \dots \dots ⋱ \dots v_{1, 11} v_{2, 11} ⋮ v_{10, 11} ⎦ ⎤ p = y

We can’t just plug this in to a calculator and solve it though. The system is underconstrained, so we need some way to limit the search to find the unique true solution, $p$ .

First of all, we know that $p$ is made up of all integers ( $p \in Z^{11}$ ), so we should only look for integer solutions. We also have some lower and upper bounds for each of the entries of $p$ :

$p_{2}, p_{3}, ..., p_{11}$ are all in the interval $[1 0^{11}, 1 0^{12}]$ .
The flag is 78 bytes long, so $p_{1}$ , its integer representation, can’t be greater than $2^{8 \cdot 78}$ .

At this point, I reformatted the data as a CSV file and loaded it into Mathematica to do the hard work of actually solving the system for me: