3
$\begingroup$

I have some issues understanding the original protocol proposed by Daniel J. Bernstein for Diffie-Hellman on Curve25519. On his web page he states to not validate remote public key, but at the same time enumerates a list of bad points for "some protocols". It does not state anything about zero check after scalar multiplication.

In another question I got linked to this article about validation, but I can not see a definitive conclusion explicitly telling to not validate inputs nor outputs.

Should Diffie-Hellman on Curve25519 be validated? By validation I mean to check that input public key is not a "bad point" and check for zero on scalar multiplication result.

$\endgroup$
5
$\begingroup$

From DJB's page:

Don't. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys.

There are some unusual non-Diffie-Hellman elliptic-curve protocols that need to ensure "contributory" behavior.

So for (EC)DH using Curve25519 you don't need to validate public keys.

If you are using Curve25519 for some other elliptic curve protocol you may need to perform validation by making sure the public key isn't in some small subset of possible public keys.

$\endgroup$
  • $\begingroup$ By ECDH you mean authenticated public keys? $\endgroup$ – user3368561 Feb 14 '18 at 21:08
  • $\begingroup$ By ECDH I mean Elliptic Curve Diffie Hellman. $\endgroup$ – puzzlepalace Feb 14 '18 at 21:09
  • $\begingroup$ Can you add a link to the specification of ECDH protocol please? Only to be sure that I understood the right thing. $\endgroup$ – user3368561 Feb 14 '18 at 21:19
  • 1
    $\begingroup$ Sure, embedded the link in the post, here it is for reference - nvlpubs.nist.gov/nistpubs/Legacy/SP/… $\endgroup$ – puzzlepalace Feb 14 '18 at 21:23
  • 1
    $\begingroup$ Input / output validation is a bit vague, I would say "even if you don't validate public keys when doing ECDH over Curve25519 an attacker can't forge malicious public keys to disclose your secret key". $\endgroup$ – puzzlepalace Feb 14 '18 at 22:01
4
$\begingroup$

Let's be more specific about the protocol, because ‘Diffie–Hellman’ can mean a lot of things including just an abelian group action on a set.

Suppose there is a set of users including Alice and Bob. Suppose each user has a public key known to everyone to be correct, by, e.g., being published in the telephone book. (This is the original setting of Diffie and Hellman's seminal paper, and is also essentially the setting of DNSCurve, probably the first application of X25519.)

When Alice wants to send a message to Bob, she looks up Bob's public key $x_0(B)$ in the telephone book, and computes $k = H(x_0([a]B))$ from $x_0(B)$ and her secret scalar $a$, where $H$ is the standard hash function. Then she uses $k$ as the secret key for symmetric-key authenticated encryption. When Bob receives a message from Alice, he decrypts it with $k = H(x_0([b]A))$, where $A$ is Alice's public key in the telephone book.

Only a self-destructive idiot would fail to follow the protocol and put a public key generated any way other than the standard method of picking $n$, an integer multiple of 8 between $2^{254}$ and $2^{255}$, uniformly at random, and publishing $A = [n]P$ where $P$ is the standard base point. Such a self-destructive idiot could also publish every message sent to them on reddit. So there's no sense in worrying about a user failing to follow the protocol for key generation, except maybe as a public health service scanning the telephone book for mistakes.

What if we don't assume a legitimate telephone book? Then we get into the territory of authenticated Diffie–Hellman key agreement protocols. The details are more than fit in the margin of this crypto.se post, but suffice it to say that if an adversary can substitute a point of low order, and your putative authenticated DH protocol doesn't detect that, you probably have bigger problems on your hands.

In the bizarre case that you manage not to have bigger problems on your hands, but you still need both parties to substantively affect the outcome of the key agreement even if one of them is malicious, you are probably better off using $H(A, B, x_0([a]B)) = H(A, B, x_0([b]A))$ as your shared secret—and, generally, you should hash the entire transcript leading up to the key agreement into it so that a meddler on the wire can't futz with any bits of the exchange without changing the resulting key.

Note that this answer is limited to X25519. The X25519 function was designed so that every possible encoded public key bit string is safe to use with every legitimate secret scalar, even if what it encodes is an illegitimate public key—i.e., not $[8n]P$ for some 251-bit integer $n$ where $P$ is the standard base point.

If an unwary user reveals $H([n]Q)$ where $Q$ is an adversary-supplied point of order 8, then since there are only at most eight possible outputs, an adversary can learn $n \bmod 8$—this is the Lim–Lee active small-subgroup attack. But since legitimate secrets in X25519 are all multiples of 8, all the adversary learns is that $n \bmod 8 = 0$ per the protocol.

Not all curves or DH functions have this property: curves with cofactor >1 used with secrets that are not multiples of the cofactor, or DH functions and protocols without point compression (like many archaic protocols using generic Weierstrass curves and no point compression), may cause unwitting implementations to leak bits of the secret if they don't reject invalid points.

The considerations for Ed25519 signatures are a little different, and addressed elsewhere (1), (2).

$\endgroup$
  • $\begingroup$ I understand that against a non "contributory" peer verification is useless. What I'm worried about is if a malicious peer can disclose my secret key or not. $\endgroup$ – user3368561 Feb 15 '18 at 11:01
  • 1
    $\begingroup$ I added some elaboration on how X25519 avoids leaking any bits of the secret key even given invalid points. Does that help? $\endgroup$ – Squeamish Ossifrage Feb 15 '18 at 15:15
0
$\begingroup$

puzzlepalece's answer is perfectly correct. For curve25519, any 32 byte represents a valid point on the curve. This is emphatically not true for other curves and how they are used.

Why validate

Let's look at P-256 for example. A point is an literally just a point with an x and y coordinate. Now for any valid x value, there can be two y values, that differ only in sign. So you don't need to store the y value, you can just store its sign and your x. Now given an x, you can compute the $y^2$ as

$$y^2 = x^3 - 3x + b \mod p$$ where P and b are defined in the standard (PDF), but are too inconvenient to write out here.

When $y^2$ is not a quadratic residue

The need for validation is because not every x will lead to a $y^2$ that has a square root mod p. Roughly half of all x will lead to a $y^2$ that has a square root (so $x^3 - 3x + b$ is a quadratic residue mod p), but about half of possible x values will not lead to a quadratic residue. And so there x values that do not produce any y value. Those xs are not valid points and cannot be used as public keys.

When x doesn't lead to the correct y

In some key formats, for example JSON Web Keys, both the x and the y values are specified. You should check that the given x, y pair is a solution to $x^3 - 3x + b$. If it isn't, then something went wrong somewhere, and you have a point that is not on the curve.

This does happen. There is a bug in the web-crypto implementation in Safari that means that it will occasionally (about 1 in 200 times) produce and export as JWK a point that is not on the curve.

curve25519 is different

[Update: What I originally said in this section was incorrect. Following Squeamish Ossifrage's comment, I have rewritten this section.]

curve25519 is designed so public points x can securely be used as public keys even if the corresponding y^2 is not a quadratic residue. I honestly do not understand how values on a twist can be used, so will say no more about it.

Using its own functions

One thing to note is that curve25519 is not just a curve (and generator point), but it is a collection of functions that perform computations on that curve efficiently. While it would be possible to use the curve parameters of ed25519 using generic elliptic curve math (well, a slight adjustment needs to be made for those that assume that the $x^2$ term's coefficient must be 3), it would lose many of the speed advantages of curve25519.

$\endgroup$
  • 1
    $\begingroup$ If by ‘curve’ you mean the group $E(\mathbb F_p)$, it's not true that every 32-byte string represents a valid point on it even for X25519: just like you described with P-256 (or P-266 if that's not a typo?), about half the possible $x$ values do not correspond to points in $E(\mathbb F_p)$, but rather to points in the twist — roughly the subgroup of $E(\mathbb F_{p^2})$ with $x \in \mathbb F_p$ and $y \in \sqrt{2} \mathbb F_p$. If the twist has subgroups of small orders, then the Lim–Lee active attack can recover the secret key modulo those orders. X25519 avoids this with twist security. $\endgroup$ – Squeamish Ossifrage Feb 16 '18 at 15:36
  • $\begingroup$ crypto.stackexchange.com/users/49826/squeamish-ossifrage is correct that I have been sloppy about curve or group. (I've made minor edits in attempt to correct that). But I need to do more research to understand what a 32 byte ed25519 public key is. In all likelihood more corrections will follow. $\endgroup$ – Jeffrey Goldberg Feb 16 '18 at 19:05
  • $\begingroup$ Thanks. I have updated my answer. I really was wrong, and presumed that it was all just a clever trick about representing points. I still do not understand what happens on twists, but I don't need to understand that to mention the fact that it works. $\endgroup$ – Jeffrey Goldberg Feb 16 '18 at 19:38
  • $\begingroup$ FYI, the nomenclature is a little confusing and has changed, but as of RFC 7748/8032: Curve25519 means the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$ over $\mathbb Z/(2^{255} - 19)\mathbb Z$; X25519 means the DH function (called Curve25519 in the original paper, but later renamed for clarity); edwards25519 means the twisted Edwards curve $-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$ over the same field (sometimes also called Ed25519); and Ed25519 means the standard instantiation of EdDSA signatures with the curve edwards25519. $\endgroup$ – Squeamish Ossifrage Feb 16 '18 at 20:42

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.