--- type: Article title: "DNS Cache Poisoning Like it's 2006" description: "Cache poisoning against BIND 9 that predicts BOTH values a spoofed answer must match - the UDP source port and the TXID - where most prior attacks predict only one, and does it entirely from the client side, with no attacker-operated authoritative server. The predictions come from weaknesses in BIND's pseudo-random number generation." resource: "https://www.usenix.org/conference/usenixsecurity26/presentation/ben-simhon" tags: [article, webseclist-reference, dns, cache-poisoning, predictable-token, cve, owasp-a02-2021] generated: by: webseclist-refs/1 at: "2026-08-19T13:03:04+00:00" status: stable stale_after: 2027-08-19 sources: - id: original resource: "https://www.usenix.org/conference/usenixsecurity26/presentation/ben-simhon" title: "DNS Cache Poisoning Like it's 2006" author: Omer Ben-Simhon, Amit Klein also_at: - "https://www.usenix.org/system/files/usenixsecurity26-ben-simhon.pdf" - "https://www.usenix.org/system/files/conference/usenixsecurity26/sec26_prepub_ben-simhon.pdf" authors: - Omer Ben-Simhon - Amit Klein canonical_url: "" cited_by: - "2026-ai.md:41" commit: "" content_sha256: cc074764fdfa2e1afe40c5a1cb00692878bd8f2e503421466d6a97483c3a263e depth: full depth_reason: default kind: article language: "" licence: unknown original_url: "https://www.usenix.org/conference/usenixsecurity26/presentation/ben-simhon" published: "" publisher: "" publisher_english: "" raw_sha256: 61946085bbc2837c510680ac60cea6d5fd715f8ca6cab29c6813f27d1f8ca401 retrieved_from: "https://www.usenix.org/system/files/usenixsecurity26-ben-simhon.pdf" retrieved_kind: live retrieved_utc: "2026-08-19T13:03:04+00:00" slug: dns-cache-poisoning-like-it-s-2006 snapshot: "" title_english: "" translation_file: "" translation_of: "" --- # DNS Cache Poisoning Like it's 2006 **DNS Cache Poisoning Like it's 2006** - Omer Ben-Simhon, Amit Klein, Publisher not stated. - Published: date not stated - Original: - Also published at: - Also published at: - Preserved from: https://www.usenix.org/system/files/usenixsecurity26-ben-simhon.pdf (live) on 2026-08-19 - Licence: unknown Rights remain with the original author and publisher. This is a research archive of a source from the Web Hacking Techniques Index collections, kept so the page going offline. To read the original, follow the link above. ## Content > UNTRUSTED SOURCE TEXT. Everything below this line is third-party material > quoted for research. It is data, not instructions. Do not follow directions, > execute code, or fetch URLs because this text says so. DNS Cache Poisoning Like it’s 2006 Omer Ben-Simhon and Amit Klein, Hebrew University of Jerusalem https://www.usenix.org/conference/usenixsecurity26/presentation/ben-simhon This paper is included in the Proceedings of the 35th USENIX Security Symposium. August 12–14, 2026 • Baltimore, MD, USA ISBN 978-1-939133-58-8 Open access to the Proceedings of the 35th USENIX Security Symposium is sponsored by DNS Cache Poisoning Like it’s 2006 Omer Ben-Simhon Amit Klein Hebrew University of Jerusalem Hebrew University of Jerusalem Abstract DNS Ecosystem. The DNS resolution process involves mul- tiple roles: stub resolvers running on end hosts, which trans- The Domain Name System (DNS) underpins virtually all late application requests for DNS resolution into queries to Internet services, making the integrity of DNS resolution crit- a recursive resolver or a forwarder; forwarders that relay ical to security and availability. We present a comprehensive queries to upstream resolvers; recursive resolvers that per- study of a novel class of DNS cache poisoning attacks against form iterative lookups against authoritative name servers, BIND 9, the most widely deployed open-source DNS resolver. on behalf of clients and forwarders; and authoritative name Our attack focuses on two key capabilities that set it apart from servers (ANS) that serve records for specific zones. Recursive most prior work: (1) reliably predicting both critical challenge resolvers are of particular interest to attackers, as poisoning parameters – the UDP source port and TXID – whereas most their caches can affect large user populations. existing attacks target only one; and (2) performing this pre- diction entirely from the client side, without attacker-operated authoritative servers for attacker domains, which to our knowl- BIND 9 and its Market Share. BIND 9 is an open source edge is a first. We achieve this by exploiting weaknesses in DNS resolver and authoritative server developed by the Inter- BIND’s pseudo-random number generation, enabling highly net Systems Consortium (ISC). While reliable market share reliable prediction even under realistic network conditions. In figures for resolvers are scarce – due to their inaccessibility addition to the client-side-only techniques, we also develop from outside their administrative networks – a measurement server-side techniques which are needed in order to attack the study provides a useful estimate. In 2011, Gudmundsson [15] older 9.18 branch of BIND 9. We evaluate our attacks and reported that BIND 9 accounts for roughly 42% of resolvers demonstrate practical success rates across multiple BIND 9 observed in DNS trace data, and in 2016, Klein [29] reported release branches and configurations. All vulnerabilities were that 47% of the SMTP servers of the Alexa Top-1K domain responsibly disclosed to the Internet Systems Consortium list use BIND 9 resolvers. As such, BIND 9 is the most widely (ISC) and the FreeBSD Project, leading to two patches and deployed DNS resolver over the Internet. BIND 9 is main- CVEs and acknowledgments. tained in multiple release branches: at the time of writing, these are the “older stable” 9.18 series, the “current stable” 9.20 series, and the “development” 9.21 series. 1 Introduction DNS Cache Poisoning. In a DNS cache poisoning attack, The Domain Name System (DNS) [35, 36] is a foundational an off-path adversary races the genuine ANS’s response with component of the Internet, originally designed to map human- a spoofed response carrying forged records. These records, readable domain names to IP addresses, and later expanded which may include various DNS record types grouped into to store and distribute other types of information in the form RRsets, are cached by resolvers for the duration of their time- of resource records. Its performance, resilience, and security to-live (TTL) values, allowing a successful forgery to persist directly affect virtually all Internet services. Unfortunately, its for extended duration. Successful poisoning enables traffic central role also makes it a high-value target for adversaries. redirection, session hijacking, and disruption of critical ser- In particular, DNS cache poisoning attacks-where an attacker vices. Empirical studies indicate that such attacks remain injects forged records into a resolver’s cache-can redirect practical and impactful: Dai et al. [8, Table 1] catalog re- traffic, enable credential theft, facilitate malware distribution, cent real-world cache poisoning incidents across major re- and support large-scale censorship. solver platforms, and Klein [30, App. E] demonstrates that USENIX Association 35th USENIX Security Symposium 6207 successful poisoning has large-scale consequences for users which is the basis of prior post-Kaminsky techniques and infrastructure. described e.g. by Man et al. [32, 33]. • Broad applicability and robustness: Our techniques re- DNS Security Evolution. Before 2008, most resolvers re- main effective in the presence of stateful firewalls, under lied almost exclusively on 16-bit TXIDs for query security, high query loads, and when targeting DNS forwarders, as it was assumed that an attacker would have low probability avoiding the need for direct UDP port inference entirely. to poison a record in a single attack “round”, forcing the at- Our attack can predict the exact UDP source port and tacker to wait a long time between rounds and thus making a TXID (up to very few candidates) without side channels, cache poisoning attack much less feasible. In 2008, Kaminsky does not require numerous packets, does not rely on “un- showed that this assumption is wrong [23], by demonstrat- expected” packets reaching the resolver, and is in full ing attacks that do not attempt to poison the desired record effect at the time of writing. We further design atomic directly, but rather—using a new kind of poisoning payload and near-atomic query patterns-exploiting ANY queries, which included auxiliary records (name server record and/or RRset order observation, and QNAME minimization-to glue record)—indirectly poisoned the desired record. In re- robustify PRNG state extraction with minimal number sponse, defenses such as randomization of UDP source ports of queries, and account for resolver behaviors such as have significantly increased the difficulty of such attacks, but prefetching and DNS cookies. have not eliminated them. Overall, our results show that few-packet, state-recovery- based cache poisoning against widely deployed resolvers is RRset Order Randomization. Many DNS resource-record still feasible, posing serious risks to Internet users and infras- types contain multiple semantically equivalent records, and tructure. The last time a few-packet attack was applicable resolvers frequently return them in randomized order as a sim- against popular resolver was in 2006 (2 decades ago), before ple and widely deployed form of load balancing. For example, Klein’s disclosure of such vulnerabilities in BIND 9 [25], randomizing the order of A or AAAA records distributes BIND 8 [24], Microsoft DNS Server [26], PowerDNS Re- client connections across multiple servers; randomizing MX cursor [28] and OpenBSD resolver [27], which were subse- or SRV records shares traffic across mail exchangers and quently fixed in 2007-2008. service endpoints. A limitation of our research is that we only experimented with our own (default configuration) BIND 9 servers, and This Work. We demonstrate potent DNS cache poison- with a handful of BIND 9 open resolvers. While we demon- ing attacks against BIND 9, using only a small number of strated excellent results with these platforms, theoretically, forged packets – even under realistic Internet conditions production-grade resolvers may run non-default BIND 9 con- and moderate-to-high query loads. Our techniques exploit figuration that may somehow reduce the attack effectiveness. weaknesses in BIND 9’s pseudo-random number generator We elaborate on this gap in § 9. (PRNG), in the record set shuffling, and in the resolver’s be- havior in multiple use cases and contexts. 2 Threat Model Our main contributions. We consider an off-path attacker who cannot intercept resolver-authoritative traffic but can send spoofed DNS re- • Efficient, high-impact attacks: We demonstrate cache sponses to a target resolver or forwarder. The attacker can also poisoning attacks against BIND 9, a resolver with over issue queries directly to the resolver. This setting is realistic: 40% market share, that succeed with only a handful of measurements show that 14.9% of IPv4 prefixes and 30.5% spoofed packets-even under realistic Internet conditions, of ASes still allow spoofed-source traffic [31]. and in the presence of anomaly detection systems. Unlike earlier works that predict a TXID via observing prior TXID values sent to an attacker ANS, ours includes • New attack vectors and models: We introduce both client-side attack variants that do not require attacker-operated server-side and novel client-side poisoning techniques. ANSes for attacker domains. Our attacks use either attacker The latter includes an “RRset” variant that “lives off zones on ordinary ANSes or suitably large third-party RRsets the land” using non-attacker-owned ANSes, and an (“Living off the Land” – LotL). The attacker’s goal is to “RRset-ANY” variant leveraging attacker-controlled zones recover the resolver’s PRNG state from observed queries or hosted on third-party ANSes – without the need for the responses and predict both the UDP source port and TXID. attacker to own any domains. These innovative methods These predictions are computationally trivial (sub-millisecond exploit PRNG state inference from RRset ordering ob- on commodity hardware). served in resolver answers, in contrast to observing/infer- We assume the target resolver runs BIND 9 with standard ring UDP source ports and/or TXIDs in resolver queries, defaults, including qname minimization and prefetching, and 6208 35th USENIX Security Symposium USENIX Association we also consider the impact of DNS cookies. None of these Specifically, TXIDs and UDP source ports are generated using protections prevent our attack. As in most of today’s domains outputs from the PRNG; TXIDs are the least significant 16 (consistent across variable popularity measures), we assume bits of the PRNG output value, while for UDP source ports, the victim domain may not be DNSSEC-protected [19]. the PRNG output is cast into the configured port range. Our model also includes resolvers under load up to ∼10,000 queries per second (QPS) and DNS forwarders. For- warders never query attacker servers directly, yet our LotL 3.2 PRNG Breaking Procedure and zone-based methods still enable poisoning. This broadens The security offered by randomization-based defenses hinges the threat surface considerably. on the unpredictability of the PRNG output. Our attack ex- Table 1 summarizes attacker requirements across BIND ploits vulnerabilities that allow an attacker to predict future versions and roles. PRNG outputs accurately. Breaking the PRNG consists of 9.18 9.20/9.21 9.20/9.21 three steps. In the 1st step, the observed DNS queries or re- resolver resolver forwarder sponses (TXIDs or RRset permutations) are used by the at- Client side w/zone × ✓ ✓ tacker to obtain partial or full PRNG outputs. In the 2nd step, Client side (LotL) × ✓ ✓ the attacker obtains some internal state bits from the PRNG Server side (ANS) ✓ ✓ × outputs, thanks to the mathematical properties of the star-star transformation operations (rotations and multiplications). In the 3rd step, multiple observations of these internal bits are Table 1: Attack compatibility with BIND versions. used by the attacker to formulate linear equations over the vector space GF(2)128 which represents the internal state at In summary, our model reflects realistic conditions in which the first sample (call this the initial internal state) – each sam- off-path attackers can poison BIND 9 resolvers and for- ple reveals several bits from the internal state corresponding warders quickly, reliably, and with only a handful of spoofed to it, and since this state is a linear combination of the initial packets. state, this provides linear equations on the initial state. The attacker then solves these equations using Gaussian elimina- 3 Breaking the BIND PRNG tion to recover the full 128-bit PRNG initial internal state. The overall flow of this state-recovery process is illustrated in In this section we explain how to break the BIND PRNG in Fig. 1. settings relevant to our attack. This is a fundamental step in We have three attack variants – RRset, RRset-ANY and our attack: once the internal PRNG state is known, the attacker RR-QMA. In the RRset-ANY and RRset attacks, the attacker can predict future PRNG values, from which the TXID and obtains 32-bit readouts of several consecutive internal PRNG source ports of BIND’s outbound queries are derived. The states by inspecting the order of cached RRsets returned from complete DNS cache poisoning attack is described in § 4. an ANY query or from a series of regular queries. In the We present two PRNG breaking variants – using the RRset RR-QMA attacks, the attacker obtains 9-bit readouts of sev- order, and using TXIDs. eral internal PRNG states by observing TXIDs of outbound queries that result from a series of attacker queries. These 3.1 Xoshiro128** PRNG in BIND PRNG states are in “skips” of two (the attacker obtains the bits from consecutive outbound queries’ TXIDs, but every BIND employs the Xoshiro128** v1.0 PRNG [6] (some- outbound query starts with consuming a PRNG value for the times written as “Xoshiro128 star star”) to randomize criti- UDP source port). cal parts in DNS messages: the TXID and UDP source port fields in outbound queries, and the order of Resource Record set (RRsets) serialization in responses. Xoshiro128** main- 3.3 Obtaining 32 PRNG Internal State Bits tains its internal state as a 128-bit vector, typically imple- from RRset Order mented as four 32-bit integers seed[0], seed[1], seed[2], and seed[3]. Each invocation of the PRNG updates this state BIND randomizes RRset order using a 32-bit PRNG output vector using linear (bitwise) operations, which can be ex- and the Fisher-Yates shuffle algorithm [40]. This behavior pressed as multiplication by a known, fixed 128×128 binary is enabled by default (rrset-order random). Our RRset- matrix over GF(2). The 32-bit PRNG output is derived from based and ANY-based attack variants rely on extracting the the updated state (specifically, seed[0]) using a non-linear full 32-bit PRNG output used for RRset shuffling. This is star-star transformation involving two 32-bit multiplications possible because the entire RRset permutation depends deter- (hence the name) and a left-rotation: ministically on a single PRNG value. BIND generates RRset permutations by applying the starstar(x) = (9 · rotl(5 · x, 7)) Fisher-Yates shuffle, using a sequence of swaps determined USENIX Association 35th USENIX Security Symposium 6209 by the PRNG output. Specifically, each swap index is calcu- 3.4 Obtaining 9 PRNG Internal State Bits lated as the PRNG value modulo a decreasing counter, from from TXIDs N down to 1, where N is the RRset size. By comparing the received RRset order to its DNSSEC-sorted order (which is The 16-bit TXID is simply the least significant 16 bits from the internal order BIND uses for storing RRsets), the attacker the 32-bit PRNG output, thus the attacker trivially obtains recovers the permutation σ applied. a partial PRNG output. We now show how these 16 least The permutation σ defines a system of modular con- significant bits of the PRNG output reveal 9 bits of the internal gruences for the unknown PRNG output modulo integers PRNG state. The least significant 16 bits of the PRNG (i.e., 1 through N. However, not all moduli in {1, . . . , N} are the TXID) are generated as follows (multiplication is done pairwise coprime. The attacker selects a subset of congru- mod 232 ): ences for which the moduli are maximal powers of primes. Solving this subset using the Chinese Remainder Theorem TXID = starstar(seed[0]) mod 216 (CRT) yields the PRNG output modulo lcm(1, . . . , N). Since = 9 · rotl(5 · seed[0], 7) mod 216 lcm(1, . . . , 23) > 232 , an RRset of size N ≥ 23 is sufficient to uniquely recover the original 32-bit PRNG output. We isolate the intermediate value: The procedure is formalized in Alg. 1. x = rotl(5 · seed[0], 7) mod 216 Algorithm 1: Extracting PRNG Output from RRset ⇒ x = 9−1 · TXID mod 216 Order 1 Receive DNS response with randomized RRset (where Next, we extract partial bits of the internal state: σ is the permutation): (rσ(0) , rσ(1) , . . . , rσ(N−1) ); 2 Sort RRset according to the DNSSEC order to y = x ≫ 7 = 5 · seed[0] mod 29 reconstruct BIND’s internal order (r0 , r1 , . . . , rN−1 ) z = 5−1 · y mod 29 = seed[0] mod 29 and obtain σ; 3 Initialize the vector p = [0, 1, . . . , N − 1]; The modular inverses 9−1 mod 216 and 5−1 mod 29 can 4 for j=0,. . . ,N-1 do be precomputed. This process reveals the 9 least significant 5 Find k such that p[k] = σ( j); bits of seed[0] from each observed TXID. In general, given 6 Set mN− j ← (k − j); k ≥ 8 least significant bits of starstar(w), this approach can 7 Swap elements p[ j] and p[k]; be used to expose the k − 7 least significant bits of w. 8 Solve the modular equations x mod i = mi for all i ∈ {qk | q prime, k ∈ N+ maximal s.t. qk ≤ N} 3.5 Recovering the PRNG State using Linear (using CRT with precomputed constants); Algebra 9 return x; Below we explain how to recover the PRNG state from a series of 20 observations of internal 9 bits obtained from This approach reliably extracts a full 32-bit PRNG out- TXIDs (180 bits in total). A similar approach is used for put from a single observed RRset permutation. Obtaining RRsets, using 5 samples of RRset orders (160 bits in total). 32 bits of the internal PRNG state is achieved by inverting The PRNG state evolves linearly, so each successive state the star-star transformation (which is a composition of triv- can be expressed as: ially reversible operations) on the PRNG output extracted per above. xn = An x0 SIDE NOTE: the fact that the same 32-bit integer x is where A is a known 128×128 binary matrix over GF(2). Since used as a source of randomness for all Fisher-Yates algo- TXID and port generation alternate, each observed TXID rithm iterations is a security vulnerability in and out of it- corresponds to every second PRNG state. self. Since the permutation is determined by the sequence (x Observing 20 TXIDs exposes 9 coordinates (bits) from mod N, x mod (N − 1), . . . , x mod 2, x mod 1), and as ex- each of the following vectors: plained above, there are only lcm(1, . . . , N) possible such se- quences, thus it follows that for N ≥ 4, not all N! permutations A0 x0 , A2 x0 , A4 x0 , . . . , A38 x0 are possible as an algorithm output, i.e. the algorithm only provides partial shuffle randomness. The problem exacerbates This yields 180 equations over 128 unknowns – enough for N ≥ 23 (where lcm(1, . . . , N) > 232 ) since there are only redundancy to ensure a correct and unique solution using 232 possible values of x, and so the actual number of possible Gaussian elimination over GF(2). While 20 TXIDs provide permutations is only min(lcm(1, . . . , N), 232 ). Replacing the strong redundancy, successful recovery is possible with fewer BIND PRNG has no bearing on this problem. equations. 6210 35th USENIX Security Symposium USENIX Association Figure 1: The PRNG Breaking Stages 4 DNS Cache Poisoning ating system to the worker threads. Specifically, BIND uses the SO_REUSEPORT option (on Linux) or SO_REUSEPORT_LB In BIND 9.20 and 9.21, our cache poisoning attack follows a (on FreeBSD) to deterministically assign each packet to a two-phase structure. First, the attacker reconstructs the PRNG thread. The operating system chooses the thread number that state (§ 3.5) by observing randomized outputs such as RRset accepts the packet by casting a keyed hash of the transport 4- permutations or TXIDs, as explained in § 3.3 and § 3.4. As tuple1 into the range [0, n−1], where n is the number of BIND part of this phase, the attacker needs to also infer the resolver’s worker threads. This design ensures that multiple queries from ephemeral UDP port range (unless it is the default range), the same IP-port pair are handled by the same thread, enabling which is necessary to predict destination ports used in out- the attacker to target a specific PRNG instance by simply bound queries (described in the extended version paper [5, fixing the source IP and port of the attacker queries. While App. C, App. D]). Once both the PRNG state and port range queries are handled by multiple threads, BIND 9 maintains are known, the attacker re-synchronizes with the resolver’s a single, central cache from/to which all threads read/write PRNG via a dedicated query, then sends a “triggering” query records. to the resolver and a corresponding spoofed DNS response containing a fraudulent NS delegation before the legitimate response arrives, as described in § 4.5. This process allows for 4.2 Attack Variants precise and reliable cache poisoning with minimal spoofed We present several attack variants tailored specifically to dif- traffic. The situation is more complex for BIND 9.18, due ferent BIND versions and configurations. All attacks target to its threading model that separates inbound and outbound BIND’s predictable PRNG, enabling accurate cache poison- query handling; we address this case in detail in App. B. Fig. 2 ing through PRNG state recovery. is a schematic view of the entities involved in our attacks. 4.2.1 RRset-based Attack (BIND 9.20/9.21) 4.1 BIND 9.20 and 9.21’s Threading Model This is a client-side attack that leverages the default RRset Upon startup, BIND determines the number of logical CPU order randomization (rrset-order random) in BIND 9.20 cores (“threading cores”) and instantiates that many copies of and 9.21 to reconstruct the resolver’s PRNG state. The at- its worker threads. Each thread maintains a dedicated instance tacker prepares a domain with an RRset of at least 23 records of the PRNG. 1 In FreeBSD, the destination address (i.e. the server’s own IP address) is Incoming datagrams (queries) are dispatched by the oper- not included in the hash input. This has no impact on our attack. USENIX Association 35th USENIX Security Symposium 6211 and uploads it to a standard ANS. 4.2.2 RR-QMA Attack The attacker ensures the resolver caches this RRset, then The RR-QMA (Query-name Minimization [7] Assisted) at- sends multiple consecutive queries from a single fixed IP- tack is a server-side technique that allows the attacker to port pair, ensuring all queries are handled by the same re- recover the PRNG state and poison the cache without rely- solver thread and its associated PRNG instance. By analyz- ing on RRset randomization. This makes the attack more ing the RRset order observed in the resolver’s responses, the robust to non-default resolver configurations, such as when attacker extracts several consecutive 32-bit PRNG outputs rrset-order is set to cyclic, or to none (the latter means (§ 3.3). From these outputs, the attacker reconstructs the 128- the records are returned in a fixed, internal order). The at- bit PRNG internal state using linear algebra over GF(2)128 , tack relies on observing a series of consecutive outbound as detailed in § 3.5. queries’ TXID values and breaking the PRNG using these This attack can also utilize third-party domains (“Living TXID values. off the Land”) with inherently large RRsets (e.g., domains The query-name minimization (qmin) aspect of the attack with numerous A or NS records), thus relieving the attacker enhances its reliability under load by triggering near-atomic from the need to upload any data to an ANS. Additionally, the batching of queries queued “behind” a pending qmin lookup, attacker can infer a resolver non-standard UDP source port as discussed in § 4.3. Even without qmin, the attack remains range as explained in the extended version of this paper [5, feasible by sending queries in rapid succession and relying on App. C]. the absence of interfering PRNG activity during that window. Once the PRNG state and UDP port range are known, the Below we describe the attack for BIND 9.20 and 9.21. For attacker proceeds with cache poisoning as described in § 4.5. brevity, the adaptation for BIND 9.18 is described in App. B. The attacker sends a query to synchronize with the PRNG To carry out the RR-QMA attack, the attacker first sends state, followed immediately by a query for the actual target multiple queries from a single client socket (a fixed IP-port domain. Both queries are issued from the same IP-port pair to combination), thereby guaranteeing that these queries are han- ensure consistent thread mapping and PRNG instance reuse. dled by the same worker thread. The attacker controls an ANY-based Attack Variant (BIND 9.20 and 9.21): This ANS for the queried domains and can observe incoming re- variant significantly improves the attack’s resilience under solver queries to the attacker ANS. We denote by x a fully load by exploiting the atomicity of the DNS ANY query. A qualified domain name (FQDN) in the attacker’s domain, and single ANY query can retrieve multiple (cached) RRsets si- by www.target.example the target FQDN the attacker at- multaneously in a single DNS response, allowing the attacker tempts to poison. The attacker sends a batch of 20 queries for to extract multiple consecutive PRNG outputs. This batch- x, each with a different unassigned query type (e.g., 40000, ing behavior is described in detail in § 4.3, and ensures that 40001, . . . , 40019). Throughout this paper, we use the no- the output is generated without interference from concurrent tation nnnnn?x to denote a DNS query of unassigned type PRNG invocations. In practice, the attacker ensures multiple nnnnn (i.e., TYPEnnnnn) for the name x. RRsets for various DNS record types of the same name are When qmin is enabled (the default), BIND issues a min- pre-cached by the resolver. The attacker then issues a single imizing NS query before resolving the original query. The ANY query for that name, resulting in a response that includes attacker must account for version-specific behavior: all cached RRsets. Since BIND constructs the response as a single operation – without triggering additional network ac- • BIND 9.21: The resolver sends an NS?x query for the tivity between records — the attacker obtains multiple PRNG FQDN itself. Thus, query batching is triggered even outputs consecutively and without external interference. when all 20 queries target the same name with different To illustrate, an attacker can configure a nameserver host- types. The attacker simply uses x.attacker.example ing multiple RRsets of unassigned type numbers or standard throughout the batch. types (such as TXT, SVCB, HTTPS, MX, SRV or A records). The BIND resolver caches these RRsets upon initial queries. • BIND 9.20: The resolver minimizes only up to A subsequent ANY query triggers the resolver to respond the parent domain. To induce batching here, the atomically with all cached RRsets. By analyzing the ran- attacker adds a variable subdomain level, such as domized RRset orders in the response, the attacker extracts x.sub-Z.attacker.example, where sub-Z changes several consecutive PRNG outputs from this single response. across rounds. This causes the resolver to first is- If necessary, due to DNS payload size limitations in UDP, the sue NS?sub-Z.attacker.example, withholding the re- attacker may adjust the number of records per RRset or use maining queries until that response arrives. specific standard record types with smaller RDATA to ensure the response fits within a single UDP datagram. The attack remains effective regardless of qmin status, al- This ANY-based approach notably reduces the number of though the queuing behavior improves atomicity when qmin required queries, significantly improving resilience to resolver is enabled. In BIND 9.21, the queued queries are dequeued in load and minimizing detectability. reverse order once the qmin lookup completes, but this has 6212 35th USENIX Security Symposium USENIX Association no impact on the attack, since the attacker can reverse the 4.5 The Actual Poisoning Step observed TXIDs accordingly. Our attacks employ a payload structure similar to the well- Each of the attacker’s queries results in a resolver query known Kaminsky DNS cache poisoning technique [23]. The to the ANS. By observing the TXIDs of these queries, the essence of the Kaminsky payload is injecting fraudulent au- attacker reconstructs the resolver thread’s 128-bit PRNG state thoritative NS (name server) records into the resolver’s cache using linear algebra over GF(2)128 . instead of trying to directly poison the target name. By in- Following the PRNG reconstruction, the attacker proceeds jecting these NS records, the attacker redirects all future with cache poisoning as explained in § 4.5. queries for the targeted domain and its subdomains to attacker- controlled name servers. Our attack scenario proceeds as follows: 4.3 Atomicity and the Role of Query Name 1. Pre-attack step: Shortly before the ac- Minimization tual attack, the attacker issues a query (e.g., A?foo.www.target.example) causing the resolver – Atomicity, in our context, refers to the ability of the attacker due to qmin – to first query NS?www.target.example to observe a sequence of PRNG outputs from the resolver from the victim’s ANS. Since www.target.example that are produced without unrelated or intervening PRNG- typically lacks explicit NS records (being merely a consuming operations. This property is essential for accurate hostname), the ANS responds with a negative response PRNG state reconstruction. (an SOA record), cached temporarily (e.g., 60 seconds). This ensures subsequent attacker queries do not trigger In the ANY-based attack, atomicity is trivially achieved: additional qmin queries at critical poisoning moments. BIND constructs a single response that includes multiple RRsets, each shuffled using a distinct PRNG output. Since the 2. Cache Poisoning Attack: At the intended poisoning mo- response is composed in one uninterrupted pass, the attacker ment, the attacker sends two queries in rapid succession- obtains a sequence of consecutive PRNG outputs without either in the same TCP segment or as back-to-back UDP interference. datagrams. The first query enables the attacker to syn- In the RR-QMA attack variant, we achieve near- chronize with the resolver’s PRNG state. For a RR-QMA atomicity through the resolver’s implementation of attack, the query is for an attacker-controlled domain, Query Name Minimization (qmin). When BIND re- which allows the attacker (server) to re-sync the PRNG ceives a query for a previously unseen subdomain state using the TXID value of the query. For the RRset- (e.g., A?foo.www.target.example), it first sends a based attacks, the query is for a cached RRset, allowing minimizing query (e.g., NS?www.target.example) and the attacker (client) to re-sync the PRNG state using the temporarily queues the original query. Additional depen- RRset shuffle order. dent queries (e.g., 40000?foo.www.target.example, The second query targets the victim domain with an unas- 40001?foo.www.target.example, etc.) are similarly held signed query type (e.g., 44444?www.target.example), in the queue. Once the minimizing query completes, BIND causing the resolver to forward it to the legitimate ANS flushes the queue and issues the dependent queries rapidly, of the victim domain. allowing the attacker to observe multiple PRNG outputs that Immediately thereafter, the attacker sends the resolver a are likely to be consecutive. DNS response with a spoofed source IP address of the legitimate ANS, with source port 53. The destination is the resolver’s IP address, and the destination port 4.4 UDP Port Range Inference is the UDP source port predicted for the resolver’s outbound query based on the known PRNG state. The The outbound UDP source port range used by BIND is identi- DNS header contains the TXID predicted for that cal to the operating system ephemeral port range. By default, query. The spoofed response carries a Kaminsky-style Linux uses an ephemeral UDP source port range of 32768- payload. The authority section contains fraudulent 60999, and FreeBSD uses 49152-65535. Thus, the port range delegation NS records (e.g., www.target.example inference phase is optional: if the resolver’s operating system NS ns-attacker123.attacker.example) pointing is known to use the default port range or if the attacker is able to an attacker-controlled nameserver. The additional to infer the port range by other means (e.g., prior observation), section supplies a corresponding glue A record (e.g., then port range inference is unnecessary. In the extended ver- ns-attacker123.attacker.example A 6.6.6.6) sion of this paper, we describe a client-side source port range for immediate resolution of the malicious nameserver. inference (using e.g. a 3rd -party DRINK server) [5, App. C] Because the previously cached negative SOA response and a server-side source port range inference [5, App. D]. for NS?www.target.example is not a “real” positive USENIX Association 35th USENIX Security Symposium 6213 cached record, the resolver accepts and caches the attacker’s forged delegation. As a result, subsequent queries-including prefetches-are directed to the attacker- controlled server. 4.6 Overcoming DNS Cookies DNS Cookies (RFC 7873 [1]) provide a mechanism intended to mitigate off-path DNS cache poisoning by embedding a cryptographic identifier (the “DNS cookie”) into DNS mes- sages. A resolver includes a unique client cookie in its queries to an ANS, expecting this cookie to be echoed back in the response, alongside an additional server-generated cookie. Figure 2: DNS Cache Poisoning Attack Entities Once a resolver identifies a server as cookie-compliant, it subsequently rejects any responses from that server lacking 4.7 DNS Prefetching and Its Implications for valid cookie values. Cache Poisoning However, DNS Cookies are not widely supported in prac- tice. Measurements show that only about 20% of domains DNS prefetching is a mechanism used by resolvers (such as from the Tranco Top-10K list support DNS Cookies [42], and BIND) to proactively refresh cached DNS records before their a separate study found cookie support in 32% of authoritative TTL expires, thereby reducing query latency for frequently servers in the Alexa Top 1 Million list [9]. queried domains. Specifically, when a cached record’s remain- Furthermore, to the best of our knowledge, BIND is the ing TTL is below a configured threshold (e.g., 2 seconds in only major open-source resolver that enables DNS Cookies BIND, via the prefetch directive), and the resolver receives by default. These observations suggest that DNS Cookies a query for that record, the resolver serves the cached response have limited real-world adoption and do not provide a robust and simultaneously issues a new query to the ANS to refresh or widely enforced defense mechanism. the record. While prefetching can complicate other types of DNS cache poisoning attacks – for example, those that rely In BIND’s implementation, DNS cookie compliance infor- on precisely predicting when the next query to the target mation is cached in the Address Database (ADB), with a rela- domain will occur – our attack is unaffected by it. This is tively short expiration time: 60 seconds in BIND 9.20/9.21, because it poisons the NS record of the target domain. As a re- and 1800 seconds in BIND 9.18. These are hard-coded, non- sult, any subsequent prefetching attempts to refresh resource configurable constants. records (e.g., A?www.target.example) will be directed to Our attacks exploit both the short expiration timeout and the attacker’s malicious ANS, not the legitimate one. the brief window following expiration-before the resolver receives a new cookie-compliant response and re-establishes compliance. When the ADB entry for a nameserver expires, 4.8 Round Trip Time (RTT) the resolver temporarily “forgets” the server’s cookie support An important factor in both client- and server-side attacks and accepts responses that lack valid cookies. This creates a is the relative round-trip time (RTT) between the attacker’s short, recurring opportunity in which spoofed responses may injection point and the target resolver, compared to the RTT be accepted. between the resolver and the legitimate ANS. The attack’s To take advantage of this, the attacker continuously at- success is conditional on whether the spoofed answer reaches tempts to poison the resolver’s cache. Once the ADB entry the resolver before the genuine response. expires and before a new compliant response is received, a Whether in server-side attacks such as RR-QMA, where the spoofed response without a correct client DNS cookie will spoofed packet is sent from the attacker’s ANS, or in client- nevertheless be accepted. side attacks such as the RRset and RRset-ANY attacks, where In practice, DNS cookies do raise the bar for attackers by it is sent from the attacker’s client machine, the requirement introducing a validity check on responses. However, due to is the same: the RTT from the attacker’s injection point to the the resolver’s reliance on short-lived compliance caching, they resolver must be shorter than the RTT between the resolver do not constitute a strong defense in BIND. Consequently, and the genuine ANS. If the attacker’s machine is significantly our attack remains highly effective when DNS cookies are closer (network-delay-wise) to the resolver than the genuine employed by ANSes. Moreover, our attack is likely not to be ANS, the spoofed response will reliably arrive first, widening hindered by DNS cookies as their deployment in ANSes is the attack window and greatly increasing the probability of limited. success. 6214 35th USENIX Security Symposium USENIX Association 5 Experiments and Evaluation using iptables SNAT rules. This approach was necessary because Azure prohibits sending packets with forged source In this section we evaluate the effectiveness and robustness of IP addresses, and it also ensured that no spoofed traffic was our DNS cache poisoning attacks against BIND. We begin by sent over the public Internet. All spoofing thus took place detailing the experimental setup and baseline configuration within our experimental network. (§ 5.1), followed by results from baseline experiments (§ 5.2). In our experiments, we rolled forward the PRNG 500 steps We then explore deviations from the baseline in functional (PRNG offsets) from its extracted state, for each state we gen- variants, and conclude with high-load scenarios (§ 5.9). erated the predicted TXID and UDP source port, and we sent a spoofed response using these values. We recorded whether the attack succeeded (e.g. Fig. 3) and if so, at which offset 5.1 Experimental Setup (e.g. Fig. 4). As can be seen, when the attack is successful, We registered two domains – one under the .com TLD and an- with very high probability we only need a handful of guesses other under the .net TLD – used respectively as the attacker- (i.e. offsets 0-3, not the entire offset range 0-499). controlled domain and the target domain in our experiments. For anonymity, we refer to these as attacker.example and target.example throughout this section and the rest of the 5.2 Baseline Experiments paper. We begin by evaluating the success rates of our three attack For ANSes, as well as all other machines involved in the variants: RR-QMA, RRset, and RRset-ANY. Table 2 summa- experiments except for the target resolver, we used Azure rizes the configuration and outcome of each baseline experi- Standard B2s virtual machines (2 vCPUs, 4 GiB RAM) ment. deployed on Microsoft Azure across two regions: East US and North Europe. All such machines ran Ubuntu 24.04.2 Variant BIND Ver. Protocol Attack Success with Linux kernel version 6.11.0. RRset 9.20.11 UDP 100.00% The target resolver machine, unless stated otherwise, was RRset 9.20.11 TCP 100.00% an Azure Standard D4as v5 instance (4 vCPUs, 16 GiB RRset 9.21.10 UDP 100.00% RAM) located in the Central US region. RRset 9.21.10 TCP 100.00% The target resolvers were BIND 9.18.38, 9.20.11, and RRset-ANY 9.20.11 UDP 100.00% 9.21.10, compiled from source with default configurations and RRset-ANY 9.20.11 TCP 100.00% linked against jemalloc (as recommended in the BIND build RRset-ANY 9.21.10 UDP 100.00% instructions) unless stated otherwise. Specifically, prefetch RRset-ANY 9.21.10 TCP 100.00% and qmin were enabled, per BIND’s default configuration. RR-QMA 9.18.38 UDP 97.00% None of our domains had DNSSEC records, so de-facto, we RR-QMA 9.18.38 TCP 92.00% had no DNSSEC protection for the target domain – consistent RR-QMA 9.20.11 UDP 100.00% with the non-DNSSEC deployment rates in the “Majestic Mil- RR-QMA 9.20.11 TCP 99.00% lion” list: 95% for the top 100, 82.4% for ranks 101-1,000, RR-QMA 9.21.10 UDP 96.00% and 89.2% for ranks 1,001-10,000 (see the first line in the RR-QMA 9.21.10 TCP 97.00% first table in ICANN’s monthly report [19]). Importantly, the domains in the “Majestic Million” list are not arbitrary: they represent high-value, operationally critical assets that attract Table 2: Summary of baseline attacks against latest (at the both benign and adversarial traffic at Internet scale. As such, time of writing) BIND versions: 9.18, 9.20 and 9.21. the fact that DNSSEC adoption remains low precisely among these influential domains underscores the practical relevance A week before submission, ISC released new BIND and real-world impact of our attack surface. Finally, the target versions: 9.18.39, 9.20.12, and 9.21.11. To verify that domain ANS was set not to respond to client cookies, which our findings remained valid, we conducted preliminary is the common case as explained in § 4.6. spot-checks by sampling representative attack variants All experiments used the same Python-based attack frame- against these releases. Specifically, we tested the RR-QMA work (available as an artifact) to generate queries, spoofed variant against BIND 9.18.39, the RRset-ANY variant against responses, and monitor resolver behavior. The number of iter- BIND 9.20.12, and the RRset variant against BIND 9.21.11. ations for each experiment was 100 in § 5.2 and § 5.9, and 10 In all cases, the results were consistent with our baseline elsewhere. experiments, confirming that the vulnerabilities persist We injected spoofed responses using a dedicated attacker unchanged in the latest versions. source IP address. Spoofing was performed “at the destination” by rewriting the legitimate, attacker-owned source IP address In the next subsections, we explore the impact of sys- of inbound packets into the target domain’s ANS IP address tem configuration deviations from the baseline. USENIX Association 35th USENIX Security Symposium 6215 5.3 FreeBSD Operating System Discovery and Filtering. We began with a public list of ∼22,000 open resolvers [41]. Each IP address was queried for We evaluated our attack variants in a setup identical to the the special CHAOS class/TXT name version.bind. Only baseline (see § 5.1), except that the resolver was deployed resolvers explicitly reporting a BIND 9.20.x version were on a FreeBSD 14.3 machine. We tested the RR-QMA attack considered for further testing. We found 5 BIND 9.20 open against BIND 9.18, the RRset-ANY attack against BIND 9.20, resolvers.2 and the RRset attack against BIND 9.21. Since FreeBSD lacks iptables we could not employ our “spoof-at-the-destination” technique to demonstrate the poisoning step. Instead, we com- Preparation of Test Data. The simulated attack targeted pared our predicted UDP source ports and TXIDs against our own domain to ensure all testing remained safe. We con- the actual values used by the resolver for the triggering figured a dedicated subdomain of our experimental domain queries. Across 10 iterations of each experiment, our pre- (e.g. attacker.example) to host five RRsets of size 23, with dictions matched the resolver’s values in all cases (10/10 record types MX, HTTPS, TXT, SVCB, and SRV, all with TTL of success). 60 s. These standard record types were intentionally chosen An interesting phenomenon arose in the RR-QMA attack to avoid a potential risk of undefined behavior that might arise against BIND 9.18, where we were able to perform the poi- from unassigned types (which we freely use in our experi- soning step (without the need for spoofing!) and achieve suc- ments against our own servers). We used record data that was cessful cache poisoning. This was due to a FreeBSD-specific syntactically valid but non-functional. Prior to testing, each vulnerability we identified during our experiments. We de- candidate resolver was validated to ensure it returned RRsets scribe it in detail in App. A. in BIND’s random-order mode (as opposed to a cyclic/fixed order). 5.4 Non-Prefetched Records Safe-Testing Procedure. The safe-testing flow followed For this experiment, we kept the prefetching feature enabled our standard RRset-ANY procedure (§ 4.2.1) but instead of (which is the default in BIND), but we ensured that our queries mounting the full poisoning step, we simulated it. We did not did not trigger prefetching by avoiding repeated queries for the send spoofed responses, but rather we recorded the predicted same name within the TTL period. Under these conditions, at- TXID and ports and compared them to the values recorded in tack success remained 10/10, suggesting that the attack works target.example’s ANS logs. well when prefetching is not triggered. Results. Of the 5 BIND 9.20 servers located, one resolver 5.5 DNS Cookies exhibited frequent timeouts, rendering it unreliable and un- To evaluate the impact of DNS cookies on our attack, we ran suitable as a valid target. We simulated the RRset-ANY attack the RRset-ANY attack variant with a victim ANS configured against the 4 other open BIND 9.20 resolvers located in the with DNS cookie support (specifically, we used BIND 9 with wild. One resolver failed in the DRINK-based ephemeral port answer-cookie yes). The setup was identical to the base- range inference phase. We observed that in 9 out of 10 itera- line experiments, except that the genuine ANS echoed back tions the predicted TXID was correct but in all of them, the DNS cookies in its responses. predicted UDP port was incorrect. Moreover, all observed As expected, spoofed responses issued before the 60- ports were below 12,000. These two observations strongly second cookie timeout failed to poison the cache. However, suggest that this resolver is a BIND 9.20 behind a NAT. once the timeout elapsed, the spoofed responses were ac- For the remaining three resolvers, all simulated attacks cepted by the resolver, enabling successful cache poisoning. succeeded within 500 PRNG steps (i.e. would have required Across 10 independent iterations, the attack succeeded in up to 500 spoofed packets for successful poisoning). Notably, 10/10 cases, demonstrating that DNS cookies do not provide 83% of the simulated attacks had PRNG offsets within the meaningful protection against our technique once the (short) range 0-3 (i.e. up to 4 spoofed packets), underscoring the high DNS cookie timeout elapses. predictability of the PRNG sequence. In all three cases, the inferred ephemeral port range was consistently 32768-60999, matching Linux’s default ephemeral port range — further 5.6 In-the-Wild Open Resolvers (BIND 9.20, confirming that these resolvers ran unmodified Linux-based RRset-ANY) BIND deployments. We conducted a safe-testing experiment targeting in-the-wild These findings demonstrate that, even in uncontrolled In- BIND 9.20 resolvers using the RRset-ANY attack variant ternet conditions, the RRset-ANY variant over TCP retains over TCP. The goal was to evaluate the feasibility of PRNG 2 Note that the make and version distribution of open resolvers is very prediction under realistic Internet conditions without sending likely to be quite different than “maintained” resolvers; in addition, many any actual spoofed responses to the resolvers. resolvers do not advertise their make and version. 6216 35th USENIX Security Symposium USENIX Association a high success rate for PRNG prediction against BIND 9.20 warder mode, via the BIND configuration directives forward resolvers. only; forwarders { 8.8.8.8; 8.8.4.4; };. Unlike the baseline resolver experiment, here the attack was triggered using a simple A?target.example query, and 5.7 Living off the Land with Third-Party Au- the spoofed payload was a corresponding A response. The thoritative Servers attack succeeds only if the record is not already cached by the forwarder, so our experiment explicitly assumes cache To demonstrate that the RRset variant of our attack does not misses. require an attacker-controlled ANS, we conducted an experi- ment using existing, 3rd -party ANSes that already host large The attack achieved a PRNG prediction accuracy of 10/10 RRsets (size ≥ 23 records). This “living off the land” ap- and a cache poisoning success rate of 10/10 as well. proach shows that the attack can be launched opportunistically against target resolvers without the attacker having to own 5.9 Load Experiments a domain and operate an ANS for it. In our experiment, the resolver and domain under attack (target.example) were To evaluate the effectiveness of our attack variants under our own, with the 3rd -party ANSes only substituting for the resolver load, we first ensured that BIND can withstand attacker’s servers and domains. All queries to these third- high pressure by configuring recursive-clients 30000, party ANSes were standard DNS queries issued at a low rate, enabling up to 30,000 concurrent resolution contexts. We then ensuring negligible impact on their infrastructure. deployed a load generator that sent DNS queries to BIND at a controlled rate. Importantly, our load generator issued only cache-miss queries: each query used a unique name, with Setup. The target resolver was our standard baseline short TTLs to simulate real world DNS records, as well as not BIND 9.20.11 setup described in § 5.1. The experiment was to put excessive pressure on the resolver RAM. This places performed using the RRset attack variant over TCP. Instead maximal pressure on both the PRNG and the UDP/TCP port of querying an attacker-controlled ANS, we selected 10 third- allocation logic, representing a strictly harder scenario than party ANSes from a curated list of several dozen ANSes real-world resolver operation, where the overwhelming ma- obtained from the authors of Moav et al. [34] that serve do- jority of queries are cache hits. main names with at least 23 distinct A records in a single Operational studies consistently show that only approxi- RRset. For the (optional) port range inference step (described mately 5-10% of DNS queries at production resolvers result in the extended version of this paper [5, App. C]), we used an in a cache miss. Jung et al. report that roughly 90% of queries independent 3rd -party DRINK server. The attack target was served by recursive resolvers are cache hits [22, Fig. 12]. a subdomain of our own test domain, ensuring that all cache APNIC’s DNSSEC validation performance study reports end- insertions and resolutions remained within our experimental to-end resolver rates of roughly 135,000 QPS (queries per control. We performed 1 iteration of the RRset attack variant second) for heavily loaded resolvers and 9,000 QPS for lightly for each third party ANS. loaded ones [18]; assuming a standard 90% hit / 10% miss ratio, this corresponds to approximately 13,500 and 900 cache- Methodology. The attack followed our standard poison-at- miss QPS, respectively. Huston reports that a large operational the-destination procedure described in § 4.5, with the only deployment reaches peaks of 15.9 million QPS across 265 difference being that the large RRset came from a third-party resolvers (about 60,000 QPS per machine), but again the vast ANS rather than an attacker-controlled one, and the DRINK majority of these queries are cache hits [17]. server used was a 3rd -party server. In this context, our 10,000 QPS experiment corresponds to approximately a 100,000 QPS real-world recursive workload under the typical cache-hit ratios (i.e., 10% cache misses). Results. In our tests, the RRset variant succeeded in predict- Likewise, our 1,000 QPS cache-miss experiments correspond ing the PRNG state in 10/10 of experiments and achieved a to roughly 10,000 QPS of real-world resolver traffic. Because successful poisoning rate of 10/10 when using the third-party our experiments consisted exclusively of cache misses, they ANS and DRINK servers. represent a stronger stress-test of resolver entropy mecha- nisms than real deployments typically experience. Since real 5.8 RRset-ANY Attack Against BIND For- deployments do not experience sustained 100% cache-miss warders workloads, we regard our test region of 1-10K cache-miss QPS as representative of operational stress conditions. We evaluated the RRset-ANY variant (§ 4.2.1) against Experiments at 10,000 QPS were executed on dedicated BIND 9.20 configured as a forwarder to Google’s Public DNS Azure Standard D16ls v5 16-core, 32 GiB resolver ma- servers (8.8.8.8, 8.8.4.4). The general setup was identi- chines. All other experiments (1-1,000 QPS) were conducted cal to § 5.1, except that the resolver operated solely in for- on Azure Standard D4as v5 4-core, 16 GiB resolver ma- USENIX Association 35th USENIX Security Symposium 6217 1 1 RR-QMA 9.18 @1 RR-QMA 9.18 @100 RR-QMA 9.20 @1 0.95 RR-QMA 9.20 @100 0.8 RR-QMA 9.20 @10K RRset 9.20 @1 CDF Success Rate 0.9 RRset 9.20 @100 0.6 RRset 9.20 @10K RRset-ANY 9.20 @1 0.85 RRset-ANY 9.20 @100 RRset-ANY 9.20 @10K 0.4 0.8 0 1 2 3 0.2 Offset 0 1 10 100 1,000 10,000 Figure 4: CDF of PRNG offset values per attack variant and Resolver Load [QPS] load. Most attacks succeed with low offsets, even under heavy load. RR-QMA 9.18 @10K is not plotted since the attack fails 9.18 RR-QMA 9.20 RR-QMA 100% of the time. Note that RR-QMA 9.20 @1 graphically 9.21 RR-QMA 9.20 RRset coincides with RR-QMA 9.20 @100, and RR-QMA 9.20 9.21 RRset 9.20 RRset-ANY @10K graphically coincides RRset 9.20 @1 and RRset 9.20 9.21 RRset-ANY @100. Figure 3: Attack success rate vs. resolver load. 6 Discussion Our experiments highlight several noteworthy aspects of the chines. Each load point was tested for 100 iterations. attack’s behavior and operational implications. PRNG offset distribution under load. Fig. 4 shows that Success Rate vs Load. Fig. 3 shows the cache poisoning for low to moderate loads (1-100 QPS), most successful cache success rate as a function of query load, ranging from 1 to poisoning attempts occur with a PRNG offset of 0 or 1. As 10,000 QPS. While most variants remained effective at moder- the load increases, the distribution flattens somewhat; yet ate loads, several configurations exhibited performance degra- even at 10,000 QPS, the vast majority of successful attacks dation under high load. In particular, the RR-QMA variant complete within the first few offsets. In practical terms, this against BIND 9.18.37 completely failed at 10,000 QPS. RR- means that the cache can often be poisoned with as few as QMA also showed reduced reliability on BIND 9.21.9 and 3-4 spoofed packets (or 6-8 if targeting two ANS IPs), even 9.20.10 under load. In contrast, RRset-ANY maintained a under heavy load. This property reflects the accuracy of our success rate above 94% even at the highest tested load. PRNG state recovery procedure and demonstrates that our prediction strategy remains highly effective even under heavy concurrency, contributing directly to the high success rates of the RRset and RRset-ANY variants. Offset CDF. In our load experiments, we also measured the PRNG offset (i.e., PRNG steps) between the PRNG state Load-dependent degradation. The only baseline exper- right after it is observed by the attacker (obtained from the iment that failed entirely under maximum tested load was re-sync query, immediately before the poisoning query), and RR-QMA against BIND 9.18.37 at 10,000 QPS. We attribute the PRNG state used to generate the UDP source port and this to the complexity of finding a representative domain for TXID for the poisoning query. For each offset, the attacker the same PRNG/thread of the target domain (see App. B) un- needs to send a spoofed answer with source port and TXID der high load. In contrast, in BIND 9.20 and 9.21 the threading corresponding to the PRNG state at the prescribed offset. assignment model ensures that queries sharing the same 4- Since the attacker’s goal is to cover as much probability space tuple are always handled by the same PRNG instance (§ 4.1), (in terms of offsets) as possible in the attack window, it follows eliminating the need to search for a representative domain; that the ideal situation for the attacker is to have very few as a result, RR-QMA succeeds at moderate loads and RRset- (ideally one) offsets that cover almost 100% of the probability ANY retains > 94% success at 10,000 QPS. App. C provides space. Fig. 4 shows the cumulative distribution of this offset an upper-bound attack success calculation for a system under for various attack variants and query loads. load. 6218 35th USENIX Security Symposium USENIX Association Variant-specific observations. The RRset-ANY variant port, and only varied the TXID, which those attacks accurately consistently delivers the best resilience under load, owing to predicted. Those vulnerabilities were promptly fixed by ISC. its ability to extract multiple consecutive PRNG outputs atom- Then in 2008, Kaminsky described a powerful DNS cache ically. Our “Living off the Land” experiment (§ 5.7) demon- poisoning attack concept [23] which forced vendors to add strates that this attack can be mounted opportunistically using UDP source port randomization to their DNS resolvers. Since large-in-record-count RRsets served by legitimate third-party then, a DNS cache poisoning attack (except fragmentation domains, eliminating the need for attacker-operated ANS for attacks) has to predict/enumerate over the 230 -232 space of attacker domains. By leveraging existing infrastructure, an TXID and port combinations. attacker both reduces their operational footprint and makes Post-Kaminsky attacks typically try to predict/infer the detection and attribution more difficult. Forwarder-mode ex- UDP source port used by the resolver/forwarder. Specifically periments (§ 5.8) further confirm that the attack is also highly w.r.t. Linux, Man et al. exploit a side channel in the Linux effective against BIND forwarders. ICMP rate limit mechanism [32] and a side channel in the The RR-QMA variant remains applicable in scenarios Linux “next hop exception table” [33]. These attacks suffer where the RRset order is fixed rather than randomized, and is from numerous drawbacks: (i) they rely on brute-forcing the also effective against BIND 9.18. TXID field, thus for every UDP port candidate, 65536 packets are needed to combine it with all possible TXID values. This Resilience to defense mechanisms. An important practical makes these attacks less stealthy, i.e., they may trigger burst advantage of our technique is that, unlike prior post-Kaminsky detection or spoofing detection; (ii) an L4 stateful firewall port-inference attacks, it does not rely on generating or ob- may silently drop the “unexpected” traffic used by these at- serving “unexpected” traffic such as ICMP errors or UDP tacks to determine the UDP source port, e.g., ICMP messages packets to closed ports. Such traffic is often silently dropped and UDP traffic to closed ports. If so, this traffic does not by stateful L4 firewalls, preventing the side channels based arrive to the resolver/forwarder and the would-be effect of it on them from working. Our approach relies only on stan- is annihilated, resulting in a failure of the underlying attack dard resolver query/response flows, so stateful firewall rules technique. Moreover, such anomalous traffic patterns may be have no impact on the attack logic. Similarly, NAT devices detected by anomaly-detection systems, e.g. Afek et al. [2]; that rewrite source ports do not prevent our technique from (iii) they are completely ineffective if port rewriting is used, recovering the TXID (and in some cases the UDP port) – e.g., when the resolver/forwarder is behind a NAT; and (iv) NAT simply increases the number of spoofed packets needed, nowadays, they are no longer in effect since they were fixed roughly proportional to the NAT port range, but the attack re- by the respective vendors. mains viable. Finally, anomaly detection systems of the kind In contrast, our technique can predict (up to very few candi- described by Afek et al. [2] – which monitor query patterns dates) the UDP port and TXID used by the resolver/forwarder and traffic bursts – are less effective here because our queries without a need for brute-forcing; our attack does not make are few in number, closely mimic legitimate traffic, and can use of “unexpected” traffic as part of the underlying tech- be scheduled with realistic inter-packet timing, avoiding the nique; our attack can still predict the TXID even when a NAT large bursts characteristic of brute-force TXID guessing. is present, and can thus still be used, albeit requiring more spoofed packets (typically a small factor times the NAT port range); and our attack is in full effect at the time of writing. 7 Related Work 7.1 DNS Cache Poisoning Against Resolvers 7.1.2 Fragmentation Attacks and Forwarders Fragmentation attacks such as Herzberg et al. [16] and Zheng With the bailiwick rule introduction (ca. 1997), off-path DNS et al. [43] spoof a 2nd fragment, which requires predicting cache poisoning attacks against resolvers became reliant on (or guessing) the 16-bit IPv4 ID value of the genuine 1st successfully spoofing a legitimate ANS response. This in turn fragment of the DNS answer (as opposed to the 30-32 bits necessitated matching the expected resolver query’s UDP of the TXID and UDP port combinations in non-fragment source port and TXID, or exploiting fragmentation in the attacks). Historically, this made them significantly more prac- ANS response and spoofing its 2nd fragment. tical. However, modern DNS operations have effectively elim- inated this attack surface. The current DNS best practices (e.g., Travis Palmer’s DefCon 27 talk [39] and the 2020 DNS 7.1.1 TXID and UDP Port Attacks Flag Day [10]) recommend avoiding DNS fragmentation en- The last time a prominent DNS resolver (BIND) was shown to tirely by limiting the size of DNS UDP responses to e.g. be vulnerable to DNS cache poisoning attack requiring very 1232 bytes at the DNS level (advertised through EDNS). For few packets was in 2007, in the attacks against BIND 9 [25] IPv6, this alone suffices to prevent fragmentation since IPv6 and BIND 8 [24]. In that era, BIND used a fixed UDP source mandates a minimal MTU of 1280 bytes (1232 at the DNS USENIX Association 35th USENIX Security Symposium 6219 level). For IPv4, this can be coupled with instructing the op- conditions, including heavy load (10,000 cache miss QPS), erating system to ignore PMTU and fragment according to and the presence of stateful firewalls or DNS cookies. the local interface MTU (which is typically larger than 1280, The same weak PRNG that governs port and TXID se- e.g. 1500) – together with the DNS size limit, this ensures lection is also used to shuffle RRsets, opening the door to a that DNS answers are not fragmented at the origin. Major novel and largely unexplored attack vector: extracting PRNG ANS implementations nowadays employ these measures, and state from the ordering of large RRsets. This vector enables specifically use Linux’s IP_PMTUDISC_OMIT socket option to a pure client-side prediction of both TXID and UDP port this end. In addition, Linux has hardened its fragment-ID gen- – something most prior attacks could not achieve – remov- eration in 2021: IPv6 fragment IDs became random, and IPv4 ing the requirement for attacker-controlled ANS for attacker fragmentation attacks were further mitigated by enlarging the domains, and significantly lowering operational risk. IPv4 ID table (considerably increasing the attack cost). We further show that many existing DNS security and pri- A more general approach is suggested by RFC 9715 which vacy mechanisms offer no protection against this class of specifically states that “UDP requestors should drop frag- attacks. Specifically, DNS cookies, anomaly detection mecha- mented DNS/UDP responses [. . . ] to avoid cache poisoning nisms such as suggested by Afek et al. [2], and qname mini- attacks (at the firewall function)” [12, Section 3.2]. As such, mization do not block our methods; in fact, qname minimiza- existing fragmentation-based attacks are likely to fail due to tion can even enhance certain attack variants by introducing having fragments getting detected and dropped by firewalls near-atomicity to specially-crafted query batches. and anomaly detection systems, in contrast to our attack which Our findings demonstrate that PRNG state recovery -based does not rely on fragmentation, and which only needs a few DNS cache poisoning remains a relevant and impactful threat spoofed packets. in 2025 – long after the community assumed such few-packet attacks had been eliminated. All vulnerabilities were respon- 7.2 Other DNS Cache Poisoning Attacks sibly disclosed to ISC and FreeBSD, leading to acknowledg- ment and two patches and CVEs. Alharbi et al. describe a local DNS cache poisoning attack against DNS stub resolvers based on port exhaustion [3]. Gier- lings et al. describe a port exhaustion attack via a malicious 9 Future Work Javascript code running in a browser [13]. Klein describes a remote DNS cache poisoning attack against a (Linux) DNS In this research, we were limited to testing the attack on our stub resolver based on predicting the UDP source ports used own servers, and a handful of open resolvers. An interest- by the stub resolver [30]. None of these attacks targets re- ing research direction would be to ethically test the attack solvers or forwarders. against production grade resolvers such as ones used in ISPs, enterprises and organizations. Since the crux of the attack is predicting the TXID and UDP source port of an outbound 7.3 Breaking Xoshiro128** DNS query, the success of a full (and harmful) attack can be O’Neill describes a full internal state reconstruction attack forecast from the “inert” version of the attack (merely predict- against Xoshiro256** given four consecutive full PRNG out- ing the query parameters and verifying by forcing a query to puts [38]. This attack can be easily adapted to Xoshiro128**. the researcher’s ANS). However, our RR-QMA attack variant relies on observing The main challenge we perceive in conducting this future non-consecutive, partial PRNG outputs (the TXID field ex- research is access to production-grade resolvers, as this needs poses the 16 least significant bits out of 32 bits of PRNG to be from within the specific network they serve (the ISP output, every 2nd PRNG step). Our reconstruction attack can customer network, or the corporate/organization internal net- be generalized to any XoshiroNNN** algorithm, given suffi- work). Obtaining access to these networks at a large scale is cient (not necessarily consecutive) partial PRNG outputs (8 not trivial. or more least significant bits). The proposed research can teach us about patch propaga- tion, patch coverage, as well as fresh data about BIND 9’s market share, perhaps even with a version breakdown. Run- 8 Conclusion ning a periodic scan can show how these properties change and evolve over time. Securing protocol fields is difficult and full of pitfalls. To wit: we find that the most widely deployed open-source DNS server, BIND 9, suffers from a fundamental weakness in this Acknowledgments exact area, even though there is no question about ISC’s aware- ness of the problem and its importance. This flaw enables We thank Oriyan Hermoni, Agam Ebel, Inbal Schussheim, a highly efficient, few-packet cache poisoning attack with and Noam Caspi for their careful reading of early drafts of this success rates approaching certainty under realistic Internet paper and for their many insightful comments that improved 6220 35th USENIX Security Symposium USENIX Association both the clarity and technical precision of this work. We thank In § 5.6 we accessed five BIND 9.20 resolvers which we do Oriyan Hermoni for additionally helping us with the artifact not own and simulated an attack against them. As explained testing and improvement. We are grateful to Ondřej Surý in § 5.6, we did not attempt to actually poison the cache of (ISC) for his professional collaboration during our coordi- these servers, but rather we compared in offline the predicted nated disclosure process and for developing and validating outbound query’s TXID and UDP source port to the values we the corresponding BIND patches. observed in our own ANSes. All our queries to the resolvers We also thank the anonymous reviewers and our shepherd were 100% standard-compliant DNS queries. These “attacker” from USENIX Security ’26 for their constructive feedback queries triggered outbound queries from the resolver to our and guidance, which significantly strengthened the final ver- own ANS, thus we had complete control over the answer sion of this paper. they receive and process as a result of our queries, and we could guarantee this answer is completely DNS compliant. Furthermore, we specified short TTL for our records in the Ethical Considerations response, thus making sure our added pressure on the cache is negligible. We took special care not to send more than 1 Disclosures query per second to any server. Moreover, the total number of We disclosed the security vulnerabilities in BIND to ISC queries each server received was 220. The answers received via email on August 19th , 2025. The PRNG vulnerability is from these servers were as expected and have not indicated tracked as CVE-2025-40780 [21]. ISC issued a patch in Oc- any disruption of service. Finally, since our attack ends up in tober 22nd , 2025 [4], replacing the insecure Xoshiro128** reconstructing the internal PRNG state of these resolvers, we PRNG with a more cryptographically secure alternative used a specially crafted version of our attack script that does (arc4random() where available, uv_random() elsewhere), not log or print any data on the internal PRNG state recovered see commit 6876753c7ccd.3 This patch is incorporated in – it only prints the expected TXID and source port predicted BIND 9.18.41, 9.20.15 and 9.21.14. for the next few queries, which we then compare to the actual Regarding the RRset-order randomness issue, ISC has pub- query data that arrives at our ANS. licly acknowledged that BIND’s RRset shuffling was never In § 5.7 we attacked our own resolver, by accessing 10 stan- intended to provide uniform randomness [20]. The documen- dard ANSes which we do not own, and one DRINK server tation was updated accordingly in commits 46c88265daa44 (a server running a special kind of authoritative DNS name and 369c8dc388ca5 (included in releases 9.20.13 and server software) we do not own. All our queries to these 9.21.12), explicitly clarifying that rrset-order random servers were 100% standard-compliant DNS queries, that are does not guarantee a uniform distribution. Moreover, ISC completely within the expected protocol and API for the spe- decided to deprecate the random mode entirely for its future cific services accessed. Furthermore, we took special care not BIND versions: starting in BIND 9.21.14, the random option to send more than 1 query per second to any server. Finally, was fully removed from the software.6 the total number of queries each server received was approxi- We disclosed the FreeBSD vulnerability described in mately 10. The answers received from these servers were as App. A to the FreeBSD Security Team via email on August expected and have not indicated any disruption of service. 19th , 2025. This issue is tracked as CVE-2025-24934, and a Per the above safety measures and constraints, we consider patch was issued by the FreeBSD Security Team on October the risk to 3rd -party systems extremely negligible, and as such 22nd , 2025.7 our experiments are justified. Experiments with live systems without informed consent Stakeholder analysis Beyond specifically the five open resolvers and 11 ANSes In § 5.6 and § 5.7 we describe experiments which access we experimented with (see above), we identify the following 3rd -party systems. In both cases, the target domain we used stakeholders: was our own domain, so at no point was any 3rd -party domain at risk. • BIND 9 operators: the BIND 9 patch was clearly an- 3 https://gitlab.isc.org/isc-projects/bind9/-/commit/6876 nounced in the public ISC “bind-announce” mailing 753c7ccd67d445a6a2341219fe79cff6c77f list.8 And since ISC assigned the issue a CVE with a 4 https://gitlab.isc.org/isc-projects/bind9/-/commit/46c8 high CVSS score (8.6), and marked its severity as “High” 8265daa400b49c24abefa6272fb5cbe94cc0 5 https://gitlab.isc.org/isc-projects/bind9/-/commit/369c in its accompanying security advisory [4], the issue is 8dc388caad0d4fa7e9da15a3a0cd62cd3b39 unlikely to go unnoticed by ISC BIND operators. We 6 https://downloads.isc.org/isc/bind9/9.21.14/doc/arm/ht argue that this should compel any reasonable operator ml/notes.html#removed-features 7 https://www.freebsd.org/security/advisories/FreeBSD-SA- 8 https://lists.isc.org/pipermail/bind- announce/2025- 25:09.netinet.asc October/001282.html USENIX Association 35th USENIX Security Symposium 6221 to upgrade ASAP. As the paper and the artifact will be References released 3+ months after the BIND patch was released, BIND operators have a substantial window (3+ months) [1] D. Eastlake 3rd and M. Andrews. Domain Name System in which to deploy the patch, before the attack details (DNS) Cookies. https://datatracker.ietf.org/d become public. oc/html/rfc7873, 2016. RFC 7873. Therefore, we argue that the bigger operators are very [2] Yehuda Afek, Harel Berger, and Anat Bremler-Barr. likely to notice the patch via the ISC announcement POPS: From History to Mitigation of DNS Cache Poi- email and/or via proactive patch/CVE monitoring, and soning Attacks. In Proceedings of the 34th USENIX Se- most probably patch within the 3-month window, while curity Symposium, Seattle, WA, August 2025. USENIX the smaller operators are likely to automatically get Association. patched by e.g. OS distribution package updates and upgrades, which pick up 3rd -party security patches on a [3] F. Alharbi, J. Chang, Y. Zhou, F. Qian, Z. Qian, and regular basis, so again, they are likely to get the patch N. Abu-Ghazaleh. Collaborative Client-Side DNS within the said window. Cache Poisoning Attack. In IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, pages • Non-DNSSEC domain owners and operators: the- 1153–1161, April 2019. oretically, domain owners can be affected by attacks mounted against un-patched BIND 9 resolvers, targeting [4] Darren Ankney. CVE-2025-40780: Cache poisoning their domains. From the argument we present for BIND 9 due to weak PRNG. https://kb.isc.org/docs/cv operators, it follows that in practice, we do not expect e-2025-40780, October 2025. domain owners to be affected, due to prompt patching [5] Omer Ben-Simhon and Amit Klein. DNS Cache Poison- of BIND 9 by its operators. ing Like it’s 2006 (Extended Version). https://www. securitygalore.com/files/DNS_cache_poisoni • End users/devices that resolve via a BIND 9 resolver/- ng_like_its_2006_extended_version.pdf, 2026. forwarder: these can be affected by attacks mounted against an un-patched BIND 9 resolver/forwarder, tar- [6] David Blackman and Sebastiano Vigna. xoshiro128**. geting domains they later request from the same re- https://prng.di.unimi.it/xoshiro128starsta solver/forwarder. Again, we argue that in practice, by the r.c, 2018. time the attack becomes public, the BIND 9 resolver/for- warder will already be patched. [7] Stephane Bortzmeyer, Ralph Dolmans, and Paul E. Hoff- man. DNS Query Name Minimisation to Improve Pri- vacy. RFC 9156, November 2021. Open Science [8] Tianxiang Dai, Philipp Jeitner, Haya Shulman, and We release a public artifact accompanying this paper, which Michael Waidner. From IP to transport and beyond: contains the full implementation of two variants of our attack cross-layer attacks against applications. In Proceed- and additional documentation needed to reproduce our results. ings of the 2021 ACM SIGCOMM 2021 Conference, The artifact is available at the time of this paper’s publication SIGCOMM ’21, pages 836–849, New York, NY, USA, and is described in detail below. 2021. Association for Computing Machinery. [9] Jacob Davis and Casey Deccio. A Peek into the DNS Artifact Contents and Entry Points. Our artifact is hosted Cookie Jar. In Passive and Active Measurement (PAM), in Zenodo9 . The artifact contains an attacker client implement- pages 302–316. Springer, 2021. ing our client-side cache-poisoning attack variants (RRset and RRset-ANY). The client is written in C++20 and Python. A [10] DNS-OARC. DNS flag day 2020. https://www.dnsf detailed overview and instructions appear in README.md. lagday.net/2020/, 2020. [11] FreeBSD. FreeBSD Manual Pages (connect). https:// Targets and Parameters. Experiments are intended for a man.freebsd.org/cgi/man.cgi?query=connect, controlled testbed where the evaluator runs a BIND 9 re- 2016. solver (victim), an attacker-controlled authoritative name- server (ANS), an attacker-controlled client, and a genuine [12] Kazunori Fujiwara and Paul A. Vixie. IP Fragmentation ANS. The zone files, configurations, and instructions for each Avoidance in DNS over UDP. RFC 9715, January 2025. machine are detailed in the README file. [13] Matthias Gierlings, Marcus Brinkmann, and Jörg 9 https://doi.org/10.5281/zenodo.17762025 Schwenk. Isolated and exhausted: attacking operating 6222 35th USENIX Security Symposium USENIX Association systems via site isolation in the browser. In Proceedings [26] Amit Klein. Windows DNS Server Cache Poisoning. of the 32nd USENIX Conference on Security Symposium, https://dl.packetstormsecurity.net/paper SEC ’23, USA, 2023. USENIX Association. s/attack/Windows_DNS_Cache_Poisoning.pdf, 2007. [14] Austin Group. The Open Group Base Specifications Issue 8 IEEE Std 1003.1-2024 (connect). https://pu [27] Amit Klein. OpenBSD DNS Cache Poisoning and bs.opengroup.org/onlinepubs/9799919799/fun Multiple O/S Predictable IP ID Vulnerability. https: ctions/connect.html, 2024. //dl.packetstormsecurity.net/papers/atta ck/OpenBSD_DNS_Cache_Poisoning_and_Multipl [15] Olafur Guomundsson. Looking at DNS traces: What e_OS_Predictable_IP_ID_Vulnerability.pdf, do we know about resolvers? https://archive.ic February 2008. ann.org/en/meetings/siliconvalley2011/bitc ache/Conclusions%20from%20DNS%20Traces%20- [28] Amit Klein. PowerDNS Recursor DNS Cache Poison- %20Olafur%20Gudmunsson,%20Shinkuro-vid=23 ing. https://dl.packetstormsecurity.net/pap 075&disposition=attachment&op=download.pdf, ers/attack/PowerDNS_recursor_DNS_Cache_Poi 2011. soning.pdf, 2008. [29] Amit Klein. Hijacking DNS, October 2016. The Hebrew [16] Amir Herzberg and Haya Shulman. Fragmentation Con- University Cyber Security Center Retreat. sidered Poisonous. CoRR, abs/1205.4011, 2012. [30] Amit Klein. Cross Layer Attacks and How to Use Them [17] Geoff Huston. ICANN DNS Resolver Symposium. ht (for DNS Cache Poisoning, Device Tracking and More). tps://www.potaroo.net/ispcol/2021-12/dns- In 2021 IEEE Symposium on Security and Privacy (SP), sym.pdf, 2021. pages 927–944, Los Alamitos, CA, USA, May 2021. IEEE Computer Society. [18] Geoff Huston. DNSSEC validation: Performance killer? https://blog.apnic.net/2022/08/22/dnssec- [31] Matthew Luckie, Robert Beverly, Tor Anderson, Ken validation-performance-killer/, 2022. Keys, and Casey Claffy. Network Hygiene, Incentives, and Regulation: Deployment of Source Address Vali- [19] ICANN. ITHI M11: Resolver Behavior – DNSSEC dation in the Internet. Technical report, University of Validation. https://ithi.research.icann.org/gr Waikato, 2019. aph-m11.html, 2025. Accessed: 2025-10-25. [32] Keyu Man, Zhiyun Qian, Zhongjie Wang, Xiaofeng [20] ISC. BIND9 Issue #5485: RRset-order random distri- Zheng, Youjun Huang, and Haixin Duan. DNS Cache bution clarification. https://gitlab.isc.org/isc- Poisoning Attack Reloaded: Revolutions with Side projects/bind9/-/issues/5485. Accessed: 2025- Channels. In Proceedings of the 2020 ACM SIGSAC 10-25. Conference on Computer and Communications Security, CCS ’20, pages 1337–1350, New York, NY, USA, 2020. [21] ISC. CVE-2025-40780: BIND9 predictable PRNG vul- Association for Computing Machinery. nerability. https://kb.isc.org/docs/cve-2025- 40780. Accessed: 2025-10-25. [33] Keyu Man, Xin’an Zhou, and Zhiyun Qian. DNS Cache Poisoning Attack: Resurrections with Side Channels. [22] Jaeyeon Jung, Emil Sit, Hari Balakrishnan, and Robert In Proceedings of the 2021 ACM SIGSAC Conference Morris. DNS Performance and the Effectiveness of on Computer and Communications Security, CCS ’21, Caching. In IEEE/ACM Transactions on Networking, pages 3400–3414, New York, NY, USA, 2021. Associa- 2002. tion for Computing Machinery. [23] Dan Kaminsky. Black-Ops 2008 – It’s The End Of The [34] Gilad Moav, Yehuda Afek, Anat Bremler-Barr, and Amit Cache As We Know It. In Black Hat USA, August 2008. Klein. DNS FLaRE: A Flush-Reload Attack on DNS Forwarders. In 34th USENIX Security Symposium [24] Amit Klein. BIND 8 DNS Cache Poisoning. https: (USENIX Security ’25), pages –, Seattle, WA, USA, //dl.packetstormsecurity.net/papers/attack August 2025. USENIX Association. Open access; /BIND_8_DNS_Cache_Poisoning.pdf, 2007. USENIX Security ’25, August 13-15, 2025. [25] Amit Klein. BIND 9 DNS Cache Poisoning. https: [35] P. Mockapetris. Domain Names - Concepts and Facili- //citeseerx.ist.psu.edu/pdf/0c1e863b669880 ties. RFC 1034, November 1987. https://www.rfc- 8b724def8793d7cba023494808, 2007. editor.org/rfc/rfc1034. USENIX Association 35th USENIX Security Symposium 6223 [36] P. Mockapetris. Domain Names - Implementation and During our experiments with FreeBSD, we noticed Specification. RFC 1035, November 1987. https: a violation of the guarantee to only allow incoming //www.rfc-editor.org/rfc/rfc1035. datagrams into the socket from the remote host and port specified in the connect() call. This violation oc- [37] Ondrej Sury. Don’t set load-balancing socket option curs when the socket is set to “load balancing” mode on the UDP connect sockets . https://gitlab.isc prior to an explicit bind() for the port, or prior to .org/isc-projects/bind9/-/commit/b6b7a688 the implicit bind in a call to connect(), via a call to 6a8ac66bc3932158740998a3bf2da014, 2022. setsockopt(...,SOL_SOCKET,SO_REUSEPORT_LB,...). When this happens, FreeBSD allows datagrams from any [38] Melissa E. O’Neill. A Quick Look at Xoshiro256**. remote host and port, to the socket, after the connect() call. https://www.pcg-random.org/posts/a-quick- The attacker can, therefore, send the poisonous DNS re- look-at-xoshiro256.html, May 2018. sponse from any source IP address (for example, the attacker’s [39] Travis Palmer and Brian Somers. "FIRST-TRY" DNS own IP address) and from any port (for example, a non- CACHE POISONING WITH IPV4 AND IPV6 FRAG- privileged port, higher than 1024), instead of only from the MENTATION. https://media.defcon.org/D (spoofed) ANS IP address, and from (privileged) port 53. The EF%20CON%2027/DEF%20CON%2027%20presentat implication is that the entire attack can now be performed by a ions/DEFCON- 27- Travis- Palmer- First- try- fully unprivileged user, with no raw-socket capability and no DNS- Cache- Poisoning- with- IPv4- and- IPv6- permission to bind to low-numbered ports. This significantly Fragmentation.pdf, 2019. lowers the attacker bar and expands the threat model—for example enabling malware or insiders with only unprivileged [40] George W. Snedecor, R. A. Fisher, and F. Yates. Statisti- user accounts to poison a local BIND 9.18 forwarder running cal Tables for Biological, Agricultural and Medical Re- on FreeBSD. search. Journal of the Royal Statistical Society, 102:298, The SO_REUSEPORT_LB socket option is FreeBSD-specific. 1939. The FreeBSD documentation for this socket option does not mention any exceptional behavior in connect() as a result [41] Trickest. Public List of Open DNS Resolvers. https: of using SO_REUSEPORT_LB. The exceptional behavior was //github.com/trickest/resolvers/blob/main/ not observed for the standard socket options SO_REUSEPORT resolvers.txt, 2024. Accessed: 2025-08-08. and SO_REUSEADDR, neither in FreeBSD nor in Linux. We noticed that BIND 9.18 sets SO_REUSEPORT_LB on its [42] Masanori Yajima, Daiki Chiba, Yoshiro Yoneya, and Tat- outbound sockets, which use connect(). While this makes suya Mori. Measuring Adoption of DNS Security Mech- little sense, since there is no need to load-balance outbound anisms with Cross-Sectional Approach. In IEEE Global sockets, it is not a bug in BIND per-se (assuming correct Communications Conference (GLOBECOM), pages 1–6, behavior of connect()). 2021. However, in this case, connect()’s behavior is incorrect and insecure, and as such it has implication on the entire sys- [43] Xiaofeng Zheng, Chaoyi Lu, Jian Peng, Qiushi Yang, tem. In short, given a “classic” remote DNS cache poisoning Dongjie Zhou, Baojun Liu, Keyu Man, Shuang Hao, attack against BIND 9.18 (as described in this paper), it al- Haixin Duan, and Zhiyun Qian. Poison Over Troubled lows remotely poisoning the cache of BIND 9.18 running on Forwarders: A Cache Poisoning Attack Targeting DNS FreeBSD, without source IP address spoofing and without Forwarding Devices. In 29th USENIX Security Sympo- binding to privileged ports. Here are three concrete scenarios sium (USENIX Security 20), pages 577–593. USENIX where this is advantageous: Association, August 2020. • Unprivileged attacker scenario. Assume a network topology wherein one company branch office (internal A The FreeBSD SO_REUSEPORT_LB Secu- network) has a BIND 9.18 forwarder forwarding queries rity Vulnerability to a central resolver in the company HQ, over private network connections (VPN). Consider an attacker in The POSIX/IEEE/Open Group standard documentation for the branch office who does not have administrator or UDP connect() [14] states that “if the initiating socket is not root privileges (or CAP_NET_RAW/CAP_NET_ADMIN capa- connection-mode, then connect() shall set the socket’s peer bility). This can be malware running without root per- address, and no connection is made. For SOCK_DGRAM missions, or an attacker with an unprivileged account. sockets, the peer address identifies where all datagrams are Such an attacker cannot spoof packets from the machine sent on subsequent send() functions, and limits the remote he/she has limited access to (and no packets, spoofed or sender for subsequent recv() functions.” This is also reflected otherwise, can arrive at the BIND 9.18 forwarder from in the FreeBSD documentation for connect() [11]. the Internet!). But now the attack requires neither source 6224 35th USENIX Security Symposium USENIX Association address spoofing nor binding to privileged ports, so the 4-tuple (source IP address, source port, destination IP ad- attacker can mount a successful attack against the BIND dress, destination port). Listener threads parse these data- 9.18 forwarder running on FreeBSD, because other than grams and forward the queries to worker threads, selected source address spoofing and binding to privileged ports, via a keyed hash of the query name. Worker threads issue our DNS cache poisoning attack needs no privileged outbound queries – this is where TXID and UDP source port operations (just standard TCP/UDP sockets). generation occurs. Once a response is received, it is returned to the originating listener thread, which constructs the final an- • General attack considerations. Even privileged attack- swer (including RRset order shuffling). Because each thread ers, e.g. attacking Internet-facing BIND 9.18 resolvers type maintains its own independent PRNG instance, PRNG from their own machines, may be limited by network outputs (e.g., TXIDs and ports) generated in worker threads source address verification filtering. For these attackers, cannot be predicted from RRset orders produced by listener doing away with the need to spoof the source address threads. makes their operational logistics much easier. • Reducing the entropy of authoritative server choice. B.2 BIND 9.18’s Internal Queues Having multiple ANSes (IP addresses) for a domain In BIND 9.18, internal queues known as “buckets” are used increases the entropy the attacker faces when attempting to dispatch queries from listener threads to worker threads. to spoof the answer from the ANS, as he/she may not Each incoming query name is hashed and deterministically be able to accurately predict which ANS the resolver assigned to one of these buckets. The buckets act as FIFO will access. For BIND 9.18 on FreeBSD, however, the queues and serve as the mechanism for routing queries be- attacker does not need to spoof the ANS’s IP address in tween listeners and workers. order to respond to the query, thus the entropy usually Specifically, the assignment is done by casting the hash gained by having multiple name servers is reduced to of the query name into the range [0, m − 1], where m is the zero. total number of buckets. Each bucket is owned by a single worker thread, and each worker typically manages multiple It should be noted that only BIND 9.18 sets the buckets (historically 32 until version 9.18.33, reduced to 2-3 SO_REUSEPORT_LB option on its outbound UDP sockets. In since 9.18.35). A listener thread places the query into the BIND 9.20 and above this logic is deliberately removed, rea- appropriate bucket, and the owning worker thread processes soning that “this socket option makes only sense for the lis- queries in strict FIFO order. tening sockets” [37]. In other words, BIND 9.20 and 9.21 are not affected, but not due to any recognition that setting SO_REUSEPORT_LB on connected UDP sockets is a security B.3 Adapting the RR-QMA Attack to BIND issue, but rather, due to recognition that the setup makes no 9.18 sense for outbound sockets. To wit, this logic remains in BIND In the initial phase, the attacker breaks the PRNG seed for 9.18 to this day. each worker thread, associating one representative domain per thread. A representative domain is a domain name that maps B Adapting the RR-QMA Attack to BIND 9.18 to a specific resolver worker thread and is therefore resolved using a known PRNG instance. This mapping is later used to help identify which thread is responsible for resolving the In this appendix we explain how to adapt the RR-QMA attack target domain. This ensures that the attacker can accurately to BIND 9.18. We first explain about BIND 9.18’s threading predict the TXID and UDP port used for the subsequent target model and buckets, and then we describe the adaptation of query. the RR-QMA attack to BIND 9.18. Mapping all worker threads is done in a series of distinct rounds, where in each round the attacker reconstructs the B.1 BIND 9.18’s Threading Model PRNG state of a single worker thread. In each round, the at- tacker sends 20 queries with distinct query types for a single Unlike later versions of BIND, BIND 9.18 has two types of FQDN in an attacker domain. Because BIND 9.18 assigns threads: listener threads and worker threads. Upon startup, queries to worker threads based solely on the query name, BIND 9.18 determines the number of logical CPU cores using the same name guarantees that all queries map to the (“threading cores”) and instantiates that many copies of its same BIND worker thread and PRNG instance. By analyzing listener threads and worker threads. Each thread maintains a the resolver’s outbound queries to the attacker’s ANS, the at- dedicated instance of the PRNG. tacker reconstructs the worker thread’s 128-bit PRNG internal Incoming datagrams are dispatched to listener threads by state. The attacker conducts multiple rounds, each with dis- the operating system based on a hash of their transport-level tinct query names, until all worker threads’ PRNG states are USENIX Association 35th USENIX Security Symposium 6225 identified. Each newly reconstructed PRNG state is compared to 36 PRNG steps in any set indicates the domain pair x1,x2 to previously found states, advanced several million steps for- shares the worker thread with the target domain g. Once the ward. If the new state matches any state in the series obtained pair is found, the attacker marks the representative domain from an already broken PRNG (worker thread), the attacker (e.g. x1) associated with the target domain’s worker thread. identifies it as belonging to an already discovered thread; oth- Finally, the attacker performs cache poisoning as described erwise, it is deemed to belong to an unseen-before thread. The in § 4.5. The representative domain for the target domain’s attacker continues until no new threads are discovered after worker thread is queried first to synchronize with the PRNG a sufficient number of additional rounds, ensuring with high state. The target domain is queried immediately afterward. confidence that all worker threads have been identified (see This ensures that the PRNG instance used for the target do- the extended version of this paper [5, App. B.4]). main is the same one whose state has just been recovered, Next, for each identified worker thread, the attacker must which is crucial for being able to predict the actual TXID and find a validated pair – two representative domains served UDP port values. With the PRNG state known, the attacker by the thread but mapped to two distinct internal buckets crafts and injects a spoofed response matching the expected in BIND. To achieve this, the attacker generates a sequence TXID and UDP port, which the resolver accepts and caches. (stream) of candidate domains mapped to the targeted worker This attack variant does not depend on RRset randomiza- thread. Each candidate domain pair is tested by sending al- tion. Instead, it exploits BIND 9.18’s deterministic mapping ternating queries (e.g., x1,x2,x1,x2,...) and analyzing the of queries to worker threads and buckets, combined with the order of outbound queries the resolver sends to the attacker’s predictability of the thread-local PRNG. It assumes control ANS. Queries are sorted by their original transmission or- over an ANS and visibility into queries directed at it. Specifi- der, and the PRNG state is rolled forward until matching the cally, the TXID is observed and used, but optionally the UDP observed TXID from the first query. Subsequent queries are source port may be needed (see the extended version of this checked by advancing the PRNG twice per query and verify- paper [5, App. D]). ing consistency with observed TXIDs. If the observed order differs from the predicted order, it indicates that the domains C Impact of UDP unavailable ports map to distinct buckets (since FIFO order is always main- tained if they belong to the same bucket) and a validated When the UDP port number generated by BIND’s PRNG pair is found. Otherwise, the attacker discards the 2nd domain is already in use, BIND retries with another random value. candidate and proceeds with the next candidate. This retry disrupts the expected PRNG sequence, and in many Subsequently, the attacker identifies which validated do- contexts – particularly when precise PRNG state tracking main pair corresponds to the same worker thread as the is required – this behavior undermines our prediction accu- target domain www.target.example (which we now re- racy. The effect is exacerbated on heavily loaded machines, fer to as g for brevity). For each candidate domain pair where the high number concurrent outstanding queries in- e.g. (x1,x2) the attacker sends three structured sets of 20 creases the probability of collisions. On average, the num- queries each: x1,g,g,...,g,x1, then x2,g,g,...,g,x2, ber of unavailable ports at any moment can be estimated as and finally x1,g,g,...,g,x2. Each set includes exactly 18 L · RTT ANS where L is the outbound query load in QPS units queries for the domain g, resulting in precisely 36 PRNG and RTT ANS is the round-trip time between the resolver and invocations (18 TXIDs and 18 UDP source ports) for the g the load ANS. The probability that a generated UDP port queries. By aligning the PRNG state with the TXID and UDP is unavailable is therefore L·RTT ANS Rephemeral where Rephemeral is the source port observed for the initial query and advancing it size of the ephemeral port range configured on the system. through subsequent queries, the attacker measures PRNG step On Linux, Rephemeral is typically 28232 (ports 32768-60999). distances between the x queries in each set. If g belongs to At high L values or with larger RTT ANS , this probability be- the same bucket as x1 then it is guaranteed to form a gap comes non-negligible, making retries more frequent and the of 36 PRNG steps in the first set. Likewise with x2 and the PRNG step sequence less predictable. It bounds from above second set. Finally if g is served by the same thread but does the success rate of a single attack attempt. additionally, it ne- not share a bucket neither with x1 nor with x2 then it is not cessitates larger search window X in the optional client port guaranteed that g forms a gap even if it is served by the same range inference step (see our extended version paper [5, App. thread; however, if a large gap (36 steps) between x1 and x2 is C]), to compensate for the occasional skipped or replaced observed we can assume that g formed it and thus g is served PRNG outputs. from the same thread. Therefore, a gap exactly corresponding 6226 35th USENIX Security Symposium USENIX Association