search menu icon-carat-right cmu-wordmark
Carnegie Mellon University

Software Engineering Institute

CERT Coordination Center

Various DNS service implementations generate multiple simultaneous queries for the same resource record

Vulnerability Note VU#457875

Original Release Date: 2002-11-19 | Last Revised: 2004-10-18

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.

By rapidly generating multiple queries for an RR to a vulnerable resolver, the attacker can induce a condition whereby the vulnerable resolver has multiple open queries for that RR. The attacker then sends a number of spoofed responses to the vulnerable resolver. Given the right combination of open queries and spoofed responses, the attacker can achieve a high probability of success with far fewer packets (by several orders of magnitude) than the traditional brute-force approach would require.

This attack is quite effective against caching nameservers that provide recursive services. Recent research by Gummadi, Saroiu, and Gribble [GUMMADI] indicates that a large proportion of nameservers are configured to provide recursive services to the Internet at large, thereby laying them open to this kind of attack.

The specific number of packets required to exploit any particular DNS resolver vary by implementation, but the following table lists a few of the more common scenarios found in a number of implementations

If the attacker has to guess...
...and is limited to the following number of open requests...
...it will take the following number of packets to achieve a 50% success rate
(includes both requests and responses)
TID only (16bits)
1
32.7 k (215)
TID only (16bits)
4
10.4 k
TID only (16bits)
200
427
TID only (16bits)
unlimited
426
TID and port (32 bits)
1
2.1 billion (231)
TID and port (32 bits)
4
683 million
TID and port (32 bits)
200
15 million
TID and port (32 bits)
unlimited
109 k
Table 1: Number of packets required to reach 50% success probability for various numbers of open queries

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

advisory-CAIS-vagner.pdf

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":

Disabling recursion puts your name servers into a passive mode, telling them never to send queries on behalf of other name servers or resolvers. A totally non-recursive name server is protected from cache poisoning, since it will only answer queries directed to it. It doesn't send queries, and hence doesn't cache any data. Disabling recursion can also prevent attackers from bouncing denial of services attacks off your name server by querying for external zones.
Non-recursive nameservers should be much more resistant to exploitation of the server vulnerabilities listed above.

Vendor Information

457875
 
Expand all

View all 44 vendors View less vendors


CVSS Metrics

Group Score Vector
Base
Temporal
Environmental

References

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

Sponsored by CISA.

Download PGP Key

Read CERT/CC Blog

Learn about Vulnerability Analysis