Subject: [TLS] Simple, secure 0-RTT for the masses

From: Bill Cox <[email-masked]>
Date: Tue, 15 Mar 2016 12:51:39 -0700

I think it is worth documenting what we feel would be the simplest secure
0-RTT mode that is safe for any company to use.  I think we owe the users a
link to such a document in the TLS 1.3 spec.  Here is my attempt at
creating the simplest possible TLS 1.3 compatible safe 0-RTT scheme.  It
uses a traditional server-side session-cache.  The protocol looks like this:

During the initial 1-RTT handshake:
- create an unencrypted ticket containing only the session ID and a
"resumption count" set to 0
- send the ticket to the client

During a 0-RTT resumption handshake:
- Get the session ID from the ticket, check for a cache hit, and drop to
1-RTT if not found
- compare the resumption counts in the session state and ticket, and fall
back to 1-RTT if they do not match
- increment the resumption count in the ticket and session state
- send the updated ticket to the client

With this protocol, POST requests are allowed in 0-RTT application data,
just like TLS 1.2.  Client certs are allowed only on the initial 1-RTT
handshake, since the 0-RTT connection cannot complete proofs of possession
before the 0-RTT application requests are executed by the server.

To see that this provides roughly TLS 1.2 security, note that so long as
the protocol never has to drop to 1-RTT, it is basically equivalent to TLS
1.2 session-ID based resumption.  When we do drop down to 1-RTT, we will
replay 0-RTT application data, opening up new replay attacks.  However,
after this paper
<http://blog.valverde.me/2015/12/07/bad-life-advice/#.VucOsJMrIxN>, I do
not believe there are any significant new replay attacks against HTTPS,
ssh, or any real protocol I can think of.  There may be weaknesses in TLS
1.3 resumption caused by the client forgetting the original connection's
security parameters, but if any are found, a client-side cache can be added.

Can this protocol be simplified by dropping the server cache?  No.  While
we can play with various server-side stateful schemes, such as strike
registers, it turns out that state on the server is _required_ for TLS 1.2
levels of security when using 0-RTT resumption.  Without server-side state,
0-RTT application data can be infinitely replayed, strong client
authentication stops working, and full PFS becomes impossible.  Note that
the above protocol does not deliver full PFS, but I claim that the modified
version described below does.

That's all I have for my attempt at "Simple, secure 0-RTT for the masses".
Below I just talk about extending the protocol to provide full PFS, which
AFAIK, the world has never implemented.

. . .

It turns out that providing full PFS over 0-RTT resumptions requires
server-side state.

Proof: Assume a server Sam has no server-side remembered session state, and
uses the same ticket decryption key to decrypt session tickets from both
Alice and Bob.  Different decryption keys are not possible because that
would require remembering which session ticket used which key.  Eve records
Alice’s resumed session, and later when Bob resumes, a server compromise
reveals Sam’s ticket decryption key to Eve.  Now Eve can decrypt Alice’s
previous resumed session since the ticket is sent from Alice to Bob before
encryption is enabled.  Clearly, the ticket contains all the information
needed to resume the encrypted session, since Sam does so without access to
any other server-side state.  Also, Alice is sending 0-RTT application data
before any new ephemeral keys can be established.  Eve simply simulates
resuming Alice's session and decrypts the 0-RTT application data, proving
that Alice's original session lacked forward secrecy.

So, stateless ticket resumption does not, and never will provide full PFS.
On the other hand, AFAIK, no one has ever provided full PFS using session
caching either.  Is there a solution?

Yes, there are multiple solutions.  For example, if TLS 1.3 were enhanced
to allow the session secrets to be re-keyed before saving the session state
to the cache, that would stop a server compromise from leaking session
secrets from past connections.  Given the current TLS 1.3 protocol as I
understand it, this is not possible, so my next-best solution is to have
the clients hold the server's session-cache decryption keys, which are
generated uniquely for each 0-RTT resumption.

In this scheme, the server stores a session-cache decryption key in the
ticket, and the ticket is not encrypted.  The protocol looks like this:

During the initial 1-RTT handshake:
- create a ticket containing the session ID, "resumption count" set to 0,
and a new session encryption key
- encrypt the session state in the cache with the session encryption key
- send the ticket to the client, and delete the session encryption key.
Note that the ticket is sent after encryption is enabled on the connection.

During a 0-RTT resumption handshake:
- check for a cache hit, and drop to 1-RTT if not found
- decrypt the cached session state with the encryption key from the ticket
- compare the resumption counts in the session-cache entry and ticket, and
fall back to 1-RTT if they do not match
- increment the resumption count
- create a new session encryption key in the ticket
- encrypt the updated session cache entry with the new session encryption
key
- send the updated ticket to the client

Did I miss anything?  Can it be simplified?

This time, when Sam's server is compromised, Eve cannot decrypt the 0-RTT
application data from Alice's previous session, because the session state
in the cache is encrypted with keys held only by the clients.  These 0-RTT
connections enjoy full PFS.

Bill

---

From: Bill Cox <[email-masked]>
Date: Tue, 15 Mar 2016 13:18:13 -0700

Correction:  TLS 1.3 PSK resumption already requires a client-side
session-cache, in order for the client to load the previous session state
and send 0-RTT data encrypted with the previous session secrets.  So, using
session caches on both sides seems to be the simplest safe 0-RTT mode
compatible with TLS 1.3.

Bill

---

From: Colm MacCárthaigh <[email-masked]>
Date: Tue, 15 Mar 2016 16:21:59 -0400

On Tue, Mar 15, 2016 at 3:51 PM, Bill Cox <[email-masked]> wrote:

> uses a traditional server-side session-cache.
>

Thanks for the awesome write up! This helped me clear my thinking a lot,
especially the proof.

> - send the updated ticket to the client

Here the resumption counts have to be synchronized between the client and
server, but is the count cryptographically authenticated? can can attacker
can take 0RTT data from session N, increment the resumption count, and
replay that 0RTT data?

Since synchronization and authenticity are both required here, would it be
simpler to use the sequence number and PRF state from the session? it can
be saved by the client and server on session close, and they take off where
they left things on any subsequent connection. That also gives clients and
their users additional confidence in the protocol: the server can't just
ignore things like resumption counts.

Another sort of warm and fuzzy reason I like this is that the whole thing
resembles a single-long-running regular TLS connection over a single TCP
socket. That makes things easier to verify, and some things easier to
implement.

> ssh, or any real protocol I can think of.
>

Unfortunately I don't think that's a safe assumption. The paper is about
browser behavior, but there are API clients and SDKs that do not retry as a
matter of design, they rely on TLS for non-replayability. In any event,
there might be no problem: wouldn't it be a TLS library bug if the library
somehow fell back to 1-RTT mode while also decrypting and passing on the
0RTT data? the client and the server need to agree on whether it was
received.
-- 
Colm

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Mar 2016 13:21:42 -0700

On Tue, Mar 15, 2016 at 12:51 PM, Bill Cox <[email-masked]> wrote:

> That's all I have for my attempt at "Simple, secure 0-RTT for the
> masses".  Below I just talk about extending the protocol to provide full
> PFS, which AFAIK, the world has never implemented.
>
> . . .
>
> Proof: Assume a server Sam has no server-side remembered session state,
> and uses the same ticket decryption key to decrypt session tickets from
> both Alice and Bob.  Different decryption keys are not possible because
> that would require remembering which session ticket used which key.  Eve
> records Alice’s resumed session, and later when Bob resumes, a server
> compromise reveals Sam’s ticket decryption key to Eve.  Now Eve can decrypt
> Alice’s previous resumed session since the ticket is sent from Alice to Bob
> before encryption is enabled.  Clearly, the ticket contains all the
> information needed to resume the encrypted session, since Sam does so
> without access to any other server-side state.  Also, Alice is sending
> 0-RTT application data before any new ephemeral keys can be established.
> Eve simply simulates resuming Alice's session and decrypts the 0-RTT
> application data, proving that Alice's original session lacked forward
> secrecy.
>
> So, stateless ticket resumption does not, and never will provide full
> PFS.  On the other hand, AFAIK, no one has ever provided full PFS using
> session caching either.  Is there a solution?
>
> secrets from past connections.
>

Can you expand on this point?
The session secret that is derived from connection N (the RMS) cannot be
used to
compute the traffic keys for connection N. Is that not the property you are
looking
for?

-Ekr

Given the current TLS 1.3 protocol as I understand it, this is not
> possible, so my next-best solution is to have the clients hold the server's
> session-cache decryption keys, which are generated uniquely for each 0-RTT
> resumption.
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>

---

From: Bill Cox <[email-masked]>
Date: Tue, 15 Mar 2016 13:59:51 -0700

> can take 0RTT data from session N, increment the resumption count, and

Crud, your right.  You broke that protocol in record time!  To make this
work with the existing TLS 1.3 spec, I think the server will have to
encrypt the ticket, which involves the whole ticket encryption key
management overhead.  Yuk.

> ignore things like resumption counts.

I prefer your solution, but it would require getting the TLS 1.3 protocol
changed.  TLS 1.3 seems to be geared towards making stateless resumption
with reusable tickets.

The issue seems to be that in TLS 1.3, tickets are reusable multiple times
to resume sessions, so we can't store the TLS sequence number in the
ticket.  If this were being used for an actual pre-shared key resumption,
it would probably be OK, but it seems to break security in multiple ways
when using tickets for TLS 1.2-style resumption, leaving us with no choice
but to emulate the continuation of the TLS sequence numbers (and PRF
state?  Is that needed?).

> socket. That makes things easier to verify, and some things easier to

That's the idea... but hard to implement, and not at all documented.

> 0RTT data? the client and the server need to agree on whether it was

This is worth more careful examination.  Each new protocol should be
analyzed for compatibility with session-cache based 0-RTT.  However, I have
not found any protocols that would have a problem.  Can you?

Protocols seem to fall into two camps.  The ones that require replay
resistance from the TLS layer all seem to terminate TLS connections in the
same place so that the session cache can be safely and efficiently
synchronized, avoiding replay attacks even when using 0-RTT.  For example,
when ssh-ing into a machine, that one machine terminates the connections,
and can have a shared cache.  None of the 0-RTT TLS-layer replay attacks
I've read seem to work against a single server-side session cache.

The other camp is HTTP-like protocols that terminate all over the place.
These all seem to be replay-tolerant because random network errors will
cause random replays, and there is no efficient way to synchronize the
session cache globally.

Bill

---

From: Bill Cox <[email-masked]>
Date: Tue, 15 Mar 2016 14:13:09 -0700

Second attempt, since Colm already broke my first attempt:

It uses a traditional server-side session-cache in addition to the current
client-side session-cache in TLS 1.3, and also a server-side ticket
encryption key.  The protocol looks like this:

During the initial 1-RTT handshake:
- create an encrypted ticket containing only the session ID and a
"resumption count" set to 0
- send the ticket to the client

During a 0-RTT resumption handshake:
- Decrypt the tikcet and get the session ID from the ticket, check for a
cache hit, and drop to 1-RTT if not found
- compare the resumption counts in the session state and ticket, and fall
back to 1-RTT if they do not match
- increment the resumption count in the ticket and session state
- send the updated ticket to the client

There is little PFS here.  Some can be had by flushing stale cache entries
and rotating the ticket encryption key often.

Are there any holes in this scheme?

Bill

---

From: Colm MacCárthaigh <[email-masked]>
Date: Tue, 15 Mar 2016 17:45:02 -0400

> changed.  TLS 1.3 seems to be geared towards making stateless resumption

We keep circling that alright, and it doesn't work without sacrificing FS
and/or replay-protection :(

> but to emulate the continuation of the TLS sequence numbers (and PRF

Sorry; I confused things by saying with PRF-state, but what I had in mind
there was turning the crank on the PRF to derive new encryption and mac
keys for the resumed session. If you do it that way; and if the PRF
provides anti-backtracking, then compromising the session cache can only be
used to decrypt future resumed connections, rather than anything previously
collected or currently active. If you're going to increment state for each
resumption; might as well provide forward secrecy too.

> I've read seem to work against a single server-side session cache.

I think I agree with that; but maybe would state it as: we can preserve
forward secrecy and replay mitigation for 0RTT data, but at the cost of
read-after-write consistency from a server-side data-store. The store
needn't be transactional, an eventually consistent store could be used: but
the miss-rate would be elevated over what we see today. So it would work
better in the single server case than the many distributed servers case -
but could work for both.

> cause random replays, and there is no efficient way to synchronize the

I think that's a dangerous position too. Triggering browser retries
requires a certain level of difficulty and has a certain amplification
factor. Sniffing wifi and sending a TCP message is far easier. An attacker
could exhaust things like server-side request throttling limits far more
quickly with the latter than the former. Besides: lowering our own levels
of security because other tools have already done the same is just another
race to the bottom.

-- 
Colm

---

From: Bill Cox <[email-masked]>
Date: Tue, 15 Mar 2016 18:38:41 -0700

> better in the single server case than the many distributed servers case -

Hmm... my first thought is we can't say all that in a "simple secure 0-RTT"
description :)  I do think it would help if all that and more were in a
more comprehensive document somewhere.

> of security because other tools have already done the same is just another

I would be happy if we could recommend at least one reasonably secure
method for 0-RTT for HTTPS that has a reasonable chance of satisfying the
skeptics, and then state that 0-RTT for other protocols, and stateless
0-RTT, needs to be carefully considered for the application.

---

From: Colm MacCárthaigh <[email-masked]>
Date: Wed, 16 Mar 2016 00:33:40 -0400

> 0-RTT, needs to be carefully considered for the application.

After meditating on this a little, how about something like this:

Benefits Forward secrecy:

* Clients SHOULD use a resumption ticket only once, and get a new
resumption ticket when using an existing one.

Benefits Forward Secrecy and Idempotence:

* Client and server should erase the existing ticket upon use.

(a captured early data section is mooted for replay quite quickly in the
default "good" case)

Benefits Idempotence;

* Make early data and application data separate record layer content types.
Make it clear that they do not form a continuous stream; you can't simply
concatenate them at the application level and bolt on to existing protocols
such as HTTP, SMTP, etc.

* Advise that clients using 0RTT SHOULD occasionally send duplicate early
data handshakes. As a normal part of the protocol, a well behaved client
should intentionally do what an attacker might do and send the whole
section twice, causing the server to resolve the duplication. Keep the
anti-bodies strong.

-- 
Colm

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 16 Mar 2016 10:17:17 +0200

> (a captured early data section is mooted for replay quite quickly in the

The best that can be done w.r.t. "forward secrecy" is to erase the
decryption-capable key used for 0-RTT on both sides, and never sending
it on the wire, even encrypted.

> concatenate them at the application level and bolt on to existing protocols

You mean inner (encrypted) content type, right (outer content type would
still be 23[TLS PROTECTED DATA]?

> section twice, causing the server to resolve the duplication. Keep the

Such duplication does not occur in attack conditions. The duplication
from attack conditions takes two forms:

- Duplication of 0-RTT data into 1-RTT data of _different_ connection.
- Duplication of 0-RTT data into 0-RTT data of _different_ connection.

In both cases, the connections are different, not the same. And this
makes a difference if e.g. protocol banners are sent as 0-RTT (and
such may very well be critical for latency).

-Ilari

---

From: Colm MacCárthaigh <[email-masked]>
Date: Wed, 16 Mar 2016 08:12:48 -0400

> it on the wire, even encrypted.

That's why I favor resuming connections where they left off, and cranking a
PRF to generate new keys; but it's not compatible with tickets at all -
works only with some kind of session store.

> still be 23[TLS PROTECTED DATA]?

Yep, sorry.

> - Duplication of 0-RTT data into 1-RTT data of _different_ connection.

I think using a different content type solves this; the early data is
illegal in the 1-RTT phase and the content type would distinguish it.

> such may very well be critical for latency).

The client would do what an attacker would; occasionally duplicate the
handshake including early data, so it would use a different connection for
it. The purpose here is to force a kind of "continuous testing in
production" that means the protocol really really does have to have
idempodence solved.

As an aside: an application protocol where latency is so sensitive that
0RTT is attractive would hardly have its own back-and-forth with banners in
the first place.

-- 
Colm

---

From: Bill Cox <[email-masked]>
Date: Wed, 16 Mar 2016 09:12:50 -0700

On Wed, Mar 16, 2016 at 5:12 AM, Colm MacCárthaigh <[email-masked]>
wrote:

> On Wed, Mar 16, 2016 at 4:17 AM, Ilari Liusvaara <[email-masked]
> > wrote:
>
> That's why I favor resuming connections where they left off, and cranking
> a PRF to generate new keys; but it's not compatible with tickets at all -

We can emulate resumption where we left off with the new ticket extension,
as I try to do above in my "second attempt".  Clearly this requires very
careful implementation, or you would not have so easily broken my first
attempt on this thread.  This is why I think we should document it, and
encourage people to analyze its security properties very carefully.

If emulation of 0-RTT resumption from where we left off is found to be as
secure as 0-RTT resumption from a cache with all the prior connection
state, then I prefer the new ticket scheme because it also supports the
riskier stateless forms of 0-RTT, which can improve speed, resumption
success rates, and lower costs (QUIC does all three).

I would love to see careful cryptanalysis of what we feel is the simplest
secure 0-RTT mode we can offer with TLS 1.3 as it is today.

One thing that helps me with analysis that I do not think is clear from the
spec: the client MUST save the entire session state to do PSK resumption,
other than:

- the previous session secrets which should be erased and replaced with the
resumption master secret
- the TLS sequence numbers since the keys changed.

Is this accurate?  I think it is important for security analysis.

Bill

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 16 Mar 2016 18:45:39 +0200

> illegal in the 1-RTT phase and the content type would distinguish it.

Nope, this can not be realistically solved, _even_ with server state
(the 0-RTT to 0-RTT duplication is unsolveable without state, but can
be solved with server state).

> 0RTT is attractive would hardly have its own back-and-forth with banners in

The problem is that such banners would not be bound to the TLS connection
in any way, which causes problems (TLS has no facility to transport data
from application inside extension).

-Ilari

---

From: Nicholas Sullivan <[email-masked]>
Date: Wed, 16 Mar 2016 12:07:42 -0700

What problem are you trying to solve here?

The forward secrecy properties of 0-RTT data in PSK mode are tied to the lifetime of the resumption secret, not a long-lived secret like the private key. If we limit the maximum lifetime of a given session ticket (say to 7 days as previously proposed on this mailing list) and recommend a similar lifetime for session ticket encryption keys, then what is the forward secrecy risk?

> On Mar 16, 2016, at 9:45 AM, Ilari Liusvaara <[email-masked]> wrote:
>