rkm0959

I participated in AeroCTF as a member of Super Guesser. We reached 1st place :)

We were able to grab first bloods on all three cryptography challenges.

Phoenix was solved by rbtree, and I solved horcrux and boggart.

Phoenix

Solution (due to rbtree)

Let's look at the encryption scheme. 

We have a key $k \in GF(2^{256})$ and known parameters $a, b \in GF(2^{256})$.

To encrypt a plaintext $m$, it is first converted to binary then padded at the front with zeros to have length 1024. 

Then, we take the first 10 bits of the polynomial representation of $a^i k +b$ for each $i$, and calculate $$xbit_i = \sum \text{(even index bits)}$$ $$ybit_i = \prod \text{(odd index bits)}$$ where calculations are done in $GF(2)$. 

Finally, we encrypt our text with a stream cipher, i.e. XOR our plaintext with $\{xbit_i \oplus ybit_i\}_{i \ge 1}$. 

We now make some observations.

• It's very likely that $ybit_i$ is $0$, since it is a product of 5 bits. Heuristically, it has a $31/32$ chance of being $0$. 
• The message bit length is guaranteed to be less than 256. This means the length of the padding is at least 768.
• If we write each 256 coefficients of $k$ as variables, then $xbit_i$ can be written as a linear combination of them (and $0, 1$)

Now we have our solution idea.

• If we assume that $ybit_i = 0$ and know the ptxt/ctxt bits, we can recover $xbit_i$. This gives us a linear equation over our 256 variables.
• Of course, we know 768 bits of the plaintext and all of the ciphertext, so we can do this for 768 different values of $i$.
• We take 256 equations out of those 768 and hope that the system of equations have a unique solution.
• If there is a unique solution, we can recover the key and perform the decryption process to get a candidate for our flag.
• If our recovered flag has "Aero{" in it, we can finish the challenge. If not, we try another set of 256 equations.

We need to have $ybit = 0$ for all 256 bits/equations we selected. This has a probability of $$(31/32)^{256} \approx 0.0003$$ of succeeding, and we also need our system to be uniquely solvable. Thankfully, our algorithm terminates in about 2000 trials, and each trial doesn't take too long. It seems like SageMath is very efficient when it comes to matrices over $GF(2)$ :) 

Here's the solution script, by rbtree. It runs in a few minutes.

Horcrux

Solution

We first take a look at what's going on.

• We have a 3000 bit prime $p$, which we know.
• We have a point $G$ on some elliptic curve $ y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ - we know $G$ but we don't know $a, b$.
• We have a 128 bit AES key we have to recover : this is split into two "horcruxes" of 64 bits.
• Each horcrux is split into two parts of 32 bits - they are XOR'ed to the coordinates of some point on the curve then given.

Writing this in mathematical equations, we have

• We are given a 3000 bit prime $p$ and three coordinates $(x_0, y_0), (x_1, y_1), (x_2, y_2)$
• 128 bit AES key is equal to $\alpha_1 || \beta_1 || \alpha_2 || \beta_2$ with each part being 32 bits, i.e. less than $2^{32}$.
• $(x_0, y_0)$ lies on a elliptic curve $y^2 = x^3 + ax + b$ over $\mathbb{F}_p$, so $y_0^2 = x_0^3 + ax_0 + b$ in $\mathbb{F}_p$.
• $(x_1 \oplus \alpha_1, y_1 \oplus \beta_1)$ lies on the curve, so $(y_1 \oplus \beta_1)^2 = (x_1 \oplus \alpha_1)^3 + a(x_1 \oplus \alpha_1) + b$
• $(x_2 \oplus \alpha_2, y_1 \oplus \beta_2)$ lies on the curve, so $(y_2 \oplus \beta_2)^2 = (x_2 \oplus \alpha_2)^3 + a(x_2 \oplus \alpha_2) + b$

Since XOR is hard to deal with, we change it to normal addition - of course, it's clear that

• $U, V \ge 0$, $V < 2^b$ implies $|(U \oplus V) - U| < 2^b$. 

Therefore, we can change each XOR to addition, by changing our constraints from $0 \le \alpha_i, \beta_i < 2^{32}$ to $|\alpha_i|, |\beta_i| < 2^{32}$.

Now we have to solve, given $p, x_0, y_0, x_1, y_1, x_2, y_2$, the system of equations $$\begin{equation*} \begin{aligned}  y_0^2 &= x_0^3 + ax_0 + b \\ (y_1 + \beta_1)^2 &= (x_1 + \alpha_1)^3 + a(x_1 + \alpha_1) + b \\ (y_2 + \beta_2)^2 &= (x_2 + \alpha_2)^3 + a(x_2 + \alpha_2) + b \end{aligned} \end{equation*}$$ over $\mathbb{F}_p$ and $|\alpha_i|, |\beta_i| < 2^{32}$. Now what do we do? There were a few ideas at this point...

Idea 1 : Lattices

Of course, "small solutions" imply that we have to use lattices. Maybe we can directly use them here?

For example, using github.com/rkm0959/Inequality_Solving_with_CVP we can solve a system of linear inequalities.

Turns out, it's quite difficult to do so, since our system has terms like $a \alpha_1$ and $a \alpha_2$. 

Because we don't know the value of $a$ and its size can be large, we can't deal with this term using this method.

To use the tool in the link, we need all terms of our equations to be either

• linear in terms of our variables (i.e. variable multiplied by a known constant)
• small (so that we can move this to the lower bound / upper bound vector for the CVP)

In this case, $a \alpha_1$ and $a \alpha_2$ term does not satisfy this requirement.

Idea 2 : Determinant

The failure of our Idea 1 leads to the key idea : removing $a$ in our system completely.

This can be done by realizing that $[1, -a, -b]^{T}$ is in the kernel of the matrix $$ \left[ \begin{matrix} y_0^2 - x_0^3 & x_0 & 1 \\ (y_1 + \beta_1)^2 - (x_1 + \alpha_1)^3 & (x_1 + \alpha_1) & 1 \\ (y_2 + \beta_2)^2 - (x_2 + \alpha_2)^3 & (x_2 + \alpha_2) & 1 \end{matrix} \right]$$ which means its determinant must be $0$ in $\mathbb{F}_p$. This gives us a polynomial equation in $\alpha_1, \alpha_2, \beta_1, \beta_2$. Now what?

The first idea was multivariable coppersmith - I tried to use defund's implementation, but the matrix size got way too large.

The second idea is, of course, lattices from Idea 1. If we expand our determinant, we will get a equation of the form $$\sum \text{(constant coefficient)} \cdot \text{(some monomial)} = 0$$ we can simply bound each monomials with $|\alpha_i|, |\beta_i| < 2^{32}$, then solve using the CVP toolkit above.

To be more precise : our equation will be in a form of $$\sum_{i=1}^k c_i m_i \equiv -c_{k+1} \pmod{p}$$ where $c_i$ is a known constant and $m_i$ is some non-constant monomial over $\alpha_i$, $\beta_i$. (Consider $m_{k+1}$ as $1$)

We solve this system by utilizing the following inequalities and plugging them into the CVP toolkit : 

$$-2^{32 \cdot \deg(m_i)} < m_i < 2^{32 \cdot \deg(m_i)}$$ $$ \sum_{i=1}^k c_i m_i+ pX = -c_{k+1}$$ where $\deg(m_i)$ is the degree of the monomial. Note that abuse of notation was used - $m_i$ is used both as a monomial, and as the actual value of the monomial with the true values of $\alpha_i$, $\beta_i$ plugged in. For further details, please take a look in the github repo and the solution.

UPD : Mystiz gives a good insight on entropy to explain why this line of thinking works. Link is here.

This is a very useful way to think about whether or not the above CVP toolkit will work, when it comes to the uniqueness of the solution.

Boggart

Solution

There is a lot going on in this code, so let's take a look at it.

• We have random 512 bit integer $M_N, M_L, M_D$ corresponding to neutral/light/dark magic
• The value magic is created as $M = \text{next_prime}(M_N | M_L) \times \text{next_prime}(M_N | M_D)$.
• We are given the values of $M_N$ and $M$ - so the factorization of $M$ is unknown.

Now, the text "the boy who lived" and the flag goes through some encryption process, and we know their ciphertexts.

• The encryption process itself is quite random - it uses the cast_ridikkulus algorithm randomly.
• To be more precise, it starts the parameter "fear" at 31337, and increases it to the next prime each time.
• Then, with a 50% chance, the text gets encrypted with the said value of "fear" and the cast_ridikkulus algorithm.
• If we have used the cast_ridikkulus algorithm 16 times, the encryption process terminates.

cast_riddikulus algorithm

Naturally, we have to look at the cast_riddikulus algorithm and how to reverse/decrypt it.

We note that the value of self.knowledge is fixed at $2$ at all times. Denote the self.experience as $x$, and the boggart as $n$.

The algorithm calculates a linear recurrence - it starts with $a_0=2$, $a_1 = x$, and moves up by $$a_{i} = xa_{i-1} - a_{i-2}$$ Let's forget about the modulos and solve this recurrence. Using standard techniques, we get $$a_n = \left( \frac{x - \sqrt{x^2 - 4}}{2} \right)^n + \left( \frac{x + \sqrt{x^2- 4}}{2} \right)^n $$ This looks kinda scary, but then we can see that this is just $$x = t + t^{-1} \implies a_n = t^n + t^{-n}$$ Note that this implication holds even when we consider the fact that we are working modulo $M$.

This has a lot of meaning - for example, the encryption function is commutative in a sense that encrypting a text (experience) with (boggart) $m$ then $n$ is equivalent to encrypting with $n$ then $m$, which is equivalent to encryption once with $mn=nm$. 

It also implies that under some "mild" conditions, we can reverse the encryption function as follows - 

• Given $ctxt \equiv t^n +  t^{-n} \pmod{M}$, we solve for the value $t^n \pmod{M}$.
• We solve for $t \pmod{M}$ using the value of $t^n \pmod{M}$.
• We get our original value $ptxt = t + t^{-1} \pmod{M}$.

In the above algorithm, we needed

• Factorization of $M$, and we need $t$ to be coprime to $M$
• $t^n + t^{-n} \equiv ctxt \pmod{M}$ to be solvable, i.e. $ctxt^2 - 4$ being a quadratic residue
• $n$ being coprime to $\phi(M)$, for the discrete root to be easy to solve 
• (of course, we can use adlemann root extraction, but that's not very fast)

Let's review our requirements and how difficult they are

• Factorization of $M$ : this is hard but must be done - and this is probably why we are given $M_N$.
• $t$ being coprime to $M$ : this will probably hold even if we don't care about it
• $ctxt^2 - 4$ being a quadratic residue : if not, we can just get our random values of $M_N, M_L, M_D, M$ again.
• $n$ being coprime to $\phi(M)$ : in our context, we will use 16 primes larger than $30000$ as $n$, so it'll most likely be true.

Therefore, it's time to go back and try to factorize $M$ with our information of $M_N$.

factorization of $M$

The key idea is that the value of $M_N$ gives us known bits of each prime $p, q$ of $M$.

• $M_N|M_L$ and $M_N|M_D$ obviously has all bits that $M_N$ has. 
• Then, we apply the next_prime function. Due to the small prime gap, this is similar to adding a few thousand to each number.
• Therefore, some lower bits will definitely change, and even higher bits can change due to carry

Consider $M'_N = M_N - (M_N \pmod{2^{16}})$, i.e. $M_N$ but changed the $16$ LSB to 0.

• If no carry happens at the 16th bit, our primes will still have all the bits of $M'_N$.
• If a carry happens at the 16th bit, we hope our primes will still have all the bits of $M'_N + 2^{16}$.

Therefore, we write $M''_N = M'_N \& (M'_N + 2^{16})$ and claim that $p, q$ all have the bits of $M''_N$.

It is known that with around 57% of the bits of $p, q$ known, we can factorize $N$ using the following algorithm -

• At stage $k$, calculate all possible $(p \pmod{2^k}, q \pmod{2^k})$ such that $pq \equiv N \pmod{2^k}$.
• Of course, we must respect the known bits of $p, q$ while calculating this.
• We can change $p \pmod{2^k}$ to $p \pmod{2^{k+1}}$ or $p + 2^k \pmod{2^{k+1}}$ while moving to the next stage.
• If we find a set of $(p, q)$ such that $pq = N$, the algorithm terminates. 
• This can be written in a depth-first search style or a breadth-first search style. The latter works better on my machine.

We require that $M''_N$ has a lot of ones in its binary representation. We simply restart the connection until we get good parameters.

For the details of the factorization algorithm, please refer to the solution script below.

how did we encrypt this?

Now we know the factorization of $M$. We can now check if $ctxt^2 - 4$ is a quadratic residue modulo $M$.

We test this for the ciphertext of the "the boy who lived" and the ciphertext of the flag. If this check fails, we run our algorithm again with a new connection for a good set of parameters. We now assume $ctxt^2 - 4$ is a quadratic residue.

We reasonably guess that our encryption algorithm will have used 16 primes out of the 35 consecutive primes larger than 31337.

We also verify that $p-1$ and $q-1$ are all coprime to these 35 candidate primes. If not, we look for a good set of parameters.

Now we can encrypt and decrypt as we like. Let's find out which 16 primes were used for encryption.

To do this, we use meet-in-the-middle algorithm. Basically what we do is

• Split the set of 35 primes into two pieces, and assume that 8 primes were used in each piece
• Calculate the encryption of "the boy who lived" with each combination of 8 primes of the first piece
• Calculate the decryption of the ciphertext with each combination of 8 primes of the second piece
• Find a match, and if there is one, we have found our set of 16 primes.
• If not, we can try a new split of the primes and continue on.

Now we know which primes were used for encryption. All we need to do is decrypt the ciphertext of the flag.

additional notes

Note 1 : speeding up cast_riddikulus algorithm

• This is a linear recurrence, so we can speedup using matrix multiplication
• However, this is also a Lucas sequence used in Williams's $p+1$ algorithm
• Therefore, we can just copy the implementation from Wikipedia to achieve a speedup.

Note 2 : requirements relaxation

• If we assume that the flag is small, we only need to work with mod $p$ or mod $q$, instead of mod $M$.
• Therefore, we can relax our quadratic residue conditions to "QR modulo at least one of the primes"
• Thankfully, I was very lucky with the parameters and got QR modulo $M$.

Note 3 : meet-in-the-middle, but not quite middle

• If we try to run the code, we can see that encryption is faster than decryption.
• Therefore, it's reasonable to give the encryption part more work than just "half" of the bunch.

The solution code is displayed in parts for reader's understanding. Feel free to comment and ask questions...

reading parameters

factorization of $M$

encryption and decryption

meet-in-the-middle

the finish, and the parameters I got

I participated in UnionCTF as a member of Super Guesser. We reached 1st place :)

Mordell Primes

Solution

The main intuition is that the numerator of $kP$ will grow very fast as $k$ increases. This can be verified by simply checking for small $k$.

Therefore, we can try to simply brute force the value of $k$ and see if the numerators multiply to $N$.

Human Server

Solution

We have to do a MITM attack, but there are some twists - Alice and Bob do a check later to see if they have the same shared secret.

Suppose Alice's secret key, public key is $d_1$, $d_1G$ and Bob's secret key, public key is $d_2$, $d_2G$.

Now let's forward Alice's key as $e_1G$ and give the nonce $r_1$ to Bob, where we know the value $e_1$.

This will make Bob's shared secret equal to $(e_1d_2G).x \oplus r_1$. Since $d_2G$ is a known value and $e_1, r_1$ are known, we can calculate this.

Similarly, let's forward Bob's key as $e_2G$ and give the nonce $r_2$ to Alice, where we know the value $e_2$.

This will make Alice's shared secret equal to $(e_2d_1G).x \oplus r_2$. We have to make this equal to Bob's shared secret. 

This can be done by selecting $r_2$ as $$r_2 = (e_1d_2G).x \oplus (e_2d_1G).x \oplus r_1$$ and we can pass the check between Alice and Bob. We now know the shared secret, so the challenge is solved.

Of course, we can just choose $e_1 = e_2 = 1$ and some random value for $r_1$.

Cr0wn St3rling

Solution

We start by making some quick observations -

• The length of key_indexes must be 8 due to the check is_valid_number.
• There are only $7^8$ keys since there are 7 possible choices for each entry of the musical key.
• Actually, the first entry of key_indexes is guaranteed to be 1. Make that $7^7$ valid key_indexes.
• Fibonacci function is implemented pretty badly, and we can change that to simple dynamic programming
• There's nothing we need to do about the $\pi$ function
• The q_grid function is suboptimal, but it runs in decent time so no need to worry about that.

We will now decrease the number of key_index candidates by using the known plaintext "union".

• Each entry of key_indexes works in a separable way, so we can work with each entry separately
• There are 7 possible choices for a specific key_indexes entry
• The problem is we do not know the length of q_grid (we do not know the variable $size$ in advance)
• For $i < 5$, the maximum value of the index is $7^4 \cdot 3$, which is small compared to the length of the q_grid for $size = 75000$.
• Therefore, we can reasonably assume that the length of q_grid is larger than the index.
• Now we can try out each candidate for a specific key_indexes entry - this is sufficient to get the first 5 entries of key_indexes.

We now have only $7^3$ candidates to work with. We can try every single one of them.

• The only slow part of the brute force is generating the q_grid and calculating its length.
• This can be done very fast by calculating q_grid for $size = 75000$ and using binary search to calculate the "actual length of the q_grid" (i.e. number of entries that are less than the actual "size" variable)
• However, since we have a lot of time, we can just calculate q_grid for $size = 75000$ then simply calculate the actual length of the q_grid with brute force. It doesn't take too long for us to get the flag anyway..

Neo-Classical Key Exchange

Solution

The first thing we notice is that list_valid checks if the length of the list is a square, and list_iter simply returns the square root.

Now we look at the main function, the list multiplication. If we stare at it for a while (and notice the "length is a square" stuff) we can find out that this list multiplication is just a matrix multiplication, where the list is the matrix entries in order.

Now we have to solve a Diffie-Hellman problem with matrices over $\mathbb{F}_p$. We will do it by solving discrete logarithm problem.

• Idea 1 : The range of the secret keys
• The range of the secret keys are from $2$ to $p$ - this implies that we do not need the entire discrete logarithm, just some part of it.
• Idea 2 : The determinant
• This idea can give us the required information of the (matrix) discrete logarithm if we calculate the respective discrete logarithm (over finite field $\mathbb{F}_p$) on the determinants. However, the primes used here are quite large, which makes this approach infeasible.

Instead of $5 \times 5$ matrices that we actually have to deal with, we first look at $2 \times 2$ matrices over the reals.

The idea is that we want to look at how matrix powers behave in a more relaxed setting, and find some properties we can use in $\mathbb{F}_p$.

We try to solve $A^k = B$. Take the Jordan Canonical Form $J$ with $A = PJP^{-1}$. Then we want to solve $$J^k = P^{-1}BP$$ so we may simply assume that $A$ is in a Jordan Canonical Form. If $A$ is in the form of $$A = \left[ \begin{matrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{matrix} \right]$$ then nothing special happens - we still need a logarithm to compute $k$, which is infeasible in $\mathbb{F}_p$. However, if $A$ is in the form of $$A = \left[ \begin{matrix} \lambda & 1 \\ 0 & \lambda \end{matrix} \right]$$ then we have some interesting phenomenon : $$A^k = \left[ \begin{matrix} \lambda^k & k \lambda^{k-1} \\ 0 & \lambda^k \end{matrix} \right]$$ and now we can get $k$ as $(k\lambda^{k-1} \times \lambda) / \lambda^k$, all of which we know and can be done in $\mathbb{F}_p$.

Let's come back to $\mathbb{F}_p$. If we want to use the Jordan Canoncial Form trick, we need our characteristic polynomial to completely split in $\mathbb{F}_p$, and we also need a block of size $2$. Our matrix satisfies all of these properties, so we can just use the exact same technique here as well.

Of course, we can see that we have calculated the discrete logarithm modulo $p$, not the full discrete logarithm.

However, because of Idea 1 (secret key range is small) this is enough to solve the problem. Here are some additional notes.

• The Jordan Canonical Form of our matrix $G$ has 4 blocks of size 1, 1, 1, 2. 
• This actually shows that the order of $G$ is $p(p-1)$ - this can be seen as the $p-1$ term dealing with the diagonal entries (Fermat's Theorem) and the $p$ term dealing with the off-diagonal term in our block of size 2. 
• If we want to solve for the discrete logarithm modulo $p-1$, we need discrete logarithm over $\mathbb{F}_p$ which we decided infeasible.
• I think there are some similarities with this challenge and TetCTF 2021 unevaluated.

Why is a raven

Solution

This is Supersingular Isogeny Diffie-Hellman protocol. Looking at the Wikipedia article and back, we see that we have extra information, $$\phi_A(P_A), \phi_A(Q_A)$$ Since $\phi_A$ has $S_A = P_A + k_AQ_A$ as it's kernel, we see that $$ \phi_A(P_A + k_AQ_A) = \phi_A(P_A) + k_A \phi_A(Q_A) = 0$$ Also, since the values here are in a subgroup of order $2^{216}$, we can calculate $k_A$ (i.e. discrete logarithm) efficiently with Pohlig-Hellman.

Now that we know $k_A$, one of the secret keys, we can just follow our algorithm to calculate the shared secret.

이번엔 2등으로 끝 ㅅㅅㅅㅅ

I participated in 0x41 CTF as a member of Super Guesser, and we reached 2nd place.

This is a very rushed writeup, hope to patch it up after I take a sleep...

Summary of the Challenge

Basically, we are given a 4-round SPN cipher, and we have to completely find the key.

To do this, we are given $2^{16}$ known plaintext/ciphertext pairs. We also know the sbox/pbox.

The Attack Idea, and the SBOX

Since this is a known plaintext/ciphertext attack, we can think about linear cryptanalysis.

To do that, we have to exploit the SBOX's linear properties. After some researching on past linear cryptanalysis challenges in CTFs, I ended up at this writeup of zer0SPN by NGG. I ran the first code block to find that the SBOX was horrible beyond belief. Denoting $\text{bit}(n, k)$ for $0 \le n < 2^8$ as the $k$th bit from the left when we write $n$ as a $8$-digit binary integer, we can see that $\text{bit}(n, k)$ and $\text{bit}(sbox[n], k)$ are heavily correlated. This is a very simple output compared to the zer0SPN challenge, where several bits come into play at once.

This is a very promising outcome, and shows we are in the right direction. I actually thought I was done at this point :P

Attack 1 : Recovering Linear Equations of the Key Bits

Now what we can do is view the SBOX as a simple XOR. 

Basically, with the above code, we can regard the SBOX as

• if $invert[i] = 0$, the SBOX does nothing to the $i$th bit
• if $invert[i]=1$, the SBOX flips the $i$th bit

If we use this idea, then literally everything we do is just permuting and XOR'ing each bit.

Of course, the SBOX is not "perfectly" an XOR, but it will be biased towards it due to the properties we found.

This gives us a method to find 64 linear equations of the key bits in $\mathbb{F}_2$. Here's how we do it.

Let's think about the very first (0th) bit of the plaintext. This bit will

• get XOR'ed by the first key bit of the first key
• SBOX'ed (which can be approximated by XOR'ing $invert[0]$)
• PBOX'ed (moved to a new position, where we know)
• and repeated like that for four times