# 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](service.i64). 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.
```pythondef 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 + 1q = 2 * prime * y0 + 1n = (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.
```0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0000a0df0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00009f610xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000005cb```
Public modulus `n` satifies `(n - 1) % prime == 0` because of upper prime gen logic. By using this fact, brute and obtain `prime`.
```pythonstart = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000
while True:    if (n - 1) % start == 0:        print(start)        exit()    start += 1```
Secondly, guess two 32bit crand values. This is [obvious](https://stackoverflow.com/questions/5574914/srandtimenull-doesnt-change-seed-value-quick-enough) because value of seed is `time(NULL)`. Use ctypes to call `srand()`.
```pythonclass 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 = 0r = 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](http://www.jscoron.fr/publications/bivariate.pdf) may solve the equation.
By using this [great implementation](https://github.com/ubuntor/coppersmith-algorithm) 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.
```pythonX = Y = 2 ** 512 # Estimated size of x0, y0P.<x, y> = PolynomialRing(ZZ)pol = (2 * p0 * x + 1) * (2 * p0 * y + 1) - nx0, y0 = coron(pol, X, Y, k=2, debug=False)[0]assert n == (2 * p0 * x0 + 1) * (2 * p0 * y0 + 1)p = 2 * p0 * x0 + 1q = 2 * p0 * y0 + 1assert p * q == n```
Factors known, get the flag!
```OOO{Be_A_Flexible_Coppersmith}```
Original binary: [service](service)
Exploit code: [solve.py](solve.py), [coppersmith.sage](coppersmith.sage)