Re: [Cfrg] Progress on curve recommendations for TLS WG

Robert Ransom <rransom.8774@gmail.com> Fri, 08 August 2014 14:40 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 A30C51B2A77 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 07:40:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 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, 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 8XuxCi-YlrFu for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 07:40:18 -0700 (PDT)
Received: from mail-qa0-x233.google.com (mail-qa0-x233.google.com [IPv6:2607:f8b0:400d:c00::233]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4B8A41B2A54 for <cfrg@irtf.org>; Fri, 8 Aug 2014 07:40:18 -0700 (PDT)
Received: by mail-qa0-f51.google.com with SMTP id k15so5628477qaq.10 for <cfrg@irtf.org>; Fri, 08 Aug 2014 07:40:17 -0700 (PDT)
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; bh=oKr+25/58A4clnKFLORPiHNlm/BJpNFeBHKq5lsnn08=; b=mXtnBoQ3UfTTURsEVpqdQHGPOApdcu9dPe2TT2lSc1dNaGVVgZW5ve7aRHb6CNsRjM lIfK8kp8Q9BxWvvqm/7wFIc5L/opkGWmC4ZXL+WlabVOiK00qQFUM3XOA6L08Og4ihZ6 qAmlejX7vi7J/ctPAiLSuCzTa7tl2kmvcOeUoQUrqMLJSFYgkh/wsVQzBN/zP0FwAk4A mUM24ZH5gHf5GxShGUs+ns6HIW3xy4QzGqd0qgmpEPmD3aO/524PkyZrO3LsYy1fp+YK zVRNH0wruciYiOynEl9WTTFwZK75FNjadyAr6Irn8KjQbRRSL81Jyxg7la8LAiFbpvnF IEuQ==
MIME-Version: 1.0
X-Received: by 10.224.86.5 with SMTP id q5mr39492979qal.36.1407508817482; Fri, 08 Aug 2014 07:40:17 -0700 (PDT)
Received: by 10.140.86.135 with HTTP; Fri, 8 Aug 2014 07:40:17 -0700 (PDT)
In-Reply-To: <20140808141506.GA24645@LK-Perkele-VII>
References: <CFFB1371.2916E%kenny.paterson@rhul.ac.uk> <20140808141506.GA24645@LK-Perkele-VII>
Date: Fri, 8 Aug 2014 07:40:17 -0700
Message-ID: <CABqy+soiwptz+Vi-nT3GJgg-FrHGPXUc-wDYe1+Pb-b0CZXDog@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/hopy-wJOGxohzpQjidG2nS_S7Mo
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
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: Fri, 08 Aug 2014 14:40:19 -0000

On 8/8/14, Ilari Liusvaara <ilari.liusvaara@elisanet.fi>; wrote:

> b) Parameters

> With parameters, random choice is not wise, given that there are very few
> (I think 4 or 2 depending on bitlength[2][3]) rational choices for
> deterministic curve per prime. It would be very hard to reach similar
> rigidity via random process.

> [2] Complete Edwards (minimal |d|) vs. Complete Montgomery (minimal |a24|),
> q < 2^n vs. q > 2^n.

There is no trade-off between efficiency in Edwards form and
efficiency in Montgomery form -- a curve with small-integer Edwards d
has its Montgomery (A+2)/4 as the reciprocal of a small integer, which
is as efficient as having (A+2)/4 be a small integer itself.  *ALL*
new curves should be specified with small-integer Edwards d.  (I've
repeated this already recently, and included a link to formulas in
that message.)


The remaining less-than-perfectly rigid aspects that I know of in
selecting a deterministic curve parameter, given the coordinate-field
order p, are:

* cofactors (For p = 3 mod 4, do you settle for curve and twist having
cofactor 8 (as Curve3617 does), or insist on the minimal cofactor 4
(as Microsoft does; note that E-521 also has cofactor 4)?  For p = 5
mod 8, where either the curve or twist must have cofactor 8, do you
operate on the one with cofactor 8 (as Curve25519 does) or the one
with cofactor 4?)

* group size (For p = 3 mod 4, do you operate on the group with
smaller order (as Curve3617 and E-521 do, perhaps by accident, and as
the MSR curves do), or operate on the group with larger order (I don't
think anyone does this)?  For p = 5 mod 8, do you insist that both
groups have order greater than the power of 2 closest to p/8 (as
Curve25519 does, in order to make key generation hard to screw up)?)

* multiplicative embedding degree (Exactly how large, or how close to
maximal, do you insist that the curve's embedding degree be?)

There may be a few others.


Robert Ransom