WACon 2022 Quals: RSA Secret Sharing

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-chal.py

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-exploit.py

 

RSA Secret Sharing: by rkm0959 (2 solves in General, 1 solve in Junior)

ON 2-out-of-3 SECRET SHARING BASED ON RSA - MemeCrypt 2022

 

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import string, signal, random, hashlib 
signal.alarm(1500)
 
def gen_pow():
    print("Solve PoW plz")
    s = ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(16))
    print(s)
    answer = input()
    hash = bytes_to_long(hashlib.sha256((s + answer).encode()).digest())
    if hash != (hash >> 26) << 26:
        exit() 
 
gen_pow()
q = getPrime(342)
print("q = {}".format(q))
 
class LCG:
    def __init__(self, a, x, b):
        self.a = a
        self.x = x 
        self.b = b 
    def fetch(self):
        ret = self.x
        self.x = (self.a * self.x + self.b) % q 
        return ret 
    
print("Hello! You are the owner of one Share Generator! Please insert your parameters :)")
a = int(input()) % q
x = int(input()) % q
b = int(input()) % q
 
assert 1 <= a < q and 1 <= x < q and 1 <= b < q 
 
LCG1 = LCG(a, x, b)
LCG2 = LCG(random.randint(1, q-1), random.randint(1, q-1), random.randint(1, q-1))
LCG3 = LCG(random.randint(1, q-1), random.randint(1, q-1), random.randint(1, q-1))
 
# in Junior Division, LCG2.a was given additionally
 
def roll():
    return LCG3.fetch() * q * q + LCG2.fetch() * q + LCG1.fetch()
 
def checkFactor(n):
    u = int(input())
    v = int(input())
    assert 1 < u < n and 1 < v < n and u * v == n
 
pr = []
 
while len(pr) < 8:
    p = roll()
    if isPrime(p):
        pr.append(p)
 
n1 = pr[0] * pr[1]
n2 = pr[2] * pr[3]
n3 = pr[4] * pr[5]
n4 = pr[6] * pr[7]
 
print(n1)
print(n2)
print(n3)
print(n4)
 
checkFactor(n1)
checkFactor(n2)
checkFactor(n3)
checkFactor(n4)
 
flag = open("flag", "r").read()
print(flag)

 

Solution

Denote $a_i, x_i, b_i$ to be the initial LCG parameters of $LCG_i$. Denote $LCG_{i, j}$ to be the $j$th value that $i$th LCG generated. 

Note that we control $a_1, x_1, b_1$. We see that with $a_i \not\equiv 1 \pmod{q}$, $$LCG_{i, j} \equiv a_i^j x_i + \frac{a_i^j - 1}{a_i - 1} b_i \equiv a_i^j \left(x_i + \frac{b_i}{a_i - 1} \right) - \frac{b_i}{a_i-1} \pmod{q}$$

We are generating roughly $1024$ bit primes, so with heuristics on prime gap we may assume that we will get our 8 primes generated in our first 6000 tries. Our first goal is to find out which of those 6000 tries were the ones that we actually generated a prime successfully.

 

To do so, we send random $a = a_1, x = x_1, b = b_1$ to the server. This generates random enough values for the LCG we control, and these LCG values will be the value of our primes modulo $q$. For each $n$, there will be two indices $u, v$ such that $$n \equiv LCG_{1, u} \cdot LCG_{1, v} \pmod{q}$$ and we may find these $u, v$ via simple brute force. 

 

Now we move on to finding the parameters for LCG2, the second LCG. If two indices $u, v$ generated $n$, we see $$n \equiv (LCG_{2, u} q + LCG_{1, u})(LCG_{2, v}q + LCG_{1, v}) \pmod{q^2}$$ and with the knowledge of $u, v, LCG_{1, u}, LCG_{1, v}$, we can write $$LCG_{1, v} LCG_{2, u} + LCG_{1, u} LCG_{2, v} \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$ Denote $$C \equiv x_2 + \frac{b_2}{a_2 - 1} \pmod{q}, \quad D \equiv - \frac{b_2}{a_2 - 1} \pmod{q}$$ and we can now write, with $LCG_{2, u} \equiv a_2^u C + D \pmod{q}$ and $LCG_{2, v} \equiv a_2^v C + D \pmod{q}$, that $$\left( LCG_{1, v}  a_2^u + LCG_{1, u} a_2^v \right) C + \left( LCG_{1, u} +LCG_{1, v} \right) D  \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$

 

Note that we have four $n$, so four such equations - and we note that $(C, D, -1)$ is orthogonal to $$\left( LCG_{1, v} a_2^u + LCG_{1, u} a_2^v, LCG_{1, u} + LCG_{1, v}, \frac{n - LCG_{1, u} LCG_{1, v}}{q} \right)$$ when considered as vectors in $\mathbb{F}_q^3$. Therefore, given three such vectors, they will be linearly dependent. This can be expressed algebraically by taking three such vectors, making a matrix with them, and then claiming its determinant is zero. 

 

This determinant will be a polynomial of $a_2$ over $\mathbb{F}_q$. There are now two ways to finish.

The first one is to directly factor this polynomial to find its roots. This is efficient enough to solve the challenge.

The second one is to get two such polynomials, using the fact that we are given not three, but four such equations. Then we can simply take the GCD of two polynomials to get a polynomial of much smaller degree. This can be solved to get $a_2$.

 

With $a_2$ calculated, we can solve the linear system to get $C, D$, and then we can solve for $x_2, b_2$ by $$x_2 \equiv C+D \pmod{q}, \quad b_2 \equiv -D(a_2-1) \pmod{q}$$ We can even check for validity of $a_2$ by checking if all four $n \pmod{q^2}$ can be recalculated accordingly. 

 

We now have full knowledge of the second LCG. There are now two ways to finish. 

The first one is to use Coppersmith's Attack - since we know 2/3 of each primes we can definitely factor each $n$. 

The second one is to apply this same logic to the third LCG - the details are practically the same. 

 

from sage.all import *
from pwn import * 
from tqdm import tqdm 
import random as rand
from Crypto.Util.number import inverse
 
conn = remote("175.123.252.200", 6666)
 
conn.recvline()
s = conn.recvline().rstrip().decode()
assert len(s) == 16
 
for i in tqdm(range(1 << 28)):
    t = str(i)
    hash = hashlib.sha256((s + t).encode()).hexdigest()
    if hash[-6:] == "000000" and hash[-7] in "048c": 
        conn.sendline(t.encode())
        break
 
q = int(conn.recvline().split()[-1])
conn.recvline()
 
a_mine = rand.randint(1, q - 1)
x_mine = rand.randint(1, q - 1)
b_mine = rand.randint(1, q - 1)
 
conn.sendline(str(a_mine).encode())
conn.sendline(str(x_mine).encode())
conn.sendline(str(b_mine).encode())
 
n1 = int(conn.recvline())
n2 = int(conn.recvline())
n3 = int(conn.recvline())
n4 = int(conn.recvline())
 
n1q = n1 % q 
n2q = n2 % q
n3q = n3 % q 
n4q = n4 % q 
 
n1qq = n1 % (q * q)
n2qq = n2 % (q * q)
n3qq = n3 % (q * q)
n4qq = n4 % (q * q)
 
targets = [n1, n2, n3, n4]
targetsq = [n1q, n2q, n3q, n4q]
targetsqq = [n1qq, n2qq, n3qq, n4qq]
 
dat = [x_mine]
for i in range(0, 10000):
    dat.append((a_mine * dat[-1] + b_mine) % q)
 
dic = {}
for i in range(10000):
    dic[dat[i]] = i
 
idx = [(-1, -1)] * 4
for i in range(10000):
    for j in range(4):
        target = (targetsq[j] * inverse(dat[i], q)) % q
        if target in dic.keys():
            other = dic[target]
            if other < i:
                idx[j] = (other, i)
            else:
                idx[j] = (i, other)
 
print(idx)
 
st = time.time()
POL = PolynomialRing(GF(q), 'a')
a = POL.gen()
 
f1 = dat[idx[0][1]] * a ** idx[0][0] + dat[idx[0][0]] * a ** idx[0][1]
f2 = dat[idx[1][1]] * a ** idx[1][0] + dat[idx[1][0]] * a ** idx[1][1]
f3 = dat[idx[2][1]] * a ** idx[2][0] + dat[idx[2][0]] * a ** idx[2][1]
 
c1 = dat[idx[0][1]] + dat[idx[0][0]]
c2 = dat[idx[1][1]] + dat[idx[1][0]]
c3 = dat[idx[2][1]] + dat[idx[2][0]]
 
v1 = ((n1 % (q * q) - dat[idx[0][1]] * dat[idx[0][0]]) // q) % q
v2 = ((n2 % (q * q) - dat[idx[1][1]] * dat[idx[1][0]]) // q) % q
v3 = ((n3 % (q * q) - dat[idx[2][1]] * dat[idx[2][0]]) // q) % q
 
det = f1 * c2 * v3 + f2 * c3 * v1 + f3 * c1 * v2 - f1 * c3 * v2 - f2 * c1 * v3 - f3 * c2 * v1 
det = det // (a ** idx[0][0])
 
while det(1) == GF(q)(0):
    det = det // (a - 1)
print("degree : ", det.degree())
a_cand = det.roots()
print(a_cand)
en = time.time()
 
print("took {} seconds".format(en - st))
 
for root, mult in a_cand:
    a_final = root 
    F1 = int(f1(a_final))
    F2 = int(f2(a_final))
    F3 = int(f3(a_final))
 
    C = ((v1 * c2 - v2 * c1) * inverse(F1 * c2 - F2 * c1, q)) % q
    D = ((v1 - F1 * C) * inverse(c1, q)) % q 
    assert (F1 * C + c1 * D - v1) % q == 0
    assert (F2 * C + c2 * D - v2) % q == 0
 
    x_final = (C + D) % q 
    b_final = (-D * (int(a_final) - 1)) % q 
 
    dat_final = [x_final]
    for i in range(10000):
        dat_final.append((int(a_final) * dat_final[-1] + b_final) % q)
    
    ok = True 
    for i in range(4):
        pr1q2 = dat_final[idx[i][0]] * q + dat[idx[i][0]]
        pr2q2 = dat_final[idx[i][1]] * q + dat[idx[i][1]]
        if (pr1q2 * pr2q2) % (q * q) != targetsqq[i]:
            ok = False 
    
    if ok:
        for i in range(4):
            pr1q2 = dat_final[idx[i][0]] * q + dat[idx[i][0]]
            pr2q2 = dat_final[idx[i][1]] * q + dat[idx[i][1]]
            
            POL = PolynomialRing(Zmod(targets[i]), 'x')
            x = POL.gen()
            f = x * q * q + pr1q2
            f = f.monic()
            share3 = f.small_roots(X = q, beta = 0.49, epsilon = 0.05)[0]
            
            p = int(share3) * q * q + pr1q2
            conn.sendline(str(p).encode())
            conn.sendline(str(targets[i] // p).encode())
        
        print(conn.recvline())

 

Comments

To solve the PoW efficiently, instead of doing the entire bytes_to_long you should just check the last 4 bytes of SHA256.

 

Sending random $a_1, x_1, b_1$ rather than $1, 1, 1$ is a bit better because with $1, 1, 1$, you can't really distinguish $3 \cdot 10 = 5 \cdot 6$ and stuff like that. With random values, it's should be possible to show that such collisions occur with a very low probability, with for example Schwartz-Zippel lemma. Proving this in mathematically precise fashion is left as an exercise for the reader. 

 

Before computing GCD or factorizing polynomials, it's helpful to reduce the degrees by dividing out some obvious parts.

 

By giving $a_2$ to the participants of Junior Division, we allow them to go straight into Coppersmith's Attack without setting up for the determinant or doing polynomial stuff. However, the only solver from Junior Division solved this challenge without Coppersmith's Attack. 

 

We note that to solve the problem, we do not need the first and third RNGs to be an LCG. Also, there's no need to let the participants select their values of $a_1, x_1, b_1$. However, letting the participants choose their $a_1, x_1, b_1$ opens up the possibility for other ideas that end up not working. The intended trap was to select $a_1, x_1, b_1$ so that the first LCG always output the same value. This does not help to solve the challenge to the best of author's knowledge. Letting the third RNG to not be an LCG forces the participant to know Coppersmith's Attack - but I did not really want to test this, since finding the $a_2$ part is already hard enough for WACon 2022 Quals. However, for Junior Division, I decided to award the knowledge of Coppersmith's Attack by giving them $a_2$. I think this was reasonable. 

 

It's also possible to solve LCG3 easier than the two methods described in the solution - this is due to the solvers in the Junior Division.

Since we have $$n = (LCG_{3, u} q^2 + LCG_{2, u} q + LCG_{1, u})(LCG_{3, v} q^2 + LCG_{2, v} q+ LCG_{1, v})$$ we can rewrite this as $$n' = \frac{n-(LCG_{2,u}q+LCG_{1,u})(LCG_{2,v}q+LCG_{1,v})}{q^2}$$ $$= LCG_{3,u}LCG_{3,v} q^2 +(LCG_{3,u}LCG_{2,v}+LCG_{3,v}LCG_{2,u})q + (LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}) $$ and now since this value can be calculated as we know $LCG_{1,u},LCG_{1,v},LCG_{2,u},LCG_{2,v},q$. 

 

Let $$\alpha = \left\lfloor \frac{LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}}{q} \right\rfloor$$ This is usually on the order of $q$, but by selecting $a_1 = x_1 = b_1 = 1$ we can force this value to be small, usually less than $10^4$.

 

We now have $$LCG_{3,u}LCG_{1,v} + LCG_{3,v} LCG_{1,u} \equiv n' \pmod{q}$$ and $$LCG_{3,u}LCG_{2,v} + LCG_{3,v}LCG_{2,u} \equiv \lfloor n' / q \rfloor - \alpha \pmod{q}$$ Therefore, if we know $\alpha$, we can solve this using a linear system easily. Since $\alpha$ is in a brute forcable range, we are done. 

 

This is a beautiful solution that I have overlooked, congratulations to the team! It's very cool that this solution uses the exact setup $a_1 = x_1 = b_1 = 1$ that I advised not to do in my second comment above. Of course, this means that they had to deal with a multiple possibilities for the index, i.e. the reason I advised not to use $a_1=x_1=b_1=1$. To see how they did it, consult their writeup in Korean. 

 

I gave participants four $n$ instead of three $n$ to make the knowledge of fast polynomial factorization or SageMath not required.

 

The description "2-out-of-3 secret sharing" comes from Coppersmith's Attack - note that if two share generators collaborate, they can find 2/3 of the primes and therefore can factorize $n$ using Coppersmith's Attack. I thought about making a challenge to check their understanding of why this challenge is about 2-out-of-3 secret sharing, but decided not to do it. Of course, only having one share generator does not allow you to factorize $n$, so this scheme fits the definition of "2-out-of-3 secret sharing". 

 

The flag was 

WACon{we_should_probably_use_a_better_RNG_than_LCG!!!_(and_hopefully_remove_the_trusted_third_party_:wink:)}

which notes that a trusted third party or TEE is required to check the primality of generated values and compute $n$. 

 

One of the solvers from General Division practically never studied cryptography in their life, but they are quite strong players in the Korean competitive programming scene. They actually solved all three cryptography challenges, which is a fascinating feat.

Of course, note that we didn't set challenges that require huge amount of prior knowledge in cryptography.