# Deterministic ECDSA - FCSC 2020

Category: Writeups
Tags: FCSC , Cryptanalysis , ECDSA

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",
0xEE353FCA5428A9300D4ABA754A44C00FDFEC0C9AE4B1A1803075ED967B7BB73F,
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

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