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:
Elliptic Curve over a Finite Field
They have domain parameters:
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.
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:
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 = 1
E = 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.