Re: [Cfrg] draft-ladd-safecurves-02

Robert Ransom <rransom.8774@gmail.com> Sat, 11 January 2014 18:06 UTC

Return-Path: <rransom.8774@gmail.com>
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 65AE51AE0A8 for <cfrg@ietfa.amsl.com>; Sat, 11 Jan 2014 10:06:51 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.45
X-Spam-Level:
X-Spam-Status: No, score=-1.45 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, MIME_8BIT_HEADER=0.3, SPF_PASS=-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 xDoxy__flYRZ for <cfrg@ietfa.amsl.com>; Sat, 11 Jan 2014 10:06:49 -0800 (PST)
Received: from mail-qc0-x230.google.com (mail-qc0-x230.google.com [IPv6:2607:f8b0:400d:c01::230]) by ietfa.amsl.com (Postfix) with ESMTP id AD5651AE086 for <cfrg@irtf.org>; Sat, 11 Jan 2014 10:06:49 -0800 (PST)
Received: by mail-qc0-f176.google.com with SMTP id e16so2744002qcx.21 for <cfrg@irtf.org>; Sat, 11 Jan 2014 10:06:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=pKLPbhxllYZbxS9odc1oRfvrEq7MSXTn7gFzp+Y3l/g=; b=DT/oUkzE3VOnWwbhkrF56x5+s5CauH0J6xmEoJ3qUigeG4jUbG25xJOxqpHwiIawks YHTs1xW9hnN0WWyWtwhvUeg25b0pGbg+I/NOXaZ6FGTp04AR91Z+rjJ9Mjt7HvZ3jMnf Gve6kd9EBDz9Kc48ucUruCSRYtG2J0gLzXM5a/nStr8SvaQpYUAFm90/o3Bb+zTCHVtw XDGXclJ+9OIJb95Hs0og+dQGmprJ2rC6rdz7WqtNvjBm9w84HT3kB3ziiA5Fob1+cDiG JtUf4zblA+RoZ9OlVMIZSLaZMl4h/12W6X827iBV7IpboFfKrObMEZQO6RruzPSLcl8k lH3Q==
MIME-Version: 1.0
X-Received: by 10.224.3.10 with SMTP id 10mr21225342qal.58.1389463598960; Sat, 11 Jan 2014 10:06:38 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Sat, 11 Jan 2014 10:06:38 -0800 (PST)
In-Reply-To: <52D17510.8060207@elzevir.fr>
References: <CACsn0c=uuzsH3Zd-tPEAMsxAbk-RpQEHpfbTh9gHJi5ggjT+qg@mail.gmail.com> <52D17510.8060207@elzevir.fr>
Date: Sat, 11 Jan 2014 10:06:38 -0800
Message-ID: <CABqy+srsziudPbVUFUU3uWJzDonEG_n6HFBSypP2c6+=6a6naw@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: =?UTF-8?Q?Manuel_P=C3=A9gouri=C3=A9=2DGonnard?= <mpg@elzevir.fr>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] draft-ladd-safecurves-02
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: Sat, 11 Jan 2014 18:06:51 -0000

On 1/11/14, Manuel Pégourié-Gonnard <mpg@elzevir.fr> wrote:
> Hi,
>
> Notes taken while reading -02 (in order of reading, so mixing typos with
> more
> important comments).
>
> - abstract: why mention the Jacobian rather than say "elliptic curves" (as
> you
> do in the intro)? Maybe say that DDH is *believed* to be hard, too.
>
> - end of the intro: "then short Weierstrass curves": then -> than
>
> - section 2 "Validation information is given at [SAFECURVES]." What do you
> mean
> exactly? Is it a repeat of "Proofs of all properties claimed exist in
> [SAFECURVES]." in the intro, or do you mean something else?
>
> - as an implementer, I'd have a preference for constants in hex. Also, I
> don't
> like the formatting very much. Starting each constant on a new line might
> help.

The basepoints should be specified by the value of the primary
coordinate and the sign bit of the other coordinate, not specified as
a pair of integers where one is too huge to be useful.

> - I second Alyssa's suggestion to split the content in two sections, too.

I strongly oppose separating the curves which happen to have been
first specified in Montgomery form from the curves first specified in
Edwards form.  Every Edwards curve is isomorphic to a corresponding
Montgomery curve and vice versa.  (That is the reason (the *only*
reason) that Dr. Bernstein advocates twist security for Edwards curves
-- twist security is only important for curves used in Montgomery
form.)

The document should also specify the equivalences.

> - formulas for Montgomery curves: I think "P_i = [i] P_1" is not what you
> want
> to say.

I don't currently remember how the inputs and outputs for those
formulas are arranged, but it's possible that “P_i = [i] P_1” may be a
useful mnemonic to give *after* explaining that the inputs are P, Q,
P-Q (in some order) and the outputs are 2P and P+Q (in some order).

> Also, I'm not sure the reference to the Kummer curve is of any
> help.

I agree that that reference in the current draft (-02) is not helpful,
but the fact that a Montgomery line is something other than a group is
absolutely critical, and it needs to be both stated and clearly
explained.  The fact that such a near-group for a genus-1 curve is
called a “Kummer line” should be part of the explanation.

> - why give the formulas for Edwards with common sub-expressions already
> eliminated, but not for Montgomery?

Presumably because the formulas he copied from EFD happened to be that way.

More importantly:

* The addition formula given for Edwards curves uses the additional
curve parameter c, but with no indication of what that parameter is.

* The addition formula given for Edwards curves uses ‘inverted’
coordinates.  No one should use those in any new implementation --
they cannot represent the point at identity, and so cannot be used in
constant-time multiplication procedures.

* The document gives one addition formula, but no guidance as to how
to use it in a multiplication routine that achieves the ‘security and
performance advantages’ mentioned in the introduction.

> - point encoding "GF_p point on E(GF_p)" isn't that a bit redundant?
>
> - "Formulas for decompression are left as an exercise to the reader." You
> can't
> be serious. The goal should be to actually help people write correct
> implementations, which this kind of funny (?) non-reference does not.

Indeed.  Dr. Bernstein had the good sense and decency to give the
exact algorithm for Edwards-form point decompression in coordinate
fields where q \in 5 + 8\ZZ in his Ed25519 signature scheme paper.

> - security considerations: "some checks in some protocols": which and
> which?
> "certain attacks": which ones? Again, please, this should be a technical
> document giving precise, actionable information.

I agree.  But I think Watson Ladd really believes that a good standard
should not specify how to implement it.

> - IANA: sorry if this is a dumb question, but I'm not sure I see the need
> for a
> IANA register here (an would it be only for the "chicago" curves or all
> known
> curves)? So far, there are protocol-specific registries (eg, TLS Named
> Curves)
> and it seems to me it has been enough.

I see no reason to have IANA try to maintain an out-of-date copy of
the list on the SafeCurves web site.  (If there is a good reason to
create an IANA registry for these, the draft will need to specify how
the registry should be managed.)

> - OTOH, it would probably be good to have OIDs for the curves here, since
> they
> could be used by many protocols.


I strongly oppose publication of this draft as an RFC.  In its current
state, it will lead readers to produce defective implementations with
most of the security flaws that ‘SafeCurves’ are meant to avoid.

I also do not believe that Watson Ladd is willing to make the changes
needed to make this document useful.  I am not willing to contribute
to this document further.


Robert Ransom