[CSAW2019] — Writeup

Writeup for CSAW CTF 2019 by Nicholas.

CSAW CTF Qualification Round 2019

I’m going to explain my writeup for some challenges that I have done in this year CSAW CTF.

Crypto: Fault Box — 400 point

The challenge give us a service and the file server.py

The Problem code

When I try to connect to the service, I was greeted by this message.

====================================
            fault box
====================================
1. print encrypted flag
2. print encrypted fake flag
3. print encrypted fake flag (TEST)
4. encrypt
====================================

So basically, we need to enter our chosen menu, and the service will return the encrypted message. For menu 1, the service will return the encrypted flag (the one that we need to decrypt), menu 2 will return the encrypted fake_flag, menu 3 will return the encrypted fake_flag also, but with different method (CRT), menu 4 will ask us for an input, and they will return the encrypted message. Let’s check the problem challenge code.

This code show that we could encrypt as many message as we can with fourth menu, but only given us chance to choose two out of the first three menu before changing its N.

After examining for a while, this challenge only give us the e value, which is 0x10001. Not only that, the challenge give us chance to encrypt as many message as we can using the fourth menu without changing the N value, but only give us chance to select two of the first three menu.

So, our first mission is we need to retrieve the N value first. Using the fourth menu and a simple math, we could retrieve the N value based on the definition of congruence itself.

The Equation to retrieve the script

Using the fourth option, We could retrieve the N based on the above equation. If you get the wrong value, that means the GCD result is N * GCD(k1, k2). To solve this problem, you just need to repeat the above equation and GCD it with the previous result.

Unfortunately, we couldn’t factor the N with factordb, so we need to examine once more the service code to craft our payload on getting the factor of N. Try to look at the option number 3, where he encrypt the fake_flag.

Seems there is a bug on that equation

So basically, the function want to encrypt the message using CRT, where ep and eq is equals to e actually. There is a bug on the encrypt where it xor the pow(m, eq, q) with fun variable. We could do derivation from this faulty equation, which eventually will lead to the factor of N.

The correct method for encrypting with CRT

Above is the correct equation if you want to encrypt the message with CRT. You could merge the c1 and c2 with CRT to retrieve the c value. But, because of the faulty equation on the c2 encryption (xor with fun variable), here what happen to the equation.

The TEST_CRT_Encrypt function equation

Based on that derivation, we could see that the the result of faulty encryption could not be divided by q, which mean that if we look for the GCD between N, we will got p. THAT’S HOW WE GET THE MODULUS FACTOR!! To make it clearer, here is the equation:

WE GOT THE P

Based on that, in order to get the factor of N, we need to have known plaintext and cipher-text first, and then using them to factorize N. That’s where the fake_flag come. We need to use the fake_flag as our message (because the option 3 return the faulty encrypted of fake_flag) to get the p and q value.

Unfortunately, the service only limit us to choose two of the first three menu. That means that we need to use option 1 to retrieve the encrypted real_flag and choose between the option two and three as our last choice. The most obvious choice is we choose the option three because what we really need is the faulty encrypted fake_flag.

Luckily, remember that we already have the N value. Examining the fake_flag generation code, the space of the fake_flag is very small (my guess is under 10000 possibility), and we could try bruteforcing the fake_flag and try encrypting it with the N value. To validate whether our fake_flag prediction is correct or not is very simple. When the result of GCD(faulty_encrypt-real_encrypt, N) is very big (because the result is p value), that means we found the correct fake_flag and the p value.

After getting the p value, we just need to do normal decryption to the encrypted_real_flag that we got from the first option. Here is my script to solve this challenge.

Solver Script

Here is the result of my script:

OOOO WE GOT THE FLAG

Flag: flag{ooo000_f4ul7y_4nd_pr3d1c74bl3_000ooo}

Crypto: Super Curve — 300 point

Here is the server.py file.

The Challenge Source Code

Reading on the code above, basically we only need to put the correct secret_scalar. Well, as you can see, the secret scalar space is very small, only 7919. We only need to brute force the secret_scalar and the service will return the flag. I don’t know if my solution is the intended solution or not because it seems to be too easy for 300 point.

Solver Script

Here is the the result of my solver script:

We got the flag

Flag: flag{use_good_params}

Crypto: byte_me — 50 point

On this challenge, we were given a service that require us to give an input, and they will return an encrypted message.

The service appearance

At first, I try to input something to gain insight about what does the service did. As you can see, when we try to connect to the service, they return an encrypted message, which I guess is the flag. I try to give blank input, and the service return the same encrypted message from the first. If I try to give an input let say “a”, the service will return a whole different encrypted message.

Based on this try, my educational guess would be it is a block cipher service, where their encrypted function would be similar to enc(input + flag). My guess about they encrypted my input + flag is because they return exactly the same thing when I give a blank input. Not only that, When I try to input a long input (see the image below), you could see that there is a block of 64 byte that was repeated.

On the above challenge, we could see that the encryption result were 112 byte, where only the first 64 byte from left is same.

So, based on my guess, we just need to attack it like a usual block cipher. We need to find first what is the correct input size, and after we know the correct input size, we could craft our payload by reducing our input while brute-forcing the flag character.

Illustration on how to solve the challenge

To recap, in order to get the flag, we need to find first how much character input do we need to fully fill 1 block, and compare the result between ‘A’ * (n-len(curr_flag)-1) and ‘A’ * (n — len(curr_flag) — 1) + guess_char

Here is the full script. Note that maybe our flag is longer than 1 block, so I decided to find the correct input to fully fill 4 block.

Here is the result of my script:

FLAGGGGGG

Flag: flag{y0u_kn0w_h0w_B10cks_Are_n0T_r31iab13...}

Web: Secure File Storage — 300 point

Under Construction. I will try to explain it if I have time