N0TH1NG T0 H1D3

Improving DNS privacy on Tor exit relays

DNS caching has many advantages, such as decreasing DNS response latency, decreasing the amount of outgoing connections and increasing system efficiency. Aside from performance and speed, DNS caching also has a significant privacy advantage. By reducing the number of outgoing DNS queries, fewer domain lookups are leaked outside the DNS server. This increases user privacy and adds some resistance to correlation attacks, in turn making it harder for adversaries to depseudonymize Tor users.

On the other hand, utilizing DNS caching (even when caching all the domains used in the world) adds another attack vector that must be considered: timeless timing attacks [1]. An adversary is able to determine when a domain is no longer cached by repeatedly querying for the DNS record, effectively making it possible to find out when the DNS record was first requested by a Tor user with some granularity [2].

In a world where:

  1. The NSA targets Tor operators, the Tor network infrastructure/relays and Tor users [3] on a structural basis.
  2. Global surveillance systems like XKeyscore [4] and its brothers and sisters [5] provide detailed insight (when needed) to most of the internet’s traffic, no matter where your autonomous system is situated.
  3. Developments and improvements on global surveillance systems have been mostly unknown to the public for more than ten years now (i.e. current scope, capabilities and retention have significantly improved).
  4. Germany actively surveils traffic of its citizens and others that use the Tor network [6] (added on 10-10-2024).

One sufficiently paranoid can reasonably assume the vast majority of outgoing DNS queries can and will be monitored on a real-time basis, adding unnecessary risks to Tor users. To mitigate these risks, a DNS setup mitigating both correlation attacks and timeless timing attacks would be ideal.

Nothing to hide is actively working towards such a system in 2024 and 2025 and in this blog we share our first thoughts on this topic.

1 Improved DNS setup

The ideal solution would be a DNS implementation that utilizes DNS caching extensively and is 100% resistant to both correlation and timeless timing attacks. But ideal doesn’t exist, so we have to settle for suboptimal. In this case these suboptimal performance indicators would be “the cache hit rate is as close to 100% as possible” or “the amount of cache misses is as close to 0 as possible”, while removing the relation between Tor user’s DNS lookup requests and outgoing DNS queries. For this, we came up with a setup that:

  1. Increases and randomizes TTL values.
  2. Uses extensive preloading of DNS records.
  3. Utilizes automatic refreshes for a long period of time.

This setup implements the DNS cache defenses at the DNS layer rather than in Tor. Having the option to implement these defenses independently of Tor will make it work with Arti in the future too and enables for improving or adding new defense layers with relative low effort.

1.1 Longer and random TTL

One of the objectives is to make the cached DNS records less predictable. TTL values are public by nature, so the idea is to ignore public values and set our own TTL values. As an example, this can look something like:

Assigning a random TTL value is actually somewhat similar to the inner workings of Tor’s internal DNS cache [7][8]. This way the original TTL value and the TTL value in our DNS servers don’t correspond, making it significantly harder for adversaries to correlate a DNS query to a user’s DNS lookup request. This is especially important in the scenarios where a person (e.g. a dissident) visits an obscure domain that’s not part of the cache already.

Another protection mechanism could be to lie about our cached records’ TTL values to anyone requesting a record. For example, always respond with a fixed TTL value or respond with a random TTL value (at the cost of more system overhead).

1.2 Extensive preloading

A list of the most popular domain names will be created regularly. Lists such as the Cisco Umbrella 1 Million, Cloudflare Radar Top 1,000,000 Domains and Tranco Top Sites 1,000,000 Ranking can be used for this purpose. These lists are merged, duplicates are removed and www subdomain counterparts are added. This list is then preloaded for both IPv4 A and IPv6 AAAA records in the DNS cache.

Many of these domains get visited frequently and by preloading them, the user’s DNS lookup requests for these domains are completely disconnected from a outgoing DNS query. Preloading this many domain names should increase the DNS cache hit rate considerably.

It’s important to preload this list every time the DNS cache starts out empty (e.g. after a server reboot), otherwise millions of DNS queries (the first for each record) would be exposed.

1.3 Automatic refreshes

From the moment a domain is looked up once, the domain will be continuously refreshed close to the end of their respective TTL cycle (ideally with a randomized offset) for a long retention period (e.g. 7 or even 30 days). Every time a domain’s record is requested, the ‘purge timer’ will be reset to zero. If a domain’s record has not been requested for the retention period, it gets purged from the cache to not let it linger around indefinitely. These same mechanics apply to the preload list.

Many domains have short TTL values, meaning that normally a DNS cache will only cache them for a limited amount of time (e.g. 5 minutes). A DNS lookup request after the TTL value expired will result in another outgoing DNS query. But with automatic refreshing of DNS records at a random time before they expire, DNS lookup request can’t be correlated to the outgoing DNS query (at least not until they are purged after the retention period).

It would be neat if the automatic refresh mechanics could be implemented in the DNS software itself, but failing this a dedicated piece of software that runs these queries in the background (effectively also refreshing the DNS records if timed well) may be a much more complex workaround. Also it’s important to make sure the (fixed) order of refreshing DNS records won’t provide any insight to adversaries.

2 Shortcomings

There may be considerable advantages to such a DNS setup, but that doesn’t mean there aren’t also shortcomings:

  1. DNS cache misses still exist.
  2. Domain groupings.
  3. Required infrastructure.
  4. It doesn’t exist yet.
  5. Only A and AAAA records.
  6. No visited domains in preload list.

2.1 DNS cache misses

DNS lookup requests that result in DNS cache misses still exist. This is especially true for obscure domains and it might be especially obscure domains that impose the greatest risk for Tor users. This risk is partly mitigated by the longer and random TTLs though. It’s impossible to preload all used domains in the world because this information is only known to the TLD registries (and sometimes a handful of researchers). Also see 2.6.

2.2 Domain groupings

Long live the modern day internet, where one visit to a website could result in DNS lookup requests for tens of other domains. And each of those domains could be detrimental to the user’s privacy, if they weren’t preloaded and/or cached already. This is a problem that is not easy to fix, but one method would be to visit the preload domain list with a headless browser, log all the domains requested and add them to the preload list. This might be a good ‘phase 2’ of this project.

2.3 Required infrastructure

One big drawback is that this DNS setup requires considerable system resources. This might not be a problem for large scale relay operators, but may be difficult to manage for smaller scale relay operators. That said, the 6 biggest exit relay operators together provide almost 50% of the exit relay consensus weight. Assuming DNS queries are distributed proportionately to this percentage and large scale relay operators would use this or similar DNS setups, then a large part of the Tor network could benefit. Also smaller scale relay operators could still use the DNS servers of large scale relay operators. This kind of DNS centralization (especially with a few trusted parties) is actually preferable according to a research paper about the effect of DNS on Tor’s anonymity [9].

The impact on the world wide DNS infrastructure should be negligible. Even the whole of the Tor network’s DNS queries combined is probably not much more than a rounding error in the DNS.

2.4 It doesn’t exist yet

The improved DNS setup doesn’t exist yet and currently there is no piece of software that’s able to do this out of the box. Fortunately PowerDNS (the DNS frontend and backend we use) is pretty extensible so this is something we want to invest in if we get the green light from the Tor Project about an option to disable Tor’s internal cache (more in 3). There also is a chance we can get a small subsidy for the changes to PowerDNS, which would help out greatly.

2.5 Only A and AAAA records

In this setup only A and AAAA records are preloaded to the DNS cache. It may be beneficial to also add other DNS record types such as MX records in the future.

2.6 No visited domains in preload list

Extensive preloading based on top 1,000,000 domain lists will provide a good preloading base, but obscure domains that were recently visited won’t be part of the preload list. When the DNS cache is emptied (for example after a server reboot or service restart), all the obscure domains are gone as well and new DNS lookup requests will result in DNS leaks again.

A potential solution for this is to make frequent ‘snapshots’ or backups of the DNS cache, and ‘insert’ it to the DNS cache after it is emptied. Or to export cache misses back to the preload list. In any case, it’s paramount to address privacy and security risks when such DNS cache exports will be created. If the cache misses would end up in a public preload list then it might give away too much information to adversaries about obscure but sensitive domains.

3 Changes to Tor

In order for this DNS setup to work, Tor’s internal DNS cache must be disabled. This cache is hardcoded so cannot be disabled by some flag. We started a conversation in the Tor community to find the best method to disable this cache in Tor. It looks like the Tor Project will come up with a branch to address this change. Meanwhile Nothing to hide will be working on the technical challenges.

Footnotes

[1] https://www.usenix.org/system/files/sec23summer_458-dahlberg-prepub.pdf
[2] Tor has some defenses in place here, but it’s a can of worms
[3] https://daserste.ndr.de/panorama/aktuell/nsa230_page-1.html
[4] https://en.wikipedia.org/wiki/XKeyscore#cite_note-NDR-5
[5] https://en.wikipedia.org/wiki/Global_surveillance
[6] https://marx.wtf/2024/10/10/law-enforcement-undermines-tor/
[7] https://gitlab.torproject.org/tpo/core/tor/-/blob/main/src/core/or/connection_edge.c#L500
[8] https://gitlab.torproject.org/tpo/core/tor/-/blob/main/src/core/or/connection_edge.h#L193
[9] https://nymity.ch/tor-dns/tor-dns.pdf