Re: [Cfrg] Consensus and a way forward

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Thu, 27 November 2014 07:07 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>
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 8985C1A889B for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 23:07:56 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-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 jQdeml8Sb6PJ for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 23:07:53 -0800 (PST)
Received: from emh03.mail.saunalahti.fi (emh03.mail.saunalahti.fi [62.142.5.109]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8C61C1A8898 for <cfrg@irtf.org>; Wed, 26 Nov 2014 23:07:53 -0800 (PST)
Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi [88.112.44.140]) by emh03.mail.saunalahti.fi (Postfix) with ESMTP id E78A81887F3; Thu, 27 Nov 2014 09:07:49 +0200 (EET)
Date: Thu, 27 Nov 2014 09:07:49 +0200
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: Watson Ladd <watsonbladd@gmail.com>
Message-ID: <20141127070749.GA16874@LK-Perkele-VII>
References: <CA+Vbu7xvvfRWyqyE9sqU7VbjzNQZp+DwRWjaV3Lw0hjLr8ye1A@mail.gmail.com> <CACsn0cmcP=9s53kGPUdNjHyJpZMfEbCkWHEGiEwPCzfMWPGPnA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <CACsn0cmcP=9s53kGPUdNjHyJpZMfEbCkWHEGiEwPCzfMWPGPnA@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/qHSwpUcNrFccM4qlocQq3i4G-qs
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Consensus and a way forward
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, 27 Nov 2014 07:07:57 -0000

On Wed, Nov 26, 2014 at 09:26:10PM -0800, Watson Ladd wrote:
> On Wed, Nov 26, 2014 at 8:25 PM, Benjamin Black <b@b3k.us>; wrote:
> > All,
> >
> > Over the past couple of weeks we have been working with Adam Langley to see
> > if we could find a compromise with which we could all live. I'm pleased to
> > say we have been successful in accommodating our respective performance and
> > trustworthy generation concerns, and I hope the resulting proposal will be
> > attractive to others, as well. The generation procedure is document in a
> > draft I've just posted that can be found at
> > http://www.ietf.org/id/draft-black-rpgecc-00.txt .

Theoretically, the following Safecurves criteria could fail, even with p
at 205 bits or above (which guarantees Rho passes):
- Multiplicative transfer
- CM Discriminant
- Twist Multiplicative transfer

But any failure here would be VERY unlikely. I think there actually might
be values of p, which cause the algorithm presented to generate a known-
weak curve (but finding such p would be too hard to do currently).

> This document doesn't address the most important questions:
> 
> 1: What goes on the wire for ECDH? Montgomery points, points native to
> each curve formula, or Weierstrass points?
> 2: How are signatures computed?
> 3: Clear bits, multiply by cofactors, or check group membership?
> 4: Point compression or no point compression?
> 
> Given that generators are recorded for a prime order subgroup, it
> would seem that we are checking group membership, which will lead to
> the check being omitted and resultant, albeit minor, security issues.

Well, many ECC algos assume prime order subgroup.

Complete Edwards curves with h=4 and h=8 have quick check for low-order
points.

Also, I would like to see:

- The inverse Montgomery parameter (1/a24). This can be arranged to be
  small using suitable isomorphism and possibly quadratic twist.
- Conversion from Edwards form to Montgomery form.
- The Montgomery u corresponding to the base point.

For the first curve, those look to be:

1/a24 = -89748
u = (1+y)/(1-y)
u(P) = 11437681968289677273267944528525036915198860913446821942098597381479763892770

The transform has extra cost of 1 addition and 1 substraction (the division
is free, because it would be needed anyway).

> >
> > The simplest summary is that we have combined the prime preferred by Adam
> > and others at the 128-bit security level with the rigid parameter generation
> > we view as essential for producing the most trustworthy curves. We have used
> > the generation procedure to produce a new twisted Edwards curve based on
> > 2^255 - 19 and a new Edwards curve based on 2^384 - 317. These new curves
> > are given as test vectors in the draft, and are also given below.
> 
> Why 2^384-317 and not 2^383-31 or 2^389-21? This choice of prime
> really pinches the allowable radixes for carry-free multiplication
> reduction, and thus hurts efficiency, more than the 2^255-19 vs
> 2^256-189 decision at the lower security level. Far from being a
> simultaneous accommodation of the performance concerns and the
> generation concerns, this is clearly horse trading, with performance
> being given the choice of the 255 bit prime, and a similar improvement
> not happening at the 384 bit prime.

Well, at least 2^383-31 is 1 mod 8, which makes difficult to compute square
roots.

Looks like 2^389-21 saves a word on both 32 and 64 bit compared to
2^384-317 when using minimal-carry rational-base implementation.


-Ilari