Curve25519 Key Validation

Question

According to the original paper of Bernstein, there is no key validation needed when using Curve25519 for Diffie-Hellman Key Exchange. However, where does this property come from?

Is there any proof or argumentation available in order to understand this really practical property of Curve25519?

Does this mean that each $x$ coordinate could belong to a point $P=(x,y)$ from Curve25519? Is that even possible?

Answer 1

The responsibility of the user of Curve25519 for DHKE is Section 3;

The legitimate users are assumed to generate independent uniform random secret keys. A user can, for example, generate 32 uniform random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the last byte, and set bit 6 of the last byte.

This is a guarantee that the legitimate users are not in the small subgroup. Remember the cofactor ($h = \#E(k)/n$) of the curve Curve25519 is $h=8$ which means that there are small subgroups of Curve25519. The orders of the subgroups are $2,4,8,n,2n,4n$, and $8n$.

Now, the attacker may choose one of the small sub-group to use the Lim–Lee active small-subgroup attacks. This attack is very effective if the co-factor has many small factors. Then, the attackers can use CRT to combine the results.

The attacker will choose a $P$ which has a small order where the discrete logarithm is easy. During the protocol, the legitimate user will reveal $[a]P$ to the attacker. Now, how much information can the attacker learn about $a$ from $[a]P$?

• The answer is given as information revealed by $[a]P$ is at most $\lceil log_2 h\rceil$ bits.

If the responsible users select their secret $a \equiv 0 \bmod h$ then $[a]P = \mathcal{O}$ for any small order, so they will expose nothing!

If you don't take responsibility then you need validation! During DHKE, for every public key you have to look at $[8]P \stackrel{?}{=} \mathcal{O}$. This has a cost of 3 doubling; $[8]P = [2]([2]([2]P))$. And, finally, to make sure that $P$ has order check $[n]P = \mathcal{O}$ with a cost of $\mathcal{O}( log_2 n)$ by the double-and-add algorithm.

Which one is better? Of course, obeying the suggestion, no need for validation and no leak of information about the secret.

---

The validation can be hard for some curves, There is an article about this;

• 2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone

  They defined a point as valid if

  1. $P \neq \mathcal{O}$

  2. The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.

  3. $P$ satisfies the curve equation ( the twist attack )

  4. Check $[n]P = \mathcal{O}$

     If the curve is prime order then the first three conditions imply the 4th. If the curve is not prime then we need to test $[h]P \neq \mathcal{O}$ for non-prime curves where $h>1$.

---

Twist attack

An attacker, instead of sending a valid point $P$ as a public key, can choose to send a point on the quadratic twist of the curve where the group order is low. If the receiver doesn't check this (3. case) then it may be vulnerable to this. Curve25519 is also secure against this attack if the user takes responsibility during the key generation;

• The twist of Curve25519 has an order $4p_2$ where prime $p_2 = 2^{253} − 55484635554744707071703875581767296995$. Therefore. Its small subgroups are $2,4$ and with the choice of the secret key, the user secure against these, too.

---

Why do we need uniform random secret keys?

There we some protocols [1] [2] that used fixed byte of the key, or low hamming weighted key for performance ( named restricted exponents 3.59 of HoAC). If the Hamming weight is $t$ of $k$ bit than there are $\binom{k}{t}$ such keys, the Shank's baby-step giant step can be modified to search in $\binom{k}{n/2}$-time. This is investigated by Heiman in 1993.

---

Does this mean that each $x$ coordinate could belong to a point $P=(x,y)$ from Curve25519? Is that even possible?

A point $P$ is in either on the Curve25519 or on its quadratic twist. A point $(x,y)$ is on the curve iff its satisfies the curve equation $$y^2 = x^3 + 486662 x^2 + x \text{ over } \mathbb{Z}/(2^{255} - 19)\mathbb{Z}$$

---

Special note: It turns out that the legitimate users did not listen the DJB, and Monero and all other CryptoNote currencies had vulnerable implementations! and Mike Hamburg constructed the Decaf to mitigate the problem from the hands of legitimate users.

---

Patent: in 1998, Certicom issued a patent about point validation the existed to 2013 ( pantent US7215773B1). High probably, due to this patent the Bluetooth LE doesn't include point validation and attackted in 2018;

• Breaking the Bluetooth Pairing Fixed Coordinate Invalid Curve Attack by Eli Biham and Lior Neumann

$$\textbf{The protocol fixed with point validation!}$$