Your message has been sent!
Thank you
- hexens
- cybersecurity
- August 11, 2023
Solving "Spot The Bug" Challenge: Attacks on Weak Elliptic Curves Explained
Hexens/Remedy third Spot The Bug Challenge recently ended, which means that today we are publishing a detailed writeup of the bug we proposed to find from our guru cryptography researcher @p0wn4j.
As a reminder, the proposed vulnerability involved a weakness in the elliptic curve, which can be exploited via Pohlig-Hellman algorithm or MOV attack. Now let's dive into the details!
EllipticCurve smart contract implements operations on an elliptic curve over a finite field:
- point scalar multiplication
- checking point is on a curve
- verifying a signature
Elliptic Curve over a Finite Field
They have domain parameters:
- a,b: Weierstrass equation’s coefficients
- p: finite field prime
- G: base point that generates a cyclic subgroup
- n: order of the subgroup generated by a generator point
- h: cofactor of the subgroup generated by a generator point
Based on these parameters elliptic curves can be cryptographically strong or can have a weak security. Cryptographically strong elliptic curves are standardized by the NIST and there are strong curve databases (1, 2).
As we can see in the smart contract our curve has these domain parameters:
a = 0x00000000000000000000000000;
b = 0x00000000000000000000000001;
p = 0x0d0d3dc4be6d0d1d91a46b371d;
G = (0x0b8f7b7b963b06f8a27ab0b288, 0x061bab2e6f5d749cbb10189162);
n = 0xd0d3dc4be6d0d1d91a46b371e.
Curves with these parameters don't exist in standard databases so that can be an indicator that a smart contract uses a weak curve.
Attacks on Weak Curves, ECDLP
Certain choices of elliptic curves and/or underlying fields reduce the security of an elliptical curve cryptosystem by reducing the difficulty of the ECDLP for that curve.
The ECDLP is a special case of the discrete logarithm problem.
Let E(Fp) elliptic curve over finite field and let P,Q be points on the curve and a number n such that P = nQ. The elliptic curve discrete log problem is to find the number n. It is computationally a hard problem but weak curves make ECDLP to be solved in a reasonable time.
Based on a type of weak curves there are several ECDLP attacks:
- Pohlig-Hellman attack
- Pairing based: MOV attack, Frey-Rück attack
- Smart attack
- Singular curve attack
- SSSA attack
and others.
For each of the attacks to be done certain conditions must be met.
The best known general purpose attack on ECDLP is a combination of the Pohlig-Hellman algorithm and the Pollard’s rho algorithm.
The most known pairing type attacks are the MOV attack and the Frey-Rück attack, which are using Weil and Tate pairing. These attacks exploit isomorphic properties to reduce ECDLP to the DLP.
Because DLP can be solved in subexponential-time, one must avoid curves that are vulnerable to these methods.
You can check challenge’s elliptic curve’s domain parameters with this SageMath script.
After running the script with these initial values:
p = 0x0d0d3dc4be6d0d1d91a46b371d
a = 0
b = 1E = EllipticCurve(GF(p), [a, b])
check(E, E(0x0b8f7b7b963b06f8a27ab0b288, 0x061bab2e6f5d749cbb10189162))
the attacker can see that ECDLP in this curve is solvable via either the Pohlig-Hellman algorithm or a MOV attack.
Attack
- The attacker can collect all the transactions where verifySignature was called
- Extract public keys from transactions’ calldata
- Calculate the sender’s private key via Pohlig-Hellman algorithm or MOV attack
- Having private keys the attacker can impersonate signature generation and verification.
Links
