DNS Query Complexity and Post-Quantum DNSSEC Under Scrutiny

At the 126th meeting of the Internet Engineering Task Force (IETF) in Vienna, Austria, at the end of July 2026, discussions about the Domain Name System (DNS) revealed both the hidden complexity of everyday DNS lookups and experiments aimed at making DNS security ready for quantum computers. Geoff Huston, reporting on the APNIC blog, summarized two key sessions: a deep dive into recursive resolver query behaviour by Ondřej Surý of the Internet Systems Consortium (ISC), and post-quantum DNSSEC ideas presented by Johan Stenstam.

A recursive resolver is the part of the DNS that does the legwork when your computer asks for a website: it starts with no knowledge about the name and repeatedly queries other DNS servers until it finds the answer. Surý examined what happens when such a resolver starts with a completely empty cache, known as a cold cache. His startling example was an IPv6 reverse name, where the query asked for a pointer (PTR) record. Resolving that single name took BIND 2.18, a widely used DNS server software, a staggering 329 queries. Not every name is that complex, but without a pre-warmed cache, the resolver's inner navigation through the DNS hierarchy becomes visible.

Several factors drive up the query count. A DNS name can have many delegation points, which are the boundaries where authority for part of the name is handed to different servers. Often those authoritative servers live in a different part of the DNS tree, called out-of-bailiwick nameservers, forcing extra lookups. Canonical names (CNAMEs), which act as aliases redirecting one name to another, can trigger entirely new resolution chains. DNSSEC validation, which verifies digital signatures on DNS data, adds further queries for Delegation Signer (DS) records up the chain. Even a simple name like www.example.com shows this web of implicit trust: a cold resolver needs a priming query for the root zone, then a query to a root server for a .com server, then a query to a .com server for an example.com server, and finally the terminal query. That seems like four points of trust, but because there are thirteen named root servers and thirteen .com servers, and because root server names themselves live in the .net zone, the full trust picture includes all of those servers too. The Transitive Trust Checker tool illustrates this network of dependencies.

Glue records add another layer. When a resolver needs the IP address of a nameserver that sits inside the same domain it is trying to resolve, the response may include those addresses in an additional section. In cases of circular dependence, the resolver is forced to trust them. Historically, glue records were included generously, but that was abused for DNS cache poisoning, where attackers inject false glue records to redirect users to malicious sites. Modern resolvers are supposed to enforce a strict in-bailiwick condition: they only trust a glue record if the nameserver's name lies within the zone being resolved. CNAME chains are especially common in content distribution networks. For example, resolving teams.microsoft.com first triggers a resolution in .com, which then leads to a chain of CNAMEs ending in the .net domain, spawning a completely new sequence of queries. Microsoft.com itself uses nameservers in azure-dns.org, azure-dns.info, azure-dns.com, and azure-dns.net, all outside its own domain, adding to the complexity.

Resolver designers face a tough choice. The "resolve everything" approach resolves the names of all out-of-bailiwick nameservers at every delegation level, which is thorough but can be exploited by malicious actors who craft names that trigger heavy workloads. The "selective resolution" approach picks a single nameserver at each level, which is efficient if that server responds, but if it fails, falling back to another server may require a full re-resolution. Surý's recommendations for domain operators and resolver implementers are practical: prefer in-domain nameservers whenever possible, limit managed DNS providers to at most two, avoid long CNAME chains, use aggressive NSEC caching (a DNSSEC feature that can prove non-existence efficiently), and set longer Time to Live (TTL) values on DNS records so that resolvers can serve answers from cache longer. He also noted that pre-resolving all nameserver names before processing creates work with little benefit.

The second major topic was post-quantum DNSSEC. Quantum computers that can break today's encryption are still speculative; the current landmark achievement is factoring the number 35. Yet history shows rapid innovation, as with the germanium transistor of 1947 leading to today's trillion-gate chips. Huston argued that the most effective mitigation today is not to deploy post-quantum cryptography (PQC) but to reduce the lifetime of DNSSEC keys, because once a key is rolled, breaking an old key is useless. DNSSEC's interlocking key structure means a key is only useful until it is replaced. The real concern is whether a future quantum computer could break a key within its usable lifetime.

If post-quantum algorithms are eventually needed, they bring practical challenges. PQC signatures are much larger, potentially forcing DNS from the lightweight User Datagram Protocol (UDP) to the heavier Transport Control Protocol (TCP), or requiring application-layer fragmentation. Huston pointed out that while technically feasible, making all DNS traffic carry huge payloads would be economically unaffordable because DNS is currently incredibly cheap due to small message sizes.

Johan Stenstam presented three experiments to explore post-quantum DNSSEC without breaking the system. His first experiment leveraged the fact that Shor's algorithm, which would break RSA encryption on a quantum computer, takes hours to days for a 2,048-bit key. He used DSYNC to roll a DNSSEC Key-Signing Key (KSK) every ten minutes for three months, pre-publishing only the quantum-opaque DS hash of the key. By the time an attacker could break the KSK, it had already been rolled and was useless. The second experiment used a split profile: a large post-quantum KSK to sign the zone's apex DNSKEY record, while a smaller Zone-Signing Key (ZSK) signed the actual responses. Ordinary queries would use the small ZSK signatures and stay within UDP limits, while only the DNSKEY record would be large. The third experiment, called the "Gargantuan" Combined Signing Key (CSK), resulted in a DNSKEY response of 23,843 bytes. Two such keys still fit in a DNS TCP response because it is under the 64K limit, but the DNS implementation needs a patch to use large buffers. Stenstam noted it then "works like a charm."

These experiments suggest that the mono-algorithm approach used in DNSSEC to date may be inappropriate for post-quantum deployment. The KSK, which is used infrequently but must remain stable for a long time, has different requirements from the ZSK, which signs every response and must be small. Innovations like split profiles