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

Solved with 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.