Break: Small Subgroup Attack on the Twist

Module 06 | Breaking Weak Parameters

Even with point validation, if the implementation does not fully check the curve equation, points on the quadratic twist can leak secret key information.

Why This Matters

Every elliptic curve $E: y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ has a companion called the quadratic twist $\tilde{E}$ . An element $x \in \mathbb{F}_p$ either:

gives a point on $E$ (if $x^3 + ax + b$ is a square in $\mathbb{F}_p$ ), or
gives a point on $\tilde{E}$ (if it is a non-square).

If a protocol uses only the $x$ -coordinate (as in X25519-style key exchange), and the implementation does not check which curve the $x$ -coordinate belongs to, an attacker can force computation on the twist.

The twist may have a different group order with small factors. Points of small order on the twist leak $d \bmod q$ just as in the invalid curve attack.

This is why modern curves like Curve25519 are designed to be twist-secure: both the curve and its twist have near-prime order.

The Quadratic Twist

Given $E: y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ , pick any non-square $\delta \in \mathbb{F}_p$ . The quadratic twist is:

\tilde{E}: y^2 = x^3 + a\delta^2 x + b\delta^3

By Hasse's theorem, $|E(\mathbb{F}_p)| = p + 1 - t$ for some $|t| \le 2\sqrt{p}$ . The twist order is:

|\tilde{E}(\mathbb{F}_p)| = p + 1 + t

Together: $|E| + |\tilde{E}| = 2(p + 1)$ . If $E$ has near-prime order, the twist might not.

In [ ]:

# === Setup: a curve whose twist has small subgroups ===
p = 10007
a_coeff = 3
b_coeff = 7
F = GF(p)

E = EllipticCurve(F, [a_coeff, b_coeff])
E_order = E.cardinality()
print(f"Curve E: y^2 = x^3 + {a_coeff}x + {b_coeff} over F_{p}")
print(f"|E(F_p)| = {E_order} = {factor(E_order)}")

# Compute the trace of Frobenius
t = p + 1 - E_order
print(f"\nTrace of Frobenius: t = p + 1 - |E| = {t}")

# The twist order
twist_order = p + 1 + t
print(f"Twist order: |E_twist| = p + 1 + t = {twist_order}")
print(f"Twist order factorization: {factor(twist_order)}")
print(f"\nCheck: |E| + |E_twist| = {E_order} + {twist_order} = {E_order + twist_order}")
print(f"       2(p + 1) = {2*(p+1)}")
print(f"       Match? {E_order + twist_order == 2*(p+1)}")

In [ ]:

# Construct the actual twist curve
# Find a non-square delta in F_p
delta = 2
while kronecker(delta, p) != -1:
    delta += 1
print(f"Non-square delta = {delta} (Legendre symbol = {kronecker(delta, p)})")

# Twist: y^2 = x^3 + a*delta^2*x + b*delta^3
a_twist = a_coeff * F(delta)^2
b_twist = b_coeff * F(delta)^3
E_twist = EllipticCurve(F, [Integer(a_twist), Integer(b_twist)])

print(f"\nTwist curve: y^2 = x^3 + {Integer(a_twist)}x + {Integer(b_twist)} over F_{p}")
print(f"|E_twist| = {E_twist.cardinality()} (expected {twist_order})")
print(f"Match? {E_twist.cardinality() == twist_order}")

# Find small prime factors of the twist order
twist_factors = list(factor(twist_order))
small_factors = [(q, e) for q, e in twist_factors if q <= 50]
print(f"\nSmall prime factors of twist order:")
for q, e in small_factors:
    print(f"  {q}^{e} = {q^e}")

Step 1: Find Points of Small Order on the Twist

For each small prime factor $q$ of the twist order, we find a point $P_q$ on $\tilde{E}$ with $\text{ord}(P_q) = q$ by computing $P_q = (|\tilde{E}|/q) \cdot R$ for a random point $R$ .

In [ ]:

# Find points of small order on the twist
twist_small_points = {}  # q -> point of order q

for q, e in small_factors:
    cofactor = twist_order // q
    for attempt in range(50):
        R = E_twist.random_point()
        P_q = cofactor * R
        if P_q != E_twist(0) and q * P_q == E_twist(0):
            twist_small_points[q] = P_q
            break

print("Points of small order on the twist:")
for q in sorted(twist_small_points.keys()):
    P_q = twist_small_points[q]
    print(f"  order {q}: P = {P_q}")
    # Verify
    assert q * P_q == E_twist(0), f"Order check failed for q={q}"
    assert (q-1) * P_q != E_twist(0) or q == 2, f"Not exactly order q"

product_of_primes = prod(twist_small_points.keys())
print(f"\nProduct of small primes: {product_of_primes}")
print(f"Server secret d = {8923}")
print(f"Product > d? {product_of_primes > 8923}")

Step 2: Extract Secret Bits via Scalar Multiplication

In an $x$ -coordinate-only protocol (like X25519), the server receives an $x$ -coordinate and computes $d \cdot P$ using only $x$ -coordinates. If the attacker sends an $x$ that corresponds to a twist point, the server unknowingly computes on the twist.

Since $P_q$ has order $q$ on the twist, $d \cdot P_q$ depends only on $d \bmod q$ . The attacker brute-forces the $q$ possibilities.

In [ ]:

# Server's secret
d_secret = 8923

# Simulate the attack: for each small-order twist point, recover d mod q
partial_results = []

for q in sorted(twist_small_points.keys()):
    P_q = twist_small_points[q]
    
    # Server computes d * P_q on the twist (unknowingly)
    server_result = d_secret * P_q
    
    # Attacker brute-forces d mod q
    for i in range(q):
        if i * P_q == server_result:
            partial_results.append((i, q))
            print(f"q = {q}: d * P_q = {server_result}  ->  d ≡ {i} (mod {q})")
            print(f"         Actual: d mod {q} = {d_secret % q}  "
                  f"{'CORRECT' if i == d_secret % q else 'WRONG'}")
            break

In [ ]:

# Combine with CRT
remainders = [r for r, q in partial_results]
moduli = [q for r, q in partial_results]

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

print("CRT system:")
for r, q in partial_results:
    print(f"  d ≡ {r} (mod {q})")

print(f"\nd_recovered = {d_recovered}")
print(f"d_actual    = {d_secret}")

if mod_product > d_secret:
    print(f"\nFull recovery! Product of moduli ({mod_product}) > d ({d_secret})")
    print(f"Match? {d_recovered == d_secret}")
else:
    print(f"\nPartial recovery: know d mod {mod_product} = {d_recovered}")
    print(f"Need more small primes for full recovery.")
    print(f"Remaining search space: {d_secret // mod_product} candidates")

The Fix: Twist-Secure Curves

A curve is twist-secure if both $E$ and its quadratic twist $\tilde{E}$ have near-prime order (large prime factor in the group order).

Curve25519 (used in X25519 key exchange) was specifically designed for twist security:

	Order	Largest prime factor
Curve25519	$8 \cdot \ell$	$\ell$ is a 252-bit prime
Twist of Curve25519	$4 \cdot \ell'$	$\ell'$ is a 253-bit prime

The cofactors (8 and 4) are tiny and harmless. The twist attack would require brute-forcing a 253-bit DLP, which is infeasible.

Other defenses:

Cofactor multiplication: Multiply received points by the cofactor $h$ to project into the prime-order subgroup, killing small-order components.
Full point validation: Check that $(x, y)$ lies on the correct curve $E$ , not the twist.

In [ ]:

# Compare: a twist-INSECURE curve vs a twist-SECURE curve
print("=== Our example curve (twist-insecure) ===")
print(f"E order:     {E_order} = {factor(E_order)}")
print(f"Twist order: {twist_order} = {factor(twist_order)}")

# Find a twist-secure curve (small example)
# We search for a curve where both E and twist have nearly-prime order
print(f"\n=== Searching for a twist-secure curve over F_{p} ===")
for a_try in range(1, 50):
    for b_try in range(1, 50):
        if (4*a_try^3 + 27*b_try^2) % p == 0:
            continue
        try:
            E_try = EllipticCurve(F, [a_try, b_try])
        except Exception:
            continue
        ord_E = E_try.cardinality()
        t_try = p + 1 - ord_E
        ord_twist = p + 1 + t_try
        
        # Check: largest prime factor is at least half the order
        largest_E = max(q for q, _ in factor(ord_E))
        largest_tw = max(q for q, _ in factor(ord_twist))
        
        if largest_E > ord_E // 8 and largest_tw > ord_twist // 8:
            print(f"Found: y^2 = x^3 + {a_try}x + {b_try}")
            print(f"  E order:     {ord_E} = {factor(ord_E)}")
            print(f"  Twist order: {ord_twist} = {factor(ord_twist)}")
            print(f"  Both orders have large prime factors!")
            print(f"  Twist attack would require brute-forcing ~{largest_tw}")
            break
    else:
        continue
    break

Exercises

secp256k1 twist: The Bitcoin curve secp256k1 has equation $y^2 = x^3 + 7$ over a 256-bit prime field. Compute the twist order (you can use SageMath on a smaller analogue). Does secp256k1's twist have small factors? Is secp256k1 twist-secure?
Cofactor defense: If the server multiplies every received point by the cofactor $h = |E|/n$ before using it, explain why small-subgroup points are mapped to the identity.
Cost analysis: If the twist order has small factors $q_1, q_2, \ldots, q_k$ , what is the total brute-force cost of the attack? Express it as $\sum q_i$ and compare to a direct ECDLP attack of cost $\approx \sqrt{n}$ .

Summary

Aspect	Detail
Vulnerability	Server processes points on the quadratic twist without validation
Root cause	$x$ -only protocols cannot distinguish curve points from twist points
Attack	Find small-order points on twist; extract $d \bmod q$ per query; combine with CRT
Twist order	$\|\tilde{E}\| = p + 1 + t$ where $t$ is the trace of Frobenius
Twist-secure	Both $E$ and $\tilde{E}$ have near-prime order (e.g., Curve25519)
Fix	Use twist-secure curves; validate points; cofactor multiplication

The twist attack teaches a subtle lesson: security depends not just on the curve you chose, but also on the curve you did not choose. The quadratic twist is an invisible companion that can undermine security if not accounted for in the curve selection and implementation.

Back to Module 06: Elliptic Curves