💡

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

2024/11/28に公開

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

この問題は keyrot13_key の関係に注目することが大切です。
今回は英小文字のみなので、各文字ごとに a~m であれば+13、n~zであれば-13されます。
今回は10文字しかないので、+13と-13をすべての文字で試しても1024通りしかありません。
これは以下のコードで列挙することができます

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

あとはRSAの平文の差がわかるとき、Franklin Reiter's Attack と呼ばれる攻撃方法が成立することを知っていればそのライブラリを使ったり、ソースコードを利用することで解くことができます。

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

この問題のゴールは異なる2つの鍵で共通の平文で同じtagを生成することです。

この問題はnonceが固定化されている脆弱性が存在しているため、平文とXORされる前の値(固定値)を知ることができそうです。
この問題を解くうえで、GCMのtag多項式演算の加算はXORと同じであることを知っておく必要があります。GCMはこちらの動画で紹介しています。ここまでついてこれていない人はこちらの動画を見てください: https://youtu.be/nXi3Mpufe5M?si=xcf2Q3du3lDpvNZw

step1: Hの導出

まずは一つの鍵で暗号化する機能(summon)を使って、GCM内部の状態をリークします。

今回平文の長さは16bytesである必要があるため、tagは以下の式で生成されます。
tは出力内容、mは入力した平文、Lは平文の長さから導出できるため既知で、それ以外の変数は未知です。
この式のH を求めることが最初のステップです。

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

ここで、 m_1+a=m_2 となる平文、m_1, m_2 を生成します。(a は既知であればいくつでも大丈夫です。a=1であれば問題が解きやすくなります。)
これらの平文を用いて、tagを2つ生成してみましょう。

\begin{aligned} (m_1 + K) H^2 + LH + S &= t_1 \\ (m_2 + K) H^2 + LH + S &= t_2 \end{aligned}

ここで、t_1 - t_2 を考えます。

\begin{aligned} t_1 - t_2 &= (m_1 - m_2) H^2 \\ H^2 &= (t_1-t_2)/(m_1 - m_2) \end{aligned}

あとは平方剰余を求めるだけですね。この問題を解くうえではHだけ求められればOKです。

step2: 共通するtagの生成

前のステップでそれぞれの鍵に対応するHを求めることができました。これを H_1, H_2 とします。またそれぞれの鍵で適当な平文 m' を暗号化しておきます。

\begin{aligned} (m' + K_1) H_1^2 + LH_1 + S_1 &= t_1 \\ (m' + K_2) H_2^2 + LH_2 + S_2 &= t_2 \end{aligned}

さて、ここで共通のタグが生成される平文mは以下の式で求めることができます。

\begin{aligned} (m + K_1) H_1^2 + LH_1 + S_1 &= (m + K_2) H_2^2 + LH_2 + S_2 \\ m &= (K_1 H_1^2 + LH_1 + S_1 + K_2 H_2^2 + L H_2 + S_2) / (H_1^2 + H_2^2) \\ m &= (m'H_1^2 + t_1 + m'H_2^2 + t_2) / (H_1^2 + H_2^2) \end{aligned}

source code

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

step1: alphaの導出

この問題はまず \alpha を求め、行列を復元する必要があります。
今回求める行列は Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) という名前がついています。
その行列式は以下の形式になることが知られています。今回は正方行列ではないので、これを少しずつずらして複数与えられます。

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

また今回の問題では、\alpha_i^2, (\sum{\alpha_i})^{65537}も与えられます。

しかしながらすべて pq で mod が取られているため、ここから \alpha_i を復元することが難しいです。

ここで、\alpha_i^2 が与えられているため、これらの式は1次以下に抑えられそうな気がします。
頑張って求めても良いですが、 groebner_basis を求めることで、この式変形を自動的に求めることができます。これはsagemathにも実装されており、簡単に使うことができます。(https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_ideal.html)

もちろん、これらの式すべての groebner_basis を求めることで \alpha を求めることはできますが、(\sum{\alpha_i})^{65537} も一緒に計算するとあまりにも次数が大きくなりすぎて計算時間が大きすぎてしまいます。

そこで、まずは行列式と、\alpha_i^2 から一次式を求め簡単にすることにしましょう。
これらは最大でも8次なので、現実的な時間で計算することができます。
ここではまだ答えが求まらないので、varietyを利用することができないため、variety ではなく groebner_basis を利用することが大切です

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)):
        print(basis[i]

この実行結果は以下のようになります。 \alpha_{35} と各変数の関係式を導き出すことができました。

x0 + 101167463165697523840879155236135415366380424009464416331763855106184994633902302674087295255438751596774946284741606345729143993302112286520469294367507812315056318317781265297438013015868686890078715661635388273272226617417231986427962523043300715969264411559608335541462289882989793354071670690306513709519*x35
x1 + 99816305691223099820353394198653556348673685338452752390709712662751963955018291035690933586495874204856425012304440226888304154089937984356244091799405992883850252885469253083907806945264024073842402938150768910238393582861876052386054944373525820386502846106714272089979496347781222903621586813884929103048*x35
x2 + 153947320566716262616994979410188678739855205152591327118109633632831079874904201207623989372460852121565808503574990737588802732830815358621180239941162812988178974481362876713673930653580228231369894797024458703841541697777606681268859123289780674638214333073327446050895932236334966741881459108747047657435*x35
...

この結果を用いることで、上記求めた係数の和を A として、以下のような変形をすることができます。

(\sum{\alpha_i})^{65537} = A^{65537} \alpha_{35}^{65537}

また、alpha_{35}^2 も与えられていることから、RSAにおいて異なるe で暗号化したものから復元する要領で \alpha_{35}を求めることができます。のこりの \alpha は groebner_basis の結果から求めることができます。

以下のコードで \alpha のすべてを求めることができます。

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

step2: pの導出

次に p を求めます。求めた行列をGとして、pに関して v=pG が与えられています。
ただし、vの各要素は1000bit程度の乱数が加えられています。

この問題は典型的なLWE(Learning with Errors)問題です。
CVP(Closest Vector Problem)という問題を解くことでもこの問題を解くことができます。
CVPを求めるためには https://github.com/rkm0959/Inequality_Solving_with_CVP これが便利です。

しかしながら、これでpを復元しても情報が足りていないため64bit程度復元できません。
今回の問題は N = pq も与えられているので、足りない部分は coppersmith で復元することにしましょう。

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)

step3: keyvecの復元

最後にkeyvecを求める問題です。 v = kG が与えられていることには変わりませんが、各要素の値の大きさと、mod p を取ると14個程度完全に破壊されている点で異なります。

実は、この問題はmod pとmod qを取るとGeneralized Reed Solomon (https://doc.sagemath.org/html/en/reference/coding/sage/coding/grs_code.html) の復元そのものです。

sagemathの機能を使うと簡単に求めることができます。

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)

これでkeyvecを復元することができたので、この問題を解くことができました。

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)

Discussion