Subject: [TLS] Can we require extensions to be sorted?

From: Bill Cox <[email-masked]>
Date: Thu, 21 Apr 2016 05:26:21 -0700

We did this in QUIC, and it is a major simplification.  This is one feature
I will be sad to loose when we switch to TLS 1.3 for the crypto in QUIC.

I've worked on 3 extensions so far: EMS, channel ID, and token binding.  We
are not allowed to negotiate channel ID or token binding unless we also
have negotiated EMS.  If channel ID and token binding are both offered by
the client, the best behavior is for servers supporting both is to pick
token binding.  Since token binding can be implemented as a custom
extension, in current implementations it is negotiated after builtin
extensions, but I cannot count on that when using the custom extension API.

The logic required to deal with inter-extension dependencies is now so
complex that TLS implementations are forced to pre-parse extensions, adding
even more complexity and latency.  Even so, that only lets extensions know
that the others exist when processed (such as EMS when processing token
binding), but it does not ensure that one extension has successfully been
negotiated before processing another.

This is a mess.  Is it too late to modify the TLS 1.3 spec to require
extensions to be sent in order of their tags?

If we were to do so, I would recommend that we use a bit-reversal pattern
for numbering official extensions when the order makes no difference, and
when they do, put them in the middle between existing extensions.  Some
extensions, like token binding, are intended to be lightweight extensions
that can be supported through a custom extension API.  Such extensions
should always come after the more complex builtin extensions, because
built-in extensions are often processed in switch statements, while custom
extensions have to be handled separately.  It is most natural for these
extensions to be parsed after builtin extensions, so maybe they should
start with a 1, and builtin extensions should start with a 0.

For example, if we had EXT1, EXT2, and EXT3 as official extensions with no
specific ordering needs, and EXT1-2 that needs to come after EXT1, but was
defined after EXT3, and TESTEXT2-1 that is still unofficial, but must come
after EXT2, and CUSTEXT1 and CUSTEXT2, the tags might look like (in order
of when they were defined):

EXT1: 0
EXT2: 0x4000
EXT3: 0x2000
EXT1-2: 0x1000
TESTEXT2-1: 0x60a5
CUSTEXT1: 0x8000
CUSTEXT2: 0xc000

The 0x608a5 starts with 0x60 for ordering half way between 0x4000 and
0x8000, and has a random odd lower byte, 0xa5, to reduce accidental
collisions between TLS implementations that happen to be experimenting with
test extensions.  The custom extensions follow a bit-reversal pattern in
the range where the MSB is set.

I'm not confident that we need to differentiate custom extensions here.
QUIC does not.  If we do, to help clarify the custom extension concept,
these are extensions that:

1) can be processed with two callbacks: one for adding, one for parsing
(which are different on client vs server)
2) do not keep any state between resumes, and are renegotiated
3) can be processed after builtin extensions

The issue of extensions requiring state between resumes confuses me, so
I'll send a separate email for help understanding it.

Bill

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 21 Apr 2016 16:39:41 +0200

I wouldn't object in general to requiring sorting, but...

1. I wouldn't want to renumber existing extensions.
2. Servers badly handle some extension orderings (e.g., an empty extension
at the end)

So we would need to stay withing these guiderails.

-Ekr

On Thu, Apr 21, 2016 at 2:26 PM, Bill Cox <[email-masked]> wrote:

> We did this in QUIC, and it is a major simplification.  This is one
> feature I will be sad to loose when we switch to TLS 1.3 for the crypto in
> QUIC.
>
> I've worked on 3 extensions so far: EMS, channel ID, and token binding.
> We are not allowed to negotiate channel ID or token binding unless we also
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>

---

From: Hubert Kario <[email-masked]>
Date: Thu, 21 Apr 2016 17:24:30 +0200

On Thursday 21 April 2016 05:26:21 Bill Cox wrote:
> feature I will be sad to loose when we switch to TLS 1.3 for the
> crypto in QUIC.
> 
> I've worked on 3 extensions so far: EMS, channel ID, and token
> binding.  We are not allowed to negotiate channel ID or token binding
> unless we also have negotiated EMS.  If channel ID and token binding
> are both offered by the client, the best behavior is for servers
> supporting both is to pick token binding.  Since token binding can be
> implemented as a custom extension, in current implementations it is
> negotiated after builtin extensions, but I cannot count on that when
> using the custom extension API.
> 
> complex that TLS implementations are forced to pre-parse extensions,
> adding even more complexity and latency.  Even so, that only lets
> extensions know that the others exist when processed (such as EMS
> when processing token binding), but it does not ensure that one
> extension has successfully been negotiated before processing another.

I don't follow.

If you understand given extension, you must reject Client Hello if that 
extension is malformed.

If one extension depends on other extension, you just need to check if 
it is present.
 
I don't see how single array lookup is overly complex, to the point that 
we need to assign new IDs to existing extensions.
-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

---

From: Andrei Popov <[email-masked]>
Date: Thu, 21 Apr 2016 17:50:40 +0000

Ø  The logic required to deal with inter-extension dependencies is now so complex that TLS implementations are forced to pre-parse extensions, adding even more complexity and latency.
I agree about the complexity. TLS extensions are essentially sub-protocols that define their own messages, and they can be inter-dependent. I’ve also seen people confused by the fact that certain “extensions” are actually necessary to implement.

Ø  Is it too late to modify the TLS 1.3 spec to require extensions to be sent in order of their tags?
I’m not sure this would help. Some extensions have the client advertising options and the server picking them; others do the reverse. The moment in the handshake where the extension can be considered “negotiated” differs per extension.

In other words, the order in which extensions are presented in the ClientHello\ServerHello so far has been the least of my problems. Figuring out which extensions to send and respond to, maximizing the chance of successful handshake, can be tricky. And then there are interop-driven rules, e.g. “never send empty extensions at the end”☺.

Cheers,

Andrei

From: TLS [mailto:[email-masked]] On Behalf Of Bill Cox
Sent: Thursday, April 21, 2016 5:26 AM
To: [email-masked]
Subject: [TLS] Can we require extensions to be sorted?

We did this in QUIC, and it is a major simplification.  This is one feature I will be sad to loose when we switch to TLS 1.3 for the crypto in QUIC.

I've worked on 3 extensions so far: EMS, channel ID, and token binding.  We are not allowed to negotiate channel ID or token binding unless we also have negotiated EMS.  If channel ID and token binding are both offered by the client, the best behavior is for servers supporting both is to pick token binding.  Since token binding can be implemented as a custom extension, in current implementations it is negotiated after builtin extensions, but I cannot count on that when using the custom extension API.

The logic required to deal with inter-extension dependencies is now so complex that TLS implementations are forced to pre-parse extensions, adding even more complexity and latency.  Even so, that only lets extensions know that the others exist when processed (such as EMS when processing token binding), but it does not ensure that one extension has successfully been negotiated before processing another.

This is a mess.  Is it too late to modify the TLS 1.3 spec to require extensions to be sent in order of their tags?

If we were to do so, I would recommend that we use a bit-reversal pattern for numbering official extensions when the order makes no difference, and when they do, put them in the middle between existing extensions.  Some extensions, like token binding, are intended to be lightweight extensions that can be supported through a custom extension API.  Such extensions should always come after the more complex builtin extensions, because built-in extensions are often processed in switch statements, while custom extensions have to be handled separately.  It is most natural for these extensions to be parsed after builtin extensions, so maybe they should start with a 1, and builtin extensions should start with a 0.

For example, if we had EXT1, EXT2, and EXT3 as official extensions with no specific ordering needs, and EXT1-2 that needs to come after EXT1, but was defined after EXT3, and TESTEXT2-1 that is still unofficial, but must come after EXT2, and CUSTEXT1 and CUSTEXT2, the tags might look like (in order of when they were defined):

EXT1: 0
EXT2: 0x4000
EXT3: 0x2000
EXT1-2: 0x1000
TESTEXT2-1: 0x60a5
CUSTEXT1: 0x8000
CUSTEXT2: 0xc000

The 0x608a5 starts with 0x60 for ordering half way between 0x4000 and 0x8000, and has a random odd lower byte, 0xa5, to reduce accidental collisions between TLS implementations that happen to be experimenting with test extensions.  The custom extensions follow a bit-reversal pattern in the range where the MSB is set.

I'm not confident that we need to differentiate custom extensions here.  QUIC does not.  If we do, to help clarify the custom extension concept, these are extensions that:

1) can be processed with two callbacks: one for adding, one for parsing (which are different on client vs server)
2) do not keep any state between resumes, and are renegotiated
3) can be processed after builtin extensions

The issue of extensions requiring state between resumes confuses me, so I'll send a separate email for help understanding it.

Bill

---

From: Watson Ladd <[email-masked]>
Date: Thu, 21 Apr 2016 10:53:04 -0700

>> extension has successfully been negotiated before processing another.

Oh nyo! Shotgun parsing doesn't work: I might actually have to write a real
parser like Sergey Bratus is always on about. Maybe I'll even ensure that
the input is well-formed, so I don't blindly go ahead and copy more to the
output then was actually there. If only there was a 50 year old book to
tell me how to write parsers.

> we need to assign new IDs to existing extensions.

If we really want a simpler TLS, let's switch to QUIC.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.