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

From: Watson Ladd <[email-masked]>
Date: Mon, 21 Jul 2014 07:42:51 -0700

On Sun, Jul 20, 2014 at 8:56 PM, Benjamin Black <[email-masked]> wrote:
> On Sat, Jul 19, 2014 at 9:50 PM, Watson Ladd <[email-masked]> wrote:
>>
>> On Sat, Jul 19, 2014 at 4:09 PM, Benjamin Black <[email-masked]> wrote:
>> > "This stems from the fact that in some specific cases an algorithm and a
>> > curve are closely linked, with the two in some sense being carefully
>> > co-designed to gain security and performance."
>> >
>> > I am aware of claims to this effect, but I have seen no evidence of
>> > meaningful security or performance gains that would be seen in practical
>> > deployments in TLS. Similar claims have been made about the dramatic
>> > performance gains from certain curve forms, but the MSR research that
>> > produced the NUMS curves shows only slight performance advantages for
>> > those
>> > forms and only at low security levels. The ECCLib implementations
>> > support
>> > the conclusion that there is little benefit. Please provide specific
>> > supporting documentation for claims of significant, not incremental,
>> > performance or security gains for TLS from this.
>>
>> http://bench.cr.yp.to/
>>
>> Of course, when it comes to TLS, the two round trips cost far more,
>> but when we have 1-RTT the exponentiations become far
>> more critical for performance. Furthermore, CPU is not free, while a
>> server can do other things while it waits.
>>
>
> If TLS 1.2 is a guide, we are 5 years from widespread TLS 1.3 deployment. I
> suggest 2 round trips is a more realistic expectation here.

TLS 1.2 offered no compelling advantages. Everyone hates latency on the web.
>
> Even with a single round trip the network latency dwarfs differences in
> latency between the various curves under discussion. As session resumption
> becomes more widespread, and I am working to see that it does, the cost is
> amortized over multiple connections, making it even less of a concern.
> Regarding a server doing "other things" while it "waits" it seems you are
> not familiar with what actually happens in large scale online services.
> Front end servers terminating customer connections have nothing else to do
> but terminate connections and route requests. If a client is slow to respond
> that just means the server is handling connections/requests from clients
> that are responsive. There is no waiting.

If the server is slow to do a calculation, that reduces the number of clients it
can handle.
>
>>
>> >
>> > If we had evidence of radically improved security or radically improved
>> > performance at a given security level I would agree it would be worth
>> > exploring. For less than 10% performance gain and no security gain I see
>> > no
>> > reason to even consider adopting a new signature algorithm. In the
>> > abstract
>> > it might seem plausible, but when faced with updating a billion devices
>> > along with all of the supporting infrastructure previously hinted at, it
>> > has
>> > to be excluded.
>> >
>> > "My own view is that we should broaden our interpretation of the scope
>> > of
>> > the request to accommodate this fact, providing both new curves, and
>> > where
>> > appropriate, pointers to algorithms for those curves."
>> >
>> > There are multiple available options that support all relevant security
>> > levels, are faster than the NIST curves, and are compatible with
>> > existing
>> > infrastructure. There will always be new curves published. Their
>> > existence
>> > cannot mean we constantly push incompatible algorithms with enormous
>> > adoption costs at scale. If the goal is radically higher performance at
>> > a
>> > given security level and we don't care at all about compatibility, then
>> > why
>> > not consider genus 2 curves or other forms which are known to be
>> > enormously
>> > faster than even the twisted Edwards curves on the table? Throwing out
>> > compatibility is a very slippery slope.
>>
>> I can't think of a reason why hyperelliptic curves shouldn't be on the
>> table.
>> Is your argument that we should keep Weierstrass form despite the
>> barrier at 13 field ops
>> per addition? By my calculation twisted (a=-1) Edwards form enables a
>> 25% speedup, (10 field ops)
>> together with increased ease of avoiding side channels. The 13 field
>> op formula is not complete,
>> and the complete method is not fast.
>>
>
> My argument is that Montgomery is not necessary to achieve the desired
> performance improvements and thus there is no justification at all for
> tossing out the existing protocols.

How does Montgomery involve tossing out an existing protocol? Or
does protocol mean something to me it doesn't to me.

A change in form from short Weierstrass is necessary to have the absolute
best speed. The more speed, the more places we can stick encryption.

>
>>
>> Secondly, scale reduces, not increases, the cost of switching. Write
>> once, deploy many. There are not that
>> many TLS implementations out there. We need a new car, which requires
>> making a garage.
>> If we are going to pay that cost, why not add the extra zero dollars for
>> the
>> Ferrar
>>
>
> There are a dozen relevant implementations and a dozen versions of each. Or
> did you think this would only be implemented going forward? Beyond that, you
> are confusing unit cost with absolute cost and completely ignoring the
> significant infrastructure costs. Where in your write once, deploy many are
> HSMs upgraded? Where are compatibility problems between independent or old
> implementations handled? Where are the customer support costs? The extensive
> interop testing? Write once, deploy many is a myth.
>
> Your Ferrari analogy is apt: expensive, unreliable, and pointless except in
> the service of vanity.
>
>>
>> >
>> > I ask once again that you and the rest of the CFRG leadership along with
>> > the
>> > TLS leadership focus on practical, clear, and specific requirements for
>> > elimination of the NIST curves. Expanding the scope beyond that either
>> > means
>> > a hasty process producing something we are likely to regret in a few
>> > years
>> > (this is a 15+ year commitment!), or a long and careful process
>> > producing
>> > something we will still want around in a few years. Pushing new crypto
>> > on
>> > vendors and customers for the sake of maybe a few percent performance
>> > improvement, and that is exactly what we are discussing here, should
>> > alarm
>> > everyone.
>>
>> We are not eliminating the NIST curves, but providing high speed
>> alternatives that should look like reasonable
>> choice for the next decade. If you don't want Curve25519 in TLS, or
>> whatever emerges, don't enable it.
>>
>
> If we were only discussing new curves, as we should be, that would be true.
> What you and others are promoting is new curves and new protocols. The small
> performance advantage of Curve25519 over a good twisted Edwards curve in
> standard ECDHE does not justify a new protocol.
>
> I wouldn't be so quick to dismiss our deploying it. Might matter in whether
> it is successful.

How is Curve25519 a new protocol?  x-coordinate only transmission was
invented in the same paper with ECC. How does that make it harder to
deploy or not?

>
>>
>> If you want to be alarmed, go read any protocol other than IPsec that
>> the IETF has made that uses cryptography,
>> and try to prove it secure/write a clearly correct implementation. (My
>> particular favorite is PGP) However,
>> I'm pretty sure that DJB and Tanja gathered all the publicly known
>> attacks on ECC on the Safecurves site.
>>
>> >
>> > I will unfortunately not be in Toronto, but a number of others from
>> > Microsoft will be and I hope there can be productive discussion on this
>> > grounded a bit more in the facts of performance, security, and practice.
>>
>> Chrome wants Curve25519. SSH uses Curve25519. Somehow we added
>> Brainpool, which no one uses,
>> without this hullabaloo. Somehow Camelia (a Japanese AES knockoff) is
>> in TLS, despite being less studied
>> than AES. So what makes these new curve so much different?
>>
>
> It would be more honest and accurate to say the Chrome/Google team wants
> more efficient curves. Curve25519 was convenient. This applies to a number
> of folks considering Curve25519, as well. There are now other options which
> do not bring the incompleteness and incompatibility concerns of Curve25519.

But your incompatibility concerns would apply to a twisted Edwards
curve as well,
and to anything not in short Weierstrass form. I see this could be an issue:
how about "RTBD: represent a group, not a Kummer surface, for use in signatures"

(I also don't think its much of one: most of the work is in the field,
not the group.
That said the fixed-based speed of twisted Edwards is mildly useful)
>
> Regarding IETF crypto adoption, you are describing how things should work: a
> variety of systems are specified and they are integrated into protocols and
> deployed by customers, resulting in some becoming very popular and others
> seeing little use. That is not a flaw in the system, it is working as
> designed and it is exactly why I don't understand the point of this request.
> Specify them all, the market will know its own.

I'm going to send this to TLS: I must confess to not having seen much
discussion of this point.
However, with signatures it is impossible to ignore even slightly used
algorithms for risk of failing
to verify something valid. This has already become an issue in DNSSEC.

Sincerely,
Watson Ladd

>
>
> Ben
>
>>
>> Sincerely,
>> Watson Ladd
>> >
>> >
>> > Ben
>> >
>> >
>> >
>> > On Fri, Jul 18, 2014 at 3:29 PM, Paterson, Kenny
>> > <[email-masked]>
>> > wrote:
>> >>
>> >> Hi Ben,
>> >>
>> >> Thanks for your questions. I agree there is ambiguity. This stems from
>> >> the
>> >> fact that in some specific cases an algorithm and a curve are closely
>> >> linked, with the two in some sense being carefully co-designed to gain
>> >> security and performance.
>> >>
>> >> I understand very well your point that if it is "curves only", then
>> >> certain curves which are incompatible with existing standardized and
>> >> widely deployed algorithms would need to be excluded.
>> >>
>> >> My own view is that we should broaden our interpretation of the scope
>> >> of
>> >> the request to accommodate this fact, providing both new curves, and
>> >> where
>> >> appropriate, pointers to algorithms for those curves. (Note that CFRG
>> >> is
>> >> not being asked to produce I-Ds for either curves or algorithms, though
>> >> that kind of work might inevitably follow depending on the exact
>> >> choices
>> >> we recommend.) Of course, we can and should have discussion on this
>> >> question of broadening of scope, as you rightly suggest below.
>> >>
>> >> Concerning your second question, yes, in an ideal world we would reach
>> >> rough consensus on the requirements, and they would be clear, complete
>> >> and
>> >> unambiguous.
>> >>
>> >> If you are in Toronto next week, I'd be glad to continue the
>> >> conversation,
>> >> otherwise, let's do it on the list.
>> >>
>> >> Regards
>> >>
>> >> Kenny
>> >>
>> >>
>> >> On 18/07/2014 06:51, "Benjamin Black" <[email-masked]> wrote:
>> >>
>> >> >Kenny,
>> >> >
>> >> >
>> >> >There is rather a lot of ambiguity in these various versions of the
>> >> >requirements. It would be helpful to get clarity on at least two
>> >> > points:
>> >> >
>> >> >
>> >> >1) Is this request for _only_ new curves, as the subject line of your
>> >> >email indicates, or for new "ECC mechanisms" as in the included list
>> >> > from
>> >> >David McGrew? If it is the former, then curves which are incompatible
>> >> >with existing standardized and widely
>> >> > deployed algorithms, at least including ECDHE and ECDSA, must be
>> >> >excluded. If it is the latter, then this request goes far beyond some
>> >> >curves and I suggest deserves a lot more debate on how far down the
>> >> > new
>> >> >cryptography rabbit hole CFRG and the IETF wish to
>> >> > go.
>> >> >
>> >> >
>> >> >2) Is the process here to agree on clear, complete, unambiguous
>> >> >requirements against which candidate curves will be evaluated? I
>> >> > believe
>> >> >the answer is, or should be, yes. However, based on ambiguities in the
>> >> >stated requirements and the subsequent further
>> >> > blurring of those requirements on the mailing list, it seems that
>> >> > might
>> >> >not be the consensus view.
>> >> >
>> >> >
>> >> >
>> >> >
>> >> >Ben
>> >> >
>> >> >
>> >> >
>> >> >
>> >> >On Mon, Jul 14, 2014 at 12:49 PM, Paterson, Kenny
>> >> ><[email-masked]> wrote:
>> >> >
>> >> >Dear CFRG,
>> >> >
>> >> >CFRG has received a formal request from the TLS Working Group for
>> >> >recommendations for new elliptic curves. Specifically, the TLS WG
>> >> > would
>> >> >like CFRG to recommend:
>> >> >
>> >> >- Curves suitable for both key establishment and digital signature
>> >> >  (though the same curves need not be used for both purposes).
>> >> >
>> >> >- One proposed curve or set of curves at the following security
>> >> >  levels: 128-bit (~256-bit curve) and 256-bit (~512 bit curve).
>> >> >  192-bit security is optional.
>> >> >
>> >> >Note that these curves are not intended to supplant current curves in
>> >> >widespread use, but rather to supplement them. Full details of the
>> >> > request
>> >> >can be found in the e-mail from the TLS WG chairs below.
>> >> >
>> >> >The CFRG chairs will coordinate a response to this request from the
>> >> > CFRG
>> >> >readership. Ideally we will reach a rough consensus through discussion
>> >> > on
>> >> >the
>> >> >list and at the upcoming IETF 90 meeting in Toronto. While no deadline
>> >> > is
>> >> >set for our response to the TLS WG, we should aim to have one ready
>> >> > within
>> >> >2 months.
>> >> >
>> >> >We regard this as a major work item for CFRG and one where CFRG can
>> >> >provide real value to the TLS WG and the IETF more widely. So we
>> >> > encourage
>> >> >(and indeed request) active participation from the widest set of
>> >> >participants on this project.
>> >> >
>> >> >As a first step, we propose to discuss the requirements for new curves
>> >> > for
>> >> >a period of 2 weeks. Using an agreed set of requirements, in a second
>> >> >step, we will then evaluate different curve proposals (including
>> >> > extant
>> >> >proposals and any emerging ones) for a period of 4 weeks. In a final
>> >> >period of 2 weeks, we will produce a proposal for the TLS WG and seek
>> >> >consensus on it.
>> >> >
>> >> >
>> >> >The first step, running for 2 weeks, begins here.
>> >> >
>> >> >A starting point for requirements can be found in David McGrew's
>> >> > recent
>> >> >CFRG post
>> >> >(http://www.ietf.org/mail-archive/web/cfrg/current/msg04461.html) and
>> >> >reproduced here:
>> >> >
>> >> >----
>> >> >
>> >> >Simplicity
>> >> >
>> >> >   R1.  Desired: easy to understand and implement [1]
>> >> >
>> >> >Efficiency
>> >> >
>> >> >   R2.  Required: amenable to compact implementations and fast
>> >> >   implementations, across both small and large processors [1]
>> >> >
>> >> >   R3.  Desired: re-use components between signatures and key exchange
>> >> >   algorithms [3]
>> >> >
>> >> >Intellectual Property
>> >> >
>> >> >   R4.  Required: available worldwide under reasonable and well
>> >> >   understood licensing terms [1]
>> >> >
>> >> >   R5.  Desired: available worldwide under royalty-free licensing
>> >> >   terms [1]
>> >> >
>> >> >Interoperability
>> >> >
>> >> >   R6.  Desired: can be used with current software implementations
>> >> >   (using different curve parameters) of TLS, PKIX, SSH, and IKE [4]
>> >> >
>> >> >   R7.  Desired: can be used within current ECC standards of TLS,
>> >> >   PKIX, SSH, and IKE [4]
>> >> >
>> >> >Security
>> >> >
>> >> >   R8.  Required: amenable to constant-time implementations, to avoid
>> >> >   side channel attacks [2]
>> >> >
>> >> >   R9.  Required: resist twist attacks [2]
>> >> >
>> >> >   R10.  Required: curve parameters should have good provenance;
>> >> >   random curves should be provably pseudorandom [5]
>> >> >
>> >> >   R11.  Desired for key exchange: resist invalid curve attacks [2];
>> >> >   note that complete addition laws help and are thus desirable [2].
>> >> >   (Note that the use of ephemeral keys also resist such attacks.)
>> >> >
>> >> >   R12.  Required for PAKE: indistinguishability of curve points from
>> >> >   random strings [2]
>> >> >
>> >> >Footnotes:
>> >> >
>> >> >   [1] Original criteria set out for the Advanced Encryption Standard,
>> >> >       which is equally applicable to ECC.  National Institute of
>> >> >       Standards and Technology (NIST) of the United States, 1998.
>> >> >
>> >> >   [2] Daniel J. Bernstein and Tanja Lange. SafeCurves: choosing safe
>> >> >       curves for elliptic-curve cryptography.
>> >> >       http://safecurves.cr.yp.to <http://safecurves.cr.yp.to/>
>> >> ><http://safecurves.cr.yp.to/>, accessed
>> >> >April 2014.
>> >> >
>> >> >   [3] Criteria identified by David McGrew, 2014.
>> >> >
>> >> >   [4] Criteria identified by Russ Housley, TLS WG meeting at IETF89.
>> >> >
>> >> >   [5] Criteria widely acknowledged on CFRG email list during 2014.
>> >> >
>> >> >----
>> >> >
>> >> >
>> >> >Our first request, then, is that you consider these requirements, and
>> >> >provide your views on their appropriateness, completeness, and
>> >> > individual
>> >> >classifications (required/desired). We will continue that discussion
>> >> > for
>> >> > 2
>> >> >weeks, until the end of the IETF meeting in Toronto. The chairs will
>> >> > then
>> >> >compile a consensus-based list of requirements of the above form,
>> >> > after
>> >> >which we will move to the second step.
>> >> >
>> >> >We thank you in advance for your participation in this important task.
>> >> >
>> >> >Regards
>> >> >
>> >> >Alexei, Kenny and Kevin (CFRG co-chairs)
>> >> >
>> >> >
>> >> >
>> >> >
>> >> >On 11/07/2014 05:44, "Joseph Salowey (jsalowey)" <[email-masked]>
>> >> >wrote:
>> >> >
>> >> >>CFRG Chairs and Security ADs,
>> >> >>
>> >> >>TLS WG would like to formally request that the
>> >> >>CFRG make a recommendation for new ECC group support for TLS
>> >> >>and other similar applications. Specifically, we request that CFRG
>> >> >>recommend the following:
>> >> >>
>> >> >>- Curves suitable for both key establishment and digital signature
>> >> >>  (though the same curves need not be used for both purposes).
>> >> >>
>> >> >>- One proposed curve or set of curves at the following security
>> >> >>  levels: 128-bit (~256-bit curvee) and 256-bit (~512 bit curve).
>> >> >>  192-bit security is optional.
>> >> >>
>> >> >>If the same curves are used for key establishment and signature, this
>> >> >>would be a recommendation for two curves.  If different curves are
>> >> >>used, this would be a recommendation for four curves.
>> >> >>
>> >> >>In addition to a recommendation, we also request that the CFRG
>> >> >> provide
>> >> >>a technical rationale for their selection.
>> >> >>
>> >> >>If the CFRG does not feel comfortable making a single set of
>> >> >>selections, we propose that they select a small number of potential
>> >> >>choices with a detailed technical analysis of the advantages and
>> >> >>disadvantages of each selection and that the Security ADs sponsor a
>> >> >>process (perhaps via SAAG) to narrow it down to the specification
>> >> >>above.
>> >> >>
>> >> >>For clarity, we are not currently requesting that CFRG replace or
>> >> >>profile the existing curves in RFC4492 and RFC 7027, although we are
>> >> >>also not ruling out such an effort in the future. The current request
>> >> >>is for a new set of curves to complement the existing ones.
>> >> >>
>> >> >>Please reach out to us if this is unclear or further information is
>> >> >>required.
>> >> >>
>> >> >>Thanks,
>> >> >>
>> >> >>TLS Chairs
>> >> >>
>> >> >>
>> >> >
>> >> >
>> >> >
>> >> >_______________________________________________
>> >> >Cfrg mailing list
>> >> >[email-masked]
>> >> >http://www.irtf.org/mailman/listinfo/cfrg
>> >> >
>> >> >
>> >> >
>> >> >
>> >> >
>> >>
>> >
>> >
>> > _______________________________________________
>> > 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
>
>

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

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 21 Jul 2014 10:47:09 -0400

> TLS 1.2 offered no compelling advantages.

Yes.  TLS 1.3 will offer some good reasons to adopt, from the simplicity, security, privacy, and efficiency areas.  The comparison to TLS 1.2 doesn't hold.

	/r$

--  
Principal Security Engineer
Akamai Technologies, Cambridge, MA
IM: [email-masked]; Twitter: RichSalz

---

From: Benjamin Black <[email-masked]>
Date: Mon, 21 Jul 2014 08:56:49 -0700

On Mon, Jul 21, 2014 at 7:47 AM, Salz, Rich <[email-masked]> wrote:

> Yes.  TLS 1.3 will offer some good reasons to adopt, from the simplicity,
> security, privacy, and efficiency areas.  The comparison to TLS 1.2 doesn't
> hold.
>
>
We are all speculating here, but I don't see how TLS 1.3 will be different
from every other new protocol/version. These things take years, even if
there are some large early adopters.

Ben