[TLS] 0-RTT and Anti-Replay

[Eric Rescorla <[e-mail]>]

In the interim in Seattle, we had an extensive discussion of 0-RTT
anti-replay in which DKG observed that all the proposed anti-replay
mechanisms provide limited protection. The underlying problem is the
desire to present a uniform interface in which the calling application
can count on reliable delivery of the data it provides in the first
flight, thus requiring the TLS stack to retransmit it automatically.

This message describes the problem and should set us up for a
discussion about the topic in Dallas. Apologies in advance for
the length of this, but I'd like to be clear.


BACKGROUND: ANTI-REPLAY
As you'll recall, TLS ordinarily uses a server-provided random value
mixed into the keys for anti-replay. This obviously doesn't work for
0-RTT. For reference, here's a simplified description of the way that
(and the way that both QUIC and snap-start do it).

- The server keeps a list of every ClientRandom it has received
  within a given time window keyed by a server context ("orbit")
  value that loosely can be thought of as indicating the data center.

- When the server receives a new ClientHello, it checks to
  see if it has seen it before and then rejects the connection.

Now consider what happens when the server reboots and loses its
state. You don't want to reject every client 0-RTT connection so
instead what you do is you ignore the client's initial data sent in
the first flight. Since the ServerHello provides a new Random value,
any data the client sends in subsequent flights has the usual
anti-replay protection.


A SOMEWHAT CONTRIVED ATTACK
This is all fine so far, but the abstraction you probably want TLS to
supply to the application is that the data it sends in the first
flight isn't lost even in this case. In order to accomodate this, the
natural design is for the TLS stack to retransmit the plaintext in the
client's first flight as the first data it sends under the new keys.

An attacker can make use of this as follows. When the client sends
the initial first flight he captures the TCP connection and makes his
own TCP connection to the server, forwarding the first flight.

Client                        Attacker                          Server

ClientHello [+0-RTT] ------------>
"POST /buy-something" ----------->

                              ClientHello [+0-RTT] --------------->
                              "POST /buy-something" -------------->

                                                   [Processes purchase]
                                 <---------- ServerHello [accept 0-RTT]
                                                  (+ rest of handshake)


The attacker just discards the server's response and then the server
somehow forces the server to reboot (this is the hard part).

Once the server has rebooted, the attacker re-sends the client's
initial flight then just forwards data back and forth to the client.

Client                        Attacker                          Server
                              ClientHello [+0-RTT] --------------->
                              "POST /buy-something" -------------->

   <--------------------------------------  ServerHello [reject 0-RTT]
                                                 (+ rest of handshake)

Finished --------------------------------------------------------->
"Post /buy-something" -------------------------------------------->
                                                  [Processes purchase]

At this point, you've mounted a successful replay attack. Obviously
this is not that great an attack because it requires you to be able to
force a reboot and also get in under the client's timeout window.


A MORE REALISTIC ATTACK
During the interim meeting, DKG observed that you could produce the
same "I've forgotten my state" situation if you have a distributed
server. Say that the server operates in two loosely-synchronized
data centers. In that case, you can get the following situation
(shown without the attacker's intervention because of ASCII art
limitation

 Client             Attacker            Server1              Server 2

ClientHello [+0-RTT] -->
"POST /buy-something" ->

                    ClientHello [+0-RTT] -->
                    "POST /buy-something" ->

                                        [Processes
                                         purchase]



                    ClientHello [+0-RTT] ----------------------->
                    "POST /buy-something" ---------------------->


   <--------------------------------------  ServerHello [reject 0-RTT]
                                                 (+ rest of handshake)

Finished --------------------------------------------------------->
"Post /buy-something" -------------------------------------------->
                                                  [Processes purchase]

Again, the attacker will need to mess with the TCP channel, but their
ability to do so is part of our basic threat model [RFC 3552].

It's important to understand that this is a generic issue, not an
issue with TLS in particular, so it's not like there's some other
0-RTT model we can lift and put into TLS that would solve the problem.


APPROACHES
One way to address this would be to simply not provide a 0-RTT mode.
This is a charter item, so that would be sad, but obviously that's not
out of the question if we really think this is bad. The more serious
question is that there's an enormous demand for this feature (see, for
instance, the discussion at the SEMI workshop), and so if we refuse to
do a 0-RTT mode, we're giving applications the annoying choice of
accepting a RTT or inventing their own 0-RTT method.


There are a number of basic ways to address this issue, but I think
the main plausible[0] ones are:

1. Keep the server state globally consistent and also temporally
   consistent so that replays can always be detected.

2. Remove the TLS anti-replay guarantee for the data sent in the first
   flight and tell applications to only send data there that can
   tolerate being replayed.

3. Remove the TLS reliable delivery guarantee for the data sent in
   the first flight, so that the stack doesn't automatically replay it.

The first of these options (global state) is possible, but only in
some limited circumstances, namely very sophisticated operators and/or
situations where there's really only one server which has good state
management. An example of the latter is WebRTC, where the server can
have a different anti-replay context for each connection.

The other two options clearly require a separate API to handle this
special first-flight data and would require applications to handle it
separately. So, for instance, in option 2, you would have something
like:

    c = new TLSConnection(...)
    c.setReplayable0RTTData("GET /....")
    c.connect();

And in the case of option 3 you would have something like:

    c = new TLSConnection(...)
    c.setUnreliable0RTTData("GET /....")
    c.connect()
    if (c.delivered0RTTData()) {
       // Things are cool
    } else {
       // Try to figure out whether to replay or not
    }

So in the former case, the choice of replay is in the TLS
stack's hands but in the latter in the application's hands.

I would expect them to have relatively similar impacts on the wire,
namely applications would self-designate certain data as replay-safe
(e.g., HTTP GETs) and would send it in the first flight and then
either let the stack retransmit (option 2) or retransmit themselves
(option 3). This isn't that odd, since, as AGL observes, browsers
already routinely retry some HTTP requests that appear to fail even for
ordinary TLS (i.e., no HTTP response was received) so in those cases
they have already circumvented the anti-replay guarantees supplied by
TLS, but of course that's different from having TLS give up those
guarantees.


RECOMMENDATION
As I said, I think we do need to supply some sort of limited 0-RTT
functionality. Given the practical difficulty of making global state
work, I think it's a mistake to build a system which relies on
this. The remaining two options require that we relax one of TLS's
guarantees and of these, relaxing reliable delivery seems safer,
and it also makes the implementation rather easier.

Accordingly, I propose that we continue to develop 0-RTT but with the
server just dropping 0-RTT first-flight data when 0-RTT is not
possible (and of course telling the client it is doing so).  The
client application can then retransmit if it believes it is safe.
In the very limited cases where application domains can in fact
safely keep state, they can profile the use of TLS to that end
and require the endpoints to behave appropriately.

Thanks,
-Ekr


[0] One implausible approach is to treat any attempt to 0-RTT when
you have lost state as a hard-fail, but this will create a lot of
random failures, so it's not really practical.