Tags: lcg crypto lll dsa
# 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.
# generation of random k
self.rand1 = randint(0, q)
self.rand2 = randint(0, q)
self.k_init = ((c * self.rand1 + c * self.rand2) + c) % c
self.k_curr = self.k_init
k1 = self.k_curr
k2 = (c * ((c * k1 + c) % c) + c * ((c * k1 + c) % c) + c) % c
self.k_curr = k2
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.
# 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 v1 - c v2 = c mod c
-c * k1 + v1 = c mod c
-c * k1 + v2 = c mod c
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:
LCG solver: [LCG.sage](LCG.sage)
Original binary: [tania](tania)
Recoverd private key: [privkey](privkey)