Deterministic ECDSA was a 50 points cryptanalysis challenge at FCSC 2020.

We are given a script, decdsa.py, and an ip/port on which the script is running as a service.

The script allows us to sign messages, using the curve `ANSSIFRP256v1`

.
The goal is to retrieve the private key and sign the message "admin".

# Quick ECDSA recap

ECDSA is a signature scheme, based on elliptic curve.

Given a curve \(E\), with a generator point \(G\) of order \(q\) (ie \(qG = \mathcal{O}\), the point at infinity), the server choose a secret key \(d\). The public key is \(Q = dG\). The curve and the generator point are also public.

To sign a message \(m\), the server computes \(h = \mathcal{H}(m)\), where \(\mathcal{H}\) is a cryptographic hash function, such as SHA256.

Then the server takes a random \(k\), and computes the point \((x,y) = kG\).

It calculates \(r \equiv x \mod q\), and \(s \equiv k^{-1}(h + rd) \mod q\).

The final signature is the pair \((r,s)\).

To verify a message \(m\), one computes \(h = \mathcal{H}(m)\), calculates \(u_1 = hs^{-1} \mod q\) and \(u_2 = rs^{-1} \mod q\). Then computes \((x,y) = u_1G + u_2Q\). If \((x,y) = \mathcal{O}\), the signature is valid.

# What if \(k\) is known

The whole security of the protocol lies on the fact that \(k\) is unknown to the attacker. What if i tell you that if someone manages to get a signature and its associated \(k\), he can recover the private key ?!

Imagine we got a message \(m\), its corresponding signature \((r,s)\) and the corresponding \(k\).

We know that \(s = k^{-1}(h + rd) \mod q\). The private key is \(d\), so lets try to isolate it on the equation :

\(sk \equiv h + rd \mod q \iff d \equiv (sk - h)r^{-1} \mod q\)

As we known all variables on the right, computing \(d\) is easy.

# Back to the challenge

In the challenge, \(k\) is simply the SHA512 of \(m\). That's really bad because its *deterministic*, we can easily recover it knowing a message and its signature.

So basically that's over, here is our plan:

- Signing a message \(m\)
- Computing the \(k\) from \(m\) and its signature \((r,s)\).
- Retrieve the private key \(d\)
- Sign the message "admin", send the signature to the server
- ???
- Profit

Here is a script implementing all of this:

```
from libctf import *
from fastecdsa.curve import Curve
from base64 import b64encode as b64e, b64decode as b64d
from hashlib import sha256, sha512
from Crypto.Util.number import long_to_bytes, bytes_to_long
C = Curve(
"ANSSIFRP256v1",
0xF1FD178C0B3AD58F10126DE8CE42435B3961ADBCABC8CA6DE8FCF353D86E9C03,
0xF1FD178C0B3AD58F10126DE8CE42435B3961ADBCABC8CA6DE8FCF353D86E9C00,
0xEE353FCA5428A9300D4ABA754A44C00FDFEC0C9AE4B1A1803075ED967B7BB73F,
0xF1FD178C0B3AD58F10126DE8CE42435B53DC67E140D2BF941FFDD459C6D655E1,
0xB6B3D4C356C139EB31183D4749D423958C27D2DCAF98B70164C97A2DD98F5CFF,
0x6142E0F7C8B204911F9271F0F3ECEF8C2701C307E8E4C9E183115A1554062CFB
)
mod = C.q
def recover_d(m,r,s):
h = bytes_to_long(sha512(m.encode()).digest())
k = bytes_to_long(sha256(m.encode()).digest())
d = ((s*k) - h) % mod
return (d * invmod(r, mod)) % mod
def sign(C, sk, msg):
ctx = sha256()
ctx.update(msg.encode())
k = int(ctx.hexdigest(), 16)
ctx = sha512()
ctx.update(msg.encode())
h = int(ctx.hexdigest(), 16)
P = k * C.G
r = P.x
assert r > 0, "Error: cannot sign this message."
s = (invmod(k, C.q) * (h + sk * r)) % C.q
assert s > 0, "Error: cannot sign this message."
return (r, s)
io = remote("challenges1.france-cybersecurity-challenge.fr", 2000)
io.recvuntil(b">>>")
io.sendline("antox")
io.recvline() # user tokens
# Retrieve a message and its corresponding signature
m,r,s = b64d(io.recvline().strip().decode()).decode().split("|")
print("Got m,r,s = {},{},{}".format(m,r,s))
r,s = int(r), int(s)
# Compute back the private key from the message and its signature
d = recover_d(m,r,s)
print("Found d = {}".format(d))
# Check that we got the correct d by signing m and checking that we got the same signature
print("Check : {}".format((r,s) == sign(C, d, m)))
# Compute the signature the server want to give the flag
r,s = sign(C, d, "admin")
forged = b64e("{}|{}|{}".format("admin", r,s).encode())
# Send it
io.recvuntil(b">>>")
io.sendline(forged)
# the server should now give us the flag !
for _ in range(10):
print(io.recvline().decode())
```

Executing it :

```
Got m,r,s = antox_#00,21232880318100022565723759902275162500883186467271275936324080295689749345913,45639382291577339757972434772651530474422657875600637520890993325136518503929
Found d = 78593266096774691231960415316042546555024606936601708022173287481629404126627
Check : True
Here is the stored flag: FCSC{2d6d125887b96c90cc3e4243b5d2ed13e0f18caccf117cb923ebf3d1f327c036}
```

and its over :-).