Security properties, attack vectors, and mitigations for elliptic curve cryptography.
Given points P and Q = kP on an elliptic curve, find the scalar k.
Security assumption: For properly chosen curves, this problem is computationally infeasible.
| Attack | Complexity | Notes |
|---|---|---|
| Baby-step Giant-step | O(√n) space and time | Requires √n storage |
| Pollard's rho | O(√n) time, O(1) space | Practical for large groups |
| Pollard's lambda | O(√n) | When k is in known range |
| Pohlig-Hellman | O(√p) where p is largest prime factor | Exploits factorization of n |
For secp256k1 (n ≈ 2²⁵⁶):
| Attack | Applicable When | Mitigation |
|---|---|---|
| MOV/FR reduction | Low embedding degree | Use curves with high embedding degree |
| Anomalous curve attack | n = p | Ensure n ≠ p |
| GHS attack | Extension field curves | Use prime field curves |
secp256k1 is immune to all known curve-specific attacks.
Vulnerability: Execution time varies based on secret data.
Examples:
Mitigations:
Simple Power Analysis (SPA): Single trace reveals operations.
Differential Power Analysis (DPA): Statistical analysis of many traces.
FLUSH+RELOAD Attack:
1. Attacker flushes cache line containing lookup table
2. Victim performs table lookup based on secret
3. Attacker measures reload time to determine which entry was accessed
Mitigations:
Similar to power analysis but captures electromagnetic emissions.
Mitigations:
The Sony PS3 Hack (2010):
If the same k is used for two signatures (r₁, s₁) and (r₂, s₂) on messages m₁ and m₂:
s₁ = k⁻¹(e₁ + rd) mod n
s₂ = k⁻¹(e₂ + rd) mod n
Since k is the same:
s₁ - s₂ = k⁻¹(e₁ - e₂) mod n
k = (e₁ - e₂)(s₁ - s₂)⁻¹ mod n
Once k is known:
d = (s₁k - e₁)r⁻¹ mod n
Mitigation: Use deterministic k (RFC 6979).
Even with unique k values, if the RNG is biased:
Mitigations:
Attack: Attacker provides point not on the curve.
Mitigation: Always validate points are on curve:
Verify: y² ≡ x³ + ax + b (mod p)
Attack: If cofactor h > 1, points of small order exist.
Mitigation:
Attack: Induce computational errors (voltage glitches, radiation).
Mitigations:
Given valid signature (r, s), signature (r, n - s) is also valid for the same message.
Impact: Transaction ID malleability (historical Bitcoin issue)
Mitigation: Enforce low-S normalization:
if s > n/2:
s = n - s
BIP-340 Schnorr signatures are non-malleable by design:
Threat: Polynomial-time discrete log on quantum computers.
Timeline: Estimated 10-20+ years for cryptographically relevant quantum computers.
DO:
- Use cryptographically secure RNG
- Validate private key is in [1, n-1]
- Verify public key is on curve
- Verify public key is not point at infinity
DON'T:
- Use predictable seeds
- Use truncated random values
- Skip validation
DO:
- Use RFC 6979 for deterministic k
- Validate all inputs
- Use constant-time operations
- Clear sensitive memory after use
DON'T:
- Reuse k values
- Use weak/biased RNG
- Skip low-S normalization (ECDSA)
DO:
- Validate r, s are in [1, n-1]
- Validate public key is on curve
- Validate public key is not infinity
- Use batch verification when possible
DON'T:
- Skip any validation steps
- Accept malformed signatures
DO:
- Validate received points are on curve
- Check point is not infinity
- Prefer compressed format for storage
DON'T:
- Accept unvalidated points
- Skip curve membership check
| Curve | Bits | Symmetric Equivalent | RSA Equivalent |
|---|---|---|---|
| secp192r1 | 192 | 96 | 1536 |
| secp224r1 | 224 | 112 | 2048 |
| secp256k1 | 256 | 128 | 3072 |
| secp384r1 | 384 | 192 | 7680 |
| secp521r1 | 521 | 256 | 15360 |