# tania Writeup

### DEFCON 2019 Quals - crypto 182

#### Understanding the system

After some reversing of the given [binary](tania), we found out that the system **signs and executes commands** by the following rules. The parameter for the system is parsed and stored at [consts.py](consts.py).

1. Commands are signed by [DSA](https://en.wikipedia.org/wiki/Digital_Signature_Algorithm)
- The system only allows us to obtain two signatures(`(r1, s1)`, `(r2, s2)`) by two commands `m1`, `m2`;
- `m1 = "the rules are the rules, no complaints"`
- `m2 = "reyammer can change the rules"`
- Random nonce `k` is generated by linear congruence generaters([LCG](https://en.wikipedia.org/wiki/Linear_congruential_generator))
2. Commands are executed(via `system()`) when successfully vertified.

LCG used for generating random nonce `k` is simulated by the following code. All the parameters `c[i]`s were parsed from the binary.

``` python
# generation of random k
class myrand(object):
def __init__(self):
self.rand1 = randint(0, q)
self.rand2 = randint(0, q)
self.k_init = ((c[6] * self.rand1 + c[7] * self.rand2) + c[8]) % c[9]
self.k_curr = self.k_init

def rand(self):
k1 = self.k_curr
k2 = (c[6] * ((c[0] * k1 + c[1]) % c[2]) + c[7] * ((c[3] * k1 + c[4]) % c[5]) + c[8]) % c[9]
self.k_curr = k2
return k1

def set_value(self, k):
self.k_curr = k
```

#### Vulnerablility: DSA with LCG nonces are dangerous!!!

We must execute command `m = "cat flag"`. We need proper signature pair `(r, s)`, which means we need to recover the secret key `x`. The [paper](https://cseweb.ucsd.edu/~mihir/papers/dss-lcg.pdf) introduces how to carve the lattice `B` for **solving congruence equations with different modulus** and setting up the target vector `Y`. After the construction of lattice `B` then running [LLL](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm) algorithm and Babai's nearest plane algorithm(obtained from [here](http://mslc.ctf.su/wp/plaidctf-2016-sexec-crypto-300/)), we successfully obtained `x` and also nonce `k1` and `k2` which were used for signing `m1` and `m2`. We have to solve the following systems of equations.

``` python
# hash function used for DSA: sha1
[z1, z2] = [int(sha1(m).hexdigest(), 16) for m in [m1, m2]]
-r1 x + k1 s1 = z1 mod q
-r2 x + k2 s2 = z2 mod q
k2 - c[6] v1 - c[7] v2 = c[8] mod c[9]
-c[0] * k1 + v1 = c[1] mod c[2]
-c[3] * k1 + v2 = c[4] mod c[5]
```

We successfully obtained the secret key `x`. The sanity of the private key can be checked by calculating public key from private key(`pow(g, x, p) == y`).

#### Signing arbitrary commands and get the flag

By knowing private key `x` and using random nonce `k`, we can obtain proper signature pair `(r,s)`. We signed `m = "cat flag"` and successfully executed it.

We get the flag:

```
OOO{Th3_RUl3s_0f_m47H_4nD_PP_sh0u1d_4lW4y5_B3_H0n0r3D}
```

exploit driver code: [solve.py](solve.py)

LCG solver: [LCG.sage](LCG.sage)

Original binary: [tania](tania)

Parsed parameters: [consts.py](consts.py)

Recoverd private key: [privkey](privkey)

flag: [flag](flag)

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