Elliptic curves in CTF: nonce reuse, biased nonces, and invalid curves

Elliptic-curve challenges look intimidating and are usually not. The curve arithmetic is a black box you can import; what breaks is the same class of thing that breaks everywhere else - a value that was supposed to be unique and was not, a parameter nobody validated, or a random number that was slightly less random than it looked.

You need three facts and no geometry. Points on the curve form a group under addition. Scalar multiplication k*G is repeated addition, and it is easy forwards. Recovering k from k*G is the elliptic-curve discrete log, and on a well-chosen curve it is hard. Every attack below avoids solving it.

ECDSA in four lines, because the attacks live in it

sign(m, d):                        verify(m, (r, s), Q):
  k = random nonce                   w  = s^-1 mod n
  R = k*G ;  r = R.x mod n           u1 = H(m)*w ;  u2 = r*w
  s = k^-1 * (H(m) + r*d) mod n      P  = u1*G + u2*Q
  return (r, s)                      return P.x mod n == r

Rearranged: d = (s*k - H(m)) * r^-1 mod n. If you learn `k` for a single signature, you have the private key. That is the entire attack surface, and the next three sections are three ways to learn k.

1. Nonce reuse: two signatures, one line of algebra

If the same k is used for two different messages, the two signatures share the same r - because r depends only on k. That is the detection rule: scan the transcript for a repeated `r`. It is a one-line check and it is the first thing to do with any set of ECDSA signatures.

Given the repeat, subtract the two s equations and d drops out, leaving k:

def recover_from_reuse(r, s1, h1, s2, h2, n):
    k = (h1 - h2) * pow(s1 - s2, -1, n) % n
    d = (s1 * k - h1) * pow(r, -1, n) % n
    return k, d

# If it fails, try the sign variants - some signers normalise s to the
# lower half of the range, which flips the sign of k for that signature.
for s2v in (s2, -s2 % n):
    ...

This is the Sony PlayStation 3 bug and the Android Bitcoin wallet bug, both of which used a constant nonce. In a CTF it usually appears as a signing oracle that will sign anything you ask - sign two things, compare the r values, and you are done. It is the same structural failure as nonce reuse in AES-GCM and as a two-time pad: a value promised to be unique, used twice.

2. Biased nonces: a lattice, not an algebra

A subtler version: the nonce is not repeated, but it is *short*. Maybe the generator produces a 128-bit value used on a 256-bit curve, or the top byte is always zero, or the nonce is a timestamp. Each signature then gives you a linear relation in d where one term is known to be small - and a collection of such relations is exactly the input a lattice reduction wants.

The setup, informally. From s*k = H(m) + r*d, each signature gives k_i = A_i + B_i * d mod n with A_i and B_i computable from public data. If every k_i is smaller than 2^(bits - l), then the vector of k_i values is unusually short in a lattice built from those relations, and LLL or BKZ finds it. Recover any one k_i and you have d.

# Hidden Number Problem lattice, one row per signature plus two.
#   [ n                     ]
#   [    n                  ]
#   [       ...             ]
#   [ B_1  B_2  ...  B_m  K/n   0 ]
#   [ A_1  A_2  ...  A_m   0    K ]
# Reduce, then look for a row whose last entry is +/- K: the private key
# sits in it, scaled.
from fpylll import IntegerMatrix, LLL

def build(As, Bs, n, bound):
    m = len(As)
    M = IntegerMatrix(m + 2, m + 2)
    for i in range(m):
        M[i, i] = n
        M[m, i] = Bs[i]
        M[m + 1, i] = As[i]
    M[m, m] = bound / n
    M[m + 1, m + 1] = bound
    return LLL.reduction(M)

3. Invalid curves and the parameters nobody checked

The addition formulas for a short Weierstrass curve y^2 = x^3 + ax + b never use b. An implementation that accepts a point from you, checks nothing, and multiplies it by its secret scalar will happily do arithmetic on a *different* curve - the one with the same a and whatever b your point implies.

That is exploitable because you get to choose that curve. Pick one whose order has a small prime factor, send a point of that small order, observe the result, and you learn the secret scalar modulo that small factor. Repeat with different small factors and recombine with CRT. This is small-subgroup confinement transplanted onto a curve, and it recovers the full key from a few dozen queries.

1. Choose a small prime q. Search for b' such that the curve y^2 = x^3 + ax + b' has order divisible by q.
2. Find a point P of order exactly q on that curve.
3. Send P. The victim computes d*P, which lives in a group of size q.
4. Brute-force i in [0, q) until i*P matches the response. Now d = i mod q.
5. Repeat for enough distinct small primes that their product exceeds n, then CRT.

Singular curves: not a curve at all

If the discriminant 4a^3 + 27b^2 is zero, the curve is singular and its group is isomorphic to something far easier - the additive group of the field (for a cusp) or the multiplicative group (for a node). The discrete log becomes a division or an ordinary discrete log mod p, both of which you can just compute. Always check the discriminant on a curve you were handed; a challenge that ships custom parameters is often shipping this.

Anomalous and low-embedding-degree curves

• Anomalous: the curve order equals the field size p. Smart's attack solves the discrete log in linear time via the p-adic logarithm. Check E.order() == p - it is one comparison and it ends the challenge.
• Supersingular / low embedding degree: the MOV and Frey-Ruck reductions map the curve's discrete log into a finite field where index calculus applies. Relevant when the embedding degree is small, which pairing-friendly curves have by construction.
• Smooth order: Pohlig-Hellman works on curves exactly as it does mod p. Factor the curve order before anything else.

4. The mistakes around the signature, not in it

Some ECDSA challenges never touch the curve. Worth checking before the maths:

• `s = 0` or `r = 0` accepted. The verifier must reject these. One that does not can be handed a trivially forged signature.
• Signature malleability. (r, s) and (r, n - s) are both valid for the same message. If the application uses the signature bytes as an identifier - a transaction id, a nonce, a cache key - both forms exist and only one is expected.
• Public key recovery. From a signature you can recover up to four candidate public keys. A system that trusts "whoever signed this" without pinning the key can be given a signature that recovers to the key you want.
• The hash, not the signature. If H is MD5 or SHA-1 and you can find a collision, you can transplant a signature between messages. That is a hash problem, not a curve problem.
• The nonce derived from the message. RFC 6979 deterministic nonces are fine. A nonce derived from the message with a *non-secret* function is not: you can compute it, and computing k is the whole game.

Working an EC challenge in order

1. Print the curve parameters. Named curve, or custom?
2. If custom: compute the discriminant (singular?), the order (equal to p? smooth?), and the cofactor.
3. If you have signatures: sort by r and look for a repeat. That single check ends a large fraction of these challenges.
4. Count the signatures. A large set with no repeats suggests bias and a lattice.
5. If you have an interactive endpoint that accepts points: check whether it validates that your point is on the curve. If not, invalid-curve.
6. Check the boring failures - s = 0, malleability, a computable nonce - before building a lattice.
7. Only if all of that is clean is the curve itself the subject, and then it is almost certainly one of the named weak families rather than a genuine ECDLP.

The through-line is that elliptic curves add no new failure modes. They add new *names* for the failure modes you already know from RSA and Diffie-Hellman: an unvalidated input, a smooth group order, and a nonce that was not unique. Recognising which of those you are looking at is most of the work, and it takes about four lines of a Python session.