[zer0pts CTF 2020] dirty laundry

tags: zer0pts CTF crypto

Challenge Summary

The challenge has the following code:

#!/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)

The challenge is the secret sharing scheme with the paillier encryption. We need to get the PRIME and pure

$f(x)$ velues to solve this.

How to solve

First, we crack the paillier encryption, because it has wierd modulis.

factoring

$n_i$

The paillier encryption has wierd modulis.

$$n_i=next\mathrm{\_}prime(PRIME+nois{e}_i)q_i$$
PRIME is 1024-bit, each noise is 256-bit, and

$q$ is 526-bit. If we define

$p_i\approx PRIME+nois{e}_i$, we can say that

$n_i=(PRIME+nois{e}_i)q_i$. Since

$$\{\begin{array}{l}{n}_1=(PRIME+nois{e}_1)q_1\\ n_2=(PRIME+nois{e}_2)q_2\end{array}$$
as a consequence,

$q_1{n}_2-q_2{n}_1=q_1{q}_{2}nois{e}_2-q_1{q}_{2}nois{e}_1$
(left-hand side is big compared to right-hand side)
We can apply LLL.

Consider the following lattice:

$$\left(\begin{array}{ccccc}{2}^{768}& n_2& n_3& n_4& n_5\\ 0& -n_1& 0& 0& 0\\ 0& 0& -n_1& 0& 0\\ 0& 0& 0& -n_1& 0\\ 0& 0& 0& 0& -n_1\end{array}\right)$$
As a result, the vector in the lattice is equal to

$(2^{278}{q}_1,v_2,v_3,v_4,v_5)$ where

$v_i=(nois{e}_i-nois{e}_1)q_1{q}_i$. We can get

$q_1$ by using LLL.

Therefore, we can calculate

$q_2\sim q_5$(

$q_i=gcd(q_1,(nois{e}_i-nois{e}_1)q_1{q}_i)$).

get noise

By the public key of the paillier encryption,

$$g^{\lambda }=1+k\lambda n$$

$g,\lambda ,n$ are known values so we can get

$k$. Since we were able to find the value of prng, we could extract noise before it was used in paillier (note the order)

get flag

Now, we have noise, so we can calculate pure

$f(x)$ and the correct

$PRIME$. Finally, we can the flag by using lagrange interpolation.

Script:

from sage.all import *
from Crypto.Util.number import inverse, long_to_bytes
from re import compile

with open("./../distfiles/output.txt") as f:
    output = f.read()

pubkey = eval(compile(r"pubkey: (.+)\n").findall(output)[0])
shares = eval(compile(r"shares: (.+)\n").findall(output)[0])

ns = []
gs = []
for n, g in pubkey:
    ns.append(n)
    gs.append(g)

# factoring
print("[+] n bits:", [n.bit_length() for n in ns])
m = matrix(ZZ, 5, 5)
m[0, 0] = 2**768
for i in range(1, m.dimensions()[0]):
    m[0, i] = ns[i]
    m[i, i] = -ns[0]
print("[+] matrix")
for i in range(m.dimensions()[0]):
    print(i, [int(x).bit_length() for x in m[i]])

ml = m.LLL()
print("[+] LLL done")
print("[+] matrix")
for i in range(ml.dimensions()[0]):
    print(i, [int(x).bit_length() for x in ml[i]])

# decrypt and get samples of prng
def dec(c, p, q, g):
    n = int(p) * int(q)
    l = int(lcm(p-1, q-1))
    m = ((pow(c, l, n**2)-1) // n) * inverse((pow(g, l, n**2)-1) // n, n)
    k = ((pow(g, l, n**2) - 1) // n) * inverse(l, n)
    return m % n, k % n

q0 = gcd(abs(ml[0][0]), ns[0])
p0 = ns[0] // q0

qs = [q0]
ps = [p0]
res = dec(shares[0][1], p0, q0, gs[0])
ms = [res[0]]
samples = [res[1]]
for i in range(1, 5):
    qi = gcd(abs(ml[0][i])//q0, ns[i])
    pi = ns[i] // qi
    mi, ki = dec(shares[i][1], pi, qi, gs[i])
    qs.append(qi)
    ps.append(pi)
    ms.append(mi)
    samples.append(ki)

# find noises
def bit_reverse(x):
    y = 0
    for i in range(256):
        y = (y << 1) | ((x >> i) & 1)
    return y

s = bit_reverse(samples[-1])
noises = []
idx = 3
for j in range(13):
    x = 0
    for i in range(256):
        msb = s >> 255
        s <<= 1
        lsb = (msb^(s>>0)^(s>>2)^(s>>5)^(s>>10)^1)&1
        s = (s|lsb) & ((1<<256)-1)
        x = (x << 1) | lsb
    noise = bit_reverse(x)
    if j % 3 == 0:
        noises.append(noise)
    elif j % 3 == 2:
        assert noise == samples[idx]
        idx -= 1
noises.reverse()
print("[+] found all noises")

xy = []
for i in range(5):
    xy.append((i+1, ms[i] - noises[i]))

# find PRIME
prev = previous_prime(ps[0])
for x in range(prev, ps[0]):
    prime = x - noises[0]
    if is_prime(prime):
        R = PolynomialRing(GF(prime), name='x')
        f = R.lagrange_polynomial(xy)
        print("[+] flag:", long_to_bytes(f(0)))