# Aero CTF 2021 Writeup

This time I am playing alone for @blackb6a and had all the crypto challenges solved (and nothing else). I found the crypto challenges in many of the CTFs this year are worth-trying, and these are no exceptions. I ended up at the 9th place. By the way, @SuperGuesser is the first to solve for *all* of the crypto challenges. Can we nerf @RBTree_ and @rkm0959?

Additionally, *phoenix* had seven solves and while *horcrux* and *boggart* had two. I think they deserved more solves. You can read a better writeup by the *super guessers* on rkm0959's blog.

## horcrux⌗

### Challenge Summary⌗

Imagine that you are a dark wizard (as dark as Voldemort). And you want to reach immortality.

What could be your plan?

Author: keltecc (Discord)

We are given `horcrux.py`

and `output.txt`

. Suppose that there is a 3000-bit prime $p$ and three points on the elliptic curve $\mathcal{C}$ over $\text{GF}(p)$, namely, $G, P=(x_P, y_P)$ and $Q=(x_Q, y_Q)$. Let's denote $\tilde{P}=(\tilde{x}_P, \tilde{y}_P)$ and $\tilde{Q}=(\tilde{x}_Q, \tilde{y}_Q)$ and the errors $0 \leq \varepsilon_i < 2^{32}$ for $i = 1, 2, 3, 4$ by

\[\varepsilon_1 = \tilde{x}_P\oplus x_P, \varepsilon_2 = \tilde{y}_P\oplus y_P, \varepsilon_3 = \tilde{x}_Q\oplus x_Q, \varepsilon_4 = \tilde{y}_Q\oplus y_Q.\]

In the challenge, we are given the prime $p, G, \tilde{P}$ and $\tilde{Q}$. The objective is to find $\varepsilon_i$'s which are used as a key to encrypt the flag.

In short, we are given three points on an elliptic curve $\mathcal{C}$. However there are *small* errors on two of them, making them not lying on the curve. The objective is to fix the errors for these points.

### Solution⌗

#### Part I: Working on the math part⌗

**Note.**The operations are done over $\text{GF}(p)$. I won’t mention mod

*p*for simplicity.

My approach is *really* tedious. Suppose that $\mathcal{C}: y^2 = x^3 + ax + b$. Then by definition,

\[ \begin{cases}\begin{aligned} {y_G}^2 = {x_G}^3 + a{x_G} + b \\ {y_P}^2 = {x_P}^3 + a{x_P} + b \\ {y_Q}^2 = {x_Q}^3 + a{x_Q} + b \\ \end{aligned}\end{cases}. \]

To begin, let's define $e_1 = x_P - \tilde{x}_P$, $e_2 = y_P - \tilde{y}_P$, $e_3 = x_Q - \tilde{x}_Q$ and $e_4 = y_Q - \tilde{y}_Q$.

**Why using $e_i$'s but not $\varepsilon_i$'s those we defined?**We would not use $\varepsilon_i$'s since they involve

*xor*operations. We don’t know how to do it on elliptic curves.

We can first eliminate $a$ and $b$ by combining the three equations like below. You can refer to my writeup for nookcrypt in UIUCTF for more details.

\[(y_G^2 - y_P^2 - x_G^3 + x_P^3)(x_G - x_Q) = (y_G^2 - y_Q^2 - x_G^3 + x_Q^3)(x_G - x_P).\]

Furthermore, we can substitute the $e_i$'s:

\[\begin{aligned} & \left[y_G^2 - (\tilde{y}_P + e_2)^2 - x_G^3 + (\tilde{x}_P + e_1)^3\right]\left[x_G - (\tilde{x}_Q + e_3)\right] \\ & = \left[y_G^2 - (\tilde{y}_P + e_4)^2 - x_G^3 + (\tilde{x}_Q + e_3)^3\right]\left[x_G - (\tilde{x}_P + e_1)\right]. \end{aligned}\]

**What was my motivation?**I tried to minimize the

*entropy*by eliminating the 3000-bit unknowns, i.e., $a, b, x_P, y_P, x_Q$ and $y_Q$. I am either removing them by combining equations, or reducing the entropy by replacing them with smaller ones.

#### Part II: Retrieving $e_i$'s via LLL⌗

I have to stress again that my approach is pretty tedious. What I did is to expand everything. The *unknowns* are marked in yellow. Also, the overbraces and the underbraces are their entropies.

\[\begin{aligned} & [(y_G^2 - {\tilde{y}_P}^2 - x_G^3 + {\tilde{x}_P}^3) - \overbrace{2{\tilde{y}_P}\htmlStyle{color: yellow;}{e_2}}^{\text{32b}} - \overbrace{\htmlStyle{color: yellow;}{e_2}^2}^{\text{64b}} + \overbrace{3{\tilde{x}_P}^2\htmlStyle{color: yellow;}{e_1}}^{\text{32b}} + \overbrace{3{\tilde{x}_P}\htmlStyle{color: yellow;}{e_1}^2}^{\text{64b}} + \overbrace{\htmlStyle{color: yellow;}{e_1}^3}^{\text{96b}}][(x_G - \tilde{x}_Q) - \overbrace{\htmlStyle{color: yellow;}{e_3}}^{\text{32b}}] \\ & = [(y_G^2 - {\tilde{y}_Q}^2 - x_G^3 + {\tilde{x}_Q}^3) - \underbrace{2{\tilde{y}_Q}\htmlStyle{color: yellow;}{e_4}}_{\text{32b}} - \underbrace{\htmlStyle{color: yellow;}{e_4}^2}_{\text{64b}} + \underbrace{3{\tilde{x}_Q}^2\htmlStyle{color: yellow;}{e_3}}_{\text{32b}} + \underbrace{3{\tilde{x}_Q}\htmlStyle{color: yellow;}{e_3}^2}_{\text{64b}} + \underbrace{\htmlStyle{color: yellow;}{e_3}^3}_{\text{96b}}][(x_G - \tilde{x}_P) - \underbrace{\htmlStyle{color: yellow;}{e_1}}_{\text{32b}}]. \end{aligned}\]

Well, I am not done. Please bear with me. There are 12 terms on the both sides if they are expanded while grouped by $e_i$'s. The number of bits of entropy on one side is $(0 + 32 + 64 + 32 + 64 + 96) + (32 + 64 + 96 + 64 + 96 + 128) = 768$. Since the total entropy is $768 \times 2 = 1536 < 3000$ bits, we can recover the whole thing with LLL.

We can construct a $25\times 25$ matrix. This is how I do it in Sagemath.

```
multiplier = [2^128]
multiplier += [2^128, 2^96, 2^64, 2^96, 2^64, 2^32]
multiplier += [2^96, 2^64, 2^32, 2^64, 2^32, 2^0]
multiplier += [2^128, 2^96, 2^64, 2^96, 2^64, 2^32]
multiplier += [2^96, 2^64, 2^32, 2^64, 2^32, 2^0]
T = diagonal_matrix(multiplier)
A = Matrix(25)
A[ 0, 0] = ((Gy^2 - aPy^2) - (Gx^3 - aPx^3)) * (Gx - aQx)
A[ 1, 0] = ((Gy^2 - aPy^2) - (Gx^3 - aPx^3))
A[ 2, 0] = -2 * aPy * (Gx - aQx)
A[ 3, 0] = -2 * aPy
A[ 4, 0] = (Gx - aQx)
A[ 5, 0] = 1
A[ 6, 0] = 3 * aPx^2 * (Gx - aQx)
A[ 7, 0] = 3 * aPx^2
A[ 8, 0] = -3 * aPx * (Gx - aQx)
A[ 9, 0] = -3 * aPx
A[10, 0] = (Gx - aQx)
A[11, 0] = 1
A[12, 0] = -((Gy^2 - aQy^2) - (Gx^3 - aQx^3)) * (Gx - aPx)
A[13, 0] = -((Gy^2 - aQy^2) - (Gx^3 - aQx^3))
A[14, 0] = 2 * aQy * (Gx - aPx)
A[15, 0] = 2 * aQy
A[16, 0] = -(Gx - aPx)
A[17, 0] = -1
A[18, 0] = -3 * aQx^2 * (Gx - aPx)
A[19, 0] = -3 * aQx^2
A[20, 0] = 3 * aQx * (Gx - aPx)
A[21, 0] = 3 * aQx
A[22, 0] = -(Gx - aPx)
A[23, 0] = -1
for i in range(24):
A[i, i+1] = 1
A[24, 0] = p
A = A * T
B = A.LLL()
B = B / T
for row in B:
if row[0] != 0: continue
if row[1] > 0: row = -row
if row[1] != -1: continue
dPx = row[14] # e1
dPy = row[3] # e2
dQx = row[2] # e3
dQy = row[15] # e4
print('dP =', (dPx, dPy))
print('dQ =', (dQx, dQy))
# dP = (1155305281, 62177711)
# dQ = (1076744709, 30259545)
print()
```

However, I have the parity messed up. Trying $(e_1, e_2, e_3, e_4)$, $(e_1, e_2, e_3, -e_4)$, ... and compute for the respective $a$ and $b$, we have a correct value for $e_i$'s:

\[(e_1, e_2, e_3, e_4) = (1155305281, -62177711, 1076744709, -30259545).\]

After all, we can derive $\varepsilon_i$'s

\[(\varepsilon_1, \varepsilon_2, \varepsilon_3, \varepsilon_4) = (3168768961, 2085996465, 3254637063, 36849519)\]

and thus have the key to decrypt the flag:

`Aero{"Voldemort," said Riddle softly, "is my past, present, and future, Harry Potter...."}`

### Addendum⌗

@keltecc (the challenge author) and @hellman1908 had a similar approach as above. Meanwhile they need not to expand the polynomial by themselves.

*keltecc*wrote a function to handles the monomials. Link here.*hellman*used resultants to deal with it. From his write-up, the size of unknown is 1408 bits. Since I have not group the terms, the unknown size is larger (1536 bits). Link here.

Thanks to *vishiswoz* who pointed out that the mistakes that I made when defining the *multipliers*. Since the amount of unknown bits are small (1536 bits) relatively to the size of the known bits (3000 bits), they did not affect the results. This is the patched lattice (with parity fixed, too):

```
multiplier = [2^128]
multiplier += [2^128, 2^96, 2^96, 2^64, 2^64, 2^32]
multiplier += [2^96, 2^64, 2^32, 2^64, 2^32, 2^0]
multiplier += [2^128, 2^96, 2^96, 2^64, 2^64, 2^32]
multiplier += [2^96, 2^64, 2^32, 2^64, 2^32, 2^0]
T = diagonal_matrix(multiplier)
A = Matrix(25)
A[ 0, 0] = ((Gy^2 - aPy^2) - (Gx^3 - aPx^3)) * (Gx - aQx)
A[ 1, 0] = -((Gy^2 - aPy^2) - (Gx^3 - aPx^3))
A[ 2, 0] = -2 * aPy * (Gx - aQx)
A[ 3, 0] = 2 * aPy
A[ 4, 0] = -(Gx - aQx)
A[ 5, 0] = 1
A[ 6, 0] = 3 * aPx^2 * (Gx - aQx)
A[ 7, 0] = -3 * aPx^2
A[ 8, 0] = 3 * aPx * (Gx - aQx)
A[ 9, 0] = -3 * aPx
A[10, 0] = (Gx - aQx)
A[11, 0] = -1
A[12, 0] = -((Gy^2 - aQy^2) - (Gx^3 - aQx^3)) * (Gx - aPx)
A[13, 0] = ((Gy^2 - aQy^2) - (Gx^3 - aQx^3))
A[14, 0] = 2 * aQy * (Gx - aPx)
A[15, 0] = -2 * aQy
A[16, 0] = (Gx - aPx)
A[17, 0] = -1
A[18, 0] = -3 * aQx^2 * (Gx - aPx)
A[19, 0] = 3 * aQx^2
A[20, 0] = -3 * aQx * (Gx - aPx)
A[21, 0] = 3 * aQx
A[22, 0] = -(Gx - aPx)
A[23, 0] = 1
for i in range(24):
A[i, i+1] = 1
A[24, 0] = p
A = A * T
B = A.LLL()
B = B / T
for row in B:
if row[0] != 0: continue
if row[1] < 0: row = -row
if row[1] != 1: continue
dPx = row[14] # e1
dPy = row[3] # e2
dQx = row[2] # e3
dQy = row[15] # e4
print('dP =', (dPx, dPy))
print('dQ =', (dQx, dQy))
# dP = (1155305281, -62177711)
# dQ = (1076744709, -30259545)
print()
```

## phoenix⌗

### Challenge Summary⌗

If you want to become a member of the Order of the Phoenix, you need to:

- be able to perfectly control the magic wand
- be able to crack the following cipher
...but maybe some of this is not needed

Author: keltecc (Discord)

**Note:**This time, we are working on $\text{GF}(2^{256})$. $+$ is equivalent to XOR now.

We are given two polynomials over $A(x)$ and $B(x)$ over $\text{GF}(2^{256})$ with the polynomial $x^{256} + x^{10} + x^5 + x^2 + 1$. A key $\kappa(x)$ is also generated while kept secret. Suppose that we want to encrypt a message $(m_1, m_2, ..., m_l) \in \mathbb{Z}_2^l$. To encrypt the $i$^{th} bit, we

- compute $R_i(x)$ given by

\[R_i(x) := [A(x)]^k \kappa(x) + B(x) = r_{i0} + r_{i1}x + r_{i2}x^2 + ... + r_{i,255}x^{255},\]

- then, compute the $i$
^{th}bit of ciphertext, $c_i$, by

\[c_i := m_i + (r_{i0} + r_{i2} + r_{i4} + r_{i6} + r_{i8}) + r_{i1} r_{i3} r_{i5} r_{i7} r_{i9}.\]

The objective is to find the key $\kappa(x)$, given a ciphertext $(c_1, c_2, ..., c_{1024})$ and knowing that $m_1 = m_2 = ... = m_{768} = 0$.

### Solution⌗

$m_1 = m_2 = ... = m_{768} = 0$ is pretty suspicious. We know that for $i = 1, 2, ..., 768$,

\[c_i = r_{i0} + r_{i2} + r_{i4} + r_{i6} + r_{i8} + r_{i1} r_{i3} r_{i5} r_{i7} r_{i9}.\]

Since the probability for $r_{i1} r_{i3} r_{i5} r_{i7} r_{i9} = 1$ is only 1/32, we can approximate $c_i$ with

\[\tilde{c_i} = r_{i0} + r_{i2} + r_{i4} + r_{i6} + r_{i8}.\]

It is expected that $c_i = \tilde{c_i}$ for most of the cases. If we can express $R_i(x)$ in terms of $\kappa(x) := k_0 + k_1 x + ... + k_{255}x^{255}$, we have a set of simultaneous linear equations in terms of $k_i$'s, while around 24 of the equations are incorrect. Since there are 256 unknowns (i.e., $k_0, k_1, ..., k_{255}$), I am picking 256 equations from $c_i = \tilde{c_i}$ and hoped all of them are correct. The chances are not that low - it is $\left(\frac{31}{32}\right)^{256} \approx 0.000295$, which is around one in 3400. We can identify the correct solution by checking the number of equations with $c_i = \tilde{c_i}$. If it is correct, then there will be around 744 $i$'s satisfying the condition. Otherwise, there are only about 512. Eventually I have the flag:

`Aero{n1c3_ISD_4tt4ck_g00d_j0b!!}`

## boggart⌗

### Challenge Summary⌗

Welcome to another Defence Against the Dark Arts lesson.

Today I will show you a new powerful charm — Riddikulus. Enjoy!

`nc 151.236.114.211 17101`

Author: keltecc (Discord)

There is a netcat service available in this challenge. We can get four numbers each time we connect: a modulus $n$, a mask $\sigma$, and a pair of ciphertexts $c_1$ and $c_2$. $c_1$ is encrypted by the known message `the boy who lived`

, while $c_2$ is the encrypted flag. The modulus is a product of two primes $p$ and $q$. This time $p := \text{NextPrime}(\sigma\ |\ \Delta p)$ and $q := \text{NextPrime}(\sigma\ |\ \Delta q)$.

However, it performs 16 rounds of encryption algorithm $\mathcal{E}$. $\mathcal{E}$ looks man-made, which is a combination of *RSA* and *Lucas sequence*. Let's annotate the attachment `boggart.py`

a bit.

```
class Wardrobe:
@staticmethod
def create_boggarts(fear, danger):
# Return an array of public exponents
while danger > 0:
fear = next_prime(fear)
if getrandbits(1):
yield fear
danger -= 1
class Wizard:
def __init__(self, magic, year, experience):
self.magic = magic # self.magic = n, the public modulus
self.knowledge = year - 1 # self.knowledge = 2
self.experience = experience # self.experience = message
def cast_riddikulus(self, boggart):
# Encrypt the message, m, with the public exponent.
knowledge, experience = self.knowledge, self.experience
while boggart > 1:
knowledge, experience = experience, (experience * self.experience - knowledge) % self.magic
boggart -= 1
self.experience = experience
def main():
# ...omitted
harry_potter = Wizard(magic, year, bytes_to_long(b'the boy who lived'))
you = Wizard(magic, year, bytes_to_long(flag))
# Perform 16 rounds of encryption
for boggart in Wardrobe.create_boggarts(boggart_fear, boggart_danger):
harry_potter.cast_riddikulus(boggart)
you.cast_riddikulus(boggart)
# ...omitted
```

### Solution⌗

#### Part I: Factoring $n$ with $\sigma$⌗

I don't have any directions to begin with. Let's try to factorize $n$ first. Since there is a netcat service this time, we can be more picky on the numbers. For instance, we can find $\sigma$ such that their set bits are evenly spaced. Also, we can assume that the set bits for $\sigma$ are also set for $p$ and $q$ (except the least 20 bits). Denote $S = (s_1, s_2, ..., s_k)$ with $s_1 < s_2 < ... < s_k$ are the set bits of $\sigma$, i.e., we have $\sigma = 2^{s_1} + 2^{s_2} + ... + 2^{s_k}$. Let's look at the algorithm I could think of.

**[Initialize]** Let's pick the smallest $j$ such that $s_j \geq 20$. Initialize the set $F_j$ by

\[F_j := \left\{(p, q) \in \mathbb{Z}^2\ |\ pq \equiv n\ (\text{mod}\ 2^{s_j}) \right\}\]

What is this $F$? Ideally, I would like to maintain a set $F$ such that every $(p, q) \in F$ satisfies $pq \equiv 1\ (\text{mod}\ 2^s)$ (for a given $s$), while $p$ and $q$ having the set bits $\sigma$ had.

**Why $s_j \geq 20$?**The set bits for $\sigma$ may not be set in $\text{NextPrime}(\sigma\ | \Delta p)$ because of carrying. In this case, I assumed that the carrying did not go too far.

**[Update]** We can define $F_i$ for $i = j+1, j+2, ..., k$ with the below algorithm.

- Initialize $F_i = \phi$, the empty set.
- For each $(p_1, q_1) \in \mathbb{Z}^2$:
- Exhaust $0 \leq u, v \le 2^{s_i}$ with $2^{s_{i-1}+1}\ |\ u$ and $2^{s_{i-1}+1}\ |\ v$.
- Write $p_2 = p_1 + u + 2^{s_i}$ and $q_2 = q_1 + v + 2^{s_i}$ (Note: they have the $s_i$
^{th}bit set). - If $n \equiv p_2q_2\ (\text{mod}\ 2^{s_i})$, then update $F_i \leftarrow F_i \cup {(p_2, q_2)}$.

**[Finalize]** For each $(p_1, q_1)$ in $F_k$,

- Exhaust $0 \leq u, v < 2^{512}$ with $2^{s_k+1}\ |\ u$ and $2^{s_k+1}\ |\ v$.
- Write $p_2 = p_1 + u + 2^{s_k}$ and $q_2 = q_1 + v + 2^{s_k}$.
- If $n = p_2q_2$, then $p_2$ and $q_2$ are the prime factors for $n$.

If you are interested, just have a look at the gist on factoring $n$. Below is the $n$ I retrieved and the corresponding $p$ and $q$. There is a paper^{1} (and its corresponding slides^{2}) more tricks to factor $n$ given partial information.

```
n = 40740327153595270257184780086389953086261120133330698714430641164791044793765728073225136444807495004396268705143115221155717342774153766221474052678956440685995627998728286518422095251317829948639280532042852083900018149268443333895256994879066082385467247811575697036554762935124165948190148187259065768291
p = 6599104293714145478554177176803578568990396482282918390864510364381920295952993884789163942979610791954293100727323403846729255137773392428824686146334083
q = 6173614681677589793159076464182384333359578951775387735487730852029780858970587865352547693301144847551051384110518957280217521699817523617984210590793377
```

**An afterthought.**My algorithm is pretty slow, and it could be sped up by computing $q_2$ from $p_2$ (instead of iterating them) on

*update*and

*finalize*. The complexity for each set update would be $\mathcal{O}(2^{s_{i+1} - s_i})$ instead of $\mathcal{O}(4^{s_{i+1} - s_i})$.

#### Part II: Identifying the cryptosystem and solving for the flag⌗

Although I have $n$ factorized, I don't even how it helps. Maybe we shall investigate how $\mathcal{E}$ works. Let's look at the `Wizard`

class, where `cast_riddikulus`

is essentially the encryption function:

```
class Wizard:
def __init__(self, magic, year, experience):
self.magic = magic # self.magic = n, the public modulus
self.knowledge = year - 1 # self.knowledge = 2
self.experience = experience # self.experience = message
def cast_riddikulus(self, boggart):
# Encrypt the message, m, with the public exponent.
knowledge, experience = self.knowledge, self.experience
while boggart > 1:
knowledge, experience = experience, (experience * self.experience - knowledge) % self.magic
boggart -= 1
self.experience = experience
```

It can be expressed in a formula. Suppose that we have the message $m$, with the public key $(n, e)$. The ciphertext $c$ is computed as

\[ \begin{bmatrix}? \\ c\end{bmatrix} \equiv \begin{bmatrix}0 & 1 \\ -1 & m\end{bmatrix}^{e-1}\begin{bmatrix}2 \\ m\end{bmatrix}\ (\text{mod}\ n). \]

It looked weird to me, since I did not expect that $m$ is also included in the transition matrix. However, learning from so much CTFs in the history, I think this cryptosystem is not designed solely for this CTF. I searched with the keywords *RSA*, *Lucas sequence* and *cryptosystem*, and found a paper on LUC cryptosystem^{3}. To decrypt a message, we need to derive the private key from the ciphertext $c$ and the factorization of $n$. Now what we have done on the first part is useful. Since the public exponents are generated by the `Wardrobe`

, let's look at how it works.

```
class Wardrobe:
@staticmethod
def create_boggarts(fear, danger): # fear = 31337 and danger = 16
# Return an array of public exponents
while danger > 0:
fear = next_prime(fear)
if getrandbits(1):
yield fear
danger -= 1
```

In short, 16 public exponents $e_1, e_2, ..., e_{16}$ such that $e_1 < e_2 < ... < e_{16}$ are generated. It is computed as a subsequence of the prime sequence $(31357, 31379, 31387, 31391, ...)$.

Since we are given a message-ciphertext pair $(m_1, c_1)$, I used a *meet-in-the-middle* approach to find the $e_i$'s. Since each round of the encryption is independent, I can encrypt $m_1$ with $e_1, e_2, ..., e_{10}$ for middletexts. On the other hand, I will decrypt $c_1$ with the private exponents derived from $e_{16}, e_{15}, ..., e_{11}$ for middletexts, too. If they are equal, then $(e_1, e_2, ..., e_{16})$ is the chain of public exponents I want. To speed up, I am working under modulo $p$ instead of modulo $n$. Not only the modulus is smaller, the private exponents are also smaller.

**Why 10+6 but not 8+8 for MITM?**The decryption is considerably slower (owing to large $d$'s) and I think we should be encrypting more.

After I have complete writing the program, I went to bed. The flag is sitting nicely when I am awake. Nice!

`Aero{Do_you_know_Peter_Pettigrew?}`