Re: [TLS] 0-RTT and Anti-Replay

Andrey Jivsov <crypto@brainhub.org> Mon, 23 March 2015 00:59 UTC

Return-Path: <crypto@brainhub.org>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 77A5C1A872A for <tls@ietfa.amsl.com>; Sun, 22 Mar 2015 17:59:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id voDRdMl9Myq1 for <tls@ietfa.amsl.com>; Sun, 22 Mar 2015 17:59:48 -0700 (PDT)
Received: from resqmta-po-06v.sys.comcast.net (resqmta-po-06v.sys.comcast.net [IPv6:2001:558:fe16:19:96:114:154:165]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 86EE91A8726 for <tls@ietf.org>; Sun, 22 Mar 2015 17:59:48 -0700 (PDT)
Received: from resomta-po-10v.sys.comcast.net ([96.114.154.234]) by resqmta-po-06v.sys.comcast.net with comcast id 6ozM1q00153iAfU01oznC3; Mon, 23 Mar 2015 00:59:47 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by resomta-po-10v.sys.comcast.net with comcast id 6ozm1q00B4uhcbK01ozmTU; Mon, 23 Mar 2015 00:59:47 +0000
Message-ID: <550F6582.9040602@brainhub.org>
Date: Sun, 22 Mar 2015 17:59:46 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: tls@ietf.org
References: <CABcZeBP9LaGhDVETsJeecnAtSPUj=Kv37rb_2esDi3YaGk9b4w@mail.gmail.com>
In-Reply-To: <CABcZeBP9LaGhDVETsJeecnAtSPUj=Kv37rb_2esDi3YaGk9b4w@mail.gmail.com>
Content-Type: text/plain; charset="windows-1252"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1427072387; bh=T7gMwz8obiOTuI3j8sP0GLny6o/i8xhG1fQ5gllBzgs=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=MzrmdfG0EPZnWi7t78cohdNVncEr0V2rpgTT0hbtxyHJU3ZCYLnUBlfrVuA4+NhvG 7JRbbXIZ6xJzOIt86dv8ghKMdGGezeSwRinPCuG4u/X/Hhx8w/oOV7xEkGFytQMohJ n+KfnfAVCIg/EVVtpi5a4n7UiS9+eRKZFaOcQNN2EsXAzI0XGXzrOOytAdIk6zVuiN cw289FUmXF36aDNRWgg4gS+mIRK0ragwXinkd3TmQplX3ByVllh+55AAkx/+n41dZd dppcrNxaAvZekOUj9nfGf/dgE4aOoQ24BgumkXpQt1igOImVrMwQpaZ9V6BOXHfcEr SMtQnMbgde6Aw==
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/GhWknqlMxHRwUv9QewMEycHxeLw>
Subject: Re: [TLS] 0-RTT and Anti-Replay
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 23 Mar 2015 00:59:51 -0000

On 03/22/2015 02:49 PM, Eric Rescorla wrote:
> 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

I think what you are proposing here is to treat a mismatch in 0-RTT 
parameters as "re-negotiate", similar to the SessionID-based reuse logic.

See more below.

> 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.

The SessionID-like fallback is a problem for a "broadcast" of the single 
"POST /buy-something" (via a replay of a captured message). Had the 
Server 2 above rejected the ClientHello [+0-RTT] which was intended for 
Server 1 (orbit1), there would be no problem.

One way to solve this is to say that the server must *fail* 0-RTT, as 
opposed to fallback to 1-RTT, if the "orbit" indicated in the 
ClientHello is not that of this server.

The only requirement here is that the server always knows its orbit. 
Servers must have different orbit IDs if they cannot handle simultaneous 
receipt of identical "POST /buy-something".

Regarding the forced server reboot. The practical issue here, it seems, 
is that it's difficult to keep the state of the global purchasing DB 
updated, so that the HTTP requests issued (replayed) simultaneously to 
servers across the globe are verified. This is less of a problem when 
TLS pins the request to the same copy of the local DB, identified by 
orbit ID.


>
>
> 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.
...