# 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 kclass 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 qk2 - 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)