🐥

SECCON13 challenges writeup(reiwa_rot13, dual_summon, Tidal wave) EN

2024/11/28に公開

CTF

crypto

tech

reiwa_rot13

description

solves: 127
---
Reiwa is latest era name in Japanese(from 2019). it's latest rot13 challenge!
note: Please submit the flag as it is.

source

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

Solution

The key to solving this challenge lies in the relationship between key and rot13_key.
Since the problem only uses lowercase English letters, each character in the key undergoes the following transformation for ROT13:

Characters in the range $a-m$ are shifted by $+13$ .
Characters in the range $n-z$ are shifted by $-13$ .

As the key is only 10 characters long, there are $2^{10} = 1024$ possible combinations of transformations. These combinations can be enumerated programmatically.

Once the difference between the plaintexts of the two ciphertexts ( $c_1$ and $c_2$ ) is determined, the problem can be solved using Franklin-Reiter's Related Message Attack. This attack allows us to recover the plaintext when the difference between two plaintexts encrypted with the same RSA modulus is known.

dual_summon

Description

import hashlib
from tqdm import tqdm
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.number import long_to_bytes
import sys
 
sys.setrecursionlimit(2000)


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"

# reference: https://zenn.dev/anko/articles/ctf-crypto-rsa
def franklinReiter(n, e, r, c1, c2):
    R.<x> = Zmod(n)[]
    f1 = x^e - c1
    f2 = (x + r)^e - c2
    return - polygcd(f1, f2).coefficients()[0]

def polygcd(a, b):
    if(b == 0):
        return a.monic()
    else:
        return polygcd(b, a % b)

for mask in tqdm(range(1<<10)):
    diff = 0
    for i in range(10):
        if ((mask >> i) & 1) == 1:
            diff += 13*256**i
        else:
            diff -= 13*256**i

    m = int(franklinReiter(n, e, diff, c1, c2))
    key = hashlib.sha256(long_to_bytes(m)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    res = cipher.decrypt(encyprted_flag)
    if res.startswith(b"SECCON{"):
        print(res)
        break

dual_summon

description

solves: 63
---
You are a beginner summoner. It's finally time to learn dual summon
nc dual-summon.seccon.games 2222

source

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)

Solution

The goal of this challenge is to create a plaintext that generates the same tag when encrypted using two different AES keys under GCM mode.

Step 1: Recovering the GCM $H$

The fixed nonce introduces a vulnerability, allowing us to leak the internal state of the GCM encryption. GCM's tag generation process for a 16-byte plaintext can be described as:

t = (m + K)H^2 + LH + S \mod (x^{128} + x^7 + x^2 + x + 1)

Here:

$t$ : tag
$m$ : plaintext
$K, L, S$ : intermediate values, some of which are known.
$H$ : the hash key to be recovered.

By encrypting two plaintexts, $m_1$ and $m_2 = m_1 + a$ , the tags $t_1$ and $t_2$ are generated. Subtracting the equations for $t_1$ and $t_2$ , we obtain:

H^2 = \frac{t_1 - t_2}{m_1 - m_2}

Taking the square root modulo the Galois field polynomial gives us $H$ .

Step 2: Generating a common tag

Once $H_1$ and $H_2$ are recovered for the two AES keys, encrypt any plaintext $m'$ to compute their respective tags $t_1$ and $t_2$ . The common plaintext $m$ that produces the same tag for both keys is given by:

m = \frac{K_1 H_1^2 + LH_1 + S_1 + K_2 H_2^2 + LH_2 + S_2}{H_1^2 + H_2^2}

After computing $m$ , the final dual-summon function can be executed successfully.

import os

set_verbose(0)
os.environ['PWNLIB_NOTERM'] = '1'
os.environ['TERM'] = 'linux'

from Crypto.Cipher import AES
import secrets
from pwn import remote
from logger import logger

F.<a> = GF(2**128, modulus=x**128 + x**7 + x**2 + x + 1)

def to_poly(x):
    bs = Integer(int.from_bytes(x, "big")).bits()[::-1]
    return F([0] * (128 - len(bs)) + bs)

def to_bytes(x):
    v = int(bin(x.integer_representation())[2:].zfill(128)[::-1], 2)
    return v.to_bytes(128 // 8, "big")

def encrypt(number, plaintext):
    logger.info(io.recvuntil(">")) # summon or dualsummon
    io.sendline('1')
    logger.info(io.recvuntil(">")) # number
    io.sendline(str(number))
    logger.info(io.recvuntil(">")) # plaintext
    io.sendline(plaintext.hex())
    io.recvline()
    tag = bytes.fromhex(io.recvline().split(b"=")[1].strip().decode('utf-8'))
    return b"", tag

L = a^120
io = remote(os.getenv("SECCON_HOST"), int(os.getenv("SECCON_PORT")))
plaintext1 = b"a"*16
plaintext2 = b"a"*15 + b"b"
c1, t1 = encrypt(1, plaintext1)
c2, t2 = encrypt(1, plaintext2)
t1, t2 = to_poly(t1), to_poly(t2)
c1, c2 = to_poly(c1), to_poly(c2)
H1 = ((t1+t2) / (a^127 + a^126)).sqrt()
S1 = t1 + c1*H1*H1 + L*H1
k1 = to_poly(plaintext1) + c1

c1, t1 = encrypt(2, plaintext1)
c2, t2 = encrypt(2, plaintext2)
t1, t2 = to_poly(t1), to_poly(t2)
c1, c2 = to_poly(c1), to_poly(c2)
H2 = ((t1+t2) / (a^127 + a^126)).sqrt()
S2 = t1 + c1*H2*H2 + L*H2
k2 = to_poly(plaintext1) + c1

plaintext1 = to_poly(plaintext1)
plaintext2 = to_poly(plaintext2)
m = to_bytes((k2*H2*H2 + L*H2 + S2 + k1*H1*H1 + L*H1 + S1)/(H1*H1 + H2*H2))

io.recvuntil(">") 
io.sendline("2") # dual summon
io.sendline(m.hex())
io.recvline()
print(io.recvline())

Tidal wave

description

solves: 19
---
A torrent of data.

source

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=}")

Solution

This problem involves reconstructing certain algebraic structures and solving problems related to lattice-based cryptography.

Step 1: Solving for $\alpha$

The challenge provides the determinant of a Vandermonde matrix derived from $\alpha$ values, along with information such as $\alpha_i^2$ and $\sum \alpha_i$ encrypted with RSA. The Vandermonde determinant is expressed as:

\prod_{0 \leq i < j \leq m} (\alpha_j - \alpha_i)

Using the provided $\alpha_i^2$ values and Groebner basis techniques, the $\alpha$ values can be recovered iteratively. The summation property of $\alpha$ is used in conjunction with RSA decryption to fully reconstruct the set.

def get_alphas():
    PR = PolynomialRing(R,"x",n)
    xs = PR.gens()
    length = k
    l = 1
    polys = []
    for l in range(5):
        print("---", l, "---")
        offset = l * 7
        poly = 1
        for i in range(length):
            for j in range(0, i):
                poly *= (xs[i+offset] - xs[j+offset])
        poly -= dets[l]
        polys.append(poly)

        for i in range(n):
            x2s = []
            for i in range(length):
                polys.append(xs[i+offset]^2 - double_alphas[i+offset])

    I = ideal(polys)
    basis = I.groebner_basis()
    param_sum = 0
    coefficients = []
    for i in range(1, len(basis)):
        param_sum += -basis[i].coefficient(xs[-1])
        coefficients.append(-basis[i].coefficient(xs[-1]))

    param_sum += 1

    last_alpha = alpha_sum_rsa / (param_sum^65537) / pow(double_alphas[-1], 32768)
    predict_alphas = []

    for c in coefficients:
        predict_alphas.append(c*last_alpha)
    predict_alphas.append(last_alpha)

    return predict_alphas

Step 2: Recovering $p$

The encoded vector $v = pG$ is provided, where $G$ is derived from the recovered $\alpha$ values. Noise is added to the elements of $v$ , making this an LWE (Learning With Errors) problem. The problem can be solved using lattice reduction techniques (e.g., CVP solvers). However, partial recovery leaves some bits of $p$ unresolved, which can be completed using the Coppersmith method.

def get_p(alphas):
    error_range = 2^1000
    G = make_G(R, alphas)
    r = p_encoded

    GZZ = G.change_ring(ZZ)
    NI = (N) * matrix.identity(ZZ, n)
    Ik = matrix.identity(ZZ, k)
    Zero = matrix(ZZ, n, k)

    step = ceil(prime_bit_length/k)

    # [m1, m2, ..., mk, k1, k2, ..., kn]
    mat = block_matrix(
        [
            [GZZ      , Ik       ],
            [NI       , Zero     ]
        ]
    )

    lb = [ZZ(r[i]) - error_range for i in range(n)] + [0 for i in range(k)]
    ub = [ZZ(r[i]) + error_range for i in range(n)] + [2**step for i in range(k)]
    load("./rkm.sage") # https://github.com/rkm0959/Inequality_Solving_with_CVP
    result, applied_weights, fin = solve(mat, lb, ub)

    pbar = 0
    for i in range(k):
        pbar += R(fin[i] * 2^(step*i))

    PR.<x> = PolynomialRing(R)
    f = x + pbar
    x0 = f.small_roots(X=2^step, beta=0.3)[0]
    return ZZ(x0 + pbar)

Step 3: Recovering the key vector

The key vector $k$ is encoded as $v = kG$ with added noise and errors in some positions. This is equivalent to a Generalized Reed-Solomon (GRS) code problem, where errors occur in the encoded values. The GRS decoder, implemented in SageMath, can recover the key vector modulo $p$ and $q$ . The full key vector is reconstructed using the Chinese Remainder Theorem.

def test_p(p, c, alphas):
    F = GF(p)
    alphas = alphas.change_ring(F)

    l = []
    for i in range(n):
        l.append(F(i))
    row = []

    G = make_G(F, alphas)

    C = codes.GeneralizedReedSolomonCode(alphas, k)

    return C.decode_to_message(c)

def get_keyvec(alphas, p, q):
    R = Zmod(N)
    G = make_G(R, alphas)
    from params import key_encoded
    key_encoded = vector(key_encoded)
    alphas = vector(alphas)

    mp = test_p(p, key_encoded, alphas).change_ring(ZZ)
    mq = test_p(q, key_encoded, alphas).change_ring(ZZ)

    mm = []
    for i in range(len(mp)):
        mm.append(crt([mp[i], mq[i]], [p, q]))

    return vector(mm)

full source code

from params import *

R = Zmod(N)
n, k = 36, 8
prime_bit_length = 512

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 get_alphas():
    PR = PolynomialRing(R,"x",n)
    xs = PR.gens()
    length = k
    l = 1
    polys = []
    for l in range(5):
        print("---", l, "---")
        offset = l * 7
        poly = 1
        for i in range(length):
            for j in range(0, i):
                poly *= (xs[i+offset] - xs[j+offset])
        poly -= dets[l]
        polys.append(poly)

        for i in range(n):
            x2s = []
            for i in range(length):
                polys.append(xs[i+offset]^2 - double_alphas[i+offset])

    I = ideal(polys)
    basis = I.groebner_basis()
    param_sum = 0
    coefficients = []
    for i in range(1, len(basis)):
        param_sum += -basis[i].coefficient(xs[-1])
        coefficients.append(-basis[i].coefficient(xs[-1]))

    param_sum += 1

    last_alpha = alpha_sum_rsa / (param_sum^65537) / pow(double_alphas[-1], 32768)
    predict_alphas = []

    for c in coefficients:
        predict_alphas.append(c*last_alpha)
    predict_alphas.append(last_alpha)

    return predict_alphas

def get_p(alphas):
    error_range = 2^1000
    G = make_G(R, alphas)
    r = p_encoded

    GZZ = G.change_ring(ZZ)
    NI = (N) * matrix.identity(ZZ, n)
    Ik = matrix.identity(ZZ, k)
    Zero = matrix(ZZ, n, k)

    step = ceil(prime_bit_length/k)

    # [m1, m2, ..., mk, k1, k2, ..., kn]
    mat = block_matrix(
        [
            [GZZ      , Ik       ],
            [NI       , Zero     ]
        ]
    )

    lb = [ZZ(r[i]) - error_range for i in range(n)] + [0 for i in range(k)]
    ub = [ZZ(r[i]) + error_range for i in range(n)] + [2**step for i in range(k)]
    load("./rkm.sage")
    result, applied_weights, fin = solve(mat, lb, ub)

    pbar = 0
    for i in range(k):
        pbar += R(fin[i] * 2^(step*i))

    PR.<x> = PolynomialRing(R)
    f = x + pbar
    x0 = f.small_roots(X=2^step, beta=0.3)[0]
    return ZZ(x0 + pbar)

def test_p(p, c, alphas):
    F = GF(p)
    alphas = alphas.change_ring(F)

    l = []
    for i in range(n):
        l.append(F(i))
    row = []

    G = make_G(F, alphas)

    C = codes.GeneralizedReedSolomonCode(alphas, k)

    return C.decode_to_message(c)

def get_keyvec(alphas, p, q):
    R = Zmod(N)
    G = make_G(R, alphas)
    from params import key_encoded
    key_encoded = vector(key_encoded)
    alphas = vector(alphas)

    mp = test_p(p, key_encoded, alphas).change_ring(ZZ)
    mq = test_p(q, key_encoded, alphas).change_ring(ZZ)

    mm = []
    for i in range(len(mp)):
        mm.append(crt([mp[i], mq[i]], [p, q]))

    return vector(mm)

alphas = get_alphas()
p = ZZ(get_p(alphas))
q = ZZ(N // p)
print(f"{p=}")
keyvec = get_keyvec(alphas, p, q)

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)
flag = cipher.decrypt(encrypted_flag)
print(flag)

reiwa_rot13

description

source

Solution

dual_summon

Description

dual_summon

description

source

Solution

Step 1: Recovering the GCM H

Step 2: Generating a common tag

Tidal wave

description

source

Solution

Step 1: Solving for \alpha

Step 2: Recovering p

Step 3: Recovering the key vector

full source code

Discussion

Step 1: Recovering the GCM $H$

Step 1: Solving for $\alpha$

Step 2: Recovering $p$