Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

[Watson Ladd <[e-mail]>]

On Mon, Dec 1, 2014 at 4:18 PM, Benjamin Black <[e-mail]> wrote:
> Several of the responses to this proposal leave me a bit confused as it
> appears they were written without having read the draft. If your perspective
> is that Curve25519 must be adopted, and under no circumstances will
> alternatives be considered, then it will be difficult to reach an
> accommodation. If instead you are interested in achieving consensus, the
> first step should be understanding alternative viewpoints and considering
> how we might find a middle ground. The draft documents such a middle ground.
>
> The draft we (Microsoft, Google and NXP) posted describes rigid generation
> of parameters for (twisted) Edwards curves. The generation process is about
> as minimalist as can be for generation of secure curves. Additional rules
> intended to produce a specific outcome are the definition of flexibility.
> Constructing a curve explicitly for a specific implementation technique is a
> short-sighted and contrary to good engineering process.

To reach that middle ground you changed the generation procedure from
the initial draft to match E-521. Professor Bernstein has pointed out
that there is an (admittedly minor) security related reason why he
rejected PinkBikeShed. Why not add this criterion to the generation
method? You already did it to get the right curve modulo 2^521-1 after
all. You also changed the choice of primes. Why not change the choice
of prime near 2^384 as well?

Were the initial parameters not rigid, or are these new parameters less rigid?

>
> In addition, having a clear, rigid generation process for the parameters
> allows those in need of curves for specific applications to easily and
> deterministically produce them. Several people involved in hardware
> implementation have expressed their concern with only producing curves based
> on special primes. For such scenarios, a random prime selection section
> could be added to the draft and the resulting curves need not find their way
> into TLS at all. Again, being creative in accommodating the needs of the
> participants is the key to consensus.

What do random primes have to do with anything related to the request
from the TLS WG, particularly if we don't recommend them for TLS?

>
> Recall that our preference was for similarly rigid generation of 3 mod 4
> special primes. We still hold that preference, but we believe so strongly in
> finding a middle ground acceptable on performance and security that we have
> agreed to a process that does not produce most of the "NUMS" curves and does
> not include our preferred prime at the 256-bit level. p = 2^255 - 19 with
> rigidly generated parameters is that performant and secure middle ground.

What about the 384 bit level, where the choice made in the draft is
not a middle ground between performance and (mythical) security, but
rather to favor a rather poor choice of prime? This was a clearly
political exercise.

>
> The generated curve for p = 2^255 - 19 is not Curve25519 and is not
> isogenous to the Montgomery curve in X25519. It is, however, not vulnerable
> to the extremely minor concern that a private key is a multiple of the group
> order. The isogenous minimum A Montgomery curve does have that concern, and
> as has already been mentioned it is a trivial problem with a trivial
> solution. Those working with signatures or ECDH with x,y points, which are
> the majority of scenarios outside TLS ECDH via X-only point format (and
> associated Montgomery isogeny), don't need to worry about it at all.
>
> As some have noted, this new curve can actually be faster than Curve25519.
> Preliminary benchmarking of our implementation of it bears that out. It is
> unfortunate that, having argued at great length for the primacy of
> performance in selection, people are rejecting similar performance gains
> because some code has already been deployed or multiplying by 8 instead of 4
> represents a security threat.

I'm having trouble seeing how a change between constants of roughly
the same size can lead to a 10-15% performance gain. What I can see is
how an implementor can compare a highly optimized implementation of
one curve to a less-well optimized implementation of another, then
make a claim about the curves.

Unless the benchmarking code is made publicly available, I'm skeptical
of such claims.

Sincerely,
Watson Ladd