Dirty Laundry Challenge Writeup [Crypto]

The description of this challenge doesn’t give much information about the challenge. In the given attachments, there are two files chall.py and output.txt.

This challenge is a combination of shamir secret sharing scheme and paillier cryptosystem.

First, it chooses a 1024 bit Prime p, and defines a sharmir secret sharing scheme with flag as the secret with number of shares equal to 5 and k = 3 (i.e requires minimum of 3 shares to obtain the secret). Each of the share(f(x)) is combined with a noise term ei and are encrypted with the paillier cryptosystem. For each share a new key pair of paillier cryptosystem is generated.

we are given the x , encrypted f(x) and correspoding paillier public key [n, g]. Corresponding code snippets are ::

Shamir secret Sharing ::

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

Paillier Encryption code ::

 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

All the noises and random values required for paillier encryption are generated using PRNG256 class defined in chall.py.

In the paillier_enc function, observe that all the public keys ni contains (p + noise(ei)) as a factor. p is same for all the ni.
My intial thought was to use this fact to solve the challenge, but I haven’t got any lead. So, I left that thought and looked for any other ways and I finally took the following approach to solve this challenge.

First step is to decrypt the paillier encrypted shares.
Paillier encryption in this challenge works as follows.

generate n = p*q    (p & q are primes) <br>
generate g = (1 + r1*n) mod n**2   (r1 can be random or equal to 1) <br>
ciphertext = (g**m)*(r2**n) mod n**2   (m is the message we want to encrypt and r2 is a random value). 

To decrypt we would need phi(n) = (p-1)*(q-1) which requires factorization of n.

Another way, we can decrypt the paillier encrypted ciphertext that I used requires the random values r1 and r2.

Given r1, r2 (random values used in paillier encryption) and [n, g] (public key) and ciphertext.
we can obtain (g*m) mod n*2 by multiplying ciphertext c with the inverse of (r2*n) modulo n*2.
given the (g**m) we can obtain the message
m = (g**m - 1)/(r1*n)
The proof of this is

Using the Binomial Expansion 
(1 + r1*n)**x = 1 + x*(r1*n) + (xC2)*(r1*n)**2 + ...
(1 + r1*n)**x mod n**2 = 1 + x*(r1*n) mod n**2

x = (((1 + r1*n)**x) - 1)/(r1*n)

g = (1 + r1*n) 
g**m mod n**2 = (1 + r1*n)**m mod n**2 = 1 + m*(r1*n) mod n**2
m = (g**m - 1)/(r1*n)

we have all the terms except r1 and r2.
we can obtain r1 from g and n.

g = (1 + r1*n) mod n**2 
(1 + r1*n) < n**2. 

As (1 + r1*n) is less than the n**2 the value doesn’t overflow and modulo doesn’t matter.We can obtain the r1
r1 = (g-1)/n.

Remember that all the random values used for the noises and in paillier encrption are generated by PRNG256 class. PRNG256 is a LFSR and contains state of single 256 bit number. PRNG256 contains a method rand which generates bit stream of length 256 and returns the integer. One can easily observe that given a single output of rand() method we can simply generate all the next random values
returned by rand() method.

For each share we can obtain r1 using the above method. r1 and r2 are generated using prng.rand(). so, we can simply obtain r2 too and Using them we can successfully decrypt the paillier encrypted shares.

After the successfully decryption of shares, we doesn’t not obtain the f(x) but f(x) + noise(ei). we have to find the noise term for each share and subtract it from the decrypted (f(x) + ei) for f(x).

Notice that noise terms are also generated using PRNG256 and PRNG256 is not seeded everytime (not seeded for each share).

We are given 5 encrypted shares, we can obtain r1 used in the encryption of first share and generate all the random numbers which are used afterwards. So, In this way we can also generate the noise used for shares 2,3,4,5 and successfully obtain the f(x2), f(x3), f(x4), f(x5).

Along with x2, x3, x4, x5 and f(x2), f(x3), f(x4), f(x5) we also have to know the field in order to extract the secret.
If we know the prime p, we can use lagrange interpolation on the points (xi, f(xi)) over GF(p) and calculating f(0) gives the secret. But we don’t know the prime p.

To obtain the prime p we use the fact that f(x) is quadratic polynomial (degree = 2) and lagrange polynomial gives the lowest degree polynomial.

As degree of f(x) is 2 the coefficient of monomial x**3 in lagrange polynomial should be zero modulo p (i.e multiple of p).

If we have more than 4 shares we can select a random subset of the 4 points and calculate the coefficient of 3rd degree monomial and gcd of all such coefficients would give the p directly and sometimes we would have to remove small factors to obtain prime p.
Here we have only 4 shares we can only obtain a single number which contains p as factor. Lucky for us the coefficient has a very small additional factors and removing them gives our required prime p.

After obtaining p, we can calculate the flag using above mentioned method.

FLAG :: zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}

You can see the implementation of the solution here).

References

1. Shamir’s Secret Sharing
   
2. Paillier Cryptosystem
   
3. Balsn’s Writeup of RCTF 2019 Crypto Challenge f(x)