# DEF CON CTF Quals 2021: Day 1

I played DEF CON CTF Quals once again with @Shellphish and we ended up at the 10th place. This blog post describes what actually was going on from my side. If you are looking for an informative blog post, this is not a good-read for you. There would be a little useful information, since I am just hanging around most of the time. I will even shamelessly copy some memes online to make the blog post looked rich in content.

After all, I am only able to solve *nooombers* (on day 1), *qoo-or-ooo* and *back-to-qoo* (on day 2). What happened on day 2 from my point of view is considerably more interesting.

## Challenge: nooombers⌗

nooombers(44 solves, 127 points)I really do not understand what this is about, but my cousin told me that once he managed to got a flag out of this. I was able to copy from my cousin's shell parts of his interactions with the server. You can find them in interaction1.txt and interaction2.txt. Unfortunately, they are incomplete.

`nooombers.challenges.ooo 8765`

Files: interaction1.txt, interaction2.txt

*Paul*,

*Subwire*and more.

### Part I: Understanding the challenge⌗

⏲️ ⏲️ *Day 1, 10:45 (165 minutes in)* ⏲️ ⏲️

It is good to be greeted in the morning with a crypto challenge. I am pretty excited to see a crypto challenge in a pwn-intensive CTF. Let's see what is it about. I bet it is attributed to *fish* since I am seeing a bunch of 魚's (i.e., the Chinese word of fish).

⏲️ ⏲️ *Day 1, 11:08 (188 minutes in)* ⏲️ ⏲️

After a while, I learned how to interact with the server. In `interaction1.txt`

, there are multiple copies of the below string:

```
髛髛髛 # Title, maybe?
鬆 # Operation 0
魢 # Operation 1
魀 # Operation 2
鯞 # Operation 3
鮂 # Operation 4
魻 # Operation 5
鬼 # Operation 6
鮳 # Operation 7
鯑 # Operation 8
鮽 # Operation 9
魵 # Operation 10
髛 # Send me something!
```

They are actually the menu. On top of that, they have defined 11 operations, namely `鬆`

, `魢`

, ... up to `魵`

. Furthermore, `髛`

is somewhere asking for inputs. At this moment, the only operation I knew it `魵`

, which is an exit. Also, worth noting that the character set changes on each `nc`

connection.

We are then able to send one of the above operations. For instance, `鬆`

. It then return a line of gibberish:

`鬆 鱷鳘鰬鰛鳘鰑鳌鲯鳗鲳...鱈鲒鲲鱱鳣鰂鳇鲫鳃鳾`

One thing I suspected is the long strings are actually used repeatedly. Therefore, I tried to translate `interaction1.txt`

into something that is slightly more readable. Each `OP_*`

is a single character representing an operation, and `RET_*_*`

is a 144-character string represents the return values of the operations.

```
Welcome to nooombers! Press enter to start...
MENU
INPUT OP_0
OP_0 RET_0_1
MENU
INPUT OP_1
INPUT RET_0_1
OP_1 RET_0_1 RET_1_1 RET_1_2
MENU
INPUT OP_3
INPUT RET_0_1
INPUT RET_1_2
OP_3 RET_0_1 RET_1_2 RET_1_1 RET_3_1
MENU
INPUT OP_2
INPUT RET_0_1
OP_2 RET_0_1 RET_1_1 RET_2_1
MENU
INPUT OP_4
INPUT RET_0_1
INPUT RET_2_1
OP_4 RET_0_1 RET_2_1 RET_1_1 RET_4_1
MENU
INPUT OP_3
INPUT RET_3_1
INPUT RET_4_1
OP_3 RET_3_1 RET_4_1 RET_1_1 RET_4_1
MENU
INPUT OP_3
INPUT RET_4_1
INPUT RET_4_1
OP_3 RET_4_1 RET_4_1 RET_1_1 RET_3_2
MENU
INPUT OP_3
INPUT RET_3_2
INPUT RET_4_1
OP_3 RET_3_2 RET_4_1 RET_1_1 RET_3_3
MENU
INPUT OP_3
INPUT RET_3_3
INPUT RET_4_1
OP_3 RET_3_3 RET_4_1 RET_1_1 RET_3_4
MENU
INPUT OP_3
INPUT RET_3_4
INPUT RET_4_1
OP_3 RET_3_4 RET_4_1 RET_1_1 RET_3_5
MENU
INPUT OP_3
INPUT RET_3_5
INPUT RET_4_1
OP_3 RET_3_5 RET_4_1 RET_1_1 RET_3_6
MENU
INPUT OP_3
INPUT RET_3_6
INPUT RET_4_1
OP_3 RET_3_6 RET_4_1 RET_1_1 RET_3_7
MENU
INPUT OP_3
INPUT RET_3_7
INPUT RET_4_1
OP_3 RET_3_7 RET_4_1 RET_1_1 RET_3_8
MENU
INPUT OP_3
INPUT RET_3_8
INPUT RET_4_1
OP_3 RET_3_8 RET_4_1 RET_1_1 RET_3_9
Too much! Disabling one option...
MENU (OP_9 REMOVED)
INPUT OP_4
INPUT RET_3_2
INPUT RET_3_3
OP_4 RET_3_2 RET_3_3 RET_1_1 RET_3_6
MENU (OP_9 REMOVED)
INPUT OP_6
INPUT RET_3_3
INPUT RET_3_2
```

I have also translated `interaction2.txt`

and knew that `OP_9`

is the operation that win us the flag. That said, if we are too annoying (i.e., sending too much queries), we're not able to get flag anymore.

### Part II: A wild but legit guess⌗

⏲️ ⏲️ *Day 1, 11:51 (231 minutes in)* ⏲️ ⏲️

While I am looking at the translated `interaction1.txt`

, a strange idea popped up to my mind. Would the below operation represent $2\times3 = 6$? We can observe, from below, that `OP_4(RET_3_2, RET_3_3) = (RET_1_1, RET_3_6)`

.

```
MENU (OP_9 REMOVED)
INPUT OP_4
INPUT RET_3_2
INPUT RET_3_3
OP_4 RET_3_2 RET_3_3 RET_1_1 RET_3_6
```

Hence, we assume that `OP_4`

is the multiplication operation. Also, `RET_3_2 = 2`

, `RET_3_3 = 3`

, `RET_3_6 = 6`

. Base on the assumption, I don't think we are ambitious to assume that `RET_3_k = k`

for all $k > 1$, `RET_3_1 = 0`

and `RET_4_1 = 1`

. Last but not least, `OP_3`

is the addition operation.

### Part III: Recovering the functions⌗

⏲️ ⏲️ *Day 1, 12:37 (277 minutes in)* ⏲️ ⏲️

I experimented for a while and I was pretty convinced that my guess is correct. It was pretty unbelieveable that I am able to guess well.

Let's translate `interaction1.txt`

mathematically and fill in what we knew. Since `RET_1_1`

is returned in every call (except the first), I am going to skip it. I am using $x_{i, j}$ as a replacement for `RET_i_j`

:

- $\text{OP}_0() = x_{0, 1}$
- $\text{OP}_1(x_{0, 1}) = x_{1, 2}$
- $x_{0, 1} + x_{1, 2} = x_{3, 1}$
- $\text{OP}_2(x_{0, 1}) = x_{2, 1}$
- $x_{0, 1} \times x_{2, 1} = 1$
- $x_{3, 1} + 1 = 1$
- $1 + 1 = 2$
- $2 + 1 = 3$
- $3 + 1 = 4$
- $4 + 1 = 5$
- $5 + 1 = 6$
- $6 + 1 = 7$
- $7 + 1 = 8$
- $8 + 1 = 9$
- $2 \times 3 = 6$

From above, it is evident that $x_{3, 1} = 0$ and $x_{2, 1} = {x_{0, 1}}^{-1}$. Hence $x_{1, 2} = -x_{0, 1}$. We are able to further derive that $\text{OP}_1$ and $\text{OP}_2$ is an inverse operator for addition and multiplication, respectively (i.e., $\text{OP}_1(x) = -x$ and $\text{OP}_2(x) = x^{-1}$). With more tests (for example, knowing that $x_{1, 1} \times x_{1, 1} = x_{1, 1} + x_{1, 1} = 0$), it is verified that those operations are using $x_{1, 1}$ is the modulo. Let's summarize what we have in the below table:

Operation | Description |
---|---|

$\text{OP}_0()$ | return a random number... maybe |

$\text{OP}_1(x)$ | return $-x\ \text{mod}\ q$ |

$\text{OP}_2(x)$ | return $x^{-1}\ \text{mod}\ q$ |

$\text{OP}_3(x, y)$ | return $x + y\ \text{mod}\ q$ |

$\text{OP}_4(x, y)$ | return $xy\ \text{mod}\ q$ |

⏲️ ⏲️ *Day 1, 13:30 (330 minutes in)* ⏲️ ⏲️

We have further guessed (and experimented) that $\text{OP}_5$ is another multiplication and $\text{OP}_6$ is exponentation. At first, I didn't know why are there two multiplications, it took me some time that they are operated on a different modulus (denote it as $p$).

⏲️ ⏲️ *Day 1, 13:33 (333 minutes in)* ⏲️ ⏲️

*Me: What is the deal for operation 7? There are so much asterisks... Let's skip it.*

⏲️ ⏲️ *Day 1, 14:03 (363 minutes in)* ⏲️ ⏲️

Instead of a simple mathematical operation, $\text{OP}_8$ takes three parameters and runs several arithmetic operations, and eventually return one value. Let's translate a sample response of the function call...

```
MENU
INPUT OP_8
INPUT X1
INPUT X2
INPUT X3
MODINV X3 Q Y1
MUL X1 Y1 Q Y2
MUL X2 Y1 Q Y3
POW R1 Y2 P Y4
POW R2 Y3 P Y5
MUL Y4 Y5 P Y6
OP_0 Y7
NEG Y7 Q Y8
ADD Y6 Y7 Q Y9
ADD Y9 Y8 Q Y10
OP_8 X1 X2 X3 Y10
```

Let's express $y_{10}$ (the output) in terms of $x_1, x_2, x_3$ (the inputs) mathematically.

\[\begin{aligned} y_{10} &= (y_9 + y_8)\ \text{mod}\ q \\ &= [(y_6 + y_7) + (-y_7)]\ \text{mod}\ q \\ &= y_6\ \text{mod}\ q \\ &= (y_4y_5\ \text{mod}\ p)\ \text{mod}\ q \\ &= ({r_1}^{y_2} {r_2}^{y_3}\ \text{mod}\ p)\ \text{mod}\ q \\ &= ({r_1}^{x_1 y_1\ \text{mod}\ q} {r_2}^{x_2 y_1\ \text{mod}\ q}\ \text{mod}\ p)\ \text{mod}\ q \\ &= ({r_1}^{x_1/x_3\ \text{mod}\ q} {r_2}^{x_2/x_3\ \text{mod}\ q}\ \text{mod}\ p)\ \text{mod}\ q \\ \end{aligned}\]

Here they have introduced two more unknowns $r_1$ and $r_2$ those are kept unchanged in the same connection.

**What is that?**During the contest, I feel like this is implementing something but I could not recall. After the contest, I was by

*N00bcak*and

*rbtree*that was actually the data signature algorithm (DSA). Turns out operation 8 is a function verifying if your signature $(x_2, x_3)$ is correct, given the digest $x_1$. Hereby $r_1$ and $r_2$ corresponds to the generator and public key, respectively.

### Part IV: Identifing the objective and getting through⌗

⏲️ ⏲️ *Day 1, 14:36 (396 minutes in)* ⏲️ ⏲️

Operation 9 is literally the most important function that we gotta look into. Since we knew most of the operations, it is pretty easy to understand what it does. Well, it is just $\text{OP}_9(x_2, x_3) = \text{OP}_8(r_0, x_2, x_3)$ for some fixed $r_0$. Now let's bring in our translated `interaction2.txt`

:

```
MENU
INPUT OP_9
INPUT X2
INPUT X3
MODINV X3 Q Y1
MUL R0 Y1 Q Y2
MUL X2 Y1 Q Y3
POW R1 Y2 P Y4
POW R2 Y3 P Y5
MUL Y4 Y5 P Y6
OP_0 Y7
NEG Y7 Q Y8
ADD Y6 Y7 Q Y9
ADD Y9 Y8 Q X2
OP_9 R0 X2 X3 X2
Correct signature! This is the flag:
...
```

Since the output for $\text{OP}_9$ is $x_2$, I assumed that our objective is to find $x_2, x_3$ such that

\[({r_1}^{r_0/x_3\ \text{mod}\ q}{r_2}^{x_2/x_3\ \text{mod}\ q}\ \text{mod}\ p)\ \text{mod}\ q = x_2.\]

⏲️ ⏲️ *Day 1, 15:08 (428 minutes in)* ⏲️ ⏲️

I was expecting that everything would be simpler if I can make

\[x_2 = {r_1}^{r_0/x_3} = {r_2}^{x_2/x_3} = 1.\]

**It did happen.** I was randomly messing around with the operations and found that they have mistakenly defined `MODINV(0) = 0`

. That said, I can set $x_2 = 1$ and $x_3 = 0$...

⏲️ ⏲️ *Day 1, 15:10 (430 minutes in)* ⏲️ ⏲️

The flag pops right away: `OOO{D0Y0uUnd3rstandWh4tANumberIs?}`

! Not so crypto, eh?

**Slack alert!**I am definitely being slack since there are no more crypto challenges in the rest of the day. 95% of the content onwards is pointless.

### Part V: Postmortem⌗

The crypto involved in this challenge is digital signature algorithm (DSA). I went through some discussions after the contest, and turns out operation 7 is the signing process for DSA, for a given digest. I think the intentional solution would be the poor random number it generates with $\text{OP}_0$ that is used in signing.

## Challenge: exploit-for-dummies⌗

⏲️ ⏲️ *Day 1, 15:33 (453 minutes in)* ⏲️ ⏲️

Since I have nothing to do, I hopped into the challenge and tried to find the answers for the unsolved trivia questions. Seeing no crypto, I decided to have a break.

## Side story: Inspecting the `/challenge`

API⌗

⏲️ ⏲️ *Day 1, 16:06 (486 minutes in)* ⏲️ ⏲️

I took some time integrating *ctfbot* to ping teammates when there is a challenge update. While I was inspecting the `/challenge`

API, I saw something fishy...

`{"message": { /* omitted... */ "unopened_by_category": {"haiku": 9}}}`

Wait, does it mean that there are only nine challenges yet-to-be released?

## Challenge: mooosl⌗

⏲️ ⏲️ *Day 1, 19:51 (711 minutes in)* ⏲️ ⏲️

kylebot — Today 19:51

This is a hash collision+musl libc

The bug is that the next pointer is not cleared after delete

What we can do is: find a pair of different keys hashed into a same bucket, one of them of length 1

Samuel — Today 19:52

hash collision! need help?

kylebot — Today 19:52

And then bruteforce the byte by querying it

I'm not on a computer rn

But yes. We need many collisions

Shortly after, *Robin* send me the code for the hash.

```
__int64 __fastcall sub_13DB(__int64 a1, unsigned __int64 a2)
{
int i; // [rsp+14h] [rbp-Ch]
__int64 v4; // [rsp+18h] [rbp-8h]
v4 = 2021LL;
for ( i = 0; a2 > i; ++i )
v4 = 322401073 * v4 + *(i + a1);
return v4;
}
```

Wow, it is pretty easy! This would be a little practice on lattices, right?

kylebot — Today 19:54

@Samuel also

Mod 0x1000

Bummer, it is a different story under modulo 0x1000. Everyone can find collisions easily...

⏲️ ⏲️ *Day 1, 21:00 (780 minutes in)* ⏲️ ⏲️

I finished the collider that finds collision in $\mathcal{O}(1)$. It finds infinitely many preimages those have the same digest. Well, I don't even know what is it used.

## Challenge: rick⌗

⏲️ ⏲️ *Day 1, 21:02 (782 minutes in)* ⏲️ ⏲️

I was once baited by crypto-related terms. This time it is *rick*.

Paul — Today 21:02

if you could undo the encryption though, that'd be super helpful

R3x — Today 21:03

isn't the encryption just xoring with letters RICK?

Ooof. This challenge actually looked fun but I did not investigate any further. I have strong teammates, after all.

## Side story: Creating a crypto challenge⌗

**Good that you read up to here.**Maybe you will be slightly benefited for the next CTF I help organizing!

I was inspired by *nooombers* to create a CTF challenge. Of course, I am not going to mention what is it. I am still unable to write an exploit after until now...

## End of day 1⌗

The organizers decided to release two more challenges near the end of the day (under GMT+8). Well, both of them are categorized as *reverse-pwn*. I rather go to bed...

Samuel — Today 23:52

darn you ooo

wake me up when there is a crypto

GH0S1 — Today 23:52

@Samuel cryptocurrency?

GH0S7_1N_7H3_F1NG3RS — Today 23:53

@Samuel this is cryptocurrency

Never mind, good night. Wait, no, it actually matters - *crypto is not cryptocurrency but cryptography*.