Tags: lcg crypto lll dsa

Rating: 5.0

# 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).