3
$\begingroup$

Studying libsodium implementation of x25519 and Ed25519 I saw that it performs an small order check comparing given inputs with a hard coded blacklist of values. Is this list exhaustive or it is a list of currently known invalid points?

Source code:

X25519 blacklist

Ed25519 blacklist

$\endgroup$
  • $\begingroup$ The list is probably exhaustive. Could you provide a link to it? $\endgroup$ – Elias Feb 14 '18 at 10:33
  • $\begingroup$ Have you read this related answer? $\endgroup$ – Lery Feb 14 '18 at 11:26
  • $\begingroup$ @Lery I didn't found it on my previous research. Thanks for the link. $\endgroup$ – user3368561 Feb 14 '18 at 11:46
6
$\begingroup$

Short answer: You don't need to worry about the blacklist or point validation unless you are designing an exotic protocol.

Medium answer:

It depends on what you are trying to do. There is a short blacklist, and a much larger set of points (too large to list) that may cause you trouble—but only if you are setting yourself up for trouble by using the primitives in an unusual novel protocol and expecting unusual security properties from them.

The ‘blacklisted’ points have low order: each point $P$ has the property that there is a very small number $n$, in this case always a divisor of 8, such that $[n]P = \mathcal O$. Thus there are only at most 8 different scalar multiples of each of these points.

This significantly reduces the number of possible shared secret values that someone computing a ‘shared secret’ using their private secret scalar $n$ and a malicious peer's ‘public key’ $P$, nearly or completely negating the contribution of the secret scalar $n$ of which there are $2^{251}$ possibilities. None of the low-order points are actually valid public keys: the standard base point $B = (9, \dots)$ does not generate them.

In sensible protocols, you normally don't need to worry about these points at all:

  • In an interactive key agreement, (a) a malicious peer is usually out of scope, (b) a MITM should be detected by authenticating the transcript, and (c) you hash the entire transcript of the key exchange including the shared secret and the hapless sap's public key $[n]B$ to produce a session key for a subsequent conversation.

  • In a signature system, you rely on verification under known public keys; a malicious signer giving one of the ‘blacklisted’ points is out of scope. Blacklisted points in signatures can't fool verifiers—the signature scheme would be horribly broken if they could.

For more details on validation, see Trevor Perrin's article on point validation in such protocols.

Any other properties, you have to be very careful about, e.g. uniqueness of public keys or signatures—and here the blacklist is not sufficient. Why is the blacklist not sufficient for some obscure applications requiring obscure security properties? If $P$ is a point of low order, and $n$ is a legitimate user's secret scalar, then for any point $Q$ generated by the base point $B$, $[n](P + Q) = [n]Q$. This happens because every legitimate secret scalar is a multiple of 8, the cofactor, and so annihilates $P$, i.e. $[8]P = \mathcal O$ is the identity. Such incautious design of a novel protocol requiring novel security properties thoroughly flummoxed Monero last year, after a casual comment by Trevor Perrin explaining this.

Long answer:

The groups that X25519 and Ed25519 work in have some nontrivial structure which make the so-called ‘invalid points’ relevant. I'll focus on X25519.

Every group has an identity element, which we call $\mathcal O$. Every element $P$ of a finite group (written additively) has a finite order $n = \operatorname{ord}(P)$, the smallest positive number of times that adding it to itself $P + \cdots + P = [n]P$ yields the identity $\mathcal O$. The order of the identity is 1; all other points have order greater than 1.

X25519 works in the prime field $\mathbb F_p$ where $p = 2^{255} - 19$, also known as $\mathbb Z/(2^{255} - 19)\mathbb Z$. Specifically, it works on bit string encodings of the $x$ coordinates of points on the curve $$E/\mathbb F_p \colon y^2 = x^3 + 486662 x^2 + x.$$ Every curve point $P$ except the identity $\mathcal O$ has an $x$ coordinate, which we will call $x(P)$. We additionally define $x_0(P) = x(P)$ when $P \ne \mathcal O$, and $x_0(\mathcal O) = 0$.

It turns out that if $P \in E(\mathbb F_{p^2})$ has $x_0(P) \in \mathbb F_p$, then for every integer $n$, $x_0([n]P) \in \mathbb F_p$, and every $P$ with the same $x_0(P)$ has the same $x_0([n]P)$. That is, scalar multiplication keeps the $x$ coordinate in the base field $\mathbb F_p$ and not in an extension field, and the $x$ coordinate of the scalar multiple $[n]P$ is uniquely defined by the $x$ coordinate of the base point $P$. This is Theorem 2.1 of the Curve25519 paper.

You don't need to understand all the details—suffice it to understand that since we work only in encodings of elements of $\mathbb F_p$, the only points we ever have to worry about are those in the group $E(\mathbb F_{p^2})$ with $x$ coordinate in $\mathbb F_p$. (Why might we have to worry about $\mathbb F_{p^2}$ at all, a quadratic extension of $\mathbb F_p$ that adds fabricated square roots to nonsquare elements of $\mathbb F_p$? There are some $x$ coordinates for which $x^3 + 486662 x^2 + x$ is nonsquare, so there is no corresponding $y$ coordinate in $\mathbb F_p$, but there is one in $\mathbb F_{p^2}$.)

The group $E(\mathbb F_p)$ of $\mathbb F_p$-rational points, or roughly those whose coordinates are in $\mathbb F_p$ and not an extension field (more precisely, the fixed points of the componentwise action of the automorphism group of $\overline{\mathbb F_p}$ that fixes $\mathbb F_p$; this definition works with projective coordinates too), has $8 p_1$ elements, where $p_1 = 2^{252} + 2774231777737235353585193779088364849$ is prime, and 8 is called the cofactor. By a standard theorem of group theory, the order of every element of $E(\mathbb F_p)$ divides $8 p_1$. This means that every element of $E(\mathbb F_p)$ has one of eight possible orders: $\{1, 2, 4, 8, p_1, 2p_1, 4p_1, 8p_1\}$.

The twist group, which is the subgroup of $E(\mathbb F_{p^2})$ with $x$ coordinates in $\mathbb F_p$ and $y$ coordinates not in $\mathbb F_p$, has $4 p_2$ elements, where $p_2 = 2^{253} - 5548463555474470707170387558176729699$ is also prime. This is the group that we don't ordinarily work with (there is no multiple of the standard base point in this group except the identity), but which about half the possible $x$ coordinates that X25519 can handle will decode to. Thus, the order of every element in the twist group divides $4 p_2$, and therefore the only eight possible orders are $\{1, 2, 4, p_2, 2p_2, 4p_2\}$.

Legitimate X25519 users choose public keys of the form $x_0([8a]P)$, where $P$ is a standard base point of prime order $p_1$, and shared secrets of the form $x_0([8a]B)$, where $x_0(B)$ is their peer's public key. The factor 8 means that the public key $x_0(B + Q)$ for a point $Q$ of order 8 (also called an 8-torsion element) yields the same shared secret as the public key $x_0(B)$, because $[8a](B + Q) = [8a]B + [8a]Q = [8a]B + [a][8]Q = [8a]B + [a]\mathcal O = [8a]B$. A malicious peer could choose such a $B + Q$, which is bitwise distinct from $B$ but always yields the same shared secret. A malicious peer could choose $B$ not of the form $[8b]P$ at all but rather a point of low order, which would reduce the number of possible shared secrets to 1, 2, 4, or 8. E.g., they could choose $\mathcal O$; then the ‘shared secret’ would be $x_0(\mathcal O) = 0$—that's where the zero check comes from.

The blacklist is the list of all points that will give zero as the ‘shared secret’. It does not list all illegitimate public keys—there are too many to list, of the form $B + Q$ where $B$ is a legitimate public key (of which there are $p_1$ possibilities) and $Q$ is on the blacklist. The only way to detect legitimate public keys is to confirm that $[p_1]B = \mathcal O$.

But for most protocols the threat model that could cause trouble by substituting illegitimate public keys is irrelevant because the same attacker, the same malicious peer, could cause trouble in all sorts of other ways anyway. For example, in DNSCurve, which was probably the original application of X25519 using static-static DH key agreement, the only problem that a malicious nameserver or user could cause by using an illegitimate public key is to leak the peer's secrets on the wire to an eavesdropper—which they could do anyway.

$\endgroup$
  • $\begingroup$ I'm asking in the context of the protocol as it is. I'm not smart enough to do anything more complex than a copy-paste with some reformatting of cryptography code. I'm just curious about what is under the hood. $\endgroup$ – user3368561 Feb 14 '18 at 20:09

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.