Support for EDNS(0) Padding Option

[imbushuo]

Duplicated from email thread.

Context:
In our study [1], we have evaluated if DNS over TLS (DoT) and DNS over 
HTTPS (DoH) resolvers support EDNS(0) padding to protect users’ privacy 
against traffic analysis. Through our measurements, we found that your 
resolver does not pad DNS responses, even if DNS queries are padded. 
This leaves your users unprotected against traffic analysis attacks. To 
tackle this privacy problem, it is recommended to pad DNS responses to 
multiples of 468 bytes. There is some guidance for resolvers 
specifically for padding with RFC 8467 and for privacy in general with 
RFC 8932.

Explanation of the Problem:
In general, DoT and DoH promise to improve privacy of DNS by encrypting 
DNS messages. While encryption is beneficial for users’ privacy, 
websites or mobile apps can still be identified with traffic analysis 
attacks solely by encrypted DNS traffic [1]. The resulting privacy 
leakage through message size patterns is already discussed in the 
standards for both protocols (see RFC 8484 and RFC 7858). As a 
protection, it is recommended to pad DNS messages to a uniform size. 
That is, resolvers should pad DNS responses to multiples of 468 bytes to 
protect their users against traffic analysis attacks.

[m13253]

That is, resolvers should pad DNS responses to multiples of 468 bytes to
protect their users against traffic analysis attacks.

The question: Why 468 bytes? Any RFCs referring to this?
Most of the time in the wild Internet, I only see padding on the request side, but not on the response side.

For HTTP/2 over TLS with optional compression, it is very hard to precisely control how many bytes to pad.
Since the padded bytes are of high entropy, which survives the compression, the size of padding may still lose confidentiality if statistical methods are used.

Therefore, there is no clear evidence whether padding can benefit, more RFCs or research results needed for a decision.

[ubapsimm]

The question: Why 468 bytes? Any RFCs referring to this?
Most of the time in the wild Internet, I only see padding on the request side, but not on the response side.

As referenced above, RFC 8467 specifies Padding Policies for Extension Mechanisms for DNS (EDNS(0)).
I have extracted the relevant parts from Section 4.1. of RFC 8467:

Based on empirical research performed by Daniel K. Gillmor
[NDSS-PADDING], padding SHOULD be performed following the Block-
Length Padding strategy as follows:

(1) Clients SHOULD pad queries to the closest multiple of 128
    octets.

(2) If a server receives a query that includes the EDNS(0) "Padding"
    option, it MUST pad the corresponding response (see Section 4 of
    RFC 7830) and SHOULD pad the corresponding response to a
    multiple of 468 octets (see below).

[NDSS-PADDING]
           Gillmor, D., "Empirical DNS Padding Policy", March 2017,
           <https://dns.cmrg.net/ndss2017-dprive-empirical-DNS-traffic-size.pdf>.

[m13253]

As referenced above, RFC 8467 specifies Padding Policies for Extension Mechanisms for DNS (EDNS(0)).

Yeah, that is for DNS over UDP53, not DoH over HTTPS.
Since Brotli + HTTPS2 + TLS adds more layers of uncertainty. (see my previous post.)
Even if the inner payload is padded into 468 octets, the resulting packet will not be 468 octets.

I would hope there to be more research on this topic before we clearly know how many bytes is suitable for DoH.

[ubapsimm]

Yeah, that is for DNS over UDP53, not DoH over HTTPS.

No, this is not the case. It does not make any sense to pad DNS responses that are transmitted in the clear. If you read the referenced RFC 8467, it clearly states directly after the excerpt:

Note that the recommendation above only applies if the DNS transport
   is encrypted (see Section 6 of RFC 7830).

There are also some best practices for resolver operators defined in RFC 8932. The excerpt here is directly for DoH:

5.1.3.2.  DoH

   DNS Privacy Threats:
      *  Known attacks on TLS, such as those described in [RFC7457].

      *  Traffic analysis, for example: [DNS-Privacy-not-so-private]
         (focused on DoH).

      *  Potential for client tracking via transport identifiers.

   Mitigations:
      *  Clients must be able to forgo the use of HTTP cookies [RFC6265]
         and still use the service.

      *  Use of HTTP/2 padding and/or EDNS(0) padding, as described in
         Section 9 of [RFC8484].

      *  Clients should not be required to include any headers beyond
         the absolute minimum to obtain service from a DoH server.  (See
         Section 6.1 of [BUILD-W-HTTP].)

Also, the DoH RFC 8484 directly states:

DoH servers can also add DNS padding [RFC7830] if the DoH client requests it in the DNS query. 
An experimental effort to offer guidance on choosing the padding length can be found in [RFC8467].

Even if the inner payload is padded into 468 octets, the resulting packet will not be 468 octets.

This is true. However, DoH responses from the same resolver will have the same length. As a result, it is more difficult for passive adversaries to detect websites or applications through message size patterns. And, there are studies, which have shown that traffic analysis is more difficult if DoT/DoH responses are padded. Actually, larger DoH resolvers such as Google and Cloudflare support padding already for more than one year.

[m13253]

Thanks for the responses. Now I understand the points.

By the way, I would be really happy if anyone have time to help me add this feature.

[gdm85]

I can give this a try; when we talk about "DNS responses", we refer to the HTTP response Content-Length, correct?

[m13253]

I can give this a try; when we talk about "DNS responses", we refer to the HTTP response Content-Length, correct?

EDNS allows both the client and server to add random garbage to the request and response in the DNS packet.
By making the length of DNS packet multiples of 128 and 468 bytes, we can reduce the risk of an attacker guessing the contents of DNS query by calculating the packet length.

I guess it's basically Content-Length, but the padding resides inside the DNS packet, in the EDNS section.

[m13253]

I have 3 concerns:

1. Paddings at different layers: EDNS can add padding, HTTP/2 can add another padding (in multiple ways), the outer TLS layer certainly adds the third layer of padding. I'm not pretty sure the interaction between them.

2. Compression algorithms may change the entropy distribution prior to encryption, which adds another layer of uncertainty. Considering the low entropy of DNS response, combined with high entropy of padding data, or vice versa. It's pretty hard to predict the final size since we are inserting padding at DNS layer, and the compression happens at HTTP/2 layer.

   (You may ask: Why not just disable compression? Well, that's another question to discuss. We do disable compression at TLS layer for security, but compression at HTTP/2 layer is generally considered beneficial more than harmful.)

3. Potential new attack surface: Does padding enable a new type of amplification attack? (Since the client pads to 128, but the server pads to 468.)

Are there any discussion at IETF side regarding padding DoH? The DoH context is important because other deployment like DoT don't address my first and second concerns.

[cslev]

Hi All,
I accidentally bumped into this conversation when googling why am I seeing EDNS padding when checking what my kdig DoH requests look like on the wire.

I want to add a sidenote to @m13253's point 3. Since the padding is only relevant if traffic is encrypted either using DoT/DoH. Both of them are on top of TCP, so the traditional amplified reflection attack cannot be achieved (as those are based on Do53/UDP packets). DoQ also requires a handshake before name resolution, so it's not applicable to DoQ either. If you send your query over Do53 with EDNS padding option set, the resolver should not pad the response. Hence, amplification should not be possible via EDNS padding.

Another sidenote to point 1. This padding should be EDNS padding because then it is part of the DNS protocol. Hence, no matter what encrypted channels you will use, be it DoT/DoH/DoQ/DoX, all can obey. If you introduce padding as HTTP/2, then it will only work in DoH/DoH3. And EDNS is already supported and understood by resolvers too.

Another interesting aspect of the padding is that while it helps against traffic analysis, in the case of DoH, the padding would also help to identify DoH itself. Note that DoH inherently blends into HTTPS (i.e., regular web traffic) thereby increasing the privacy of the users. However, by padding each DoH request/response, it is easier to detect DoH and differentiate it from Web traffic. Note that due to the Opportunistic profiles DNS stub resolvers adapt, once an encrypted DNS connection fails (because of being blocked), your stub resolver seamlessly fallback to plain-text DNS where you will expose your DNS queries.
There might be better padding solutions to avoid this. There was a research project I was involved in, where other padding techniques were considered to defeat DoH detection models that are based on traffic analysis.