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 xx. getSecret calculates gx+eimodN2g^x + e_i \mod N^2 where ei(0i<4)e_i (0 \le i < 4) is relatively smaller polynomial than other values. When you choose g=N+1g = N + 1, you can get xN+1+eimodN2xN + 1 + e_i \mod N^2. Let this be yiy_i. Since you can get 4 shares and each share has 11 terms, you have 4×11=444 \times 11 = 44 equations: xNj+δj0+eijyij=0modpxN_j + \delta_{j0} + e_{ij} - y_{ij} = 0 \mod p, where Nj,eij,yijN_j, e_{ij}, y_{ij} is the coefficient of xjx^j in N,ei,yiN, e_i, y_i, respectively and δj0\delta_{j0} is a Kronecker delta. xx 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 t0,t1,t2t_0, t_1, t_2 and initial seed_x be s0,s1,s2s_0, s_1, s_2. After Random.next is called, its seed_x will be s1,s2,t0s0+t1s1+t2s2modps_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 s0,s1,s2s_0, s_1, s_2 which will generate MM such that Mv1=w1Mv_1 = w_1, where v1v_1 and w1w_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 MM 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 MM is not full rank because M.det() == 0. But happily (maybe intentionally) the len(FLAG) is 49=16×3+149 = 16 \times 3 + 1. Therefore the last element in v0v_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 v0v_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 mim_i be i-th block of username, which is input of get_token, and cic_i be i-th block of token, which is output of get_token. You are given m1,m2,c1,c2m_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 c1,c2,c3,c3c_1, c_2, c_3, c_3, because c1c2c3c3=c1c2c_1 \oplus c_2 \oplus c_3 \oplus c_3 = c_1 \oplus c_2. Looking carefully how get_token works, you can choose m2c1c2,m2c1c3m_2 \oplus c_1 \oplus c_2, m_2 \oplus c_1 \oplus c_3 as m3,m4m_3, m_4 to generate c1,c2,c3,c3c_1, c_2, c_3, c_3. It's shown as follows:

    In 3rd block's encryption, the input of the first AES is m2c1m_2 \oplus c_1. Let the output be x=AES1(m2c1)x = \mathrm{AES}_1(m_2 \oplus c_1). Then the input of the second AES is 00 because tmp2 is also xx. Therefore 3rd block of token is c3=AES2(0)c_3 = \mathrm{AES}_2(0). This holds true when 4th block of input is m4=m2c1c3m_4 = m_2 \oplus c_1 \oplus c_3. So the output of get_token should be c1,c2,c3,c3c_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 rr. We can describe pi=2air+1,qi=2bir+1p_i = 2a_ir + 1, q_i = 2b_ir + 1, where ai,bia_i, b_i is i-th a,ba, b, respectively. Then ni=4r2aibi+2r(ai+bi)+1n_i = 4r^2a_ib_i + 2r(a_i+b_i) + 1. Since we have two nn, you can know rr by calculating gcd of n01n_0 - 1 and n11n_1 - 1 and factoring it. After rr is known, since ai,bia_i, b_i is relatively smaller than other parameters, you can find ai,bia_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}