Three Tickets

Task description

A Flask app issues ECDSA-signed tickets across three tiers, Silver, Gold and Diamond, each on SECP256k1, each deriving a private key from a different third of the flag.

FLAG[:12] becomes the Silver private key, FLAG[12:16] the Gold private key, FLAG[16:] the Diamond private key, each recovered from that tier’s own leaked (h, r, s) ECDSA signatures.

The common relationship

Every tier shares the same underlying algebra: for a signature (r, s) over message hash h, the nonce k used to produce it satisfies k = A*d + B (mod n), where A = r * s^{-1} mod n and B = h * s^{-1} mod n are both directly computable from the signature, and d is the tier’s private key. What differs between the three tiers is how that tier generates k, and each generation scheme turns out to need its own specific attack.

Silver: a large but still biased nonce

k = rng.getrandbits(256) & ((1 << 244) - 1)

The top 12 bits of every nonce are forced to zero, bounding k below 2^244 on a 256-bit curve. Twelve bits of bias per signature is a small leak, so this tier needs the most signatures of the three, about 25, to recover the key. The attack is a standard scaled Hidden Number Problem lattice: multiplying through by S = 2^244 turns what would otherwise be a lattice with fractional entries into one with pure integers, and the target vector, all of whose entries land near S^2, shows up directly in the reduced basis after LLL on a 27x27 matrix.

Gold: a shorter, more exposed nonce

state = (A * state + C) % (1 << 128)   # 128-bit LCG
rc4_val = (rc4_byte() << 8) | rc4_byte()
return ((state >> 16) << 16) | rc4_val

Combining a 128-bit LCG state with 16 bits from an RC4 keystream still caps the whole nonce at 128 bits, a far more severe bias on a 256-bit curve than Silver’s. The same scaled-lattice HNP construction recovers the key directly from just 4 signatures.

Diamond: a nonce tied directly to the key

return self.priv_key ^ self.rng.getrandbits(64)

Here the nonce isn’t just short, it’s the private key itself, XORed with only 64 random bits, meaning k and d are numerically close (within about 2^64 of each other), not just both small. Substituting e = k - d (so |e| < 2^64) into the signature relation and working with two signatures at once eliminates d algebraically, reducing the problem to a small 2D closest vector problem: build a 2D lattice from the two signatures’ coefficients, LLL-reduce it, then use Babai’s nearest-plane algorithm to find the particular short (e_1, e_2) pair that satisfies both signatures’ relations simultaneously. A subtlety here: Babai’s rounding step needs dividing numbers around 2^384 by a lattice determinant around 2^256, and Python’s native float division only carries 53 bits of precision, nowhere near enough; integer rounding ((2*a + b) // (2*b)) avoids the precision loss entirely.

Putting the three pieces together

Tier	Signatures needed	Technique	Recovered
Silver	about 25	scaled HNP lattice (244-bit bound)	FLAG[:12] = CTF2026[3723
Gold	4	scaled HNP lattice (128-bit bound)	FLAG[12:16] = 9937
Diamond	2	2D CVP via Babai rounding	FLAG[16:] = 1781]

Concatenated: CTF2026[372399371781].

Why three different techniques for one flag

Each tier’s nonce weakness has a genuinely different shape: a large but still-bounded value (Silver), a value an order of magnitude smaller still (Gold), and a value defined by its closeness to the secret itself rather than its absolute size (Diamond). All three reduce to variants of the same underlying Hidden Number Problem, but the right lattice construction, and how many signatures it actually needs, depends on exactly which kind of bias is present.