Securinets CTF Quals 2022 Writeup

Mon Apr 11 2022

I participated Securinets CTF Quals 2022 as a member of WreckTheLine. The results were 3rd/255!

Here is my writeup for challs I solved.

Crypto

Sherry

9 solves

sherry.sage
#!/usr/bin/env sage
from Crypto.Util.number import *
import random, sys, json

FLAG = "Securinets{REDACTED}"

def getRandomElement(F, deg):
        return F.random_element(degree=deg)

def polyToList(p):
        return p.list()

def listToPoly(F, l):
        return sum(F(c*x^i) for i, c in enumerate(l))

def polySum(p1, p2):
        if p1.parent() == p2.parent():
                return p1 + p2
        else:
                return p1 + p1.parent()(p2)

def getShare(g, secret):
        y = g^secret
        e = getRandomElement(PolynomialRing(GF(getPrime(256)), "x"), 10)
        s = polySum(y, e)
        share = polyToList(s)
        return share


if __name__ == '__main__':
        print(f"Welcome to Black Organization.\nTo join us, you have to guess our secret.\n")

        p = getStrongPrime(512)
        P = PolynomialRing(GF(p), "x")
        x = P.gen()
        N = getRandomElement(P, 10)
        Q.<x> = P.quotient_ring(N^2)

        G = Q(getRandomElement(P, 10))
        secret = random.randint(1, p-1)
        pub = G^secret

        params = {"N": polyToList(N), "pub": polyToList(pub), "G": polyToList(G), "p":p}
        print(f"{params}\n")

        for _ in range(5):
                try:
                        inp = json.loads(input("Your guess : "))
                        if 'g' not in inp or 's' not in inp:
                                raise ValueError("You must send a generator and a secret.")

                        g = listToPoly(Q, inp['g'])
                        s = int(inp['s'], 16) % p

                        if g^s == pub:
                                if s != secret:
                                        print(f"Don't cheat! :)")
                                        continue
                                print(f'From now, your name will be Sherry! Here is your flag : {FLAG}')
                                sys.exit()

                        else:
                                share = {'share': getShare(g, secret)}
                                print(f'{share}\n')

                except Exception as e:
                        print(e)
                        sys.exit()

Let secret be $x$ . getSecret calculates $g^x + e_i \mod N^2$ where $e_i (0 \le i < 4)$ is relatively smaller polynomial than other values. When you choose $g = N + 1$ , you can get $xN + 1 + e_i \mod N^2$ . Let this be $y_i$ . Since you can get 4 shares and each share has 11 terms, you have $4 \times 11 = 44$ equations: $xN_j + \delta_{j0} + e_{ij} - y_{ij} = 0 \mod p$ , where $N_j, e_{ij}, y_{ij}$ is the coefficient of $x^j$ in $N, e_i, y_i$ , respectively and $\delta_{j0}$ is a Kronecker delta. $x$ can be found as CVP. You can use rkm0959's solver to solve this.

solve.sage
import json

from Crypto.Util.number import long_to_bytes
from pwn import remote

io = remote("20.233.7.174", 4869)
io.recvuntil(b"secret.\n\n")
data = json.loads(io.recvline().strip().decode().replace("'", "\""))
print(data)

N = data["N"]
pub = data["pub"]
G = data["G"]
p = data["p"]

def get_share(g: list[int], s: int):
    data = {}
    data["g"] = g
    data["s"] = long_to_bytes(s).hex()
    io.sendlineafter(b"Your guess : ", json.dumps(data).encode())
    ret = io.recvline().decode().strip()
    if "From" in ret:
        return ret
    else:
        return json.loads(ret.replace("'", "\""))


shares = [get_share([N[0]+int(1)] + N[1:], 0)["share"] for _ in range(4)]

M = 4
# [k0-0, k0-1, ..., k0-10, k1-0, k1-1, ..., k1-10, ..., k3-10, 1, x]
mat = matrix(ZZ, 11 * M + 2, 11 * M + 2)
for i in range(11 * M):
    mat[i, i] = p
for i in range(M):
    share = shares[i]
    for j in range(11):
        if j == 0:
            mat[11 * M, 11 * i + j] = share[j] - 1
        else:
            mat[11 * M, 11 * i + j] = share[j]
        mat[11 * M + 1, 11 * i + j] = -N[j]
mat[11 * M, 11 * M] = 1
mat[11 * M + 1, 11 * M + 1] = 1
lb = [0] * 11 * M + [1] + [0]
ub = [2 ** 256] * 11 * M + [1] + [p]

res = solve(mat, lb, ub)
secret = res[2][-1]

print(get_share(G, int(secret)))

Securinets{Why_s0_ch41_0f_c0mb1n1ng_b1n0m14l_w1th_LLL_m4_b0y!}

Matrand

13 solves

matrand.sage
from Crypto.Util.number import bytes_to_long, getStrongPrime
from Crypto.Util.Padding import pad
import random

FLAG = b"Securinets{REDACTED}"
FLAG = FLAG.lstrip(b"Securinets{").rstrip(b"}")
assert len(FLAG)*8 == 392

class Random():
	def __init__(self, p, taps):
		self.p = p
		self.taps = taps
		self.seed_x = [random.randrange(1, self.p-1) for _ in range(3)]

	def reseed(self, x):
		self.seed_x = self.seed_x[1:] + [x]

	def next(self):
		x = (self.taps[0]*self.seed_x[0] + self.taps[1]*self.seed_x[1] + self.taps[2]*self.seed_x[2]) % p
		self.reseed(x)
		return x

p = 0xfa667a4f92149261c2d9a7d1e43d5a83a4342d880b6ddfbe40072d3f439eb917a2815564090fef8087fbdfeb51e9977603ad91a3317ec3754554f8da472747c5
taps = [random.randrange(1, p-1) for _ in range(3)]
R = Random(p, taps)

w = []
msgs = [pad(FLAG, 64), os.urandom(64)]
for msg in msgs:
	v = vector(GF(p), [bytes_to_long(msg[i:i+16]) for i in range(0, len(msg), 16)])
	while True:
		M = Matrix(GF(p), [[R.next() for i in range(4)] for j in range(4)])
		if M.det() == 0:
			break
	w.append(list(M*v))

print(f"{msgs[1].hex()}")
print(f"taps = {taps}")
print(f"w = {w}")

Let taps be $t_0, t_1, t_2$ and initial seed_x be $s_0, s_1, s_2$ . After Random.next is called, its seed_x will be $s_1, s_2, t_0s_0 + t_1s_1 + t_2s_2 \mod p$ and it returns the last element in seed_x. This will be done repeatedly by 16 times.

Since both of msgs[1] and w[1] are known, you can find initial (after the first msgs[0] encryption) seed $s_0, s_1, s_2$ which will generate $M$ such that $Mv_1 = w_1$ , where $v_1$ and $w_1$ is made from msgs[1] and w[1] respectively.

from binascii import unhexlify

from Crypto.Util.number import bytes_to_long

msgs1 = unhexlify("52bdab087cbc26016605c2ed9db568b1e8b9d32d88f3ec908d45881c8ef3f9ed3a5f7a0ab4c254aa1d1fcba7efb4ed5b962c3273e79329e7bc544139bfe316f0")
taps = [1842210300811086273065827398759743912915718658444224465833586808197511829816340388182142455674251678020695260023383508160051592177696059916602556617963171, 2468822200728551209978345472877806860090591869287755448409462559548289371325308801472245606715062680443066084045095666891750193076456795735144192061617484, 4441995047487466535676864584036085081002851633641768883198660437261418643709913468961853355698553714794339200444086551867857078306412444322744910169805671]
w = [[3713642445895001428522512847062805623796418435672963931169745954211722614199382461272816960658234728506695568663825011161019433384185650183379138191176952, 7144559904171643719023967766036532926212453726703639479660938469398898061205228419047409252315693998357198138203179112006934467513277629283773755181624025, 9730898858135619977492473744493893875525167103348228292628298031856712518300703886060686037505807623372649321646185736641320733729944604667638331467236806, 982761183860510181104803682295701042303749583243542307006835875249160141536101505661498943433784394682201130252172729991259686246608238009279551943777614], [13087135870271729162495373447284077623624591342449677698229062125951074963352559438665132843906275381573072190198250600718038662358301774413182065139333573, 7900300493165963608255417079749358977108350304314866134915275476436819439073074361551261380869306728436525131736711153565043240813730335376674981201555006, 8064883856663750994554771494087385774263666022299201562162567711297173383942050919419925496864660025834632951286325411061789494937378370183433838519883571, 1122715781418837045743113509478705525298638257591950512552224446895014267316526874337404794082924614806288289416358939243616265915863814885517143322022320]]
p = 0xfa667a4f92149261c2d9a7d1e43d5a83a4342d880b6ddfbe40072d3f439eb917a2815564090fef8087fbdfeb51e9977603ad91a3317ec3754554f8da472747c5

PR.<s0, s1, s2> = PolynomialRing(GF(p))

def next(s_list):
    x = taps[0] * s_list[0] + taps[1] * s_list[1] + taps[2] * s_list[2]
    return [s_list[1], s_list[2], x]

s_list = [s0, s1, s2]
M = []
for _ in range(4):
    row = []
    for _ in range(4):
        s_list = next(s_list)
        row.append(s_list[-1])
    M.append(row)

v = list(map(bytes_to_long, [msgs1[i: i+16] for i in range(0, 64, 16)]))
polys = []
for i in range(4):
    poly = PR(0)
    for j in range(4):
        poly += M[i][j] * v[j]
    poly -= w[1][i]
    polys.append(poly)

I = PR.ideal(polys)
print(I.variety())

[{s0: 1930252392776308382855743234159540438588931061329348447530508147143445725393369743246362437615497885641363736630710222657410627996919055751804867966457482, s1: 3449158437127560743382682490714044130504481699174703113647429560657334421538185255875160066385964903880611375106671234105501619000175684253778142872216717, s2: 12320225976777645971110537903319202605348092585756234791504499089975050639177671716812315801040329914568236111865320431811630512261838288065151630247911025}]

Since Random.next is reversible, you can find $M$ used for the encryption of FLAG.

s0 = 1930252392776308382855743234159540438588931061329348447530508147143445725393369743246362437615497885641363736630710222657410627996919055751804867966457482
s1 = 3449158437127560743382682490714044130504481699174703113647429560657334421538185255875160066385964903880611375106671234105501619000175684253778142872216717
s2 = 12320225976777645971110537903319202605348092585756234791504499089975050639177671716812315801040329914568236111865320431811630512261838288065151630247911025

def prev(s_list):
    x = (s_list[2] - taps[1] * s_list[0] - taps[2] * s_list[1]) * pow(taps[0], -1, p)
    return [x, s_list[0], s_list[1]]


s_list = [s0, s1, s2]
M = []
s_list = next(s_list)  # for simplicity
for _ in range(4):
    row = []
    for _ in range(4):
        s_list = prev(s_list)
        row.append(s_list[-1])
    M.append(row[::-1])
M = M[::-1]
M = matrix(GF(p), M)
assert M.det() == 0

The small problem is that $M$ is not full rank because M.det() == 0. But happily (maybe intentionally) the len(FLAG) is $49 = 16 \times 3 + 1$ . Therefore the last element in $v_0$ has only less patterns than 256, \x00\x0f\x0f...\x0f, \x01\x0f\x0f...\x0f, ..., \xff\x0f\x0f...\x0f. You can try each of them by brute force and find exact $v_0$ by seeing the decrypted message is printable one (or by seeing the decrypted message is the shortest).

from Crypto.Util.number import long_to_bytes

k = M.right_kernel().basis()[0]
assert (M * k).list() == [0] * 4
t = vector(GF(p), w[0])
v_base = M.solve_right(t)

for i in range(32, 128):
    target = i * 256**15 + bytes_to_long(b"\x0f"*15)
    tmp = pow(k[3], -1, p) * target
    v = v_base + tmp * k
    assert v[3] == target
    assert (M * v).list() == w[0]
    msg = b""
    for j in range(4):
        msg += long_to_bytes(int(v[j]))
    print(len(msg), msg)

Securinets{If_y0u_4r3_n0t_c4r3ful_th3n_t3ll_m3_why_s0_p4d???}

Well

14 solves

well.sage
import random, hashlib, os, sys
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

FLAG = b"Securinets{REDACTED}"

def gen_key(P, Q):
    seed = P.weil_pairing(Q, P.order())
    return hashlib.sha256(str(seed).encode()).digest()[:16]

e1, e2 = 19, 61
l1, l2 = 2, 3
p = l1^e1*l2^e2 - 1
_.<x> = PolynomialRing(GF(p))
Q.<i> = GF(p^2, modulus=x^2 + 1)

E = EllipticCurve(Q, [1, 0])
assert E.is_supersingular()

K = E(0)
while (l1^(e1-1))*K == 0:
	K = l2^e2 * E.random_point()
φ = E.isogeny(K)

while True:
	G1 = E.random_point()
	G2 = E.random_point()
	φ_G1 = φ(G1)
	φ_G2 = φ(G2)
	if φ_G1.order() == φ_G2.order():
		break

key = gen_key(φ_G1, φ_G2)
iv = os.urandom(16)
aes = AES.new(key, AES.MODE_CBC, iv)
encrypted_flag = aes.encrypt(pad(FLAG, 16))

print(f"G1 : {G1.xy()}")
print(f"G2 : {G2.xy()}")
print(f"Encrypted flag : {(iv + encrypted_flag).hex()}")

~~Since isogeny is deterministically defined by what torsion the points are, $\phi$ has no randomness in this chall. Therefore you can regenerate φ_G1 and φ_G2 and AES's key. That's all.~~ I found that it's not true. Sometimes φ_G1.order() != φ_G2.order(). So my solution was finding correct φ by brute force. Sorry for that.

For those who are not familiar with SIKE (Supersingular Isogeny Key Exchange), this tutorial is very informative.

solve.sage
import hashlib
from binascii import unhexlify

from Crypto.Cipher import AES


e1, e2 = 19, 61
l1, l2 = 2, 3
p = l1^e1*l2^e2 - 1
_.<x> = PolynomialRing(GF(p))
Q.<i> = GF(p^2, modulus=x^2 + 1)
E = EllipticCurve(Q, [1, 0])
assert E.is_supersingular()


enc = unhexlify("5238b0bc552cace82eb8720f6bee2d152ed0c3a45d3fe86f7d904df9efa31b40eb2284c87e73a5e2600c844372b8b7420da2722455581570bf18a8ef22280b940ba69aec87178411623fa33b834d7c69")
iv, enc = enc[:16], enc[16:]
G1 = E(34735918084090202897593769666415912*i + 53482232157237035307100327428524263, 48716523247512551581211337754377626*i + 18469114223967347488924301515919074)
G2 = E(6186860115142711551318211085390795*i + 65490251252288585102613221918526955, 54848282634693884763474278364486267*i + 60565150582625553764803863462597187)

K = E(0)
while (l1^(e1-1))*K == 0:
    K = l2^e2 * E.random_point()
phi = E.isogeny(K)

phi_G1 = phi(G1)
phi_G2 = phi(G2)
assert phi_G1.order() == phi_G2.order()


def gen_key(P, Q):
    seed = P.weil_pairing(Q, P.order())
    return hashlib.sha256(str(seed).encode()).digest()[:16]


key = gen_key(phi_G1, phi_G2)
aes = AES.new(key, AES.MODE_CBC, iv)
print(aes.decrypt(enc))

Securinets{W31l_p41r1ng_0r_w1ll_sm1th_wh4t_d0_y0u_pr3f3r?}

AES2

19 solves

aes-2.py
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os, sys, hashlib, random

FLAG = b"Securinets{REDACTED}"

key, iv1, iv2 = [os.urandom(16) for _ in range(3)]

def xor(a, b):
	return bytes(i ^ j for i, j in zip(a, b))

def get_token(msg, iv1, iv2):
	if len(msg) % 16 != 0:
		msg = pad(msg, 16)
	aes = AES.new(key, AES.MODE_ECB)
	blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]
	enc = b""
	tmp1 = iv1
	tmp2 = iv2
	for block in blocks:
		tmp = aes.encrypt(xor(block, tmp1))
		_tmp = aes.encrypt(xor(tmp, tmp2))
		enc += _tmp
		tmp1 = _tmp
		tmp2 = tmp
	return enc

def proof(msg):
	res = b"\x00"*16
	for i in range(0, len(msg), 16):
		res = xor(res, msg[i:i+16])
	return hashlib.sha256(res).digest()


if __name__ == "__main__":
	alice_username = os.urandom(32)
	alice_token = get_token(alice_username, iv1, iv2)
	print(f"Alice's creds : {alice_username.hex()} -> {alice_token.hex()}\n")

	while True:
		try:
			username = bytes.fromhex(input("Username : "))
			token = get_token(username, iv1, iv2)
			print(f"Your creds : {username.hex()} -> {token.hex()}")

			if proof(token) == proof(alice_token):
				if token == alice_token:
					print(f"You are not Alice!")
					sys.exit()
				else:
					print(f"Hey Alice! Here is your flag {FLAG}")
					sys.exit()	
			else:
				print("Try again!\n")
		except Exception as e:
			print(e)
			print("Invalid input.\n")

Let $m_i$ be i-th block of username, which is input of get_token, and $c_i$ be i-th block of token, which is output of get_token. You are given $m_1, m_2, c_1, c_2$ (username and token) and should find another username which will generate token such that proof(token) == proof(alice_token) and token != alice_token. Since proof calculates xor of each 16 bytes blocks, the 64 bytes username such that get_token(username) is $c_1, c_2, c_3, c_3$ , because $c_1 \oplus c_2 \oplus c_3 \oplus c_3 = c_1 \oplus c_2$ . Looking carefully how get_token works, you can choose $m_2 \oplus c_1 \oplus c_2, m_2 \oplus c_1 \oplus c_3$ as $m_3, m_4$ to generate $c_1, c_2, c_3, c_3$ . It's shown as follows:

In 3rd block's encryption, the input of the first AES is $m_2 \oplus c_1$ . Let the output be $x = \mathrm{AES}_1(m_2 \oplus c_1)$ . Then the input of the second AES is $0$ because tmp2 is also $x$ . Therefore 3rd block of token is $c_3 = \mathrm{AES}_2(0)$ . This holds true when 4th block of input is $m_4 = m_2 \oplus c_1 \oplus c_3$ . So the output of get_token should be $c_1, c_2, c_3, c_3$ .

solve.py
import re
from binascii import unhexlify

from pwn import remote, context, xor

context.log_level = "DEBUG"

io = remote("20.233.7.174", 4870)
io.recvuntil(b"Alice's creds : ")
ret = io.recvline().strip().decode()
username, token = map(unhexlify, re.findall(r"(.*) -> (.*)", ret)[0])

m1 = username[:16]
m2 = username[16:32]
c1 = token[:16]
c2 = token[16:32]
m3 = xor(c1, m2, c2)

io.sendlineafter(b"Username : ", (username + m3).hex())
io.recvuntil(b"Your creds : ")
ret = io.recvline().strip().decode()
_, tmp_token = map(unhexlify, re.findall(r"(.*) -> (.*)", ret)[0])
c3 = tmp_token[32:48]
m4 = xor(c1, m2, c3)
io.sendlineafter(b"Username : ", (username + m3 + m4).hex())
print(io.recvline())
print(io.recvline())

Securinets{r0ll_y0ur_0wn_structur3_4nd_g3t_c0ll1d3d}

Escrime

50 solves

escrime.py
from Crypto.Util.number import getStrongPrime, getPrime, isPrime, bytes_to_long

FLAG = b"Securinets{REDACTED}"

def genPrime(prime):
    while True:
        a = getPrime(256)
        p = 2*prime*a + 1
        if isPrime(p):
            break
    while True:
        b = getPrime(256)
        q = 2*prime*b + 1
        if isPrime(q):
            break
    return p, q

prime = getStrongPrime(512)
p1, q1 = genPrime(prime)
p2, q2 = genPrime(prime)
assert p1 != p2 != q1 != q2

n1 = p1*q1
n2 = p2*q2
e = 65537

m1 = bytes_to_long(FLAG[:len(FLAG)//2])
m2 = bytes_to_long(FLAG[len(FLAG)//2:])

c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)

print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"e = {e}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

Let prime be $r$ . We can describe $p_i = 2a_ir + 1, q_i = 2b_ir + 1$ , where $a_i, b_i$ is i-th $a, b$ , respectively. Then $n_i = 4r^2a_ib_i + 2r(a_i+b_i) + 1$ . Since we have two $n$ , you can know $r$ by calculating gcd of $n_0 - 1$ and $n_1 - 1$ and factoring it. After $r$ is known, since $a_i, b_i$ is relatively smaller than other parameters, you can find $a_i, b_i$ by multivariate Coppersmith's method using like defund's implementation.

solve.sage
from Crypto.Util.number import long_to_bytes


# gcd(n1 - 1, n2 - 1) and factor
r = 12397002878565866184412236037259205021945058505472864688501145731895119789392433217522880454989374040698621943547773164450323280239641723319936790061247301

def find_a_b(n):
    PR.<a, b> = PolynomialRing(Zmod(n))
    f = 4*r**2*a*b + 2*r*(a+b) + 1 - n
    bounds = (2**256, 2**256)
    roots = small_roots(f, bounds)
    a, b = roots[0]
    return a, b

a1, b1 = find_a_b(n1)
a2, b2 = find_a_b(n2)

p1 = 2*r*a1 + 1
q1 = 2*r*b1 + 1
p2 = 2*r*a2 + 1
q2 = 2*r*b2 + 1
phi1 = (p1 - 1) * (q1 - 1)
phi2 = (p2 - 1) * (q2 - 1)
d1 = int(pow(e, -1, phi1))
d2 = int(pow(e, -1, phi2))

print(long_to_bytes(int(pow(c1, d1, n1))) + long_to_bytes(int(pow(c2, d2, n2))))

Securinets{G3n3r4t1ng_pr1m3s_1n_4_sp3c1f1c_f0rm_4lm0st_4lw4ys_3nds_b4dly}