Aug
11

## 1st Crypto CTF 2019 – Least Solved Challenges

Brief solution ideas to the least solved Crypto CTF challenges.

### Midnight Moon

We can see that the primes are generated as follows. Let $m$ be the right half of the flag (as an integer) and $l$ be its byte length. We repeat the transformation $m \mapsto ((m+1)\cdot l)\oplus l$ until $m$ is prime. This is the first prime $p$. Then we set $m = (2m+1)$ and repeat the first transformation until we get another prime. As a result, the second prime $q$ is approximately equal to $2 l^e p$, where $e$ is the number of iterations in the last process. We can guess $e$ and $l$ (note that $e$ is upper bounded by $log_l n$) and then apply the Fermat factorization method to the number $2 l^e n = 2 l^e p q$. It should work since $2 l^e p \approx q$. Since $e$ can vary a lot, we can only hope that the approximation is good enough. However, there is a little subtlety with the Fermat method. It works only if both close factors have the same parity, which is not the case: $2l^e p$ is even and $q$ is odd. This of course can be easily overcome by multiplying the number by $4$, which corresponds to multiplying both close factors by 2.

In the challenge the modulus can be factored with $l=27$ and $e=442$. The next step is to guess the number of applications of the transformation $m \mapsto ((m+1)\cdot l)\oplus l$ when going from initial $m$ to the first prime $p$. After trivial inversion of the transformation, we obtain the right half of the flag: “4D3_1n__m1dNi9hT_witH_L0v3!}”. We could study the encryption function to decrypt the first half, but we can already guess the whole flag: “CCTF{M4D3_1n__m1dNi9hT_witH_L0v3!}”, which is correct.

### Starving Parrot

The primes are generated by taking two random values and applying some fixed unknown polynomial to them. Once the two values are primes, the process is finished. Since we have access to the polynomial, we can easily recover it, for example by putting 10000000000000000000000000000000 as input we can clearly see the output 100…003700..002019. The polynomial is trivially deduced: $x^{13} + 37x+2019$. It follows that
$$n = (r^{13} + 37r+2019) \cdot (s^{13} + 37s+2019)$$
for some $r,s$ of size roughly 55 bits. Observe that $\sqrt[13]{n}$ provides a good approximation of $rs$. In fact, in the given setting $\lfloor \sqrt[13]{n} \rfloor = rs$. This number has 108 bits and can be easily factored:
$$\begin{multline*}251970989651144357978582196759904 = 2^5 \cdot 11 \cdot 13^2 \cdot 61 \cdot 239 \cdot 491\cdot\\ \cdot 3433 \cdot 137383 \cdot 1254599604823.\end{multline*}$$
This number has 2304 divisors in total. Each divisor gives a candidate for $r$ and its complement is a candidate for $s$. By applying the polynomial to them, we can obtain potential prime factors and check if they result in the same modulus. In the challenge we obtain
\begin{align*}r &= 30132816491977336,\\ s &= 15416171199104228.\end{align*}
Given the factorization, we can easily decrypt the message (don’t forget to invert the operations applied to the message before squaring):

“CCTF{it5____Williams____ImprOv3d_M2_Crypt0yst3m!!!}”.

### Oliver Twist

We can recognize the (twisted) Edwards curve addition formulas:
\begin{align*} x_3 &\equiv (x_1 y_2 + y_1 x_2) / (1 + d x_1 x_2 y_1 y_2)\pmod{p},\\ y_3 &\equiv (y_1 y_2 – a x_1 x_2) / (1 – d x_1 x_2 y_1 y_2) \pmod{p}. \end{align*}
In our case $a=3$ and $d=2$. You can learn a bit about twisted Edwards curves for example from slides by Christiane Peters. We are given $y$-coordinate of a point that was generated from the flag in a particular way. In order to find the $x$ coordinate, we have to plug the $y$ coordinate into the curve equation and solve for $x$:
$$3x^2 + y^2 – 2x^2y^2-1\equiv 0 \pmod{p}.$$
This is a quadratic equation in $x$ and we can easily find both roots. One of them is significantly smaller than $p$, so we can assume that this is the one we are looking for. This point $(x,y)$ is obtained from doubling the point $(m’, y)$ $(m’ \mod 3)$ times, where $m’$ is generated from the flag. Since we found a small $x$, we can guess that $m’ \mod 3 = 0$ and no squarings occured and that $x = m’$. Now, $m’$ is generated from the flag $m$ by adding $\sum_{i=1}^t 2^i + 3i$ to it for some small integer $t \ge 313$. We guess $t$ and subtract the added terms. We obtain for $t=313$ the flag:

“CCTF{N3w_But_3a5Y_Twisted_Edwards_curv3_Crypt0sys7em}”.

1. ##### Kevin Hu says:

Hi! I’m new to CTFs and was curious to how you got past the captcha problem before all the nc challenges.

1. ##### hellman says:

You have to write a small script to bruteforce it basically. You roughly needed 2^24 attempts to solve each challenge.

2. ##### Mister7F says:

how did you solve “NSA basement” ?
I’m very curious

1. ##### hellman says:

The factorization is easy since there are many common primes. The problem is that (apparently) the messages were encrypted with python’s Crypto.Cipher.PCKS_OAEP + Crypto.PublicKey.RSA. For some reason Crypto.PublicKey.RSA fails to decrypt if n is multi-prime. You have to decrypt manually and then use Crypto.Cipher.PKCS_OAEP to unpad.

3. ##### Kd says:

Even without anything fancy, it could be brute forced pretty quickly by a basic python script which just tested random strings.

4. ##### Mister7F says:

I factorized most of the “n” (using the GCD algo), but I couldn’t decipher…
Thank you :) I’ll try again :)

5. ##### IamLupo says:

Thank you for showing me the solution for Midnight Moon. I found the last part pretty fast. I became stuck on the first part because l was 27 =.=’

I had a crazy idea to figure out the prime factors of C[0]. And based with this to make create sets i call x. And to solve: x = y^k mod n to find possible k that where on the range: “CCTF{XXXXXXXXXXXXXXXXXXXXXX”.

Second idea i had it could be python had a random generation bug when you found the 1e (variable y) and 3e(variable v) random number. Based with these variable that i could generate variable u?

Here my result: https://pastebin.com/7Ccba7TA

6. ##### gmcn says:

About the challenge of supernatural, we successfully converted the calculation of the mod n elliptic curve to mod p (n = p * q).For the ECDLP problem of mod p, we try to use the sage built-in function discrete_log() to solve it, however, we don’t get it (for 5 min). Do you have any better solution for this?

1. ##### hellman says:

I contacted the author and he told that he had a mistake. The curves should have been anomalous. The challenge is unsolvable.