Subject: [TLS] Resumption and Forward Secrecy, 0-RTT and Safety

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 28 Mar 2016 11:55:32 -0700

Over the past week or so I've sent a few messages here on 0RTT but I've
been muddling together some separate concerns, and I'd like to split them
apart and treat them separately, with some concrete suggestions.

*Resumption and Forward Secrecy*
One of the reasons I'm excited about TLS1.3 is the prospect of greater
deployment of forward secrecy. Compromise of a credential - like an RSA or
ECDSA key - shouldn't crack open a trove of collected data. But a pitfall
here has been session tickets and session caches.

If an attacker compromises a session ticket encryption key, they can
decrypt any sessions encrypted which used that key. If an attacker
compromises a session cache, they can decrypt any sessions contained in the
cache.  In the real world: the former is much worse than the latter. A
cache is bounded in size and capacity and has real cost associated with
storing entries; it's also more likely to be sharded with "local" caches
relying on routing affinity.  On the other hand it is cheap and convenient
to use a single session ticket encryption key. Widely deployed software
(e.g. Apache, nginx ... ) has poor support for key rotation - for example
no schedule for rotating keys, no tracking how many times each key is used,
no support for multiple keys overlapping in time. It is not surprising to
see configurations where the same ticket encryption key has been in use for
years; outlasting RSA key lifetimes.

Put bluntly; session tickets as deployed in the real world defeat the point
of forward secrecy. A compromise of a single credential loads to a
catastrophic loss in security for previously collected sessions. Worse of
all: users have no way to audit how these keys are being managed. At least
it's possible to observe how long an RSA/ECDSA key is in use.

An alternative way to go is to restructure session resumption as single-use
session resumption IDs. Here's how it would work:

* TLS client asks server for 1 ... N session resumption IDs.  Both the
client and server iterate their PRF/KDFs N times ... deriving the same keys
(without exchanging them). The server then nominates N small (e.g. 8 byte)
IDs for each set of resumption state.

* Each ID is valid for use on a future connection. TLS clients are advised
that they MUST use each ID just once; discarding and erasing it upon use
during the resumption handshake.

Now this balloons the already-costly cost of session caches; by a factor of
N. And strangely, that's the point - it structures things so that the cache
implementor is incentivized to evict and replace entries. With eviction in
place; the regular security model of TLS is also restored. A compromise of
the cache only puts future connections at risk, and future connections are
generally always at risk due to server compromise.

I've built and operated a large CDN, and we use tickets (though we rotate
the keys!), and it would be an increase in costs to implement a session
cache, though I'd guess it's manageable. But that does suck. My argument
here is squarely user-security-centric;  TLS tickets are a dangerous sharp
edge that implementors keep screwing up. I think they should be blunted,
even at the expense of increasing costs for people like me.

One might reasonably say that this cost is too much, that forward secrecy
isn't worth losing tickets (which are cheap) over. But then, if we are
willing to sacrifice FS, why not go back to just encrypting using the
server key? that's a lot simpler. And that's how 0RTT is defined,  which
brings me to ...

*0RTT and Safety*
0-RTT had the potential to lower the latency for a lot of web users; which
is an awesome goal. Though I'd like to point out that the benefits don't
look that great to me compared to keeping connections alive for very long
periods of time:  Despite the name 0RTT still requires 1RTT (the TCP SYN ->
SYN|ACK exchange) before any data can be sent. A long-lived connection
doesn't have this problem : and in response to web sockets, IOT, and other
shifts, the technology to keep millions of connections open for long
periods of times on the server side (and even move live connections between
machines) is improving, along with long-lived connection battery-conserving
improvements for mobile. A connection that you keep open is "really" 0RTT;
the socket is primed for immediate I/O.

I see at least three different challenges with 0RTT as defined. The first
is a general and high level one: we seem to willing to accept a "lower"
level of security for 0RTT data (e.g. no FS, even if the rest of the
session has it). Why? What is it we think is special about this data that
it is "less" worth protecting? surely there are very sensitive things in
urls, surely there are potential oracles and other things in there too? It
just seems super strange to me.

The second challenge is that the replayability of the 0RTT poses a
cryptographic safety challenge. Take Lucky13 - which is a brilliant attack
and is stunningly effective against DTLS because it is so easy to replay
over and over; barely needing to change any parameters - and let the server
do the work. 0RTT looks very similar. It doesn't seem wise to let cipher
text manipulators take as many cracks at the whip as they'd like.

The third challenge is that the 0RTT plaintext data itself may not be safe
to replay; that is that it might trigger some kind of non-idempotent
action. Idempotence is really really hard, it isn't safe to simply plug in
a replayable section to existing protocols. There's also a huge difference
between being tolerant to a small number of replays, and a large unbounded
number. For example: a large unbounded number may be used to generate DOS
attacks against  throttles and quotas.

*Tying things together*
Short of some kind of transactional locking protocol during TLS handshakes,
I don't think there is a scheme that can perfectly prevent replay. Bill
Cox' analysis is a really good one here. But I'd like to observe that the
sort of single-use-session-id cache outlined above has a nice property that
it makes for a sort of strike register. Since the server-side implementor
is incentivized to evict entries, or at least mark them as used, so that
the slot is available for re-use; that can be doubled-up as a "we've seen
this already" signal. This reduces the replay window to the time period for
that signal to propagate (e.g. for an eviction to happen from the cache).

So 0RTT data could be encrypted under the resumption session id. That
creates the challenge that the session might not be there any more, so the
server may not be able to decrypt the 0RTT data. I actually think this is a
plus, and lines up with a separate important change I think is necessary -
the 0RTT data shouldn't be application data. It should be a separate,
optional, stream. I find it helpful to think of it as a hint, so it could
be called "replayable_hint". Instead of breaking apart an existing protocol
and putting some of it in the early data and some in the application data
transparently (a disaster in waiting), the client and server would have to
formally agree on the kind of data that could be in a "replayable_hint".
This goes a long way to mitigating many protocol level idempotency
concerns, and has no impact on the kind of pre-fetching people want to do
for HTTP and other protocols. At a bare minimum, I think we should make
this change.

Lastly, and this is a little crazy but I haven't let that stop me before
... to guard against the smaller replay window and idempotency problems at
the application levels,clients should occasionally send duplicate and
unrelated hints, just opportunistically. This keeps the server side
application "on notice" that that kind of craziness can occur, and better
to have it happen a little all of the time in a controlled way, than rarely
by attackers.

*Summary*
A common theme in the above is that it makes things more expensive for
server-side implementors, and that sucks - but I don't see another way to
avoid some of the pitfalls here; and I'm unhappy with the state of tickets
today. If I'm on my own on that, I'd be interested in what kinds of data
people might kind convincing. My own impressions come from being an Apache
httpd developer and assisting people with configurations and running
workshops at conferences. It's not scientific, but the prevalence of
non-rotation is so severe in my sample set that I'm convinced it's the
norm.

-- 
Colm

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 28 Mar 2016 12:58:28 -0700

On Monday, March 28, 2016, Colm MacCárthaigh <[email-masked]> wrote:

> A long-lived connection doesn't have this problem : and in response to web
> sockets, IOT, and other shifts, the technology to keep millions of
> connections open for long periods of times on the server side (and even
> move live connections between machines) is improving, along with long-lived
> connection battery-conserving improvements for mobile.
>

Mobile phones users constantly lose network connectivity and make up an
increasingly growing  majority of Internet clients. MPTCP is great but the
reality is mobile network deployment isn't ubiquitous on planet earth and
mobile clients constantly go offline and back online several times
throughout a day on average.

-- 
Tony Arcieri

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Mon, 28 Mar 2016 22:31:07 +0200

Let me try to understand the concerns here.

> Resumption and Forward Secrecy

PSK_ECDHE in TLS 1.3 does provide forward secrecy for 1-RTT data, yes?
This is already better than TLS 1.2 where we had no way to do forward-secret resumption.
In that case, the concern is mainly for 0-RTT, which I agree is harder to get right.

> 0RTT and Safety
> I see at least three different challenges with 0RTT as defined. The first is a general and high level one: we seem to willing to accept a "lower" level of security for 0RTT data (e.g. no FS, even if the rest of the session has it). Why? What is it we think is special about this data that it is "less" worth protecting? surely there are very sensitive things in urls, surely there are potential oracles and other things in there too? It just seems super strange to me. 

I wonder if the QUIC folks have an answer to this question? It would be good to gather “typical” intended use cases of 0-RTT data.
In any case, it is good to distinguish this forward secrecy concern from replay, because secrecy is in the control of the client, who can choose to send or not send sensitive data, but replay detection is in the hands of the server.

> The second challenge is that the replayability of the 0RTT poses a cryptographic safety challenge. Take Lucky13 - which is a brilliant attack and is stunningly effective against DTLS because it is so easy to replay over and over; barely needing to change any parameters - and let the server do the work. 0RTT looks very similar. It doesn't seem wise to let cipher text manipulators take as many cracks at the whip as they'd like. 
> The third challenge is that the 0RTT plaintext data itself may not be safe to replay; that is that it might trigger some kind of non-idempotent action. Idempotence is really really hard, it isn't safe to simply plug in a replayable section to existing protocols. There's also a huge difference between being tolerant to a small number of replays, and a large unbounded number. For example: a large unbounded number may be used to generate DOS attacks against  throttles and quotas. 

Yes, detecting and preventing replays by default would be good.
However, I wouldn’t tie this in with the session mechanism. 
Wouldn’t we want to prevent replay of DH 0-RTT requests?

Best,
Karthik

> 
> The third challenge is that the 0RTT plaintext data itself may not be safe to replay; that is that it might trigger some kind of non-idempotent action. Idempotence is really really hard, it isn't safe to simply plug in a replayable section to existing protocols. There's also a huge difference between being tolerant to a small number of replays, and a large unbounded number. For example: a large unbounded number may be used to generate DOS attacks against  throttles and quotas. 
> 
> Tying things together
> Short of some kind of transactional locking protocol during TLS handshakes, I don't think there is a scheme that can perfectly prevent replay. Bill Cox' analysis is a really good one here. But I'd like to observe that the sort of single-use-session-id cache outlined above has a nice property that it makes for a sort of strike register. Since the server-side implementor is incentivized to evict entries, or at least mark them as used, so that the slot is available for re-use; that can be doubled-up as a "we've seen this already" signal. This reduces the replay window to the time period for that signal to propagate (e.g. for an eviction to happen from the cache). 
> 
> So 0RTT data could be encrypted under the resumption session id. That creates the challenge that the session might not be there any more, so the server may not be able to decrypt the 0RTT data. I actually think this is a plus, and lines up with a separate important change I think is necessary - the 0RTT data shouldn't be application data. It should be a separate, optional, stream. I find it helpful to think of it as a hint, so it could be called "replayable_hint". Instead of breaking apart an existing protocol and putting some of it in the early data and some in the application data transparently (a disaster in waiting), the client and server would have to formally agree on the kind of data that could be in a "replayable_hint". This goes a long way to mitigating many protocol level idempotency concerns, and has no impact on the kind of pre-fetching people want to do for HTTP and other protocols. At a bare minimum, I think we should make this change. 
> 
> Lastly, and this is a little crazy but I haven't let that stop me before ... to guard against the smaller replay window and idempotency problems at the application levels,clients should occasionally send duplicate and unrelated hints, just opportunistically. This keeps the server side application "on notice" that that kind of craziness can occur, and better to have it happen a little all of the time in a controlled way, than rarely by attackers.  
> 
> Summary
> A common theme in the above is that it makes things more expensive for server-side implementors, and that sucks - but I don't see another way to avoid some of the pitfalls here; and I'm unhappy with the state of tickets today. If I'm on my own on that, I'd be interested in what kinds of data people might kind convincing. My own impressions come from being an Apache httpd developer and assisting people with configurations and running workshops at conferences. It's not scientific, but the prevalence of non-rotation is so severe in my sample set that I'm convinced it's the norm. 
> 
> -- 
> Colm
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 28 Mar 2016 13:39:03 -0700

> In that case, the concern is mainly for 0-RTT, which I agree is harder to

Yes  ... and  I left that out in the interests of clarity for the argument
... but I mean this scheme for the 0RTT data (hence the tying it together).
I should have been more clear, thanks!

> I wonder if the QUIC folks have an answer to this question? It would be
> good to gather “typical” intended use cases of 0-RTT data.
> In any case, it is good to distinguish this forward secrecy concern from
> replay, because secrecy is in the control of the client, who can choose to
> send or not send sensitive data, but replay detection is in the hands of
> the server.
>

A lot falls out from replay. If there are side-channels in how the server
handles the 0RTT section (and we can be certain that there will be) then
the ability to replay the section greatly amplifies the attackers ability
to use those side-channels to determine things about the data. Where the
data is a url, which can contain things like passwords, session ids, and
other bearer tokens, that's a bad combo.

> Wouldn’t we want to prevent replay of DH 0-RTT requests?

I should be more clear: I mean to replace the DH 0-RTT part with 0-RTT
parts that are encrypted under separate single-use PSK states.

-- 
Colm

---

From: Bill Frantz <[email-masked]>
Date: Mon, 28 Mar 2016 14:04:20 -0700

On 3/28/16 at 11:55 AM, [email-masked] (Colm MacCárthaigh) wrote:

>surely there are very sensitive things in urls,

A number of URLs include an authorization token which authorizes 
access to a resource. This token is frequently a long 
"unguessable" number. It must be kept secret. I think DropBox 
URLs are one example.

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | The first thing you need when  | Periwinkle
(408)356-8506      | using a perimeter defense is a | 16345 
Englewood Ave
www.pwpconsult.com | perimeter.                     | Los Gatos, 
CA 95032

---

From: Andrei Popov <[email-masked]>
Date: Mon, 28 Mar 2016 21:28:13 +0000

Ø  It would be good to gather “typical” intended use cases of 0-RTT data.
It is likely that the typical use of 0-RTT data will be to convey a Web browser’s first GET request to a site, on a newly established connection.

Ø  … because secrecy is in the control of the client, who can choose to send or not send sensitive data…
Generally, how can a browser distinguish sensitive data?

Cheers,

Andrei

From: TLS [mailto:[email-masked]] On Behalf Of Karthikeyan Bhargavan
Sent: Monday, March 28, 2016 1:31 PM
To: Colm MacCárthaigh <[email-masked]>
Cc: [email-masked]
Subject: Re: [TLS] Resumption and Forward Secrecy, 0-RTT and Safety

0RTT and Safety

Best,
Karthik

Tying things together

Summary

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

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Mon, 28 Mar 2016 23:30:39 +0200

> Generally, how can a browser distinguish sensitive data?

By not sending cookies or authorization headers, for example?

>  
> Cheers,
>  
> Andrei
>  
> From: TLS [mailto:[email-masked] <mailto:[email-masked]>] On Behalf Of Karthikeyan Bhargavan
> To: Colm MacCárthaigh <[email-masked] <mailto:[email-masked]>>
> Cc: [email-masked] <mailto:[email-masked]>
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>

---

From: Andrei Popov <[email-masked]>
Date: Mon, 28 Mar 2016 21:47:23 +0000

Not sending cookies/authz headers in 0-RTT would solve a part of the problem, but will browser vendors go for that? I could be wrong, but there seems to be considerable interest in 0-RTT Token Binding…. so folks must be planning on sending tokens☺.

From: Karthikeyan Bhargavan [mailto:[email-masked]]
Sent: Monday, March 28, 2016 2:31 PM
To: Andrei Popov <[email-masked]>
Cc: Colm MacCárthaigh <[email-masked]>; [email-masked]
Subject: Re: [TLS] Resumption and Forward Secrecy, 0-RTT and Safety

>  … because secrecy is in the control of the client, who can choose to send or not send sensitive data…

Cheers,

Andrei

From: TLS [mailto:[email-masked]] On Behalf Of Karthikeyan Bhargavan
Sent: Monday, March 28, 2016 1:31 PM
To: Colm MacCárthaigh <[email-masked]<mailto:[email-masked]>>
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [TLS] Resumption and Forward Secrecy, 0-RTT and Safety

0RTT and Safety

Best,
Karthik

Tying things together

Summary

--
Colm
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwww.ietf.org%2fmailman%2flistinfo%2ftls&data=01%7c01%7cAndrei.Popov%40microsoft.com%7c88d384e16d794a23be0c08d35750543d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=IU9aYW%2b6Gt0pnbIVXnT2yGNzOCGfmvvg%2fY5yFhiKlYY%3d>

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 28 Mar 2016 15:06:23 -0700

Yes, I believe that this is what people want.

On Mon, Mar 28, 2016 at 2:47 PM, Andrei Popov <[email-masked]>
wrote:

> Not sending cookies/authz headers in 0-RTT would solve a part of the
> problem, but will browser vendors go for that? I could be wrong, but there
> seems to be considerable interest in 0-RTT Token Binding…. so folks must be
> planning on sending tokensJ.
>
>
>
> *From:* Karthikeyan Bhargavan [mailto:[email-masked]]
> *Sent:* Monday, March 28, 2016 2:31 PM
> *To:* Andrei Popov <[email-masked]>
> *Cc:* Colm MacCárthaigh <[email-masked]>; [email-masked]
>
> *Subject:* Re: [TLS] Resumption and Forward Secrecy, 0-RTT and Safety
>
>
>
> *From:* TLS [mailto:[email-masked] <[email-masked]>] *On
> Behalf Of *Karthikeyan Bhargavan
> *Sent:* Monday, March 28, 2016 1:31 PM
> *To:* Colm MacCárthaigh <[email-masked]>
> *Cc:* [email-masked]
> *Subject:* Re: [TLS] Resumption and Forward Secrecy, 0-RTT and Safety
>
>
>
> Short of some kind of transactional locking protocol during TLS
> handshakes, I don't think there is a scheme that can perfectly prevent
> replay. Bill Cox' analysis is a really good one here. But I'd like to
> observe that the sort of single-use-session-id cache outlined above has a
> nice property that it makes for a sort of strike register. Since the
> server-side implementor is incentivized to evict entries, or at least mark
> them as used, so that the slot is available for re-use; that can be
> doubled-up as a "we've seen this already" signal. This reduces the replay
> window to the time period for that signal to propagate (e.g. for an
> eviction to happen from the cache).
>
>
>
> <https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fwww.ietf.org%2fmailman%2flistinfo%2ftls&data=01%7c01%7cAndrei.Popov%40microsoft.com%7c88d384e16d794a23be0c08d35750543d%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=IU9aYW%2b6Gt0pnbIVXnT2yGNzOCGfmvvg%2fY5yFhiKlYY%3d>
>
>
>

---

From: Ryan Hamilton <[email-masked]>
Date: Mon, 28 Mar 2016 15:49:48 -0700

>> planning on sending tokensJ.
​We (Chrome) definitely want this (sending cookies in 0-RTT requests), and
are doing this today with QUIC (which we can't wait to TLS 1.3-ify). ​

---

From: Martin Thomson <[email-masked]>
Date: Tue, 29 Mar 2016 10:53:51 +1100

On 29 March 2016 at 08:04, Bill Frantz <[email-masked]> wrote:
> A number of URLs include an authorization token which authorizes access to a
> resource. This token is frequently a long "unguessable" number. It must be
> kept secret. I think DropBox URLs are one example.

The risk to the secrecy of that sort of data is limited.

The primary risk is in the traffic analysis that might be performed as
a result of replaying.

---

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 28 Mar 2016 17:44:20 -0700

On Mon, Mar 28, 2016 at 3:49 PM, Ryan Hamilton <[email-masked]> wrote:

>> On Mon, Mar 28, 2016 at 2:47 PM, Andrei Popov <[email-masked]
>> > wrote:
>>

Let's leave aside all of the parts about resumption tokens for a minute.
How big  adeal would it be if the early data were like the hints I
outlined? Let's say a request pattern looked something like;

[ replayable_hint data ]
GET /foo/bar/1234 HTTP/1.1
Host: www.example.com
Cookie: somedata
[ application_data ]
GET /foo/bar/1234 HTTP/1.1
Host: www.example.com
Cookie: somedata
...

Obviously this is trivial for clients to generate and send. On the server
side; the server could treat the hint as a signal to start rendering
"/foo/bar/1234". Obviously the request and the headers are more or less
duplicated here; and that uses some bandwidth, but it seems like a pretty
trivial amount. The server can reply with its rendering at the same point
as the existing 0-RTT proposal; it needn't even read the duplicate
request(s) in the application data section.

The benefit is that it makes a lot of idempodence issues go away; if the
application protocol has to reason about the types of data explicitly, we
can be less worried about the potential impact on the many other kinds of
protocol that are layered on top of TLS.

Then next; and slightly crazier - what if the browser were to very
occasionally connect and send only the hint, and the server just had to
deal with it. How big a deal would that be?

-- 
Colm

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Tue, 29 Mar 2016 10:21:28 +0200

> ​We (Chrome) definitely want this (sending cookies in 0-RTT requests), and are doing this today with QUIC (which we can't wait to TLS 1.3-ify). ​

I see. So, it is quite likely that the most common usage of TLS 1.3 would send sensitive data in 0-RTT.
It is unfortunate that the forward secrecy of this data is determined solely by mechanisms (e.g. tickets, client-side caches) 
and policies (e.g. ticket encryption key rollover time) that are outside the scope of TLS.

I wonder if it would be better to give more guidance to implementations to better manage these mechanisms.
For example, servers that use ticket only for 1-RTT resumption can set the ticket expiry and ticket encryption key rollover time as they do for TLS 1.2.
However, servers that support tickets for 0-RTT must use a much shorter expiry/rollover period to reduce the forward secrecy window.
How short should this window be in practice? 

Note that choosing the expiry/rollover period also determines the replay window, and it is less obvious whether the two windows should be the same.
E.g. we may be happy with a 1-hour forward secrecy window, but only a 10-minute replay window?

Best,
Karthik

---

From: Martin Thomson <[email-masked]>
Date: Tue, 29 Mar 2016 20:57:53 +1100

On 29 March 2016 at 19:21, Karthikeyan Bhargavan
<[email-masked]> wrote:
> Note that choosing the expiry/rollover period also determines the replay
> window,

I think that we can fix that one easily, as I suggested in an earlier
mail.  I plan to open a PR that does that.

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 29 Mar 2016 22:18:27 -0700

> are doing this today with QUIC (which we can't wait to TLS 1.3-ify). ​

I went to RealWorldCrypto 2016 and saw the TLS track and all of the
analysis TLS 1.3 has received, and while it wasn't TRON, I can sympathize
with why you might want TLS 1.3, namely the extensive analysis it is
receiving as an up and coming cryptographic standard which is a clear
choice for academic researchers to focus on.

That said, I really don't understand Google's excitement to switch from
QUIC's crypto to TLS 1.3. QUIC crypto seems like a much simpler and cleaner
protocol which fulfills many of the same goals as TLS, and while it hasn't
received as much scrutiny as TLS 1.3, it seems like it doesn't need as much
by design due to its relative simplicity.

I also understand Facebook is adding QUIC-crypto-over-TCP support to
proxygen (there was also a talk at RWC2016) for use in their mobile apps as
a stopgap for doing 0-RTT until such a time as 0-RTT ships in TLS 1.3.

Can you speak to specific reasons why the Chrome team "can't wait to TLS
1.3-ify" over QUIC, specifically reasons different from the ones I have
already highlighted above?

-- 
Tony Arcieri