Subject: [TLS] Ephemeral key exchange in TLS Snap Start (was RE: TLS Snap Start)

From: "Brian Smith" <[email-masked]>
Date: Mon, 5 Jul 2010 12:58:33 -0500

Adam Langley wrote:
> I've just submitted a draft for TLS Snap Start: 0-RTT handshakes for TLS
> 
> http://www.ietf.org/id/draft-agl-tls-snapstart-00.txt
> http://www.imperialviolet.org/binary/draft-agl-tls-snapstart-00.html

I don't see the need to support implementations that don't do OCSP stapling.
Who is going to care enough about performance to go through the
*substantial* effort to implement this extension correctly, but not
implement OCSP stapling? And, if both sides implement OCSP stapling, then
each connection will either be a full non-snap-start handshake (with a
stapled OCSP), a normal session resumption, or a snap start session
resumption--and never a snap-start full handshake.

If snap start were reformulated to work just for session resumptions, then
the client could generate a keyblock using:

        PRF(SecurityParameters.master_secret, "key expansion",
client_random)

Then, the client could use that keyblock to create a single-use write cipher
spec, write the TLSCiphertext record into ClientSnapStart using that cipher
spec, and then forget the cipher spec. The server would generate the same
keyblock, use it to create a single-use read cipher spec, read the
TLSCiphertext record from the ClientSnapStart using that cipher spec, and
then forget that cipher spec.

Then, the client and server carry on just like with a normal session
resumption handshake, exchanging the exact same messages as a normal session
resumption. Optionally, the server could use your TLS false start extension
to start sending application data immediately.

Note that this wouldn't require the client to "predict" anything that the
server may send, ephemeral key exchange, client authentication, etc. would
all work normally.

Thoughts?

Regards,
Brian

---

From: Adam Langley <[email-masked]>
Date: Tue, 6 Jul 2010 11:47:44 -0400

On Mon, Jul 5, 2010 at 1:58 PM, Brian Smith <[email-masked]> wrote:
> And, if both sides implement OCSP stapling, then

It appears that you're assuming that a client's ability to persist
state is the same for OCSP information and for session information.
This isn't the case. OCSP information is public and can be cached on
disk for long periods of time. Session information cannot.

> the client could generate a keyblock using:

You're not the first to suggest the things would be considerably
simpler if we only dealt with the resumption case. I think that's
probably true.

However, the observed attempted resume rate at Google is only about
50%. Thus, we would be sacrificing a round trip for half of our
connections.

Additionally, with an eye on the future, OCSP will hopefully disappear
once we start putting ECDH public values in DNSSEC records. At that
point, the cost/benefit of resumption needs to be reexamined. Because
of that, I don't believe we should deprioritise the full handshake
case.

AGL

---

From: "Brian Smith" <[email-masked]>
Date: Sat, 31 Jul 2010 17:37:12 -0500

Adam Langley wrote:
> > And, if both sides implement OCSP stapling, then each connection will
> > either be a full non-snap-start handshake (with a stapled OCSP), a
> > normal session resumption, or a snap start session resumption--and
> > never a snap-start full handshake.
> 
> It appears that you're assuming that a client's ability to persist state is the same
> for OCSP information and for session information.
> This isn't the case. OCSP information is public and can be cached on disk for long
> periods of time. Session information cannot.

Yes, I did assume that, because many systems have a mechanism for safely storing the session information across process executions. For example, Windows's SChannel and maybe some other operating-system-provided TLS stacks do allow that, IIRC. But, I see advantages of snap start for full handshakes anyway. Please see below.

> You're not the first to suggest the things would be considerably simpler if we
> only dealt with the resumption case. I think that's probably true.
> 
> However, the observed attempted resume rate at Google is only about 50%.
> Thus, we would be sacrificing a round trip for half of our connections.

Potentially, implementing snap start for full handshakes will cause the resumption rate to decrease. If I am writing a client, and there's no significant direct performance benefit *to the client* to resume a session, then I am better off *never* resuming a session if the server supports snap start, because resuming a session allows the server to link my connections together, and my users' privacy is better protected by not giving the server that ability to link requests together trivially.

> Additionally, with an eye on the future, OCSP will hopefully disappear once we
> start putting ECDH public values in DNSSEC records. At that point, the
> cost/benefit of resumption needs to be reexamined.

That is effectively the same thing that TLS (EC)DHE key exchange does. All that is missing is an indication from each side that the given server (EC)DH parameters may be cached and reused in future connections (i.e. the key exchange is somewhere between ephemeral and static). If such an indication were added, then the client would be able to use snap start in its ClientHello for the (EC)DHE key exchange mechanisms too. And, except for DH_anon, the DH parameters can be safely cached on disk, because they are signed by the server.

I think that snap start can and should be factored into multiple pieces:

1. An extension (or new cipher suites) for indicating that the (EC)DH parameters in a ServerKeyExchange message are not really ephemeral, but rather are reusable for a certain duration of time. This part could be used reused independently of the other parts.

2. An extension that allows the client to put its ClientKeyExchange in a ClientHello extension. For DHE key exchanges, this would depend on the preceding extension.

3. The rest of snap start, modified to depend on the preceding extensions.

Given #1 and #2, the handshake would be optimized to a sequence similar to session resumption, but allowing a request for client authentication:

ClientHello
(w/ ClientKeyExchange)
				ServerHello
		                              [ChangeCipherSpec]
		                              Finished
				CertificateStatus*
				CertificateRequest*
				NewSessionTicket*
 [ChangeCipherSpec]
Finished
Certificate*
CertificateVerify*
Application Data         <--->	Application Data

Notice that, since the key exchange is done before the server sends its ServerHello, the CertificateStatus, CertificateRequest, Certificate, CertificateVerify, and NewSessionTicket messages can be encrypted and authenticated simply by placing them after the Finished messages, instead of before them. This would provide the extra benefit of even better privacy for the client user than previous attempts like [1] and [2], including unlinkability of session tickets (but still subject to traffic analysis).

Given #1, #2, and #3, the handshake would be optimized to the following:

ClientHello
(w/ ClientKeyExchange
 and Snap Start)
				ServerHello
		                              [ChangeCipherSpec]
		                              Finished
				CertificateStatus*
				NewSessionTicket*
				Application Data*
[ChangeCipherSpec]
Finished
Application Data*       <--->	Application Data*

Like I mentioned before, I think snap start should be modified so that only the initial ClientHello-embedded application-data is encrypted/authenticated using the keys derived purely from client-supplied information. All the subsequent application data should be protected using new keys derived using a random value generated by the server. For many applications, this would greatly reduce the impact of many replay attacks that weren't caught due to some error on the server side in managing the strike register, because it would provide the same guarantee as standard TLS that the server would *never* reuse IVs and keys, even if the client did. And, this change may  allow may allow many applications to work securely even *without* a strike register. For example, it seems like a public search engine that allowed read-only queries wouldn't necessarily need a strike register if this modification were made to snap start.

Regards,
Brian

[1] http://tools.ietf.org/html/draft-urien-badra-eap-tls-identity-protection-01
[2] http://tools.ietf.org/html/draft-hajjeh-tls-identity-protection-09

---

From: Adam Langley <[email-masked]>
Date: Sat, 31 Jul 2010 20:45:00 -0400

> 1. An extension (or new cipher suites) for indicating that the (EC)DH parameters in a ServerKeyExchange message are not really ephemeral, but rather are reusable for a certain duration of time. Thi…

I believe that this is isomorphic to (EC)DH_(RSA|DSS). Although I must
admit that I've never seen a fixed DH TLS connection, and a brief
check of the RFC wasn't enlightening. I'm not aware of the standard
format for (EC)DH_(RSA|DSS) certificates, although I suppose that the
X.509 PublicKey field is flexible enough to admit a fixed DH value. If
the server knew that the client could trust the fixed DH value via
another means (i.e. DNSSEC) then the signature of the certificate
could be omitted and the _(RSA|DSS) part rendered moot.

> 2. An extension that allows the client to put its ClientKeyExchange in a ClientHello extension. For DHE key exchanges, this would depend on the preceding extension.

I believe that the fixed DH value would be included in the client's
certificate with (EC)DH_(RSA|DSS). Again, probably unsigned.

> Given #1 and #2, the handshake would be optimized to a sequence similar to session resumption, but allowing a request for client authentication:

(I intended that Snap start already allow for client-side
certificates, although none of my unittests verify this.)

> Notice that, since the key exchange is done before the server sends its ServerHello, the CertificateStatus, CertificateRequest, Certificate, CertificateVerify, and NewSessionTicket messages can be…

I like encrypting as much as possible in principle.

> Like I mentioned before, I think snap start should be modified so that only the initial ClientHello-embedded application-data is encrypted/authenticated using the keys derived purely from client-su…

Your point about making sure that the server never reuses an IV + Key
is a very good one. I would want to consider it for a couple of days
but, at this point, I think it has sufficient merit to warrant
changing Snap Start. I suspect that my thinking was clouded because it
wouldn't have been easy in the original formulation of Snap Start, but
is much more so with the current one.

In general, I see EDH as much more of a spectrum than the dichotomy
that I often find it presented as. At one extreme, multiple EDH
handshakes could be performed in a single connection to protect
different time spans of that connection. At the other, the practice of
rotating RSA keys every year provides some forward security: a
compromise of this year's key doesn't allow for retrospective
decryption of last year's traffic.

When using ECDHE with a 224-bit curve (or larger), I think key
compromise is the greatest danger. The work required to calculate
discrete logs in such a large group suggests that, if accomplished,
the attacker probably has such a monumental breakthrough (i.e. a
quantum computer) that per-connection EDH probably isn't going to
present much more of a challenge.

Therefore, rotating a fixed DH value at some frequency may well
provide a better performance/security trade-off than per-connection
EDH. (And I'm probably pointing out the obvious when I say that DNSSEC
seems to provide a convenient, dynamic trust base for that.)

AGL