Subject: [TLS] Refactoring client auth/re-key

From: Eric Rescorla <[email-masked]>
Date: Sat, 18 Oct 2014 15:32:20 +0100

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.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 18 Oct 2014 08:15:19 -0700

On Sat, Oct 18, 2014 at 7:32 AM, Eric Rescorla <[email-masked]> wrote:
So I seem to remember DJB telling me that once you have a properly
made channel via Diffie-Hellman, that authenticating requires just
signing a value derived from the key. (Sadly I forgot/don't know the
proof, so someone will have to check this or tell me I'm completely
wrong) So we don't need the session hash to include the certificates,
and so don't need to keep the running hash going past the first
exchange.

Concretely the idea would be as follows: A sends to B g^x, and B
responds with g^y. Both calculate MS=H(g^xy, g^x, g^y). (Of course, we
need to hash the actual messages.)

At this point we can compute channel_AtoB_key=PRF(MS, "channel AtoB
key"),  channel_BtoA_key=PRF(MS, "channel BtoA key"),
A_authstr=PRF(MS, "A authstr"), B_authstr=PRF(MS, "B authstr"). The
channel keys can be used to encrypt each side as in the proposal, and
the authstrs can be signed and sent over the channel to provide a
proof of identity. Furthermore, we could extract a channel binding in
an analogous manner, or application level keys in the same way, or a
resumption key in the same way.

Because we run the rest of the exchange over an encrypted,
authenticated channel, message manipulation isn't as much of an issue,
so the updates don't need to include the hashes they do above.

This seems to me to remove a lot of complexity in your proposal,
without affecting security. It also gets closer to generic security:
any authentication mechanism that uses a fresh value can use
A_authstr. Any means of providing a secure channel with a shared
string can use the keys, etc.

Sincerely,
Watson Ladd

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 18 Oct 2014 17:10:59 +0100

Watson,

Thanks for your comments.

On Sat, Oct 18, 2014 at 4:15 PM, Watson Ladd <[email-masked]> wrote:

> proof of identity.

Trying to think through this a bit, is this a generic comment on the
session-hash proposal even for TLS 1.2 where they are careful to
sign everything up to CertificateVerify? See:

https://tools.ietf.org/html/draft-ietf-tls-session-hash-02#section-4.1

Perhaps one of the authors of that document can weigh in here.

Best,
-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 18 Oct 2014 20:46:55 +0300

> and so don't need to keep the running hash going past the first

AFAIK, It is sufficient (dunno if DJB told that).

The idea is: Ensure that keys are unique, even in face of active
attack, and only the (true) endpoints can compute those.

This can be done by hashing in transcript of negotiation and key
exchange into keys obtained from DH.

This causes the following:
- If attacker does not tamper with key exchange, the session key
  becomes unknowable.
- If attacker does tamper with key exchange, the two sides will not
  agree about keys (since keys are unique), and later channel
  authentication will fail.
- Attacker can't replay captured credentials, because keys will
  then be different from anything seen so far (uniqueness).

There's a subtle trap here tho: The authentication messages have to be
exchanged via the channel itself, not out-of-band. Otherwise the
authentication is broken. Not much of an issue here.

> need to hash the actual messages.)

That doesn't quite work (why?) :-)

Hint: What's missing (and it is not "certificate")?

> resumption key in the same way.

One subtle decision: Is there a split beween "system" (TLS uses
internally) and "user" keys (handed to application via TLS-EXTRACTOR).

One could imagine that with some of the proposals about fixing key
deriviation, some would want that.

Also, if there is no finished with nontrivial data, one would need
to derive a fake binding value for backward compatiblity (but that's
easy to do).

Also, due to some signature schemes having some real-world nonideal
properties, one wants to also throw the keys used into the message
(easiest way is to throw the whole certificate or hash thereof in).

Also, do client signatures need replay protection (prevents replaying
te same certificate in the same connection)?

Also, could be useful to have some sort of "label" along with client
certificate that gets notified along with the certificate to the
application.

The idea is that TLS would not process the client certificates more
than just validating the signature. Instead, if validation succeeds,
it would fire callback to application, reporting that certificate with
label X and contets Y has been successfully validated.

Then the application could calculate what to do with the certificate
and have latter communications refer to the certificate.

This is AFAIK needed with some applications (along with some more app-
level signaling) to use client authentication safely.

-Ilari

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sat, 18 Oct 2014 20:18:30 +0200

>                                  ClientHello.random + ServerHello.random)
When you write "ClientHello.random + ServerHello.random", don't you rather mean
"transcript so far"?

Manuel.

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 18 Oct 2014 19:45:12 +0100

> When you write "ClientHello.random + ServerHello.random", don't you rather

Good catch. I do indeed.

Thanks,
-Ekr

---

From: Watson Ladd <[email-masked]>
Date: Sat, 18 Oct 2014 14:55:59 -0700

> https://tools.ietf.org/html/draft-ietf-tls-session-hash-02#section-4.1

That struck me as an implementation driven decision, since
implementations keep a running hash for the Finished message, which is
repurposed in the session hash proposal. Furthermore, what I  proposed
only works because we are sending the identities over a secure
channel: otherwise an attacker could remove the client authentication
and replace it with their own, thus causing both sides to disagree
over what the authentication status is.

The session hash was designed to be as minor a change as possible to
TLS 1.2. I've got no interest in mixing security improvements with
massive changes, as that slows adoption big time. While you could make
a similar change to TLS 1.2, it would be unnecessarily large.

My only other comment is that this is a much larger change than
1.1->1.2. Perhaps we really should be honest and call it TLS 2.0.

Sincerely,
Watson Ladd

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

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Sun, 19 Oct 2014 08:57:25 +0200

> and so don't need to keep the running hash going past the first

At least one form of this construction (as used in IKEv2) is well-explained 
and proved in the original SIGMA paper:
http://www.iacr.org/cryptodb/data/paper.php?pubkey=1495

> sign everything up to CertificateVerify? See:

As Ilari hints, it is not enough to hash the client-server key shares into
the master secret. In a negotiated protocol like TLS, we need to add
the DH parameters, the algorithms used to derive the keys, and the
algorithms that the resulting key will be used with. (The crypto proofs
typically fix these values and so they don’t necessarily appear in the
academic protocols.)

For session hash in TLS 1.2, the log up to ClientKeyExchange contains
all this data, and we need to hash at least the Hellos and the KeyExchanges.
So even if the client and server are anonymous the session hash context binds the master secret.

One may argue that the client and server authenticated identities (Certificates) do not
need to be included in the session hash. This would be true for the initial handshake,
but not for resumption. One use of the TLS 1.2 master secret is as a key for session
resumption, and the Triple Handshake attack relies on the master secret not being
bound to the peer’s identity. 

For TLS 1.3, I need to stare about the Update protocol a bit more, but I think authentication
after an initial DH handshake could be made safe (a la SSH and IKEv2). That is,
the first master secret hashes the keyshares, and the second master secret/connection key
hashes in the identities. 

The question that bothers me is which key/master secret would we use for session resumption? If it is the initial (unauthenticated) master secret, I think there will be attacks. 
If we only allow the last (authenticated) master secret to be resumed, we would probably
recover the guarantees of session hash. 

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 19 Oct 2014 11:15:52 +0300

On Sun, Oct 19, 2014 at 08:57:25AM +0200, Karthikeyan Bhargavan wrote:
> 
> One may argue that the client and server authenticated identities
> (Certificates) do not need to be included in the session hash. This
> would be true for the initial handshake, but not for resumption. One
> use of the TLS 1.2 master secret is as a key for session resumption,
> and the Triple Handshake attack relies on the master secret not being

I think this is just wrong. And if it was true, you would have much
much worse problems.

- To defeat the renego fix, you need finished collision.
- To get finished collision, you need MS collision.
- MS collision is already damaging in itself.

If kex is passive-attack secure, MS hashes in kex parameters, exchange
keys, nonces (only needs to be unique across exchange key
offered) and kex result: Then MS collision impiles that kex
parameters, exchange keys and nonces are the same (kex result will be
the same too).

But since kex is passive-attack secure, MS will be unknowable for the
attacker, and any tampering will make handshake fail.

Now, for non-PFS key exchanges, certificates can contain exchange keys.
In practicular, RSA kex server certs do contain exchange key. And
thus under "hash exchange keys", you need to hash it.

In fact, one wants slightly stronger property: Each and every full
handshake computes a fresh MS never before seen, even if peer is
maliscous. But hashing the stuff listed above is sufficient for that,
because each (exchange key, nonce) pair from honest peers will be
unique, forcing the MS computed by those to be different (what
MS maliscous endpoints compute is no consideration).

The reason why one wants to also hash the crypto negotiation is to
avoid downgrade attacks.

-Ilari

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Sun, 19 Oct 2014 11:58:04 +0200

> thus under "hash exchange keys", you need to hash it.

You’re right, including the peer identity applies mainly for non-PFS exchanges where
the peer’s keycard is closely linked to its identity (RSA, PSK, and Fixed DH/ECDH) 
For DHE/ECDHE, if the client/server negotiate a known good group/curve, agreeing
upon the DH params should be enough. Since, by default, the server can choose an
arbitrary group, it seems prudent to include its identity.

---

From: Martin Thomson <[email-masked]>
Date: Sun, 19 Oct 2014 10:09:31 -0700

> typically fix these values and so they don’t necessarily appear in the

And it's not just that there are multiple options of algorithm.
Because there is choice involved, you need to include all the options
that were available.  Otherwise, clients are exposed to the
possibility of downgrade.

Hence the simplification of including the entire transcript still.

---

From: Martin Thomson <[email-masked]>
Date: Sun, 19 Oct 2014 10:15:42 -0700

> arbitrary group, it seems prudent to include its identity.

I'm glad someone pointed that out; I've been meaning to.  The
session-hash draft talks about binding to identities, but that isn't
the important characteristic.

The important characteristic is that the master secret is bound to
information that can only be known to the communicating peers.  In the
non-ephemeral (legacy) mode, that means identity, but that's only
consequential.

Maybe this sentence needs to be revised:
   The Transport Layer Security (TLS) master secret is not
   cryptographically bound to important session parameters such as the
   client and server identities.