Shattered Nonce

An ECDSA signing oracle on secp256k1 (nc challenge.ctf.uscybergames.com 59683) prints its public key Q on connect, signs any message with sign <hex>, and grants the flag if you submit a valid signature of give_me_the_flag via auth <r> <s>. The "hardening" zeroes the top byte of every nonce, so each nonce satisfies k < 2^248 — an 8-bit bias. Biased ECDSA nonces are exactly the Hidden Number Problem, and ~256/8 ≈ 32 signatures are enough to recover the private key with a lattice.

Solve

1. Confirm the curve: Q lies on secp256k1 (y^2 = x^3 + 7), not P-256. The signing hash is SHA-256 over the raw bytes of the hex message, with z = int(SHA256(msg)) reduced mod n.
2. Collect signatures of distinct messages. For each, s·k ≡ z + r·d (mod n) gives k = s⁻¹z + s⁻¹r·d (mod n). Set A_i = s_i⁻¹ r_i and B_i = s_i⁻¹ z_i, so k_i = A_i·d + B_i (mod n) with 0 ≤ k_i < 2^248.
3. Build the HNP lattice. With bound B = 2^248, the vector (k_0,…,k_{m-1}, d·B/n, B) is a short combination of the rows below, so LLL surfaces it. Read d back from the row whose last coordinate is ±B. Verify d·G == Q.
4. With d known, sign give_me_the_flag under a fresh nonce of your own and submit it. solve.sage:

import json, hashlib, socket, re, os

p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
E  = EllipticCurve(GF(p), [0, 7])
G  = E(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
       0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
Q  = E(0x5391bd684eb4f12e07150fc404b8641866a078621b474c319423f387cafa91d5,
       0xd14371a8ed9952bcae43e42377e4e07b00cfef829ea921217799e9d1efdd4643)
B  = 2^248
HOST, PORT = "challenge.ctf.uscybergames.com", 59683

def rd(sk, until):
    buf = b""
    while until not in buf:
        buf += sk.recv(4096)
    return buf

sk = socket.create_connection((HOST, PORT)); sk.settimeout(8)
rd(sk, b"quit")
sigs = []
for i in range(60):
    msg = "%064x" % i
    sk.sendall(("sign %s\n" % msg).encode())
    m = re.search(rb"r = (0x[0-9a-f]+)\s*s = (0x[0-9a-f]+)", rd(sk, b"s = 0x"))
    sigs.append((msg, int(m.group(1), 16), int(m.group(2), 16)))
sk.close()

m = len(sigs)
A, Bb = [], []
for msg, r, s in sigs:
    z = int.from_bytes(hashlib.sha256(bytes.fromhex(msg)).digest(), "big") % n
    si = inverse_mod(s, n)
    A.append(si * r % n); Bb.append(si * z % n)
M = Matrix(QQ, m + 2, m + 2)
for i in range(m): M[i, i] = n
for i in range(m): M[m, i] = A[i]; M[m + 1, i] = Bb[i]
M[m, m] = QQ(B) / QQ(n); M[m + 1, m + 1] = B

d = None
for row in M.LLL():
    if abs(row[m + 1]) == B:
        cand = int((row[m] * (1 if row[m + 1] == B else -1) * n / B)) % n
        if cand * G == Q: d = cand; break
        if (-cand % n) * G == Q: d = -cand % n; break
assert d is not None, "key recovery failed"

z = int.from_bytes(hashlib.sha256(b"give_me_the_flag").digest(), "big") % n
while True:
    k = int.from_bytes(os.urandom(32), "big") % n
    r = int((k * G)[0]) % n
    s = inverse_mod(k, n) * (z + r * d) % n
    if r and s: break

sk = socket.create_connection((HOST, PORT)); sk.settimeout(8)
rd(sk, b"quit")
sk.sendall(("auth %x %x\n" % (r, s)).encode())
print(rd(sk, b"}").decode(errors="replace"))

5. Run sage solve.sage. Recovered key d = 0x44afc33ae436879801240ce8b0162aaa34f23c3ad146b5fe805ce156f59fa3b0, and the forged signature authenticates.

Flag: SVIUSCG{h1dd3n_numb3r_pr0bl3m_15_n0t_s0_h1dd3n}