Subject: [TLS] ESNI and padding

From: Stephen Farrell <[email-masked]>
Date: Wed, 19 Jun 2019 23:34:16 +0100

Hiya,

TL;DR: I think we ought remove the ESNIKeys.padded_length field,
define a purely algorithmic padding scheme with no configuration
needed and RECOMMEND that people using ESNI don't use names that
are exceptionally long.

In the web, ESNI is hides the web site to which a browser is
connecting but there are a few ways in which the lengths of
handshake fields could give the game away. So the current
draft provides mechanisms to avoid those issues in the
handshake. But I think we can do better with less.

(As a side-note - the ESNI spec is not trying, and shouldn't try,
to define how to pad TLS application traffic. While that is something
that will need to be figured out, it's out of scope for ESNI, which
rightly only deals with the handshake IMO.)

My main problem with the current approach is that a server might not
(easily) know the longest name or certificate that they will serve
for the duration for which one ESNIKeys value is current.  I've come
across openssl related code and mails that indicate that server code
accesses the server cert and private key via a DB lookup.  That DB
might not be readily searchable for whomever generates the ESNIKeys.
The current draft calls for fixing the padded_length in the ESNIKeys
structure published in the DNS to cover the longest needed.  It
could easily be problematic to ensure those don't get out of whack,
leading to avoidable error cases. The current approach also links
the cadence with which one updates the DNS with how often new TLS
server certificates appear, which seems like an undesirable and
unnecessary linkage. And of course, while the length of the
server name is under local control, the length of certificates
is not.

Separately, I think the current approach will lead to deployments
over-estimating the padding needed "just in case", e.g. CF's
deployment calls for padding to 260 octets (and I've copied
that in mine so far:-) I would assume CF picked that number
for that not-great "just in case" reason but don't know. In any
case, 260 seems wasteful to me and if it ended up widespread
could cause an issue later if the ClientHello gets bigger for
other reasons, and/or if someone started to depend on it for
some weird reason.

What I'd suggest instead:

- delete the padded_length field from ESNIKeys, so nobody needs
  to configure anything for padding
- clients MUST pad to a multiple of N octets where N is in the
  spec (I'd suggest N=32, but any number that's longer than
  nearly all real TLS server names would be good)
- we RECOMMEND clients randomly add an additional N octets of
  padding with probability X%, perhaps with X=10 (btw - am I
  right in thinking that if X% is greater than the percentage
  of real names that are longer than N, then we're good?)
- we STRONGLY RECOMMEND that servers choose names shorter than
  N octets for hidden web sites
- servers pad Certificate to a multiple of M octets (M=2000 maybe)
  and CertificateVerify to a multiple of O octets (with O=500 maybe)

I'd be fine with any minor changes to the above as well
or with another scheme that allows us to get rid of the
ESNIKeys.padded_length field.

Cheers,
S.

PS: There was a little discussion of this on github, [1] but
I figure this is really one the WG ought deal with.

[1] https://github.com/tlswg/draft-ietf-tls-esni/pull/122

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 19 Jun 2019 18:17:05 -0700

>   N octets for hidden web sites

I am not in favor of these changes.  They reduce protocol flexibility for
servers
which know what they are doing and largely can be implemented in the
protocol
by servers which do know what they are doing.

Again, this has a huge negative impact on performance and the server can
do much better if it's smart.

In addition to the comments above, your number for O is way too large
if the server has effectively any information about which algorithms it is
using. Even if you know that you only use RSA-2048 (by far the dominant
size) then you can do far better than 500. Similarly, if you have the same
set of algorithms for all your domains, this does not leak any information.

-Ekr

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 20 Jun 2019 09:20:26 +0100

Hiya,

> I am not in favor of these changes.  They reduce protocol flexibility for

I don't see being asked to configure a new thing that has
subtle relationships with other things that aren't always
under the control of one entity as "flexibility." I see
that as a burden, and maybe as a protocol design bug.

> by servers which do know what they are doing.

That kind of anthropomorphism often seems to me to indicate
a weak argument:-) Servers don't "know" anything - the question
is whether the current setup could cause problems for a range
of possible deployments, and I think it could if there's less
tight coupling between how ESNIKeys get generated and published
and how names and certificates are handled. IIUC that kind of
setup does exist in the wild.

To give an example, say some hoster is doing ESNI and has set
padded_length to 55. If a new customer turns up with a 56 octet
name, then that hoster has to unexpectedly touch ESNIKeys or
deal with possibly weird ESNI problems for at least a TTL. If
we had an algorithmic approach it should just continue to work.

Characterising that hoster as "not knowing what they're doing"
seems to me wrong. I think that'd be more a case of us not
knowing what we're doing:-)

As to the specific numbers in my mail - I don't much care
what's picked, and do agree that some measurements would help
pick good numbers. I also agree that CertificateVerify is much
less of a concern in reality. But asking that Certificate be
padded "such that its length equals the size of the largest
possible Certificate (message) covered by the same ESNI key"
would in some cases require a new database search for each
TLS session. And since the Certificate message is the path
and not one certificate that could be quite expensive to
impractical depending how a server stores/builds paths. I
also believe that some openssl deployments do this via
locally implemented callbacks so it'd be hard to know how
badly or not the current approach might affect those.

Cheers,
S.

---

From: Ben Schwartz <[email-masked]>
Date: Thu, 20 Jun 2019 07:20:48 -0400

On Wed, Jun 19, 2019 at 6:34 PM Stephen Farrell <[email-masked]>
wrote:
...

>   N octets for hidden web sites

As you are clearly aware, this approach provides essentially no privacy
protection in the case where a user is repeatedly connecting to a very long
domain on a server whose other domains are reasonably short.

Rather than make a privacy-vs-efficiency tradeoff in the spec, the current
text leaves this option to the implementer.  For example, within the
current protocol (albeit bending the recommendations slightly), an
implementer could easily bucket names by length, and offer separate
ESNIKeys for each length bucket.  I think this is preferable; only the
server operator knows their own privacy and efficiency goals.  In my view,
setting N=32 for the first bucket would reproduce most of the benefits of
this proposal without altering the current protocol.

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 20 Jun 2019 13:04:18 +0100

Hiya,

> domain on a server whose other domains are reasonably short.

Yep. I don't believe that that's at all a common scenario,
but if I'm wrong then sure, the approach I outlined wouldn't
be a good plan, at least not with N=32, but maybe some other
N would work fine. Do we know how common very long SNI names
are? (I don't.)

If we think that scenario is a real problem, that can't be
sufficiently mitigated via picking a good N, then I guess
always having padding_length==260 would be the only answer.
In which case I see no upside and some downsides in having
that field in ESNIkeys.

> this proposal without altering the current protocol.

Fair point. OTOH, if you did that, the last (or maybe even
all but the first) bucket would likely mean an ESNIKey used
for very few names, so you end up with the same issue you
called out above. And it adds some more complexity to what's
an already complicated thing. So while that could always
be done, and with the current spec, I'd not be keen to
recommend it myself.

I just looked back at RFC8467 which recommends padding DNS
queries to a multiple of 128 octets. I also looked at a couple
of DNS queries on my laptop just now and there seems to be
about 40 octets overhead over and above the qname length
(each "." adds two octets in the encoded length vs. the
string length it seems). So one could I guess argue for some
commensurate amount of padding in the ESNI extension and
whatever was used for DoT or DoH. I wonder if the data DKG
used to generate that recommendation in 8467 might tell us
anything here?

Again though, I think considering DNS query padding argues
that this ought be a client-driven thing and not tied to the
ESNIKeys. If no padding was used for DoT or DoH, the ESNI
length may already have leaked regardless of the padded_length.
That said, I'm not sure what, if any, padding is being done
by DoT or DoH clients. (I use stubby and it does some padding
sometimes but I'm not sure what.)

Cheers,
S.

---

From: Ben Schwartz <[email-masked]>
Date: Thu, 20 Jun 2019 09:16:10 -0400

> used to generate that recommendation in 8467 might tell us

I've implemented RFC 8467 myself, and I'm grateful for the recommendation,
but I think it's rightly marked Experimental.  It's not clear how to judge
the amount of privacy protection it offers, or whether it's truly a good
balance between privacy and efficiency.

However, as a matter of overhead, your test suggests that RFC 8467 roughly
doubles the size of each query packet.  That's similar to the proportional
effect of maximum ESNI padding on a typical ClientHello.  Proportionally, I
expect RFC 8467 adds more padding to the whole DNS transaction than current
ESNI adds to the whole TLS handshake.  It might even be true in absolute
terms, on average.  In the context of a full TLS connection, the
proportional impact of ESNI is even smaller.

> ESNIKeys.

One important difference between these cases is that DNS is essentially an
"open world", where no one knows the whole space of possibilities, whereas
a specific server is a "closed world", a finite set of domains (known only
to the server operator).  That puts the server operator in the unique
position to make correct padding decisions, and also makes the adversary's
job much easier if the padding is incorrect.

If no padding was used for DoT or DoH, the ESNI
> sometimes but I'm not sure what.)

In general, I think we should assume that no SNI information is leaking
through other channels when making design choices for ESNI.  Otherwise, we
risk ESNI itself becoming the limiting factor in the future as those other
leaks are fixed.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 20 Jun 2019 06:48:02 -0700

> that as a burden, and maybe as a protocol design bug.

Well, opinions differ, I suppose. The server implementor is free to
implement the policies you suggest here.

> a weak argument:-)

I'm assuming this is just snark, not something you think has any
rhetorical force.

Servers don't "know" anything - the question
> we had an algorithmic approach it should just continue to work.

And as I said, the hoster is free to implement that value themselves. But
I'm not in favor of opposing them.

> knowing what we're doing:-)

Again, I suppose opinions differ.

> TLS session.

I don't really know why you think that.

-Ekr

And since the Certificate message is the path

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 20 Jun 2019 14:50:27 +0100

> proportional impact of ESNI is even smaller.

Sure, compared to the full TLS exchange padded_length==260
isn't so much.

> job much easier if the padding is incorrect.

True, but not always true, in the sense that the server
s/w may not have such an easy job knowing the sizes in
all deployments (for Certificate padding) and similarly
keeping that in whack with the padded_length in the DNS
can be tricky as it can involve multiple entities. (But
I'm starting to repeat myself:-)

> risk ESNI itself becoming the limiting factor in the future as those other

Sure. I fully agree with that, but nonetheless if DNS
query padding and ESNI padding are both being done as
we'd like, then having both be controlled on the same
side of the TLS connections seems more robust to me.

Cheers,
S.

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 20 Jun 2019 15:07:08 +0100

Hiya,

> Again, I suppose opinions differ.

Yep:-)

> I don't really know why you think that.

I've come across openssl mails/github issues (I'd
have to go back and find 'em again though so this
is just from memory) where servers use a callback
to take the SNI value and query a DB to get the
private key and cert to use in the TLS session. If
the current requirement is to be met, such code
would need to change to figure out the max Certificate
message that could be sent in order to pad as per
the spec. If that code only pulls the server cert
from the DB and then figures out what intermediates
to also send in the Certificate message, then
correctly implementing the spec could be v. hard,
and likely wouldn't be done would be my guess. I'd
not be surprised if they just do some other thing
like read a configuration setting or something and
that could be brittle as certs are updated in the
DB with e.g. new X.509 extensions added. I'd imagine
that servers using other libraries may well face
the same issue.

But just to be clear - that's not an end of the
world thing, but if done badly, could leak length
information, so I'd be happy if we could find a
padding scheme that'd be easier to implement in a
library for servers where the set of TLS server
certs isn't a small static set. Hence my suggestion
of padding to some multiple of M which wouldn't
require any new DB lookups or config settings for
that purpose.

Cheers,
S.

---

From: "Christopher Wood" <[email-masked]>
Date: Tue, 25 Jun 2019 13:49:05 -0700

On Thu, Jun 20, 2019, at 6:16 AM, Ben Schwartz wrote:
> 
> 
> On Thu, Jun 20, 2019 at 8:04 AM Stephen Farrell 
> <[email-masked]> wrote:
> > 
> >  Hiya,
> > 
> I've implemented RFC 8467 myself, and I'm grateful for the 
> recommendation, but I think it's rightly marked Experimental. It's not 
> clear how to judge the amount of privacy protection it offers, or 
> whether it's truly a good balance between privacy and efficiency.
> 
> However, as a matter of overhead, your test suggests that RFC 8467 
> roughly doubles the size of each query packet. That's similar to the 
> proportional effect of maximum ESNI padding on a typical ClientHello. 
> Proportionally, I expect RFC 8467 adds more padding to the whole DNS 
> transaction than current ESNI adds to the whole TLS handshake. It might 
> even be true in absolute terms, on average. In the context of a full 
> TLS connection, the proportional impact of ESNI is even smaller.
> 
> One important difference between these cases is that DNS is essentially 
> an "open world", where no one knows the whole space of possibilities, 
> whereas a specific server is a "closed world", a finite set of domains 
> (known only to the server operator). That puts the server operator in 
> the unique position to make correct padding decisions, and also makes 
> the adversary's job much easier if the padding is incorrect.

+1 -- I don't think we ought to change the current text. 

Best,
Chris (no hat)