Elliptic Curve Cryptography Flaws

Elliptic Curve Fundamentals

An elliptic curve over a finite field $\mathbb{F}_p$ is defined by the Weierstraß equation:

$$y^2 \equiv x^3 + ax + b \pmod p$$

Point addition ($P + Q = R$) forms an abelian group. Scalar multiplication ($k \cdot P$) involves adding point $P$ to itself $k$ times.

The security of Elliptic Curve Cryptography (ECC) relies on the Elliptic Curve Discrete Logarithm Problem (ECDLP): given points $P$ and $Q = k \cdot P$, find scalar secret $k$.

---

1. ECDSA Nonce Reuse Attack

ECDSA (Elliptic Curve Digital Signature Algorithm) signs a hash message $m$ using a secret key $d$ and a random per-signature nonce $k$:

$$r = (k \cdot G)_x \pmod n$$ $$s = k^{-1} (h(m) + r \cdot d) \pmod n$$

The Vulnerability

If a signature generator reuses the same nonce $k$ across two signatures for messages $m_1$ and $m_2$:

1. $r_1 = r_2 = r$ (identical $r$ component exposes nonce reuse immediately).
2. Subtract the two signature equations: $$s_1 - s_2 = k^{-1} (h(m_1) - h(m_2)) \pmod n$$
3. Recover nonce $k$: $$k = \frac{h(m_1) - h(m_2)}{s_1 - s_2} \pmod n$$
4. Recover private key $d$: $$d = \frac{s_1 \cdot k - h(m_1)}{r} \pmod n$$

# Python snippet for ECDSA Nonce Reuse Private Key Recovery
from Crypto.Util.number import inverse

def recover_ecdsa_key(r, s1, s2, h1, h2, n):
    # Recover secret nonce k
    k = ((h1 - h2) * inverse(s1 - s2, n)) % n
    # Recover private key d
    d = ((s1 * k - h1) * inverse(r, n)) % n
    return d

---

2. Invalid Curve Attack

In point addition algorithms, if the server receives point $Q = (x, y)$ and computes $k \cdot Q$ without verifying that $y^2 \equiv x^3 + ax + b \pmod p$:

An attacker sends points on an alternative, invalid curve $y^2 = x^3 + ax + b’$ whose order $n’$ is divisible by small primes!

By querying invalid curve points of small order, the attacker recovers $k \pmod{q_i}$ for multiple small primes $q_i$, then combines them using CRT to extract the private scalar $k$.

---

3. Pohlig-Hellman Attack on Weak Order Curves

If the order of the curve $N = #E(\mathbb{F}_p)$ is smooth (factors into small primes $N = p_1^{e_1} p_2^{e_2} \dots p_m^{e_m}$), the ECDLP can be solved in polynomial time using the Pohlig-Hellman algorithm in SageMath.

from sage.all import *

# Define curve in SageMath
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

E = EllipticCurve(GF(p), [a, b])
G = E(P_x, P_y)
Q = E(Q_x, Q_y)

# Solve ECDLP
k = G.discrete_log(Q)
print(f"Recovered scalar k: {k}")