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

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 14 Jul 2014 19:49:41 +0000

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
>
>

---

From: Watson Ladd <[email-masked]>
Date: Mon, 14 Jul 2014 18:11:52 -0700

>   192-bit security is optional.

I would like these to be taken as minimums. There is no reason
Curve4417 should not be used for 192 bit security
or Goldilocks448 if performance is acceptable.

I am not sure that 512 bits is needed: the NSA only uses P-384 for Top
Secret data. Perhaps this is an area where the
TLS WG can do some more thinking about what they want to see.

> period of 2 weeks, we will produce a proposal for the TLS WG and seek

What should a proposal look like? A family of similar curves, one for
each length?
How much implementation should be done? Making very fast
implementations can require a lot of coding,
but I think we know about how fast prime shapes will be, and curve
shape+prime shape gives you
everything but the TLC factor.

>    R3.  Desired: re-use components between signatures and key exchange

How about code size for R3 to make it more amenable to argument?

>    R5.  Desired: available worldwide under royalty-free licensing

I would make R5 a requirement. Royalties are a nonstarter for many users.

>    R7.  Desired: can be used within current ECC standards of TLS,

These desiderata are worthwhile, but implementors have signalled they
are willing to make
large changes for performance.

>    R9.  Required: resist twist attacks [2]

I don't like R9: twist attacks are only an issue with algorithms that
work on the compressed form. It just feels different.
Perhaps the requirement should be that implementations that miss
checks avoid being completely insecure.
>    (Note that the use of ephemeral keys also resist such attacks.)

I feel this should be folded into an edited R9.
>    R12.  Required for PAKE: indistinguishability of curve points from

Mike Hamburg will know better than I, but my vague recollection is
that Elligator 2 worked for everything.
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 14 Jul 2014 18:47:10 -0700

> TLS WG can do some more thinking about what they want to see.

I agree, but I’m biased since Ed448-Goldilocks is my proposal.

> checks avoid being completely insecure.

I agree.  That said, I expect every proposal except Brainpool to have the obvious
interpretation of this property: that the twist’s order is not smooth.

> I feel this should be folded into an edited R9.

In general invalid curve attacks are a property of an implementation, not a curve.
But complete addition laws should probably be on the list as nice-to-have.

> that Elligator 2 worked for everything.

“Elligator squared” works for everything.  Elligator 2 works (in DJB’s proposed PAKE)
for every prime-field curve of even order.

Also, this isn’t required for every PAKE, just for EKE.  The alternatives SPAKE2 and
JPAKE don’t need this.  SPEKE, SPAKE2EE and Dragonfly want an encoding, but
it just has to map to the curve and doesn’t have to be uniform.  This means that
SWU will suffice if Elligator 2 isn’t available (i.e. they work on most or all curves).

I propose that R12 should be nixed.  And I’m not biased in this direction, since I’m an
author on the Elligator paper, and my proposal has this indistinguishability property.

Cheers,
— Mike Hamburg

---

From: Ben Laurie <[email-masked]>
Date: Tue, 15 Jul 2014 10:16:27 +0100

> for every prime-field curve of even order.

What is DJB's proposed PAKE?

---

From: Johannes Merkle <[email-masked]>
Date: Tue, 15 Jul 2014 11:51:41 +0200

> large changes for performance.

Well, I'm not so sure. On the TLS mailing list, there have been some messages expressing the opposite opinion.
https://www.ietf.org/mail-archive/web/tls/current/msg12960.html
http://www.ietf.org/mail-archive/web/tls/current/msg12975.html
https://www.ietf.org/mail-archive/web/tls/current/msg12320.html
http://www.ietf.org/mail-archive/web/tls/current/msg12983.html

Actually, you have responded to most of these, but this does not necessarily eliminate the objections.

> work on the compressed form. It just feels different.

I absolutely agree. My impression is that this requirement is based on a misconception.

> checks avoid being completely insecure.
This would be a requirement on the implementation not on the curve. I think this is out-of-scope.

> I feel this should be folded into an edited R9.

Agreed, this is a requirement on the implementation not on the curve. Even curves with twist security are susceptible to
invalid curve attacks if the implementation does not use an x-coordinate ladder.

-- 
Johannes

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Jul 2014 07:39:54 -0700

> Actually, you have responded to most of these, but this does not necessarily eliminate the objections.

Since we aren't replacing the NIST curves its fine if some, even a lot
of, people don't want to use them. Not everyone uses
Camelia or AES after all.

By contrast, the interest in Curve25519 comes from the speed: no one
wants or uses Brainpool because it is slow.
(The fact that we already have a set of alternative curves with
nothing to recommend them beyond alternative generation is frequently
forgotten in these arguments). If we sacrifice speed in favor of
Weierstrass form, I'm not going to be very happy:

1: We asked about using something very fast
2: There were no security objections
3: The IETF happened
4: We got something slow, out of deference to people who won't use it anyway.

Now, for GLV curves there may be patent issues, and for
hyper-and-elliptic (use hyperelliptic curves for variable base,
elliptic curves for fixed base with deep cleverness to interconvert)
the complexity might not be worth the added speed. It's not that
simplicity isn't important, but that the range of performance vs.
complexity tradeoffs tends to strongly favor speed in this domain.

(One interesting counterexample is Bitcoin: the CM is not used despite
the curve being designed for it)

Sincerely,
Watson Ladd

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 15 Jul 2014 11:13:24 -0700

> What is DJB's proposed PAKE?

It’s an EKE variant.  You keep generating ephemeral keys until you find one which encodes with Elligator (pr ~ 1/2), then encrypt the encoding with the password using a wide-block ideal cipher.  The other party does the same.  Since the encoding looks like a random string, the attacker can’t check a guess for the password.

With Elligator this doesn’t work for every protocol, because Elligator only encodes half the points on the curve, so you have to rejection sample.  For contrast, Tibouchi’s “Elligator squared” [1] — though it’s really a rework of earlier papers, eg [2] on which Tibouchi is also an author — works on every elliptic curve.  It takes twice the space (can be compressed slightly though) and more time to encode, but since you don’t have to rejection sample it can be faster overall.  As a result, even if you like EKE, you can do it on any curve — you just need an ideal block cipher with a sufficiently wide block size.

Cheers,
— Mike

[1] http://eprint.iacr.org/2014/043
[2] https://eprint.iacr.org/2009/340

---

From: "Joseph Salowey (jsalowey)" <[email-masked]>
Date: Wed, 16 Jul 2014 15:35:59 +0000

> TLS WG can do some more thinking about what they want to see.

[Joe] We've received a few comments about this offline so I want to clarify on desired strengths. TLS supports 256-bit symmetric key ciphers and we want to have recommended curves to match this key strength.  We leave it up to the CFRG to determine what ECC key strengths are appropriate above 128-bit symmetric key strength.  It is also not necessary that the recommendation for higher strength curves be delivered at the same time, it would be OK to deliver a recommendation for the 128-bit curves before the higher strength curves.

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 16 Jul 2014 08:48:25 -0700

> [Joe] We've received a few comments about this offline so I want to clarify on desired strengths. TLS supports 256-bit symmetric key ciphers and we want to have recommended curves to match this key…

IIRC there's a reasonable argument for using 256-bit symmetric ciphers
with lower-strength curves.  There are brute-force attacks that can
break a small, random fraction of many 128-bit symmetric keys much
more quickly than any specific key could be broken, but I haven't
heard of similar attacks against ECDH.

--Andy

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 16 Jul 2014 23:39:41 +0200

I'm reviewing the selection criteria.  Some of the requirements are
rather fine-grained and poorly justified, and appear to limit the search
space.  If taken literally, I believe they exclude some good candidates
and steer the selection into a rather small field of available options.

I'm fine with R1-R3.

>    R5.  Desired: available worldwide under royalty-free licensing

I believe non-royalty-free licensing terms is a nonstarter.  I suggest
collapsing this into:

R4'. Required: available for worldwide implementation (by both
     proprietary and free open source software) and use under well
     understood and royalty-free licensing terms

>    R7.  Desired: can be used within current ECC standards of TLS,

I do not see why these are desirable properties, so I disagree they
should be a selection criteria.  These properties restricts the search
space.  I would prefer if the CFRG are at liberty to recommend the best
alternative even if it is clearly not re-usable in existing software or
standards.  I would go even further saying that one of the reasons for
doing this excercise is that the existing software and standards are not
sufficient.

On the topic of interoperability, I would propose to add the following,
to me, more important property:

Rx. Desired: either a clear algorithm description exists (with clarity
on byte-ordering etc) or multiple interoperable implementations are
available.

If some alternative does not appear to be sufficiently specified or
widely implemented, the CFRG could take on driving a document to clarify
the solution.

>    (Note that the use of ephemeral keys also resist such attacks.)

Instead of R8-R11, I suggest to summarize this more generally as:

R8'. Required: the solution should be secure against reasonable and
well-understood threats, including (but not limited to and necessarily
not all of) brute-force, side-channel, invalid-curve, twist attacks, or
maliciously chosen curve parameters.

Designing against security threats is a balance, and I would say that
there are no perfect solutions.  Every solution will have some area
where they perform less well compared to some other solution.  I believe
the overall choice(s) should reflect well-balanced alternatives with
strong advantages and some understood disadvantages.

>    R12.  Required for PAKE: indistinguishability of curve points from

I do not see why this is a desirable property for TLS, or other IETF
areas, so I disagree it should be a requirement.

/Simon

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 16 Jul 2014 15:30:15 -0700 (PDT)

> areas, so I disagree it should be a requirement.

  WIthout rehashing a TLS thread, not all sockets in the world connect
to port 443 and TLS is not synonymous with HTTPS. There are valid
uses of a PAKE with TLS, they just aren't browser-based.

  In addition, the numerous IETF documents that misuse PSKs
(MSCHAPv*, IKEv*, numerous TLS-PSK ciphersuites, EAP-PSK, etc)
would seem to suggest that we should have a nice way to use them
correctly.

  I support requirement R12.

  regards,

  Dan.

---

From: Benjamin Black <[email-masked]>
Date: Thu, 17 Jul 2014 22:51:29 -0700

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]

---

From: Benjamin Black <[email-masked]>
Date: Thu, 17 Jul 2014 22:51:54 -0700

"If taken literally, I believe they exclude some good candidates and steer
the selection into a rather small field of available options."

I suggest this is the nature of this process and is indicative of objective
and thorough engineering. It is often the case that the requirements
exclude all available candidate solutions, necessitating new development.
That is actually how this process started in the first place: new
requirements emerged and excluded the existing curves. Exclusion is a
feature, not a bug.

The alternative, which it seems you are suggesting, is to adjust the
requirements based not on the problem we are trying to solve but on
immediately available options that would be excluded if the requirements
were complete and adhered to in the process. In my experience that
inevitably leads to poor outcomes. In particular, in this instance we are
talking about setting a precedent for IETF adopting cryptography which has
not been standardized by any other body. We must not cut any corners on
what will be Internet cryptography for at least the next 15 years.

"I would prefer if the CFRG are at liberty to recommend the
best alternative even if it is clearly not re-usable in existing software or
standards."

See my response to Kenny a few minutes ago: the request was explicitly for
new curves, nothing more. Expanding the scope to include new algorithms
implies enormously more work on requirements, specification, and
deployment. For example, a curve which was incompatible with ECDSA would
require a new signature algorithm, which in turn would require new cipher
suites, new certificates issued by CAs from new hardware and software
platforms yet to be developed, and so on. That list doesn't even touch on
all the challenges it presents for customers of these technologies.

I share the desire to push towards more modern cryptography in IETF
specifications, but that desire is tempered by an acute awareness of the
cascade of expensive and high risk change that comes along with changing
too much too quickly. I recommend we adhere to both the letter and the
spirit of the subject line in Kenny's initial email and focus only on new
curves which are compatible with existing algorithms and protocols.

Ben

---

From: Benjamin Black <[email-masked]>
Date: Thu, 17 Jul 2014 23:03:06 -0700

"TLS supports 256-bit symmetric key ciphers and we want to have recommended
curves to match this key strength.  We leave it up to the CFRG to determine
what ECC key strengths are appropriate above 128-bit symmetric key
strength."

Can you clarify why this is the case? TLS already has suites with 256-bit
symmetric ciphers and they are paired with 192-bit security level
components, including curves [1]. I can see arguments in favor of either
192 or 256, but I don't see how this is now a CFRG decision.

"It is also not necessary that the recommendation for higher strength
curves be delivered at the same time, it would be OK to deliver a
recommendation for the 128-bit curves before the higher strength curves."

Can you clarify why this is the case? I'm not aware of any other
standardization effort that has done this and see no reason for it.

Ben

[1] RFC5289

On Wed, Jul 16, 2014 at 8:35 AM, Joseph Salowey (jsalowey) <
[email-masked]> wrote:

> [Joe] We've received a few comments about this offline so I want to
> clarify on desired strengths. TLS supports 256-bit symmetric key ciphers
> and we want to have recommended curves to match this key strength.  We
> leave it up to the CFRG to determine what ECC key strengths are appropriate
> above 128-bit symmetric key strength.  It is also not necessary that the
> recommendation for higher strength curves be delivered at the same time, it
> would be OK to deliver a recommendation for the 128-bit curves before the
> higher strength curves.
>
> >>

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Fri, 18 Jul 2014 14:21:16 +0000

I can say a few words about the AES-256/P-384 security disparity, since it is largely
the fault of Suite B.  Suite B had wanted to use AES-192/P-384, but a survey of
available hardware implementations showed that many has skipped over AES-192
and gone to AES-256.  Hence AES-256 was put into Suite B rather than the preferred
AES-192.  But since 192-bits of security was the intended security goal, we kept P-384.

From: Cfrg [mailto:[email-masked]] On Behalf Of Benjamin Black
Sent: Friday, July 18, 2014 2:03 AM
To: Joseph Salowey (jsalowey)
Cc: [email-masked]
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

"TLS supports 256-bit symmetric key ciphers and we want to have recommended curves to match this key strength.  We leave it up to the CFRG to determine what ECC key strengths are appropriate above 128-bit symmetric key strength."

Can you clarify why this is the case? TLS already has suites with 256-bit symmetric ciphers and they are paired with 192-bit security level components, including curves [1]. I can see arguments in favor of either 192 or 256, but I don't see how this is now a CFRG decision.

"It is also not necessary that the recommendation for higher strength curves be delivered at the same time, it would be OK to deliver a recommendation for the 128-bit curves before the higher strength curves."

Can you clarify why this is the case? I'm not aware of any other standardization effort that has done this and see no reason for it.

Ben

[1] RFC5289

On Wed, Jul 16, 2014 at 8:35 AM, Joseph Salowey (jsalowey) <[email-masked]<mailto:[email-masked]>> wrote:

On Jul 14, 2014, at 6:11 PM, Watson Ladd <[email-masked]<mailto:[email-masked]>> wrote:
> On Jul 14, 2014 12:49 PM, "Paterson, Kenny" <[email-masked]<mailto:[email-masked]>> wrote:
>>
>> Dear CFRG,
>>

>> On 11/07/2014 05:44, "Joseph Salowey (jsalowey)" <[email-masked]<mailto:[email-masked]>>
>> wrote:
>>
>> [email-masked]<mailto:[email-masked]>
> [email-masked]<mailto:[email-masked]>

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

---

From: "Joseph Salowey (jsalowey)" <[email-masked]>
Date: Fri, 18 Jul 2014 20:59:11 +0000

On Jul 17, 2014, at 11:03 PM, Benjamin Black <[email-masked]<mailto:[email-masked]>> wrote:

[Joe]  The CFRG has the cryptographic expertise to determine what pairings are appropriate.

[Joe]  As a practical matter 128-bith strength ciphers are sufficient for most current deployments.  From what I understand there are currently curves families under consideration which do not currently the higher strength key size defined.  If the CFRG determines these curves have significant enough advantages it could make this recommendation while the details of the higher strength curves are being worked out.  However, the CFRG is not obliged to wait.

Ben

[1] RFC5289

>>       http://safecurves.cr.yp.to<http://safecurves.cr.yp.to/> <http://safecurves.cr.yp.to/>

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 18 Jul 2014 22:29:29 +0000

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:

>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.
>
>
>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,
>

---

From: Benjamin Black <[email-masked]>
Date: Sat, 19 Jul 2014 15:42:36 -0700

"The CFRG has the cryptographic expertise to determine what pairings are
appropriate."

As do a number of others, including other leaders of the TLS working group.
I refer you again to RFC5289 and again request an explanation for this
contradicting of all prior practice in the TLS working group.

"As a practical matter 128-bith strength ciphers are sufficient for most
current deployments."

For higher security requirements, as a practical matter for most
deployments, 256-bit symmetric ciphers are combined with 192-bit strength
curves. I would also suggest you are making an incorrect assumption in
saying 128-bit is sufficient. I think you'll find some very large online
services defaulting to 256-bit ciphers. So, based on your own metric of
current deployment, with which I agree, the required curve strengths are
128 and 192. If you wish to apply a different metric, and especially if you
wish to apply different metrics for the different strengths, then I'd ask
that you bring something rather stronger to the table as justification.

"From what I understand there are currently curves families under
consideration which do not currently the higher strength key size defined."

This is irrelevant! We are talking about requirements for TLS, not
immediately available curves we could adopt if we squint a bit and ignore
the enormous overhead inherent in migrating to them. If they don't have the
higher strength defined, they are not viable candidates. That's how this
process works. If you instead insist on wrapping the requirements around
the curves then I am unclear on the point of this exercise, at least on an
engineering level.

"If the CFRG determines these curves have significant enough advantages it
could make this recommendation while the details of the higher strength
curves are being worked out.  However, the CFRG is not obliged to wait."

Once again, this is absolutely contrary to all prior work in TLS and almost
all work across IETF. It implies that every single curve at every strength
will need at least one new draft and possibly more since there is
discussion of allowing new signature schemes for no apparent reason. What
is the rush that requires this highly unusual direction?

Ben

On Fri, Jul 18, 2014 at 1:59 PM, Joseph Salowey (jsalowey) <
[email-masked]> wrote:

>
>  On Jul 17, 2014, at 11:03 PM, Benjamin Black <[email-masked]> wrote:
>
>  "TLS supports 256-bit symmetric key ciphers and we want to have
> recommended curves to match this key strength.  We leave it up to the CFRG
> to determine what ECC key strengths are appropriate above 128-bit symmetric
> key strength."
>
>  Can you clarify why this is the case? TLS already has suites with
> 256-bit symmetric ciphers and they are paired with 192-bit security level
>  [Joe]  As a practical matter 128-bith strength ciphers are sufficient
> for most current deployments.  From what I understand there are currently
> curves families under consideration which do not currently the higher
> strength key size defined.  If the CFRG determines these curves have
> significant enough advantages it could make this recommendation while the
> details of the higher strength curves are being worked out.  However, the
> CFRG is not obliged to wait.
>
>
>  Ben
>
>  [1] RFC5289
>
>

---

From: Benjamin Black <[email-masked]>
Date: Sat, 19 Jul 2014 16:09:42 -0700

"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.

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 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.

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.

Ben

---

From: Watson Ladd <[email-masked]>
Date: Sat, 19 Jul 2014 21:50:17 -0700

> 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.

> 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
> appropriate, pointers to algorithms for those curves."
>

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.

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

>
> 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 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.

> 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?

Sincerely,
Watson Ladd

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

---

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

Ben

On 19/07/2014 18:42, "Benjamin Black" <[email-masked]> wrote:

>As do a number of others, including other leaders of the TLS working
>group. I refer you again to RFC5289 and again request an explanation for
>this contradicting of all prior practice in the
> TLS working group.

I'm not sure of the relevance of RFC 5289 here. It does not define any new
curves or fundamentally different algorithms using curves, but instead
simply formalises the use of stronger hash functions for HMAC in existing
combinations such as ECDHE_ECDSA and ECDH_ECDSA. I see that as having been
a necessary bit of tidying-up in the face of realistic concerns about the
long-term security of HMAC-MD5.

As far as I know, the TLS WG is free to ask for advice from any body or
group. It is also free to ignore whatever advice it gets - including from
CFRG. And, in reality, the cryptographic expertise in the TLS WG to which
you refer is also active in CFRG.

Cheers

Kenny

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 20 Jul 2014 14:38:19 +0200

On 20/07/2014 06:50, Watson Ladd wrote:
>> [...] Please provide specific
It is rather unfortunate that http://bench.cr.yp.to/impl-dh/nistp256.png returns
a 404 error.

Manuel.

---

From: Tanja Lange <[email-masked]>
Date: Sun, 20 Jul 2014 18:16:40 +0200

> It is rather unfortunate that http://bench.cr.yp.to/impl-dh/nistp256.png returns
That implementation only supports sparc and we currently have no 
modern sparc (donations welcome!).

Nobody submitted decent DH implementations of the NIST curves, 
take a look at the signatures page instead
	http://bench.cr.yp.to/impl-sign/ecdonaldp256.html
that implementation wraps OpenSSL's implementation.

	Tanja

---

From: David McGrew <[email-masked]>
Date: Mon, 21 Jul 2014 07:45:51 -0400

Hi Simon,

On Jul 16, 2014, at 5:39 PM, Simon Josefsson <[email-masked]> wrote:

> should be a selection criteria.  

These properties are valuable because 1) they lower the cost of adopting the new curves, thus making adoption faster or more likely, 2) they simplify (at least some) implementations by allowing them to avoid implementing an additional ECC scheme and a protocol interface for it.    Many people do see these requirements as important; this was Russ Housley’s point at the mic at the last TLS WG, and I agree with him.   Simplicity of design and implementation is a really important point that we need to not lose sight of.   Less code, fewer bugs.

I concede that these properties do limit the design space, which is why they should be “desired” rather than required.    In my opinion, anyway.

What is most important is that people understand which criteria are met by a given ECC scheme, so that they understand what they are actually getting. 

> These properties restricts the search

I agree that this is a good criteria, though I will note that multiple interoperable implementations are no substitute for a clear algorithm description.  

> Instead of R8-R11, I suggest to summarize this more generally

I disagree.   These requirements should be kept separate because they allow us to differentiate between different proposed ECC schemes.

> as:

Yeah, I take your point.   In the context of TLS, perhaps this should be worded as “desired: indistinguishability of curve points from random strings, so that the curves could also be used in PAKE protocols”.    This would allow for implementation and specification re-use for PAKE, which could make a PAKE easier to adopt.  

David

---

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:
>>
> 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.
>> > has
> 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.

> 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.
>
>>
>> >
>> > means
> 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?

> 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

>> >> >classifications (required/desired). We will continue that discussion
>> >> > for
>> >> > 2

---

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: Joachim Strömbergson <[email-masked]>
Date: Mon, 21 Jul 2014 17:39:14 +0200

Aloha!

Simon Josefsson wrote:
> I believe non-royalty-free licensing terms is a nonstarter.  I
> suggest collapsing this into:
> 

Please generalize to free, open source. Period.

If someone (like me for example) would like to develop en open source HW
implementation, the "software" distinction really is a hindrance that I
think stems from ignorance that there are open HW implementations too.

(This software only designation is unfortunately pretty common in open
licenses for algorithms.)

- -- 
Med vänlig hälsning, Yours

Joachim Strömbergson - Alltid i harmonisk svängning.
========================================================================

---

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