Subject: Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry

From: Patrick Pelletier <[email-masked]>
Date: Sun, 08 Sep 2013 18:34:49 -0700

Given the doubt that's recently been cast on the NIST curves, is it time 
to revive the idea of adding curve25519 as a named curve?

--Patrick

On 3/1/10 4:20 PM, Adam Langley wrote:
> We would like to start testing EC DHE in order to give our users
> forward-secrecy.
>
> In order to do this cheaply, one of the curves that we would like to
> test with is curve25519[1]. There are several implementations of it
> [2][3][4] and it's 3-4x faster than NIST's p256 (as implemented in
> OpenSSL), while being constant-time.
>
> Curve25519 doesn't currently appear on IANA's list of named curves[5]
> and we would like to see it included.
>
> As a first step I'd like to ask if there are any objections?
>
>
> Cheers
>
> AGL
>
>
> [1] http://cr.yp.to/ecdh/curve25519-20060209.pdf
> [2] http://cr.yp.to/ecdh.html
> [3] http://code.google.com/p/curve25519-donna/
> [4] http://bench.cr.yp.to/results-dh.html
> [5] http://www.iana.org/assignments/tls-parameters/
>

---

From: Douglas Stebila <[email-masked]>
Date: Mon, 9 Sep 2013 21:12:19 +1000

Recent news has highlighted doubts on a particular elliptic curve-based pseudorandom number generation algorithm, Dual_EC_DRBG, in which a particular point is used for which no explanation is given on how the point was generated. If it was generated so that its discrete logarithm is known with respect to another point, then a backdoor exists that can recover the seed.  (http://rump2007.cr.yp.to/15-shumow.pdf)

The NIST-standardized elliptic curves p256/p384/p512 are not related to this particular issue. 
- The prime p for each field has a special form chosen for efficiency (http://cacr.uwaterloo.ca/techreports/1999/corr99-39.pdf), not entirely unlike how the prime 2^155-19 was chosen for efficiency in curve25519.  There are no results that suggest that one prime is weaker than another prime for elliptic curve cryptography.
- The curve parameters were generated "verifiably at random", meaning a seed was chosen, and then the curve parameters a and b were generated by hashing the seed a pre-determined number of times using SHA-1.  (Appendix 4 ofhttp://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, or Section 3.1.3.1 of SEC1 http://secg.org, or ANSI X9.62)  
- I don't think it's specified how the generator was chosen, but the Diffie-Hellman problem is self-reducible, so there are no weak generators.

There are other reasons to support curve25519, including efficiency and resistance to side-channel attacks because constant-time implementations.  But not because of concerns over backdoors in p256/p384/p512.

Douglas

On 2013-09-09, at 11:34 AM, Patrick Pelletier <[email-masked]> wrote:

> Given the doubt that's recently been cast on the NIST curves, is it time to revive the idea of adding curve25519 as a named curve?
> 
> --Patrick
> 
>

---

From: Douglas Stebila <[email-masked]>
Date: Mon, 9 Sep 2013 21:08:15 +1000

The NIST-standardized elliptic curves p256/p384/p512 are not related to this particular issue. 
- The prime p for each field has a special form chosen for efficiency (http://cacr.uwaterloo.ca/techreports/1999/corr99-39.pdf), not entirely unlike how the prime 2^155-19 was chosen for efficiency in curve25519.  There are no results that suggest that one prime is weaker than another prime for elliptic curve cryptography.
- The curve parameters were generated "verifiably at random", meaning a seed was chosen, and then the curve parameters a and b were generated by hashing the seed a pre-determined number of times using SHA-1.  (Appendix 4 of http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, or Section 3.1.3.1 of SEC1 http://secg.org, or ANSI X9.62)  
- I don't think it's specified how the generator was chosen, but the Diffie-Hellman problem is self-reducible, so there are no weak generators.

Douglas

On 2013-09-09, at 11:34 AM, Patrick Pelletier <[email-masked]> wrote:

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Nick Mathewson <[email-masked]>
Date: Mon, 9 Sep 2013 12:18:46 -0400

On Mon, Sep 9, 2013 at 7:12 AM, Douglas Stebila <[email-masked]> wrote:
 [...]
> - The curve parameters were generated "verifiably at random", meaning a seed was chosen, and then the curve parameters a and b were generated by hashing the seed a pre-determined number of times us…

A possibly foolish question, but I couldn't find the answer in any of
the documents you listed:

Is it documented how the seeds were chosen?

(In either case, +1 on trying to making curve25519 named. In the FOSS
cryptography world nowadays, I see many more new users of curve25519
than of the NIST curves, because of efficiency and
ease-of-implementation issues.)

yrs,
-- 
Nick Mathewson

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 09 Sep 2013 22:08:54 +0200

Douglas Stebila <[email-masked]> writes:

> There are other reasons to support curve25519, including efficiency
> and resistance to side-channel attacks because constant-time
> implementations.

I agree.  To be able to move forward with standardization of the idea,
an Internet Draft may help.  I have create one:

http://www.ietf.org/id/draft-josefsson-tls-curve25519-00.txt

Feedback most welcome!

/Simon

---

From: Nico Williams <[email-masked]>
Date: Mon, 9 Sep 2013 14:31:15 -0500

Agreed, we need curve25519 cipher suites because of its technical
advantages, not due to any FUD about the other ECDH curves that we have.

Nico
--

---

From: Douglas Stebila <[email-masked]>
Date: Tue, 10 Sep 2013 09:40:34 +1000

> Is it documented how the seeds were chosen?

I haven't found any information on how the seeds were chosen.  The earliest reference I have listing the seeds is a September 1998 draft of ANSI X9.62, a copy of which is available here: https://github.com/ANSSI-FR/parsifal/blob/master/docs/tls/X9-62-1998--ECDSA.pdf, but this provides no reason for the choice of seeds.  Maybe there's someone from X9F on this mailing list who has some historical insight?

Douglas

---

From: Dan Brown <[email-masked]>
Date: Tue, 10 Sep 2013 01:22:41 +0000

I'm the current editor of ANSI X9.62 and X9.63, but joined X9F1 a little later than the‎ time in question, so am not the best historical source.

‎Anyway, I had thought the 15 NIST curves were included in ANSI X9.63 in 2001, but most were not in X9.62 in its first 1998 version, and only added in the 2005 version.

The curve seed sources were not documented in ANSI or NIST docs. I've wondered about it a few times, but could never see a concrete problem. At least intuitively, it would only be a problem if:

1) a large fraction of elliptic curves were weak, or

2) sha1 preimages are easy to find and some unknown but rare class of elliptic curves are weak.

‎Both of these would undermine more than just the curve choice, and seem extremely unlikely.

An alternative would have been to select the seeds in a canonical way, eg as the smallest integer above some math constant causing the curve generated via the hash to be good. In this case, the curve could be said to be pseudorandom‎, but not random.

I welcome any points or info I've missed, and will gladly forward to the rest of X9F1.

...

The generators for the NIST curves are not verifiably random, but X9.62-2005 added a method to generate them that way, for new curves or algorithms (eg X9.92 uses this method).

ECDSA does not share the random self-reducibility property with ECDH‎, hence the check that r is not zero (and vr gens for new curves to supplement the r check ).

...

The ECRNG standards in question do have options for users to select verifiably random constants, which removes any doubts, unless sha512 is weak.

Given the importance of key generation, some might consider the cost of using an ECRNG. Others just need keys faster. Hence the options in standards, eg HMAC and AES based RNGs.

Sent from my BlackBerry 10 smartphone on the Rogers network.
From: Douglas Stebila
Sent: Monday, September 9, 2013 7:41 PM
To: Nick Mathewson
Cc: [email-masked]
Subject: Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry

Douglas

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Rob Stradling <[email-masked]>
Date: Tue, 10 Sep 2013 09:34:47 +0100

> http://www.ietf.org/id/draft-josefsson-tls-curve25519-00.txt

Simon, thanks for creating this draft.

draft-merkle-tls-brainpool-04 (on which you've based this new draft) says:
    "While the ASN.1 object identifiers
    defined in [RFC5639] already allow usage of the ECC Brainpool curves
    for TLS (client or server) authentication through reference in X.509
    certificates according to [RFC3279] and [RFC5480] , their negotiation
    for key exchange according to [RFC4492] requires the definition and
    assignment of additional NamedCurve IDs."

Your draft defines a NamedCurve ID for Curve25519, thereby enabling it 
to be used for key exchange.  But what about "(client or server) 
authentication through reference in X.509 certificates..."?

I'm not aware of an equivalent of RFC5639 for Curve25519.  Should we 
create one?  Or could we simply define some new ASN.1 Object Identifiers 
in your draft?

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Nick Mathewson <[email-masked]>
Date: Wed, 11 Sep 2013 11:10:24 -0400

On Mon, Sep 9, 2013 at 9:22 PM, Dan Brown <[email-masked]> wrote:
> I'm the current editor of ANSI X9.62 and X9.63, but joined X9F1 a little later than the time in question, so am not the best historical source.
>
> Anyway, I had thought the 15 NIST curves were included in ANSI X9.63 in 2001, but most were not in X9.62 in its first 1998 version, and only added in the 2005 version.
>
> Both of these would undermine more than just the curve choice, and seem extremely unlikely.

That's true, so long as "large fraction" and "rare" are defined
appropriately.  But I think what most of the people who worry about
this are worried about is something like:

3) A small-ish fraction of elliptic curves (say, one in every
quadrillion or quintillion or so) has some as-yet-unknown weakness,
and building a sha1 brute-forcing engine to find seeds that would
produce such curves was economically viable the late 1990s.

After a little time investigating SHA1 speeds on late-1990s FPGAs,
special-purpose chips, and general purpose CPUs, a
back-of-the-envelope calculation suggests that, given about ten
million dollars of hardware and about half a year's worth of
processing time, searching quintillions of seeds to find curves with
desired properties wouldn't have been unrealistic.

Now, none of this means that the seeds in question actually _were_
chosen in any hostile way, of course. But it would make it more
comforting if anybody could point out where the seeds actually came
from.

best wishes,
-- 
Nick Mathewson

---

From: Dan Brown <[email-masked]>
Date: Wed, 11 Sep 2013 17:12:05 +0000

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Nick Mathewson
> Sent: Wednesday, September 11, 2013 11:10 AM
> To: Dan Brown
> > The curve seed sources were not documented in ANSI or NIST docs. I've
> wondered about it a few times, but could never see a concrete problem.
> At least intuitively, it would only be a problem if:
> >
[DB]  Good point.  My colleague Randy Tsang mentioned a similar point to me
yesterday.  

Your situation (3) is what I meant by my (1).  By a "large fraction", I
meant one with an inverse representing a feasible number of steps.  I should
have clarified this, because there are many other reasonable meanings of
large fraction.  Sorry.  More importantly, I should clarify why I consider
this to undermine more than just the curve choice.

Firstly, if the hypothetical weakness was that the DLP was easy, then
installing such a backdoor would be unwise, because it would backfire once
somebody else discovers the weakness.  I do not see how the hypothetical
weakness could be a high-entropy trapdoor, unless SHA1 inversion was
possible.  (This would be analogous to my scenario #2.)  So, an open
backdoor would be feasible for somebody else to discover the weakness, only
being a matter of insight.

Secondly, if we take the view that an undiscovered classes of weak curves
might exist, say with density 2^(-30), and needing research work 2^(40) to
find, then we must reduce the claimed security level of any given curve, to
a level appropriate to these levels, 70 bits in this example.  Given that
many people would be likely to use the same curve, this level may not be
acceptable.  In other words, the hypothesis of your scenario 3 above, also
mildly jeopardizes other curves (but not to the same extent as a
maliciously-chosen curve, of course).  

In other words, a simplistic viewpoint is to define security levels against
best-known attacks, which excludes all the situations above.  A more
sophisticated type of security level attempts to anticipate
as-yet-undiscovered or as-yet-undisclosed attacks, and by tracking the rate
of discovery, inferring from evidence whether attacks are undisclosed, and
so on.  

Aside: it should be comforting that NIST also recommends "Koblitz" curves
which have no wiggle room, and hence no opportunity for a backdoor.  (Some
articles on efficient scalar multiplication of Koblitz curves are
informative here.)  Such curves are canonical, rather than verifiably
random.  I believe that Curve25519 is also canonical in a similar way in
that it relies on small curve coefficients.   One security argument against
canonical curves is that they are special and would be more likely belong to
some weak class (but see (*) below).  (Similar special class: curves of
order p defined over Fp are weak.)  For various reasons, many have
gravitated away from Koblitz curves.

Perhaps the ideal is a combination of verifiably random and canonical, which
I mentioned in my previous message.  Again: hash a small value, or otherwise
wiggle-free value, to obtain the curve of desirable order, etc.  This might
be worthwhile, though not tremendously worthwhile by the arguments above.

(*) On the other hand, special cases may also resist some attacks. For
example, Jao recently proposed using supersingular curves to avoid
subexponential-time isogenies.

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 11 Sep 2013 10:12:31 -0700

Rob Stradling <[email-masked]> writes:

> create one?  Or could we simply define some new ASN.1 Object
> Identifiers in your draft?

Yes perhaps.  What would the purpose of using Curve25519 in X.509
certificates be?  Performance is less critical there than for ECDH, but
if you or someone else has numbers indicating X.509 signature
verification being a performance bottle neck I would be convinced
otherwise.  There could be other reasons than performance though, but
they should be articulated and examined.

RFC 5639 contains a lot of things, is there anything other than the OID
and PKIX usage you think is relevant for Curve25519?

/Simon

---

From: Douglas Stebila <[email-masked]>
Date: Thu, 12 Sep 2013 09:32:57 +1000

On the topic of a smallish fraction of elliptic curves being weak, I asked Alfred Menezes, a prof at Waterloo who knows a lot about elliptic curves and was active in the development of ECC in the late 90s; he wrote this to me:

> The idea at the time was to rule out the possibility of someone choosing
> *very* special curves. For example, if one knows that elliptic curves
> of a certain order N over a certain prime field GF(p) are weak, then it
> would not be possible to find a seed which gave such a curve. It was felt 
> that if a significant proportion of elliptic curves (e.g. 1/10000000) over 
> a fixed field GF(p) or GF(2^m) (with m prime) which meet the standard 
> requirements (e.g. group order divisible by a large prime, sufficiently 
> large embedding degree, etc.) was found to be weak, then that would in 
> any case spell the end of ECC. Certainly if one has a weak curve then 
> one can produce a much larger family of weak curves by low-degree 
> isogeny walks.

This is quite similar to what Dan has said in his reply to your email, that existence of a non-negligibly sized class of weak curves would jeopardize other randomly selected curves.

I agree with you that it would be more comforting to know where the seeds came from.  Alfred told me he didn't know.  And I can't see any discernible pattern in the seeds (nothing obvious in ASCII; not in the first few million decimal digits of e or the first 200 million decimal digits of pi).  

But I also find convincing the argument that even one in 2^50 or 2^60 randomly selected curves being weak would cause major doubts about the security of random 256-bit curves.  There are at least distinct 2^256 elliptic curves over a 256-bit prime, and if even one in 2^60 was weak, then there would be roughly 2^200 weak elliptic curves over that prime.  

To me, this is saying that either you reject all randomly generated curves of (near) prime order over a prime field, or you believe there is no non-negligbly sized class of weak curves.  

Douglas

---

From: Kyle Hamilton <[email-masked]>
Date: Wed, 11 Sep 2013 17:03:57 -0700

Curve25519 is not suitable for authentication.  Ed25519 would be more
appropriate, I think.

-Kyle H

On Tue, Sep 10, 2013 at 1:34 AM, Rob Stradling <[email-masked]>wrote:

>> http://www.ietf.org/id/draft-**josefsson-tls-curve25519-00.**txt<http://www.ietf.org/id/draft-josefsson-tls-curve25519-00.txt>
>>
>> Feedback most welcome!
>>
>
> Your draft defines a NamedCurve ID for Curve25519, thereby enabling it to
> be used for key exchange.  But what about "(client or server)
> create one?  Or could we simply define some new ASN.1 Object Identifiers in
> your draft?
>
> --
> Rob Stradling
> ______________________________**_________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/tls<https://www.ietf.org/mailman/listinfo/tls>
>

---

From: Rob Stradling <[email-masked]>
Date: Thu, 12 Sep 2013 13:51:57 +0100

On 11/09/13 18:12, Simon Josefsson wrote:
> certificates be?

I just thought it seemed like a logical thing to do.  We can already do 
ECDHE-ECDSA using the NIST curves for both keys in certs and for key 
exchange, so why wouldn't we allow Curve25519 to be used for both purposes?

Unless NIST can prove that their curves aren't backdoored, I think it's 
likely that some folks (rightly or wrongly) will want to do ECDHE-ECDSA 
without touching the NIST curves at all.  What options do they have?

> Performance is less critical there than for ECDH, but

I don't have any performance figures, I'm afraid.

> and PKIX usage you think is relevant for Curve25519?

Pass.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 12 Sep 2013 13:58:28 +0000

On Sep 12, 2013, at 3:51 PM, Rob Stradling <[email-masked]> wrote:

> I just thought it seemed like a logical thing to do.  We can already do ECDHE-ECDSA using the NIST curves for both keys in certs and for key exchange, so why wouldn't we allow Curve25519 to be used for both purposes?
> 
> Unless NIST can prove that their curves aren't backdoored, I think it's likely that some folks (rightly or wrongly) will want to do ECDHE-ECDSA without touching the NIST curves at all.  What options do they have?

Umm, the brainpool curves are available.

Also, I don't get why performance would be less critical than that of ECDHE. In a full handshake, you do both an ECDSA signature and the ECDHE operations. Why would one matter while the other does not?

Yoav

---

From: Dan Brown <[email-masked]>
Date: Thu, 12 Sep 2013 14:44:09 +0000

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Rob Stradling
> Sent: Thursday, September 12, 2013 8:52 AM
> 

[DB] Five NIST curves are Koblitz curves, which are not backdoored.

> without touching the NIST curves at all.  What options do they have?

[DB] Koblitz curves.

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 12 Sep 2013 19:41:42 +0200

> [DB] Five NIST curves are Koblitz curves, which are not backdoored.

Personally I don't expect any of the NIST curves to be backdoored, but I
don't agree with the reasoning (which I've seen elsewhere before) that if
you have doubts about the pseudorandom NIST urves due to their unexplained
seeds, the NIST Koblitz curves are less suspect because that degree of
freedom is missing.

I won't repeat here why I'm not actually worried about the pseudorandom
curves (I don't think I could add anything to your and Douglas Stebila's
arguments in the thread "Testing consensus for adding curve25519 to the EC
named curve registry"). Now *if* one assumes that there's a (thin-spread
but non-negligible) class of weak curves among them (so that the seeds
could have been chosen to create backdoors), why would it be more
far-fetched to assume that the class of Koblitz curves is weak *in its
entirety*?  After all, these particular curves are known to have extra
structure by design!

Bodo

---

From: Dan Brown <[email-masked]>
Date: Thu, 12 Sep 2013 19:00:14 +0000

Hi Bodo,

Aside: maybe discussion like this should move to CFRG, because its
generality could affect other WGs, and its theoretical what-if nature may
not interest many in TLS WG.  For now, I just changed the subject line.

To briefly recap: some people hypothesize (a) existence of an undisclosed
weak curve classes and (b) authorities pushing curves, via seed searches,
into the weak class.  Koblitz curves resist (b).  You said you do not
believe (b).  You raised the point again that Koblitz curves may be hit by
(a) alone.  (I tried to raise this point (a) for Koblitz curves, in the
other thread, noting them to be special, just like Curve25519.) I have said
before Koblitz curves provide evidence against (b) else: Why place a
backdoor on one curve, but not another? My argument was a little vague on
this point, so I will try to clarify it first

You are quite right that if Koblitz fall to a different version of (a), then
(b) would remain viable backdoor mechanism for the VR curves, because now
all NIST curves would be weak.  This event essentially presumes two
undisclosed weak classes of curves (or one, which contains both the Koblitz
curves and the all VR curves).  In other words, it assumes a larger class of
weak curves, so it is more unlikely.  It is more far-fetched, albeit only
slightly so.  And everything here is hypothetical, remember. 

Ignoring (b) completely is another hypothesis worthy of consideration.  In
this case, a highly informal argument that Koblitz are less likely than VR
curves to be affected by (a) is that the Koblitz curves slightly pre-date
the VR curves, and by virtue of their simple coefficients, are more amenable
to inspirational analysis.  Put another way, the VR curve coefficients are
not easy for a person to manipulate.  So, any human research efforts could
have targeted Koblitz but not VR curves.  Also, research efforts just to
find arbitrary weak classes of curves could be viewed as unlikely of hitting
a VR curve, and thus be viewed as having less incentive (exception: strong
believers in (b) would be much more likely to believe in a weak class
containing the VR curves).  So, it seems, at least to me, the fact that
Koblitz have would have been subjected to more effort, or at least more
incentive. (Indeed, your intuition, which is that a weak class is more
likely to include Koblitz, is an instance of researchers seeing Koblitz
curves as more likely target to achieve research success.)  From the lack of
published attacks, we can infer a lower probability of an undisclosed
attack, because there may be a greater number of samples: attempts to
discover such a class.  But then again, the Suite B VR curves may also
received quite a bit of scrutiny too.

Best regards,

Dan

From: [email-masked] [mailto:[email-masked]] On Behalf Of Bodo
Moeller
Sent: Thursday, September 12, 2013 1:42 PM
To: [email-masked]
Subject: Re: [TLS] Curve25519 in TLS

I won't repeat here why I'm not actually worried about the pseudorandom
curves (I don't think I could add anything to your and Douglas Stebila's
arguments in the thread "Testing consensus for adding curve25519 to the EC
named curve registry"). Now *if* one assumes that there's a (thin-spread but
non-negligible) class of weak curves among them (so that the seeds could
have been chosen to create backdoors), why would it be more far-fetched to
assume that the class of Koblitz curves is weak *in its entirety*?  After
all, these particular curves are known to have extra structure by design!

Bodo

---

From: Rob Stradling <[email-masked]>
Date: Thu, 12 Sep 2013 20:04:25 +0100

>> On 11/09/13 18:12, Simon Josefsson wrote:
<snip>
> Umm, the brainpool curves are available.

Yes, and the brainpool curves are also available for key exchange.

So why bother making curve25519 available for key exchange?

> Also, I don't get why performance would be less critical than that of ECDHE. In a full handshake, you do both an ECDSA signature and the ECDHE operations. Why would one matter while the other does…

+1

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 12 Sep 2013 13:41:56 -0700

Rob Stradling <[email-masked]> skrev:
>>> I just thought it seemed like a logical thing to do.  We can already
>do ECDHE-ECDSA using the NIST curves for both keys in certs and for key
>>> Unless NIST can prove that their curves aren't backdoored, I think
>it's likely that some folks (rightly or wrongly) will want to do
>ECDHE-ECDSA without touching the NIST curves at all.  What options do
>they have?
>>

For performance reasons?  It is more efficient.

/Simon
>
>> Also, I don't get why performance would be less critical than that of
>ECDHE. In a full handshake, you do both an ECDSA signature and the
>ECDHE operations. Why would one matter while the other does not?
>
>+1

---

From: Rob Stradling <[email-masked]>
Date: Thu, 12 Sep 2013 21:57:07 +0100

On 12/09/13 21:41, Simon Josefsson wrote:
<snip>
> For performance reasons?  It is more efficient.

So then...

>> ECDHE operations. Why would one matter while the other does not?

...it sounds like it does make sense, for performance reasons, to allow 
Curve25519 (or Ed25519, presumably) to be used for keys in certs too.

---

From: Nico Williams <[email-masked]>
Date: Thu, 12 Sep 2013 16:12:41 -0500

> Curve25519 (or Ed25519, presumably) to be used for keys in certs too.

Yes.

Of course, in practice it's much easier to deploy new ECDH curves for
key agreement than new signature algorithms because the former are
easily negotiated in actual protocols, while the latter are less so.
But, yes.

Nico
--

---

From: Rob Stradling <[email-masked]>
Date: Fri, 13 Sep 2013 10:27:37 +0100

On 12/09/13 22:12, Nico Williams wrote:
<snip>
> easily negotiated in actual protocols, while the latter are less so.

Disagree, I think.  Doesn't the "Supported Elliptic Curves Extension" 
make it easy enough for TLS?

RFC4492 (Section 5.3) says:
   "If the client has used a
    Supported Elliptic Curves Extension, the public key in the server's
    certificate MUST respect the client's choice of elliptic curves;"

So if a TLS Client advertises support for Simon's proposed Curve25519 
NamedCurve, then surely that Client is implying that it supports both 
Curve25519 for key exchange _and_ Curve25519 keys in certs?

---

From: "Paul Bakker" <[email-masked]>
Date: Fri, 13 Sep 2013 11:45:33 +0200

> Curve25519 for key exchange _and_ Curve25519 keys in certs?

I think what Nico means is that the ServerKeyExchange message allows for the
TLS protocol to handle yet-unnamed curves for key-exchange with any client
(that properly handles them).
(http://tools.ietf.org/html/rfc4492#section-5.4)

For the "Supported Elliptic Curves Extension" to 'work' you need the client
to know about the curve beforehand. It has to be named already.
Thus deployment is harder as client actually need to be upgraded.

Regards,
Paul Bakker

---

From: Yoav Nir <[email-masked]>
Date: Fri, 13 Sep 2013 14:10:01 +0000

On Sep 13, 2013, at 12:27 PM, Rob Stradling <[email-masked]> wrote:

> Disagree, I think.  Doesn't the "Supported Elliptic Curves Extension" make it easy enough for TLS?

No, because the key that I use is the private key that matches the public key in the certificate I got from some vendor. If I got a certificate with the NIST P-256 curve, I can't use the Curve25519 signatures. I can only use the NIST P-256 curve, because that is what is in my certificate. For ECDHE I can support multiple curves.

This also affects the CAs. They can't deploy certificates with Curve25519 unless all browsers support those curves, so in reality, only the NIST curves are currently viable for signatures.

Yoav

---

From: Rob Stradling <[email-masked]>
Date: Fri, 13 Sep 2013 23:37:36 +0100

> No, because the key that I use is the private key that matches the public key in the certificate I got from some vendor. If I got a certificate with the NIST P-256 curve, I can't use the Curve25519…

Sure.

> This also affects the CAs. They can't deploy certificates with Curve25519 unless all browsers support those curves,

Disagree.  If only one browser signals support for the Curve25519 
NamedCurve in the "Supported Elliptic Curves Extension", then (suitably 
enhanced) servers could send Curve25519/Ed25519 certs to this browser 
and RSA/DSA/P-256/whatever certs to other browsers.

> so in reality, only the NIST curves are currently viable for signatures.

Agreed, but I'm thinking about the future.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 24 Sep 2013 17:28:11 +0200

> Identifiers in your draft?

Curve25519 is not directly usable with ECDSA, I believe, so OIDs aren't
sufficient.  Ed25519 is more relevant, however it uses the EdDSA
signature system instead of ECDSA so possibly more of RFC 5480 has to be
duplicated/modified in order for Ed25519 to work.

Given the performance improvements with Ed25519, I think this is a
interesting topic to pursue.  Perhaps a small team of people can get
together and work out what is required.  It doesn't belong in the TLS WG
though.

/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 24 Sep 2013 17:32:30 +0200

All,

I have updated my Curve25519 draft, primarily to clarify that Curve25519
isn't directly applicable to X.509 signatures.

http://tools.ietf.org/html/draft-josefsson-tls-curve25519-01

/Simon

---

From: Adam Langley <[email-masked]>
Date: Tue, 24 Sep 2013 11:34:12 -0400

> duplicated/modified in order for Ed25519 to work.

Curve25519 and Ed25519 are the same curve - Ed25519 just uses the
twisted Edward's isomorphism of curve25519 to make some calculations
simpler and then builds a Schnorr-like signature scheme with it.
(Curve25519 implementations typically use a Montgomery ladder which
isn't suitable for some of the operations that the signature scheme
needs.)

(Indeed, one can use the Ed25519 code to perform fixed-base,
curve25519 operations faster than the curve25519 code.)

Cheers

AGL

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 24 Sep 2013 22:06:54 +0200

> curve25519 operations faster than the curve25519 code.)

Sure, I know, but I don't see how to get to signing PKIX certs anyway.
Ed25519 is used with EdDSA, not ECDSA.  RFC 5480 is about ECDSA, ECDH,
and ECMQV.  5480 does not specify how EdDSA is used with PKIX.

Are you saying that you would use the ECDSA vehicle of RFC 5480 for
EdDSA as well?  It seems like mild abuse of the acronyms, but I may be
mistaken.

Or perhaps my question really is: how do you think we'll get to signing
PKIX certs using EdDSA with the Ed25519 curve?

My (not published) Ed25519 PKIX draft define OIDs for Ed25519 but I'm
not convinced that is sufficient.

/Simon