Subject: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement

From: Simon Josefsson <[email-masked]>
Date: Sat, 11 Jan 2014 17:32:53 +0100

Dear WG,

I may have missed to announce this document before, since some people
appear to have missed it.  This email is an attempt to introduce the
draft to the TLS WG properly.

This draft started out as specifying Curve25519 ECDHE key agreement for
TLS, back on September.  Manuel Pegourie-Gonnard jumped in as co-author
and has added details on public/private key representation, shared
secret computation, and test vectors, for the -02 draft.

In the latest -03 version of the draft, I have changed the document to
specify EC Named Curve code points for all "additional elliptic curves"
(i.e., Curve25519, E382, M383, Curve3617, M511, E521).  Some of the
Curve25519-related text may no longer be applicable to all curves, but
hopefully that can be fixed later on.

The latest draft is here:
http://tools.ietf.org/html/draft-josefsson-tls-curve25519-03

The additional curves come from the following CFRG draft, and my current
thinking is that our draft (for TLS) would stay in sync with the list of
curves in the CFRG document.

http://tools.ietf.org/html/draft-ladd-safecurves-02

We'd appreciate general feedback on the draft, especially if there is
any interest in adopting this document, and particular feedback on the
following points:

1) Do we need all these curves defined for TLS?  What is the selection
   critera for including/exluding some of the curves?  Is that a TLS
   process, or an CFRG process?

2) Does description of private/public key representation and computation
   of shared secret belong in draft-josefsson-tls-curve25519?  It has to
   be somewhere, I believ, but possibly this could go into
   draft-ladd-safecurves, or some other generic document, unless there
   are TLS-specific aspects.  Insight into this would be appreciated.

Cheers,
/Simon

---

From: Dr Stephen Henson <[email-masked]>
Date: Sat, 11 Jan 2014 17:28:16 +0000

>    are TLS-specific aspects.  Insight into this would be appreciated.

A comment on the following paragraph:

   This document only describes usage of additional curves for ephemeral
   key exchange (ECDHE), not for use with long-term keys embedded in
   PKIX certificates (ECDH_ECDSA and ECDH_ECDSA).  This is because
   Curve25519 is not directly suitable for authentication with ECDSA,
   and thus not applicable for signing of e.g.  PKIX certificates.  See
   draft-josefsson-eddsa-ed25519 for a parallel effort.

Although the curves are not directly suitable for authentication this doesn't
actually matter because the certificate doesn't have to be signed using the same
curve or indeed the same algorithm. So it would (for example) permit a
certificate containing a curve25519 key signed by a CA using a Brainpool curve
(or even RSA with the relaxed CA signing rules of TLS 1.2). However to do that
would require a standard for the use of curve25519 in certificates which
currently doesn't exist.

Having said that the static ECDH ciphersuites are rarely used and don't offer
forward secrecy.

IMHO a discussion of private/public key format should be in a separate document
which would include an appropriate ASN1.1 format (e.g. PKCS#8 for private keys
and SubjectPublicKeyInfo for public keys). That would enable the use of
curve25519 (and other curves) in a wider range of applications, not just TLS.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 11 Jan 2014 09:31:05 -0800

> curve25519 (and other curves) in a wider range of applications, not just TLS.

But for that we need an OID. Does anyone know where to get one/have
one they want to assign?

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

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

---

From: Dr Stephen Henson <[email-masked]>
Date: Sat, 11 Jan 2014 17:38:03 +0000

> But for that we need an OID. Does anyone know where to get one/have

Private OID arcs are easy to obtain. The following has been suggested for
curve25519:

       1.3.6.1.4.1.3029.1.5.1

        iso(1)
        identified-organization(3)
        dod(6)
        internet(1)
        private(4)
        enterprise(1)
        gutmann(3029)
        ???(1)
        ???(5)
        ???(1)

If we want to use all the curves mentioned they will of course all need OIDs.

Steve.

---

From: Robert Ransom <[email-masked]>
Date: Sat, 11 Jan 2014 09:40:20 -0800

On 1/11/14, Dr Stephen Henson <[email-masked]> wrote:
> curve or indeed the same algorithm.

Montgomery and Edwards curves can easily be used for signature schemes
(remember that “authentication” can refer to protocols other than
signatures).  The problem with using them in ECDSA is that ECDSA is
specified in terms of curves in short-Weierstrass form, and having to
map these curves to short-Weierstrass form would be ugly.  Dr.
Bernstein's EdDSA is even worse: it prohibits every curve that Dr.
Bernstein himself has specified since Curve25519.

It would be easy for a competent author to specify a signature scheme
which doesn't constrain the point formats that it uses.  Feng Hao's
I-D specifying Schnorr proofs of knowledge could be used as a starting
point for this.

Robert Ransom

---

From: Alyssa Rowan <[email-masked]>
Date: Sat, 11 Jan 2014 17:50:45 +0000

On 11/01/2014 16:32, Simon Josefsson wrote:

> [draft-josefsson-tls-curve25519-03]

Strong interest here. Curve25519 in particular has extremely fast,
public-domain constant-time implementations compared to, say,
secp256r1, with better security, and a less clouded origin.

Better forward security at a very fast speed? Yes please!

1. Representation - Endian

I had thought that I might point out that all the existing routines in
the wild use little-endian representations and so that might be a good
reason to prefer that, so the routines can be used directly to
accelerate rollout.

But on reflection, pretty much everything else in internet standards
goes big-endian, so there's consistency there, and an endian swap
isn't exactly a big deal. No objection.

2. Monty & Eddie

You list both Montgomery and Edwards curves in that list. I suggest
just listing the Montgomery curves (Curve25519, M383 and M511) for
this use, as these are the forms that are the very natural choices for
ECDHE, with the handy x-coordinate-only feature.

Edwards forms (Curve1174, E382, Curve3617, E521 in their natural
states) are more eminently suitable for other uses like authentication
(although definitely should not be used with ECDSA, and note EdDSA as
specified is actually closely tied to Ed25519 - really we should
specify a new derivative, which we should really get on with).

You can also convert between the representations (e.g. Ed25519 is the
twisted Edwards isomorphism of Curve25519). The ones which are
naturally specified in Montgomery form have handy basepoints in that form.

I'd suggest putting Curve25519 as a MUST to implement, and M383 and
M511 as a MAY.

3. Security Considerations: Implementation

Thoughtful. Do we need to directly specify that implementations MUST
avoid side-channel attacks, because otherwise they might be tempted to
implement them in a way that isn't constant-time?

(There's a typo in that section, by the way; "22519".)

4. Other uses

I think other uses of these curves, which should definitely be
specified, should be specified in another draft (i.e. something like
EdDSA one, though it may not end up being exactly EdDSA).

We'll want OIDs for that. Can we get some for these "Chicago curves"?
I gather there's one suggested for Curve25519: could Mr Gutmann
perhaps please provide us with some for all of the others? (We could
put them in the eventual CFRG informational RFC for posterity, then.)

- -- 
/akr

---

From: Dr Stephen Henson <[email-masked]>
Date: Sat, 11 Jan 2014 17:56:42 +0000

> implement them in a way that isn't constant-time?

While that is a concern for long time use how significant is it for epehemeral
ciphersuites? In that case the key is typically, generated one ECDH operation
performed and then discarded.

Steve.

---

From: Robert Ransom <[email-masked]>
Date: Sat, 11 Jan 2014 09:58:21 -0800

> ECDHE, with the handy x-coordinate-only feature.

Every Edwards curve listed on the SafeCurves web site can be used just
as efficiently in Montgomery form.  (The converse is not true --
curves with small-integer Montgomery parameter are needlessly
unpleasant to use in Edwards form.  No one should be generating new
curves with small-integer Montgomery parameter.)

> I'd suggest putting Curve25519 as a MUST to implement, and M383 and

Don't use M383 and M511 -- their coordinate fields are awful.
Curve3617 is much better; E-521 and Ed448-Goldilocks are okay.

> implement them in a way that isn't constant-time?

YES.

Robert Ransom

---

From: Alyssa Rowan <[email-masked]>
Date: Sat, 11 Jan 2014 18:17:18 +0000

On 11/01/2014 17:56, Dr Stephen Henson wrote:

>> [the potential risks of non-constant-time ECDHE]
> While that is a concern for long time use how significant is it for
> epehemeral ciphersuites? In that case the key is typically,
> generated one ECDH operation performed and then discarded.

Hmm. I take your point: repeated attacks wouldn't be useful because
the keys are different each time anyway, so side-channel attacks
relying on iteration won't work - they'd have to be one-shot affairs,
and side-channel attacks which work in one shot are extraordinarily
rare and extremely contrived.

Nevertheless, they are not quite so contrived as to be impossible in
all cases, especially given a really determined adversary with
proximity - and all the good implementations of these curves are
already constant-time/memory-access patterns/etc.

I don't think we really want to encourage the proliferation of ones
that aren't (mostly due to the much higher risk that someone'll go
ahead and unwittingly later use them in something that did need them
to be constant-time!).

I'd soften it to a SHOULD implement in a way which minimises the
impact of any possible side-channel attack, but I'd make growly noises
at anyone who didn't in practice. We've had enough timing troubles in
TLS already: the opportunity to avoid another, even if it seems
useless now, I think should be taken.

- -- 
/akr

---

From: Adam Langley <[email-masked]>
Date: Sat, 11 Jan 2014 14:03:39 -0500

> isn't exactly a big deal. No objection.

Happy to see curve25519 specified, but I do object to this. Every
curve25519 implementation follows djb's API, which is byte orientated.
I think it's sensible to leave the exact field representation to the
DH function rather than have that concept spill into TLS. Maybe future
DH functions will want to save an inversion and send extended
coordinates or something.

Flipping the endianness just means that every single implementation
has to undo it before feeding it into the curve25519 function.

Cheers

AGL

---

From: Kurt Roeckx <[email-masked]>
Date: Sat, 11 Jan 2014 20:09:19 +0100

> implement them in a way that isn't constant-time?

So looking at currently available implementations of this, they
are not all constant-time.  See
https://code.google.com/p/curve25519-donna/ for intance that the
portable C version is marked as being none costant-time.

The only other known portable implementation that I know of is by
Matthew Dempsky that's part of nacl, for which I can't find any
information about it being costant-time or not and assume it's
not.

Kurt

---

From: Adam Langley <[email-masked]>
Date: Sat, 11 Jan 2014 14:13:10 -0500

> portable C version is marked as being none costant-time.

Actually, the Tor folks and others have fixed that. I just haven't
updated the page.

Cheers

AGL

-- 
Adam Langley [email-masked] http://www.imperialviolet.org

---

From: Matt Caswell <[email-masked]>
Date: Sat, 11 Jan 2014 19:42:44 +0000

> Private OID arcs are easy to obtain. The following has been suggested for

Given that private OID arcs are easy to obtain would it not be better
to get an IETF arc for this use, rather than using someone's personal
arc? (Is there not an IETF arc already - that seems surprising!?)

Matt

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 11 Jan 2014 19:44:53 +0000

> arc? (Is there not an IETF arc already - that seems surprising!?)

Russ has managed a PKIX OID arc for years and is in the process of
turning that into a set of IANA registries. I mailed him and the
authors of these drafts so expect they'll figure it out.

S.

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 11 Jan 2014 11:51:28 -0800

>    process, or an CFRG process?

Speaking as chair:

The TLS WG is not chartered (or qualified) to assess curves. What I
believe is needed is for the IETF (whether directly or through the
CFRG) to come to consensus on what curves we believe our
protocols should support and then we can adopt them across
the relevant security WGs, doing whatever protocol-specific
work is required then.

I've spoken with our AD about this a little bit, but as far as I know
such an effort hasn't actually been started. Perhaps this is a topic
for SAAG?

-Ekr

---

From: Matt Caswell <[email-masked]>
Date: Sat, 11 Jan 2014 20:00:50 +0000

> such an effort hasn't actually been started. Perhaps this is a topic

Isn't that exactly what Watson Ladd's draft is? That was initiated out
of discussions within CFRG, and is currently being debated by CFRG.

Matt

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 11 Jan 2014 12:40:22 -0800

On Sat, Jan 11, 2014 at 12:00 PM, Matt Caswell <[email-masked]> wrote:
> Isn't that exactly what Watson Ladd's draft is?

Perhaps. That's not quite clear to me from the draft, and for
instance the title is "Additional Elliptic Curves for IETF protocols"
and the contents seem to be, as promised, additional curves.
The mailing list discussion seems consistent with that.

What I believe is actually needed is not just definitions of new
curves but a harmonized set of recommendations about which
curves IETF should or should not use, which we can then use
as a guide to protocol adoption and recommendation (see
for instance http://tools.ietf.org/html/draft-sheffer-tls-bcp-01#section-4.1).

Perhaps that's the endpoint of the CFRG discussion of draft-ladd,
but just based on what I've seen so far it seems like a bigger
discussion. I suspect the CFRG has a role to play here, but
probably this is an IETF security area question as well. That's
why I suggested this would be a good question for SAAG.

-Ekr

---

From: "Salz, Rich" <[email-masked]>
Date: Sat, 11 Jan 2014 16:57:27 -0500

> Given that private OID arcs are easy to obtain would it not be better to get an IETF arc for this use, rather than using someone's personal arc?

It absolutely shouldn't matter; OID's are opaque identifiers and a "vanity IETF" number is silly.  It's much more sensible to use something that is already in use.

	/r$

--  
Principal Security Engineer
Akamai Technology
Cambridge, MA

---

From: Matt Caswell <[email-masked]>
Date: Sat, 11 Jan 2014 22:35:13 +0000

> It absolutely shouldn't matter; OID's are opaque identifiers and a "vanity IETF" number is silly.  It's much more sensible to use something that is already in use.

For Curve25519 possibly (although I hadn't got the impression that the
proposed OID had seen any significant deployment) - but there are a
number of other curves in need of OIDs.

I also wouldn't see an IETF arc as a "vanity" arc. It's a clear marker
of those OIDs that have some backing of a standards authority. No big
deal - but if setting one up is easy to do, why would we not want to
do that?

Its probably a moot point, because from Stephen Farrell's response it
seems like there is something we can use anyway.

Matt

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 12 Jan 2014 08:29:42 +0200

> specify a new derivative, which we should really get on with).

As far as I know (from reading the Ed25519 paper), no, EdDSA is not
tied to Ed25519.

Quoting the paper:

"Choice of curve. Our recommended curve for EdDSA is a twisted Edwards
curve birationally equivalent to the curve Curve25519 from [12]."

Note the word "recommended".

One problem with defining EdDSA for larger curves is that the needed
hashes are large. Even if one uses ~3/2 expansion (largest possible
for certain pretty simple modulo algorithm), even E382 is going to
blow 512 bits.

And there are very few hashes with serious analysis that can do
>512 bits.

-Ilari

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 12 Jan 2014 15:47:35 +0100

> would require a standard for the use of curve25519 in certificates which
Agreed. Actually, a previous (unpublished) version of the draft had a more
precise wording about that, but I unfortunately deleted it in the editing
process. Thanks for noticing.

> Having said that the static ECDH ciphersuites are rarely used and don't offer
Right.

> curve25519 (and other curves) in a wider range of applications, not just TLS.
I don't disagree that such a document would be a useful addition, but since
ECDHE in TLS isn't using ASN.1 to represent the keys, and only needs to
represent public keys, I felt like the easiest way forward was to specify only
what's needed to do ECDHE in TLS, that is how to represent public keys, without
ASN.1.

Manuel.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 12 Jan 2014 15:54:31 +0100

> ECDHE, with the handy x-coordinate-only feature.
I tend to agree. But as was noted by others (including Robert Ransom on the CFRG
list), every Edwards curve can also be used to do Montgomery. So I'm curious to
hear more about whether people are also interested by the Edwards curve for
ECDHE or if the Montgomery curves are enough.

One argument for using only the Mongtgomery curves is that we probably don't
need more than one curve (of the same origin) at each security level. But then,
this argument could be used to conclude we don't need the Montgomery curves at all.

> (There's a typo in that section, by the way; "22519".)
Thanks.

Manuel.

---

From: Robert Ransom <[email-masked]>
Date: Sun, 12 Jan 2014 07:01:14 -0800

> ECDHE or if the Montgomery curves are enough.

* ECDH should use only Montgomery form, *never* Edwards form.  (There
are key-agreement protocols which require Edwards form.  ECDH is not
one of them.)

* Every curve with minimal Edwards-form parameter can be efficiently
used in Montgomery form with the simplest possible implementation.
The converse is not true.

* Most of the ‘SafeCurves’ curves (including all of the ones specified
in Montgomery form, except Curve25519) would be needlessly unpleasant
to implement.  The only curves that I could support using for ECDH at
this time are Curve25519, Curve3617, and (possibly) E-521.

Robert Ransom

---

From: Alex Elsayed <[email-masked]>
Date: Sun, 12 Jan 2014 07:02:12 -0800

> information about it being costant-time or not and assume it's

I'd suspect that the reason there's no information about that _part_ of NaCl 
being constant-time is due to the constant-time guarantees being stated as 
applying to _all_ of NaCl (http://nacl.cace-project.eu/features.html)

> No data-dependent branches
> ...
> No data-dependent array indices
> ...
> No dynamic memory allocation
> ...

Thus, if it didn't meet those constraints it wouldn't be in NaCl at all.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 12 Jan 2014 16:17:28 +0100

> the relevant security WGs, doing whatever protocol-specific
Thanks for making that clear.

Just to be sure I'm not misunderstanding, is the problem adding a whole family
of curves, or would that be just the same if the draft was only about
Curve25519? I'm asking because there seem to be interest by many people,
including implementers, to have support for Curve25519 in TLS sooner rather than
later, and if I remember correctly there was some consensus in the thread [1]
about the fact that it would be a nice option to add (even if there was
disagreements on some points, eg comparing the "rigidity" of Curve25519 vs
Brainpool).

[1]: https://www.ietf.org/mail-archive/web/tls/current/msg09813.html

So, do you think it would OK to pursue efforts on a Curve25519-only draft, or if
any draft adding new curves should way for a document from CFRG and/or SAAG
establishing more general guidance on which curves (and associated protocol
variants) to use for IETF protocols given that such a document will probably be
much longer to produce than just a Curve25519-in-TLS document?

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 12 Jan 2014 07:18:13 -0800

> The converse is not true.

Why is using twisted Edwards form, or the Montgomery ladder, so bad from
an implementation perspective? Twisted Edwards form makes the converse
true. I now mention it in the draft, as well as the AFRICACRYPT paper which
introduces it.

Not every implementation needs to be the fastest, just fast enough.

> this time are Curve25519, Curve3617, and (possibly) E-521.

You will have to expand on this. All of these curves have primes of
similar shapes,
and while some might require more annoying limb placements than
others, without having
actual implementations to compare, we don't know how big the impact
actually will be.

M-383 is actually better than Curve3617 from your perspective: it
reduces the size of
the actual coefficient in Montgomery form and in twisted Edwards form
will be the same size.
The prime is also the same.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 12 Jan 2014 16:29:47 +0100

> performed and then discarded.
I was under the impression that, for performance reasons, some implementations
(I thought this included OpenSSL but your message seems to imply I was mistaken)
didn't discard the private exponent after each key exchange but instead reused
it for a given period of time and/or number of key exchanges.

If that is the case, then these implementations probably need to be constant-time.

Also, though it's a less compelling argument, there's always the risk that a
non-constant time implementation used initially only for truly ephemeral keys
will be re-used later with long-term keys.

Manuel.

---

From: Kurt Roeckx <[email-masked]>
Date: Sun, 12 Jan 2014 16:35:04 +0100

> applying to _all_ of NaCl (http://nacl.cace-project.eu/features.html)

I also looked at the source in the mean time and couldn't see an
obvious problems with it.

So I think all known implementations are currently constant-time.

Kurt

---

From: Dr Stephen Henson <[email-masked]>
Date: Sun, 12 Jan 2014 15:36:24 +0000

> what's needed to do ECDHE in TLS, that is how to represent public keys, without

Although TLS and ASN.1 represent the keys in different ways they are wrappers
round the same low level point format specified in X9.62/SEC1.

Specifically in RFC4492 for TLS in 5.4, the description of ECPoint.

There is an equivalent reference for certificates in in RFC5480 2.2, again ECPoint.

I think we should keep this consistency and have the point format for the new
curves defined in one standard, whatever that might be.

Steve.

---

From: Robert Ransom <[email-masked]>
Date: Sun, 12 Jan 2014 07:46:36 -0800

On 1/12/14, Watson Ladd <[email-masked]> wrote:
>>> I tend to agree. But as was noted by others (including Robert Ransom on
>>> the
>>> CFRG
>>> list), every Edwards curve can also be used to do Montgomery. So I'm
>>> curious
>>> to

Dr. Bernstein's Ed25519 paper specifies the a=-1 twist because that
twist has strictly faster formulas than any other value of a, even if
that twist requires a large value of d.

> Not every implementation needs to be the fastest, just fast enough.

That does not justify choosing curves in a way that unnecessarily
harms the performance of simple implementations and raises the
complexity of fully optimized implementations.

> the actual coefficient in Montgomery form and in twisted Edwards form

Curve3617's Montgomery-form parameter is 1/3617 (or something close to
it).  (In the Montgomery formulas, a reciprocal-of-small-integer
parameter is as efficient as a small-integer parameter.)  M-383's
Montgomery-form parameter will be a small integer with about 6 decimal
digits.

> The prime is also the same.

Curve3617's coordinate field is 414-bit; M-383's coordinate field is
383-bit.  I don't think they're the same.

Robert Ransom

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 12 Jan 2014 17:04:27 +0100

> curves defined in one standard, whatever that might be.
Good point.

Since this format may be used by more than just TLS, and was originally defined
outside the IETF, what would be the most appropriate place to discuss extending it?

Manuel.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 12 Jan 2014 17:17:44 +0100

> has to undo it before feeding it into the curve25519 function.
I understand your point.

Concerning implementations, unless I'm mistaken all the implementations of
Curve25519 you mention use custom routines for field arithmetic. I was thinking
about other implementations might want to use a more generic bignum library,
whose output function will probably be big-endian since that's the ordering
generally used in protocols. So for these implementations, big-endian would
probably be more natural.

(As a matter of fact, that's precisely the case of the implementation in
PolarSSL, but of course it wouldn't be fair to count it as pre-existing the
draft, since I've been involved in both the draft and this implementation.)

Manuel.

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 12 Jan 2014 14:21:16 -0500

I don't want this question to get lost in the general discussion so I am explicitly addressing this to the AD's

>> I think we should keep this consistency and have the point format for 
>> the new curves defined in one standard, whatever that might be.

> Since this format may be used by more than just TLS, and was originally defined outside the IETF, what would
> be the most appropriate place to discuss extending it?

Some folks have been working on a concrete proposal, which is that we "take" 0x41 as a new marker byte in ECPoint, and use that to mean "key format defined by the curve"  Ask IANA to maintain a curve point-format registry.  For example, Curve25519 would have 0x41 followed by the 32 bytes of x-value for the key.

So, where should such a document be started?

Many of us are feeling pressure to implement ECDHA to get PFS for our customers, and see the efficiency of Curve25519 as very important.  That is, the  clock is ticking...

	/r$

---

From: Dr Stephen Henson <[email-masked]>
Date: Sun, 12 Jan 2014 19:29:26 +0000

> Many of us are feeling pressure to implement ECDHA to get PFS for our customers, and see the efficiency of Curve25519 as very important.  That is, the  clock is ticking...

Based on the current text, perhaps draft-ladd-safecurves (which might get
renamed) being discussed in CFRG? It already has some brief notes on key formats
though not the same as above.

I'm thinking we'd have a section indicating a (recommended, suggested or just
possible) key format and then the TLS, a certificate format document and any
other interested protocols could reference it.

Steve.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 12 Jan 2014 11:33:19 -0800

> though not the same as above.

I've expanded the section on key formats. So far I'm using big-endian.
The last thing I want to do is
reignite the crusade. Yes, there is a software compatibility issue,
but it is a minor one.

> other interested protocols could reference it.

Good idea: in fact the latest versions have a compressed point format.
The compressed point patent is
expiring this summer, and I don't think it applies to anything that
isn't short Weierstrass anyway.

---

From: Sean Turner <[email-masked]>
Date: Sun, 12 Jan 2014 14:39:18 -0500

> It absolutely shouldn't matter; OID's are opaque identifiers and a "vanity IETF" number is silly.  It's much more sensible to use something that is already in use.

Agree with Rich here.  OIDs are OIDs whether it’s a private arc, a google arc, or an IETF arc - it just doesn’t matter as long as we pick one and standardize it.  If one has been used in the wild we ought to just adopt it.

spt

---

From: Sean Turner <[email-masked]>
Date: Sun, 12 Jan 2014 14:46:53 -0500

Rich,

Stephen and I will come up with a plan.  I hope to get back to you fairly soon being that Stephen and I chat at least once a week and we’ve known this was coming down the pipe.

spt

---

From: Adam Langley <[email-masked]>
Date: Sun, 12 Jan 2014 14:53:48 -0500

> probably be more natural.

Using a generic bigint library is tough if you want to be constant
time. (For example, integer division on Intel is variable time.)

Also, internally, the library likely stores values as a series of
words in little-endian order and is likely to be operating on
little-endian systems, so little-endian is the more native
representation.

I guess my overall point is that I don't see the concept of an
"integer" as being a good one to put into TLS here. I think keeping a
DH function as something that operates on bytestrings makes sense.
Maybe they'll want to operate on binary fields, or compress the 'y'
coordinate into one of the unused bits, or export a different
coordinate form.

Cheers

AGL

---

From: "Jim Schaad" <[email-masked]>
Date: Sun, 12 Jan 2014 13:24:09 -0800

You can get OIDs assigned out of the PKIX arc by IANA when the document
progresses.  Russ is currently moving control of the arc from him to IANA>

Jim

> -----Original Message-----
> From: TLS [mailto:[email-masked]] On Behalf Of Matt Caswell
> Sent: Saturday, January 11, 2014 11:43 AM
> To: Dr Stephen Henson
> Cc: [email-masked]; Simon Josefsson
> Subject: Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS
ECDH
> key agreement
> Given that private OID arcs are easy to obtain would it not be better to
get
> an IETF arc for this use, rather than using someone's personal arc? (Is
there
> not an IETF arc already - that seems surprising!?)
> 
> Matt

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 12 Jan 2014 17:43:52 -0500

> Stephen and I will come up with a plan.  I hope to get back to you fairly soon being

Great, thanks.  If there's anything I can do to help please let me know.

	/r$

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Mon, 13 Jan 2014 00:38:14 +0100

> time. (For example, integer division on Intel is variable time.)
Right, but it seems to me some randomisation can help here.

> little-endian systems, so little-endian is the more native
Agreed.

> coordinate into one of the unused bits, or export a different
If there was currently no concept of "integer" in TLS, I'd totally agree with
you here. But since there is, and they usually are represented as big-endian,
there is a tension between being consistent with existing usage and going the
arguably better way.

Manuel.

---

From: Adam Langley <[email-masked]>
Date: Sun, 12 Jan 2014 20:12:49 -0500

> there is a tension between being consistent with existing usage and going the

When it comes down to it - reversing 32 bytes isn't going to make or
break it in either way.

I guess I just see a byte string orientated interface to DH functions
as being the right way to go. We have a legacy of over-general
elliptic curve support that tries to support arbitrary curves and that
led to 'integers' being a concept in TLS regarding EC. However,
nobody(?) implements explicit_prime/explicit_char2 so what we actually
have are three DH functions: p256, p384 and p521 and they serialise as
0x04 <big-endian x> <big-endian y> in practice. Although it's an
opaque <1..2^8-1> in RFC 4492, the big-endian is coming from X9.62.

So, given an opaque<1..2^8-1> in TLS and a desire to plug curve25519
in there, using curve25519's format just seems less surprising and
simpler.

Cheers

AGL

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 12 Jan 2014 21:17:45 -0500

> So, given an opaque<1..2^8-1> in TLS and a desire to plug curve25519 in there, using curve25519's format just seems less surprising and simpler.

+1

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Mon, 13 Jan 2014 03:41:18 +0100

On 13/01/2014 03:17, Salz, Rich wrote:
>> So, given an opaque<1..2^8-1> in TLS and a desire to plug curve25519 in
>> there, using curve25519's format just seems less surprising and simpler.
> 
> +1
> 
Just to be clear: curve25519's format, plus a leading byte, (eg. 0x41) to
indicate "curve specific encoding"?

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 12 Jan 2014 18:55:04 -0800

> indicate "curve specific encoding"?

I have no objection to this idea. If a snap/false/jump/start in TLS
1.3 needs to indicate the curve in a compact way,
we can handle that later.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 12 Jan 2014 19:22:55 -0800

>    process, or an CFRG process?

It's unclear. Eric Resola (in a cousin n-removed from this email)
seems to think that
CFRG should do it, but unless he asks the CFRG chairs there doesn't seem to be
a process for this conversation to happen. Part of the reason is that
Curve25519 is
secure, so in some sense there is nothing to discuss on the CFRG end.
It comes down to
"what should be supported" and efficiency argues Curve25519 should be
in the mix.

The easiest solution is someone to ask if anyone disagrees, and if no
one does, consider
the security conversation over.

>    are TLS-specific aspects.  Insight into this would be appreciated.

It looks good, but the specification should ideally be in the draft or
cited in an informative RFC. draft-ladd aims to completely
specify what is exchanged, and so is a better (IMHO) source for the
normative part then the curve25519 paper.
Worst case you can write something close to the specification section
of "Cryptography in NaCl" or "Curve25519:
New Diffie-Hellman Speed Records" in the case draft-ladd fails to progress.

Sincerely,
Watson Ladd

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 12 Jan 2014 23:44:37 -0500

> Just to be clear: curve25519's format, plus a leading byte, (eg. 0x41) to indicate "curve specific encoding"?

Yes.

---

From: Yoav Nir <[email-masked]>
Date: Mon, 13 Jan 2014 07:27:14 +0000

> "what should be supported" and efficiency argues Curve25519 should be

Or you can do the equivalent of the signature authentication in IKEv2 draft:
http://tools.ietf.org/html/draft-kivinen-ipsecme-signature-auth-04

Just create a draft for a TLS extension that allows you to specify a curve and point format as OIDs. Not sure whether that's a good idea, though.

> the security conversation over.

That didn't work so well for Dragonfly, did it?

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Mon, 13 Jan 2014 07:21:35 -0800

> That didn't work so well for Dragonfly, did it?

The huge difference between these curves and Dragonfly is that these
curves satisfy every known property required to make ECDH secure, and
also some designed to make implementation easier. Dragonfly had
obvious security flaws.

If you want more of a process, go ahead and start it. But I think what
you will get is a bunch of "Yes, these numbers are prime"
and "I clicked all the links on safecurves.cr.yp.to and used PARI to
verify everything". If they are missing attacks, that's one thing,
but they aren't.

Security conversations are never over: it's entirely possible that
tomorrow a paper hits IACR which identifies a new set of
weaknesses in elliptic curves, and then we have to go through and see
which ones fall.

Sincerely,
Watson Ladd