2
$\begingroup$

I read some specifications/norms regarding ECDH. I noticed that most norms do not require to check that the public point is actually on the curve. This puzzles me a bit. Isn't it necessary to make this check for security reasons?

An additional puzzling fact is that the JavaCard API does not have a function to check if a public point belongs to the curve. This implies, if I implement the ECDH in Javacard according to the standard (I.e. without checking if the point is on the curve) and assume further that no BigInteger arithmetic is present, then no applet will be able to perform this check. Is that intensional by the JavaCard specification or a missing requirement/function?

$\endgroup$
2
$\begingroup$

Isn't it necessary to make this check for security reasons?

Sometimes it's safe to skip it.

Of course, there's Curve25519 (and similar curves), where you transmit only the $x$ coordinate, and has twist security; that's safe. Note: if you don't use 'cofactor ECDH', the attacker could deduce 3 bits of your private value; as the attacker can't gain anything else, that's not a major issue).

However, lets assume you're talking about a curve where the public value has both the $x$ and $y$ coordinate.

Then, if you always generate a fresh private value each time, then it's still safe. Yes, the other side could select a bogus public value that made reconstructing the shared secret by a third party easy; however, they could do that already with a good public value (e.g. selecting one with low entropy), and hence there's no additional weakness. They could also deduce information about your private multiplier; however, if you're just using it that one time, that's not an issue.

On the other hand, if you intend to reuse the same private value for multiple exchanges, you really want to check the peer's public value to see if it's on the curve; if you don't, then they can recover your private value with shockingly few exchanges.

On the third hand, checking if the public point is actually on the curve is really cheap (less than 1% of the cost of actually performing the ECDH operation itself).

My opinion: I personally don't see any reason for not performing it, even if you never reuse a private value (that is, other than the Curve25519 case; it's a lot more expensive there, and there's never any need...)

$\endgroup$
2
$\begingroup$

The general answer is: it depends on the curve and the cryptosystem.

EDIT: The original question mentioned ‘ECDH’ without qualification, which is a general term covering many specific cryptosystems. The question was then updated to specify the JavaCard API. For the case of the specific cryptosystems implemented by the JavaCard API, namely IEEE P1363 ECDH over short Weierstrass curves with $(x, y)$ coordinates that may or may not be compressed, point validation is almost certainly necessary. Whether the JavaCard library does it internally or whether you must write code to do it yourself, I don't know—that's a programming question you'll have to ask somewhere else.

Original answer to the more general question below:


One of the SafeCurves criteria is that the curve be safely usable for $x$-coordinate Diffie–Hellman without point validation: the cofactor of the curve and its twist must be small enough that the amount of information revealed about the secret scalar $n$ by revealing $x([n]M)$ given maliciously chosen $x(M)$ is negligible, for all possible values of $x(M)$ including ones not in the legitimate curve's subgroup or ones not on the legitimate curve at all.

  • Thus, for the curve Curve25519 and the Diffie–Hellman cryptosystem X25519, point validation is not necessary: at worst, the defender learns three bits of the secret scalar $n$. This is because the cofactor of the curve is 8 and the cofactor of its quadratic twist is 4, and X25519 works only in $x$ coordinates.

    Thus the only invalid curve an attacker can use is the quadratic twist, by feeding in the $x$ coordinate of a point on the quadratic twist and not on the legitimate curve, and the only small subgroups an attacker can use on the curve or its quadratic twist are negligibly small.

    (In correct use of X25519, legitimate users always choose $n \equiv 0 \pmod 8$ anyway so that $[n]M = \infty$ for all $M$ in all small subgroups, but the SafeCurves criteria require the leak to be negligible even if a legitimate user with slightly broken software chooses $n \not\equiv 0 \pmod 8$.)

  • In contrast, for the curve NIST P-224 and an analogous $x$-coordinate Diffie–Hellman cryptosystem, point validation is necessary because although NIST P-224 itself has prime order and thus no small subgroups, the order of the quadratic twist of NIST P-224 has a dangerously small 118-bit largest prime factor $\ell'$.

    Without point validation, an attacker can feed $x(M_{\ell'})$ to a legitimate user where $M_{\ell'}$ is a point of order $\ell'$ on the quadratic twist, and learn $x([n]M_{\ell'})$, from which they can perform a feasible ECDLP computation to learn $n \bmod \ell'$, revealing nearly half the bits of $n$. This may be enough to figure out $n$ from the legitimate public key, or they may repeat with the other factors of the quadratic twist order.

One of the benefits of a single-coordinate ladder—such as the Montgomery ladder or Brier–Joye ladder—is that it compresses the space of inputs you must be willing to consider from $(x, y)$ values or $(x, \operatorname{sgn} y)$ values to just $x$ values. Decaf thwarts the attacks in another way by going further, at the cost of a little encoding and decoding performance: by picking a point encoding that naturally interprets every possible bit string as a valid point, so that there isn't even a way to feed a malicious point $M$ into a legitimate user.

However you do it, designing a protocol to obviate the need for input validation makes secure implementations simpler and faster: you need not remember to write an error branch in the first place for invalid values of $x(M)$, and you need not make the error branch behave sensibly.


This question was about ECDH, but what about other cryptosystems, e.g. ECDSA? Do they require point validation, or are there curves for which they require point validation? In the case of ECDSA over some curve $E/k$ and some field $k$, only the verifier is given externally supplied inputs: $A$, the public key, an element of $E(k)$; and $(r, s)$, a signature, for $r, s \in \mathbb{Z}/\ell\mathbb{Z}$, where $\ell = \#E(k)$ is the prime order of the group.

  • If an adversary could control $A$, the adversary could forge signatures anyway by choosing a point whose secret scalar they know.

  • If an adversary could find some way to control $(r, s)$ that tricks the verifier into accepting it for a public key $A$ beyond the adversary's control, that means the adversary can forge signatures. The standard signature verification equation $$r \equiv x([H(m)\,s^{-1}]G + [r s^{-1}]A) \pmod \ell$$ is supposed to thwart this anyway; if it doesn't, the signature scheme is broken.

So there are cryptosystems in which point validation doesn't matter no matter what curve you use, and you could use a variety of different curves for different purposes when you're designing a system, some of which require point validation in some cryptosystems and some of which don't. But complexity is the enemy of security, and if you can reuse the same curve—e.g., Curve25519—for many different purposes, then the cost of designing and implementing the system securely is lower.

$\endgroup$
9
  • $\begingroup$ Minor question: I thought that, with X25519 (without cofactor DH or setting the lsbits to 0), the attacker could learn only the 2 lsbits, not 3. Yes, the cofactor is 8, however, I had thought that the subgroup of lower order points was isomorphic to $\mathbb{Z}/4 \times \mathbb{Z}/2$; the attacker could use that, but that gives them the private value modulo $\text{lcm}(4, 2) = 4$. Admittedly, this is not a big deal; however, am I missing something? $\endgroup$
    – poncho
    Sep 5 '17 at 17:49
  • $\begingroup$ If $M$ has order 8, then there are 8 distinct values of $[n]M = [n \bmod 8]M$, from which the adversary can solve the easiest ECDLP ever to learn $n \bmod 8$, no? Am I missing something? $\endgroup$ Sep 5 '17 at 18:43
  • $\begingroup$ My mistake; I had thought that the weak subgroup was $\mathbb{Z}/4 \times \mathbb{Z}/2$; it's actually isomorphic to $\mathbb{Z}/8$. $\endgroup$
    – poncho
    Sep 5 '17 at 18:59
  • $\begingroup$ My mistake; I had apparently failed to read your question: of course if the subgroup of order 8 is isomorphic to $\mathbb Z/4\mathbb Z \times \mathbb Z/2\mathbb Z$, then the maximum order of any element is 4, and indeed at best you learn $n \bmod{\operatorname{lcm}(4,2)} = n \bmod 4$. But, e.g., the points $\pm[\ell]x^{-1}(4)$ have order 8, so the subgroup must be $\mathbb Z/8\mathbb Z$. $\endgroup$ Sep 5 '17 at 19:42
  • 1
    $\begingroup$ @Lery: Really, I think the controversy is overblown and enclosed in tunnel vision. The real lesson is that you need to pay attention to how a DH function fits into your larger protocol, just like you need to pay attention to how a curve fits into a DH construction. Need each user to influence the outcome? Don't just hash the field element $x([ab]P)$ to derive the shared secret; hash the tuple $(x([ab]P),x([a]P),x([b]P))$. No full input validation needed (are $A$ and $B$ both in $\langle P\rangle$?), no partial input validation needed (is $[b]A$ or $[a]B$ the identity?), no branches needed. $\endgroup$ Sep 8 '17 at 2:44
1
$\begingroup$

Actually, ECDH with Weierstraß curves is normally specified by ANSI X9.63, which mandates validation (it is in section 5.2.2.1 of my copy of X9.63-2001).

If you consider curve equations $Y^2 = X^3 + aX + b$ for a given constant $a$, and any point $(X,Y)$ in the whole plane is part of one such curve (simply set $b = Y^2 - X^3 - aX$). If working over a field of $q$ elements, then you have $q$ curves. Doing ECDH is safe only as long as you play on curves with a proper order (basically prime order, or maybe a prime multiplied by a very small cofactor). If you receive a point $(X,Y)$ but don't check whether it falls on the intended curve, and then proceed to multiply it by your secret ECDH key, then you may be doing the multiplication in a subgroup of very small order, thereby leaking information on your private key. This is bad.

RFC 7748 specifies two curves, called "Curve25519" and "Curve448", for which the ECDH does not need validation, because of the two following reasons:

  • In their ECDH specifications, only the $X$ coordinate is transmitted; the $Y$ coordinate is rebuilt dynamically from the equation (this is equivalent to something called "point compression")(*). That way, the point you will work on may fall only on two specific curves (the formal curve, and its "twist"), not a bazillion of possible curves.

  • Curve25519 and Curve448 were chosen so that both variants of each curve are "safe" for ECDH (order is a big prime multiplied by 4 or 8).

NIST curves cannot avoid validation because:

  • Points are usually conveyed as $(X,Y)$, not $X$ only. Point compression is not well supported by implementations (possibly because there used to be some patent issues on point compression).

  • Even if using point compression, the twist curve is not safe.

Fortunately, curve validation is inexpensive, both in CPU time and code size, so good implementations will do it with very little overhead. Unfortunately, there are bad implementations out there...

As a side note, Curve25519 and Curve448 also exist as an alternate form called a "twisted Edwards curve", with a different equation. When using Edwards curve, point validation is back! See for instance RFC 8032, section 5.1.3: a point is received as one coordinate ($x$) and the second coordinate ($y$) is recomputed; this is point compression. When the rebuilding fails, the received point is rejected.

Therefore, point validation is avoided only for some specific curves designed specifically to avoid point validation, and even for those curves, you may skip validation only for ECDH, not for other usages.


(*) Yes, I know that there are details and I am simplifying here.

$\endgroup$
1

Your Answer

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