Re: [TLS] Dropping "do not stick out" from ECHO

Nick Sullivan <nick@cloudflare.com> Mon, 23 March 2020 17:40 UTC

Return-Path: <nick@cloudflare.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DEC863A0D74 for <tls@ietfa.amsl.com>; Mon, 23 Mar 2020 10:40:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.com
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 D5zs9mYLWVUS for <tls@ietfa.amsl.com>; Mon, 23 Mar 2020 10:40:17 -0700 (PDT)
Received: from mail-vs1-xe2c.google.com (mail-vs1-xe2c.google.com [IPv6:2607:f8b0:4864:20::e2c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 854453A0D36 for <tls@ietf.org>; Mon, 23 Mar 2020 10:40:17 -0700 (PDT)
Received: by mail-vs1-xe2c.google.com with SMTP id d18so1413688vso.7 for <tls@ietf.org>; Mon, 23 Mar 2020 10:40:17 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=OXHhG9ZSYIYqNp3XlyMkZmiZSRs8zVVIiZ6B956Go70=; b=xDJjcdGWqK9cWfFmd5ASIz5p5nyiERTB6yUWE7g72ehqjOJhRqdXcRsiofcDlYEhx1 jQWp5JgdFxqhFvb4HqEezV7yhphHUQWGnpRP/PJAu3R+2rjgt6MutzSjRa964kMxamNb TnrzCS4T+qdZxBVno/TpxTb2I9dVGtyMNiPDU=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=OXHhG9ZSYIYqNp3XlyMkZmiZSRs8zVVIiZ6B956Go70=; b=lU2Uqe+Uoh9Rad1/5I97mgK0mbQhs1JXNxmL0x2mG++aCZw22FV8gbLSMsNomCZypR 860APMDl/PMZp4vRpDQL/Lm9GfAB/9RF66iFgDZwQG9zoCdC0UGFBnlOePWAOOx090ND QNRzog5oPjmPHWGyTpYgV1rVSCwLjN44CXU6dY4DhcgRR0cv9ZpFQJNy6hii4Riw5TlW VPkRX/Ih9XKdse8gInte5fRV0RRKl65sCPHgQH7ScLeQncvcItjKP/sQi33MIlz+jR2c ugYlZytQBH912fyh/QzaXOrIXe2wPrmig9+ScP9KQeJI+imsB/62hirDsZCBCioE4KF1 gtVg==
X-Gm-Message-State: ANhLgQ3XLYTm/fybs3DiljNzxbunTxU4jWYq7CEZRzG8nA3bXxSTY1L+ RuU6V0kuyZ/RSZq/RK4L5cUpbh2ehPyf3TMYERE+hhbkwuj+jA==
X-Google-Smtp-Source: =?utf-8?q?ADFU+vsLcfBIeEwu5cbv2FSOMi14uafG111zsNVzkp7h?= =?utf-8?q?7W7KtCmGccl0ubfM1IOQpIteBdzSYGQTbSKMVGBlbSQXsS8=3D?=
X-Received: by 2002:a67:c78b:: with SMTP id t11mr15854619vsk.212.1584985216230; Mon, 23 Mar 2020 10:40:16 -0700 (PDT)
MIME-Version: 1.0
References: <EB7DEE42-8EC4-4347-BA10-0EBF90CBF398@heapingbits.net> <CAFDDyk8U7R9ROizUMQebC_r+bnNQi8XbCc1qyHgmqMvA-WKTUg@mail.gmail.com> <7b575c92-894d-4fc8-998d-a55fc0ddb450@www.fastmail.com>
In-Reply-To: <7b575c92-894d-4fc8-998d-a55fc0ddb450@www.fastmail.com>
From: Nick Sullivan <nick@cloudflare.com>
Date: Mon, 23 Mar 2020 10:37:55 -0700
Message-ID: <CAFDDyk_KhuzM6HQQJ==1WM1Wo65XcbrfRU8otApRBHz1wg+eiQ@mail.gmail.com>
To: Christopher Wood <caw@heapingbits.net>
Cc: "TLS@ietf.org" <tls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000c9d39e05a18920d1"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/-z46nl46dopsoyINRwXYkLu01EU>
Subject: Re: [TLS] Dropping "do not stick out" from ECHO
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.29
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: <https://mailarchive.ietf.org/arch/browse/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 2020 17:40:39 -0000

Replies inline again.

On Mon, Mar 23, 2020 at 8:40 AM Christopher Wood <caw@heapingbits.net>
wrote:

> Trying to reply succinctly inline below!
>
> On Mon, Mar 23, 2020, at 3:54 AM, Nick Sullivan wrote:
> > I have reservations.
> >
> > On Sun, Mar 22, 2020 at 9:54 AM Christopher Wood <caw@heapingbits.net>
> wrote:
> > > One of the original motivating requirements for ECHO (then ENSI) was
> "do
> > >  not stick
> > >  out" [1]. This complicates the current ECHO design, as clients must
> > >  trial decrypt
> > >  the first encrypted handshake message to determine whether a server
> used
> > >  the inner
> > >  or outer ClientHello for a given connection. It's also trivial to
> probe
> > >  for ECHO
> > >  support, e.g., by sending a bogus ECHO with the same key ID used in a
> > >  target client
> > >  connection and checking what comes back.
> >
> > Do you mean that it’s trivial for an attacker to probe a server for
> > ECHO support or whether it’s trivial to check if a given connection
> > used ECHO or not?
>
> In the current design: both.
>
> > In the current draft it seems trivial to identify servers that support
> > ECHO by:
> > - querying DNS and seeing whether the record exists
> > - connecting to the server with an ECHO extension that has a random key
> > ID and ECHO ciphertext and checking if the server returns “retry_keys”
> > (yes means ECHO support)
> >
> > Both of these can be done without observing a specific connection.
>
> Agreed. I think we should assume that attackers know which servers support
> ECHO and which do not.
>
> > If we’re talking about “don’t stand out,” would it be fair to consider
> > the attack you hinted at above as an active attack to identifies
> > whether a given connection used ECHO or not (3b in Ben’s email)? If so,
> > it points to a weakness in the current protocol description that could
> > be remedied.
>
> It's definitely an active attack. I don't disagree that it's possible to
> fix. What I am concerned with is the cost of fixing it.
>
> > Here are three scenarios:
> >
> > Client connects to confirmed ECHO-enabled server with valid key:
> > 1) client connects to server using an ECHO extension created with a
> > valid key ID and a valid ciphertext for that ID
> > 2) server responds with handshake encrypted using the inner CH
> >
> > Client connects to confirmed non-ECHO-enabled server with GREASE:
> > 1) client connects to server using an ECHO extension with a random
> > invalid key ID, and an invalid ciphertext
> > 2) server responds with handshake encrypted using the outer CH, no
> > retry_keys
> >
> > Client connects to ECHO-enabled server with GREASE (say DNS was
> > blocked):
> > 1) client connects to server using an ECHO extension with a random
> > invalid key ID, and an invalid ciphertext
> > 2) server responds with handshake encrypted using the inner CH, sends
> > default cert and retry_keys
> >
> >
> > For these scenarios, the attacker collects the handshakes and key IDs,
> > and wants to determine which is which. The attacker then probes the
> > servers with three connections:
> >
> > A. client connects to ECHO-enabled server using an ECHO extension with
> > a valid key ID (taken from a connection), and an invalid ciphertext
> >
> > The server will match the key ID and return “decryption_error” when the
> > ECHO ciphertext fails to decrypt.
> >
> > B. client connects to ECHO-enabled server using an ECHO extension with
> > an invalid key ID (taken from a GREASE connection), and an invalid
> > ciphertext
> >
> > The server will respond with handshake encrypted using the outer CH,
> > including retry_keys.
> >
> > C. client connects to non-ECHO-enabled server using an ECHO extension
> > with a the invalid key ID (taken from a GREASE connection), and an
> > invalid ciphertext
> >
> > The server will respond with handshake encrypted using the outer CH.
> >
> >
> > All three are distinguishable. This lets the attacker know whether a
> > given connection actually used ECHO (outer handshake) or GREASE for an
> > ECHO -enabled site. This shows that we don’t currently have property 3a
> > from Ben’s reply.
> >
> > A simple way to eliminate this oracle would be for the server to treat
> > ECHOs that have valid IDs but are corrupted or don’t match the outer CH
> > differently: treat them as GREASE handshakes and respond using the
> > outer CH and retry_keys. This would make the results from A and B
> > indistinguishable.
> >
> > Given this modification, is there still an active attack to determine
> > if a specific connection used the outer or inner CH?
>
> Yep -- David's attack still applies. If the outer CH has no ciphersuites
> and the connection succeeds, then the inner CH was  used.
>

This malleability seems troublesome. My position has been that with
ECHI/ESNI, we are introducing a new threat model into TLS, one in which the
handshake no longer protects high-entropy secrets, but also low-entropy
secrets. With low-entropy secrets, the risks of oracles from taking chunks
of the handshake and plugging them into different flows is high, so
malleability is a risk. My intuition here is that having malleability also
makes the analysis (say, with Tamarin) much more complex.

> Does David Benjamin’s cut-and-paste attack still work if the cipher
> > list in the inner client hello is just a pointer to the cipher list in
> > the outer client hello?
>
> Not that specific one. But we probably shouldn't pick and choose which
> things we need to bind, as that was problematic in past designs. Instead,
> we would probably need to bind the entire outer CH to the inner CH. (The
> current design has the machinery to do this: export a PSK from the HPKE
> context and use it to compute a binder over the outer CH.)
>

We have a binding mechanism right now, OuterExtensions.hash. In the default
case where inner and outer cipher lists are the same, the inner cipher list
will be a pointer to the outer cipher list with a hash. Any modification of
the outer extensions will result in a different OuterExtensions.hash,
causing the ECHO extension to become invalid. I'm not saying that this is
the only attack of the type, but that we do have a binding mechanism that
defends against it.

The OuterExtensions feature is a weak binding mechanism, though. It only
applies to extensions that are identical for both inner and outer CH. I
would be (again) in favor of exporting a PSK from the ECHO and using it as
a binder for the outer client hello. You mentioned that this may be too
much juice to squeeze, but is it? The only conflict I can see with TLS 1.3
is during resumed connections, in which two binders need to be verified,
which doesn't seem like a big deal since binders already cover each other.
Having a binder over the outer handshake also removes the need for the
additional overhead of the OuterExtensions.hash.

I consider both active and passive blocking to be threats since both
in-line (middlebox blocks on known extension) and probe-based post-hoc
blocking (middlebox replays client hello to see certificate) are both
deployed in middleboxes today. With a PSK binder and the proposed mechanism
above (always fall back to retry_keys if the ECHO extension or the binder
is corrupt), I don't see a mechanism for an attacker to test whether the
inner or outer CH was used for a given connection. Still, I'd like to see a
proof of this from the theoreticians. Adding an explicit signal on the wire
seems like a very bad choice since it makes inline blocking trivial (and
likely!), which could hinder the ability to ramp up deployment.

Upgrading from a widely deployed blockable solution to a non-blockable
solution seems like it will be challenging. We should fix this now rather
than later.


> > >  I propose we remove this requirement and add an explicit signal in SH
> > >  that says
> > >  whether or not ECHO was negotiated. (This will require us to revisit
> > >  GREASE.)
> >
> > A downside of this modification is that ECHO is no longer able to be
> > used by existing TLS 1.3 servers without modification.
> >
> > One of the neat features of ECHO is that a a server-controlled proxy
> > that only has access to ESNI keys can determinate which client hello to
> > use (inner vs. outer). This allows a shim proxy to decrypt ECHO (or
> > fail to) and send a singular CH on to the real server running
> > unmodified TLS 1.3 software. This modularity opens up a massive
> > opportunity for the large TCP load balancing providers out there with a
> > lot of IP space to enable ECHO for legacy applications without needing
> > access to their private key. Having a signaling extension in the
> > handshake eliminates this deployment scenario (one that CF is currently
> > exploring).
> >
> > Of course, without modifying the server, ECHO is less effective since
> > it won’t be possible to apply padding to the server’s portion of the
> > handshake. However, being able to deploy ECHO as an independent proxy
> > service is something I consider a huge plus of the current design. We’d
> > be losing it by adding a new signaling extension.
>
> Admittedly, this is a nice feature. However, I don't have confidence in
> its efficacy without server-side changes. (This is probably worth a
> separate thread.)
>

What do you mean by efficacy? Once we have a PoC of an ECHO load balancer,
I'd be happy to share it.

>
> Thanks!
> Chris
>