Tags: crypto paillier rng
Rating:
# Dirty Laundry (crypto, 636p, 14 solved)
Author: SIben
A fun crypto challenge. Realized that my solution was different from the one
already 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 custom
prng. Then, a polynomial `ax^2 + bx + c` in GF(prime) is created, where `c` is
the 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 final
result is encrypted using the Paillier cryptosystem.
Here are the steps I followed to recover the flag.
## Breaking the PRNG
The PRNG implementation is
```python
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
```
Since the state is 256-bits long, and each `_pick` operation consumes 1 bit
from the state, the `rand` function consumes and resets one full state. It is
therefore quite trivial to retrieve the state at a given point in the
computation:
```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 recover
previous output values:
```python
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
```
Now, given any public key `(n, g)` given for the Paillier encryption step, we
are able to retrieve one output of the PRNG by doing:
```python
out = (g - 1) / n
```
The reason this works is because `1 + prng.rand() * n` is systematically
smaller than `n^2`, as `prng.rand()` is 256 bits long, and `n` is 1536 bits
long.
So with this, we know all the values output by `prng.rand()` during the
encryption. Bonus: we know the low 256 bits of `PRIME`, as it is used to
originally seed the PRNG.
## Decrypting the Paillier encryption
```python
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
```
Since we know all the outputs of the PRNG as well as `n`, `g` and `c`, we can
now retrieve:
```python
pow(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 allow
us 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:
```python
g**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:
```python
g**m = 1 + m*k*n [n**2]
```
From that, it's trivial to recover `m`. Here is sample code:
```python
r = 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`. To
retrieve the result of the polynomial evaluation, we just subtract the noise
value that was generated using the broken PRNG.
```python
m = m - noise
```
## Recovering PRIME
Doing the previous step, we can recover the evaluation of the polynomial in
five points, such that we have:
```python
prime = 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, then
we have found a multiple of `PRIME`, most likely with low divisors if any. Good
candidates for this `L` would be `L = x - x` where `x` is represented by two
different values.
I found the following:
```python
# 2a = 6a - 4a
a2p = (2 * m1 + m4 - 3 * m2) - (m4 - m3 - m2 + m1)
# 6a
a6p = (2 * m1 + m4 - 3 * m2)
# 8a
a8n = m5 - m3 - m3 + m1
# 2a = 8a - 6a
a2n = 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 recover
the flag:
```python
inv2 = invert(2, PRIME)
a = (a2p * inv2) % PRIME
b = (m2 - m1 - 3*a) % PRIME
c = (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 file
available below.
# Appendices
## solve.py
```python
from gmpy2 import invert, gcd
# Copy-pasting because I am lazy
shares = ...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 RNG
orig_rng = PRNG256(int(bin(out)[2:].zfill(256)[::-1], 2))
for _ in range(2):
orig_rng.reverse_state()
# RNG at that point in time
rng = PRNG256(int(bin(out)[2:].zfill(256)[::-1], 2))
# Retrieving noise value
for _ 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 - 4a
a2p = (2 * m1 + m4 - 3 * m2) - (m4 - m3 - m2 + m1)
# 6a
a6p = (2 * m1 + m4 - 3 * m2)
# 8a
a8n = m5 - m3 - m3 + m1
# 2a = 8a - 6a
a2n = 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) % PRIME
b = (m2 - m1 - 3*a) % PRIME
c = (m1 - a - b) % PRIME
print(hex(c)[2:].replace('L', '').decode('hex'))
```
## chall.py
```python
#!/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)
```
```python
#!/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 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]]
```
