### [Cfrg] curves, coordinates, and computations

"D. J. Bernstein" <djb@cr.yp.to> Tue, 29 July 2014 22:13 UTC

Return-Path: <djb-dsn2-1406671250.32404@cr.yp.to>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (ietfa.amsl.com [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 2195F1B28FA
for <cfrg@ietfa.amsl.com>; Tue, 29 Jul 2014 15:13:22 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: 1.473

X-Spam-Level: *

X-Spam-Status: No, score=1.473 tagged_above=-999 required=5
tests=[BAYES_20=-0.001, RCVD_IN_DNSWL_LOW=-0.7,
TO_NO_BRKTS_PCNT=2.173, UNPARSEABLE_RELAY=0.001] autolearn=no

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id F1v4UsvSBqL3 for <cfrg@ietfa.amsl.com>;
Tue, 29 Jul 2014 15:13:19 -0700 (PDT)

Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224])
by ietfa.amsl.com (Postfix) with SMTP id 25CB71B28F3
for <cfrg@irtf.org>; Tue, 29 Jul 2014 15:13:18 -0700 (PDT)

Received: (qmail 5864 invoked by uid 1011); 29 Jul 2014 22:13:19 -0000

Received: from unknown (unknown)
by unknown with QMTP; 29 Jul 2014 22:13:19 -0000

Received: (qmail 8708 invoked by uid 1001); 29 Jul 2014 22:13:12 -0000

Date: 29 Jul 2014 22:13:12 -0000

Message-ID: <20140729221312.8707.qmail@cr.yp.to>

From: "D. J. Bernstein" <djb@cr.yp.to>

To: cfrg@irtf.org

Mail-Followup-To: cfrg@irtf.org

Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/rykhMuD80Lc_XfVuL3r3vmN4FGM

Subject: [Cfrg] curves, coordinates, and computations

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.15

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Tue, 29 Jul 2014 22:31:30 -0000

I've noticed that quite a few proposed requirements and comments have been confusing three separate decisions: * which _curves_ should be used in protocols such as TLS; * which _coordinates_ should be used in protocols; and * which _computations_ the implementations will carry out. For the _curves_ there are several options under discussion: * short Weierstrass curves such as NIST P-256, the curve y^2 = x^3-3x+c mod 2^256-2^224+2^192+2^96-1, where c is a big random-looking number that I won't repeat here; * Montgomery curves such as y^2 = x^3+486662x^2+x mod 2^255-19 (Curve25519); * Edwards curves or more generally twisted Edwards curves such as x^2+y^2 = 1+3617x^2y^2 mod 2^414-17 (Curve41417) or Microsoft's -x^2+y^2 = 1+15342x^2y^2 mod 2^256-189. For the _coordinates_ sent through the wire there are also several options, including * short-Weierstrass x and y coordinates (often with y compressed); * short-Weierstrass x by itself (proposed in the first ECC paper); * Montgomery x by itself (used in practically all deployments of Curve25519 for one-time DH and for longer-lasting DH); * Edwards x and y (increasingly widely deployed in Ed25519 signatures, with y compressed); and many more. For the _computations_ there are also several options, including * the Montgomery ladder (typical advertisement: excellent speed together with unmatched simplicity), * windowed "extended Edwards" scalar multiplication (typical advertisement: even faster than Montgomery for keygen), and * windowed "Jacobian" scalar multiplication (typical advertisement: reusing older software). There seems to be a common misconception that making a decision at one of these levels forces the decisions at all of the other levels. In fact, as I'll describe in detail below, specifying a curve still leaves tremendous freedom to the protocol designer to choose coordinates: * Edwards curves support Edwards coordinates, Montgomery coordinates, and short-Weierstrass coordinates. * Montgomery curves with points of order 4 (e.g., Curve25519) support Edwards coordinates; all Montgomery curves support Montgomery coordinates and short-Weierstrass coordinates. * Short Weierstrass curves with cofactor 1 (e.g., P-256) have by far the worst compatibility---obviously they support short-Weierstrass coordinates, but they fail to support Edwards coordinates and fail to support Montgomery coordinates. Furthermore, specifying a curve and coordinates still leaves tremendous freedom to the implementor to choose a computation. For example, Edwards curves in short-Weierstrass coordinates support the Montgomery ladder for scalar multiplication. See https://www.imperialviolet.org/2013/05/10/fastercurve25519.html for another example spelled out in detail. Cofactor-1 short Weierstrass curves are again the worst case for compatibility; for example, they don't support the Montgomery ladder, and they don't support extended-Edwards scalar multiplication. As a concrete compatibility example, let me take NIST's ECDSA standard, which NIST defines mostly via reference to ANSI X9.62. The standard is parametrized by a choice of short Weierstrass curve Y^2 = X^3+aX+b mod p meeting various criteria (or a binary curve; for simplicity I'll ignore this option). What's sent through the network as a public key---what actually matters for interoperability of public keys---is * the X-coordinate of a point on the curve Y^2 = X^3+aX+b mod p and * the Y-coordinate of the point, encoded as a string in a specified way, optionally with Y compressed. Everybody knows that NIST P-256 is compatible with the ECDSA standard. The NIST P-256 curve y^2 = x^3-3x+c obviously matches the format Y^2 = X^3+aX+b. One can check that P-256 meets all of the standard criteria. What about Montgomery curves? For example, does Curve25519 support ECDSA? Yes, it does. This is a trivial shift of coordinates: substitute x = X-486662/3 and Y = y into y^2 = x^3+486662x^2+x to obtain Y^2 = X^3-(236839902241/3)X+(230521961007359098/27) which is in exactly the short-Weierstrass format allowed by ECDSA. One can also check that this curve meets all of the criteria required by the ECDSA standard: for example, the Curve25519 cofactor 8 is well within the allowed range of cofactors (FIPS 186-4 says cofactor<=2^14 for 255-bit primes). One standards-compliant way to specify this example of ECDSA is to specify a = 236839902241/3 etc., not even mentioning the equation y^2 = x^3+486662x^2+x normally used to define Curve25519. What about Edwards curves? Does Microsoft's -x^2+y^2 = 1+15342x^2y^2 mod 2^256-189 support ECDSA? The answer is again yes, although getting to a Weierstrass curve is slightly more complicated; see below. If you have a complete implementation of standard ECDSA then you can simply plug these curves into the implementation. You'll get better speeds with a reduction method specialized to the new primes, raising the question of what speeds are possible for each prime (see, e.g., https://www.imperialviolet.org/2010/12/21/eccspeed.html), and what simplicity is possible when you don't care about speed, and the tradeoffs possible between the desiderata of speed and simplicity. But those issues aren't the topic of this message. If you have a more limited implementation of ECDSA, for example one specific to NIST P-256, then you'll certainly need to add code for the new primes, but there's a good chance that the code has at least a high-level Jacobian scalar-multiplication layer that works for arbitrary short-Weierstrass curves. For example, you might have copied the scalar-multiplication method stated in the ANSI standard, although this particular method leaks tons of information through timing and is much slower than other methods---the sort of code (and standard) that ought to be replaced no matter what happens with the curve choice! Beyond the benefits of a new prime, using ECDSA with these new curves gives you access to better scalar-multiplication options. For example, in the case of Curve25519: * Take the short-Weierstrass coordinate X provided as input. * Subtract 486662/3 to obtain the Montgomery coordinate x. * Use the Montgomery ladder for scalar multiplication. (This is the very short code that I displayed in my talk in Toronto.) * Add 486662/3. (This gets back to the short-Weierstrass output.) * Use a few extra lines to compute the other output y. This code is considerably simpler, faster, and less error-prone than the scalar-multiplication procedure in the ANSI standard. This option isn't available for NIST P-256, so if you have to support both curves then you might prefer the old-fashioned Jacobian approach, but other people will still take advantage of the Montgomery-ladder option. As a fancier example, starting from the Montgomery coordinates x and y of a Curve25519 point, you can compute Edwards coordinates X = sqrt(486664)x/y, Y = (x-1)/(x+1) on the corresponding Edwards curve X^2+Y^2 = 1+(121665/121666)X^2Y^2. You can then use, e.g., windowed extended-Edwards scalar multiplication. Compared to Jacobian scalar multiplication this is considerably faster and has the huge advantage of not having to worry about exceptional cases in the code. This generalizes to any complete Edwards curve; see the Bernstein--Lange paper that introduced Edwards-curve cryptography. You might be worried about the divisions involved in these conversions between Edwards coordinates and other coordinates. This is one of the motivations for EdDSA, and in particular Ed25519, which sends Edwards coordinates for Curve25519 through the wire (compressed) rather than sending short Weierstrass coordinates ECDSA-style or sending Montgomery coordinates. One shouldn't overestimate the speed benefit here--- * the two divisions in a conversion are trivially merged into one, * constant-time division is only about 10% of optimized constant-time scalar multiplication, and * there are several well-known tricks to merge coordinate-conversion divisions into other operations, typically reducing 10% below 1% ---but there's an obvious benefit in simplicity. This isn't compatible with ECDSA, but ECDSA also has many other problems that motivate doing something new. (Similarly, sending the Montgomery x-coordinate has clear benefits for ECDH/ECDHE.) An intermediate transition option would be to support both Ed25519 and ECDSA with Curve25519, sharing all of the underlying scalar-multiplication code, with an eye towards eventually allowing simpler implementations that support only Ed25519. Similarly, (1+y)/(1-y) - 30682/46029, sqrt(-4/15343)(1+y)/((1-y)x) are ECDSA-compatible coordinates for the Microsoft curve. These two coordinates satisfy a short Weierstrass equation. So choosing a twisted-Edwards curve such as the Microsoft curve doesn't rule out ECDSA, doesn't rule out the Montgomery ladder, etc. To summarize, all of the _curves_ under discussion support ECDSA. So I'm quite puzzled by Microsoft's "requirements" that "new curves" must "support standard ECDHE and ECDSA algorithms" and must "support standard EC point representations". The most obvious interpretations of these "requirements" are content-free. A subsequent Microsoft slide asserts that Montgomery curves ("curve family: Montgomery") "can't be used with ECDSA". This is simply wrong. There is no problem using Montgomery _curves_ with ECDSA. The fact that ECDSA specifies short-Weierstrass _coordinates_ means that sending Montgomery _coordinates_ would not be standards-compliant, but it's trivial to send short-Weierstrass _coordinates_ for a Montgomery curve. It's particularly strange that Microsoft makes this assertion only for Montgomery curves and not for (twisted) Edwards curves. If Microsoft is trying to suggest that simply sending the Edwards x and y is compliant with the ECDSA standard, then a retraction is required; again, the ECDSA standard specifies short-Weierstrass coordinates. If Microsoft is trying to suggest that one can use Edwards _curves_ with ECDSA, then this is of course true, but it's not an advantage of Edwards over Montgomery. I'm similarly quite puzzled by Nigel Smart insisting on "curves" whose "definition is in Weierstrass form". If this were actually imposed as a requirement then all of the curve proposers would go through the trivial exercise of reformulating all of these curves in Weierstrass form, elevating style over content. This superficial translation wouldn't remove the good reasons, or the ability, for new protocols to specify other _coordinates_ (as in Ed25519), and similarly it wouldn't remove the extended implementation options that I've described above. The most flexibility would still be achieved by translated Montgomery curves and translated Edwards curves. Nigel also insists on "curves" whose "data format for point transfer" is "in Weierstrass form". This is a syntax error, asking the curve object to answer a "data format" question that it doesn't know how to answer. I understand that Nigel wants protocols to use old-fashioned Weierstrass coordinates, but he's wrong in suggesting that this could rule out any of the curves under discussion. (As a side note, I don't know what his rationale is, while I see important advantages to other choices.) Let me again emphasize that requiring _curves_ to support ECDSA etc. is content-free. Every curve under discussion supports ECDSA, and this clearly isn't going to change. Nigel is wrong in suggesting that this sort of requirement would exclude Edwards curves, and Microsoft is wrong in suggesting that this sort of requirement would exclude Montgomery curves. Surely a requirement (or desideratum) that confuses people, and that doesn't actually accomplish anything, should be eliminated. The actual story is that Montgomery curves and Edwards curves support _extra_ options---options that have undisputed value---while _also_ supporting the old-fashioned options. As far as I can see, this confusion is _almost_ the entire source of opposition to Montgomery curves and/or Edwards curves. The reason I'm saying "almost" is that I also saw Nigel claiming that cofactor 1 has a critical security benefit ("vital to avoid mistakes")---but details to support this claim are missing. Note that * IEEE allows cofactors; * ANSI allows cofactors; * NIST claims that "For efficiency reasons, it is desirable to have the cofactor be as small as possible", but NIST allows larger cofactors and doesn't claim that smaller cofactors matter for _security_; and * Certicom's pet SEC 1 standard originally required cofactor<=4 but switched in 2009 to allowing larger cofactors. Post-NIST research has produced overwhelming evidence that properly chosen curves with larger cofactors, when implemented in the most natural ways, _eliminate_ several critical pitfalls that nobody knows how to eliminate for cofactor 1. See http://safecurves.cr.yp.to/ladder.html http://safecurves.cr.yp.to/twist.html http://safecurves.cr.yp.to/complete.html for summaries and references. Does anyone have a serious argument against Montgomery and/or Edwards? I'm not aware of anything. I think there's an overwhelming case for insisting that each new curve be compatible with the widest range of options: short Weierstrass coordinates, Jacobian scalarmult, Montgomery coordinates, Montgomery scalarmult without point validation, Edwards coordinates, Edwards scalarmult without special cases, etc. This means requiring each curve to have * a point of order 4, to support Edwards coordinates and Montgomery coordinates (improving simplicity, speed, and security); * a unique point of order 2, to eliminate failure cases in the simplest possible way; and * twist security, so that input validation isn't necessary for single-coordinate DH. Some examples of curves meeting all these criteria are Curve25519, Curve41417, E-521, and Microsoft's new twisted-Edwards curves---again, it's wrong to think that Edwards curves aren't Montgomery-compatible or vice versa. Examples of curves that _don't_ qualify are * the NIST curves (which obviously are grandfathered in), * the Brainpool curves (ditto), and * Microsoft's non-Edwards curves (which I think should be tossed). Excluding inferior options will obviously simplify the discussion. For example, if all remaining options automatically support Elligator 1 and/or Elligator 2, then there's no need to discuss which applications care about this support, and whether Elligator Squared is adequate. It would also be helpful for CFRG to figure out which range of ECC mechanisms it's recommending: for example, just a curve choice, or also coordinate choices for common applications. Since a large part of the motivation for new curves is to enable better implementations, it makes sense to carefully consider and document major implementation options, even though it's ultimately up to the implementor to decide what to do within the bounds of interoperability. ---Dan

- [Cfrg] curves, coordinates, and computations D. J. Bernstein