home - links - about - /git/ - rss

FCSC 2020 - Deterministic ECDSA [EN]

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(

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()
    k = int(ctx.hexdigest(), 16)

    ctx = sha512()
    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.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

# the server should now give us the flag !
for _ in range(10):

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

Creative Commons License