Akasec CTF 2024 Writeup

Sanity Check (MISC)

Discordに入り、#rulesチャネルのトピックを見ると、フラグが書いてあった。

AKASEC{Typ1c4l_s4n1ty_ch3ck_1n_d1sc0rd}

Sperm Rev (REV)

$ strings sperm_rev| grep AKASEC                       
AKASEC{strings_b35t_t00l_1n_r3v3r5e_eng1n33r1ng}

AKASEC{strings_b35t_t00l_1n_r3v3r5e_eng1n33r1ng}

Lost (CRYPTO)

平文の上位ビットがわかっているので、Coppersmithの定理を使って復号する。

#!/usr/bin/env sage
from Crypto.Util.number import *

with open('out.txt', 'r') as f:
    params = f.read().splitlines()

e = 2
n = int(params[0].split(' ')[-1])
c = int(params[1].split(' ')[-1])
cor_m = int(params[2].split(' ')[-1])

PR.<x> = PolynomialRing(Zmod(n))
f = (cor_m + x)^e - c
x0 = int(f.small_roots(X=2^160, beta=1)[0])
m = cor_m + x0
flag = long_to_bytes(m).decode()
print(flag)

AKASEC{c0pp3r5m17h_4774ck_1n_1ov3_w17h_5m4ll_3xp0n3nts}

Power Over All (CRYPTO)

暗号処理の概要は以下の通り。

・ps = key_gen()
　・ps = []
　・n: ランダム2以上2**6以下の整数
　・n回以下繰り返し
　　・p: 256ビット素数
　　・psにpを追加
　・psを返却
・c = encrypt([FLAGの数値化したもの], ps)
　・m: FLAGの数値化したもの
　・psをソート
　・psの各pについて以下を実行
　　・e = 2
　　・m = pow(m, e, p)
　・mを返却
・psとcを出力

legendreの定理を使って、平方を取っていくことを繰り返す。複数の数値に復号されるので、文字列にしてフラグの形式になるものを探す。

#!/usr/bin/env python3
from Crypto.Util.number import *

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

def tonelli_shanks(a, p):
    if legendre(a, p) != 1:
        return -1

    q = p - 1
    s = 0
    while q % 2 == 0:
        q >>= 1
        s += 1

    for z in range(2, p):
        if legendre(z, p) == p - 1:
            break

    m = s
    c = pow(z, q, p)
    t = pow(a, q, p)
    r = pow(a, (q + 1) // 2, p)

    t2 = 0
    while True:
        if t == 0: return 0
        if t == 1: return r
        t2 = (t * t) % p
        for i in range(1, m):
            if t2 % p == 1:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        m = i
        c = (b * b) % p
        t = (t * c) % p
        r = (r * b) % p

with open('out.txt', 'r') as f:
    params = f.read().splitlines()

ps = eval(params[0].split(' = ')[1])
c = int(params[1].split(' = ')[1])

ms = [c]
for p in ps[::-1]:
    tmp = []
    for m in ms:
        x = tonelli_shanks(m, p)
        if x != -1:
            tmp.append(x)
            tmp.append(p - x)
    ms = tmp

for m in ms:
    flag = long_to_bytes(m)
    if flag.startswith(b'AKASEC{'):
        flag = flag.decode()
        print(flag)
        break

AKASEC{akasec+palestine=<3}

GCL (CRYPTO)

暗号処理の概要は以下の通り。

・BIITS = 128
・m: 128ビット素数
・s: ランダム127ビット整数
・a: ランダム127ビット整数
・b: ランダム127ビット整数
・c = []
・r = s
・FLAGの各文字について以下を実行
　・r = lcg(r, ord(i))
　　・ord(i) * (a * r + b) % mを返却
　・cにrを追加
・m、cを出力

flagが"AKASEC{"から始まることを前提にa, b, sを求める。
n番目の文字を処理した後のrをrnと表すと、以下のようになる。

r0 = flag[0] * (a * s + b) % m
r1 = flag[1] * (a * r0 + b) % m
r2 = flag[2] * (a * r1 + b) % m
        :

そして以下のように変形できる。

r0 * inverse(flag[0], m) = (a * s + b) % m
r1 * inverse(flag[1], m) = (a * r0 + b) % m
r2 * inverse(flag[2], m) = (a * r1 + b) % m

さらに以下のように変形でき、a, b, sを算出できる。

(r2 * inverse(flag[2], m) - r1 * inverse(flag[1], m)) % m = a * (r1 - r0) % m
a = (r2 * inverse(flag[2], m) - r1 * inverse(flag[1], m)) * inverse(r1 - r0, m) % m
b = (r1 * inverse(flag[1], m) - a * r0) % m
s = (r0 * inverse(flag[0], m) - b) * inverse(a, m) % m

あとは順に逆関数inverseを使って、flagの各文字を求めていく。

#!/usr/bin/env python3
from Crypto.Util.number import *

with open('out.txt', 'r') as f:
    params = f.read().splitlines()

m = int(params[0].split(' = ')[1])
c = eval(params[1].split(' = ')[1])

head_flag = b'AKASEC{'

a = (c[2] * inverse(head_flag[2], m) - c[1] * inverse(head_flag[1], m)) * inverse(c[1] - c[0], m) % m
b = (c[1] * inverse(head_flag[1], m) - a * c[0]) % m
s = (c[0] * inverse(head_flag[0], m) - b) * inverse(a, m) % m
print('[+] a =', a)
print('[+] b =', b)
print('[+] s =', s)

assert head_flag[0] * (a * s + b) % m == c[0]
for i in range(6):
    assert head_flag[i+1] * (a * c[i] + b) % m == c[i+1]

c = [s] + c
flag = ''
for i in range(len(c) - 1):
    code = c[i + 1] * inverse(a * c[i] + b, m) % m
    flag += chr(code)
print('[*] flag:', flag)

実行結果は以下の通り。

[+] a = 57879387829375788513313321928485165943
[+] b = 123253563871232818483050010946596502567
[+] s = 96397753169964322958020651044633108293
[*] flag: AKASEC{++see_?!_just_some_math--}

AKASEC{++see_?!_just_some_math--}

Twin (CRYPTO)

暗号処理の概要は以下の通り。

・e = 5
・p, q: 256ビット素数
・n = p * q
・m1: FLAGを数値化したもの
・m2: m1を8ビットシフトしたもの
・c1 = pow(m1, e, n)
・c2 = pow(m2, e, n)
・n, c1, c2を出力

m1は以下の式で表せる。

m1 = m2 * 256 + A (A: 0以上255以下)

m2 * 256 と m1 の差は255以下で、それぞれのRSA暗号化したものはわかる。このため、Coppersmith's Short Pad Attackで復号できる。

#!/usr/bin/env sage
from Crypto.Util.number import *

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]

    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

with open('out.txt', 'r') as f:
    params = f.read().splitlines()

e = 5
n = int(params[0].split(' = ')[1])
c1 = int(params[1].split(' = ')[1])
c2 = int(params[2].split(' = ')[1])

c2_2 = c2 * pow(256, e, n) % n

diff = short_pad_attack(c2_2, c1, e, Integer(n))
m2 = related_message_attack(c2_2, c1, diff, e, n)
m1 = int(m2 + diff)
flag = long_to_bytes(m1).decode()
print(flag)

AKASEC{be_on_the_right_side_of_history_free_palestine}