Tags: coppersmith crypto re
Rating: 2.0
# 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.
```python
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`.
```python
start = 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()`.
```python
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](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.
```python
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](service)
Exploit code: [solve.py](solve.py), [coppersmith.sage](coppersmith.sage)
