coooppersmith Writeup

DEFCON 2020 Quals - crypto 130 - 41 solves

I was told by a cooopersmith that I should send hackers encrypted messages because it is secure. coooppersmith.challenges.ooo 5000

Observation

Reversing is done. There are two steps to get the flag.

1. test(): Guess two consecutive crandom output which seed is time(NULL).
2. getEncFlag(): Obtain encrypted flag and decrypt it.

Prime generation algorithm

Public modulus n = p * q is generated by weird logic. It first gets 60 byte input seed from user, and generate 512 bit prime prime. Below is the genPrime() logic.

def genPrime(seed):
    assert len(seed) <= 120
    v = int(seed, 16)
    l = len(seed)
    shift_val = 4 * (128 - l)
    v8 = v << shift_val
    v7 = 2 ** (shift_val / 2)
    v2 = 0
    for _ in range(100):
        r = randrange(v7)
        prime = r + v8
        while prime >> shift_val == v:
            if isPrime(prime):
                v2 = 1
                break
            prime += 1
        if v2:
            break
    return prime

After that, service uses prime as seed to generate two 1024 bit primes p, q using function genRSAPublicKey(). It iterates until it generates primes with following contraints, where x0, y0 are 512 bit values.

p = 2 * prime * x0 + 1
q = 2 * prime * y0 + 1
n = (2 * prime * x0 + 1) * (2 * prime * y0 + 1) 

Exploit

First send seed as value of 'ff' * 60 The entropy of prime is controlled by seed. If I use maximum value of seed, It becomes feasible to brute and find out the value of prime. When seed has 60 byte length, random r for genPrime() falls in range(65536) and can be easily guessed. Below is the example output of genPrime() in hex.

0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0000a0df
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00009f61
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000005cb

Public modulus n satifies (n - 1) % prime == 0 because of upper prime gen logic. By using this fact, brute and obtain prime.

start = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000

while True:
    if (n - 1) % start == 0:
        print(start)
        exit()
    start += 1

Secondly, guess two 32bit crand values. This is obvious because value of seed is time(NULL). Use ctypes to call srand().

class RandomWrapper():

    def __init__(self, delta, seed=None):
        self.c = ctypes.CDLL('/lib/x86_64-linux-gnu/libc.so.6')
        if seed:
            self.seed = seed - delta
        else:
            self.seed = self.c.time(0) - delta
        pwn.log.info('seed: {}'.format(self.seed))
        self.c.srand(self.seed)
        self.Random = self.c.rand

    def Random(self):
        return self.Random()

delta = 0
r = RandomWrapper(delta)
s = r.Random()
t = r.Random()
ans = (s + t) & 0xffffffff

Now we have c and prime. To factor n = (2 * prime * x0 + 1) * (2 * prime * y0 + 1), I have to find out x0 and y0. Bivariate coppersmith may solve the equation.

By using this great implementation of Coron's reformulation of Coppersmith's algorithm for finding small integer roots of bivariate polynomial over n, I recovered x0 and y0. Below is the polynomial constructed for applicating coppersmith.

X = Y = 2 ** 512 # Estimated size of x0, y0
P.<x, y> = PolynomialRing(ZZ)
pol = (2 * p0 * x + 1) * (2 * p0 * y + 1) - n
x0, y0 = coron(pol, X, Y, k=2, debug=False)[0]
assert n == (2 * p0 * x0 + 1) * (2 * p0 * y0 + 1)
p = 2 * p0 * x0 + 1
q = 2 * p0 * y0 + 1
assert p * q == n

Factors known, get the flag!

OOO{Be_A_Flexible_Coppersmith}

Original binary: service

Exploit code: solve.py, coppersmith.sage

Original writeup (https://github.com/pcw109550/write-up/tree/master/2020/DEFCON/coooppersmith).