Subject: Review of draft-thomson-http-replay-latest

From: Victor Vasiliev <[email-masked]>
Date: Thu, 3 Aug 2017 13:54:51 -0400

First of all, I would like to thank the authors for taking up the work
of writing this draft; a well-defined application profile for use of
0-RTT in HTTP was for a long time something that everyone believed
should exist but no one actually worked on, and it's nice to finally see
it materialize.

Now, let's go to the most contentious point first.

## What does "early" mean?

The profile does not define whether a single request can span from early
to non-early data, or whether, say, a single HTTP/2 frame can cross that
boundary (for TLS 1.3 over TCP).

In general, there are two world views possible here:
* Being "early" is an inherent property of data transmitted over TLS,
  with some data being inherently marked as "early" by virtue of being
  transmitted using early data keys.
* Being "early" is a temporal property of the data; the data is early
  until the server receives a liveness proof from the client.
(this is so far without taking into account relays)

Both of those viewpoints provide the same level of security guarantee,
specifically, the server can determine whether the data received is a
potential replay or not.  I would personally like advocate for the
second model, due to following:
1. This approach works well for QUIC case where the boundary between
   early and regular data may not be well-defined (for instance, early
   data packet can be retransmitted with normal key, leading to early
   and non-early data being interleaved).
2. This approach allows the server to buffer up the request until the
   ClientHello is received in order to process it; if you believe in the
   first approach, this does not make sense since the early data is
   always early, and your only option is to always reject the request.
3. This approach allows the intermediary to retry the request after
   receiving 4NN from backend and liveness proof from the client, saving
   some time (more below).
4. There is no changes to parsing wire format required, since the
   liveness information is communicated to the application layer through a
   separate channel (liveness check function).

## Intermediaries

The proposed Early-Data header scheme is solid, and seems to me like the
only reasonable approach to solve the problem of interaction between the
intermediaries and 0-RTT.

The semantics of the header is currently tied to the first approach, the
one where being "early" is the property of the data itself.  This could
be easily avoided by shifting the definition to the one based on desired
security semantics instead of a particular mechanism: the header should
be defined as "indication that the intermediary believes the request
could potentially be a 0-RTT replay".  I would also rename it to
something like Not-Replay-Safe.

4NN error code should specify that the server must not process the
request if it actually receives, and in general should have same
semantics as HTTP/2 REFUSED_STREAM (I expect the user agents to
implement them at the same place).

I believe that with semantics above it should be safe for intermediaries
retry requests on 4NN.  This potentially saves the time it takes to
process the request, from two full round-trip times between the client
and the server to one full round-trip time plus largest of {RTT between
client and intermediary, RTT between intermediary and server}.  This, of
course, can be done only if the intermediary did not receive Early-Data
header from upstream, which is why it's important for the clients to not
send Early-Data header.

## Pull request 25

So far, this has been a review of latest editor's copy of the draft.
There is also https://github.com/martinthomson/http-replay/pull/25

I believe that this pull request should not be adopted.  There is no
good justification for drastic change of the proposed application
profile (neither in text nor on the mailing list), and the attacks
suggested are retry attacks and not replay attacks.  The reasoning
behind the change is extremely dangerous, as it seems to imply that
Early-Data header could protect the clients from retry attacks, which it
cannot.  Commenters on this list have already pointed out that the
similar class of retry attacks works with TLS 1.2.

## Minor points

"replays are under the control of an attacker, and are therefore
malicious" -- I am not sure "malicious" is the right word here; retries
can be also attacker-induced.  The important distinction is that replays
can be done in much greater quantity and without the client's knowledge.

## Summary

This draft is a very solid starting point, and I support its adoption
as-is (and oppose its adoption if #25 is merged).

I am grateful to Martin, Mark and Willy for taking on this essential
work.  I encourage the authors to converge on a stable header format and
error code sooner rather than later, since wide adoption of 0-RTT is
likely to happen fairly soon.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 4 Aug 2017 10:50:43 +1000

Thanks for the feedback Victor.

> boundary (for TLS 1.3 over TCP).

That's a mistake.  It was in an early draft and got removed.  I opened
https://github.com/martinthomson/http-replay/pull/28 for this.

> (this is so far without taking into account relays)

This second model is actually what we arrived at, but likely failed to
articulate well.

However, I think that you need to at least recognize the first model
to be entirely safe.  As I noted in #28 above, even if the handshake
completes, it doesn't mean that the once-early data is entirely safe.
This goes back to the need for consistent handling.

> something like Not-Replay-Safe.

In practice, this won't do anything other than change the name.
Keeping the focus on mechanics makes this somewhat more concrete, I
think.

> implement them at the same place).

Right.

> header from upstream, which is why it's important for the clients to not

Opened https://github.com/martinthomson/http-replay/issues/29 - I'll
work on a proposal.

> I believe that this pull request should not be adopted.

I have closed that PR based on this (and other) feedback.

> can be done in much greater quantity and without the client's knowledge.

https://github.com/martinthomson/http-replay/pull/30 - I think that
the point about greater quantity is largely addressed by the
mitigations that TLS now mandates.

---

From: Victor Vasiliev <[email-masked]>
Date: Fri, 4 Aug 2017 01:53:44 -0400

On Thu, Aug 3, 2017 at 8:50 PM, Martin Thomson <[email-masked]>
wrote:

> to be entirely safe.

I do recognize this.

> As I noted in #28 above, even if the handshake

I am not sure I can read that from #28, I seem to read it as the opposite?
I might be confused here.

I am not sure I understand in which sense it's not safe.

> This goes back to the need for consistent handling.

Could you elaborate on the concept of consistent handling?  I've read #27,
and I still can't quite understand what problem you are trying to solve.

> Keeping the focus on mechanics makes this somewhat more concrete, I

Agreed.

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 4 Aug 2017 15:07:42 +0900

> I am not sure I understand in which sense it's not safe.

(Stated below is my understanding and it could be wrong, but)

Consider the case a server uses strike register to protect against
0-RTT replay attacks. If a server misidentifies a request sent using
0-RTT data to be confirmed by ClientFinished, there is a chance that
such protection would fail.

Rereading the draft, could it be the case that the fact that the use
of strike-register is never discussed in the document even though
other methods (e.g., unconditionally send 4NN, buffer the 0-RTT data
until ClientFinished) are being mentioned is causing confusion?

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Fri, 4 Aug 2017 16:21:02 +1000

> I am not sure I understand in which sense it's not safe.

The problem I'm concerned about is the one that Subodh described, one
where you have two connections:

1. a completed handshake where the server processes the request on the
assumption that it is safe to do so (because it is now past the
handshake)

2. a replayed handshake where the server processes the request
differently prior to the handshake completing

If the processing in 1 wasn't cognizent of the potential for 2, the
server might leak information in its processing at 1 (for instance, by
making decisions based on the results of the processing that happened
at 2).

An example: say that the processing involved an idempotent update of a
stored value.  That's safe to do before the handshake is complete if
that is all that happens.  However, this request might produce a
response that is still non-idempotent.  If the value changes, the
server might echo the previous value in the response.  The processing
seems safe to do immediately - on its own it would be idempotent - but
the response generation isn't (the presence or absence of the previous
value exposes information through the length of the message), which
demonstrate that the logic is flawed.  Even deferring response
generation until after the handshake completes, if the information
that it acts on was generated before the handshake.

That's the sort of understanding I wanted to convey with #28.  That
is, without going too much into detailed examples like that.

> and I still can't quite understand what problem you are trying to solve.

I probably got this confused with a separate issue there.  Consistent
handling is more to prevent inadvertent creation of leaks when
processing a request.  If requests are sometimes processed by nodes
and deferred until handshake completion by other nodes, then the nodes
that process the requests expose information.  For the replay defenses
to be effective (either delay or 425), the application of those
defenses needs to be consistent across all nodes.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 4 Aug 2017 16:52:37 +1000

> defenses needs to be consistent across all nodes.

Let me walk this back a little.  I sat down and tried to see how
inconsistent application of the defenses could be exploited and I drew
a blank.  It looks like the concerns here largely devolve to whether
actions taken have side-effects.

We could probably simplify the position then and say that if the
request is safe to process, then that needs to be constant - different
nodes at different times can't reach different conclusions.  That's
the consistency we need.  If we don't have that, then an attacker can
go shopping for someone to exploit.

I think that there is still some value in #27 in terms of explaining
some of the corner cases, but that probably needs to be redistributed
throughout the remainder of the document.  The core is in the simple
statement.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 4 Aug 2017 10:43:35 +0300

> such protection would fail.

That depends on what happens on if 0-RTT strike register check fails:

- Rejecting the entiere connection is safe (allowed if strike register
  is not probablistic).
- Rejecting 0-RTT is safe.
- Rejecting the request is unsafe.
- Auto-retrying the request is unsafe.

The above impiles that there should not be HTTP-level strike registers
for 0-RTT. Thus, each 0-RTT request, including replayed ones, should be
processed independently, with one of three different dispositions:

- Handle immediately
- Wait for ClientFinished
- Reject immediately

And first and last two interpretations must not be mixed for the same
request.

However, that there should not be 0-RTT strike registers at HTTP level
does not imply that there should not be HTTP-level request strike
registers, but those strike registers need to span both 0-RTT and 1-RTT
in order to combat retries, not just replays.

The usefulness of TLS-level strike register is being a fast first
pass, filtering down the potential torrent of events into a manageable
stream. Handling such torrent directly is very difficult, and easily
exposes the application for timing or denial-of-service attacks.

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Fri, 4 Aug 2017 17:58:28 +1000

> And first and last two interpretations must not be mixed for the same

This is the consistency that I was looking for, thanks for restating this.

FWIW, I also have convinced myself that both reject and delay can be
used interchangeably to get the same basic correctness guarantee we're
looking for.

> in order to combat retries, not just replays.

I share this view.  TLS does what it can to prevent replay, but the
ultimate defense (if you ever want to handle 0-RTT, or ever really) is
to have anti-replay/de-duplication at the level of the request.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 4 Aug 2017 11:07:12 +0300

> to have anti-replay/de-duplication at the level of the request.

Given how eager browsers are to retry requests (and some UI gotchas
that cause duplicate requests), one already needs to have request-level
deduplication if the application is meant to be accessed from browsers.

-Ilari

---

From: Victor Vasiliev <[email-masked]>
Date: Fri, 4 Aug 2017 15:58:25 -0400

> go shopping for someone to exploit.

I am fine with requiring the resource having to be either always safe, or
always unsafe, including:
 1. Requiring this to be consistent across small-term timescales, and path
    through which the request gets processed.
 2. Banning resources which process the same request differently based on
    whether it was received through 0-RTT or 1-RTT ("processing" here means
    not rejecting).

I assume this means we no longer need to be able to find the early data
boundary
on the wire?

---

From: Martin Thomson <[email-masked]>
Date: Mon, 7 Aug 2017 09:27:38 +1000

On 5 August 2017 at 05:58, Victor Vasiliev <[email-masked]> wrote:
> boundary on the wire?

Strange how these things progress...  I think that I'd like to hear
what Ben thinks.  I can't think of a reason for this right now.

(Clarity about the status of things is still probably desirable, but
it seems that we don't have a concrete requirement that would make it
mandatory.)

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 7 Aug 2017 16:02:55 -0500

> it seems that we don't have a concrete requirement that would make it

I think I've lost track of some of the reasoning in the previous
messages, so I had to try to re-derive some of it.

If I'm reading correctly, it's now being claimed that the important
property to retain is that the answer to the question "is this request
safe to respond to before the client is 'authenticated'?" must be
consistent across all nodes.  This is in the context of the previous
analysis which considered three possible options for a given 0-RTT request:

- Handle immediately
- Wait for ClientFinished (only available when Early-Data header is absent)
- Reject immediately

with the claim that reject and delay are in some sense equivalent, in
terms of the safety of the request.  So, combining the two statements we
would find that, for a given (HTTP-level?) request, all nodes must
either handle it and reply immediately, or take the other option.  (The
"other option" being, "pick one of 'reject immediately' and 'wait for
ClientFinished' (if applicable)".)

An interesting follow-up question is what the desired/permitted behavior
is when a node is under attack.  Luckily, the TLS 1.3 spec has forbidden
the use of just the timestamp check that would allow trivial replay
floods of captured packets, but an attacker could still be generating
new repeated 0-RTT requests of their own.  A node under attack clearly
has the option of rejecting 0-RTT entirely at the TLS layer, but do we
want it to also be able to shunt off "expensive" HTTP requests at the
HTTP layer?  If so, that seems in contradiction to the above requirements.

For the sake of argument, I'll proceed on the assumption that we want to
preserve this HTTP-level invariant and make TLS-layer 0-RTT reject the
only way to shed load while under attack.

Anyway, if we take as assumptions that all nodes consistently classify
requests as 0-RTT-safe/unsafe, and the further (natural) restriction
that the reply contents do not differ when handled as 0-RTT or handled
as 1-RTT, then there does not seem to be a reason to need the early data
boundary on the wire (as opposed to just the boolean "is the handshake
done?") -- safe requests always get a reply, and it's the same reply no
matter what.  Unsafe requests can get rejected or processed depending on
the handshake-done boolean, and nothing needs the "was any of this
request early data?" information.

I've also tried to think about what an attacker can do with delaying
traffic and/or replaying 0-RTT.  There doesn't seem to be much that the
attacker can do that's qualitatively different from observing the
ClientHello+0-RTT and replaying it at a different node, though.  So, I
think I agree with you (Martin + Victor), and the early data boundary on
the wire is probably not needed.

I'm sure we'll see problems with servers (and clients, I suppose) making
the wrong decision about requests being safe or not, but there's only so
much we can do about that in the spec.

-Ben

---

From: David Benjamin <[email-masked]>
Date: Mon, 07 Aug 2017 22:07:16 +0000

On Mon, Aug 7, 2017 at 5:08 PM Benjamin Kaduk <[email-masked]> wrote:

> On 5 August 2017 at 05:58, Victor Vasiliev <[email-masked]> <[email-masked]> wrote:
>
> I think I've lost track of some of the reasoning in the previous messages,
> so I had to try to re-derive some of it.
>
> property to retain is that the answer to the question "is this request safe
> to respond to before the client is 'authenticated'?" must be consistent
> across all nodes.  This is in the context of the previous analysis which
> considered three possible options for a given 0-RTT request:
>
> - Handle immediately
> would find that, for a given (HTTP-level?) request, all nodes must either
> handle it and reply immediately, or take the other option.  (The "other
> option" being, "pick one of 'reject immediately' and 'wait for
> the use of just the timestamp check that would allow trivial replay floods
> of captured packets, but an attacker could still be generating new repeated
> 0-RTT requests of their own.  A node under attack clearly has the option of
> rejecting 0-RTT entirely at the TLS layer, but do we want it to also be
> able to shunt off "expensive" HTTP requests at the HTTP layer?  If so, that
> seems in contradiction to the above requirements.
>

To make sure I'm understanding you correctly, the scenario here is a server
is sufficiently under load that it would like to request a round-trip from
the peer before responding to GET /expensive_thing?

If the server is really overloaded, it can send HTTP 503. But I'm guessing
503 triggers a sharper client back-off than you like in this
scenario. Perhaps you're only sort-of-overloaded and retrying at 1-RTT is
fine? As you say, a sort-of-overloaded server could reject 0-RTT at the TLS
level instead. Though perhaps you have GET /cheap_thing that you are still
willing to respond to.

In that case, using one of the second two options seems fine to me. Perhaps
the consistency rule needs to be a bit more nuanced: It is always okay to
take an unsafe request and make it safe (either by waiting or 4xx) before
responding. But if you wish for certain kinds of requests to only be
handled safely, you had better consistently do this! If you're just trying
to deal with load, doing either is fine.

I don't think this would invalidate any of the rest of the reasoning.

> preserve this HTTP-level invariant and make TLS-layer 0-RTT reject the only
> way to shed load while under attack.
>
> requests as 0-RTT-safe/unsafe, and the further (natural) restriction that
> the reply contents do not differ when handled as 0-RTT or handled as 1-RTT,
> then there does not seem to be a reason to need the early data boundary on
> the wire (as opposed to just the boolean "is the handshake done?") -- safe
> requests always get a reply, and it's the same reply no matter what.
> Unsafe requests can get rejected or processed depending on the
> handshake-done boolean, and nothing needs the "was any of this request
> early data?" information.
>

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 7 Aug 2017 18:05:22 -0500

On 08/07/2017 05:07 PM, David Benjamin wrote:
>
>     An interesting follow-up question is what the desired/permitted
>     behavior is when a node is under attack.  Luckily, the TLS 1.3
>     spec has forbidden the use of just the timestamp check that would
>     allow trivial replay floods of captured packets, but an attacker
>     could still be generating new repeated 0-RTT requests of their
>     own.  A node under attack clearly has the option of rejecting
>     0-RTT entirely at the TLS layer, but do we want it to also be able
>     to shunt off "expensive" HTTP requests at the HTTP layer?  If so,
>     that seems in contradiction to the above requirements.
>
>
> To make sure I'm understanding you correctly, the scenario here is a
> server is sufficiently under load that it would like to request a
> round-trip from the peer before responding to GET /expensive_thing?
>

Right.

-Ben

> If the server is really overloaded, it can send HTTP 503. But I'm
> guessing 503 triggers a sharper client back-off than you like in this
> scenario. Perhaps you're only sort-of-overloaded and retrying at 1-RTT
> is fine? As you say, a sort-of-overloaded server could reject 0-RTT at
> the TLS level instead. Though perhaps you have GET /cheap_thing that
> you are still willing to respond to.
>
> In that case, using one of the second two options seems fine to me.
> Perhaps the consistency rule needs to be a bit more nuanced: It is
> always okay to take an unsafe request and make it safe (either by
> waiting or 4xx) before responding. But if you wish for certain kinds
> of requests to only be handled safely, you had better consistently do
> this! If you're just trying to deal with load, doing either is fine.
>

---

From: Martin Thomson <[email-masked]>
Date: Tue, 8 Aug 2017 14:39:13 +1000

On 8 August 2017 at 08:07, David Benjamin <[email-masked]> wrote:
> 503 triggers a sharper client back-off than you like in this scenario.
> Perhaps you're only sort-of-overloaded and retrying at 1-RTT is fine? As you
> say, a sort-of-overloaded server could reject 0-RTT at the TLS level
> instead. Though perhaps you have GET /cheap_thing that you are still willing
> to respond to.

I think that the advice we give there is that if you *might* send a
different response from different nodes, then 503 isn't right and 4NN
(Too Early) is better, even if it means less backing off.

You could probably make a case that returning 503 is consistent - it
depends on server state that is independent of whether the request is
replayed.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 8 Aug 2017 07:41:00 +0200

> depends on server state that is independent of whether the request is

With that said, I think we could suggest that a client should possibly
stop using 0-RTT for a while with a server exhibiting 5xx responses or
connection resets, because this means the server is unreliable or
possibly overloaded and 0-RTT may participate to increase this load if
the server has to respond 4NN a lot (ie it is required to process twice
the amount of requests).

Willy