← All writeups

Crypto

easy-dsa

Category: Crypto Flag: GPNCTF{MaYb3 We 5HoULd h4v3 HireD 4 pr0FEssIoNAL?}

"Challenge around ECDSA."

TL;DR

The service signs arbitrary messages with ECDSA over NIST P-521 and lets us claim a flag if we present a valid signature on a message it has not signed. ECDSA is unforgeable... unless the per-signature nonce k is biased. Here secure_random generates k from a single SHA-256 digest reduced mod n−1, so k ≤ 2^256 while the curve order n ≈ 2^521. That is a ~265-bit nonce bias per signature — a textbook Hidden Number Problem. Collect ~14 signatures, recover the private key d with a lattice attack (using Babai's nearest-plane CVP, not the naive SVP embedding — see the pitfall below), then forge a signature on a fresh recipe.

The Challenge

We're given main.py. The relevant pieces:

secret_key = ECC.generate(curve="p521")
public_key = secret_key.public_key()
secure_namespace = UUID(bytes=b"kitchenexplosion")

def secure_random(sk, message):
    key_id = uuid3(secure_namespace, sk.export_key(format="PEM")).bytes
    msg_id = uuid3(secure_namespace, message).bytes
    random_generator = sha256(key_id)
    random_generator.update(msg_id)
    return int.from_bytes(random_generator.digest()) % (int(sk._curve.order) - 1) + 1

def hash_message(message):
    return int.from_bytes(sha256(message).digest())

def sign(sk, message):
    n = int(sk._curve.order)
    e = hash_message(message)
    z = e & ~(1 << n.bit_length())
    k = secure_random(sk, message)
    P = k * sk._curve.G
    r = P.x % n
    s = pow(k, -1, n) * (z + int(r * sk.d)) % n
    return (int(r), int(s))

Interaction (ncat --ssl <host> 443):

So the goal is an existential forgery: a valid signature on a message we never asked it to sign.

The Vulnerability — a biased nonce

ECDSA's one non-negotiable rule: the nonce k must be uniform and secret over [1, n−1]. Any structure leaks the private key. Look at how k is produced:

random_generator = sha256(key_id)        # SHA-256 state
random_generator.update(msg_id)
return int.from_bytes(random_generator.digest()) % (int(sk._curve.order) - 1) + 1

random_generator.digest() is a SHA-256 output — exactly 32 bytes = 256 bits. The curve order of P-521 is

n ≈ 6.86 × 10^156 ≈ 2^521   (521 bits)

Since 2^256 < n − 1, the reduction % (n−1) does nothing, and

k = digest + 1   ∈   [1, 2^256]

Every nonce is at most 256 bits, but a proper nonce should be ~521 bits. That's a 265-bit leak per signature — an enormous bias.

(There's a second red herring: z = e & ~(1 << n.bit_length()). With n.bit_length() == 521 this clears bit 521 of e. But e = SHA-256(message) is only 256 bits, so bit 521 is already 0 — the mask is a no-op. Both sign and verify apply it identically, so it's irrelevant.)

From bias to Hidden Number Problem

For each signature i we know (r_i, s_i) and z_i = SHA-256(m_i). ECDSA gives:

s_i = k_i^{-1} (z_i + r_i · d)  (mod n)
⇒   k_i = s_i^{-1} z_i + s_i^{-1} r_i · d  (mod n)

Define a_i = z_i · s_i^{-1} mod n and t_i = r_i · s_i^{-1} mod n. Then

k_i = a_i + t_i · d   (mod n),     with    0 < k_i ≤ 2^256 = B.

a_i, t_i are known; d and the k_i are unknown but the k_i are small (< B ≪ n). This is exactly the Hidden Number Problem: recover the hidden d given many "a_i + t_i·d mod n is small" relations. Each relation pins ~265 bits of d; with a handful of signatures we have far more than the 521 bits of d, and a lattice finds it.

Exploitation

A pitfall worth documenting: the SVP embedding has a trivial vector

The "standard" HNP recipe builds a lattice whose shortest vector encodes the k_i, then runs LLL. The usual embedding lattice (dimension m+2, scaled by n to stay integer) is

rows 0..m-1:  n²·e_i
row m   (d):  (n·t_0, …, n·t_{m-1},  B,    0  )
row m+1 (c):  (n·a_0, …, n·a_{m-1},  0,   n·B )
target:       (n·k_0, …, n·k_{m-1}, B·d,  n·B )

This does not work here, and it took some debugging to see why. The lattice contains a trivial vector

n·(row m) − Σ t_i·(row i)  =  (0, …, 0, n·B, 0)

— i.e. the α = n multiple of the d-row, with the modular rows cancelling the first m coordinates. Its norm is n·B ≈ 2^777, which is shorter than the genuine HNP target (≈ √(m+2)·2^777). So LLL happily returns this useless vector (and its relatives), and the target encoding d never appears in the reduced basis. Concretely, dumping the reduced basis showed the shortest vector was (0,…,0, ±n·B, 0) and no row yielded d.

The root cause is structural: d is only defined mod n, so α = d and α = d + n differ by exactly that trivial vector. The embedding gives the d-coordinate a full free column, and that freedom manufactures a shorter-than-target vector.

The fix: Babai nearest-plane CVP

Phrase the problem as Closest Vector instead of Shortest Vector (the Nguyen–Shparlinski formulation). No embedding column ⇒ no trivial vector.

Build an (m+1)-dimensional lattice (scaled by n to keep everything integer):

rows 0..m-1:  n²·e_i                       (modular lattice)
row m   (d):  (n·t_0, …, n·t_{m-1},  B)    (the d-direction, weight B on last coord)
target:       (−n·a_0, …, −n·a_{m-1}, 0)

A lattice point is d·(row m) + Σ c_i·(row i) = (n(t_i·d + c_i·n), …, B·d). Choosing the c_i to reduce each coordinate mod n, its distance to the target in coordinate i is n·(a_i + t_i·d − c_i·n) = n·k_i — small. So the lattice vector closest to the target has:

LLL-reduce the basis, run Babai's nearest-plane algorithm to find that closest vector, and read d = (last coordinate) / B. As a belt-and-suspenders check, you can also recover d from any near-zero coordinate via d = (k_i − a_i)·t_i^{-1} mod n and verify d·G == Q against the public key.

This recovers d cleanly and deterministically — validated on 4 independent fresh keys offline before going live (recover=True, forged_verifies=True for all).

The lattice toolkit (pure Python)

No fpylll/Sage needed. attack.py implements:

def recover_d(sigs, n, Q_check=None, mul_check=None, B=1 << 256):
    m = len(sigs)
    ts  = [r * pow(s, -1, n) % n for (z, r, s) in sigs]
    as_ = [z * pow(s, -1, n) % n for (z, r, s) in sigs]

    dim = m + 1
    M = [[0] * dim for _ in range(dim)]
    for i in range(m):
        M[i][i] = n * n
    for i in range(m):
        M[m][i] = n * ts[i]
    M[m][m] = B
    target = [-n * as_[i] for i in range(m)] + [0]

    R = lll(M)
    w = babai(R, target)                       # closest lattice vector
    # w[m] == B*d  ->  d
    d = (w[m] // B) % n
    # ... (also cross-check via each k_i and against the public key) ...
    return d

Forging the signature

Once d is known, forging is trivial — we are now the signer. Pick a fresh recipe (one we never sent to sign), choose any nonce k, and produce a standard ECDSA signature:

forge_msg = b"give-me-the-flag"          # not in already_signed
z = int.from_bytes(sha256(forge_msg).digest()) & ~(1 << n.bit_length())
k = int.from_bytes(os.urandom(66)) % (n - 1) + 1
R = k * G
r = int(R.x) % n
s = pow(k, -1, n) * (z + r * d) % n       # valid signature with the real key

Send flag please → forge_msg → (r, s) and collect the flag.

Full network solver

import socket, ssl, sys, os
from hashlib import sha256
from Crypto.PublicKey import ECC
from attack import recover_d

HOST = sys.argv[1]; PORT = 443; NSIGS = 14
ctx = ssl.create_default_context(); ctx.check_hostname = False; ctx.verify_mode = ssl.CERT_NONE
s = ctx.wrap_socket(socket.create_connection((HOST, PORT)), server_hostname=HOST)

# ... recv_until() / send_line() helpers ...

curve = ECC.generate(curve="p521")._curve
n = int(curve.order); G = curve.G
MASK = ~(1 << n.bit_length())
z_of = lambda m: int.from_bytes(sha256(m).digest()) & MASK

# 1) gather signatures
sigs, signed = [], []
for i in range(NSIGS):
    msg = b"recipe-%d" % i; signed.append(msg)
    recv_until("> "); send_line("sign " + msg.hex())
    recv_until("s1: "); r  = int(recv_until("\n").strip(), 16)
    recv_until("s2: "); sv = int(recv_until("\n").strip(), 16)
    sigs.append((z_of(msg), r, sv))

# 2) public key
recv_until("> "); send_line("get pkey")
recv_until("x: "); qx = int(recv_until("\n").strip())
recv_until("y: "); qy = int(recv_until("\n").strip())
Q = ECC.construct(curve="p521", point_x=qx, point_y=qy).pointQ

# 3) recover private key
d = recover_d(sigs, n, Q_check=Q, mul_check=lambda dd: dd * G, B=1 << 256)

# 4) forge & redeem
forge = b"give-me-the-flag"; z = z_of(forge)
k = int.from_bytes(os.urandom(66)) % (n - 1) + 1
r = int((k * G).x) % n
sg = pow(k, -1, n) * (z + r * d) % n
recv_until("> "); send_line("flag please")
recv_until("recipe (hex): "); send_line(forge.hex())
recv_until("s1 (hex): ");    send_line(hex(r))
recv_until("s2 (hex): ");    send_line(hex(sg))
print(s.recv(4096).decode(errors="replace"))

Run

$ python solve.py pickled-carrot-...-5sbx.gpn24.ctf.kitctf.de
sig 0 ... sig 13
recovering private key via lattice...
recovered d: 0x19584cda05a7f96413a572eb048cbe93da4620d0cc8be721267e67025ebaf754...
forged r=0x93c7e6...  s=0x235566...
Congratulations. Here is your flag: GPNCTF{MaYb3 We 5HoULd h4v3 HireD 4 pr0FEssIoNAL?}

Root Cause & Fix

The fatal mistake is rolling a custom nonce generator that emits only 256 bits of entropy for a 521-bit modulus. ECDSA nonce bias as small as a few bits per signature is already exploitable via lattices; 265 bits is catastrophic — a dozen signatures fully recover the key.

The correct approach is RFC 6979 deterministic ECDSA, which derives k via HMAC-DRBG and produces a full-width, uniformly distributed nonce in [1, n−1]. (pycryptodome's own DSS.new(key, 'deterministic-rfc6979') does this; the home-grown secure_random here should never have existed.) Either way, the nonce must span the entire order, not the output width of whatever hash happened to be convenient.

As the flag concedes: Maybe we should have hired a professional?

Notes / Gotchas