PlaidCTF 2017

Pykemon

Category: Web

Posted on April 24, 2017

Gotta catch them FLAGs! Take this with you. (Link to binary)

This challenge was relatively simple. You could capture different pykemon by clicking on them, and each had a different chance of success, or rarity. The Flag was treated as a pykeymon but with a rarity of 0 meaning it was impossible to catch. Each pykeymon had a description that you could view when you caught it, and the flag had the actual flag. The site had a cookie through Flask that is simple to decrypt to get a base64'd version of the flag. We used a modified version of the python source available here. After decoding the cookie, the descriptions were encoded in Base64. Decode the one corresponding to the flag to find the flag.

Flag: PCTF{N0t_4_sh1ny_M4g1k4rp}


multicast

Category: Crypto

Posted on April 26, 2017

You need to have Sage installed to tackle this challenge.

Håstad's attack is an attack on RSA when the same message m is encrypted with different public keys (e's + N's), but keeping the public exponent `e` constant. Notably, `e` has to be really small.

Unfortunately, in the given challenge, it is not exactly the same message m, but rather a polynomial with a single variable m (and one guaranteed to have exactly 1 solution mod n):

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):
    while True:    
        p = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
        q = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
        ni = p*q
        phi = (p-1)*(q-1)
        if gcd(phi, e) == 1:
            break

    while True:
        ai = randint(1,ni-1)
        if gcd(ai, ni) == 1:
            break

    bi = randint(1,ni-1)
    mi = ai*m + bi  # <-- This is the polynomial! It is guaranteed to have a unique solution m because ai and ni are coprime.
    ci = pow(mi, e, ni)
    out.write(str(ai)+'\n')
    out.write(str(bi)+'\n')
    out.write(str(ci)+'\n')
    out.write(str(ni)+'\n')

Luckily, according to this paper, the Håstad attack is still possible, as there are 5 keys given, and the exponent is 5, and the maximum degrees of the polynomials are all 1. Perfect! Just a little more work is required.

The steps are:

  1. Make all five polynomials corresponding to the h polynomials in the linked paper above.
  2. Multiply them by the inverse of their leading coefficients modulo their respective n's to make them monic.
  3. Make a final polynomial from the sum of the 5 monic ones, choosing the T coefficients using the Chinese Remainder Theorem as specified by the paper.
  4. Use Coppersmith's univariate method to find the root of that polynomial. This root is the original message m, which is the flag.

Solution (included are the given values from the challenge!):

a1 = 69083553146183344839772978505267712546348345951915552104934666999364893606414967631473531356169090286677897220956536147203986323670778671853966574104550916190831974039291113434428713226539656233005536401237618731903013444912424490954403050283261443145833828774338405850464149745370010921929208582803372719662
a2 = 27025595670607123748133955387986761928986723842407963667833744851457582823949409825451502999363014637018266381381800334740959357732693327871649715849440610655814448606276225985636706847320729571129651265791968308846145775455134446011658371731137714821594128627843120134392299295278193619998726010683820300906
a3 = 3004029671513060545517047598385797934912754972599429487078366757715733246340760740484289209221138121568405251845847578856114711659946228365274190780159966913357682874178318970562635144717761245951754408952773122354583612422645258507146795630561366955268226048296864853067903656400207186949463324893914485565
a4 = 42305211872257990504112591982462712826623117527580306258621876854892728665082535381823460722212076449810881809439537932537619270097066694079814712136330261508201872405339882571623217945205024525421229411985020496914748229102523658456972139082089291624782533401385935487411288676903751198610145921301518231107
a5 = 35798442949372217448131245718267683892608947365147471016957781854054771928382329233065506241624702265207177594187978141208820788381204095301540789196845409818326829309725267401115274448449544207730582441399296587733377747658506089439891602945020732454221665678849354836056443444544603686977883511757122333808

b1 = 1847353606880715823527099792264841437499256859046112182901817731898583109812226034453486290034759426343181112477498401843027934563915568068662901070357638240406212287869791959600724393823543974271939728800168160170264361943043888105413027223078955278440961637038127459036967868261370295558665462738851664674
b2 = 76626521446699164152465241536023395842467420530412705255543098462161399927889232797875074266701010280661667851769988806969262190694662659916308198862288454347865777843483804317714263754964326435968683758707252482706186266157923587034286069745922345373717550980870551177895535541280767243258161167226140529179
b3 = 39916349286626463801197107509708900778499859478703695888378041406302001988773262878930035955207487249221227735861868182215434820807844055889132141226547303138247159556705455695270756436706739886462479337109843197568024375533105139465029460850504284879314129902197486373473299170494478698741715992027042335920
b4 = 37927948227203538741746385301195518552457676697015260677758470292294745311488915679784285945487731017142600921756814455642818173556814139042013977633776585763163271296255014647248684364947573160457459801483696377003575286309739820627536302900476424058673287304085337544422656511271366685116274814463373028939
b5 = 15148604454321045616017299717211628700774278430049633748723698755621714384646643282913626328387905917563070000934175316190944226369346680779250458706206743862204417104832969982264440206554850551723416393459529398494316425018200651517022177685036277113534264161058597282135279496222169055121895473052233762246

c1 = 13924397671629169794872532654354896735104301636897981275021597449713744312702850679542667853889775700566291452624971794825605462609659305736119167763171202028684488729179106128850062049316631850373987498751231054904292395688010798166991604433834113228237987911867991301264314792383410544657232986272138720776
c2 = 74820001900443652318294067181707795319993357148314983190736617977547527951708569170206478241294503335669164830735894900549009883421968340647253048091278584463455833751347773269310148496440204410893225151858930449694234125324321395015257722229646579662704510552084383728048226410232141635889320648460673299335
c3 = 14108999386222915459940913638433135402751523880380098398237968303803785854582535395117824943688282642164021530817702254201291805032640778641839809162886268856556652703619578965302291774447936003759868066323907388148146727752981125365333046242305065445858381847752308536916145502431706840471314490470498925933
c4 = 29808378278310626950656040722768610557513777159495566134112105939237344988328390169388824486265334935284692186547128505302437631500267072936205473588904993250984366335171085215776781494184026623681600861765081754836053424849422843633084928107942855476866942904060229897408614881375916806167293356422910088562
c5 = 90847039947327313643774540191254303763104502856236195148227169238729840332433440088244863054796973078431673232305152421572163200464861625035107176753552370732936207870756803675490237581973525804663863823181351604257906567409397759543713937699041851977124940235865938476195092603195522703292454934101412022811

n1 = 107176667955056054888106289112863406099193890480114548290390156586316295797860714447523894766296345238663487884525751440074160698573876676529510120482633305843604033670838833224316621039974842663423971964367617383524243164757298543267528648455662196669719411550337416706436014652957797379123891565563380621721
n2 = 116940935524323795130742526994657925027084667081524402264947741484054748546876541534619667289853985612350852220069194599338546449074832255593771931123087798582432365325897386813589970457955530817464044545954375253380129491859158211405510009895941963611340400391118219478974834168088677930751757315159110921841
n3 = 100668102943542293762890526110731145470895119442621421158649868631915746146377966542031367735374167457406299434355768725246104804285632863373024153609404762902208230939718098090168262799174612923680636870557478441319366190063047687786785211877198536555745316733683533528849562416675658775836498023052914901749
n4 = 80450031402201203587730534009338660865222026164984422981250298135548464160260574889923232542563882168618899594606271070764435488631855210441010916420059803623249294290301484880522559794167514055495411717729597100446344174893389277795663285345593590647340104666332031316803275436638414115193469755829893511487
n5 = 93862849424043561789940054837392625966883465717813492561917969675964529083848723311514364070936115132154848096497003118110036719543385624344289211314373383330520240583297483284951457880437389550791045654411987778690675595035123064122359417085803319134114455113012761800931917960807358624095094896528184569953
N = n1*n2*n3*n4*n5
e = 5

F.<x> = PolynomialRing(Zmod(N), implementation='NTL')

# Step 1
h1 = (a1*x+b1)^e-c1
h2 = (a2*x+b2)^e-c2
h3 = (a3*x+b3)^e-c3
h4 = (a4*x+b4)^e-c4
h5 = (a5*x+b5)^e-c5

# Step 2
h1 *= inverse_mod(int(h1.lc()), n1)
h2 *= inverse_mod(int(h2.lc()), n2)
h3 *= inverse_mod(int(h3.lc()), n3)
h4 *= inverse_mod(int(h4.lc()), n4)
h5 *= inverse_mod(int(h5.lc()), n5)

# Step 3
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])

pol = t1*h1 + t2*h2 + t3*h3 + t4*h4 + t5*h5 # should be monic

# Step 4 (the Coppersmith method is built-in to Sage)
XX = 2**512
roots = pol.small_roots(XX)
flag = int(roots[0])
print hex(flag)[2:-1].decode('hex')

PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}


Copyright © Cornell Hacking Club 2021