[ESAIP CTF 2023] All crypto challenges
Tags: #cryptography #ctf
2023-06-02
This article contains write-ups for all cryptography challenges from ESAIP CTF 2023. All challenge files, prompts and solves are available here.
The event was nice and I had a great time competing with my friends. However, I’d like to quickly rant before diving into the write-ups.
<rant>
- Please make sure the given source code actually works (even better, publish the Dockerfiles you use so players don’t have to waste time debugging)
- I was tired and didn’t notice I had solved a challenge locally because no flag was printed … turns out the challenge file didn’t contain a placeholder flag :) </rant>
Bowser’s Box
Bowser wants to get the ultime lucky box ! You new to find it before him !
Probably my favourite challenge, not too hard but an interesting concept nonetheless. The following Python source code is given:
from Crypto.Util.number import bytes_to_long
from multiprocessing import Process
from os import urandom
import socket
BANNER = b"""
__________ /\ __________
\______ \ ______ _ ________ __________)/ ______ \______ \ _______ ___
| | _// _ \ \/ \/ / ___// __ \_ __ \/ ___/ | | _// _ \ \/ /
| | ( <_> ) /\___ \\\\ ___/| | \/\___ \ | | ( <_> > <
|______ /\____/ \/\_//____ >\___ >__| /____ > |______ /\____/__/\_ \\
\/ \/ \/ \/ \/ \/
"""
def read_line(s):
body = b""
while True:
ch = s.recv(1)
if ch == b"\n":
break
body = body + ch
return body
def challenge(s):
s.send(BANNER)
s.send(b"What's the SBox you want to use for the encryption?\n")
s.send(b"Example : 1,2,3,4,5,6...\n")
try:
sbox = read_line(s).decode()
sbox = sbox.split(",")
sbox = tuple([int(x) for x in sbox])
assert len(sbox) == 256
except:
s.send(b"SBox is invalid!\n")
exit()
# N.B: modified version of https://github.com/bozhu/AES-Python to work with
# python3 and where SBOX is passed to constructor and set before
# change_key is called
from aes import AES
master_key = bytes_to_long(b"ECTF{??????????}")
AES = AES(master_key, sbox)
ciphertext = AES.encrypt(bytes_to_long(urandom(120)))
s.send(b"Cipher text: " + str(ciphertext).encode() + b"\n")
return
if __name__ == '__main__':
s = socket.socket()
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
s.bind(("0.0.0.0", 55555))
s.listen(10)
while True:
client, addr = s.accept()
print("Got connect from " + str(addr))
p = Process(target=challenge, args=(client,))
p.daemon = True
p.start()
client.close()
We can control the SBOX for the encryption of a single random message and we have to leak the key. I originally thought of doing something like in this StackOverflow post where the SBOX is set to an identity mapping ([0x0, 0x1, ..., 0xff] => [0x0, 0x1, ..., 0xff]) so that no substitution actually takes place but it wouldn’t have worked as we need to leak the encryption key, not the plaintext.
What I chose to do instead was to send an empty/null SBOX (256 zeros). The commented encrypt function below explains why.
def encrypt(self, plaintext):
# convert plaintext block to 4 x 4 matrix
self.plain_state = text2matrix(plaintext)
# plaintext ^= round_keys[:4]
self.__add_round_key(self.plain_state, self.round_keys[:4])
# useless, we'll see why below
for i in range(1, 10):
self.__round_encrypt(self.plain_state, self.round_keys[4 * i : 4 * (i + 1)])
# perform substitution but since the SBOX is all 0s the resulting plain_state
# will also be all 0s, thus rendering entirely useless every operation done
# until now
self.__sub_bytes(self.plain_state)
# shift the rows (useless as all the values are 0)
self.__shift_rows(self.plain_state)
# plain_state ^= xor round_keys[40:]
# but as the plain_state is all 0s we have
# plain_state = round_keys[40:]
self.__add_round_key(self.plain_state, self.round_keys[40:])
# return plain_state (round_keys[40:]) as an int
return matrix2text(self.plain_state)
Basically, by using a null SBOX, we’ve turned the encryption function into the following:
def encrypt(self, plaintext):
return matrix2text(self.round_keys[40:])
Since the round_keys are derived from the “master key” (via the key scheduling algorithm) and each byte of the master key affects the same byte of each round key we can bruteforce the master key character by character.
This can be done with the following Python script:
from aes import AES, text2matrix, matrix2text
from Crypto.Util.number import long_to_bytes, bytes_to_long
import string
# Got this value by sending a null sbox to the remote server
ct = long_to_bytes(201063020592992157563690216943176785208)
pt = b''
for i in range(16): # 16 byte key
for c in string.printable:
test_key = pt + c.encode() + b'\x00' * (15 - len(pt))
cipher = AES(bytes_to_long(test_key), [0]*256)
if long_to_bytes(matrix2text(cipher.round_keys[40:]))[i] == ct[i]:
pt += c.encode()
break
print(pt)
# b'ECTF{AEEES_SBOX}'
Mario Chest
Mario wanted to hide his deepest secret in a chest to defeat Bowser. He shared part of the chest code with some of his friends, but now Mario is gone and the code is incomplete… You need to retrieve this secret !
We’re given the following Python source code:
import random
from decimal import Decimal,getcontext
from multiprocessing import Process
import socket
getcontext().prec = 80
FLAG = ""
# Menu
menu_options = {
"1": 'Get the secret',
"2": 'Create new share',
"3": 'Exit',
}
banner = b"""
_
_____ _ | | _____ _ _
| |___ ___|_|___|_|___ | | |_ ___ ___| |_
| | | | .'| _| | . | |_ -| | --| | -_|_ -| _|
|_|_|_|__,|_| |_|___| |___| |_____|_|_|___|___|_|
"""
# Print menu
def print_menu(s):
for key in menu_options.keys():
menu = key+ '--'+menu_options[key]
s.send(menu.encode()+b"\n")
# Get user input
def read_line(s):
body = b""
while True:
ch = s.recv(1)
if ch == b"\n":
break
body = body + ch
return body
def str_to_int(secret):
return sum([ord(c) * (256 ** i) for i, c in enumerate(secret)])
def int_to_str(secret_int):
secret_str = []
while secret_int > 0:
secret_str.append(chr(secret_int % 256))
secret_int //= 256
return ''.join(secret_str)
def create_point(x):
a = int(str(6**3)[1:] + str(5**4)[:2])
b = int(str(3**3)[1:] + str(4**4)[1:])
c = a * b
return x - c
def create_share(x,m,secret):
coefficients = coeff(m, secret)
shares.append((x, polynom(x, coefficients)))
def reconstruct_secret(shares):
sums = 0
for j, share_j in enumerate(shares):
xj, yj = share_j
prod = Decimal(1)
for i, share_i in enumerate(shares):
xi, _ = share_i
if i != j:
prod *= Decimal(Decimal(xi)/(xi-xj))
prod *= yj
sums += Decimal(prod)
return int(round(Decimal(sums), 0))
def polynom(x, coefficients):
point = 0
for coefficient_index, coefficient_value in enumerate(coefficients[::-1]):
point += x ** coefficient_index * coefficient_value
return point
def coeff(t, secret):
coeff = [random.randrange(0, 10**5) for _ in range(t - 1)]
coeff.append(secret)
return coeff
def generate_shares(n, m, secret):
coefficients = coeff(m, secret)
shares = []
for _ in range(1, n+1):
x = random.randrange(1, 10**5)
shares.append((x, polynom(x, coefficients)))
return shares
def verify_secret(generated_secret):
if generated_secret == FLAG:
return f"Okey, I'll share my secret with you : {FLAG}"
else :
return "I won't share my secret if you won't share yours ( ͡° ͜ʖ ͡°)"
# Challenge
def challenge(s):
s.send(banner)
while (True):
print_menu(s)
choice = read_line(s)
if choice.decode("utf-8") == "1":
pool = []
pool.append(shares[-1])
pool.append(shares[-2])
reconstructed = int_to_str(reconstruct_secret(pool))
result = verify_secret(reconstructed)
s.send(result.encode()+b"\n")
elif choice.decode("utf-8") == "2":
s.send(b"Enter your new share ID number : \n")
ID = read_line(s)
point = int(ID)
create_share(create_point(point),t,secret_int)
elif choice.decode("utf-8") == "3":
break
else:
s.send(b"Wrong choice: send 1,2 or 3\n")
# Main
if __name__ == '__main__':
t, n = 5, 10
secret_int = str_to_int(FLAG)
shares = generate_shares(n, t, secret_int)
s = socket.socket()
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
s.bind(("0.0.0.0", 55555))
s.listen(10)
while True:
client, addr = s.accept()
print(f"Got connect from {addr}")
p = Process(target=challenge, args=(client,))
p.daemon = True
p.start()
client.close()
The program seems to erronously implement a SSSS (Shamir’s Secret Sharing Scheme) in which we can either create a new share or recover the secret (if the reconstructed secret is equal to the original secret). Two functions from the original source code have been rewritten below to highlight the implentation errors.
def create_point(x):
# This function should make it so we can't chose the value
# of the resulting point, thankfully for us that's not the case
return x - 1256472
def reconstruct_secret(shares):
# Only the last 2 shares (instead of all 5) are used to recover
# the secret so we can rewrite the function as follows:
(xj,yj), (xi,yi) = shares
sums = Decimal(Decimal(xi) / (xi-xj)) * yj \
+ Decimal(Decimal(xj) / (xj-xi)) * yi
return int(round(Decimal(sums), 0))
From the rewritten version of the reconstruct_secret function it’s obvious that, for each part of the equation, if either x or y are equal to 0 then that part of the equation will be equal to 0.
Thus if we can create a share (0, f(0)), the function will always return f(0) (ie. the secret) and we can recover the flag. The demonstration for this is given below, where s is the share created by the program and u is the share we’ve created.
xi / (xi - xj) * yj + xj / (xj - xi) * yi <=> s / (s - u) * f(u) + u / (u - s) * f(s)
<=> s / (s - 0) * f(0) + 0 / (0 - s) * f(s)
<=> 1 * f(0) + 0 * f(s)
<=> f(0)
To do this, we can simply create a new share with an ID of 1256472 (so that create_point will return 0 and the share (0, secret) will be created).
$ nc AAA.BBB.CCC.DDD 55555
# [...]
1--Get the secret
2--Create new share
3--Exit
2
Enter your new share ID number :
1256472
1--Get the secret
2--Create new share
3--Exit
1
Okey, I'll share my secret with you : ECTF{WhEn_Mari0_W4nTs_To_Share}
Square Mario
While your were playing mario you found those 2 files, please find a way to decrypt them!
We’re given the following Python source code and output.
from Cryptodome.Util.number import bytes_to_long, getPrime
FLAG = open("flag.txt", "rb").read()
def square(x, m, n=5):
for _ in range(n):
x = pow(x, 2, m)
return x
def encrypt(flag):
p = getPrime(1024)
x = square(bytes_to_long(flag), p)
return (x, p)
(X, P) = encrypt(FLAG)
print("X =", X)
print("P =", P)
#X = 65567906504707001412451629380105920336765646875361267702392177389975788601105395041727677960531694075172671673825534663404646697891108703571487714370157822718820383082425198093895770956243411362693772945081793898878903728208012455412074768926681046872056914503511397246233621635857399405920045067524154745070
#P = 126419363563553215091646637314497854198261588036382180640893319022541659598027100223880826774071842687403022731516037083359599621020514054284689589273154786802636897124000251303336410620757242551598664334914370563254424053331496101404625326501881265007678722518697084930349838815078675100361385273502712083087
The flag is converted to a long before being squared 5 times modulo P (so X = flag ** 32 % P).
Thus we can simply recursively take the modular square root of X (and -X % P, as there are two roots) using the Tonneli-Shanks algorithm.
from libnum import n2s
def mod_sqrt(a, p):
def legendre_symbol(a, p):
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return p
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1
n = 2
while legendre_symbol(n, p) != -1:
n += 1
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
X = 65567906504707001412451629380105920336765646875361267702392177389975788601105395041727677960531694075172671673825534663404646697891108703571487714370157822718820383082425198093895770956243411362693772945081793898878903728208012455412074768926681046872056914503511397246233621635857399405920045067524154745070
P = 126419363563553215091646637314497854198261588036382180640893319022541659598027100223880826774071842687403022731516037083359599621020514054284689589273154786802636897124000251303336410620757242551598664334914370563254424053331496101404625326501881265007678722518697084930349838815078675100361385273502712083087
X = [X]
for _ in range(5):
X = [mod_sqrt(x, P) for x in X] + [(-mod_sqrt(x, P))%P for x in X]
for x in X:
if n2s(x).startswith(b'ECTF'):
print(n2s(x))
# b'ECTF{7c2fc5155efcebd7264625c8f4e4db1aea7d489515368cf1626b3d6dffc01e63}'
Toad Sauce
README.md:
It's not a surprise, Toad loves *censored* sauce !
He tried to create his own *censored* sauce by mixing 6 of his favorite ingredients.
Retrieve the secret recipe !
flag.enc:
QVWQ{M0lP_Ld_MUj1gj_Fh_Na0n}
From the challenge prompt, we can guess that the flag was encrypted with a Cesar cipher with 6 different and repeating shifts. Since we have the crib ‘ECTF’ we can calculate the first 4 shifts (out of 6).
from string import ascii_uppercase as up
from string import ascii_lowercase as lo
a = 'QVWQ{M0lP_Ld_MUj1gj_Fh_Na0n}'
b = 'ECTF'
key = [ord(a_) - ord(b_) for a_,b_ in zip(a,b)] + [0, 0]
def cesar(a, key):
arr = []
for a_,k in zip(a,key):
if a_ in up:
arr.append(up[ (up.index(a_) - k) % 26])
elif a_ in lo:
arr.append(lo[ (lo.index(a_) - k) % 26])
else:
arr.append(a_)
return arr
print(''.join(cesar(a, key * 100)))
# ECTF{M0sM_Ld_TRy1gx_Cw_No0k}
As I have no respect for crypto challenges where we’re only given a flag.enc file, we can guess the rest of the flag: ECTF{T0aD_Is_TRy1ng_To_Co0k}.
Luigi Ascent
README.md:
I heard that Luigi wanted to touch the Scy !
flag.enc:
ELgU0l}C30cm0~Tt_Heu~FsT__d~{_oSCs~
“Scy” hints that the flag was encrypted with a scytale cipher. Using an online decryptor we can try all numbers of columns until we get the flag: ECTF{L3ts_g0_ToUcH_S0me_Cl0uds}.