Every request begins with a name: DNS, discovery and the cost of resolution

Year 1 / Module 8 Computer systems, networks and security / Unit 4 / Every request begins with a name: DNS, discovery and the cost of resolution

Every request begins with a name: DNS, discovery and the cost of resolution

HCI1108 · Unit 4 of 10

Because naming is a cached distributed database, its design choices decide both how quickly a design recovers from failure and who is able to observe where a user is going, and neither consequence is settled by encrypting the lookup alone.

Every request begins with a name: DNS, discovery and the cost of resolution

A person types a name, and a connection opens somewhere. Between those two events a lookup happens, carried out by the domain name system on nearly every request. Mockapetris (1987a) specified that system as a distributed, hierarchical database whose resolvers cache what they learn. The time to live on each record decides how long an answer may be reused. The cache is the design, and it decides two things. It decides how quickly the system recovers when a name fails, and it decides who can see where a person is going. Both consequences were built into naming before anyone thought about security, and encryption settles only one of them. The unit that follows asks what the connection does with a resolved name.

Resolution is a cache with a lifetime, not a query

Mockapetris (1987a) sets out the model the rest of the unit depends on. Names are delegated down a tree, and a resolver that already holds an answer returns it without asking anyone. The time to live on a record bounds that reuse, and a zero value prohibits caching. The companion specification (Mockapetris, 1987b) fixes the message format and the resolver's retry and timeout behaviour. It works on the assumption that the worst-case round trip is five to ten seconds. A failed lookup is not an error message. It is a delay with a published shape.

The design produces a system whose copies disagree. Schomp and colleagues (2013) probed for open resolvers, doubling the previous estimate of their number from fifteen to thirty-two million. Twenty per cent imposed at least one hundred milliseconds of delay before a query left the resolving infrastructure. Only nineteen per cent consistently returned correct time to live values, so the lifetime an authoritative server sets is often distorted before the answer reaches the client.

The cache is the surface an attacker can write to

Wang (2014) returns to the attack that made naming a security topic. Cache poisoning does not break a cipher. It places a forged answer into a resolver's cache, so clients are sent to a server the attacker chose and the wrong binding is reused until its lifetime expires. Wang examines the attacker's choice space under a maximum-efficiency model, and studies which parameters can be tuned in favour of a forged answer. He proposes defensive measures, calling the attack arguably the most dangerous against DNS while DNSSEC is still on its way to global deployment. The failure belongs to the design. The shared cache that makes resolution fast is what is exploited.

Recovery is a placement decision

Partridge, Mendez and Milliken (1993) make recovery a routing decision rather than a data decision. In anycasting, several servers share one address, and the routing system selects which instance receives a datagram. They motivate it with a resolver sending to a well-known address instead of a configured list. They note that routers may wish to avoid an instance that has crashed recently.

The specification supplies the case and its limit. Its worked example is a resolver that need not be configured with the addresses of its servers, and can query a well-known DNS anycast address instead. Routers handle failure by preferring another instance, and on a local network the memo suggests hosts keep the address mapping for about a minute so a dead server is dropped quickly. The limit is recorded in the same document. Nothing verifies membership in an anycast address, so a host can volunteer to serve that address and divert queries to itself. An eavesdropper can answer with false information undetected. Recovery by routing sits where the client cannot inspect it.

The encrypted lookup was standardised twice, at a measured cost

Plain resolution was designed to be connectionless and readable. Zhu and colleagues (2015) treat that choice as the cause of three problems: eavesdropping that compromises privacy, source-address spoofing that enables denial-of-service attacks, and reply-size limits that constrain key sizes. Their design, T-DNS, runs resolution over TCP with transport-layer security. Their evaluation reports roughly nine per cent extra latency to the recursive resolver, and twenty-two per cent when TCP reaches the authoritative server.

The field then standardised both routes they sketched. Hu and colleagues (2016) carry queries over a TLS connection on a dedicated port, gaining confidentiality and integrity at the cost of statelessness. Hoffman and McManus (2018) carry the same queries inside HTTPS, so a lookup can travel on a connection the browser already holds.

What a signature proves is not confidentiality

Arends and colleagues (2005) state that the security extensions provide origin authentication and integrity protection for DNS data. They state in the same passage that they do not provide confidentiality.

Chung and colleagues (2017) measured adoption and tried to sign domains bought from leading registrars. They report that one per cent of .com, .net and .org domains were properly signed. Forty per cent of domain owners using a third-party operator did not complete the required steps. A security property of naming is decided by an intermediary with no stake in it.

The measurement tests the promise

Lu and colleagues (2019) ran the first end-to-end, large-scale measurement of encrypted resolution. Accessibility and latency were satisfying, and encrypted queries were less likely to be disrupted by in-path interception. The operational findings are less so. Twenty-five per cent of DNS-over-TLS providers used invalid certificates. Encrypted resolution was used by far fewer users than plain resolution.

Bortzmeyer, Dolmans and Hoffman (2021) specify query name minimisation, in which a resolver sends upstream only the part of the name each authority needs. They record the price: a cold resolver sends more queries, one per label. ververis and colleagues (2025) measured the mechanism meant to make encryption automatic, the discovery of designated resolvers. They found configuration errors that would leave a compliant client failing to upgrade in over ninety-nine per cent of observed cases. More than ninety-seven per cent of enabled resolvers delegated to major DNS cloud providers.

Contested question: does encrypting the lookup conceal where a person goes?

The disagreement is between two readings of the same encryption. The first holds that confidentiality between client and resolver is the property that matters. Zhu and colleagues (2015) claim protection from eavesdroppers on the path, and Hu and colleagues (2016) and Hoffman and McManus (2018) standardise it. On that reading traffic metadata is a separate matter.

Siby and colleagues (2020) argue that the separate matter is the whole problem. They build a traffic-analysis attacker for encrypted resolution. They report that it identifies visited domains using one hundred and twenty-four times less data than the equivalent attack on HTTPS flows. They find the standardised padding schemes ineffective, and they conclude that client location, resolver and platform degrade but do not stop the attack. Their adversary sits between client and resolver, so the encryption hides the question from everyone except the party the client chose to ask. That is where the critique meets ververis and colleagues (2025). If more than ninety-seven per cent of enabled resolvers delegate to a few cloud providers, confidentiality to the resolver becomes concentration of observation.

The evidence that would settle the question is not in print. It would need three things: an adversary position stated in advance, an inference experiment on padded traffic at realistic overheads, and a measure of whether consolidation changes what one provider can infer. Lu and colleagues (2019) measured availability and latency but not inference. Siby and colleagues measured inference in controlled collection, and ververis and colleagues measured configuration.

A second dispute asks whether encrypted resolution is late because of the protocol or of deployment. Chung and colleagues (2017) find the same pattern in DNSSEC, where adoption waits on registrars.

The evidence on each side is of a different kind. The confidentiality position rests on standardised documents and an evaluation by their designers (Zhu et al., 2015; Hu et al., 2016; Hoffman and McManus, 2018). The traffic-analysis position rests on one controlled inference study (Siby et al., 2020) and on one deployment measurement (ververis et al., 2025). While the dispute is open, the designer states the adversary's position before claiming confidentiality and treats the resolver as a party the user chooses rather than a neutral one, though on a managed device the choice is made for them. The strongest objection is that this unit treats concentration as the live risk on the strength of one measurement of delegation, and concentration alone does not show that a provider learns more than the pattern Siby and colleagues recover.

Where the argument is heading

The direction of the field is to move from a configured resolver to a discovered one, and to treat concentration as the live risk. Bortzmeyer, Dolmans and Hoffman (2021) minimise what each stop in the lookup learns. ververis and colleagues (2025) found the discovery mechanism meant to make encryption automatic failing in the field, and where it works, pushing delegation towards a few cloud providers. The open question is no longer whether the lookup can be encrypted. It is who ends up holding the encrypted lookups, and what a client can prove about the resolver it silently accepted.

The sources this unit rests on

Mockapetris, P. V. (1987a). Domain names: concepts and facilities. RFC 1034. doi:10.17487/rfc1034 Specified the domain name system as a distributed, hierarchical database served by caching resolvers, with the time to live controlling how long an answer may be reused. The cache is the design, so speed and staleness arrive together.
Mockapetris, P. V. (1987b). Domain names: implementation and specification. RFC 1035. doi:10.17487/rfc1035 Fixed the message format, the record types and the resolution procedure, including retransmission timeouts and a working assumption that the worst-case round trip is five to ten seconds. The timing of a failed lookup is published behaviour.
Partridge, C., Mendez, T. and Milliken, W. (1993). Host anycasting service. RFC 1546. doi:10.17487/rfc1546 Proposed a service in which servers share one address and the routing system selects the instance that receives a datagram, motivated with a resolver sending to a well-known address rather than a configured list. Recovery needs no client-visible change.
Arends, R., Austein, R., Larson, M., Massey, D. and Rose, S. (2005). DNS security introduction and requirements. RFC 4033. doi:10.17487/rfc4033 Defined the goals of the security extensions as origin authentication and integrity of DNS data, and stated that they do not provide confidentiality. Integrity of an answer and privacy of a question are different products.
Schomp, K., Callahan, T., Rabinovich, M. and Allman, M. (2013). On measuring the client-side DNS infrastructure. Proceedings of the 2013 Internet Measurement Conference. doi:10.1145/2504730.2504734 Discovered the client-side resolving infrastructure and doubled the previous estimate of open resolvers from fifteen to thirty-two million, reporting that only nineteen per cent consistently returned correct time to live values. The measurement reaches the resolver, not the authoritative server.
Wang, Z. (2014). A revisit of DNS Kaminsky cache poisoning attacks. 2014 IEEE Global Communications Conference (GLOBECOM). doi:10.1109/glocom.2014.7417017 Examined the attacker's choice space under a maximum-efficiency model, studied which parameters can be tuned in favour of a forged answer, and proposed defensive measures. It reopens an attack treated as settled.
Zhu, L., Hu, Z., Heidemann, J., Wessels, D., Mankin, A. and Somaiya, N. (2015). Connection-oriented DNS to improve privacy and security. 2015 IEEE Symposium on Security and Privacy. doi:10.1109/sp.2015.18 Built and evaluated T-DNS, which runs resolution over TCP and transport-layer security, measuring roughly nine per cent additional latency to the recursive resolver and twenty-two per cent with TCP to the authoritative server, with connection reuse of sixty to ninety-five per cent. The encrypted lookup is affordable.
Hu, Z., Zhu, L., Heidemann, J., Mankin, A., Wessels, D. and Hoffman, P. (2016). Specification for DNS over Transport Layer Security (TLS). RFC 7858. doi:10.17487/rfc7858 Specified carrying resolution over a TLS connection on a dedicated port, giving confidentiality and integrity between client and resolver, at the cost of the statelessness plain resolution had. The route is standardised, not experimental.
Chung, T., van Rijswijk-Deij, R., Choffnes, D., Levin, D., Maggs, B. M., Mislove, A. and Wilson, C. (2017). Understanding the role of registrars in DNSSEC deployment. Proceedings of the 2017 Internet Measurement Conference. doi:10.1145/3131365.3131373 Measured DNSSEC adoption and attempted signing at leading registrars, reporting that one per cent of .com, .net and .org domains were properly signed. Forty per cent of owners using a third-party operator did not finish the required steps.
Hoffman, P. and McManus, P. (2018). DNS queries over HTTPS (DoH). RFC 8484. doi:10.17487/rfc8484 Defined how to carry DNS queries and answers inside HTTP over TLS so that a lookup can travel on a connection the client may already hold. It is the second standardised route to the same privacy goal.
Lu, C., Liu, B., Li, Z., Hao, S., Duan, H., Zhang, M., Leng, C., Liu, Y., Zhang, Z. and Wu, J. (2019). An end-to-end, large-scale measurement of DNS-over-encryption: how far have we come? Proceedings of the Internet Measurement Conference. doi:10.1145/3355369.3355580 Measured encrypted resolution end to end, finding accessibility and latency satisfying but a quarter of DNS-over-TLS providers used invalid certificates and few users had adopted it. Availability and use are different facts.
Siby, S., Juarez, M., Diaz, C., Vallina-Rodriguez, N. and Troncoso, C. (2020). Encrypted DNS -> privacy? A traffic analysis perspective. Network and Distributed System Security Symposium. doi:10.14722/ndss.2020.24301 Built a traffic-analysis attacker for encrypted resolution, identified visited domains using one hundred and twenty-four times less data than attacks on HTTPS flows, and found the standardised padding schemes ineffective. It is the sharpest counter-argument.
Bortzmeyer, S., Dolmans, R. and Hoffman, P. (2021). DNS query name minimisation to improve privacy. RFC 9156. doi:10.17487/rfc9156 Specified sending only the part of a query name that each authority needs, so no operator learns the whole name being resolved, and recorded the cost: a cold resolver sends more queries, one per label. Privacy is paid for in queries.
ververis, v., Sassala, S., Roth, F. and Bajpai, V. (2025). Path to encrypted DNS with DDR: adoption, configuration patterns and privacy implications. Proceedings on Privacy Enhancing Technologies. doi:10.56553/popets-2025-0140 Measured deployment of the mechanism that lets a client discover its network's encrypted resolver: configuration errors would leave a compliant client failing to upgrade in over ninety-nine per cent of observed cases, while more than ninety-seven per cent of enabled resolvers delegated to major DNS cloud providers. An available encrypted resolver and a used one differ.

Check your understanding & apply it · 4 questions, 1 essay

1A team sets a very long time to live on a record that points at a load balancer it may fail over within minutes. What does the unit's account of the cache predict?

2A hospital encrypts all its name lookups to a resolver it trusts and concludes that a forged-answer attack is now closed. Which correction does the unit's account of poisoning support?

3An operator claims that because its lookups are encrypted, no observer between the client and the resolver can learn which sites a user visits. Which judgement does the unit's evidence support?

4A team adopts query name minimisation to reduce what each stop in the lookup learns, and expects no change in query volume. What does the unit's account predict?

5Essay A hospital network proposes to send every name lookup to an encrypted resolver run by one large public provider, and argues that this makes it safe to log which external sites staff and patients reach. Using Mockapetris (1987a, 1987b) on caching and its lifetime, Schomp and colleagues (2013) on what the client-side resolving infrastructure measures, Partridge, Mendez and Milliken (1993) on anycasting, Wang (2015) on cache poisoning, Arends and colleagues (2005) on what a signature proves, Zhu and colleagues (2015) on the cost of the encrypted route, Chung and colleagues (2017) on registrar-dependent deployment, Lu and colleagues (2019), Bortzmeyer, Dolmans and Hoffman (2021), Siby and colleagues (2020) and ververis and colleagues (2025), write an assessment that (a) states which failure and which exposure the proposal addresses and which it leaves untouched, (b) makes the strongest case for the proposal, (c) makes the strongest case against it, and (d) names the measurement that would decide between the accounts and one observation that would count against the proposal.

The proposal addresses one exposure and one failure. It hides the lookup from an observer between the client and the resolver, which the transport routes are built to do, and it moves resolution off a resolver the network may not control, which matters because Schomp and colleagues (2013) found that only nineteen per cent of open resolvers consistently returned correct time to live values and that twenty per cent imposed at least one hundred milliseconds of delay before a query left the resolving infrastructure. It does not address the failure that has nothing to do with encryption. Wang (2015) shows that a forged answer placed in a resolver's cache is reused until its lifetime expires, which is a property of caching that Mockapetris (1987a, 1987b) builds in, and no transport encryption prevents it. It does not address integrity either, since Arends and colleagues (2005) state that the security extensions, which do provide origin authentication and integrity, explicitly do not provide confidentiality, so the proposal buys the opposite of what a signature buys. The strongest case for the proposal is real. Plain resolution is readable on the path, the encrypted alternatives are standardised and affordable, and Zhu and colleagues (2015) measured roughly nine per cent additional latency to the recursive resolver, so the friction is small. Bortzmeyer, Dolmans and Hoffman (2021) can reduce what each stop in the lookup learns even against an observer. The strongest case against is that it concentrates observation rather than removing it. Siby and colleagues (2020) place an adversary between client and resolver and still identify visited domains using one hundred and twenty-four times less data than attacks on HTTPS flows, finding the standardised padding ineffective, so the provider the hospital trusts becomes the party with the clearest view. ververis and colleagues (2025) show where that concentration lands: more than ninety-seven per cent of enabled resolvers delegated to major cloud providers, and configuration errors would leave a compliant client failing to upgrade in over ninety-nine per cent of observed cases. Lu and colleagues (2019) add that availability is not use, since few clients had adopted what was already reachable. The measurement that would settle the choice is an inference experiment run on traffic padded at the overheads the deployment actually uses, with the adversary position stated in advance, comparing what one provider can infer across its customers against what an on-path observer can infer with no encryption. The observation that would count against the proposal is a single provider identifying the visited domains from the padded traces of its own clients. Chung and colleagues (2017) give the reason to expect a deployment to fail on its own, since adoption of a naming security property waits on intermediaries rather than on the site that wants it. Partridge, Mendez and Milliken (1993) supply the alternative that needs no change of resolver at all, since an anycast address lets the routing system move a request away from an instance that has failed.