# Seccon CTF 2024 Quals
I participated in this CTF with team `ADA INDONESIA COY` which was a merger of multiple Indonesian teams. This is a major success as we managed to secured 5th place in the quals, and got to proceed to the finals! Huge props to my teamates who carried hard on the other categories. I personally worked on Cryptography challenges, and this is a writeup of the three challenges we solved.

## reiwa_rot13
This challenge is a fairly simply RSA challenge, where we are given two ciphertexts whose plaintext are ROT13 transformations of each other.

from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

This immediately signals the Franklin Reiter attack as both plaintext are related by some known function. The only issue is that we do not exactly know for each character whether it is rotated by increasing, (`A -> N`), or decreasing (`N -> A`) its value. As there are only two possibilities and ten characters, we can simply brute force this.

### Solver

from Crypto.Util.number import *
import hashlib
from Crypto.Cipher import AES
from libnum import n2s
from tqdm import tqdm

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

def gcdp(a, b): 
    while b:
        a, b = b, a % b
    return a.monic()

def franklinreiter(w):
    P.<X> = PolynomialRing(Zmod(n))
    g1 = (X + w)^137 - c1
    g2 = (X)^137 - c2
    result = gcdp(g1, g2).coefficients()
    return -result[0]

def gen(cur = 0, idx = 0):
    if idx == 10:
        yield cur
        return
    cur = cur << 8
    yield from gen(cur + 13, idx + 1)
    yield from gen(cur - 13, idx + 1)

for diff in tqdm(gen()):
    res = franklinreiter(diff)
    key_g = n2s(int(res))
    if len(key_g) == 10:
        key = n2s(int(res + diff))
        key = hashlib.sha256(key).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        print("encyprted_flag = ", cipher.decrypt(encyprted_flag))

## dual_summon
This challenge revolves around creating a collision on the tag of the AES-GCM encryption scheme. The only twist is that we need to create a collision on two different AES-GCM cipher keys using the same 16 bytes plaintext.

from Crypto.Cipher import AES
import secrets
import os
import signal

signal.alarm(300)

flag = os.getenv('flag', "SECCON{sample}")

keys = [secrets.token_bytes(16) for _ in range(2)]
nonce = secrets.token_bytes(16)

def summon(number, plaintext):
    assert len(plaintext) == 16
    aes = AES.new(key=keys[number-1], mode=AES.MODE_GCM, nonce=nonce)
    ct, tag = aes.encrypt_and_digest(plaintext)
    return ct, tag

# When you can exec dual_summon, you will win
def dual_summon(plaintext):
    assert len(plaintext) == 16
    aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
    aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
    ct1, tag1 = aes1.encrypt_and_digest(plaintext)
    ct2, tag2 = aes2.encrypt_and_digest(plaintext)
    # When using dual_summon you have to match tags
    assert tag1 == tag2

print("Welcome to summoning circle. Can you dual summon?")
for _ in range(10):
    mode = int(input("[1] summon, [2] dual summon >"))
    if mode == 1:
        number = int(input("summon number (1 or 2) >"))
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        ct, tag = summon(number, name)
        print(f"monster name = [---filtered---]")
        print(f"tag(hex) = {tag.hex()}")

    if mode == 2:
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        dual_summon(name)
        print("Wow! you could exec dual_summon! you are master of summoner!")
        print(flag)

Looking at the GCM scheme, we see that for one block of plaintext the tags are calculcated with the formula `tag = E(counter_0) + H * (l + H * (E(counter_1) + pt))` where `E` is the encryption function and `H` is the authentication polynomial derived from the encryption key. Note that this calculation is done modulo some irreducible polynomial. Now, notice that if we have tags for `pt1` and `pt2`, the difference of those tags would just be `delta_tag = H * H * (pt1 - pt2)` as all other values used in calculating the tags are constant. Thus, given two tags from each GCM cipher (with different keys), we could obtain the value of `H1 ** 2` and `H2 ** 2` respectively. Using this, we can easly calculate how much we need to increase the plaintext such that the tags are the same. Note that when increasing the value of the plaintext by one, `tag1` would increase by `H1 ** 2` and `tag2` would increase by `H2 ** 2`. Thus, subtracting and dividing by this would give us the appropriate plaintext to create a collision.

### Solver

from azunyan.conn import remote, process
from libnum import n2s, s2n

#r = process(['python3', 'server.py'])#, level='debug')
r = remote('dual-summon.seccon.games', int(2222))

BF.<X> = GF(2)[]
FF.<A> = GF(2 ^ 128, modulus=X ^ 128 + X ^ 7 + X ^ 2 + X + 1)
pt1 = b'\x00' * 16
pt2 = b'\x80' + b'\x00' * 15

def bytes2ele(data):
    integer = s2n(data)
    res = 0
    for i in range(128):
        # rightmost bit is x127
        res += (integer & 1) * (A ^ (127 - i))
        integer >>= 1
    return res

def ele2bytes(element):
    integer = element.integer_representation()
    res = 0
    for i in range(128):
        res = (res << 1) + (integer & 1)
        integer >>= 1
    return n2s(int(res))

def summon(choice: int, data: bytes):
    r.sendlineafter(b'>', b'1')
    r.sendlineafter(b'>', str(choice).encode())
    r.sendlineafter(b'>', data.hex().encode())
    r.recvuntil(b'tag(hex) = ')
    return r.recvtype(bytes)

def win(data: bytes):
    r.sendlineafter(b'>', b'2')
    r.sendlineafter(b'>', data.hex().encode())
    r.interactive()

tag1_1 = summon(1, pt1)
tag1_2 = summon(1, pt2)
tag2_1 = summon(2, pt1)
tag2_2 = summon(2, pt2)

h1 = bytes2ele(tag1_2) + bytes2ele(tag1_1)
h2 = bytes2ele(tag2_2) + bytes2ele(tag2_1)

dh = h1 - h2
dt = bytes2ele(tag2_1) + bytes2ele(tag1_1)
x = dt / dh

payload = ele2bytes(x)
win(payload)

### Tidal wave
This challenge mainly consists of two parts, recovering some value alpha given some obsfucation through polynomials, and recovering keys obsfucated with some matrix multiplication.

import random
from Crypto.Util.number import getPrime
import secrets
from flag import flag

def get_Rrandom(R):
    return secrets.randbelow(int(R.order()))

def make_G(R, alphas):
    mat = []
    for i in range(k):
        row = []
        for j in range(n):
            row.append(alphas[j]^i)
        mat.append(row)
    mat = matrix(R, mat)
    return mat

def split_p(R, p, prime_bit_length, length):
    step = ceil(prime_bit_length/length)
    res = []
    while p > 0:
        res.append(ZZ(p % (2**step)))
        p >>= step
    return vector(R, res)

def make_random_vector(R, length):
    error_range = 2^1000
    res = []
    for _ in range(length):
        res.append(R(secrets.randbelow(int(error_range))))
    return vector(R, res)

def make_random_vector2(R, length):
    error_cnt = 28
    res = vector(R, length)
    error_pos = random.sample(range(length), error_cnt)
    for i in error_pos[:error_cnt//2]:
        res[i] = get_Rrandom(R)*p
    for i in error_pos[error_cnt//2:]:
        res[i] = get_Rrandom(R)*q
    return vector(R, res)

n, k = 36, 8
prime_bit_length = 512
p = getPrime(prime_bit_length)
q = getPrime(prime_bit_length)
N = p*q
R = Zmod(N)

alphas = vector(R, [get_Rrandom(R) for _ in range(n)])
G = make_G(R, alphas)

dets = [G.submatrix(0,i*k-i,8,8).det() for i in range(5)]

double_alphas = list(map(lambda x: x^2, alphas))
alpha_sum_rsa = R(sum(alphas))^65537

keyvec = vector(R, [get_Rrandom(R) for _ in range(k)])
pvec = split_p(R, p, prime_bit_length, k)

p_encoded = pvec*G + make_random_vector(R, n)
key_encoded = keyvec*G + make_random_vector2(R, n)

print(f"{N=}")
print(f"{dets=}")
print(f"{double_alphas=}")
print(f"{alpha_sum_rsa=}")
print(f"{p_encoded=}")
print(f"{key_encoded=}")

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
encrypted_flag = cipher.encrypt(pad(flag, AES.block_size))
print(f"{encrypted_flag=}")

### Recovering alpha

Note that we have a lot of equations surrounding alpha, e.g. the value of `a_i ** 2 (mod n)`, the values of `det(G)`, and the value `sum(alpha)^65537 (mod n)`. Considering that the matrix `G` is just composed of powers of `a_i`, we can simplify each element to be either constant or a multiple of `a_i`. Furthermore, because deteminants of `G` are taken in sizes `8 x 8`, the polynomial formed from the deteminant of `G` has at most degree `8`. This is still small enough for Groebner Basis, and trying this out, we obtain interesting results (cr: **Wrth** & **swusjask**).

def gen_M(x, double_alphas):
    return matrix(
        P,
        [
            [1 for _ in range(8)],
            [x[i] for i in range(8)],
            [double_alpha for double_alpha in double_alphas],
            [x[i] * double_alpha for i, double_alpha in zip(range(8), double_alphas)],
            [double_alpha ** 2 for double_alpha in double_alphas],
            [
                x[i] * double_alpha ** 2
                for i, double_alpha in zip(range(8), double_alphas)
            ],
            [double_alpha ** 3 for double_alpha in double_alphas],
            [
                x[i] * double_alpha ** 3
                for i, double_alpha in zip(range(8), double_alphas)
            ],
        ],
    )
    
def make_G(R, alphas):
    mat = []
    for i in range(k):
        row = []
        for j in range(n):
            row.append(alphas[j]**i)
        mat.append(row)
    mat = matrix(R, mat)
    return mat

f_list = []
for i in range(5):
    M = gen_M(x[i*(k-1):i*(k-1)+8], double_alphas[i*(k-1):i*(k-1)+8])

    f_list.append(M.det() - dets[i])
for i,xs in enumerate(x):
    f_list.append(xs**2 - double_alphas[i])

I = P.ideal(f_list)
grob = I.groebner_basis()


We obtain monomials in the form of `a_i + k * a_35`. To recover `a_35`, we can use the given sum of alphas. Knowing `rsa_sum = sum(a_i) ** 65537`, we can substitute each `a_i` in the form of `k_i * a_35` and for some `A`, obtain `rsa_sum = A * (a_35) ** 65537`. As we know also the value of `a_35 ** 2`, we can recover `a_35` by dividing (inverse modulo) `a_35 ** 65537` by `a_35 ** 2` until we are left with degree one.

subconst = []
for i in range(1, 36):
    subconst.append(-grob[i].coefficients()[1])
    
sumx = sum(x)

for i in range(35):
    sumx = sumx.subs({x[i]: subconst[i]*x[35]})
    
alpha_sum_rsax = sumx**65537

resultx35 = alpha_sum_rsa * alpha_sum_rsax.coefficients()[0]**-1

x35 = resultx35 * R(double_alphas[35]**(65537//2))**-1

### Recovering keyvec
Knowing alpha, we can reconstruct `G` easily. Now, take note of how `key_encoded` is calculated.

key_encoded = keyvec*G + make_random_vector2(R, n)

def make_random_vector2(R, length):
    error_cnt = 28
    res = vector(R, length)
    error_pos = random.sample(range(length), error_cnt)
    for i in error_pos[:error_cnt//2]:
        res[i] = get_Rrandom(R)*p
    for i in error_pos[error_cnt//2:]:
        res[i] = get_Rrandom(R)*q
    return vector(R, res)

Note that the error vector constructed by `make_random_vector2` has exactly eight zero entires, and that the length or the original `keyvec` is also of length eight. As such, if we can guess which eight entires are the original contain the original value of `keyvec * G`, we can recover `keyvec` through by solving the equation system. Note that the number of possibilities of the positions of the entries are `36 C 8 = 30260340` or about 30 million, and we felt that this was still small enough to brute force. In retrospect, this is probably not the cleanest way to solve it.

choices = list(combinations(choices, 8))
total = len(choices)
block_size = total // block_cnt
choices = choices[block * block_size: (block + 1) * block_size]

for ch in tqdm(choices):
    H = G.matrix_from_columns(ch)
    key_choices = [key_encoded[i] for i in ch]
    key_choices = vector(R, key_choices)
    
    guess_keyvec = H.solve_left(key_choices)
    key = hashlib.sha256(str(guess_keyvec).encode()).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    encrypted_flag = cipher.decrypt(encrypted_flag)
    if b'SECCON' in encrypted_flag:
        print(encrypted_flag)
        exit(0)

After running this for about 20 minutes (with multiple threads and PCs), we discover that the winning combination is (0, 7, 11, 15, 22, 26, 31, 34), and we discover the flag.

### Solver

from sage.all import *
from itertools import combinations
from tqdm import tqdm
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
                    

f = open('output.txt').readlines()

N= 0
double_alphas = []
dets = []
alpha_sum_rsa = 0
p_encoded = []
key_encoded = []
n = 36
k = 8

for line in f:
    exec(line)
    
p = 13063745862781294589547896930952928867567164583215526040684813499782622799740291421111907000771263532192148557705806567586876208831387558514840698244078507

print(N % p)

R = Zmod(N)
P = PolynomialRing(R, 36, "x")
x = P.gens()

def gen_M(x, double_alphas):
    return matrix(
        P,
        [
            [1 for _ in range(8)],
            [x[i] for i in range(8)],
            [double_alpha for double_alpha in double_alphas],
            [x[i] * double_alpha for i, double_alpha in zip(range(8), double_alphas)],
            [double_alpha ** 2 for double_alpha in double_alphas],
            [
                x[i] * double_alpha ** 2
                for i, double_alpha in zip(range(8), double_alphas)
            ],
            [double_alpha ** 3 for double_alpha in double_alphas],
            [
                x[i] * double_alpha ** 3
                for i, double_alpha in zip(range(8), double_alphas)
            ],
        ],
    )
    
def make_G(R, alphas):
    mat = []
    for i in range(k):
        row = []
        for j in range(n):
            row.append(alphas[j]**i)
        mat.append(row)
    mat = matrix(R, mat)
    return mat

f_list = []
for i in range(5):
    M = gen_M(x[i*(k-1):i*(k-1)+8], double_alphas[i*(k-1):i*(k-1)+8])

    f_list.append(M.det() - dets[i])
for i,xs in enumerate(x):
    f_list.append(xs**2 - double_alphas[i])

I = P.ideal(f_list)
grob = I.groebner_basis()

print("Done first grob")
subconst = []
for i in range(1, 36):
    subconst.append(-grob[i].coefficients()[1])
    
sumx = sum(x)

for i in range(35):
    sumx = sumx.subs({x[i]: subconst[i]*x[35]})
    
alpha_sum_rsax = sumx**65537

resultx35 = alpha_sum_rsa * alpha_sum_rsax.coefficients()[0]**-1

def polynomial_gcd(f1, f2):
    while f2:
        f1, f2 = f2, f1 % f2
    return f1.monic()

f = x[35]**65537 - resultx35
g = x[35]**2 - double_alphas[35]

x35 = resultx35 * R(double_alphas[35]**(65537//2))**-1

f_list.append(x[35] - x35)
I = P.ideal(f_list)
grob = I.groebner_basis()

alphas = []
for i in range(36):
    alphas.append(-grob[i].coefficients()[1])

print("Done second grob")
G = make_G(R, alphas)

key_encoded = vector(R, key_encoded)

choices = [i for i in range(36)]

import sys
block = int(sys.argv[1])
block_cnt = 8
print(f'Block: {int(block)}/8')
choices = list(combinations(choices, 8))
total = len(choices)
block_size = total // block_cnt
choices = choices[block * block_size: (block + 1) * block_size]

for ch in tqdm(choices):
    H = G.matrix_from_columns(ch)
    key_choices = [key_encoded[i] for i in ch]
    key_choices = vector(R, key_choices)
    
    guess_keyvec = H.solve_left(key_choices)
    key = hashlib.sha256(str(guess_keyvec).encode()).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    encrypted_flag = cipher.decrypt(encrypted_flag)
    if b'SECCON' in encrypted_flag:
        print(encrypted_flag)
        exit(0)