Re: [Cfrg] Consensus and a way forward

[Ilari Liusvaara <[e-mail]>]

On Wed, Nov 26, 2014 at 09:26:10PM -0800, Watson Ladd wrote:
> On Wed, Nov 26, 2014 at 8:25 PM, Benjamin Black <[e-mail]> 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