Easy DSA — GPN CTF 2024

Description

We don't just hand out our prized flags to everyone. Applicants must prove themselves worthy by sharing cool new recipes with us. For security reasons, these recipes of course need to be signed by us. I have the feeling there might be some logic error here but I just can't figure it out...

Connection: ncat --ssl <host> 443

English summary: The server is an ECDSA signing oracle on curve P-521 (secp521r1). It exposes an interactive menu:

• sign [hex recipe] — returns a signature (s1=r, s2=s) over the recipe.
• get pkey — returns the public key point (x, y).
• flag please — asks for a recipe (hex) that is not in the already-signed list, plus s1 and s2; if standard ECDSA verify() passes, it prints the flag.
• check please — quit.

Goal: produce a valid signature on a recipe we never asked the oracle to sign, i.e. forge a signature, which requires recovering the private key.

Analysis

The implementation (main.py) uses PyCryptodome's ECC on p521. The interesting part is the nonce generator and the signing routine.

Deterministic nonce generator:

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

Signing:

n = int(sk._curve.order)
e = hash_message(message)            # int.from_bytes(sha256(message).digest()) -> 256-bit
z = e & ~(1 << n.bit_length())       # n.bit_length() == 521; clears bit 521 -> z == e (no-op)
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

Two observations:

1. The z masking is a red herring. hash_message returns a 256-bit integer (a SHA-256 digest). n.bit_length() is 521, so ~(1 << 521) only clears bit 521. Bit 521 of a 256-bit value is already 0, so z == e. This is bait to make you look at the wrong place.

2. The nonce is badly biased. secure_random returns int.from_bytes(sha256(...).digest()) % (n-1) + 1. The SHA-256 digest is only 256 bits, and 2^256 < n-1 (n is 521 bits), so the modular reduction never triggers. Every nonce satisfies 1 <= k < 2^256. The top ~265 bits of every nonce are zero.

A biased ECDSA nonce is the classic precondition for a Hidden Number Problem (HNP) lattice attack — the same class of bug as Minerva / CVE-2024-23342 (ecdsa-python). With ~265 bits of bias on a 521-bit curve, only a couple of signatures are needed to recover the private key.

Vulnerability

The nonce k is generated from a 256-bit hash while the curve order n is 521 bits, so k < 2^256 ≪ n. From the signing equation:

s * k = z + r * d   (mod n)
=> k = s^{-1} * z + s^{-1} * r * d   (mod n)

Write this as k_i = t_i * d + u_i (mod n) where t_i = s_i^{-1} * r_i and u_i = s_i^{-1} * z_i. Because each k_i is unusually small (< 2^256), the unknown d is the solution to a Hidden Number Problem: the vector of biased k_i is a short vector in a lattice built from the public (t_i, u_i) pairs and n. Running LLL to reduce the lattice and then CVP (closest vector) to the target (u_i) recovers d. Two signatures suffice given the large bias.

Once d is known, the "not already signed" check is meaningless: we just self-sign any fresh recipe with standard ECDSA and the server's correct verify() accepts it.

Solution

Step by step:

1. Connect over TLS and read the public key Q via get pkey.
2. Request a few signatures (sign) on arbitrary distinct recipes to collect (r, s) pairs.
3. Build the HNP lattice from t_i = s_i^{-1} r_i, u_i = s_i^{-1} z_i (with z_i == e_i == sha256(recipe) as an int), scaled by n // 2^256. Reduce with LLL and solve CVP with fpylll to recover candidate d.
4. Validate the candidate against Q (and try n - d, since the lattice can yield the negation).
5. Self-sign a fresh recipe (deadbeef) that was never sent to the oracle, using standard ECDSA with the recovered d.
6. Submit it to flag please and read the flag.

lattice.py — HNP lattice (LLL + CVP)

from hashlib import sha256
from fpylll import IntegerMatrix, LLL, CVP
from fpylll.fplll.gso import MatGSO

N = 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409
BITS = 256  # nonce upper bound: every nonce k < 2^256

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

def z_of(message):
    e = hash_message(message)
    return e & ~(1 << N.bit_length())  # == e (masking is a no-op)

def recover_d(sigs):
    n = N
    B = 1 << BITS
    ts, us = [], []
    for (msg, r, s) in sigs:
        z = z_of(msg)
        s_inv = pow(s, -1, n)
        ts.append((s_inv * r) % n)
        us.append((-s_inv * z) % n)
    m = len(sigs)
    dim = m + 1
    scale = n // B
    M = IntegerMatrix(dim, dim)
    for i in range(m):
        M[i, i] = n * scale
    for i in range(m):
        M[m, i] = int(ts[i]) * scale
    M[m, m] = 1
    target = [int(us[i]) * scale for i in range(m)] + [0]
    LLL.reduction(M)
    gs = MatGSO(M); gs.update_gso()
    closest = CVP.closest_vector(M, target)
    return abs(closest[-1]) % n

exploit.py — full chain (pwntools + PyCryptodome)

import sys, re
from hashlib import sha256
from pwn import remote
from Crypto.PublicKey import ECC
from lattice import recover_d, z_of, N

def sign_with_d(d, message, k=None):
    n = N
    G = ECC.construct(curve="p521", d=1).pointQ  # d=1 -> Q = G
    if k is None:
        k = int.from_bytes(sha256(message + b"forge").digest()*3, 'big') % (n-2) + 1
    P = k * G
    r = int(P.x) % n
    z = z_of(message)
    s = pow(k, -1, n) * (z + r * d) % n
    return r, s

def main():
    use_ssl = "--ssl" in sys.argv
    io = remote(sys.argv[1], int(sys.argv[2]), ssl=use_ssl, timeout=20)
    io.recvuntil(b"> ")
    io.sendline(b"get pkey")
    line = io.recvuntil(b"> ").decode()
    qx = int(re.search(r"x:\s*(\d+)", line).group(1))
    qy = int(re.search(r"y:\s*(\d+)", line).group(1))
    Q = ECC.construct(curve="p521", point_x=qx, point_y=qy).pointQ
    recipes = [b"\xaa\xaa", b"\xbb\xbb", b"\xcc\xcc"]
    sigs = []
    for rcp in recipes:
        io.sendline(b"sign " + rcp.hex().encode())
        resp = io.recvuntil(b"> ").decode()
        r = int(re.search(r"s1:\s*0x([0-9a-fA-F]+)", resp).group(1), 16)
        s = int(re.search(r"s2:\s*0x([0-9a-fA-F]+)", resp).group(1), 16)
        sigs.append((rcp, r, s))
    G = ECC.construct(curve="p521", d=1).pointQ
    d = None
    for nsig in (2, 3):
        cand = recover_d(sigs[:nsig])
        if int((cand * G).x) == int(Q.x):
            d = cand; break
        if int(((N-cand) * G).x) == int(Q.x):
            d = N-cand; break
    forge_recipe = b"\xde\xad\xbe\xef"
    r, s = sign_with_d(d, forge_recipe)
    io.sendline(b"flag please")
    io.recvuntil(b"recipe (hex): "); io.sendline(forge_recipe.hex().encode())
    io.recvuntil(b"s1 (hex): "); io.sendline(hex(r).encode())
    io.recvuntil(b"s2 (hex): "); io.sendline(hex(s).encode())
    print(io.recvline().decode())

main()

Run:

python3 exploit.py <host> 443 --ssl

The lattice recovered the private key d from just 2 signatures; self-signing a fresh recipe (deadbeef) and submitting it to flag please returned the flag.