Subject: Re: [TLS] Curve25519 in TLS and Additional Curves in TLS

From: Kurt Roeckx <[email-masked]>
Date: Wed, 2 Apr 2014 18:43:40 +0200

On Wed, Jan 22, 2014 at 05:18:54PM +0100, Simon Josefsson wrote:
> 
> 1) Curve25519 for TLS.  This was the original scope of the draft.  The
> URL is: <http://tools.ietf.org/html/draft-josefsson-tls-curve25519>.  As
> far as I know, there are no outstanding issues, and it is possible to
> implement and deploy Curve25519 in TLS following the draft.  Please
> prove me wrong with comments or preferrably patches to the draft.

So what's the status of this?

Kurt

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 02 Apr 2014 19:22:02 +0100

On 02/04/2014 17:43, Kurt Roeckx wrote:

> So what's the status of this? [draft-josefsson-tls-curve25519]

As I recall, there were only three issues raised in the discussion in
January (and one tiny one I'm raising now that is very easily fixed in
the normal course of RFC editing). Discussion seemed to just peter out
after then.

If I may summarise where we left off (and _please_ speak out if you
feel I'm grossly mischaracterising anything or got anything wrong!):—

1. Draft-04 uses its own point format, a 'big-endian' representation,
   (and adds a length byte).

   That differed from every existing Curve25519 implementation in the
   wild, which use a 'little-endian' representation.

   • Both Rich Salz and Robert Ransom spoke strongly for simply using
     the existing little-endian format used by all Curve25519
     implementations already in the wild, and pointed out there was no
     technical reason to break compatibility and change that to
     anything else.

     [No such technical reasons were seemingly presented in the ensuing
      discussion. /akr]

   • Manuel Pégourié-Gonnard wasn't married to the point format in -04,
     had no objection to using the existing little-endian format, and
     requested comments 'in the next few days' from anyone who did have
     objections.

   • Watson Ladd said endianness wasn't a good reason to vote no, and
     asked please not to reignite the endianness 'holy war'.

   • Nikos Mavrogiannopoulos pointed out protocols are often expected
     to outlive existing implementations and aren't typically designed
     based on them.

     [Although this one would, presumably, be an exception? /akr]

     He also pointed out almost all IETF protocols use the big-endian
     format for transferring integers, so that implementations would be
     prepared for any endian issues anyway.

   • James Cloos suggested 'Internet-endian is the better choice'.
     [I presume, from context, that he meant big-endian. /akr]

   • Bill Frantz simply pointed out that it wouldn't be unprecedented
     to have little-endian data in an Internet Protocol.

   [For what it's worth - i.e. almost nothing! - I myself favour
    matching the Curve25519 reference: so, little-endian. /akr]

2. We need to specify what, exactly, to do with the unused high bit.

   As the discussion in January covered, except for one, buggy
   implementation, all Curve25519 implementations in the wild always
   produce 0, and always ignore it.

   We should probably specify that as required behaviour; it allows for
   using it for something else later, which was discussed. Manuel
   agreed that implementations SHOULD mask off the high bit. That's not
   in draft-04, but it should be in -05?

   There was talk about maybe using it later for sign-of-y or something
   else, for other protocols. I don't know if that went anywhere.

   [Again, I favour the draft simply matching the original Curve25519
    implementation: high bit SHOULD be 0, high bit SHOULD be ignored.
    /akr]

3. The length byte was talked about, and the consensus seemed broadly
   to be: specify 32 now, allow 64 for if we want, say, an Edwards-form
   y-coordinate for some other protocol later, and have the first 32
   bytes of that match the 32-byte format.

   [I have no position on this. /akr]

4. The NamedCurve value allocation is still [TBD1] in -04 - we'd need an
   actual value allocated before implementing that in the wild (outside
   of pure testing, where we can just use a private value)?

That's about all I can remember. Were there any other substantive issues?

Thanks for reminding us about the stalled discussion.

I'm keen to start getting things out there myself: if we can wrap up
the remaining issues, I think that'd be good for everyone.

- -- 
/akr

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 2 Apr 2014 15:26:03 -0400

Nice summary.

I think we had consensus around using the little-endian point format, but this requires some more overhead (a new ECPoint type and an IANA registry) that nobody has stepped up to do yet.

--  
Principal Security Engineer
Akamai Technology
Cambridge, MA

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 02 Apr 2014 23:03:49 -0700

On 04/02/2014 11:22 AM, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

The ECPoint is defined as follows,

            struct {
                opaque point <1..2^8-1>;
            } ECPoint;

Is the format on the wire per section 2.3
    33 32 xx xx xx ... xx
or, suggested,
    65 64 xx xx xx ... xx yy yy yy ... yy ?

Or I am reading it incorrectly and the extra byte mentioned in the draft 
is actully a part of standard TLS encoding of the length byte?

At first I interpreted it as former. Then the question is why the 
(excessive) length byte is needed? The negotiated Curve25519 tells that 
32 bytes are expected. (If there are 64, there is a y there.)

> the remaining issues, I think that'd be good for everyone.
...

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 03 Apr 2014 10:55:35 +0200

> is actully a part of standard TLS encoding of the length byte?
The intention of the current draft is that the wire format be

32 xx xx ... xx

So the "additional length byte" is indeed just the one from the TLS encoding.

In the next iteration of the draft, it might change to

33 tt xx xx .. xx

Where tt would be an "encoding type" which would allow for future extensions
like transmitting y too, or a bit of y, or (parts of) other representation (eg
Edwards coordinates).

Manuel.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 03 Apr 2014 10:57:12 +0200

> Nice summary.
+1 Thanks for putting it together.

> I think we had consensus around using the little-endian point format,

Agreed.

> but
> this requires some more overhead (a new ECPoint type and an IANA registry)
> that nobody has stepped up to do yet.
> 
Yep.

I'll try to update the draft soon, probably over the week-end.

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 3 Apr 2014 09:52:58 -0700

> like transmitting y too, or a bit of y, or (parts of) other representation (eg

I don't think this is a good idea. At the time when one side sees the
point it is too late to negotiate. So points with different encodings
should be indicated as different in the Client Hello message to enable
negotiation of which one to send. Furthermore, I don't see benefit to
the potential extensions yet for pure DH.

Also, do we really need a length prefix on a string that is always 32
bytes long? I get that the TLS encoding provides that, but length
prefix formats are a can of worms: what should happen when 33 0 or 32
32 xx .. are encountered?

Sincerely,
Watson Ladd

>
> Manuel.
>
> _______________________________________________
> 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: Andrey Jivsov <[email-masked]>
Date: Thu, 03 Apr 2014 10:35:38 -0700

> the potential extensions yet for pure DH.
I second this.

> 32 xx .. are encountered?
I assume you are commenting on the case with tt present. Certainly, 
there will need to be consistency checks with such a tt.

My reply regarding the current draft with clarification from Manuel follows:

RFC 5246 is listed as a normative reference. As such, it defines the the 
encoding for the

    opaque something <1..2^8-1>

The reader is expected to know that "something" is encoded with an additional byte for the length. Thus, I find the item (2) in sec. 2.3 confusing (IMHO more confusing than helpful).

>     Note that ECPoint.point differs from the definition of public keys in
>     [Curve25519  <http://tools.ietf.org/html/draft-josefsson-tls-curve25519-04#ref-Curve25519>] in two ways: (1) the byte-ordering is big-endian, wich
>     is more uniform with how big integers are represented in TLS, and (2)
>     there is an additional length byte (so ECpoint.point is actually 33
>     bytes), again for uniformity (and extensibility).

Would the following be clearer:

> Unlike the definition of public keys specified in [Curve25519],
> ECPoint.point uses big-endian byte ordering. As defined in [RFC5246],
> the ECPoint.point is serialized with one-byte block size. The payload must be 32
> bytes, even when one or more leading bytes are zeros.

...

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 03 Apr 2014 21:13:56 +0200

On 03/04/2014 18:52, Watson Ladd wrote:
> negotiation of which one to send.

That's the intention, yes (indicating supported point formats in the existing
ClientHello and ServerHello extensions).

> Furthermore, I don't see benefit to
Just because we can't see a benefit for extensions now doesn't mean we shouldn't
leave the door open for later ideas.

> 32 xx .. are encountered?
Well, what's already hapenning: implementations check for consistency. This is
no different than with the current short Weierstrass curves.

Manuel.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 03 Apr 2014 21:15:08 +0200

>> bytes, even when one or more leading bytes are zeros.
Thanks for the helpful suggestion.

Manuel.

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 7 Apr 2014 11:51:02 +0200

You wrote:

> > 1) Curve25519 for TLS.  This was the original scope of the draft.
> > The URL is:
> > <http://tools.ietf.org/html/draft-josefsson-tls-curve25519>.  As
> > far as I know, there are no outstanding issues, and it is possible
> > to implement and deploy Curve25519 in TLS following the draft.
> > Please prove me wrong with comments or preferrably patches to the
> > draft.
> 

The above is still the current status as far as I am aware.

To move the draft forward in the RFC process, we need find an AD to
sponsor the draft or (I guess) the TLS WG to adopt it.

It would be useful if TLS implementers let the list know what their
status is (waiting/planning/implemeted/rejected).

If interop testing is pending on having an assigned number, I suggest
using 65024 as the Curve25519 EC Named Curve number for testing
purposes.

/Simon

---

From: Watson Ladd <[email-masked]>
Date: Mon, 7 Apr 2014 07:55:27 -0700

> sponsor the draft or (I guess) the TLS WG to adopt it.

Does anyone object to the WG adopting it?

Sincerely,
Watson Ladd

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 08 Apr 2014 23:24:39 -0400

> Does anyone object to the WG adopting it?

I support WG adoption of draft-josefsson-tls-curve25519.

	--dkg

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 9 Apr 2014 07:37:31 -0400

I support it to, but I want to see it in little-endian format, which requires a bit more coordination before it could be published.

	/r$

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 09 Apr 2014 13:50:31 +0200

> I support it to, but I want to see it in little-endian format, which requires a bit more coordination before it could be published.

I believe you have already made your point several times. I think it is
important to see comments from people who plan or work on implementing
this draft, how each format affects them and whether there is a need for
little-endian.

regards,
Nikos

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 09 Apr 2014 13:17:47 +0100

>this draft, how each format affects them and whether there is a need

Don't we already seem to have consensus on little-endian, and that is what will be in the revised draft-04?

Was the revised draft not what we're talking about? Sorry if I'm misunderstanding. [The significant fallout from the "Heartbleed" bug may be causing a little more disruption at present than is normally typical.]

Subject to that (see the previous comments in my summary), I have no objections to the WG adopting the revised draft -04 with the amendments discussed (as little-endian).

As previously stated, implementation of the draft is notably simplified by using the native little-endian format already used by all implementations of curve25519. (As everyone will no doubt have fresh in their mind, the simpler an implementation is able to be, the less likely it is to have nasty bugs, in general at least.)

- --
/akr

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 09 Apr 2014 15:00:57 +0200

> Don't we already seem to have consensus on little-endian, and that is what will be in the revised draft-04?

I believe that you summarized the issue very nicely in a previous
e-mail, but my reading of having a consensus for little-endian is
different than yours.

As far as I am concerned, I do not see why an implementation which will
not use the existing code, must treat the endianness of points from
curve25519 differently than the points of any other curve in TLS. In any
case, the arguments are already presented and that's what I mentioned to
Rich. I think we need more input from other people who plan or are
already implementing this curve in TLS.

regards,
Nikos

---

From: Watson Ladd <[email-masked]>
Date: Wed, 9 Apr 2014 08:00:40 -0700

> already implementing this curve in TLS.

Your code should not use the bignum library you already have. It
should call into libnacl or the guts that are in libsodium, both quite
liberally licensed.

This is because DJB writes and distributes perfect code, and you do
not. Your bignum implementation has data-dependent branches and so
leaks information to an attacker on the same hardware, as well as
taking different times depending on branch state. If particularly bad,
you have data dependent loops in reduction modulo a prime. libnacl
avoids all these problems.

In fact, because you are the GnuTLS developer, I know exactly what
your bignum library, gmp does. And it isn't pretty: operations can
take different paths depending on argument size, which includes
lopping off zero limbs. Modulo is computed by division, which involves
an instruction that is notoriously variable-time on many
architectures.

Your bignum implementation is also slow. This is because it has to
permit arbitrary chains of addition between multiplications, which
don't happen in ECC. As a result it needs to reduce each sum, which is
unnecessary and slow. The libnacl implementations defer this reduction
until the end, and partially reduce products for additional speed,
taking advantage of the prime.

The gap between the implementation you will write, and the
implementation you can just use, in security, speed, and safety, is
enormous.

If you do decide to persist in this folly, reversing the bytes won't
stop you, sadly. But I wish it could.

Sincerely,
Watson Ladd

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 09 Apr 2014 08:57:37 -0700

Re endianess,

shouldn't the decision here be based on the current distribution of 
little v.s. big endian architecture on CPUs that are likely used in TLS 
servers and accelerators?

( It doesn't matter much for end-clients, I suppose. One may argue that 
this doesn't matter for the rest either. But then the argument goes that 
the big endian is the traditional canonical representation. )

---

From: Yoav Nir <[email-masked]>
Date: Wed, 9 Apr 2014 19:09:36 +0300

On Apr 9, 2014, at 6:57 PM, Andrey Jivsov <[email-masked]> wrote:

> Re endianess,
> 
> shouldn't the decision here be based on the current distribution of little v.s. big endian architecture on CPUs that are likely used in TLS servers and accelerators?
> 
> ( It doesn't matter much for end-clients, I suppose. One may argue that this doesn't matter for the rest either. But then the argument goes that the big endian is the traditional canonical representation. )

It became the canonical representation when the Internet ran on Sun boxes with Sparc chips, which were Big-endian, and a little bit on other platforms such as mainframes and powerPCs (which were also big-endian) and VAX and Intel (which were little-endian). Now Intel dominates the servers, and the clients are split among Intel and ARM, both of which are little-endian. 

Regardless, reversing a string of bytes is such an efficient process, that it probably makes no measurable difference in performance which way the bits on the wire are read and written.

I think the decision should be made based on convenience and the chance for errors, although I can’t tell which way that goes. BTW: the same decision should be made for ChaCha/Salsa and Poly1305.

Yoav

---

From: Fabrice <[email-masked]>
Date: Wed, 9 Apr 2014 11:24:35 -0700

> On Apr 9, 2014, at 4:50, Nikos Mavrogiannopoulos <[email-masked]> wrote:
> 

As a possible implementer of this, I don't care one bit. I would most likely use an existing little endian implementation, but I can also reverse a byte string when needed.

-- Fabrice

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 10 Apr 2014 10:22:45 +0200

> an instruction that is notoriously variable-time on many

And how does this affect an ephemeral key exchange? I'll reply for you.
It has no effect, because it is an ephemeral key exchange.

Being constant time, _matters_ when you do operations on a long-term
key, not when you do one operation on a one-time-key. So in the cases
where it matters nettle (the crypto library used by gnutls), is constant
time, and outperforms all other implementations so far.

> Your bignum implementation is also slow. 

See the point above. I'd be interested to know how you figured that gmp
is slow.

btw. I never mentioned implementing curve25519 using gmp or otherwise,
because I am not going to implement the low level part of it. That's why
I asked input from other who plan to implement it. 

> stop you, sadly. But I wish it could.

Please keep your poison for yourself.

regards,
Nikos

---

From: Watson Ladd <[email-masked]>
Date: Thu, 10 Apr 2014 08:49:36 -0700

> It has no effect, because it is an ephemeral key exchange.

Not so: if I have a side channel that leaks to a local attacker,
ephemeral keys are just as vulnerable as long term keys.
Furthermore, Curve25519 can be used with long-term DH keys also.

> time, and outperforms all other implementations so far.

Of Curve25519? Do you have publicly verifiable benchmark data for this?
For P256 I'd be a little surprised: AGL and Shay Gureon have put a lot
of work into optimized assembler implementations.

> See the point above. I'd be interested to know how you figured that gmp

GMP works for \mathbb{Z} very well. But it can't ever skip a reduction
or a carry because you might ask it a question that requires it to
have an answer fully reduced in the next step.

If I know that I'm working modulo Z/pZ for some p, then I can pick
representatives in any ring with a morphism to Z/pZ. This extra
freedom can only help, never hurt.

> Please keep your poison for yourself.

"You" refers to everyone who wants to do this themselves. I wouldn't
implement it myself either.
The point is that all curves need to be treated by largely separate
code for the field arithmetic for the optimum in performance.

A byte swap is really not going to keep anyone from implementing
Curve25519: I see no reason to fight this holy war.

Sincerely,
Watson Ladd

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 10 Apr 2014 21:28:14 +0100

On 10/04/2014 09:22, Nikos Mavrogiannopoulos wrote:

> And how does this affect an ephemeral key exchange?

Assuming all side-channel attacks require repetition seems like the
kind of rather dangerous thinking that has bought TLS very unpleasant
surprises in the past. We've had quite enough of those already, I think.

Curve25519 was designed _specifically_ so that it can use a lovely,
extremely fast, constant-time Montgomery ladder: if you're not using
that, frankly, you're doing it wrong. (Section 5 of the draft already
addresses that, on my reading.)

> That's why I asked input from other who plan to implement it.

OK. Try _not_ to make your own implementation, especially not using a
generic bignum library: you'll both have side-channel problems, and
your performance will suck compared to the existing implementations.

Several liberally-licensed, extremely good, highly-optimised, correct
implementations of Curve25519 already exist: libsodium, for example.
They're probably better in every way than one you (or I) could write.

Practical implementation on most platforms in software therefore
pretty much consists of taking a good implementation; carefully
building scaffolding around it to plug it in; very thoroughly testing
that; and that's it.

This draft is, very simply, the standards part of that 'scaffolding'.

Given big-endian is the 'wrong way round' from what comes out of and
goes into literally every one of these implementations, it seems a bit
silly to ask basically everyone to byte-swap for no reason when we
could just... not.

That's why I say use the existing little-endian format. It's not a
holy war, it just feels utterly pragmatic in this case, just because
it's simpler that way.

Given bugs like Heartbleed, goto fail, the recent GnuTLS one (that
doesn't have a cute name as far as I know?), and doubtless, many more
to come - the simpler we can make that scaffolding, the less
opportunity there is overall to screw it up.

That's my take on it, anyway.

- -- 
/akr

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 11 Apr 2014 09:33:42 +0200

> surprises in the past. We've had quite enough of those already, I think.

Could you elaborate on how to achieve repetition on a protocol that runs
only once with the same key? I find your argumentation hard to follow.

> addresses that, on my reading.)

I never questioned that, it will be very appropriate when one can use it
with static keys (i.e., ECDH - which are not in this draft). My comment
is for the existing draft that uses the curve for an ephemeral key
exchange, and were directed to the overplay of the relevance of constant
time (as you do here) without understanding whether it is relevant for
the threats on the protocol under discussion. So to recap, being
constant time is a good thing, but not very relevant for ECDHE.

regards,
Nikos

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 11 Apr 2014 08:53:37 +0100

>only once with the same key? I find your argumentation hard to follow.

Perhaps you misunderstand. Naïvely assuming that every dangerous side-channel attack absolutely needs amplification via repetition is, I feel, optimistic (or, depending on your point of view, pessimistic).

(And if I ever develop such a one-shot attack, I shall name it something like #yolo, because cute attack names are in vogue.)

That's the kind of thinking that got us 20:20 hindsight gems like '[this timing attack] is not believed to be large enough to be exploitable'. Please let's be more careful.

Using good Curve25519 implementations gives us the opportunity to eliminate potential side-channels. Don't waste that opportunity.

- --
/akr

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 11 Apr 2014 10:04:59 +0200

> only once with the same key? I find your argumentation hard to follow.
I think Alyssa's point was not that you can achieve repetetion, but that
progress in the attacks may some day lead to powerful attacks that don't need
repetition at all.

How much information the attacker can get in one pass depends on many factors,
such as the attacker's abilities (noised timing only and real-time power trace
are very different settings) and the implementation techniques. With a naive
double-and-add algorithm (on a short Weierstrass curve, no using unified
formulas) and an attacker able to get a precise enough power trace, I don't
believe the attacker needs repetition to get the full ephemeral key.

Of course this is a fairly extreme example, but I think it shows side-channels
are not entirely irrelevant for ephemeral keys, at least in some contexts.

That said, I agree that side-channels are probably much less of a threat for
ephemeral keys than for long-term keys in most settings.

Manuel.