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

From: "Paterson, Kenny" <[email-masked]>
Date: Sun, 27 Jul 2014 20:04:45 +0000

Dear CFRG,

We made good progress last week in Toronto and on the mailing list in
discussing requirements for curve selection, as well as getting into some
of the specifics of the different curve options.

The chairs have had requests to increase the time given to our discussion
of requirements in the light of the Toronto meeting, and we are happy to
accommodate that. We therefore plan to extend the previously announced
schedule so that this initial phase will run for another 2 weeks (until
Friday 8th August). We will then run the second phase (focussing on
concrete curve proposals) for 4 weeks, as previously planned.

Whilst it may be tempting to jump in and start discussing concrete
performance aspects of the different, specific curve proposals, or drift
off onto other topics entirely, the chairs would like to ask everyone to
try to focus on requirements for a bit longer. Here are a few questions to
help keep things on track and seed further discussion:

- What is the cost of keeping backwards compatibility with existing
defined point formats in RFC 4492, if any, for different curve shapes
(Edwards, twisted Edwards, Montgomery, Weierstrass-only form)?

- If ephemeral really means ephemeral, what are the implications for the
mix of fixed-base/variable-base computations in ECDHE and what, if any,
are the implications for the choice of curve type?

- Correspondingly, what are the implications for our choices if we accept
that ephemeral reuse is the expected behaviour?

- Do the current proposals (Curve25519 and friends, and the NUMS curves)
provide an adequate degree of rigidity that is likely to satisfy the
widest set of commentators? Or should we be thinking about generating
fresh curves using a public process having verifiably random inputs? What
would the likely impact be on performance?

- Would selecting curves that are not in Weierstrass form materially slow
down deployment?

Thanks for your considered inputs so far.

Regards,

Kenny (for the chairs)

---

From: Watson Ladd <[email-masked]>
Date: Mon, 28 Jul 2014 17:17:22 -0700

> (Edwards, twisted Edwards, Montgomery, Weierstrass-only form)?

The cost is the cost of the isogeny in and out. It should be possible
to make a table of isogenies between each format
and when they exist: the information is out there but scattered.

However, RFC 4492 treats point formats as opaque, and while crypto
libraries may assume all curves use a particular
format, this hasn't stopped them from adding Curve25519 support
through different API paths.

> are the implications for the choice of curve type?

If ephemeral means ephemeral, then we have 1 fixed+1 variable
multiplication. Variable multiplication alone no longer is as
important.

> that ephemeral reuse is the expected behaviour?

If all multiplications are variable base for ECDHE, Montgomery is the
clear winner here. (Actually, Gaudry genus 2, but
people seem less excited by it)

> would the likely impact be on performance?

I think minimal parameter is enough rigidity. Random inputs would have
to be the closing price and daily trade volumes of all S&P 500
constituents on some day in the fall: no one can manipulate that
because it is in the future. The impact of random primes would be
pretty bad:
the best reduction algorithms take quadratic time in the number of digits.
> - Would selecting curves that are not in Weierstrass form materially slow

I don't know the answer to this question.

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: Russ Housley <[email-masked]>
Date: Thu, 31 Jul 2014 15:11:43 -0400

Kenny asked for input on five specific questions.  Here are my thoughts on the first one.

> (Edwards, twisted Edwards, Montgomery, Weierstrass-only form)?

It is important to look at the use of ECC in TLS (RFC 4492), but we also need to look at PKIX since TLS will rely on certificates to bind the public key to the subject name.  RFC 5480 talks about ECC in certificates.  In my view, we should not ignore other uses of ECC in making this decision.  RFC 5753 talks about ECC for CMS; RFC 4754 talks about ECC for IKE and IKEv2; RFC 5349 talks about ECC for Kerberos PKINIT; RFC 5656 talks about ECC for Secure Shell.

For the certificate, RFC 5480 is aligned with the X9.62 specification, but the most difficult choices are not supported:
   o namedCurve -- MUST be supported.
   o implicitCurve -- MUST NOT be used.
   o specifiedCurve -- MUST NOT be used.

Since we have already limited the choice to named curves, we can simply assign names (object identifiers) to whatever curve we select.  This frees us from trying to make specify the curve using the X9.62 syntax.

For the TLS handshake, it seems to me that we can assign compatible values Supported Elliptic Curves Extension, and if necessary, for the Supported Point Formats Extension.

Russ