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

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():
ciphers = encrypted.split(", ")
flag = []
for c in ciphers:
ch = solve_single(int(c))
if f is not None:
flag.append(ch)
return ''.join(flag)

``````

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