Najljepše Latice (Most Beautiful Petals)

Task description

A Flask app issues ECDSA-signed tickets to two kinds of users (one on SECP256k1, one on NIST256p), and the flag is behind an endpoint that needs a JWT signed by the admin.

“Latice” is Croatian for flower petals, not lattice (that would be “rešetka”); the title is a pun on how the word sounds to an English speaker, a direct nod toward the lattice-based attack the task wants.

The weak nonce

Every ECDSA signature needs a fresh, uniformly random nonce k; reuse or bias in that nonce is historically one of the most exploited weaknesses in the whole scheme. Here:

k = (ALPHA * k_base + beta + random.getrandbits(184)) % n

k_base is derived from an HMAC of the current timestamp (around 220 bits once shifted), ALPHA is a small fixed multiplier (about 15 bits), and beta is a small deterministic value from the message length. Genuine randomness only ever contributes 184 bits on top of that. Added together, the whole nonce k never exceeds roughly 236 bits, on a curve whose order n is about 256 bits. That means the top roughly 20 bits of every nonce are always zero, a fixed bias of about 20 bits relative to what a truly random nonce would need.

Why a biased nonce breaks ECDSA

A biased nonce, one with fewer effective random bits than the curve order, turns recovering the private key into an instance of the Hidden Number Problem: given enough signatures, each one constrains the unknown private key d through a linear relationship involving its own (partially known) nonce, and with enough constraints, LLL lattice reduction can find a short vector in a specially constructed lattice that reveals both the nonces and d itself.

From each signature (r_i, s_i) with message hash h_i, k_i = s_i^{-1} * (h_i + r_i * d) mod n. Since k_i is small (bounded by the known bias), pairs of signatures eliminate the unknown d and reduce to a relation purely between nonces: k_i = t_i * k_0 + u_i (mod n), where t_i and u_i are computable directly from the signatures.

Solving with LLL

Building an (m+1) x (m+1) lattice matrix from m collected signatures, with rows encoding the modular relation (n on the diagonal for reduction rows) and the nonce relation itself in the last two rows, the target short vector, (k_1, ..., k_{m-1}, k_0, B) where B is the known nonce bound, shows up directly in the lattice’s reduced basis after LLL. Once k_0 is recovered from that vector, the private key follows immediately: d = (s_0 * k_0 - h_0) * r_0^{-1} mod n.

With roughly 20 bits of bias per signature, recovering a 256-bit key needs on the order of 256 / 20 ≈ 13 signatures at minimum; collecting 20 (well within the server’s rate limit of one login per second) comfortably clears that.

The exploit

from fpylll import IntegerMatrix, LLL
from ecdsa import SigningKey, SECP256k1
import requests, jwt, time

TARGET = "http://chal.live.hackultet.hr:14010"
n = SECP256k1.order
B = 1 << 236   # the known nonce bound

s = requests.Session()
s.post(f"{TARGET}/register", data={"username": "grower", "password": "pw", "type": "gardener"})

sigs = []
for _ in range(20):
    r = s.post(f"{TARGET}/login", data={"username": "grower", "password": "pw"})
    token = r.json()["token"]
    header, payload, sig = token.split(".")
    r_val, s_val = decode_der_signature(sig)      # r, s from the ECDSA signature
    h_val = sha256_to_int(f"{header}.{payload}")
    sigs.append((h_val, r_val, s_val))
    time.sleep(1)   # the login rate limit

h0, r0, s0 = sigs[0]
a0_inv = pow(r0 * pow(s0, -1, n), -1, n)
m = len(sigs) - 1
mat = IntegerMatrix(m + 2, m + 2)
for i in range(m):
    mat[i, i] = n
for i, (h, r, sv) in enumerate(sigs[1:]):
    a = (r * pow(sv, -1, n)) % n
    b = (h * pow(sv, -1, n)) % n
    t = (a * a0_inv) % n
    u = (b - t * (h0 * pow(s0, -1, n) % n)) % n
    mat[m, i] = t
    mat[m + 1, i] = u
mat[m, m] = 1
mat[m + 1, m + 1] = B

reduced = LLL.reduction(mat)
for row in reduced:
    if abs(row[-1]) == B:
        k0 = row[-2] if row[-1] == B else -row[-2]
        d = ((s0 * k0 - h0) * pow(r0, -1, n)) % n
        break

admin_key = SigningKey.from_secret_exponent(d, curve=SECP256k1)
forged = jwt.encode({"username": "admin", "role": "admin"}, admin_key.to_pem(), algorithm="ES256")
print(s.get(f"{TARGET}/flag", headers={"Authorization": f"Bearer {forged}"}).text)

Trimmed around the actual lattice construction; decode_der_signature and sha256_to_int are small helpers around the standard ecdsa and hashlib calls.

Why “beautiful” bias is still exploitable

The individual pieces of this nonce (a fresh random component, a time-dependent term, a small deterministic offset) look, superficially, like a reasonable attempt to mix in enough unpredictability per signature. What actually matters for ECDSA’s security is not that a nonce contains some randomness, but that it’s effectively indistinguishable from uniform across the full range [0, n); a fixed shortfall of even twenty-some bits, however it arises, is exactly the gap a lattice attack is built to close.