"K-resolver" presented at NDSS MADWeb 2020

Abstract: Centralized DNS over HTTPS/TLS (DoH/DoT) resolution, which has started being deployed by major hosting providers and web browsers, has sparked controversy among Internet activists and privacy advocates due to several privacy concerns. This design decision causes the trace of all DNS resolutions to be exposed to a third-party resolver, different than the one specified by the user’s access network. In this work we propose K-resolver, a DNS resolution mechanism that disperses DNS queries across multiple DoH resolvers, reducing the amount of information about a user’s browsing activity exposed to each individual resolver. As a result, none of the resolvers can learn a user’s entire web browsing history. We have implemented a prototype of our approach for Mozilla Firefox, and used it to evaluate the performance of web page load time compared to the default centralized DoH approach. While our K-resolver mechanism has some effect on DNS resolution time and web page load time, we show that this is mainly due to the geographical location of the selected DoH servers. When more well-provisioned anycast servers are available, our approach incurs negligible overhead while improving user privacy.

The datasets

For the reproducibility of our paper, we also make the data used in our paper available here.

MADWeb Q&A

We are very thankful for all attendees of NDSS MADWeb 2020 for their constructive questions. We hereby briefly summarize the questions asked during the Q&A of our talk together our responses.

Q1: If you choose to always send the same domain to the same resolver, this particular resolver will learn your your visiting frequency to this domain. Is this bad for privacy?

A1: Our design choice is to make sure one’s visit to a domain can ONLY be known to ONE resolver, which we argue that this design choice is better than exposing the visit to more than one resolver. Although rotating the resolution for a particular domain seems to remedy this problem, but this design is not optimal for the user’s privacy. As far as we are concerned, DNS caching maybe a good solution for this problem.

Q2: Have you thought of a case in which adversaries can collude and try guessing all domains visited by a user using a priori theory?

A2: In our threat model, we are not taking colluding adversaries into consideration. In an ideal future, when there is a significant number of DoH/DoT resolvers become available, we believe that “colluding” is not really an option if K is large enough.

Q3: What if two different sub domains (e.g., a.youtube.com, b.youtube.com) belong to the same company?

A3: Our current hash function used in K-resolver is unaware of this context. As we mentioned in the discussion session of our work, a category-specific hash function can cope with this issue.

Recommendation for A3: we can try looking at the authoritative name server of the sub domains (or their same subnet) to examine if the sub domains are owned by the same entity.

Q4: Regarding the design of your K-resolver in Firefox, how do you resolve DNS queries when a user uses the same tab for diff domains, or input the same domain in two diff tabs?

A4: It’s our design choice to make sure that regardless of where the “parent” domain is input, as long as the domain is navigated in the URL bar, it is always resolved by the same resolver. Typing a new domain into the URL bar will trigger our K-resolver mechanism to pick a new resolver based on the hash value of the domain.