[zer0pts CTF 2020] dirty laundry

chall.py, output.txt가 주어진다.

dirty laundry.zip

9.9 kB

#!/usr/bin/sage
from sage.all import *
from Crypto.Util.number import getStrongPrime, bytes_to_long

from secret import flag

class PRNG256(object):
    def __init__(self, seed):
        self.mask = (1 << 256) - 1
        self.seed = seed & self.mask

    def _pick(self):
        b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b

    def rand(self):
        x = 0
        for i in range(256):
            x = (x << 1) | self._pick()
        return x

PRIME = getStrongPrime(1024)
prng = PRNG256(PRIME)

def paillier_enc(m, p, noise):
    p = next_prime(p + noise)
    q = getStrongPrime(512)
    n = p * q
    g = (1 + prng.rand() * n) % n**2
    c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2
    return n, g, c

def make_shares(secret, k, shares, prime=PRIME):
    PR, x = PolynomialRing(GF(prime), name='x').objgen()
    f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)])
    xy = []
    pubkey = []
    for x in range(1, shares+1):
        noise = prng.rand()
        n, g, y = paillier_enc(f(x) + noise, prime, noise)
        pubkey.append([n, g])
        xy.append([x, y])
    return pubkey, xy

secret = bytes_to_long(flag)
pubkey, shares = make_shares(secret, 3, 5)

print("[+] len(flag):", len(flag))
print("[+] pubkey:", pubkey)
print("[+] shares:", shares)

sage에 쫄았지만 사실 sage를 사용하는 문제는 아니였다. 꽤 괜찮게 재밌었던 문제.

우선 1024bit 강력한 소수를 잡아주고 PRNG256의 seed 값으로 넣어준다. 의사난수를 생성해주는 class로 보이는데 보통 이런건 난수를 leak할 수 있을 것 같다.

PRNG256은 받은 seed의 하위 256비트만 사용한다. rand 함수를 보면 pick 함수의 리턴값을 상위 비트부터 채워진다. pick 함수의 취약점을 찾는 건 굉장히 까다로워 보인다. pick 함수를 거치면 seed 값이 오른쪽으로 1 shift되고 상위 1비트에 b값이 들어오게 된다. 따라서 rand 함수의 리턴값이 x라면, 이후의 seed 값은 x를 거꾸로 뒤집어 놓은 값과 같다.

make_shares라는 함수는 우선 f를 이차식꼴로 만들어 상수항에 flag, 1차, 2차 계수에는 랜덤값을 넣어준다. 그리곤 for 문을 5번 도는데, 돌 때마다 prng.rand()가 세번 실행된다. 그 값을 순서대로 R0, R1, R2 라 하겠다. 수식으로 함수를 정리하자면,

이 중, n, g, y에 값을 알 수 있다. 그런데 g 값을 잘 살펴보면, n은 1536bit, R1 은 256bit로 nR1 은 n^2 보다 커질 수 없다. 따라서 그냥 g는 1+nR1 이 되고 따라서 R1의 값을 구해낼 수 있다. 그러면 seed 값을 알게되어 이 뒤에 모든 R 값을 알 수 있게 된다.

다음과 같은 수식이 성립하고 또한 nR1f(x)는 n^2 을 넘을 수 없으므로,

이다.

f 값을 구하면 이 다음은 연립방정식을 풀면된다. sage도 익숙해질겸 matrix를 생성해서 flag를 구하였다.

Exploit Code

#!/usr/bin/sage
from sage.all import *
from Crypto.Util.number import *
from fractions import *

class PRNG256(object):
    def __init__(self, seed):
        self.mask = (1 << 256) - 1
        self.seed = seed & self.mask

    def _pick(self):
        b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b

    def rand(self):
        x = 0
        for i in range(256):
            x = (x << 1) | self._pick()
        return x

pubkey = [[1341233826702376842498119940039016826282055747303464974435594326637538907180149241566365225911074218597539880291426265503244204409536388336349105099303221252199164187921036400118788488925884552440483653638244202969641876448593915624469362160298646189903056069767976491733960779483023305191435635289734365528710722401088230332490023131911734288011232016872906051832164035804891447455672110954242647111735228814935698789659541198379357658233047482430645842400366769, 26674131724614738833784434076708623929346303545393320399944409878863187402150503055207795853307211144249179748395076848334742855586049336411971031238044174387954252693537728148985955948048292029557791508049506146642880016520533230306989498523300220064692662847160710441255197572391506435448482713046019266895261344521636514739951705743608587218033949609867770113753539973249063631220635085754002655371345431327359674264770777710263422098079037291585196293197114766337658570276078577504309446984989309950901135119579313915133962619448102748], [1411836429669183892966134560305538366838547135114531535251720851922638607907850507674940852917802242615202155607148892358461384679202044548831141295353829571829695255020484687938869019916289932148352179781631904110271902114010910086393396910500275240681423526254331492385949217178047157696773667958133033180038804263460584550022281663780195927924119675790311322672399731902027722031296853164002026620552741589967849779933976523556743919696732887883645621044361611, 54901986783642835051699889113428335659585153809842942356885004842920465421336706391742814742564346205356241657334450930082155461145433648171896778260206136182255774717095790534292114459150791413586339545764791219429615253607065582132297246948860985575596282841990693455389149847062253133706015420405086059551754437445312366999921584484205222674268615179520174172834649126131935196501454388399695961162329114143523185659562031324488650262065740579199795214468943489727171700351304387397461071307646615194578618714043441377328663670751933627], [1827670639023479057974423662769264575893916686880865506873460556631343496594640149665454545389837639322275346518374263849034235979447405363606817187890637783196194162726024155794431981524906947485134171466324929779048499566048313669091401079263506127226379009753084566863868890271238236467261185095363669354791741608878314575987029663948818461252180763032199904220494918133642971421746749038691538192915859604276912102975568194119467980419612286906176868952703619, 141955627685405861596265155634043580262274251775483613944451161608579951914157317215316282492132012795129761525653914539354069858559035449093879514616280531615371142125208924414389214738475566668885506757054698120214732427844927492109681218414883961942239601431792698791724207705264637074459890882510377535948407156226101316457666689930453121343643609559536469767469803312169661110669941502466830780526471703979445391121676012137033701185329849968518454602730837677935298633914797575550202371889703865031673251813095889426000075905120210715], [1402052496936016320097183149388969226815975944499402219852856803114088852450193317864886134127265736138410526536722880486066577543930136034727844243512981614084924117627899623040044660188020312540158405739267327536264551679882312483493710047604544613918162585552941665913115010517121759370648692761286982491236666306877105976920137441035714264352280173247224313429635552985171274872512067599818448065403462190853902179488909659352339753894521914217223448955215971, 86436796561750399172835178406595458158200152808363576725949152209752050457844658406574932376510960241857243310231191629391788175840467781934160642603459961684570827889722817126673212897198457329009359718685889481495826330541120466944045405490044949949259866864077324005529448874478602844692164951174440203087657096219194318354305991767616656455848089449159017933275879827733328877162500978230626795632715808168172022720272496925901610663582044355831900584113960342572153829531696471382379336709069115911649499884361699625754418888357105356], [1342704677106999319938700388688741153377785166648218447242877900112547844266669406514804811924511017558918915960330401218483170328967889513789896923310776509048521832125539811902549091395153161067069971385687776610710438852173147435486069694433486331195576027716222479219032032167578074212853391036064686760331515843088926026790746958731708142341497399752153088465594599246790180097507576747721603670126927119225609501504821203851575717696464442894256866979152071, 151778423244836361358618726678490961359665141861531434745037765026759553125937345447572403824004985824284188179016742237419300096576909738404031925822083587101759301624897645367726786635718018753092807084873240915940763159043557284908261185169254084475196021977237239622460403373815939034200532293365581548664725892312716054043939540402460543140481578956351181169010805594314620139932866466533726652277935117332880706565744981667712583109377942817662191762058437395347618376144282145949244368040832594427185427142218601311894439404196869044]]
shares = [[1, 597508787369395694379078055274758557631538862739941784216641187447047696613646680523204534254585433553841883904815873020522119769161150848487658944289025139852884425534715254212765760070437058597554314741974198161950731308938774064571532399460855957695621714795771549456243813779399463109411846725520743344118554521413815793297768851076100135443002760221642947948812785225122631701884241216019284262219988306790748365483241216049579680655534490056279281295122379176443966669667315043992274193717298501474638381448820981658485993472350525815696097401765948865514729845467484551526100202532018343011967560856014086051860031235536215643818290727062383335942089683311730283931932548912461126311217820002459492022071267001562804194559301166310110244724819006466684456151803974731484616982434451280906366032894303395363863415992620820995729046300233942195095878917887892047030748729267329243516360791348477702146680442138382721731], [2, 1456602020473336436595302182756958090511415476510657696986700623481719785551149148046222482541285365312188959543693509514194665154201380523065476755444520574235515226702501340621170242202481024616882142010693536315240074931107987736512086290237614373546387137118763177589626855206838418103751404170044959913691735814429141324338320985853997370723970242452295801714270370307506226450063833723978620621565509156414542500828358085837989711050634637181122088180962097398190523961973415973551114076986713383243786853784427170667899647985426058777600468130304251574650780445218699779580427275505399994170596637813422179447545139427789051628741760457519163521253124217051884027796849542531386743511788474207049545545002209680929220223136064442178057025754413867781284144371821327271523387818972046823739716532656252490038504917848103009173556160906958786293914926056507083575731302212603218169279706378356509037364037831069878231086], [3, 1595390928798835569336924563570335102923880736692143989367168050283822219400199743337809496383236309872055902908859973435410009867512480962418933647220942557496021772016027755153856780432756247783750165029188435931829475752098685139218491512524939261083097196175538068246302620283880442794354650203913256502298415299185414984420565985768541932846631373242689036582178180151029187744659165675733768586790929935335022733816827888717408760672442814312920814112098749134708381258920239270611481275188904733904484814532961896311957117153388398557892281039130937627251977203045005113457955326984992365109238884156875118258875576742912093629961904108637328565523791833431848861487780279931219592300441525537266970002720517825091950356133381996157142667046040400474609347986971206237389511449743320732065481903260813584781835955382208803634275373602785992176618584713593998708722680023507255977968510697362982348044089009664597010849], [4, 1011012847725577745336080393532189501492336190558468303901251128666948418862933107036802327706950463653743889588322849131239222018844807849320331335500253801822404870042943180018988070672118930708294758392176800835465940314497189212667345256623160148381248676718065742459754530766291525548914975338009832256832712589706835806517309607232698495103676951407256990497727674074485975124944372384103938197756270712242538878327377737064117888518506218677244903776303353809628478075251845418928422454505051034628606854452823018144040158582352384256981850775768889499743760124313790601039804655287368427678715298719610014768027055861100647302291703640051847379108339724116217620803865940790490720181318014407063347236752588796661376810081172579531972899972207972694482013181432385593628852052754597961311854114120889315842451116669964549895840227042765846799089720825799247881359370434521814841837587026380076995924399761319705723220], [5, 585069911394639305069783453652980853778745872799905806085352980735658699442233349825102728267563130252863283620016490723644364840781783036228871276919495247201207769697803633760636387168623971368425694237096294184568991213677440659398241600565247753979592046970818227704368395870777535026523567976874952173624307944192305292867662966386645876919788206043645183603762002422420998136405555517112532618282483706131862387809257609229574812285296154253501278056085465591743515177435365781927790199047842732048344042345351145298190659111295473008507446985055866290274758068271147032318530780490684852153963206087326840116434394159695925404604438964668680275485416592324577630006500633520246499405212932824588562414909326852417065336364436077691987208909857190371325101826958691831214195954288881703669647778463778679987622877010187433236808312183932607053247793338457198918138891876330549197934696966944916096701567755521275990739]]

n, g = pubkey[0]
x, y = shares[0]

R1 = (g-1)/n
seed = int(bin(R1)[2:].rjust(256, '0')[::-1], 2)
prng = PRNG256(seed)
prng.rand()

f_x = []
for i in range(1, 4):
    n, g = pubkey[i]
    x, y = shares[i]
    noise = [prng.rand() for _ in range(3)]
    pow_g = inverse(pow(g, noise[0], n*n), n*n)*y*inverse(pow(noise[2], n, n*n), n*n)%(n*n)
    f = (pow_g-1)/(n*noise[1])
    f_x.append(f)

A = matrix(QQ, 3, [1, 2, 4, 1, 3, 9, 1, 4, 16])
b = matrix(QQ, 3, 1, f_x)
x = A.solve_right(b)

print long_to_bytes(x.list()[0])

Capture the Flag

---