Re: [Cfrg] 25519 naming

"D. J. Bernstein" <djb@cr.yp.to> Thu, 28 August 2014 06:54 UTC

Return-Path: <djb-dsn2-1406711340.7506@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 620C11A06CC for <cfrg@ietfa.amsl.com>; Wed, 27 Aug 2014 23:54:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.7
X-Spam-Level:
X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=0.001] autolearn=ham
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 PuwG8XXOdRzF for <cfrg@ietfa.amsl.com>; Wed, 27 Aug 2014 23:54:02 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 721E21A047B for <cfrg@irtf.org>; Wed, 27 Aug 2014 23:54:00 -0700 (PDT)
Received: (qmail 1967 invoked by uid 1011); 28 Aug 2014 06:53:59 -0000
Received: from unknown (unknown) by unknown with QMTP; 28 Aug 2014 06:53:59 -0000
Received: (qmail 20444 invoked by uid 1001); 28 Aug 2014 06:53:53 -0000
Date: 28 Aug 2014 06:53:53 -0000
Message-ID: <20140828065353.20442.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5CD3966@XMB116CNC.rim.net>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/udDc_-rcak1vxXhaWmWyeDq2PUw
Subject: Re: [Cfrg] 25519 naming
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: Thu, 28 Aug 2014 06:54:05 -0000

The ANSI ECDSA standard specifies elliptic curves mod p to have short
Weierstrass form y^2 = x^3+ax+b (see the "elliptic curves and points"
section), specifies ECDSA public keys as points on such curves ("key
pair generation"), specifies required encodings ("conversions between
data types that SHALL BE USED in the algorithms specified in this
Standard"---emphasis added), and in particular specifies the string
encodings of curve points (x,y) ("point-to-octet-string conversion").

The NIST ECDSA standard simply copies the ANSI formats (e.g., requiring
signatures to be "verified as specified in ANS X9.62"). As for Internet
wire formats, RFC 4492 states that its point formats "are specified in
[7]"; [7] is a normative reference, the ANSI ECDSA standard. RFC 4492
requires exactly these formats to be used on the wire in TLS. An
implementation using a different format wouldn't interoperate with
standard TLS ECDSA. Similar comments apply outside the TLS context.

I'm not saying that these are good standards. I'm also not saying that
it would be difficult for IETF to deviate from the previous standards
and specify a better wire format (as I recommend). I'm simply saying
that various claims here regarding ECDSA compliance are incorrect.

Last month I had already pointed out several serious errors in Microsoft
claims regarding compliance with existing standards such as ECDSA. I was
expecting a response to help move the discussion forward---for example,
withdrawing the claims, or perhaps pinpointing an area of legitimate
dispute if there is one. Instead some of the errors were simply
repeated. This is a disappointingly unproductive pattern. I would hope
to see more responsiveness in the future.

David Leon Gil writes:
  [ regarding short-Weierstrass coordinates, Montgomery coordinates, etc. ]
> I'd suggest that talking in this way is better than talking about
> different curves as 'coordinate systems'.

The word "coordinates" is broader than you think. See, e.g., polar
coordinates.

The distinction between, e.g., short-Weierstrass coordinates and Edwards
coordinates for Curve25519 is much more superficial than the distinction
between, e.g., Curve25519 and NIST P-256. The change of coordinates for
Curve25519 has no effect on field arithmetic (which is most of the code
in a good implementation), has only a small effect on overall efficiency
(since the implementor can change coordinates internally), and has a
provably negligible effect on important security metrics such as
discrete-logarithm difficulty.

It's important for curves to _support_ Montgomery coordinates and
(complete) Edwards coordinates, and there's an extra gain in simplicity
from choosing wire formats carefully (as in X25519 for DH and Ed25519
for signatures), but there are many other issues that transcend the
choice of coordinates and that should be discussed without the
distraction of specifying coordinates.

---Dan