FPTU SecAthon 2020 | Cryptographic Writeup | CRY301 & CRY302

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.

CRY301

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.

MAGIK_STRING = b"Aww, c'mon, what's the worst that could happen?"

def handle(self):
        self.request.sendall(banner())
        n, d, e = gen_key_pair()
        self.request.sendall(b'    n = %d' % (n) + b'\n')
        self.request.sendall(b'    e = %d' % (e) + b'\n')
        self.request.sendall(b'    d = %d' % (d) + b'\n')
        self.request.sendall(
            b'\n    Now if you say the magik number correctly, I\'ll give you a magik string as a reward\n')
        self.request.sendall(b'    Enter your number here: ')
        try:
            magik_number = int(self.rfile.readline().decode())
        except ValueError:
            self.request.sendall(b'\n    ' + random_quotes() + b'\n')
            return
        if magik_number == pow(bytes_to_long(MAGIK_STRING), e, n):
            self.request.sendall(b'\n    ' + random_quotes() + b'\n')
            return
        if not pow(magik_number, d, n) == bytes_to_long(MAGIK_STRING):
            self.request.sendall(b'\n    ' + random_quotes() + b'\n')
            return
        self.request.sendall(b'\n    ' + rewards() + b'\n')

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}

CRY302

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.

MAGIK_STRING = b"I cannot be good. I must be perfection."
SUFFIX = b"You lack imagination."

def handle(self):
    self.request.sendall(banner())
    n, d, e = gen_key_pair()
    self.request.sendall(b'    n = %d' % (n) + b'\n')
    self.request.sendall(b'    e = %d' % (e) + b'\n')
    self.request.sendall(b'    d = %d' % (d) + b'\n')
    self.request.sendall(
        b'\n    Now if you say the magik number correctly, I\'ll give you a magik string as a reward\n')
    self.request.sendall(b'    Enter your number here: ')
    try:
        magik_number = int(self.rfile.readline().decode())
    except ValueError:
        print('Not a number')
        self.request.sendall(b'\n    ' + random_quotes() + b'\n')
        return
    if magik_number == pow(bytes_to_long(MAGIK_STRING), e, n):
        print('Sent c')
        self.request.sendall(b'\n    ' + random_quotes() + b'\n')
        return
    if not long_to_bytes(magik_number).endswith(SUFFIX):
        print('Not end with suffix')
        self.request.sendall(b'\n    ' + random_quotes() + b'\n')
        return
    if not pow(magik_number, d, n) == bytes_to_long(MAGIK_STRING):
        print('Decrypt does not return magik')
        self.request.sendall(b'\n    ' + random_quotes() + b'\n')
        return
    self.request.sendall(b'\n    ' + rewards() + b'\n')

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

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