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⌗

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

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}\]

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)

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.

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

1. Initialize $F_i = \phi$, the empty set.
2. 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$,

1. Exhaust $0 \leq u, v < 2^{512}$ with $2^{s_k+1}\ |\ u$ and $2^{s_k+1}\ |\ v$.
2. Write $p_2 = p_1 + u + 2^{s_k}$ and $q_2 = q_1 + v + 2^{s_k}$.
3. 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¹ (and its corresponding slides²) more tricks to factor $n$ given partial information.

n = 40740327153595270257184780086389953086261120133330698714430641164791044793765728073225136444807495004396268705143115221155717342774153766221474052678956440685995627998728286518422095251317829948639280532042852083900018149268443333895256994879066082385467247811575697036554762935124165948190148187259065768291
p = 6599104293714145478554177176803578568990396482282918390864510364381920295952993884789163942979610791954293100727323403846729255137773392428824686146334083
q = 6173614681677589793159076464182384333359578951775387735487730852029780858970587865352547693301144847551051384110518957280217521699817523617984210590793377

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

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?}