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
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:
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.
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 ? We can observe, from below, that 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 , 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 as a replacement for RET_i_j
:
From above, it is evident that and . Hence . We are able to further derive that and is an inverse operator for addition and multiplication, respectively (i.e., and ). With more tests (for example, knowing that ), it is verified that those operations are using is the modulo. Let's summarize what we have in the below table:
Operation | Description |
---|---|
return a random number... maybe | |
return | |
return | |
return | |
return |
⏲️ ⏲️ Day 1, 13:30 (330 minutes in) ⏲️ ⏲️
We have further guessed (and experimented) that is another multiplication and 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 ).
⏲️ ⏲️ 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, takes three parameters and runs several arithmetic operations, and eventually return one value. Let's translate a sample response of the function call...
Let's express (the output) in terms of (the inputs) mathematically.
Here they have introduced two more unknowns and those are kept unchanged in the same connection.
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 for some fixed . Now let's bring in our translated interaction2.txt
:
Since the output for is , I assumed that our objective is to find such that
⏲️ ⏲️ Day 1, 15:08 (428 minutes in) ⏲️ ⏲️
I was expecting that everything would be simpler if I can make
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 and ...
⏲️ ⏲️ Day 1, 15:10 (430 minutes in) ⏲️ ⏲️
The flag pops right away: OOO{D0Y0uUnd3rstandWh4tANumberIs?}
! Not so crypto, eh?
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 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...
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 1Samuel — 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.
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 . 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 helpfulR3x — 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⌗
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 cryptoGH0S1 — 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.