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

From: "Christopher Wood" <[email-masked]>
Date: Sun, 22 Mar 2020 09:54:15 -0700

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.

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

What do others think?

Thanks,
Chris (no hat)

[1] 
https://tools.ietf.org/html/draft-ietf-tls-sni-encryption-09#section-3.4

---

From: Christian Huitema <[email-masked]>
Date: Sun, 22 Mar 2020 10:58:39 -0700

On 3/22/2020 9:54 AM, Christopher Wood wrote:

> One of the original motivating requirements for ECHO (then ENSI) was
> "do not stick
> 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

Section 5 of this draft says:

                                                              ... In
   practice, it may well be that no solution can meet every requirement,
   and that practical solutions will have to make some compromises.

   In particular, the requirement to not stick out presented in
   Section 3.4 <https://tools.ietf.org/html/draft-ietf-tls-sni-encryption-09#section-3.4> may have to be lifted, especially for proposed solutions
   that could quickly reach large scale deployments.

As part of AUTH48 changes, we agreed to add a line in section 3.4
pointing to this comment is section 5.

We can observe that ECHO already sticks out, because of the presence of
an unexpected encrypted field in the Client Hello. So in practice ECHO
deployment already relies on achieve large scale deployment, and
possibly greasing the encrypted parameter.

-- Christian Huitema

---

From: Jonathan Hoyland <[email-masked]>
Date: Sun, 22 Mar 2020 21:48:32 +0000

I'm worried that it'll be too tempting for orgs and Governments to just
drop sessions which have negotiated ECHO.
Even if we had wide scale deployment of GREASE, if a third-party can allow
GREASE but block successful ECHO handshakes then all the effort we've
expended will be wasted.

Does the probing attack only apply in cases without a key share, or is it
also possible in cases where key shares are in use?

Regards,

Jonathan

On Sun, 22 Mar 2020 at 18:00, Christian Huitema <[email-masked]> wrote:

> out" [1]. This complicates the current ECHO design, as clients must trial
> decrypt
> I propose we remove this requirement and add an explicit signal in SH that
> says
> As part of AUTH48 changes, we agreed to add a line in section 3.4 pointing
> to this comment is section 5.
>
> We can observe that ECHO already sticks out, because of the presence of an
> unexpected encrypted field in the Client Hello. So in practice ECHO
> deployment already relies on achieve large scale deployment, and possibly
> greasing the encrypted parameter.
>
> -- Christian Huitema
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Ben Schwartz <[email-masked]>
Date: Sun, 22 Mar 2020 17:49:45 -0400

It might be helpful to have a more precise definition of "do not stick out".

Considering a passive intermediary on the network path who cannot see the
DNS path, I can think of a few different "not stick out" properties we
might want:

1. The intermediary cannot identify clients that support ECHO.
2. The intermediary cannot identify servers that support ECHO.
2a. ... based on the connection contents alone.
3. The intermediary cannot tell whether ECHO was actually used.
3a ... based on the connection contents alone.

ECHO currently does not have Property 1.
Property 2 seems unlikely to be achievable in practice.  By publishing an
ECHOConfig, the server reveals its support for ECHO to everyone.  Chris
also noted a way to probe directly for confirmation.
Property 2a seems to be the topic at hand.
Property 3/3a relies on GREASE.  Like Property 2, Property 3 is (normally)
easily broken by an intermediary with a database of published ECHOConfigs.
[*]

I'm OK with losing Property 2a.  However, Property 3a seems achievable and
potentially valuable.  Consider a network where most clients support ECHO
and use GREASE, but only a minority can actually fetch ECHOConfigs, e.g.
ECHOConfig fetching requires the user to change their DNS configuration.
An intermediary who wants to record all SNIs could block only the
connections that actually activate ECHO, forcing clients to revert their
DNS configuration change and reveal the SNI.  Limiting this blocking to
public names that the intermediary is aware of seems like a worthwhile
step, especially since these names can be rotated relatively rapidly
(~minutes).

Property 3a is compatible with a flag in the ServerHello, so long as the
flag says "ECHO in use" when actually GREASE is in use.  This could be
achieved by reporting "ECHO in use" whenever the SNI is not a Public Name
used by the server (assuming it is not an actual origin name), or adding a
"long term ID" field (at least 32 bits) to ECHOConfig that persists across
key rotations.

Perhaps a good approach would be a flag meaning "ECHO retry in use".
(Would it be safe to move "retry_keys" to the unencrypted extensions?)

--Ben Schwartz

P.S. Ideally, I still want Property 1.  I imagine it might be possible by
formatting the ECHO as 0-RTT data, as Christian Huitema and others have
discussed over the years.

[*] Actual ECHO ClientHellos to a server at some IP will have the Public
Name in the SNI field, whereas GREASE ClientHellos will have the origin
name there instead.  However, if the ECHOConfig Public Name is in fact a
valid origin, then (with sufficiently good GREASE) the intermediary is
unable to state with certainty whether any particular user visited that
domain, even if many users cannot actually fetch ECHOConfigs.  In the
extreme, a server could publish a slate of ECHOConfigs that name _all_ of
its domains as Public Names, so that seeing any of them in the SNI field is
not proof of anything.

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 22 Mar 2020 15:14:25 -0700

> drop sessions which have negotiated ECHO.

Well, those orgs will also be able to block encrypted DNS, without which
ECHO is useless. We don't have an answer for this either.

> GREASE but block successful ECHO handshakes then all the effort we've

This seems like it needs more than a bare assertion.

It's certainly the case that some entities will opt to block ECHO but many
will not and the clients (and hence users) can be made aware of which ones
do.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 22 Mar 2020 15:16:04 -0700

I think we should relax this requirement. It's turning out to be hard
enough to design ECHO as-is.

If/when we get ECHO fully designed and widely deployed, we can then try to
find designs which use the same basic design but are more stealthy.

Trying to fix everything at once makes the best the enemy of the good.

-Ekr

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 22 Mar 2020 22:23:47 +0000

Hiya,

I was wondering what I wanted to say about this, until...

> Trying to fix everything at once makes the best the enemy of the good.

Yeah, that's about right. Well said.

I very much like the idea of working on a more-stealthy
mode later.

I think we might be able to go even further in terms
of simplifying ECHO in various ways that can make it
easier to implement and deploy now without affecting
the security properties/analysis. (I think I've whined
about those on the list before but can regurgitate if
useful:-)

Cheers,
S.

---

From: Christian Huitema <[email-masked]>
Date: Sun, 22 Mar 2020 15:59:22 -0700

> about those on the list before but can regurgitate if

I agree with Stephen. If we have a solid & verified spec, let's deploy
it. Then conduct an effort to mitigate the sticking out problem. I can
see a number of plausible ways to do that. Greasing is one. Actually
using the extension even for sites that have just one SNI, but want to
hide usage of multiple ALPN. In the case of QUIC, using the extension to
negotiate a secret and protect the Initial packets. If everybody does
it, the cost of blocking becomes very large.

-- Christian Huitema

---

From: "Martin Thomson" <[email-masked]>
Date: Mon, 23 Mar 2020 10:10:48 +1100

On Mon, Mar 23, 2020, at 03:54, Christopher Wood wrote:
> that says whether or not ECHO was negotiated. 

Here's a spitball signaling option that might not stick out:

Client sends (in the ECHO) a random value, N, with 32(?) < |N| << 128.  And N != either of the values we reserve for signaling downgrade.

Server sends that value in the ServerHello.random, in the same place we signal downgrade.

If the client sees that value, then it proceeds with the trial encryption with an expectation that it will work.

> (This will require us to revisit GREASE.)

I'm not following how this relates, sorry.

---

From: "Christopher Wood" <[email-masked]>
Date: Sun, 22 Mar 2020 19:57:14 -0700

On 22 Mar 2020, at 16:10, Martin Thomson wrote:

> Client sends (in the ECHO) a random value, N, with 32(?) < |N| << 128. 
>  And N != either of the values we reserve for signaling downgrade.
>
> If the client sees that value, then it proceeds with the trial 
> encryption with an expectation that it will work.

We’ve discussed variants of this in the past. It’d work as a signal. 
However, CH modification attacks to figure out whether a connection uses 
ECHO exist. One of them, pointed out offline by David Benjamin, is to 
remove all ciphersuites from the outer CH and see what happens with the 
connection. Preventing this would likely require us to revisit the 
binder approach, which was always complex enough to beg the question: is 
the juice worth the squeeze?

Like Stephen suggests, I think working on a stealthy variant of this 
later on is probably the best path forward. (I think we’re close 
enough to the Tor and Pluggable Transports orbit as is.)

> I'm not following how this relates, sorry.

Sorry, it’s not the specific SH extension signal that would require 
this. It’s the general question of whether or not we should drop (or 
relax) this “do not stick out” requirement. As Ben pointed out, 
knowledge of valid record_digest values, which we should assume is known 
to the adversary given that these are public, makes this difficult with 
GREASE.

Best,
Chris

---

From: Nick Sullivan <[email-masked]>
Date: Mon, 23 Mar 2020 03:54:57 -0700

I have reservations.

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

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.

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?

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?

> whether or not ECHO was negotiated. (This will require us to revisit

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.

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 23 Mar 2020 08:39:50 -0700

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 <[email-masked]> wrote:
> 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:
> - 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)
> 

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. 

> 1) client connects to server using an ECHO extension created with a 
> valid key ID and a valid ciphertext for that ID
> 1) client connects to server using an ECHO extension with a random 
> invalid key ID, and an invalid ciphertext
> 1) client connects to server using an ECHO extension with a random 
> invalid key ID, and an invalid ciphertext
> 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
> 
> 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
> 
> 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
> 
> 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.
> 
> 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.

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

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

Thanks!
Chris

---

From: Nick Sullivan <[email-masked]>
Date: Mon, 23 Mar 2020 10:37:55 -0700

Replies inline again.

On Mon, Mar 23, 2020 at 8:40 AM Christopher Wood <[email-masked]>
wrote:

> "do
> used
> probe
> 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.
>
> 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.

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

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

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 23 Mar 2020 11:17:33 -0700

On Mon, Mar 23, 2020, at 10:37 AM, Nick Sullivan wrote:
> Replies inline again.
> 
> On Mon, Mar 23, 2020 at 8:40 AM Christopher Wood <[email-masked]> wrote:
> 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.

It doesn't complicate the model, since the model does not try to capture whether or not ECHO was negotiated. 

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

Well, this isn't part of the design. Only extensions can be de-duped, as you note below.

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

True, we could remove OuterExtensions.hash.

To be clear: ECHO resumption binders are not in the outer CH, they're in the inner CH. This would require checking one binder for the outer CH and then another for the inner CH (if an ECHO connection was resumed). 

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

Yep, blocking based on that signal is definitely a risk.

> solution seems like it will be challenging. We should fix this now 
> rather than later. 
> 
> > 
> What do you mean by efficacy? Once we have a PoC of an ECHO load 
> balancer, I'd be happy to share it. 

I think simple traffic analysis might render ECHO useless unless servers participate in padding. 

Best,
Chris