# Dirty Laundry (crypto, 636p, 14 solved)Author: SIben
A fun crypto challenge. Realized that my solution was different from the onealready published on CTFtime, so decided to contribute a little.
We get the challenge code (**chall.py** below) and its output (**output.txt**below).Essentially, a strong 1024-bit prime is generated, and used to seed a customprng. Then, a polynomial `ax^2 + bx + c` in GF(prime) is created, where `c` isthe flag. This polynomial is then evaluated for `x in [1..5]`. A noisy value(generated using the custom PRNG) is added to this result, and the finalresult is encrypted using the Paillier cryptosystem.
Here are the steps I followed to recover the flag.
## Breaking the PRNG
The PRNG implementation is
```pythonclass 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```
Since the state is 256-bits long, and each `_pick` operation consumes 1 bitfrom the state, the `rand` function consumes and resets one full state. It istherefore quite trivial to retrieve the state at a given point in thecomputation:
```python# Given `out` an output of the PRNG, we reconstruct the PRNG as follows:y = PRNG256(int(bin(out)[2:].zfill(256)[::-1], 2))```
Once the state is retrieved, it's easy to reverse it as well to recoverprevious output values:
```pythondef reverse_state(self):    seed = self.seed    for _ in range(256):        cur = (seed >> 255) & 1        b0 = ((seed >> 1)^(seed >> 4)^(seed>>9)^cur^1)&1        seed = ((seed << 1) | b0) & self.mask
    self.seed = seed```
Now, given any public key `(n, g)` given for the Paillier encryption step, weare able to retrieve one output of the PRNG by doing:
```pythonout = (g - 1) / n```
The reason this works is because `1 + prng.rand() * n` is systematicallysmaller than `n^2`, as `prng.rand()` is 256 bits long, and `n` is 1536 bitslong.
So with this, we know all the values output by `prng.rand()` during theencryption. Bonus: we know the low 256 bits of `PRIME`, as it is used tooriginally seed the PRNG.
## Decrypting the Paillier encryption
```pythondef 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```
Since we know all the outputs of the PRNG as well as `n`, `g` and `c`, we cannow retrieve:
```pythonpow(g, m, n**2) = c * pow(prng.rand(), n, n**2)**(-1) % n**2```
Although this is an instance of the DLP, it has certain properties that allowus to compute it easily (the Paillier cryptosystem actually relies on that).
The rule can be informally given as:
```python(1 + n)**m = 1 + mn [n**2]```
Since `g = 1 + k*n` for some integer `k`, we have that:
```pythong**m = (1 + k*n)**m = 1 + m*k*n [k**2*n**2]```
This is not exactly what we have here but `1 + m*k*n` is still smaller than`n**2` since m is 1024 bits long and k is 256 bits long (1024 + 256 < 1536).Thus, since `k**2*n**2 % n**2 == 0`, we have that:
```pythong**m = 1 + m*k*n [n**2]```
From that, it's trivial to recover `m`. Here is sample code:
```pythonr = pow(rng.rand(), n, n**2)m = (c * invert(r, n**2)) % n**2
assert (m - 1) % (g - 1) == 0
m = (m - 1) / (g - 1)```
With that, we recovered the `m` parameter of the call to `pailler_enc`. Toretrieve the result of the polynomial evaluation, we just subtract the noisevalue that was generated using the broken PRNG.
```pythonm = m - noise```
## Recovering PRIME
Doing the previous step, we can recover the evaluation of the polynomial infive points, such that we have:
```pythonprime = PRIME
m1 = m[0]m2 = m[1]m3 = m[2]m4 = m[3]m5 = m[4]
# x = 1, a    + b   + c = m1 [prime]# x = 2, a*4  + b*2 + c = m2 [prime]# x = 3, a*9  + b*3 + c = m3 [prime]# x = 4, a*16 + b*4 + c = m4 [prime]# x = 5, a*25 + b*5 + c = m5 [prime]```
We are looking for some linear combinations `L`, such that on principle,`L == 0`. However, if we find a case where `L` should be `0` and isn't, thenwe have found a multiple of `PRIME`, most likely with low divisors if any. Goodcandidates for this `L` would be `L = x - x` where `x` is represented by twodifferent values.
I found the following:
```python# 2a  = 6a - 4aa2p = (2 * m1 + m4 - 3 * m2) - (m4 - m3 - m2 + m1)
# 6aa6p = (2 * m1 + m4 - 3 * m2)# 8aa8n = m5 - m3 - m3 + m1
# 2a = 8a - 6aa2n = a8n - a6p
# YAY, it's the prime!PRIME = a2p - a2n
# Bonus: possible to check that the value looks good.assert PRIME % 2**256 == orig_rng.seed % 2**256```
With `PRIME` known and the equations available, it is now trivial to recoverthe flag:
```pythoninv2 = invert(2, PRIME)
a = (a2p * inv2) % PRIMEb = (m2 - m1 - 3*a) % PRIMEc = (m1 - a - b) % PRIME
print(hex(c)[2:].replace('L', '').decode('hex'))```
And we get: `zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}`.
Complete solution, original challenge file and commented challenge fileavailable below.
# Appendices
## solve.py
```pythonfrom gmpy2 import invert, gcd
# Copy-pasting because I am lazyshares = ...snipped...
pubkeys = ...snipped...
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
    def reverse_state(self):        seed = self.seed        for _ in range(256):            cur = (seed >> 255) & 1            b0 = ((seed >> 1)^(seed >> 4)^(seed>>9)^cur^1)&1            seed = ((seed << 1) | b0) & self.mask
        self.seed = seed
# Get output from the first call to prng in paillier:n0, g0 = pubkeys[0]_, c0 = shares[0]
out = (g0 - 1) / n0
# Original seeded RNGorig_rng = PRNG256(int(bin(out)[2:].zfill(256)[::-1], 2))for _ in range(2):    orig_rng.reverse_state()
# RNG at that point in timerng = PRNG256(int(bin(out)[2:].zfill(256)[::-1], 2))
# Retrieving noise valuefor _ in range(2):    rng.reverse_state()
noise = rng.rand()
# Resetting the rng to the right place.for _ in range(1):    g0_base = rng.rand()    assert g0_base * n0 + 1 == g0
r0 = pow(rng.rand(), n0, n0**2)m0 = (c0 * invert(r0, n0**2)) % n0**2
assert (m0 - 1) % (g0 - 1) == 0
m0 = (m0 - 1) / (g0 - 1)m0 = m0 - noise
assert m0 == m0 % n0
m = [m0]noises = [noise]ns = [n0]
for i in range(1, len(pubkeys)):    n, g = pubkeys[i]    _, c = shares[i]
    noise = rng.rand()
    # Skip calls to rng    for _ in range(1):        g_base = rng.rand()        assert g_base * n + 1 == g
    ri = pow(rng.rand(), n, n**2)    mi = (c * invert(ri, n**2)) % n**2
    assert (mi - 1) % (g - 1) == 0    mi = (mi - 1) / (g - 1)    mi = mi - noise
    # Should be the case?    assert mi % n == mi
    m.append(mi)    noises.append(noise)    ns.append(n)
m1 = m[0]m2 = m[1]m3 = m[2]m4 = m[3]m5 = m[4]
# 2a  = 6a - 4aa2p = (2 * m1 + m4 - 3 * m2) - (m4 - m3 - m2 + m1)
# 6aa6p = (2 * m1 + m4 - 3 * m2)# 8aa8n = m5 - m3 - m3 + m1
# 2a = 8a - 6aa2n = a8n - a6p
# YAY, it's the prime!PRIME = a2p - a2n
assert PRIME % 2**256 == orig_rng.seed % 2**256
inv2 = invert(2, PRIME)
a = (a2p * inv2) % PRIMEb = (m2 - m1 - 3*a) % PRIMEc = (m1 - a - b) % PRIME
print(hex(c)[2:].replace('L', '').decode('hex'))```
## chall.py
```python#!/usr/bin/sagefrom 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)```
## commented_chall.py
```python#!/usr/bin/sagefrom 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 is much smaller than n**2, so we can retrieve prng.rand() for each    # share    g = (1 + prng.rand() * n) % n**2    # Here we can find all the m from (1 + n)^x = 1 + nx [n^2]    # <=> (1 + kn)^x = 1 + knx [(kn)^2]    c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2    return n, g, c
# (p * q1) = n1 - (noise1 * q1)
# (p + noise1) * q1 = n1# (p + noise2) * q2 = n2# (p + noise3) * q3 = n3
# given one output of PRNG256.rand(), we retrieve the seed for the next calls# as such:# y = PRNG256(int(bin(out)[2:].zfill(256)[::-1], 2))# earliest we can retrieve is from the first g, by taking out = (g - 1) / n.# Then it can be reverted to find the noise & the low 256 bits of p.# Then the problem is DLP, but an easy instance.
# From the m, we can deduce the shares:# x = 1, a    + b   + c = m1 [prime]# x = 2, a*4  + b*2 + c = m2 [prime]# x = 3, a*9  + b*3 + c = m3 [prime]# x = 4, a*16 + b*4 + c = m4 [prime]# x = 5, a*25 + b*5 + c = m5 [prime]
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 = []    # Loop of length five    for x in range(1, shares+1):        noise = prng.rand()        n, g, y = paillier_enc(f(x) + noise, prime, noise)        pubkey.append([n, g])        # x is the polynomial parameter and c the ciphertext        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)```
## output.txt
```python[+] len(flag): 53[+] pubkey: [[1341233826702376842498119940039016826282055747303464974435594326637538907180149241566365225911074218597539880291426265503244204409536388336349105099303221252199164187921036400118788488925884552440483653638244202969641876448593915624469362160298646189903056069767976491733960779483023305191435635289734365528710722401088230332490023131911734288011232016872906051832164035804891447455672110954242647111735228814935698789659541198379357658233047482430645842400366769, 26674131724614738833784434076708623929346303545393320399944409878863187402150503055207795853307211144249179748395076848334742855586049336411971031238044174387954252693537728148985955948048292029557791508049506146642880016520533230306989498523300220064692662847160710441255197572391506435448482713046019266895261344521636514739951705743608587218033949609867770113753539973249063631220635085754002655371345431327359674264770777710263422098079037291585196293197114766337658570276078577504309446984989309950901135119579313915133962619448102748], [1411836429669183892966134560305538366838547135114531535251720851922638607907850507674940852917802242615202155607148892358461384679202044548831141295353829571829695255020484687938869019916289932148352179781631904110271902114010910086393396910500275240681423526254331492385949217178047157696773667958133033180038804263460584550022281663780195927924119675790311322672399731902027722031296853164002026620552741589967849779933976523556743919696732887883645621044361611, 54901986783642835051699889113428335659585153809842942356885004842920465421336706391742814742564346205356241657334450930082155461145433648171896778260206136182255774717095790534292114459150791413586339545764791219429615253607065582132297246948860985575596282841990693455389149847062253133706015420405086059551754437445312366999921584484205222674268615179520174172834649126131935196501454388399695961162329114143523185659562031324488650262065740579199795214468943489727171700351304387397461071307646615194578618714043441377328663670751933627], [1827670639023479057974423662769264575893916686880865506873460556631343496594640149665454545389837639322275346518374263849034235979447405363606817187890637783196194162726024155794431981524906947485134171466324929779048499566048313669091401079263506127226379009753084566863868890271238236467261185095363669354791741608878314575987029663948818461252180763032199904220494918133642971421746749038691538192915859604276912102975568194119467980419612286906176868952703619, 141955627685405861596265155634043580262274251775483613944451161608579951914157317215316282492132012795129761525653914539354069858559035449093879514616280531615371142125208924414389214738475566668885506757054698120214732427844927492109681218414883961942239601431792698791724207705264637074459890882510377535948407156226101316457666689930453121343643609559536469767469803312169661110669941502466830780526471703979445391121676012137033701185329849968518454602730837677935298633914797575550202371889703865031673251813095889426000075905120210715], [1402052496936016320097183149388969226815975944499402219852856803114088852450193317864886134127265736138410526536722880486066577543930136034727844243512981614084924117627899623040044660188020312540158405739267327536264551679882312483493710047604544613918162585552941665913115010517121759370648692761286982491236666306877105976920137441035714264352280173247224313429635552985171274872512067599818448065403462190853902179488909659352339753894521914217223448955215971, 86436796561750399172835178406595458158200152808363576725949152209752050457844658406574932376510960241857243310231191629391788175840467781934160642603459961684570827889722817126673212897198457329009359718685889481495826330541120466944045405490044949949259866864077324005529448874478602844692164951174440203087657096219194318354305991767616656455848089449159017933275879827733328877162500978230626795632715808168172022720272496925901610663582044355831900584113960342572153829531696471382379336709069115911649499884361699625754418888357105356], [1342704677106999319938700388688741153377785166648218447242877900112547844266669406514804811924511017558918915960330401218483170328967889513789896923310776509048521832125539811902549091395153161067069971385687776610710438852173147435486069694433486331195576027716222479219032032167578074212853391036064686760331515843088926026790746958731708142341497399752153088465594599246790180097507576747721603670126927119225609501504821203851575717696464442894256866979152071, 151778423244836361358618726678490961359665141861531434745037765026759553125937345447572403824004985824284188179016742237419300096576909738404031925822083587101759301624897645367726786635718018753092807084873240915940763159043557284908261185169254084475196021977237239622460403373815939034200532293365581548664725892312716054043939540402460543140481578956351181169010805594314620139932866466533726652277935117332880706565744981667712583109377942817662191762058437395347618376144282145949244368040832594427185427142218601311894439404196869044]][+] shares: [[1, 597508787369395694379078055274758557631538862739941784216641187447047696613646680523204534254585433553841883904815873020522119769161150848487658944289025139852884425534715254212765760070437058597554314741974198161950731308938774064571532399460855957695621714795771549456243813779399463109411846725520743344118554521413815793297768851076100135443002760221642947948812785225122631701884241216019284262219988306790748365483241216049579680655534490056279281295122379176443966669667315043992274193717298501474638381448820981658485993472350525815696097401765948865514729845467484551526100202532018343011967560856014086051860031235536215643818290727062383335942089683311730283931932548912461126311217820002459492022071267001562804194559301166310110244724819006466684456151803974731484616982434451280906366032894303395363863415992620820995729046300233942195095878917887892047030748729267329243516360791348477702146680442138382721731], [2, 1456602020473336436595302182756958090511415476510657696986700623481719785551149148046222482541285365312188959543693509514194665154201380523065476755444520574235515226702501340621170242202481024616882142010693536315240074931107987736512086290237614373546387137118763177589626855206838418103751404170044959913691735814429141324338320985853997370723970242452295801714270370307506226450063833723978620621565509156414542500828358085837989711050634637181122088180962097398190523961973415973551114076986713383243786853784427170667899647985426058777600468130304251574650780445218699779580427275505399994170596637813422179447545139427789051628741760457519163521253124217051884027796849542531386743511788474207049545545002209680929220223136064442178057025754413867781284144371821327271523387818972046823739716532656252490038504917848103009173556160906958786293914926056507083575731302212603218169279706378356509037364037831069878231086], [3, 1595390928798835569336924563570335102923880736692143989367168050283822219400199743337809496383236309872055902908859973435410009867512480962418933647220942557496021772016027755153856780432756247783750165029188435931829475752098685139218491512524939261083097196175538068246302620283880442794354650203913256502298415299185414984420565985768541932846631373242689036582178180151029187744659165675733768586790929935335022733816827888717408760672442814312920814112098749134708381258920239270611481275188904733904484814532961896311957117153388398557892281039130937627251977203045005113457955326984992365109238884156875118258875576742912093629961904108637328565523791833431848861487780279931219592300441525537266970002720517825091950356133381996157142667046040400474609347986971206237389511449743320732065481903260813584781835955382208803634275373602785992176618584713593998708722680023507255977968510697362982348044089009664597010849], [4, 1011012847725577745336080393532189501492336190558468303901251128666948418862933107036802327706950463653743889588322849131239222018844807849320331335500253801822404870042943180018988070672118930708294758392176800835465940314497189212667345256623160148381248676718065742459754530766291525548914975338009832256832712589706835806517309607232698495103676951407256990497727674074485975124944372384103938197756270712242538878327377737064117888518506218677244903776303353809628478075251845418928422454505051034628606854452823018144040158582352384256981850775768889499743760124313790601039804655287368427678715298719610014768027055861100647302291703640051847379108339724116217620803865940790490720181318014407063347236752588796661376810081172579531972899972207972694482013181432385593628852052754597961311854114120889315842451116669964549895840227042765846799089720825799247881359370434521814841837587026380076995924399761319705723220], [5, 585069911394639305069783453652980853778745872799905806085352980735658699442233349825102728267563130252863283620016490723644364840781783036228871276919495247201207769697803633760636387168623971368425694237096294184568991213677440659398241600565247753979592046970818227704368395870777535026523567976874952173624307944192305292867662966386645876919788206043645183603762002422420998136405555517112532618282483706131862387809257609229574812285296154253501278056085465591743515177435365781927790199047842732048344042345351145298190659111295473008507446985055866290274758068271147032318530780490684852153963206087326840116434394159695925404604438964668680275485416592324577630006500633520246499405212932824588562414909326852417065336364436077691987208909857190371325101826958691831214195954288881703669647778463778679987622877010187433236808312183932607053247793338457198918138891876330549197934696966944916096701567755521275990739]]```