[TLS] Refactoring client auth/re-key

[Eric Rescorla <[e-mail]>]

Folks,

What follows is a drafty proposal for tackling a number of different
desiderata for 1.3 while also simplifying much of the protocol
analysis. The following integrates a bunch of separate discussions
starting with the YYZ interim and ideas from Adam Langley, Alfredo
Pironti, Andrei Popov, Martin Thomson and others.

The idea here is to unify:

 1. Session hash.
 2. Key refresh (based on MT's proposal from YYZ)
 3. Client authentication

As background, the current handshake looks like this.

       ClientHello
       ClientKeyShare            -------->
                                                       ServerHello
                                                    ServerKeyShare
                                                [ChangeCipherSpec]
                                              EncryptedExtensions*
                                                      Certificate*
                                               CertificateRequest*
                                                CertificateVerify*
                                 <--------                Finished
       [ChangeCipherSpec]
       Certificate*
       CertificateVerify*
       Finished                  -------->


Now that we are adopting session-hash, we want to use it for TLS 1.3
as well, but a straight adaptation is inconvenient because:

1.  We have moved encryption up so we need to generate the keys
    before we have either cert, but we then can't incorporate
    them into the session hash.

2.  We want the server to be able to send data in his first flight
    if he doesn't care about client auth.

In addition, there are a couple of other pieces of which would be nice:

3.  Be able to add client auth at any part of the handshake.

4.  Be able to regenerate the traffic keys now that we have
    removed renegotiation.

These last two are the major purposes served by renegotiation.


We could try to address each of these individually, but taking a look
at this, it seems like we could solve a number of these problems
together by pulling client auth out of the main handshake and into a
followon protocol (see below). This would leave us with a single,
uniform, handshake whether client auth is being used or not.


       ClientHello
       ClientKeyShare            -------->
                                                       ServerHello
                                                    ServerKeyShare  <-- A
                                              EncryptedExtensions*
                                                      Certificate*
                                                CertificateVerify*
                                 <--------                Finished  <-- B
       Finished                  -------->

This would integrate with session-hash as follows:

- At point A we would generate one set of keys based on the MS and the
  transcript so far. Those keys would be used to encipher the rest of
  the handshake.

- At point B we would generate a new set of keys based on the MS and
  the transcript so far. Those keys would be used to encipher the
  traffic and the Finished messages. [0]


REKEY
Of course, we now need to have rekeying and client auth. I propose to
merge those into a single mechanism called Update. For simplicity,
let's consider Update without client auth first.

  enum { rekey(1), ack(2),  authentication(3), (255) } UpdateType;
  struct {
    UpdateType update_type;

    switch (update_type) {
      case rekey:
        Random random;

      case ack:
        opaque digest<0..255>;  /* Based on the PRF */

      ...
    }
  } Update;

In order to force a re-key, an implementation sends an Update message
with a random nonce. It then digests the existing traffic keys in the
sending direction with the Update contents (see below). The other side
must respond with an UpdateAck which includes a digest of the Update
message, computed using the PRF and similarly digests its update
message with its sending keys. The result is that the sending keys in
both directions now depend on the entire sequence of Update messages
that have been sent.



KEY SCHEDULE
There are a lot of different things we could do for the key schedule
but it's useful to have a concrete proposal, so consider the following.

Currently TLS has a single Master Secret which is used to compute
directional traffic keys. Instead, we should have two unidirectional
MSs, each initially generated from the initial PMS. E.g.,

      master_secret_client = PRF(pre_master_secret, "master secret_client",
                                 ClientHello.random + ServerHello.random)
                                 [0..47];

      master_secret_server = PRF(pre_master_secret, "master secret_server",
                                 ClientHello.random + ServerHello.random)
                                 [0..47];

Every time an Update is sent by element X, we recompute master_secret_X,
as follows:

      master_secret_X_{i+1} = PRF(master_secret_X_i, "master_secret_update",
                                  Update_message)

We then recompute the traffic keys based on the current master secret. This
produces the following pattern in each direction:

                       X           Y
                       |           |
                       v           v

      PMS -->    MS_0 --->  MS_1 ---> MS_2 --->  ...
                  |          |         |
                  v          v         v
               Traffic    Traffic   Traffic
                Keys 0     Keys 1    Keys 1

As should be clear, once MS_{i+1} has been computed from MS_{i} we can
discard MS_{i}. This provides a form of protection for the previous traffic,
since if you compromise either side at (for instance) the point labelled Y,
then it's not possible to decrypt traffic sent at X, since you would need
MS_0 or TK_0, but these can have been discarded at this point, and since
the PRF is nominally one-way, you can't compute MS_{i} from MS_{i+1}. [1]


SIMULTANEOUS UPDATE
It's obviously possible that both sides will try to update at once.
That shouldn't be a problem here since the order of the Updates and hence
key changes is deterministic on both sides. For example:


           Client                                   Server
[C_MS_0]                                                     [S_MS_0]
           Update (A) ------------------------>
[C_MS_1]
                      <------------------------  Update (B)
                                                             [S_MS_1]
                      <------------------------     ACK (C)
                                                             [S_MS_2]
           ACK (D)    ------------------------>
[C_MS_2]


The key computations are as follows:

C_MS_1 = PRF(C_MS_0, A)
S_MS_1 = PRF(S_MS_0, B)
C_MS_2 = PRF(C_MS_1, D) [D depends only on B]
S_MS_2 = PRF(S_MS_1, C) [C depends only on A, but S_MS_2 depends
                         on S_MS_1 which depends on B].

Note: the above needs double-checking since I haven't coded it up and
it's possible there's some way to get confused. The important property
we are trying to have is that we don't need to worry about which of
two messages that cross in flight was sent first.


CLIENT AUTH
We can easily extend this mechanism to allow client auth (as well as
adding keys to the server, I suppose) by allowing the Update message
to contain a Certificate and CertificateVerify. I.e.,

  enum { rekey(1), ack(2),  authentication(3), (255) } UpdateType;
  struct {
    UpdateType update_type;

    switch (update_type) {
      case rekey:
        Random random;

      case ack:
        opaque digest<0..255>;  /* Based on the PRF */

      case authentication:
        Certificate certificate;
        CertificateVerify verify;
    }
  } Update;

Note: it might be nice to always have the Random value.

One open issue is what the CertificateVerify should cover. Probably
what's most convenient is to maintain a running hash of the initial
transcript plus every Update that has been sent in the forward
direction. Note that we don't want to include Updates sent in the
reverse direction, since that would create race conditions where
it's not clear if a CertificateVerify from the client covers
an Update sent at approximately the same time from the server.

Note that this causes the simultaneous update (above) to result in
S_MS_2 to depend on Update(B).  Though B is part of a different update
exchange, it appears before C in the transcript (and they are sent by
the same side) and is therefore covered by the hash used in the
certificate verify

Important note: I've removed CertificateRequest entirely. As Andrei
Popov has pointed out, it's (a) complicated and (b) insufficiently
flexible. The idea here is to push this up to the application layer
where we can be more expressive and avoid the clunky CR syntax we have
now. It is also obviously possible for the client to unilaterally
offer client auth or the server to unilaterally add a new server
certificate [This last may be regarded as a bug or a feature.]

-Ekr

[0] One could also imagine using the original keys to encipher
the Finished message, or generating yet more keys. When Alfredo
and I discussed this, he didn't think this affected the proof, so
I've proposed the simplest option.

[1] Note that this doesn't address the question of resumption. If we
retain resumption, we need to keep a secret which can be used for
resumption. It's easy to make it distinct from the C_MS_0 and C_MS_1
generated in the full handshake by generating a third independent
resumption secret R_MS from the initial PMS. This would be used for
resumed connections; obviously this means that if you recover R_MS
you can attack all the resumed connections but not the original
connecn. We could probably invent some techniques for keeping
those connections, but it's hard to do without keeping state on
the server.