Cryptography Write Up | FU SecAthon Season 3 | FPTU 2020

This is an annual competition for FPT University students to practice their skills with jeopardy CTF challenges. I was with my team, M1sh13f, and we’re at the #5 place. Congrats me and my amazing teammates!!!!

No more beating around the bush, here are my write-ups for the first two cryptography challenges.

Challenge: CRY301 – 1000 pts

Server responses when you connect with the netcat command

When netcat to the server, I can easily see that this cryptography challenge is about RSA encryption and decryption with the presence of public key n, e and also the private key d.

But clearly, the server doesn’t tell anything about the ciphertext to decrypt or the message to encrypt. So, I take a look at the given zip file, containing two files: quotes.py and server.py.

The quotes.py file contains a list of possible messages that the server will send you if you don’t come up with the right flag. So, I don’t spend any minute on the quotes.py but the other file server.py.

The main handle function in server.py

So, the message to encrypt here is the given MAGIK_STRING. And you need to find the ciphertext. It’s easy enough as the server already gave out the key. But you can see that the server won’t accept the value of c = pow(message, e, n).

The solution here is to find the number c’ that c and c’ are congruent modulo n. Simply enough, you just need to add c with n.

c’ = c + n

Send c’ to the server and here is the flag:

FUSEC{Rul3s_4r3_m4d3_t0_b3_br0k3n_lik3_buildingz_0r_p30pl3_1602068882}

Challenge: CRY302 — 1000 pts

This challenge is an upgraded version of the CRY301 problem you have seen above. netcat to the server will ask us to input the magik number.

Check out the given source code, it tells us something about the prefix of the magik number.

A part of the server.py file

This challenge gives us more condition for the valid magik number. Similar to the first problem, we will need to find the number c’ that c and c’ are congruent modulo n. Also, c’ must end with the given SUFFIX.

Check out the first hint for some help.

The first hint tells us to use Sagemath, to find the roots of an equation????

The first hint gave me the idea of crafting an equation. As c’ and c are congruent modulo n, c’ = c + x * n. So, I have one side of an equation with an unknown x.

The other side of the equation will present the condition of ending with SUFFIX. The second and third hints tell me exactly what I was looking for.

The second hint is about how the bytes_to_long() and long_to_bytes() function work

The ultimate last hint is about how the endswith() method can be presented into the equation

So, here is the other side of the equation c’ = k * 16 ** len(hexlify(SUFFIX)) + bytes_to_long(SUFFIX) with the unknown k. You can calculate the length of SUFFIX and the value of bytes_to_long(SUFFIX). And the complete equation with c = pow(magik_String, e, n):

c + x * n = k * 16 ** 42 + 130709955709673130759780524244946733922755218992686

The next step is to solve this equation and find one value of x and k. The Sage Cell Server, an online version of Sagemath, can help.

Sagemath command to solve the equation from Sagemath doc

Replace the c and n value, and here is the output.

The unknowns x and k are described through the new t_0 variable.

Now I only need the x value, so I will choose a random value for t_0 to find x. The simplest case is t_0 = 0, and I have the value of x. Then calculate c’ = c + x * n.

Submit c’ to the server and here is our flag.

FUSEC{In_c4rn4g3_I_bl00m_lik3_4_fl0w3r_in_th3_d4wn_1602085220}

I will update the write-up for the final challenge of this competition as soon as possible. Thank you for reading.

Keeping on CTF :))) !!!!

— Jessie —