Main takeaways:

• Adoption of qmin is increasing slowly but steadily

• Implementation of qmin differs, depending on which resolver software is used

• Qmin can slightly increase the query load and lookups can fail in a few cases

So how are DNS queries privacy sensitive?

When an application (e.g. a browser or an email client) uses the DNS to look up the IP address of a domain name, it uses the domain’s full name. As a result, if you point your browser to www.netflix.com, it reveals to the DNS that you are likely interested in watching films. Similarly, a query to www.nos.nl reveals that you are probably interested in the latest news from the Dutch public broadcasting company. While those queries are probably not very privacy sensitive, a query for some-bad-disease.example.nl has the potential to reveal sensitive medical information.

As the DNS operator for the .nl TLD, SIDN receives more than a billion DNS queries a day for all sorts of different domain names. Our name servers don’t know the IP address of either example.nl or some-bad-disease.example.nl; they merely refer the querying resolver to the name servers for example.nl, disregarding the some-bad-disease. A resolver could therefore simply ask us for the name servers for example.nl, without revealing the full query name (some-bad-disease.example.nl). What we see in practice, however, is that more than 50 % of queries to the .nl name servers contain more information than necessary. The reasons for that are largely historical.

Minimising the query name

Query name minimisation (qmin), an IETF standard introduced in 2016 as (see RFC 7816), describes how recursive resolvers should limit the information revealed to the minimum. So, in the example above, a resolver should query us only for example.nl and only for its name servers, not for the IP address.

While that sounds simple enough, the concept of qmin is a little more complicated in practice. The main reason is that delegations can exist at any level. For example, a domain a.b.c.d.e.example.com might have name server delegations at any (or none) of the subdomains. The cut-off point where authority over one part of the domain ends, and another name server’s authority begins, is known as a zone cut. Consequently, qmin implementations theoretically have to query for the domain iteratively, increasing the length of the domain by one step each time, until a delegation is encountered.

Deployment

Because the standard is more than two years old, and because some resolver software already has qmin implementations, we were curious to know how far qmin deployment has progressed on the Internet.

We detected qmin support by utilising the fact that a non-qmin resolver will miss any delegation that happens in one of the labels before the terminal label. So, if we delegate to a different name server, with a different record for the terminal label in one of the labels before the terminal label, qmin resolvers will obtain a different answer from that obtained by non-qmin resolvers.

We, therefore, scheduled a series of longitudinal measurements using the RIPE Atlas measurement network. We performed a lookup with every resolver in the RIPE Atlas network by repeating queries for a.b.qnamemin-test.domain.example every hour, where the domain name in question was under our control. We were able to detect a non-qmin resolver because such a resolver will send a query for the full qname to the authoritative name server for qnamemin-test.domain.example, and will end up with a TXT reply containing the text: “qmin NOT enabled”. A qmin resolver will send a query for just the second-to-last label, b.qnamemin-test.domain.example, to the authoritative name server for qnamemin-test.domain.example. For that minimised query, it will receive a delegation to a different name server, which will return a TXT record containing the text: “qmin enabled.' In total, we tested over 18,000 resolvers.

Figure 1 below shows the adoption of qmin since May 2017. In our study period, adoption grew from 0.7% to 16.8%. The huge increase in April 2018 was mostly due to RIPE Atlas probes that rely on Cloudflare’s open resolver, which supports qmin by default since April 2018. Updated numbers are published daily here.

Figure 1: The adoption of qmin since May 2017

As well as using RIPE Atlas, we measured the adoption of qmin by checking open resolvers and the .nl name servers. First, we queried a list of 1.2 million open resolvers which map to 110,000 unique IP addresses, observed by our authoritative name servers. Out of those, only 1.6% were found to support qmin.

Within .nl, the situation looks slightly better (see Figure 2). Since June 2017, the number of queried second-level domain names has increased from around 33% to 44% today. We assume that a resolver supports qmin if it sends mostly queries for the two rightmost labels of a domain name (example.nl in some-bad-disease.example.nl). You can find daily updated statistics on our statistics website stats.sidnlabs.nl.

Figure 1: The adoption of qmin in the .nl domain since June 2017

Implementation

According to the standard, a resolver that implements qmin should iteratively increase the name length by one label, querying for the NS type, until it reaches the full name. Then it should switch to the original query type. In practice, however, we see that qmin is implemented in many different ways, but never quite as described in the standard.

We used RIPE Atlas again and let each probe’s resolver query a test domain with 24 labels under our control. By collecting the queries directly from the authoritative name server, we see that resolvers that implement qmin do not send one query for every single label, but usually send a query for the first few labels and then skip to the last label of the query name. Knot DNS and BIND start off by sending NS queries, but Unbound queries for A records only. Resolvers adopt such strategies to reduce the query load and avoid getting stuck in misconfigured zones. The following table shows how many resolvers we observed exhibiting the different behaviours.

Table 1: Top 6 signatures seen at Authoritative Resolvers, mapped to resolver implementations

By signature we mean the following: To group resolver behaviour, we map the incoming query behaviour observed at our authoritative name server to signatures, containing length, order, and type of inbound queries. Our test domain is at the second label depth, so we observe queries starting from the third label depth. For example, an algorithm asking for NSat the 3rd label, then for NSat the 4th label, and then for A at the final, 24th, label, will be mapped to the signature 3NS-4NS-24A.

Performance hit

Finally, we were curious to know whether qmin has any impact on performance or the query success rate. We set up a testbed, with resolvers running Unbound (version 1.8.0), Knot (3.0.0) and BIND (9.13.3), and queried the million most popular domain names, as listed in the Cisco Umbrella top list. Unbound and BIND both support strict and relaxed versions of qmin, so we tested both versions in each case. In strict mode, resolvers do not fall back to sending the full QNAME to potentially broken name servers. We started our measurements with an empty cache.

Depending on the implementation, we measured an increase in queries of between 19% in Unbound and 26% in BIND. The actual increase with production resolvers is probably lower because caching will reduce the overhead.

We also noticed that we were unable to resolve some of the domain names when running the resolvers with the strictest implementations of qmin: up to 3% with Unbound and up to 5% with BIND. Fortunately, however, we did not observe any increase when Unbound was run in relaxed mode and only a 0.5% increase with BIND in relaxed mode. The table below summarises our measurement results. Note that the relatively high number of errors, even with qmin disabled, is a property of the Umbrella top list.

Table 2: Performance and result quality acrossqminmodes and resolvers

Measure qmin yourself

You can test whether your resolver supports qmin by querying the domain below, using the command line tool dig, which relies on the same technique:

dig a.b.qnamemin-test.internet.nl TXT

Conclusion: the DNS is becoming more private

Our results show that qmin is on the rise, which we believe is a good thing. The slight decrease in performance is an acceptable trade-off for an increase in privacy for Internet users and the performance penalty in production is probably lower than observed in our tests.

You can find more details about the measurements in our paper, which was produced in collaboration with Quirin Scheitle (Technical University of Munich), Willem Toorop and Ralph Dolmans (both NLnet Labs) and Roland van Rijswijk-Deij (NLnet Labs and University of Twente). We have also made our award-winning data sets public.

This blog was originally published on the SIDN Labs Blog