Break: Invalid Curve Attack

Module 06 | Breaking Weak Parameters

If a server does not validate that received points lie on the curve, an attacker can send points on weaker curves and extract the secret key piece by piece.

Why This Matters

In ECDH, a server receives a public key point from a client and computes a scalar multiplication $d \cdot P$ using its secret key $d$ . But what if the point $P$ does not lie on the expected curve?

The elliptic curve addition formulas for short Weierstrass form $y^2 = x^3 + ax + b$ only use the coefficient $a$ , not $b$ . This means the server will happily compute scalar multiplication on a point from a different curve $y^2 = x^3 + ax + b'$ (same $a$ , different $b$ ) without noticing.

The attacker chooses $b'$ so that the alternative curve has small-order subgroups. A point of small order reveals $d \bmod (\text{small order})$ via brute force. Repeating with different small-order points and combining via CRT recovers the full secret $d$ .

This attack has been demonstrated against real TLS implementations.

In [ ]:

# === The target curve ===
p = 10007
a_coeff = 3
b_coeff = 7

E_target = EllipticCurve(GF(p), [a_coeff, b_coeff])
G = E_target.gens()[0]
n = E_target.cardinality()

print(f"Target curve: y^2 = x^3 + {a_coeff}x + {b_coeff} over F_{p}")
print(f"Curve order: {n} = {factor(n)}")
print(f"Generator G = {G}")

# The server's secret key
d_secret = 8923
Q_public = d_secret * G
print(f"\nServer's secret key: d = {d_secret}")
print(f"Server's public key: Q = {Q_public}")

Step 1: Find Alternative Curves with Small Subgroups

The attacker searches for values $b'$ such that the curve $E': y^2 = x^3 + ax + b'$ has an order divisible by small primes. For each such $b'$ , the attacker finds a point of small prime order on $E'$ .

Key insight: the addition formulas for Weierstrass curves only use $a$ :

x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1

where $\lambda = (y_2 - y_1)/(x_2 - x_1)$ for addition or $\lambda = (3x_1^2 + a)/(2y_1)$ for doubling. The parameter $b$ never appears!

In [ ]:

# Search for alternative curves with small-order subgroups
F = GF(p)

# We want to collect enough small primes to reconstruct d mod (product of primes)
# We need the product of collected primes to exceed d_secret.
target_small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
found_curves = {}  # small_prime -> (b', point of that order)

for b_prime in range(0, p):
    if b_prime == b_coeff:
        continue  # skip the real curve
    # Check that 4a^3 + 27b'^2 != 0 (non-singular)
    if (4 * a_coeff^3 + 27 * b_prime^2) % p == 0:
        continue
    try:
        E_prime = EllipticCurve(F, [a_coeff, b_prime])
    except Exception:
        continue
    order_prime = E_prime.cardinality()
    
    for q in target_small_primes:
        if q in found_curves:
            continue
        if order_prime % q == 0:
            # Find a point of order q
            cofactor = order_prime // q
            # Try random points until we get one of order q
            for _ in range(20):
                try:
                    P_rand = E_prime.random_point()
                    P_q = cofactor * P_rand
                    if P_q != E_prime(0) and q * P_q == E_prime(0):
                        found_curves[q] = (b_prime, P_q)
                        break
                except Exception:
                    pass
    
    # Check if we have enough primes
    product = prod(found_curves.keys()) if found_curves else 0
    if product > p:
        break

print("Found invalid-curve points:")
print("Prime q b_prime Point P Order check")for q in sorted(found_curves.keys()):
    b_prime, P_q = found_curves[q]
    E_check = EllipticCurve(F, [a_coeff, b_prime])
    check = q * P_q == E_check(0)
    print(f"{q} {b_prime} {str(P_q)} {str(check)}")

print(f"\nProduct of primes: {prod(found_curves.keys())}")
print(f"Need at least: {d_secret}")
print(f"Sufficient? {prod(found_curves.keys()) > d_secret}")

Step 2: Query the Vulnerable Server

The attacker sends each small-order point $P_q$ (from curve $E'$ with parameter $b'$ ) to the server. The server computes $d \cdot P_q$ using the standard point addition formulas, which only use $a$ , not $b$ .

Since $P_q$ has order $q$ , the result $d \cdot P_q$ is one of only $q$ possible points. The attacker brute-forces all $q$ possibilities to find $d \bmod q$ .

In [ ]:

def vulnerable_server(client_point_coords, server_secret, a, p):
    """A server that does NOT validate the curve point.
    It just does scalar multiplication using the Weierstrass formulas.
    
    In a real implementation, this would use the formulas that only involve 'a',
    not 'b'. We simulate by computing on the actual curve the point belongs to."""
    x, y = client_point_coords
    F = GF(p)
    # The server doesn't check b! It infers b from the point.
    b_inferred = Integer(F(y)^2 - F(x)^3 - F(a) * F(x))
    E_inferred = EllipticCurve(F, [a, b_inferred])
    P = E_inferred(x, y)
    result = server_secret * P
    return (Integer(result[0]), Integer(result[1]))

# Attack: send each small-order point and brute-force d mod q
partial_results = []  # list of (d mod q, q)

for q in sorted(found_curves.keys()):
    b_prime, P_q = found_curves[q]
    E_prime = EllipticCurve(F, [a_coeff, b_prime])
    
    # Send P_q to the server; get back d * P_q
    result_coords = vulnerable_server(
        (Integer(P_q[0]), Integer(P_q[1])), d_secret, a_coeff, p
    )
    result_point = E_prime(result_coords[0], result_coords[1])
    
    # Brute force: try all i in [0, q-1] until i * P_q == result
    for i in range(q):
        if i * P_q == result_point:
            partial_results.append((i, q))
            print(f"q = {q}: d * P_q = {result_point}, "
                  f"brute force -> d ≡ {i} (mod {q})")
            break

# Verify each partial result
print(f"\nVerification:")
for d_mod_q, q in partial_results:
    print(f"  d mod {q} = {d_mod_q}  "
          f"(actual: d mod {q} = {d_secret % q})  "
          f"{'CORRECT' if d_mod_q == d_secret % q else 'WRONG'}")

Step 3: Combine with CRT to Recover the Full Secret

We now have a system of congruences:

d \equiv d_1 \pmod{q_1}, \quad d \equiv d_2 \pmod{q_2}, \quad \ldots

Since all $q_i$ are distinct primes, they are pairwise coprime. By the Chinese Remainder Theorem (Module 04), there is a unique solution modulo $\prod q_i$ .

In [ ]:

# Combine partial results with CRT
remainders = [d_mod_q for d_mod_q, q in partial_results]
moduli = [q for d_mod_q, q in partial_results]

print("System of congruences:")
for d_mod_q, q in partial_results:
    print(f"  d ≡ {d_mod_q} (mod {q})")

d_recovered = CRT(remainders, moduli)
modulus_product = prod(moduli)

print(f"\n=== CRT Solution ===")
print(f"d_recovered = {d_recovered}")
print(f"d_actual    = {d_secret}")
print(f"Match? {d_recovered == d_secret}")
print(f"\nModulus product: {modulus_product}")
print(f"Solution is unique in [0, {modulus_product})")

# Final verification
Q_check = d_recovered * G
print(f"\nVerification: d_recovered * G = {Q_check}")
print(f"Server's public key Q         = {Q_public}")
print(f"Keys match? {Q_check == Q_public}")

The Fix: Point Validation

The defense is simple: always validate that received points satisfy the curve equation.

Given a point $(x, y)$ , check:

$x, y \in [0, p-1]$
$y^2 \equiv x^3 + ax + b \pmod{p}$ (point is on the correct curve)
The point is not the point at infinity
Optionally: $n \cdot P = \mathcal{O}$ (point is in the correct subgroup)

In [ ]:

def secure_server(client_point_coords, server_secret, E_curve):
    """A server that DOES validate the curve point."""
    x, y = client_point_coords
    p_field = E_curve.base_field().cardinality()
    
    # Validation step 1: coordinates in range
    if not (0 <= x < p_field and 0 <= y < p_field):
        return "REJECTED: coordinates out of range"
    
    # Validation step 2: point on curve
    try:
        P = E_curve(x, y)  # SageMath will raise an error if not on curve
    except TypeError:
        return "REJECTED: point not on curve"
    
    # Validation step 3: not the identity
    if P == E_curve(0):
        return "REJECTED: point at infinity"
    
    # Safe to compute
    result = server_secret * P
    return (Integer(result[0]), Integer(result[1]))

# Test: invalid curve point is rejected
q_test = sorted(found_curves.keys())[0]
b_test, P_test = found_curves[q_test]
result = secure_server(
    (Integer(P_test[0]), Integer(P_test[1])), d_secret, E_target
)
print(f"Invalid curve point ({P_test[0]}, {P_test[1]}):")
print(f"  Server response: {result}")

# Test: valid point is accepted
valid_point = 42 * G
result_valid = secure_server(
    (Integer(valid_point[0]), Integer(valid_point[1])), d_secret, E_target
)
print(f"\nValid curve point ({valid_point[0]}, {valid_point[1]}):")
print(f"  Server response: {result_valid}")

Exercises

Query count: How many server queries does the attack need in total? Express this as a function of the secret key size and the small primes used.
Montgomery curves: The Curve25519 (Montgomery form) key exchange uses only the $x$ -coordinate. Research why the invalid curve attack is harder against X25519.
Subgroup check: Even if the point is on the correct curve, it might be in a small subgroup (if the curve has cofactor $h > 1$ ). Why does checking $n \cdot P = \mathcal{O}$ prevent this?

Summary

Aspect	Detail
Vulnerability	Server does not check if received point lies on the expected curve
Root cause	Weierstrass addition formulas use $a$ but not $b$
Attack	Send points of small order from curves with different $b'$ ; brute force $d \bmod q$ ; combine via CRT
Cost	One query per small prime; brute force at most $q$ values each
Fix	Validate $y^2 = x^3 + ax + b$ for received points; check subgroup membership

The invalid curve attack illustrates a general principle: never trust external input. In cryptographic protocols, every received value must be validated against the expected mathematical structure. A missing check turns the hardness of ECDLP into a trivial CRT computation.

Back to Module 06: Elliptic Curves