PlaidCTF 2017 供養（Writeup）

CTF

PlaidCTF 2017に参加。236ptで182位。

sanity check (Misc 1)

The flag is PCTF{poop}

logarithms are hard (Misc 10)

What is e1.000000001?

Please enter in decimal with 7 places. (For example, if the answer was 2.71828183… the flag would be 2.7182818 )

普通に計算すると2.7182818になるが、通らない。

$ gp -q
? exp(1.000000001)
2.7182818311773270651784736213955195583

過去の問題にならい、対数に関するバグについて調べてみると、関数電卓TI-35Xのバグについて書かれているページが見つかった。

関数電卓TI-30X/TI-36X SOLARで計算される値を答えたところ、通った。

2.7191928

zipper (Misc 50)

壊れているzipファイルが与えられる。

$ unzip zipper_50d3dc76dcdfa047178f5a1c19a52118.zip
Archive:  zipper_50d3dc76dcdfa047178f5a1c19a52118.zip
warning:  filename too long--truncating.
:  bad extra field length (central)

データがdeflateで圧縮されているものと仮定し、1バイトずつずらしながら展開を試みるとフラグが得られた。

import zlib

with open('zipper_50d3dc76dcdfa047178f5a1c19a52118.zip') as f:
    data = f.read()

for i in xrange(len(data)):
    print hex(i)
    chunk = data[i:]
    try:
        print zlib.decompress(chunk, -15)
    except zlib.error as e:
        pass
$ python test.py
0x0
0x1
f
0x2

(snip)
0x42


Huzzah, you have captured the flag:
PCTF{f0rens1cs_yay}




(snip)
0xea
0xeb

Multicast (Crypto 175)

RSA。 generate.sageを読むと、mを512bitの整数として、ai, bi, ci, niを5組出力しており、これがdata.txtとして与えられている。

nbits = 1024
e = 5
flag = open("flag.txt").read().strip()
assert len(flag) <= 64
m = Integer(int(flag.encode('hex'),16))
out = open("data.txt","w")

for i in range(e):
    (snip)
    mi = ai*m + bi
    ci = pow(mi, e, ni)
    (snip)

一般化されたHåstad’s broadcast attackで解ける。

a1 = 69083553146183344839772978505267712546348345951915552104934666999364893606414967631473531356169090286677897220956536147203986323670778671853966574104550916190831974039291113434428713226539656233005536401237618731903013444912424490954403050283261443145833828774338405850464149745370010921929208582803372719662
b1 = 1847353606880715823527099792264841437499256859046112182901817731898583109812226034453486290034759426343181112477498401843027934563915568068662901070357638240406212287869791959600724393823543974271939728800168160170264361943043888105413027223078955278440961637038127459036967868261370295558665462738851664674
c1 = 13924397671629169794872532654354896735104301636897981275021597449713744312702850679542667853889775700566291452624971794825605462609659305736119167763171202028684488729179106128850062049316631850373987498751231054904292395688010798166991604433834113228237987911867991301264314792383410544657232986272138720776
n1 = 107176667955056054888106289112863406099193890480114548290390156586316295797860714447523894766296345238663487884525751440074160698573876676529510120482633305843604033670838833224316621039974842663423971964367617383524243164757298543267528648455662196669719411550337416706436014652957797379123891565563380621721
a2 = 27025595670607123748133955387986761928986723842407963667833744851457582823949409825451502999363014637018266381381800334740959357732693327871649715849440610655814448606276225985636706847320729571129651265791968308846145775455134446011658371731137714821594128627843120134392299295278193619998726010683820300906
b2 = 76626521446699164152465241536023395842467420530412705255543098462161399927889232797875074266701010280661667851769988806969262190694662659916308198862288454347865777843483804317714263754964326435968683758707252482706186266157923587034286069745922345373717550980870551177895535541280767243258161167226140529179
c2 = 74820001900443652318294067181707795319993357148314983190736617977547527951708569170206478241294503335669164830735894900549009883421968340647253048091278584463455833751347773269310148496440204410893225151858930449694234125324321395015257722229646579662704510552084383728048226410232141635889320648460673299335
n2 = 116940935524323795130742526994657925027084667081524402264947741484054748546876541534619667289853985612350852220069194599338546449074832255593771931123087798582432365325897386813589970457955530817464044545954375253380129491859158211405510009895941963611340400391118219478974834168088677930751757315159110921841
a3 = 3004029671513060545517047598385797934912754972599429487078366757715733246340760740484289209221138121568405251845847578856114711659946228365274190780159966913357682874178318970562635144717761245951754408952773122354583612422645258507146795630561366955268226048296864853067903656400207186949463324893914485565
b3 = 39916349286626463801197107509708900778499859478703695888378041406302001988773262878930035955207487249221227735861868182215434820807844055889132141226547303138247159556705455695270756436706739886462479337109843197568024375533105139465029460850504284879314129902197486373473299170494478698741715992027042335920
c3 = 14108999386222915459940913638433135402751523880380098398237968303803785854582535395117824943688282642164021530817702254201291805032640778641839809162886268856556652703619578965302291774447936003759868066323907388148146727752981125365333046242305065445858381847752308536916145502431706840471314490470498925933
n3 = 100668102943542293762890526110731145470895119442621421158649868631915746146377966542031367735374167457406299434355768725246104804285632863373024153609404762902208230939718098090168262799174612923680636870557478441319366190063047687786785211877198536555745316733683533528849562416675658775836498023052914901749
a4 = 42305211872257990504112591982462712826623117527580306258621876854892728665082535381823460722212076449810881809439537932537619270097066694079814712136330261508201872405339882571623217945205024525421229411985020496914748229102523658456972139082089291624782533401385935487411288676903751198610145921301518231107
b4 = 37927948227203538741746385301195518552457676697015260677758470292294745311488915679784285945487731017142600921756814455642818173556814139042013977633776585763163271296255014647248684364947573160457459801483696377003575286309739820627536302900476424058673287304085337544422656511271366685116274814463373028939
c4 = 29808378278310626950656040722768610557513777159495566134112105939237344988328390169388824486265334935284692186547128505302437631500267072936205473588904993250984366335171085215776781494184026623681600861765081754836053424849422843633084928107942855476866942904060229897408614881375916806167293356422910088562
n4 = 80450031402201203587730534009338660865222026164984422981250298135548464160260574889923232542563882168618899594606271070764435488631855210441010916420059803623249294290301484880522559794167514055495411717729597100446344174893389277795663285345593590647340104666332031316803275436638414115193469755829893511487
a5 = 35798442949372217448131245718267683892608947365147471016957781854054771928382329233065506241624702265207177594187978141208820788381204095301540789196845409818326829309725267401115274448449544207730582441399296587733377747658506089439891602945020732454221665678849354836056443444544603686977883511757122333808
b5 = 15148604454321045616017299717211628700774278430049633748723698755621714384646643282913626328387905917563070000934175316190944226369346680779250458706206743862204417104832969982264440206554850551723416393459529398494316425018200651517022177685036277113534264161058597282135279496222169055121895473052233762246
c5 = 90847039947327313643774540191254303763104502856236195148227169238729840332433440088244863054796973078431673232305152421572163200464861625035107176753552370732936207870756803675490237581973525804663863823181351604257906567409397759543713937699041851977124940235865938476195092603195522703292454934101412022811
n5 = 93862849424043561789940054837392625966883465717813492561917969675964529083848723311514364070936115132154848096497003118110036719543385624344289211314373383330520240583297483284951457880437389550791045654411987778690675595035123064122359417085803319134114455113012761800931917960807358624095094896528184569953

e = 5
n = n1*n2*n3*n4*n5
t1 = crt([1,0,0,0,0], [n1,n2,n3,n4,n5])
t2 = crt([0,1,0,0,0], [n1,n2,n3,n4,n5])
t3 = crt([0,0,1,0,0], [n1,n2,n3,n4,n5])
t4 = crt([0,0,0,1,0], [n1,n2,n3,n4,n5])
t5 = crt([0,0,0,0,1], [n1,n2,n3,n4,n5])

PR.<x> = PolynomialRing(Zmod(n))
g1 = (a1*x + b1)^e - c1
g2 = (a2*x + b2)^e - c2
g3 = (a3*x + b3)^e - c3
g4 = (a4*x + b4)^e - c4
g5 = (a5*x + b5)^e - c5

g = 1*t1*g1 + 2*t2*g2 + 3*t3*g3 + 4*t4*g4 + 5*t5*g5
g = g.monic()

kbits = 64*8
x = g.small_roots(X=2^kbits, beta=1)[0]

print hex(long(x))[2:-1].decode('hex')
sage@vm-ubuntu64:~$ sage test.sage
PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}

所感

他に解きたかった問題は以下。

  • no_mo_flo (Reversing 125)
  • Echo (Web 200)
  • Pykemon (Web 151)
  • bigpicture (Pwnable 200)