Overview
Various implementations of DNS services may allow multiple simultaneous queries for the same resource record, allowing an attacker to apply probabilistic techniques to improve their odds of successful DNS spoofing.
Description
Some implementations of DNS services contain a vulnerability whereby multiple requests for the same resource record (RR) will generate multiple outstanding queries for that RR. As a result, it is possible for an attacker to apply a 'birthday attack' technique to dramatically improve the probability of a successful DNS spoofing attack. When performed against a caching nameserver, this can result in cache poisoning; however, similar techniques could be applied to some stub resolvers as well. The only distinction between this attack and the traditional brute-force approach (1 query with multiple spoofed replies) is the generation of multiple simultaneous queries. The attacker need not sniff any packets between the victim resolver and the legitimate nameservers for the RR being spoofed. An attacker's success against any particular resolver instance will be probabilistic in nature, with a persistent attacker always being able to achieve a reasonable probability of success given enough attempts.
As expected, the traditional brute-force case where the attacker tries to guess the transaction ID or TID/port pair based on a single open request requires the attacker to search half the search space (15 or 31 bits, respectively) to achieve a 50% probability of success. However, when the attacker is able to induce the resolver into generating multiple simultaneous requests, the total number of packets required falls off rapidly. There are, of course, more effective methods to achieve DNS spoofing in certain cases, including sniffing query packets directly or the predictable transaction ID issues discussed in CA-1997-22 "BIND - the Berkeley Internet Name Daemon". Additionally, Michal Zalewski's paper "Strange Attractors and TCP/IP Sequence Number Analysis" [ZALEWSKI] describes a method for analyzing the predictability of transaction IDs which we believe could be extended to analyze Transaction ID / UDP port pairs as well. Zalewski's paper was also discussed in CA-2001-09 "Statistical Weaknesses in TCP/IP Initial Sequence Numbers". The 'birthday attack' method described here appears to be reasonably well known in the DNS developer community, but we have been unable to find significant public discussion of it and are thus documenting it here. Further discussion of the probability calculations Assume that the transaction IDs generated by the vulnerable resolver are unpredictable by the attacker (if they're not, then the attack is far simpler than what we describe here; see CA-1997-22 for more). The attacker does not know what the transaction IDs are, but can control how many transaction IDs the vulnerable resolver has open for a particular query at a given time by generating a series of otherwise legitimate queries. (The total number of transaction IDs open on the vulnerable resolver does not factor into this -- only the transaction IDs resulting from the attacker's queries count.) Let m = the number of possible transaction ID / UDP port combinations q = the number of open queries initiated by the attacker r = the number of bogus replies generated by the attacker Note that if the UDP ports are predictable, m = 216. If they are not predictable, m = 232. Of course, if both the transaction IDs and UDP ports are predictable, m approaches 1. The goal for the attacker, therefore, is to find the smallest possible sum of (q + r) with a maximum probability of success. The first bogus reply sent by the attacker will have a probability of success given by P1 = q / m The attacker does not need to care whether any particular reply was successful or not. The only thing the attacker has to keep track of is what IDs have been sent in the bogus replies so there will not be any duplicates. Thus, since the attacker knows what the ID was in the first reply and doesn't want to repeat IDs, he only has a pool of (m - 1) IDs to pick from on the second reply. Therefore, the second reply has a probability of success of P2 = q / (m - 1) Likewise, for each successive iteration, the number of possible IDs the attacker will pick from shrinks by 1. In the generic case, Pn = q / (m - (n - 1)) Each Pn represents the probability of success in the nth iteration, independently of all previous iterations. We can therefore represent the probability of a miss in the nth iteration as Qn where Qn = 1 - Pn = 1 - (q / (m - (n - 1))) The cumulative probability of having missed in all iterations up to and including the nth iteration is CumulativeMissn = Q1*Q2*...*Qn and therefore the cumulative probability of at least one success with r bogus replies is CumulativeHitr = 1 - CumulativeMissr Thus we can calculate the probability of compromise given q queries and r replies. We do this by iteratively fixing q and incrementing r until we reach the desired Pr. To find the optimal combination of q and r, we repeat the process for a number of values of q. "Optimal" is defined as the minimum sum of (q + r). When one considers cases where q > 1, it quickly becomes evident that the attacker's advantage grows significantly with relatively small numbers of queries (q << m). For example, performing the calculations as described above for m = 216, the attacker's probability of success reaches the 50% mark with as few as (q + r) ~= 425 packets. References: [GUMMADI] Krishna P. Gummadi, Stefan Saroiu, and Steven D. Gribble, "King: Estimating Latency between Arbitrary Internet End Hosts", http://www.icir.org/vern/imw-2002/imw2002-papers/198.pdf [ZALEWSKI] Michal Zalewski, "Strange Attractors and TCP/IP Sequence Number Analysis", http://razor.bindview.com/publish/papers/tcpseq.html
|
Impact
An attacker could leverage this vulnerability to remotely spoof DNS responses, which may lead to DNS cache poisoning. |
Solution
Apply a patch from your vendor. |
Disable recursion on any nameserver responding to DNS requests made by untrusted systems. As mentioned in "Securing an Internet Name Server": |
Vendor Information
CVSS Metrics
| Group | Score | Vector |
|---|---|---|
| Base | ||
| Temporal | ||
| Environmental |
References
- http://www.dimap.ufrn.br/
- http://www.icir.org/vern/imw-2002/imw2002-papers/198.pdf
- http://razor.bindview.com/publish/papers/tcpseq.html
- http://mathworld.wolfram.com/BirthdayProblem.html
- http://mathworld.wolfram.com/BirthdayAttack.html
- http://www.securityfocus.com/guest/17905
- http://www.rnp.br/cais/alertas/2002/cais-ALR-19112002a.html
- http://www.rnp.br/cais_en/
- http://www.cert.org/advisories/CA-1997-22.html
- http://www.cert.org/advisories/CA-2001-09.html
- http://www.cert.org/archive/pdf/dns.pdf
Acknowledgements
Thanks to Vagner Sacramento, DIMAp-UFRN. This vulnerability was discovered by Vagner Sacramento during the development of his master thesis in the DIMAp/UFRN (Department of Computer Science and Applied Mathematics / Federal University of Rio Grande do Norte) under the orientation of Prof. Thais Vasconcelos Batista and Prof. Guido Lemos de Souza Filho. CAIS/RNP (the Brazilian Research Network CSIRT) publicly reported the vulnerability after conducting several experiments in order to validate its claims.
This document was written by Allen Householder & Ian A Finlay.
Other Information
| CVE IDs: | None |
| Severity Metric: | 40.50 |
| Date Public: | 2002-11-19 |
| Date First Published: | 2002-11-19 |
| Date Last Updated: | 2004-10-18 15:01 UTC |
| Document Revision: | 49 |