Subject: [TLS] Limiting replay time frame of 0-RTT data

From: Kyle Nekritz <[email-masked]>
Date: Fri, 11 Mar 2016 20:21:07 +0000

Similar to the earlier discussion on 0.5-RTT data, I'm concerned with the long term ability to replay captured 0-RTT early data, and the attack vectors that it opens up. For example, take a GET request for an image to a CDN. This is a request that seems completely idempotent, and that applications will surely want to send as 0-RTT data. However, this request can result in a few things happening:
    1) Resource unavailable
    2) Resource cached locally at edge cluster
    3) Cache miss, resource must be fetched from origin data center
#1 can easily be differentiated by the length of the 0.5-RTT response data, allowing an attacker to determine when a resource has been deleted/modified. #2 and #3 can also be easily differentiated by the timing of the response. This opens up the following attack: if an attacker knows a client has requested a resource X_i in the attacker-known set {X_1, X_2, ..., X_n}, an attacker can do the following:
    1) wait for the CDN cache to be evicted
    2) request {X_1, X_2, ..., X_(n/2)} to warm the cache
    3) replay the captured client early data (the request for X_i)
    4) determine, based on the timing of the response, whether it resulted in a cache hit or miss
    5) repeat with set {X_1, X_2, ..., X_(n/2)} or {X_(n/2 + 1), X_(n/2 + 2), ..., X_n} depending on the result
This particular binary search example is a little contrived and requires that no-one else is requesting any resource in the set, however I think it is representative of a significant new attack vector that allowing long-term replay of captured early data will open up, even if 0-RTT is only used for seemingly simple requests without TLS client authentication. This is a much different threat than very short-term replay, which is already somewhat possible on any TLS protocol if clients retry failed requests.

Given this, I think it is worth attempting to limit the time frame that captured early data is useful to an attacker. This obviously doesn't prevent replay, but it can mitigate a lot of attacks that long-term replay would open up. This can be done by including a client time stamp along with early data, so that servers can choose to either ignore the early data, or to delay the 0.5-RTT response to 1.5-RTT if the time stamp is far off. This cuts down the time from days (until the server config/session ticket key is rotated) to minutes or seconds.

Including the client time also makes a client random strike register possible without requiring an unreasonably large amount of server-side state.

I am aware that client time had previously been removed from the client random, primarily due to fingerprinting concerns, however these concerns can be mitigated by
1) clients can choose to not include their time (or to include a random time), with only the risk of their .5-RTT data being delayed
2) placing the time stamp in an encrypted extension, so that it is not visible to eavesdroppers

Note: it's also useful for the server to know which edge cluster the early data was intended for, however this is already possible in the current draft. In ECDHE 0-RTT server configs can be segmented by cluster, and with tickets, the server can store cluster information in the opaque ticket.

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 12 Mar 2016 13:56:29 +0100

Hi Kyle,

Clever attack. I don't think it would be unreasonable to put a low
granularity time stamp in the
ClientHello (and as you observe, if we just define it it can be done
backward compatibly)
or as you suggest, in an encrypted block. With that said, though couldn't
you
also just include the information in the HTTP header for HTTP? Do you think
this is a sufficiently
general issue that it merits a change to TLS.

-Ekr

On Fri, Mar 11, 2016 at 9:21 PM, Kyle Nekritz <[email-masked]> wrote:

> Similar to the earlier discussion on 0.5-RTT data, I’m concerned with the
> long term ability to replay captured 0-RTT early data, and the attack
> vectors that it opens up. For example, take a GET request for an image to a
> CDN. This is a request that seems completely idempotent, and that
> applications will surely want to send as 0-RTT data. However, this request
> can result in a few things happening:
>     1) Resource unavailable
> #1 can easily be differentiated by the length of the 0.5-RTT response
> data, allowing an attacker to determine when a resource has been
> deleted/modified. #2 and #3 can also be easily differentiated by the timing
> of the response. This opens up the following attack: if an attacker knows a
> client has requested a resource X_i in the attacker-known set {X_1, X_2,
> ..., X_n}, an attacker can do the following:
>     2) request {X_1, X_2, …, X_(n/2)} to warm the cache
>     5) repeat with set {X_1, X_2, …, X_(n/2)} or {X_(n/2 + 1), X_(n/2 +
> 2), …, X_n} depending on the result
> This particular binary search example is a little contrived and requires
> that no-one else is requesting any resource in the set, however I think it
> is representative of a significant new attack vector that allowing
> long-term replay of captured early data will open up, even if 0-RTT is only
> used for seemingly simple requests without TLS client authentication. This
> is a much different threat than very short-term replay, which is already
> somewhat possible on any TLS protocol if clients retry failed requests.
>
> Given this, I think it is worth attempting to limit the time frame that
> captured early data is useful to an attacker. This obviously doesn’t
> prevent replay, but it can mitigate a lot of attacks that long-term replay
> would open up. This can be done by including a client time stamp along with
> early data, so that servers can choose to either ignore the early data, or
> to delay the 0.5-RTT response to 1.5-RTT if the time stamp is far off. This
> cuts down the time from days (until the server config/session ticket key is
> rotated) to minutes or seconds.
>
> Including the client time also makes a client random strike register
> possible without requiring an unreasonably large amount of server-side
> state.
>
> I am aware that client time had previously been removed from the client
> random, primarily due to fingerprinting concerns, however these concerns
> can be mitigated by
> 1) clients can choose to not include their time (or to include a random
> time), with only the risk of their .5-RTT data being delayed
> Note: it’s also useful for the server to know which edge cluster the early
> data was intended for, however this is already possible in the current
> draft. In ECDHE 0-RTT server configs can be segmented by cluster, and with
> tickets, the server can store cluster information in the opaque ticket.
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Sat, 12 Mar 2016 18:45:48 +0100

Hi Kyle,

In my talk at TRON, I was also concerned by potential attacks from allowing 
unlimited replay of 0-RTT data. I recommended that TLS 1.3 servers should
implement replay protection using a cache, but requiring clients to provide
a timestamp in the client random is a great idea. Perhaps this would also
allow TLS 1.3 servers to detect clients whose clocks are too out-of-sync with
the server (and hence vulnerable to expired certificates)?

Best,
Karthik

> On 12 Mar 2016, at 13:56, Eric Rescorla <[email-masked]> wrote:
> 
> Hi Kyle,
> 
> Clever attack. I don't think it would be unreasonable to put a low granularity time stamp in the
> ClientHello (and as you observe, if we just define it it can be done backward compatibly)
> or as you suggest, in an encrypted block. With that said, though couldn't you
> also just include the information in the HTTP header for HTTP? Do you think this is a sufficiently
> On Fri, Mar 11, 2016 at 9:21 PM, Kyle Nekritz <[email-masked] <mailto:[email-masked]>> wrote:
> Similar to the earlier discussion on 0.5-RTT data, I’m concerned with the long term ability to replay captured 0-RTT early data, and the attack vectors that it opens up. For example, take a GET request for an image to a CDN. This is a request that seems completely idempotent, and that applications will surely want to send as 0-RTT data. However, this request can result in a few things happening:
>     1) Resource unavailable
>     5) repeat with set {X_1, X_2, …, X_(n/2)} or {X_(n/2 + 1), X_(n/2 + 2), …, X_n} depending on the result
> Given this, I think it is worth attempting to limit the time frame that captured early data is useful to an attacker. This obviously doesn’t prevent replay, but it can mitigate a lot of attacks that long-term replay would open up. This can be done by including a client time stamp along with early data, so that servers can choose to either ignore the early data, or to delay the 0.5-RTT response to 1.5-RTT if the time stamp is far off. This cuts down the time from days (until the server config/session ticket key is rotated) to minutes or seconds.
> 
> Note: it’s also useful for the server to know which edge cluster the early data was intended for, however this is already possible in the current draft. In ECDHE 0-RTT server configs can be segmented by cluster, and with tickets, the server can store cluster information in the opaque ticket.
> 
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>
> 
>

---

From: Brian Smith <[email-masked]>
Date: Sat, 12 Mar 2016 09:33:28 -1000

> tickets, the server can store cluster information in the opaque ticket.

Shouldn't the server also put a 0-RTT timestamp in the opaque ticket and
then implement the same time limiting you suggest using that timestamp?
That way, the timestamp would be authenticated and would not leak the
client's system time information.

Note that this would be better than relying on HTTP timestamps because it
would work for any protocol, not just HTTP.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Erik Nygren <[email-masked]>
Date: Sat, 12 Mar 2016 21:49:40 -0500

That does seem like a good idea to include a client time stamp in the 0RTT
flow to let the server force 1RTT in the case where this is too far off as
this bounds the duration of the replay window.  (I suspect we'll find a
whole range of other similar attacks using 0RTT.)  An encrypted client
timestamp could presumably be probed by the server.  (ie, if the server
response is a different size for timestamp-expired vs timestamp-not-expired
an attacker could keep probing until they change?)  That does seem like
more effort, however.

           Erik

On Sat, Mar 12, 2016 at 7:56 AM, Eric Rescorla <[email-masked]> wrote:

>> Note: it’s also useful for the server to know which edge cluster the
>> early data was intended for, however this is already possible in the
>> current draft. In ECDHE 0-RTT server configs can be segmented by cluster,
>> and with tickets, the server can store cluster information in the opaque
>> ticket.
>>

---

From: Martin Thomson <[email-masked]>
Date: Sun, 13 Mar 2016 20:36:25 +1100

I assume that you would run a tight tolerance on the 0RTT resumption by
saving the client's clock error in the ticket.  That a way only clients
with bad drift get no 0RTT. To do that all sessions need time.

I do not see how the server can do this in general without client help. But
the solution also addresses Brian's concern. The client doesn't need
absolute time, just relative time: How long since the ticket was issued.
Then it's an addition to the psk_identity only.
On 13 Mar 2016 1:49 PM, "Erik Nygren" <[email-masked]> wrote:

>>> Similar to the earlier discussion on 0.5-RTT data, I’m concerned with
>>> the long term ability to replay captured 0-RTT early data, and the attack

---

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

+1 for supporting client timestamps.  Various methods for mitigating 0-RTT
security limitations (PFS, proofs of possession, replay),  involve using a
timestamp.  It has use outside the attack described above.

---

From: Jeffrey Walton <[email-masked]>
Date: Sun, 13 Mar 2016 19:36:39 -0400

> allow TLS 1.3 servers to detect clients whose clocks are too out-of-sync

Be careful here. The whole point of 0-RTT is to start consuming data
before its authenticated to save a few milliseconds in network time.
All those parameters are controlled by the attacker.

We never worried about the extra roundtrip using satellite comms with
0.5 to 1.0 second delays. Additionally, most of my delays in fetching
web pages seems to be delays in Google APIs and servings third party
ads. 0-RTT seems to be a solution looking for a problem.

---

From: Ryan Hamilton <[email-masked]>
Date: Mon, 14 Mar 2016 12:15:16 -0700

On Sun, Mar 13, 2016 at 4:36 PM, Jeffrey Walton <[email-masked]> wrote:

> 0-RTT seems to be a solution looking for a problem.
>

​Google has been using 0-RTT as part of the QUIC transport for quite a
while now. In April of last year, we posted about the performance benefits
we're seeing from QUIC
<http://blog.chromium.org/2015/04/a-quic-update-on-googles-experimental.html>.
Among other things, that post said:

Even on a well-optimized site like Google Search, where connections are
often pre-established, we still see a 3% improvement in mean page load time
with QUIC.

>From the browser side of things, 0-RTT is a solution to a very real
problem. We are excited about TLS 1.3 supporting 0-RTT (or 0-RTT
resumption) and converting QUIC to use the TLS 1.3 handshake as a result.

Cheers,

Ryan

---

From: Kyle Nekritz <[email-masked]>
Date: Mon, 14 Mar 2016 20:43:11 +0000

As others have said I do think adding client time solves much more than just this specific issue. Running a client nonce cache at scale also likely requires client time in order to limit the storage needed to a reasonable amount.

I like the idea of including time since receiving the session ticket instead of absolute time. This allows for clients with high clock skew but still an accurate steady clock to use 0-RTT, and likely for tighter bounds to be placed on the time.  The natural place to put this would be the client hello, where it would be unencrypted, which would leak the time of ticket issuance. How concerning is this, is it worth encrypting this time?

Kyle

From: TLS [mailto:[email-masked]] On Behalf Of Martin Thomson
Sent: Sunday, March 13, 2016 5:36 AM
To: Erik Nygren <[email-masked]>
Cc: [email-masked]
Subject: Re: [TLS] Limiting replay time frame of 0-RTT data

I assume that you would run a tight tolerance on the 0RTT resumption by saving the client's clock error in the ticket.  That a way only clients with bad drift get no 0RTT. To do that all sessions need time.

I do not see how the server can do this in general without client help. But the solution also addresses Brian's concern. The client doesn't need absolute time, just relative time: How long since the ticket was issued. Then it's an addition to the psk_identity only.
On 13 Mar 2016 1:49 PM, "Erik Nygren" <[email-masked]<mailto:[email-masked]>> wrote:
That does seem like a good idea to include a client time stamp in the 0RTT flow to let the server force 1RTT in the case where this is too far off as this bounds the duration of the replay window.  (I suspect we'll find a whole range of other similar attacks using 0RTT.)  An encrypted client timestamp could presumably be probed by the server.  (ie, if the server response is a different size for timestamp-expired vs timestamp-not-expired an attacker could keep probing until they change?)  That does seem like more effort, however.
           Erik

On Sat, Mar 12, 2016 at 7:56 AM, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:
Hi Kyle,

-Ekr

On Fri, Mar 11, 2016 at 9:21 PM, Kyle Nekritz <[email-masked]<mailto:[email-masked]>> wrote:

_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l2j4BjkO0Lc3u4CH2z7jPw&m=hKiQKAVn_GFQiKNtyPpO5SW6BjMTNV0jf6nb7qdIqxA&s=w1kyX4_66LehjWfy5-625X8MU8TX9JTSRIcgTlU6iqA&e=>

_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l2j4BjkO0Lc3u4CH2z7jPw&m=hKiQKAVn_GFQiKNtyPpO5SW6BjMTNV0jf6nb7qdIqxA&s=w1kyX4_66LehjWfy5-625X8MU8TX9JTSRIcgTlU6iqA&e=>

_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l2j4BjkO0Lc3u4CH2z7jPw&m=hKiQKAVn_GFQiKNtyPpO5SW6BjMTNV0jf6nb7qdIqxA&s=w1kyX4_66LehjWfy5-625X8MU8TX9JTSRIcgTlU6iqA&e=>

---

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 14 Mar 2016 17:04:09 -0400

On Mon, Mar 14, 2016 at 3:15 PM, Ryan Hamilton <[email-masked]> wrote:
> while now. In April of last year, we posted about the performance
> benefits we're seeing from QUIC

Are you sacrificing forward secrecy in this case? For a concrete example:
suppose $oppressive_government is collecting all traffic as a routine
matter of course, and then later a remote-ex, memory-disclosure, or
decrypt-oracle  (like the recent DROWN) came along on the server side:
could it be used to decrypt all of $worthy_dissident's requests? how long
for, how do you manage that trade-off?

On the "3% speed up" - we're not going to see that for TLS 1.3 though -
right? there's still the TCP handshake to perform; or is some kind of
custom TCP in the works? (does TCPCT work on the client side?). Do you have
any human perception data; to people even notice the 3% at this point?
(loading google seems remarkably fast!).  There's a very strong temptation
to bias for what's easy to measure here.

-- 
Colm

---

From: Jeffrey Walton <[email-masked]>
Date: Mon, 14 Mar 2016 17:16:56 -0400

>> problem. We are excited about TLS 1.3 supporting 0-RTT (or 0-RTT resumption)
>> and converting QUIC to use the TLS 1.3 handshake as a result.
>
> ...
> TCP in the works? (does TCPCT work on the client side?). Do you have any
> human perception data; to people even notice the 3% at this point? (loading
> google seems remarkably fast!).  There's a very strong temptation to bias
> for what's easy to measure here.

We also lack statistics on the other costs associated with security
failures. The best I can tell, we have no idea of the impact if its
not in US Financial.

I wrote to the United Nations and Human Rights Watch a while back, and
they don't appear to collect statistics on human rights violations
after incidents like Diginotar.

I can't help but wonder how many folks would agree to controls like
Public Key Pinning with Overrides or 0-RTT if their well being and
their family's well being were at stake.

Jeff

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 14 Mar 2016 14:32:38 -0700

On Mon, Mar 14, 2016 at 1:43 PM, Kyle Nekritz <[email-masked]> wrote:

> As others have said I do think adding client time solves much more than
> just this specific issue. Running a client nonce cache at scale also likely
> requires client time in order to limit the storage needed to a reasonable
> amount.
>
>
>
> I like the idea of including time since receiving the session ticket
> instead of absolute time. This allows for clients with high clock skew but
> still an accurate steady clock to use 0-RTT, and likely for tighter bounds
> to be placed on the time.  The natural place to put this would be the
> client hello, where it would be unencrypted, which would leak the time of
> ticket issuance. How concerning is this, is it worth encrypting this time?
>

My view of this is that we probably are going to eventually want client
EncryptedExtensions
(perhaps for ALPN as Ilari suggests). So, we might as well just add it and
stuff time
there.

-Ekr

>
> Kyle
>
>
>
> *From:* TLS [mailto:[email-masked]] *On Behalf Of *Martin Thomson
> *Sent:* Sunday, March 13, 2016 5:36 AM
> *To:* Erik Nygren <[email-masked]>
> *Cc:* [email-masked]
> *Subject:* Re: [TLS] Limiting replay time frame of 0-RTT data
>
>
>
> I do not see how the server can do this in general without client help.
> But the solution also addresses Brian's concern. The client doesn't need
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l2j4BjkO0Lc3u4CH2z7jPw&m=hKiQKAVn_GFQiKNtyPpO5SW6BjMTNV0jf6nb7qdIqxA&s=w1kyX4_66LehjWfy5-625X8MU8TX9JTSRIcgTlU6iqA&e=>
>
>
>
>
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l2j4BjkO0Lc3u4CH2z7jPw&m=hKiQKAVn_GFQiKNtyPpO5SW6BjMTNV0jf6nb7qdIqxA&s=w1kyX4_66LehjWfy5-625X8MU8TX9JTSRIcgTlU6iqA&e=>
>
>
>
>
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l2j4BjkO0Lc3u4CH2z7jPw&m=hKiQKAVn_GFQiKNtyPpO5SW6BjMTNV0jf6nb7qdIqxA&s=w1kyX4_66LehjWfy5-625X8MU8TX9JTSRIcgTlU6iqA&e=>
>
>

---

From: Ryan Hamilton <[email-masked]>
Date: Mon, 14 Mar 2016 17:44:19 -0700

> for, how do you manage that trade-off?

​My understanding is that QUIC's current 0-RTT scheme provides effectively
the same protection as TLS with perfect forward security, at least assuming
that session resumption is enabled. This is because, as I understand it,
even with PFS connections, and attacker who is able to compromise the
server and access the session resumption key can do bad things. In our QUIC
deployments, we limit the lifetime of the QUIC 0-RTT static secret to
roughly the lifetime of our session resumption key.

I confess, I am not an expert in this area and am relaying conversations
I've had in the past. I hope I'm not making a mess of them.

> to bias for what's easy to measure here.

​We have other data (which I don't think we've published, at least not in
that post) which shows that this improvement is definitely perceptible to
users. The improvements in response time are correlated with other metrics
showing that users notice the improvements and behave accordingly. When we
have screwed up 0-RTT (whoops, bug!) these metrics declined. Then when we
fixed it again, they recovered. ​I could go on for a long time about the
various A/B experiments we have run, but suffice to say we're very
confident that 0-RTT is a significant win.

Keep in mind that 3% for search represents *all* page views, not just those
that are the first on a connection, for which 0-RTT can be used. Many of
those page views are on long lived questions for which 0-RTT did not come
into plays, so the effect of 0-RTT on the page views which it sped up is
amortized across all views.

Hope that helps,

Ryan

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 14 Mar 2016 18:43:46 -0700

> roughly the lifetime of our session resumption key.

This is, I think, more or less true.

In general, against complete compromise of the server at time X, the
security is limited to whatever
long-term key was used to protect that data. Generally, this means that
tickets and static DHE
are comparable against server key compromise [0], so for this kind of
attack tickets and semi-static
DH are roughly comparable (indeed, you could imagine having the
configuration ID be an
encryption of the semi-static DH key under the ticket key making them
strictly comparable) [1].
The situation is obviously more complicated with attacks where you don't
have control of
the server (e.g., oracle-type stuff) and I suspect depends on the details
of the attack.

-Ekr

[0] As AGL points out, client key compromise is somewhat different.
[1] If you decide to instead store keying material on the server rather
than use tickets,
then TLS 1.3 PSK 0-RTT actually has somewhat better properties because you
can negotiate
a new key with each connection and establish a new "ticket", so the result
is that compromise
of the server is a future secrecy threat but not a threat to past
connections.

---

From: Bill Cox <[email-masked]>
Date: Mon, 14 Mar 2016 19:22:32 -0700

I am probably reading this wrong, but isn't the PFS problem with tickets
fixed in TLS 1.3?  In TLS 1.2, they were sent to clients before
ChangeCipherSpec, so given the server-side ticket encryption key, an
attacker could decrypt past tickets, and then use that data to decrypt past
sessions.

In TLS 1.3, tickets are sent after the full handshake completes, after
encryption is enabled for the connection.  Now, if an attacker has the
ticket encryption key, it is not possible to decrypt old connections.  Is
that right?  It looks to me like tickets have real PFS in TLS 1.3.

Bill

---

From: Martin Thomson <[email-masked]>
Date: Tue, 15 Mar 2016 13:25:58 +1100

> that right?  It looks to me like tickets have real PFS in TLS 1.3.

It's the properties of the session that matter here, not the tickets.

The tickets are sent in the clear in the resumed handshake.

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 14 Mar 2016 19:59:50 -0700

> The tickets are sent in the clear in the resumed handshake.

Right. As far as I can tell, that's required. TLS 1.3 PFS *is* much better
with
respect to tickets because the ticket established in connection N cannot
be used to decrypt that connection. In addition, because you can do
PSK-ECDHE,
you can confine the PFS risk to the 0-RTT data.

-Ekr