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

[Christopher Wood <[e-mail]>]

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 <[e-mail]> 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 <[e-mail]> 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.

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

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

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

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

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

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

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

Best,
Chris