Rating:

Official
--------
We are given a x86_64 ELF
- we can Sign a command (allowed ls..., stat..., du... , forbidden cat flag) and get a signature (r,s)
- we can Execute a command if we provide a signature (r,s)

By examining the binary we understand that it signs the command with DSA. The public parameters are hard coded in the binary as strings, while the private parameter is loaded from a file.

This is the signing process:
1. The DSA nonce is generated reading 0x14 bytes from /dev/urandom and stored in a global variable (k), the random bytes are later shuffled during the signing process
2. The input is then read, up to 256 bytes. There is a buffer overflow (at offset 0x1D26): with a 256 byte long input, the first byte of k is overwritten by a null byte
3. k is then shuffled, and the overwritten byte is moved from the first position (k[0]) to the last (k[19])
4. k is interpreted as an hex number

This means that we can reliably and consistently set the least significant byte of k to a fixed amount(0x00).

DSA is vulnerable to faults in the secrets, so even a few constant bits can compromise the private key.

By reading [this paper](https://hal.inria.fr/hal-00777804/document), we decided to implement a lattice attack on the alghorithm.

We estimated that we needed ~70 faulted signatures to be able to implement the attack (and to guarantee that the SVP solution contained the private key).

### Solver

We collected several signatures
```python
from Crypto.PublicKey import DSA

q = 739904609682520586736011252451716180456601329519
sign = [[47817980213997116983990891662989699152988893000, 550778919109238643794725030183918198033267410208, 115707849027963465953307322004337573514841630363], ...
```

We decided to implement a [modified version](https://crypto.stackexchange.com/questions/44644/how-does-the-biased-k-attack-on-ecdsa-work) of the algorithm in the paper which is (allegedly) faster.

The goal is to have `m.LLL(...)[0][-1] == 1`. It the condition is satisfied, we have found the privatekey.

```python
M = []
t = []
u = []

for i in range(len(sign)):
t.append(
(sign[i][1] * pow(sign[i][2] * 2^8, -1, q)) % q
)
u.append(
(-sign[i][0] * pow(sign[i][2] * 2^8, -1, q)) % q
)
M0 = []
for a in t:
M0.append(int(a))
M1 = []
for b in u:
M1.append(int(b))
for i in range(len(sign)):
Mi = [0] * (len(sign) + 2)
Mi[i] = q
M.append(Mi)
M.append(M0 + [1, 0])
M.append(M1 + [0, 1])
from sage.modules.free_module_integer import IntegerLattice
m = IntegerLattice(M)
m.LLL(delta=0.999999999, eta=0.501)[0]
```

Out[]: (...61262266441191146369913672082151254217822682617, 1)

### Final sanity check

If we got it correctly, the following condition should be true:
```python
mx = 61262266441191146369913672082151254217822682617
y = 12813568285675088759086...
g = 52865703933600072480340...
p = 14577437014070574361928...
pow(g, q - mx, p) == y
```

And it is! So we:

1. Set privkey locally to 678642343241329440366097580369564926238778646902 and sign "cat flag"
2. Get a valid signature
3. Execute cat flag on remote
4. ???
5. Profit

Original writeup (https://mhackeroni.it/archive/2018/05/20/defconctfquals-2018-all-writeups.html#official).