3
$\begingroup$

According to the "Guide to Elliptic Curve Cryptography" (page 182), it's possible to recover $d$ with an invalid curve attack.

How can this value be used once recovered? For example, with Elliptic Curve Diffie Hellman (in TLS for example), what can we do with $d$?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

  1. $P+O=O+P=P$
  2. 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$
  3. 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
$\endgroup$
8
  • $\begingroup$ I'm considering ECDSA out of the question since it has a different key. $\endgroup$
    – kelalaka
    Mar 4, 2021 at 18:50
  • $\begingroup$ could you explain why ECDSA is out of the question please ? $\endgroup$
    – cmdEvo
    Mar 4, 2021 at 18:53
  • 1
    $\begingroup$ You got the key from static ECDH, but the key for ECDSA is different from that one. You cannot send an invalid curve to attack since signatures don't work in this way. The signer signs and sends and you verify it. $\endgroup$
    – kelalaka
    Mar 4, 2021 at 18:54
  • 1
    $\begingroup$ There is a related vulnerability in ECDSA when the base point is not validated by a certificate. This allows arbitrary forgery. See cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2020-0601 $\endgroup$
    – Daniel S
    Mar 4, 2021 at 19:24
  • $\begingroup$ @DanielShiu The CurveBall is a bit different, the attacker doesn't access the private key. They use the weakness that the library doesn't check the base point. $\endgroup$
    – kelalaka
    Mar 4, 2021 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.