Weierstrass Curves point addition formulas
Consider the Weierstrass equation
$$y^2 = x^3 + a x + b$$
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.
- $P+O=O+P=P$
- If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
- If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;
\begin{align}
x_3 = & \lambda^2 -x_1 - x_2 \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1}, & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1}, & \text{if $P = Q$} \\[2ex]
\end{cases}$$
The addition law on Weierstrass curves doesn't use the constant $\color{red}{b}$. This is the core of the attack.
Invalid curve attack
Consider that the used curve is Secp256k1 with curve equation $y^2 = x^3+7$.
Now, using the fact that the addition formulas don't use $7$, an attacker $A$ can choose a public key $(x_a,y_a)$ such that it is on another curve $$y^2 = x^3+c$$ with small order $n$. Now, you did not validate this public key and used $[a](x_a,y_a)$ as an input for the KDF to derive the key. Now the attacker can try all $n$ possible values $[i](x_a,y_a)$, $ 0 \leq i <n$ and validate the result form the encrypted message that you send.
Now, you are not aware of anything and $A$ doesn't stop there, next time chooses another point on the same curve with a different small order or carries the attack on another curve. Finally, they combine all extracted information with the Chinese remainder theorem (CRT).
Now the attacker accessed the key, and use it.
TLS
If the public key of the attacker is not validated with a CA and you assume that as it is then you have a problem.
In pre-TLS 1.3 the EDHK doesn't have to be ephemeral (ECDHE). In this case, it is called static. If you use static then the attacker can extract your key. The recorded past communications are no longer safe.
Since you computed the exchange points during any DHKE by $[d]Q_b$ with $Q_b = [d_b]G$ is the Bobs public key then they can recalculate $[d]Q_b$. After that, we can decrypt all recorded sessions.
If you use TLS 1.3 (you should) then you have to use ECDHE. In the ephemeral case, the private and public keys are generated on the fly. They are protected with signatures. In this case, the attacker can only recover the current private key that is not used for any other session.
This is good since it is the forward secrecy as defined in the original DHKE paper. To achieve forward secrecy the old keys must be deleted and this is exactly what TLS does.
Therefore it can be dangerous in pre-TLS 1.3 where static DHKE is allowed.
The countermeasures
- Validate the point
- The CA verifies the point and you trust the CA by a chain of trust.
- Use compressed points on your protocol, during the uncompressing the validation is included.
- Use EDHKE