6
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ I would be fine with keeping this question open, answering the question directly, and possibly using the given rather technical reference to substantiate that answer. $\endgroup$ – Maarten Bodewes Jan 22 at 10:53
6
$\begingroup$

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 order of the subgroups are $2,4,8,n,2n,4n,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 AntipaDaniel BrownAlfred MenezesRené StruikScott Vanstone

    They defined a point is 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}$ for prime curves ($h=1$) and check $[h]P \neq \mathcal{O}$ for non-prime curves ($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}$$

$\endgroup$
6
  • $\begingroup$ Just to add to this, The “no need to validate” is a save curve criteria and therefore also intentional for curve25519. However it can be argued that not knowing/following about the static key bits is - as the question shows - still possible, safecurves.cr.yp.to/twist.html $\endgroup$ – eckes Jan 22 at 23:02
  • $\begingroup$ @eckes wouldn't it be nice if all standard curves have this? $\endgroup$ – kelalaka Jan 22 at 23:36
  • $\begingroup$ Yeah, but American and European governments still stick with non safe NIST or Brainpool Curves since its.. uh.. tradition? $\endgroup$ – eckes Jan 22 at 23:43
  • $\begingroup$ @kelalaka to be more specific on the very last point: Did you mean that $P=(x,y)$ is always either on Curve25519 or on the quadratic twist of Curve25519? $\endgroup$ – Marc Jan 25 at 6:56
  • $\begingroup$ @kelalaka the guarantee that we are not in a small subgroup comes from: "...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." ? As mentioned in the paper, this is just an example. So implementations of Curve25519 may not follow this? $\endgroup$ – Marc Jan 25 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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