DNS Query Privacy revisited

By on 11 Sep 2020

Category: Tech matters

Tags: , , ,

Blog home

I wrote a first version of this post in August 2019, and ended it with the comment: “It’s likely that we will return to this measurement of the use of QNAME Minimisation in a year or so to see if anything has changed from the picture today.”

Well, a year has passed and it’s time to review this topic and see what has changed in the DNS resolution environment over the past 12 months.

Much has been said and written in recent times about the use of the Domain Name System (DNS) as a means of looking at the behaviour of end systems and inferring user behaviours.

Almost every transaction starts with a DNS query, and if one were to assemble the complete set of DNS queries generated by an Internet user it would be possible to assemble a relatively complete picture of their online activity. For many years this aspect of the DNS as a means of observation into the activities of others received little attention from the mainstream, but the more recent sensitivities over state and private digital surveillance have brought significant attention to the overall topic of DNS privacy.

Another reason for all this attention is that in terms of privacy, the DNS resolution protocol has been sadly lacking in some basic privacy protections. The DNS name resolution protocol was not designed with privacy as the foremost consideration. The queries and responses are unencrypted, which makes them prone to hostile man-in-the-middle manipulation and they leak superfluous information to third party onlookers.

There are two major approaches to try and mitigate DNS privacy issues.

The first approach is to make it harder to eavesdrop on DNS queries by using encryption for DNS transactions. The issues around encryption and the efforts with DNS-over-TLS (DoT) and DNS-over-HTTP (DoH) are a current topic of very high interest in the DNS world.

The second approach is to reduce the information leakage by reducing the amount of information in each DNS query. The IETF published an approach to achieve this using a technique called ‘Query Name Minimisation’ (QNAME Minimisation or Qmin), described in an Experimental RFC document (RFC 7816, “DNS Query Name Minimisation to Improve Privacy” by Stephan Bortzmeyer, March 2016).

In this post, we will take another look at QNAME Minimisation in a little more detail and present some results of our measurement of the current level of use of this resolver query technique in today’s Internet.

What is QNAME Minimisation?

The technique described in RFC 7816 is a query management approach based on a principle described in RFC 6973, ‘Privacy Considerations for Internet Protocols’ (July 2013), which could be summarized as ‘the less data you emit the fewer privacy issues you are likely to encounter’.

The DNS has conventionally optimized its behaviour for simplicity and performance. The underlying factor in the DNS name resolution protocol is that a DNS recursive resolver does not necessarily know in advance which servers are authoritative for a given zone, so it has to discover this information. Also, if a name has several labels the resolver does not necessarily know where the zone cuts occur between labels.

For example, the zone c.example.com may contain a delegation record for the label b. The zone b.c.example.com might contain a delegation record for the label a. The zone a.b.c.example.com might contain a resource record for this name. In this case there are zone cuts between b and c and between a and b in the domain name a.b.c.example.com. Alternatively, the zone c.example.com might contain a resource record for the label a.b, in which care there are no further zone cuts below c.example.com.

diagram explaining the above example

The point here is that a resolver cannot determine in advance just by examining the domain name where the zone cuts might be. They are discovered by the resolver during the name resolution process.

The zone cuts may relate to a desire on the part of a zone administrator to split the zone management role to different servers. They may also relate to a change in administrative control where the name space below the cut is delegated to a different administrative entity.

The IETF chartered the dbound Working Group in 2014 to work on a way to make these points of delegation that relate to a change of administrative control explicit. The idea was to allow the DNS to self-describe these points of change of administrative control within the DNS name hierarchy itself. The effort was directed to replacing the volunteer-operated Public Suffix List, which has some concerning shortcomings.

Critical dependencies on the Internet are everywhere (Source: XKCD)

The dbound Working Group worked on a problem statement for a couple of years. The group was shut down in early 2017 without publishing any of its work as an RFC. Instead, we continue to rely on the volunteer efforts of the Mozilla Foundation to maintain the public suffix list, and we currently have no alternative in mind. Perhaps this reliance on volunteer effort may resurface as an issue in the coming months due to the current adverse economic conditions impacting Mozilla.

This implicit reliance on the erstwhile work of volunteers was a feature of the early Internet, and perhaps one of its core strengths at the time. These days the Internet is a trillion-dollar sector and it seems a little uncomfortable to still find critical dependencies on volunteer effort when that effort underpins large amounts of the Internet’s commercially operated service infrastructure.

In the absence of this meta-information about the structure of the namespace, a DNS recursive resolver uses the full query name in all queries as it descends the name hierarchy looking for the lowest level authoritative name server, as this iteractive technique will expose the zone cuts and the name servers for each zone.

To expand on this a little, DNS resolution occurs in a ‘top-down’ manner, and when an authoritative server for a zone receives a query for a name that is only resolvable in a delegated subordinate zone (that is, at a level in the zone hierarchy that is lower in the name hierarchy than the zone served by this authoritative server) it returns a NOERROR code and no Answer Section in its response (a ‘NODATA’ response). The response includes the name of the next lower level delegated zone and its name servers, as enumerated in the delegation record (the point of the zone cut), in the Authority Section of the response and the IP addresses of these name servers in the Additional Section of the response, assuming that these addresses are known to the authoritative server.

The DNS is a strict hierarchal namespace, so each server is only aware of immediately delegated zones. The name resolution process will iterate down through the hierarchy to either reach the server that can provide an authoritative response for this query name or obtain a response indicating that the name does not exist in the DNS. This process is illustrated in Figure 1.

Diagram showing DNS 'discovery’ process in name resolution.
Figure 1 – DNS ‘discovery’ process in name resolution.

Of course, an efficient recursive resolver will use cached information whenever it can, so the process is typically nowhere near as exhaustive and slow as it may appear from this informal description.

This description is not exactly the case in all situations. A server may be an authoritative server for both a ‘parent’ zone and some or all of its delegated ‘child’ zone or zones. The query does not specify which zone is the intended subject of its query, allowing the server to answer the query using data from the most specific served zone in the name hierarchy that partially matches the query name.

How does QNAME Minimisation alter this behaviour? To quote from RFC 7816:

Instead of sending the full QNAME and the original QTYPE upstream, a resolver that implements QNAME minimisation and does not already have the answer in its cache sends a request to the name server authoritative for the closest known ancestor of the original QNAME. The request is done with:

  • the QTYPE NS
  • the QNAME that is the original QNAME, stripped to just one label more than the zone for which the server is authoritative

A resolver using QNAME Minimisation implicitly assumes that each label in the query name corresponds to a zone cut. The resolver queries a parent zone server, using an abbreviated query name that is truncated after the name of the immediate child label and uses a query type of NS. This altered resolution process is illustrated in Figure 2.

Diagram showing the DNS “discovery” process in name resolution using QNAME Minimisation.
Figure 2 – DNS ‘discovery’ process in name resolution using QNAME Minimisation.

Let’s look at the query sequence in two cases to illustrate the difference between full name queries and minimized name queries. In the case of a full name query for the name myspecialname.me.example.com the query name has been exposed to a root server, a.com server, a example.com server and a me.example.com server. If the query logs from any of these servers were to be inspected my ‘interest’ in the name myspecialname.me.example.com would be evident. In the minimized case the information ‘leak’ has been trimmed considerably. The root server only sees a query for the .com label, the com servers only see a query for example.com, and so on.

In terms of an improvement to DNS privacy, this technique sounds like a great step forward. Nothing changes for authoritative servers and it’s only the recursive resolvers that change their behaviour to trim the query name and alter the query type to a ‘neutral’ query for the NS record rather than expose the intended query type to these servers. Only at the target zone is the full query name used with the original query type.

This approach essentially removes superfluous information from the DNS query stream. The approach can be deployed incrementally, and the benefits are immediately available to those recursive resolvers, and their user population, that use this QNAME Minimisation technique. 

In short, it seems like an ideal technology change, where current incumbent service providers need to do nothing to allow those who want to adopt this approach to proceed. The benefit for those who do this is that they cease to broadcast their actions and intent to a larger circle of potential DNS onlookers.

QNAME Minimisation considerations

Why hasn’t this technique been deployed in all resolvers already? And why isn’t this the default mode of operation of the DNS?

Assuming that the concerns relating to DNS privacy aren’t just the products of the fevered imagination of a few activists in the IETF, but a reflection of a larger set of very real user community concerns over obsessive levels of DNS surveillance, then surely there would be a clear consumer preference for services that use such techniques to improve DNS privacy.

Why have vendors not identified this consumer preference and deployed products to meet this incipient demand? If all this is so simple and easy and is deployable in a piecemeal and uncoordinated manner then what’s stopping us from doing this?

The QNAME Minimisation picture is nowhere as simple as you might think at this juncture. Several DNS structures need to be considered:

Empty Non-Terminal (ENT) zones

What if the query name does not exist? 

The simple response is that whenever the QNAME minimizing resolver receives an NXDOMAIN response then it should stop and return NXDOMAIN as the response to the querier.

NXDOMAIN is a very particular form of response indicating that this name does not exist in any form in the DNS, not even as a delegation point. NXDOMAIN means that this name, and any name that shares this name as a common suffix, does not exist.

Only in theory do theory and practice coincide. In practice, they don’t.

The practice of the DNS is filled with odd behaviours and stupid DNS tricks that tend to assume a particular mode of resolver behaviour. As Shumon Huque has pointed out in a recent OARC meeting, some common Content Delivery Networks (CDNs) host content by using CNAME records to map a client’s name into their CDN namespace and then assume that subsequent queries into the CDN zone’s namespace always contain the full query name. Rather than assuming that every name needs to be ‘discoverable’ as a top-down hierarchical search, they assume that their part of the DNS is an exact match lookup.

A common CDN hosting technique is to map a hosted content name into the content provider’s managed namespace through a CNAME DNS alias record.

For example, if the CDN provider uses the common DNS suffix such as hosted-service.cdn then the service name www.example.com would be mapped into the hosted service by placing a CNAME record for www.example.com, aliasing this name to www.example.com.hosted-service.cdn.

The strict definition of a CNAME record is that the recursive resolver follows the CNAME record and recommences name resolution for this alias name.

Read: Characterizing CNAME cloaking-based tracking

In this example, the recursive resolver would then use the query name www.example.com.hosted-service.cdn to query the DNS. When the server for hosted-service.cdn is queried for this name it will then return the provider’s hosting point for the client www.example.com.

The service provider is not hosting example.com, nor .com, so rather than synthesizing a delegation hierarchy that includes empty non-terminal zones for com.hosted-service.cdn and example.com.hosted-service.cdn, the service provider often uses a zone structure that emulates a flattened enumerated namespace. In other words, the hosted-service.cdn zone server behaves in a manner that is consistent with having a zone file that has an entry for www.example.com.hosted-service.cdn. In this light, it is not inconsistent for the server to respond with NXDOMAIN for all name queries in hosted-service.cdn apart from precisely those names that are mapped to the hosted content.

The result: If a partial form of these mapped names is passed to the CDN’s authoritative server, then an NXDOMAIN may be generated by the server, which will confuse a Qmin recursive resolver. 

These are instances of so-called ‘Empty Non-Terminal’ (ENT) zones, where the zone exists in the DNS hierarchy, but aside from a delegation record, it has no other record. The expected response when an ENT is queried is NODATA (response code 0 (NOERROR) and an empty Answer Section). The NXDOMAIN is an overclaim in this case as NXDOMAIN is intended to be interpreted as ‘this name does not exist and there are no delegated names in the name hierarchy below this name’.

As long as the recursive resolver used the full query name this anomalous use of NXDOMAIN does not have any visible impact. QNAME Minimisation exposes this anomaly as it expects queries for all shortened name forms of a defined query name to return the names for the servers of the delegated zone.

NS vs A Query types

RFC 7816 points out some issues that have been encountered with DNS load distributors, where the response to a NS query is the somewhat unhelpful response code of REFUSED. The specification suggests that a possible workaround is to use an A Query Type with the minimized query name. 

Don’t forget that a QNAME minimizing resolver asks the parent zone server about the child zone name, so this A Query Type is analogous to asking for the NS record, and the anticipated response to the A Query Type is a NODATA response with the details of the name servers of the child zone in the Authority Section.

This is the same information to that provided if the NS Query Type was correctly handled. Don’t forget that the parent zone is not authoritative for the child zone, so the NS query to the parent can only generate a NODATA response, rather than an authoritative answer.

If the only reasons to use NS queries is to mask the intended query type for intermediate queries, then it can be argued that an A Query Type is so common that in itself it gives out even less information than the NS Query Type. Our measurement shows that this is the conclusion reached by resolver vendors and the predominate query type in QNAME minimizing resolvers is for an A record, not an NS record. 

DNS zone server misconfiguration

As has been said many times the DNS is nowhere near as simple as it looks. Configuring authoritative servers for zones can be prone to all kinds of subtle errors. A server for a delegated zone does not necessarily know that it is a ‘properly’ delegated server. 

For example, a DNS server can be set up to serve the zone b.c.example.com, but it is not explicitly aware whether or not the server for c.example.com has listed this server as a delegated nameserver for the zone. The server will still answer all queries for names in b.c.example.com if it is asked. If the zone was DNSSEC-signed, then DNSSEC validation would expose any attempt to pass off false data in this manner, but for unsigned domain names or non-validating resolvers, this can have unintended consequences.

Most of the time it’s not a problem, as it is difficult for the DNS to discover this rogue server. A top-down conventional name server discovery process will use the parent zone delegation details to find the child zone’s name servers, and so on. As the parent zone’s delegation records do not point to the rogue server, the server will not be discovered in the normal course of events.

However, consider the case where a server is a duly delegated server for both the parent zone and is also an undelegated server for a child zone.

Continuing our example, if our server (an undelegated server for b.c.example.com) was also a duly delegated server for c.example.com, and this zone contained a delegation record for b.c.example.com that pointed to an entirely different server. When a recursive resolver passes a query to this server for the name a.b.c.example.com it does so because it has been told that this is an authoritative server for the zone c.example.com. However, the query does not contain any such information about intention, and the server will use the most specific served zone, in this case, the undelegated b.c.example.com zone, to answer the query.

QNAME Minimisation imposes a stricter regime on this situation. A QNAME minimizing resolver will use the query name b.c.example.com when querying this server and will correctly follow the zone delegation directions to the duly delegated server for this zone.

An illustration of the difference between these two cases is shown in Figure 3.

Diagram showing DNS resolution anomalies between full name and minimized name queries.
Figure 3 – DNS resolution anomalies between full name and minimized name queries.

This form of DNS configuration, where a single server is configured to serve both zones and direct or indirect ancestors of these zones, is not uncommon in the DNS. As long as all servers of a zone are kept in sync with each other and serve the same information then this DNS server situation will be largely unnoticed. However, two tools will explicitly follow the full delegation path and will not ‘short cut’ across zone cuts, namely DNSSEC validation and QNAME Minimisation. 

Status of recursive resolvers and QNAME Minimisation

There is a small set of recursive resolver implementation in use in the Internet today. This small set of DNS resolvers includes ISC’s Bind 9, NLnet Lab’s Unbound, CZ.NIC’s Knot and the Power DNS Recursor.

In Bind 9, QNAME Minimisation has been on by default since version 9.14.0. The configuration option is called qname-minimization and it can be set to off,relaxed and strict. The off setting disables QNAME Minimisation completely, strict proceeds with QNAME Minimisation as described by RFC 7816, and relaxed first tries QNAME Minimisation, but falls back to a regular resolution if it fails (presumably through the ENT issues described previously). The default setting is relaxed, although that may change in future releases of Bind.

In Unbound, QNAME Minimisation has been included since release 1.7.2 and is on by default. There are two directives: qname-minimisation, which is either yes or no; and qname-minimisation-strict, which determines fallback behaviour if the name fails to resolve. Strict mode yes turns off this fallback behaviour. The default in Unbound is not to use strict mode.

In Knot, QNAME Minimisation is enabled by default. In the struct kr_qflags the member NO_MINIMIZE can be turned on to disable this behaviour.

In Power DNS Recusor, QNAME Minimisation was implemented in 4.3.0-alpha1 and enabled by default since 4.3.0-beta1.

Measuring QNAME Minimisation

Let’s now turn to the measurement results.

We want to understand the extent of deployment of QNAME Minimisation in the DNS today, both as a count of the number of visible resolvers that ask authoritative servers and as a count of the proportion of users who send their queries to QNAME minimizing resolvers.

As usual, when attempting to measure the DNS, we need to take into consideration the conventional caching behaviour of resolvers. So, to expose the queries being made by resolvers we use a pair of unique dynamically generated labels in the test scenario. The labels were served by DNS servers that are operated as part of the measurement experiment and the query logs were analysed to determine the extent to which resolvers were performing QNAME Minimisation.

We ran this test from the 6 February 2019 until the 24 July 2019. During that period we saw 644,406 ‘visible’ resolvers (recursive resolvers that query authoritative servers). Of this set of visible resolvers some 69,869 resolvers queried for the intermediate name form, indicating that they were performing some form of QNAME Minimisation.

ResolversQminQuery Type
NSAAAAA
644,40669,86914,52355,36016
11%2%9%0%% of all resolvers
21%79%0%% of Qmin resolvers

Table 1a – Per Resolver QMin Counts: 2019

We reran the test this year from the 15 August until the 7 September. In these 24 days, we observed 240,287 unique IP addresses of visible DNS resolvers (Table 1b).

ResolversQminQuery Type
NSAAAAA
240,28727,9691,03226,9350
11%0%11%0%% of all resolvers
3%96%0%% of Qmin resolvers

Table 1b – Per Resolver QMin Counts: 2020.

In the shorter observation period in 2020 (Table 1b) we saw approximately one-third the number of DNS resolvers, but the same relative proportion, namely 11% of these resolvers, used QNAME Minimisation. So not much has changed here.

There is one significant change in the Query Type. In 2019, there was still some use of the NS Query Type; this has all but vanished in 2020, and the query type is now an A record.

This figure of 11% of all visible resolvers does not show to what extent QNAME Minimisation is being used in today’s DNS. For that, we need to count relative use, and one way of doing this is to count the query load.

QueriesNON QminQminQuery Type
NSAAAAA
1,107,728,8661,087,081,32920,647,5524,651,59915,993,2842,654
98%2%0%1%0%% of all
queries
23%77%0%% of Qmin
queries

Table 2a – Query Counts: 2019

In 2019, Some 2% of all queries were using QMin, and of these queries, some three-quarters of these QNAME minimized queries used the A Query Type, not the NS type.

QueriesNON QminQminQuery Type
NSAAAAA
756,582,911670,281,37680,364,1535,937,37980,364,1530
88%11%0%10%0%% of all
queries
6%93%0%% of Qmin
queries

Table 2b – Query Counts: 2020

Table 2b shows a distinct change since 2019. Now some 11% of all seen queries are for the minimized name and the overall majority of such queries use the NS Query Type. There has been an appreciable increase in the use of QNAME Minimisation over the past 12 months.

We can break this down a little further, by looking at the query patterns for each individual experiment. Table 3a shows the results from the 2019 measurement.

ExperimentsQminQuery Type
NSAAAAA
429,773,28811,089,8232,811,0538,336,0081,721
3%1%2%0%% of all
experiments
25%75%
0%% of Qmin
experiments

 Table 3a – Experiment Counts: 2019

The number of users that we observed using Qmin resolvers in 2019 was quite small: some 3% of users send their queries through QMin resolvers. This is the measurement that has changed significantly over 12 months. We now see some 18% of users using resolvers that support QNAME Minimisation.  

ExperimentsQminQuery Type
NSAAAAA
165,955,86530,166,1622,064,4998,336,0080
18%1%17%0%% of all
experiments
6%93%
0%% of Qmin
experiments

Table 3b – Experiment Counts: 2020

Where are these users? Table 4a lists those economies where we collected more than 20,000 sample points throughout the 2019 measurement period, and where 10% or more of the users in these economies used a recursive resolver that performed QNAME Minimisation.

ExperimentsSamplesQmin %Name
MG105,21673%Madagascar
IQ283,58543%Iraq
NP278,58543%Nepal
NE19,24432%Niger
BY214,91130%Belarus
AO268,28829%Angola
NZ135,71425%New Zealand
PT199,84723%Portugal
ZA817,38521%South Africa
MM23,94014%Myanmar
MY349,91412%Malaysia
AM23,08312%Armenia
UA291,95312%Ukraine
IR550,99911%Iran
CZ115,28410%Czech Republic

Table 4a – QNAME Minimisation query rates per economy: 2019

What a curious collection of economies! It is unclear whether service providers in these economies have enabled QNAME Minimisation deliberately, or whether this is an outcome of using a recursive resolver such as the recent version of the Bind 9 resolver or the Knot resolver, where this functionality has been enabled by default.

The list has changed somewhat over the past 12 months, notably in India where more than half of the user population there passes their queries through QNAME minimizing resolvers.

ExperimentsSamplesQmin %Name
CY43,46654%Cyprus
IR2,550,71953%Iran
NE192,21152%Niger
IN24,238,56351%India
BW42,77350%Botswana
NP293,49649%Nepal
MG192,51647%Madagascar
AF219,68843%Afghanistan
IQ1,483,95042%Iraq
ZW195,69141%Zimbabwe
DE2,808,83241%Germany
GM22,18538%Gambia
PT323,98436%Portugal
GE111,94836%Georgia
SI70,62336%Slovenia

Table 4b – QNAME Minimisation query rates per economy: 2020

Two economies of interest are not listed in Table 4: China, which has seen a growth of 4% to 14% of users over the past 12 months, and the United States, where the growth is from under 1% to 5% of users.

Open DNS resolvers

Just a little under one-third of all users in the Internet today have Open DNS resolvers in the DNS resolver set that they use.

In terms of the set of Open DNS resolvers deployed in the Internet, Google’s public DNS server does not appear to support QNAME Minimisation (which is the most popularly used DNS Open resolver). Within the collection of the 10 most popularly used Open DNS resolver services, Cloudflare’s 1.1.1.1 service, Quad9, and the OpenDNS service resolve their queries using QNAME Minimisation.

Table 5 shows the current measurements of the use of QNAME Minimisation for the major Open DNS resolvers in 2020.

Open DNS ResolverQmin RatioExperimentsQmin Experiments
Google DNS0%99,461,6121,397
114 DNS6%16,010,343887,461
Cloudflare50%9,202,1764,634,222
Open DNS69%8,049,9905,532,784
dnspai5%7,817,329417,661
onedns11%6,017,193644,946
Verisign0%1,122,7180
Quad 970%1,077,202785,760
Level30%913,1930
Yandex0%569,82911
Neustar59%563,892331,570
dnswatch57%235,789133,229
dyn58%157,76792,279
cnnic0%152,3080
greenteamdns0%86,05751
he97%57,38955,888

Table 5 – QNAME Minimisation query rates for Open DNS Resolvers: 2020

These measurements are interesting in that only one open DNS resolver — Hurricane Electric’s Open DNS service — has a 97% QNAME Minimisation ratio. The Open Resolver’s services that record ratios of between 50% and 70% raise a question as to what is happening here? Are the individual resolver engines used by the service at different levels of support for QNAME Minimisation? Or is some other DNS query pattern causing only some queries to be handled using QNAME Minimisation?

It is unclear to me whether QNAME Minimisation in a very heavily used public DNS resolver provides any substantive beneficial privacy outcome for the users of this service. In many ways, each user is ‘hiding in a crowd’ and their individual queries are lost in the volume of queries being made by such recursive resolvers in the first place.

It would also be expected that the Open Resolver’s caches would be heavily populated so the full query name would be unlikely to be passed to the servers at the higher levels of the DNS name hierarchy in any case. Yes, the recursive resolver is privy to each user’s DNS activity, but that is part of the direct consequences of using such a service in the first place and is unrelated to the QNAME Minimisation aspect of the resolver’s behaviour.

The story changes completely when using a small volume DNS resolver, such as a resolver in a home network. The small client pool means that the resolver can be linked to end users, particularly if the resolver’s clients share an IP address subnet with the resolver. A small volume recursive resolver may not have a continually refreshed local cache, so the full query names are more likely to be passed across to DNS servers at all levels in the DNS hierarchy.

As ever, all privacy bets are off when Explicit Client Subnet (ECS) attributes are attached to the query! But the true horror of ECS is best left as a story for another post!

From 3 to 18% in 24 months

Our measurements indicate that in mid-2020 some 18% of users pass their queries through resolvers that actively work to minimize the extent of leakage of superfluous information in DNS queries. This is a significant increase from the 3% of users seen some 12 months ago. Hopefully, this will rise to upward of 90% in the coming 12 months!

Rate this article

The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please answer the math question * Time limit is exhausted. Please click the refresh button next to the equation below to reload the CAPTCHA (Note: your comment will not be deleted).

Top