Why do public keys need to be validated?

For some curves it's necessary to validate the public-key of the other side before running an elliptic-curve Diffie-Hellman key-exchange. Apparently if you don't validate the public key, small subgroup attacks can leak your private key.

I have a few questions related to this issue:

1. Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?
2. Which validations need to be performed? Just check if the order of the point is large enough?
3. Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?
• A vuln that was revealed in some implementations of Cryptonote was due to the fact that by not validating points, you can pick two points P and P + qK, where K is not generated by G, and q is the order of G. Note that qK != 0. If the exponent e by chance is even (50/50 odds), then eP + eqK = eP, giving you two distinct points A, B, where eA = eB. Since eA was mathematically used for validation that A corresponds to a given coin, and A itself was saved in a hashmap to check if it's been used before, it allowed double spend attacks by using B. Nov 28 '18 at 16:49

Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's mostly unimportant for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^2 = x^3 + ax + b \bmod p$? Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard algorithms (and where we're dealing solely with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^2 = x^3 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to. That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem? Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation). The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor. For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values). If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret. This effectively gives the attacker $log_2 r$ bits of our private exponent; doing this a handful of times for different values of $r$ allows him to recover our entire private exponent.

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^2 = x^3 + ax + b \bmod p$; that's cheap and totally foils this attack. The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying if $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value). As far as I know, all curves can have implementations which are vulnerable.

• I wasn't considering your first attack, because I forgot that many protocols don't use compressed points. I was only considering checks of points which result from decompression, and thus are on the curve. Such as checking that $qY=0$. I'll need to reread some papers, to check if some of the attacks I read about assume points not on the curve. At least some checks seem to be curve specific, since the Curve25519 paper mentions choosing parameters so that any compressed point can be used without validation. Sep 19 '12 at 15:38
• @CodesInChaos: if we're talking about a prime-order curve, and we get a point $Y$ that's on the curve, and not the point at infinity, then there's no further validation possible; we know that there must be some value $y$ with $Y = yG$, and so it is a possible public value from the peer. Sep 19 '12 at 15:43
• @poncho What do you mean by "to make sure that his point is not the point-at-infinity"? The point-at-infinity has no coordinates, so it can't actually be represented by a pair of X and Y coordinates that the attacker sends you. Feb 16 '18 at 17:04
• @BogdanAlexandru: well, that depends on how the point is communicated. If you simply don't have a 'bits-on-the-wire' representation for 'point at infinity', well, then it is in fact a nonissue. However, sometimes we use packages that were designed to handle the general EC case (and not only the parts that are of interest to crypto), those packages may have some hooks to communicate the identity element Feb 16 '18 at 17:18
• @poncho Thanks for the reply. So in effect there is no issue if you receive the keys over some specific communication protocol, where you expect two coordinates, each with a specific number of octets. Feb 16 '18 at 18:57

Depends what you mean by "validate". You should always validate any Public Key, as otherwise how do you know who owns it? If you are not sure of the owner, you are open to a man-in-the-middle attack.

But I guess by validate you mean validate that the point is of the right order? You should certainly check that its on the curve (easy) and check that its not a point of small order. The possible orders are the divisors of the number of points on the curve. This possibility can and should be avoided by using a curve with a prime number of points, in which case only one order (the right one) is possible.

If your curve has multiple small subgroups, then an attacker can over time get to see your private key modulo the order of each of them. And then the Chinese Remaninder theorem might in theory be used to find your full secret.

So.. (a) Use a curve with a prime number of points on it and (b) Check that any points sent to you are actually on the curve. And you are good to go...

• I thought order $1$ was possible even for curves with a prime number of points (although if I $\hspace{1.2 in}$ understand how things work, that's not a security risk). $\:$
– user991
Sep 19 '12 at 18:27
• @RickyDemer: the only order 1 point on an elliptic curve is the point at infinity. As long as we reject that, an order 1 point is not a possibility. Oct 8 '12 at 17:45