Phantom Nonce — PerfectRootCTF Writeup

Flag: r00t{ECDSA_n0nces_fr0m_an_LCG_c0llaps3_t0_a_quadratic_in_d__rhin0_charge}

---

1. Challenge Overview

“To make signing ‘fast and deterministic’, an intern swapped the secure random nonce for a tiny generator: k_{i+1} = (A·k_i + B) mod n.”

Four ECDSA signatures over secp256k1, all nonces generated by a secret LCG. The flag is sealed with a keystream keyed on the recovered private key and LCG parameters.

Item	Description
public_key	secp256k1 point (pubkey, unused for the attack)
signatures	4 × (msg, r, s) — ECDSA with LCG nonces
sealed_flag_hex	flag XORed with a SHA-256 stream keyed on 'kifaru|d|A|B'

---

2. ECDSA primer

For each signature, with message hash h, nonce k, private key d:

r = (k·G).x  mod n
s = k⁻¹ · (h + r·d)  mod n

If the nonce k leaks or is predictable, d = (s·k − h)·r⁻¹ mod n — the whole key collapses. Here the nonces aren’t repeated (so no trivial reuse attack), but they’re related by a known affine recurrence.

---

3. The attack: LCG nonces ⇒ quadratic in d

Rearrange the signature equation to make each nonce affine in d:

k_i = h_i·s_i⁻¹ + r_i·s_i⁻¹ · d  =  u_i + v_i·d      (u_i, v_i known mod n)

The LCG relation between consecutive nonces gives:

k_{i+1} − k_i = (A−1)·k_i + B
k_{i+2} − k_{i+1} = A·(k_{i+1} − k_i)

Let U_j = u_{j+1} − u_j, V_j = v_{j+1} − v_j. Substituting k = u + v·d:

(U_1 + V_1·d) = A·(U_0 + V_0·d)
(U_2 + V_2·d) = A·(U_1 + V_1·d)

Eliminate A by division → a single quadratic equation in d:

(V_2·V_0 − V_1²)·d² + (U_2·V_0 + V_2·U_0 − 2·U_1·V_1)·d + (U_2·U_0 − U_1²) ≡ 0 (mod n)

Solve with the quadratic formula mod n (Tonelli–Shanks for the square root) — two candidate d values; the one that verifies all four signatures is the key.

Then A and B fall out of any two consecutive nonces:

A = (k_3 − k_2)·(k_2 − k_1)⁻¹ mod n
B = (k_2 − A·k_1) mod n

---

4. Unsealing the flag

base = f'kifaru|{d}|{A}|{B}'          # decimal strings
ks0  = sha256(base.encode()).digest() # first 32 bytes of keystream
ks_i = sha256(keystream_so_far).digest()   # running-hash stream
flag  = sealed XOR keystream

The “SHA-256 stream” was a running hash: block 0 = SHA256(base), each next block = SHA256(all previous keystream bytes).

---

5. The solve (Python)

import hashlib, json

# ---------- part 1: recover d, A, B from the signatures ----------
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

sigs = [(hashlib.sha256(s['msg'].encode()).digest(), int(s['r'],16), int(s['s'],16))
        for s in json.load(open('service.json'))['signatures']]

def uv(hh, r, s):
    si = pow(s, -1, n)
    return (hh*si) % n, (r*si) % n

u, v = zip(*[uv(*sg) for sg in sigs])
U = [(u[i+1]-u[i]) % n for i in range(3)]
V = [(v[i+1]-v[i]) % n for i in range(3)]

a2 = (V[2]*V[0] - V[1]*V[1]) % n
a1 = (U[2]*V[0] + V[2]*U[0] - 2*U[1]*V[1]) % n
a0 = (U[2]*U[0] - U[1]*U[1]) % n

def tonelli(x, p):                     # sqrt mod p (p ≡ 1 mod 4 here)
    if pow(x, (p-1)//2, p) != 1: return None
    q, s = p-1, 0
    while q % 2 == 0: q //= 2; s += 1
    z = 2
    while pow(z, (p-1)//2, p) != p-1: z += 1
    m, c, t, r = s, pow(z, q, p), pow(x, q, p), pow(x, (q+1)//2, p)
    while t != 1:
        i, tt = 0, t
        while tt != 1: tt = tt*tt % p; i += 1
        b = pow(c, 1 << (m-i-1), p)
        m, c, t, r = i, b*b % p, t*b*b % p, r*b % p
    return r

rt = tonelli((a1*a1 - 4*a2*a0) % n, n)
d_cands = [(-a1 + r) * pow(2*a2, -1, n) % n for r in (rt, n-rt)]

for d in d_cands:
    k = [pow(s, -1, n) * (hh + r*d) % n for hh, r, s in sigs]
    if k[3] != (0) and all(1 for _ in k):
        pass
    # verify: r must equal (k·G).x mod n
    # (elliptic multiplication omitted here — in practice verify all 4 sigs)
    A = (k[2]-k[1]) * pow((k[1]-k[0]) % n, -1, n) % n
    B = (k[1] - A*k[0]) % n
    if k[3] == (A*k[2]+B) % n:         # LCG relation holds -> d is correct
        break

# ---------- part 2: unseal ----------
sealed = bytes.fromhex(json.load(open('service.json'))['sealed_flag_hex'])
base = f'kifaru|{d}|{A}|{B}'
ks = hashlib.sha256(base.encode()).digest()
while len(ks) < len(sealed):
    ks += hashlib.sha256(ks).digest()  # running-hash stream
flag = bytes(sealed[i] ^ ks[i] for i in range(len(sealed)))
print(flag.decode())

---

6. Key takeaways

1. Nonce-relatedness is as fatal as nonce reuse. Even with a fresh, unpredictable-looking nonce per signature, a linear relationship between them reduces ECDSA to a quadratic equation in d (with 4 signatures, or a lattice solve with fewer).
2. Never derive nonces from a small-state generator. ECDSA requires uniformly random k per signature — deterministic RFC 6979 or CSPRNG only.
3. The affine trick: any ECDSA nonce is expressible as u + v·d from the public signature values — the standard first move in every related-nonce attack.
4. The flag name says it all: “ECDSAs nonces from an LCG collapse to a quadratic in d — rhino charge” (kifaru = rhino in Swahili).

---

Challenge: Phantom Nonce — PerfectRootCTF · Solved: 2026-07-31