Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

From: Brian LaMacchia <[email-masked]>
Date: Sun, 20 Jul 2014 23:53:22 +0000

Well, not exactly, there are some important differences between Curve25519 and the two NUMS curve sub-families.  In particular, note that draft-black-numscurves includes both a set of Weierstrass *and* a set of twisted Edwards curves.  We included the Weierstrass curves in order to provide a deterministically-generated curve family for TLS that could be used as a "drop-in replacement" for the NIST prime curves in existing implementations.  This seems particularly important given that the TLS WG charter for TLS 1.3 focuses on improving the confidentiality aspects of the protocol, not its performance, and includes an admonition to "minimize gratuitous changes" to the protocol.  It has also been my experience that of those customers now asking for non-NIST curves, their motivation is more about the way the NIST curves were generated than their performance.  As the NUMS paper and released libraries demonstrate, one can get significant performance improvements over the NIST curves while still using Weierstrass curves at the same security level.

					--bal

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
Sent: Sunday, July 20, 2014 2:51 PM
To: Nigel Smart
Cc: [email-masked]
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

[snip]

This process began with Curve25519 for TLS. Then Microsoft showed up with substantially similar NUMS curves. I think it was obvious that new code was going to be written and this was understood by the TLS 1.3 WG.

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 20 Jul 2014 22:32:24 -0400

>  s: Denotes the bit length, here s in {256,384,512}.
>  p: Denotes the prime number defining the base field.
>  c: A positive integer used in the representation of the prime
>          p = 2^s - c.

In light of the recent discussion, would an attempt to reach a consensus 
on the value of p first has a higher chance for success at this point?

Assuming we want a new p, some arguments for a fixed F(p) are:

* the specs like Curve25519 are "stacks of layers", which prescribe a 
Curve, co-factor multiplication, F(p) operations, and an integer format 
(fixing p seems as one of the the least controversial tasks among these 
"layers")
* the performance advantage are mostly attributed to the F(p) operations 
(factor of n improvement in F(p) results in ~ n^2 curve performance)
* F(p) operations are platform-specific  (if there is assembler code 
used in the "stack", it will likely be restricted to the F(p))
* F(p) clarity will let hardware vendors focus on optimizations (and not 
worry about the entire stack)
* same F(p) doesn't prohibit multiple curves over it; ( fixing F(p) 
first and the curve or curves later will allow implementations to 
proceed sooner and enables a compromise )
* fixed F(p) allows greater flexibility to upgrade the curves (future 
curves will likely have hardware support available, sensitive code resused).
* fixed F(p) reduces the code size, increases interoperability 
(currently NUMS and Curve25519 are at odds here)

This narrow focus leads to these questions regarding the F(p):
* is a pseudo-Mersenne p an appropriate p for the new curves (the only 
cons to this so far is that such a p fixes the Curve's order to be close 
to 2^s; besides the trivial one that this makes the Pollard-rho faster)
* Curve25519 uses 255 instead of 256; however, CFRG can choose s=255 for 
128 bit security as well (citing "historic" reasons).

Should CFRG seek consensus on the above two questions first?

---

From: Watson Ladd <[email-masked]>
Date: Sun, 20 Jul 2014 20:13:28 -0700

On Sun, Jul 20, 2014 at 7:32 PM, Andrey Jivsov <[email-masked]> wrote:
> In light of the recent discussion, would an attempt to reach a consensus on
> the value of p first has a higher chance for success at this point?

What is wrong with the program the chair outlined for a competition, and how
does your proposal fix them?

> * the specs like Curve25519 are "stacks of layers", which prescribe a Curve,
> co-factor multiplication, F(p) operations, and an integer format (fixing p
> seems as one of the the least controversial tasks among these "layers")
> * F(p) operations are platform-specific  (if there is assembler code used in
> the "stack", it will likely be restricted to the F(p))
> * same F(p) doesn't prohibit multiple curves over it; ( fixing F(p) first
> and the curve or curves later will allow implementations to proceed sooner
> and enables a compromise )
> * fixed F(p) allows greater flexibility to upgrade the curves (future curves
> will likely have hardware support available, sensitive code resused).
> * fixed F(p) reduces the code size, increases interoperability (currently
> NUMS and Curve25519 are at odds here)

How long do you think this is going to take? It should be taking much
shorter than
the time it takes to design hardware. Furthermore, all of the choices
come with software
implementations liberally licensed.

I don't quite understand your replacement point: many tricks such as
hyper-and-elliptic,
endomorphisms (misleadingly called Koblitz curves), etc. require
primes with some special
properties or use extension fields. Even going to the Kummer surface
in genus 2 involves dropping
field size, so the F(p) will need to be sized differently.

Any future proposal if we need it can use an F(p) defined now, possibly.

> * is a pseudo-Mersenne p an appropriate p for the new curves (the only cons
> to this so far is that such a p fixes the Curve's order to be close to 2^s;
> besides the trivial one that this makes the Pollard-rho faster)
> * Curve25519 uses 255 instead of 256; however, CFRG can choose s=255 for 128
> bit security as well (citing "historic" reasons).

The extra word for the top bit is a pain. The loss of half a bit in
"security" is really de minimis.
> Should CFRG seek consensus on the above two questions first?

No, because that is not how this is being done, and there is a strong
(but rebuttable) presumption that
the chair knows what they are doing in organizing WG activities.

Sincerely,
Watson Ladd

>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 21 Jul 2014 02:15:11 -0400

On 7/20/2014 11:13 PM, Watson Ladd wrote:
> does your proposal fix them

I meant this as an additional nice to have property. I could state a 
specific requirement, e.g. "2^s-C with s max",  but my main point is to 
show a benefit to have a commitment to a fixed p for each s.

> implementations liberally licensed.

If there is an unquestionable winner, similar to an AES finalist, then 
there is no worry about universal adoption.

The issue with ECC has always been fragmented ecosystem. At this point 
we are looking at SuiteB / CFRG's choice split. A consensus on F(p) has 
benefits to get more support behind the CFRG choice.

The availability of software libraries is not helping the products that 
need hardware acceleration.

> field size, so the F(p) will need to be sized differently.

The importance of these other possibilities should be considered, of 
course. I had current contenders in mind. Fewer choices helps with adoption.

> Any future proposal if we need it can use an F(p) defined now, possibly.
Right, a fixed p with typical constrains on p covers many important 
choices of curves. We can hope that a large class of future curves 
should be able to use the same F(p) layer.

There is also hope that national standards may feel motivated to use the 
"standard p" on performance/hardware reasons with "their" curves, as 
opposed to completely defining the entirely new stack.

> "security" is really de minimis.
Could you please be more specific about how this brings in a new word?

( Even with the off-the-shelf CPUs, we currently have x86, x86_64, 
AVX2-256, and upcoming AVX-512. Please define your target instruction set)