Crypto Party 2

Challenge summary

A remote service holds an ECDSA (NIST P-256) private key secret_key, uses it to sign up to 6 attacker-chosen messages (“friend names”), and encrypts the flag with AES-ECB under key = long_to_bytes(secret_key, 32). Each signature’s nonce is:

k = bytes_to_long(str(uuid.uuid4())[:32].encode())

i.e. NOT a proper random 256-bit scalar — it’s the literal ASCII bytes of the first 32 characters of a random UUID4 string.

Vulnerability

A UUID4 string has the fixed layout xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx (y in {8,9,a,b}). Restricting to the first 32 characters and reading the big-endian byte value at each position:

• positions 8, 13, 18, 23 = literal ’-’ (0x2D)
• position 14 = literal ‘4’ (0x34, UUID version)
• position 19 = one of {‘8’,‘9’,‘a’,‘b’} (UUID variant)
• the other 26 positions = an independent random ASCII hex digit, i.e. one of 16 values in {0x30..0x39} u {0x61..0x66}

So k = a known constant (from the fixed bytes) + a sum of 26 (+1 small) per-position “offset” terms, each bounded to a small range and multiplied by a known place-value weight (a power of 256). Effectively only ~106 of k’s 256 bits are unpredictable — this is a biased/partially-known ECDSA nonce, recoverable via the Hidden Number Problem (HNP) and lattice reduction (LLL), using signatures over messages we chose ourselves (so we get h = SHA256(m) for free).

Per-signature relation: s*k = h + r*d (mod n) => k = A + B*d (mod n) with A = h*s^-1 mod n, B = r*s^-1 mod n computable from each captured (m, r, s).

Attack

1. Captured a batch of 6 signatures from one live connection.
2. Modeled each nonce’s 26 unknown hex-digit bytes (and the 1 variant byte) as small non-negative integer offsets from a known base — using the interval relaxation [0,54] per hex-digit slot (not the exact 16-value alphabet) was precise enough; no extra case-splitting needed.
3. Eliminated the shared unknown d by taking pairwise differences of the 6 per-signature HNP relations against a reference signature (signature 0): B_0 * k_a - B_a * k_0 = B_0*A_a - B_a*A_0 (mod n) for a=1..5. This leaves only the small per-signature nonce offsets as unknowns (6 nonces * 27 small unknowns = 162 total), no more direct dependence on the (much larger, ~256-bit-range) secret key inside the lattice target.
4. Built an LLL lattice of dimension 168 (162 “offset” coordinates scaled to read off directly + 5 “equation” coordinates scaled up to force them to exactly 0 + 1 Kannan-embedding coordinate), reduced it with python-flint’s fmpz_mat.lll(). The short vector containing the embedding coordinate at +-weight directly gives all 162 offsets.
5. Reconstructed nonce k_0 from the recovered offsets, then d = (k_0 - A_0) * B_0^{-1} mod n.
6. Sanity-checked every recovered k_i decodes to a structurally valid 32-byte UUID-prefix (dashes/version/variant in the right spots) before trusting the recovered key.
7. key = long_to_bytes(d, 32), AES-ECB-decrypt ct -> flag.

(Note: an earlier attempt that kept d as an explicit ~256-bit unknown directly in the lattice, rather than eliminating it via pairwise differencing first, failed — the embedding target ended up essentially as large as the Gaussian-heuristic shortest-vector estimate, leaving LLL no safety margin. Removing d algebraically before building the lattice was the key fix.)

Lesson

“Looks random” isn’t the same as “is random” — a UUID4 has ~122 bits of real entropy inside a 128-bit-looking, 36-character string, and truncating

• using its ASCII form directly as a nonce leaks the fixed format bytes outright and constrains every other byte to a 16-value alphabet. Any structured/low-entropy ECDSA nonce, even one that “looks like enough bits” at a glance, is a lattice attack waiting to happen once you can collect a handful of signatures.