COMPFEST CTF 2020

Mon, Sep 7, 2020 3-minute read

This is writeup for COMPFEST CTF 2020. It’s such a long time I haven’t taken part in any CTFs. Actually, I have some knowledge and experience about cryptography but I haven’t used it for years. I want to refine it.
So, let’s get it.

I-Hope-It-Is-Easy

Challenge gives us 2 files: prob.py and encrypted.txt.
Here is the prob.py:

import random

def f(n):
    c = 0
    for i in range(2, n):
        if (n^0 == n):
            if (n*n // n == n):
                if (2*n != n-1):
                    if (n**0 + 1 != 1):
                        m = n
                        while (m > 0):
                            m -= i
                        if (m == 0):
                            c += 1
    if (c == 1):
        return True
    else:
        return False

FLAG = open('flag.txt', 'rb').read()
encrypted = []
a = 10**400
b = 10**500
n = random.randint(a, b)
for c in FLAG:
    while(not(f(n))):
        n = random.randint(a, b)
    encrypted.append(c ^ n)
    n += 1

txtFile = open('encrypted.txt', 'w')
txtFile.write(', '.join(list(map(str, encrypted))))

Let’s look at function f(n):

The if sequence is always True
The next while and if is to test m is divisible by i.

So, f returns True only if n has only one divisor that’s greater than 1. Hence, n is square number. Now, we have a condition to verify n for each cipher number in encrypted.txt
Below is python script to solve this challenge.

# brute force in printable character set
# find n by XOR cipher with character
# if n is square number returns the corresponding character
def solve_single(c):
    for i in string.printable:
        n = ord(i) ^ c
        if gmpy2.is_square(n):
            return i
    return None

#
def get_flag():
    encrypted = open('encrypted.txt').read()
    ciphers = encrypted.split(", ")
    flag = []
    for c in ciphers:
        ch = solve_single(int(c))
        if f is not None:
            flag.append(ch)
    return ''.join(flag)


print get_flag() # COMPFEST12{ez_pz_lemonade_squeez_a42447}

Mutual-Friend

The challenge provides us a zip archive which contains 5 files.
After quick glance at those files, we can conclude:

primes.txt has 4000 primes
main.py applies the RSA encryption with pair of primes from primes.txt.

So, if server returns 2 N that has the same one factor, we can find another factor then decrypt the corresponding cipher.
Below is dummy script to solve the challenge.

import socket
import gmpy2

HOST = '128.199.157.172'
PORT = 27268

try:
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    print "Socket successfully created"
except socket.error as err:
    print "socket creation failed with error %s" %(err)

s.connect((HOST, PORT))
requested = False
N = None
c = None
e = 65537
while True:
    # dummy check
    if not requested:
        d = s.recv(4096)
        s.sendall('\n')
        requested = True
    recv = s.recv(8192)
    if not repr(recv).__contains__("N ="):
        s.sendall(b'\n')
        continue
    data = repr(recv).split('\\n')
    data = data[1:-2]
    # get the first N
    if N is None:
        N = int(data[0].split(' = ')[1])
        c = int(data[-1].split(' = ')[1])
        s.sendall(b'\n')
        continue

    N1 = None
    for d in data:
        if d.__contains__("N = "):
            N1 = int(d.split(' = ')[1])
            break
    if N1 is None:
        continue
    gcd = gmpy2.gcd(N, N1)
    # find another N that has the same factor
    if gcd != 1:
        print "Found " + "="*81
        p = gcd
        q = gmpy2.div(N, gcd)
        phi = (p-1)*(q-1)
        d = gmpy2.invert(e, phi)
        plain_text = hex(gmpy2.powmod(c, d, N))[2:].decode("hex")
        print plain_text  # COMPFEST12{Euclid_W0ulD_b_Pr0Ud_Ov_4l1_7h3sE_MetH_eXpeRt5_a39e7a}
        break

    s.sendall(b'\n')

That’s 2 challenges I solved. The mutual-friend makes me realize that I’ve lost really much. I have to re-read about RSA to solve this.
Shame on me.

I'm Envy-T