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 process2. 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 byte3. 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```pythonfrom Crypto.PublicKey import DSA
q = 739904609682520586736011252451716180456601329519sign = [[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.
```pythonM = []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 IntegerLatticem = 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:```pythonmx = 61262266441191146369913672082151254217822682617y = 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 signature3. Execute cat flag on remote4. ???5. Profit