Subject: [TLS] Closing on keys used for handshake and data messages

From: Joseph Salowey <[email-masked]>
Date: Fri, 3 Jun 2016 14:54:53 -0700

We still have a significant outstanding TLS 1.3 issue affecting involving
which key to use for handshake and data records.  Antoine Delignat-Lavaud,
Bjoern Tackmann, Cas Cremers, Eric Rescorla, Felix Guenther and Markulf
Kohlweiss put together a summary of the issue which is included below.  We
need to close on an approach to this issue so we can begin a final
cryptographic review of the protocol.  The plan is to have discussion of
this issue for a week after which the chairs will start a week consensus
call based on this discussion.  After the chairs judge consensus, the
author will produce a draft reflecting the consensus that can go out for
review by the cryptographic community.

Thanks,

J&S

BACKGROUND

TLS 1.3 currently encrypts post-handshake handshake messages
(NewSessionTicket, KeyUpdate, and post-handshake client authentication)
with the application traffic keys. This makes it hard to do certain kinds
of proofs, particularly cryptographic style proofs that make statements
about the entire handshake (including encrypted post-handshake messages)
being composable with application traffic. These proofs rely on having
separate keys for these handshake-type messages and the application
traffic.

Unfortunately, the TLS record framing is not easily compatible with having
multiple keys used simultaneously: because we encrypt the content type, it
is not possible to use it to determine which key to use to decrypt. We
examined a number of proposals which would allow you to simultaneously have
encrypted content types and separate keys, but they all appear to be
nonviable for one reason or another:

   -

   Trial decryption has serious implementation problems
   -

   Double-encrypting handshake messages in both the handshake key and the
   application key does not actually provide the required key separation
   -

   Separately encrypting the content type is inefficient in a number of
   ways, especially for DTLS (and would need separate security analysis). This
   is probably the most viable of the “try to get both” designs.

This leaves us with two primary alternatives:

   1.

   Use the same key (as in the current draft-13)
   2.

   Restore a public content type and different keys

I discuss these in a bit more detail below

USE THE SAME KEY

As stated above, using the same key for handshake and application traffic
precludes certain types of proof. However, this is not to say that either
it is insecure to use the same key or that no proof is possible.
Specifically:

   -

   Using the same key is not an obstacle for symbolic proof methodologies.
   -

   In particular, if one is willing to restrict the proof of the handshake
   to the original handshake messages, then TLS 1.3 still provides key
   separation.
   -

   Hugo Krawczyk has a forthcoming paper which demonstrates the security of
   the current keying model using cryptographic techniques in a “secure
   channels” model. Also, the miTLS proof of TLS 1.3 does not rely on
   separation, as it considers the record protocol together with the handshake.

Nevertheless, there was broad and strong agreement at TRON that key
separation considerably simplifies cryptographic proofs in the
computational model by enabling modular analysis of handshake encryption
and the record protocol. The motivation for switching keys from handshake
to application traffic is somewhat undermined by late handshake messages
being encrypted under the application traffic key. This can be viewed as a
design compromise that breaks the separation principle for post-handshake
messages while still incurring some of the overhead of separate keys in the
handshake.

PUBLIC CONTENT TYPES

Clearly, having a public content type and separate keys for handshake and
application data provides full key separation, at the cost of revealing
whether a given record is handshake or application data (and potentially
alerts). The major question that the group had was whether it was actually
possible to conceal this information effectively, even with encrypted
content types, since hiding the handshake messages in the application
traffic requires detailed knowledge about the application traffic pattern
(e.g., packet lengths, timing, response patterns, etc.). It’s clear some
analysis of this is needed.

In addition, changing to public content types would potentially necessitate
changes to the packet format: the current record design uses the fact that
the content type is nonzero to overload it as a padding delimiter, and if
we were to add a public content type, we would either need to duplicate the
content type in both locations or remove the inner content type and find
some new way to make the padding unambiguous. Note that because we already
have a dummy content type, even having two copies would not make the packet
longer currently, though we are hoping to eventually remove the external
content type, in which case we might end up having the record not shrink by
as much as one might like [0].

[0] There are probably designs that would actually let us keep the minimal
packet size if we were willing to break the format on the wire. One
potential design would be to retain the inner encrypted content type but
rob a bit from the length (which currently has the first bit always set to
low) to indicate which key is in use.

---

From: Dave Garrett <[email-masked]>
Date: Sat, 4 Jun 2016 02:26:00 -0400

On Friday, June 03, 2016 05:54:53 pm Joseph Salowey wrote:
>    - Trial decryption has serious implementation problems
>    - Double-encrypting handshake messages in both the handshake key and the
>    - Separately encrypting the content type is inefficient in a number of

Could someone please elaborate on why nested encryption would be a problem? No objection to avoiding trial decryption, though.

The general expectation I would have for doing double encryption here would be to encrypt TLSCiphertext normally with the application traffic key and TLSCiphertext.content would be the real unencrypted length plus an aead-ciphered struct of the message which is encrypted with the relevant key. (the unencrypted length would be the inner encrypted block's length, in this scenario)

Dave

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 4 Jun 2016 12:51:11 +0300

On Sat, Jun 04, 2016 at 02:26:00AM -0400, Dave Garrett wrote:
> Could someone please elaborate on why nested encryption would be a
> problem?

The problem is that nested encryption does not solve the separation
problem (application misusing keys it has[1] in ways that interact
badly with the (late) handshake[2]).

Essentially the difference is "the generated key is safe to use with
any protocol" versus "the generated key is safe to use for TLS 1.3".

And if the first is not true, proving the second is harder (even if
it should be true, barring massive design errors[3] or applications
doing utterly crazy stuff[4]).

[1] Nevermind it REALLY SHOULD NOT actually have those keys, but only
plaintext access to its own mux stream.

[2] In normal TLS operation, the protocol mux/demux prevents such
interference from actually occuring.

[3] Like grossly broken protocol mux.

[4] Stuff applications have absolutely no legimate business of doing
(if I ever see such things, my first assumption about the cause will
be malice).

-Ilari

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 09 Jun 2016 17:56:37 -0400

>    is probably the most viable of the “try to get both” designs.

I'm saddened by this analysis :( I understand that trial decryption
precludes inplace decryption, and i can see why that makes it a
non-starter for some implementations.

I confess i was hoping that double-encrypting would provide some measure
of useful key separation for cryptanalysis.  I don't think i understand
Ilari's explanation in this thread, though, so i'd appreciate any other
attempts to clarify.

>    1. Use the same key (as in the current draft-13)
>    2. Restore a public content type and different keys

Between these two options, I strongly prefer option 1.

> analysis of this is needed.

We know that traffic analysis is difficult, and may in some cases be
impossible.  This is an area in need of active research.  However,
deciding to make it *always* impossible to protect because we don't know
how to protect it absolutely is "security nihilism", and i hoped we were
moving beyond that mindset as a community.

If we don't have a mechanism to hide this metadata, then we certainly
won't develop any useful practice around actually making it
indistinguishable.  Protecting users is a multidimensional problem.  We
should provide a mechanism to make this information indistinguishable in
the axis we know how to handle (encrypting the material itself) so that
there is a reason for people to work on the axes we don't yet know how
to handle (protecting against traffic analysis).

      --dkg

---

From: Björn Tackmann <[email-masked]>
Date: Tue, 14 Jun 2016 11:18:14 +0200

Hi dkg,

sorry for my late response.

Let me start by saying that I do not believe that this is really critical; after all, we can prove alternative (1) as well — it’s just less clean and makes the proofs harder to write, read, and verify, which is generally not a good thing for a cryptographic protocol. On the other hand, the privacy improvements offered by alternative (2) appear to be rather moderate; even if we were to realistically achieve the best privacy it could offer, it would protect the fact that a “new session ticket” message (is this a gain at all?) or a client auth message was sent. If I understood correctly, client auth has not been widely used in previous TLS versions, and even if this would change, it’s not quite clear how big the gain is. Maybe you have more precise insights into this than I do?

> On Jun 9, 2016, at 11:56 PM, Daniel Kahn Gillmor <[email-masked]> wrote:
> 

Double encryption is not problematic. It just does not have advantages over alternative (1) in terms of cryptographic analysis (it does not quite help in modularizing the proofs). On the other hand, we’ve heard (others may want to chime in) that it /does/ make the implementation more cumbersome, in the sense that it requires more changes to the existing code base.

In that sense, it appears to be strictly dominated by alternative (1).

> moving beyond that mindset as a community.

I beg to disagree here.

First, we would not drop it for no reason whatsoever. We would drop it because dropping it has other advantages. It’s a trade-off.
Second, we should in any case carefully point out that this mechanism alone, i.e., without proper padding etc., may not provide any additional privacy guarantees. A security mechanism that does not work can be worse than no mechanism at all if people start relying on it without understanding what it achieves.

Introducing a mechanism without analyzing it is somewhat akin to what happened to encryption with compression. (Used properly, it can be useful.) I hoped we were moving beyond that mindset — sorry for echoing ;-)

> to handle (protecting against traffic analysis).

I’m totally in for protecting user privacy. I simply believe that we should first specify what we want, then see whether we can achieve it, and then build the mechanism that does it.

Cheers,
Bjoern

--
Björn Tackmann
Postdoctoral Research Scholar
Computer Science & Engineering, UC San Diego

---

From: Douglas Stebila <[email-masked]>
Date: Wed, 15 Jun 2016 15:38:42 -0400

On Jun 3, 2016, at 17:54, Joseph Salowey <[email-masked]> wrote:
> 
> Unfortunately, the TLS record framing is not easily compatible with having multiple keys used simultaneously: because we encrypt the content type, it is not possible to use it to determine which key to use to decrypt. We examined a number of proposals which would allow you to simultaneously have encrypted content types and separate keys, but they all appear to be nonviable for one reason or another:

[...]

> 	• Separately encrypting the content type is inefficient in a number of ways, especially for DTLS (and would need separate security analysis). This is probably the most viable of the “try to get both” designs.

I'd also like more information about the reasoning behind saying that separately encrypting the content type is inefficient.  

There was some discussion off-list (but not much) about a proposal to encrypt content type (handshake or application) with a separate key, then encrypting data with the corresponding key (handshake key or application key).  The content type would be encrypted using unauthenticated encryption, resulting in a single byte of ciphertext.  The authenticated encryption using the corresponding key would include the type as associated data to authenticate it.  

This had a few drawbacks as I remember it: 
1) requires one additional byte in the communication; 
2) requires deriving and keeping an extra key (the "content type key") around;
3) requires additional encryption/decryption
4) composability of the application key would still be lost because of post-handshake client authentication.

In the off-list discussion, Eric had a potential solution to (1).  (3) was unavoidable but in my opinion relatively minimal cost.  (4) is true, but we now have Hugo's results that give a form of restricted composability that accommodate post-handshake client authentication.  

There may have been additional discussions that I wasn't around for.  I have heard it suggested that (2) is the particularly problematic aspect for DTLS, but I do not know enough about DTLS to understand this.  Even if it is problematic for DTLS, if it is not so problematic for TLS, then why not do it for at least TLS?  

Douglas