Affected software: Microsoft Windows 2003 SP2, Microsoft Windows 2000 SP4 Server Vendor URL: www.microsoft.com Severity: Medium References: Microsoft Security Bulletin MS07-062, CVE-2007-3898
2) Vulnerability Description
Microsoft DNS server generates predictable DNS transaction IDs. If the server is configured to allow recursive queries it is possible to insert fake records in the DNS cache (DNS cache poisoning) by guessing the next transaction ID that the server will use and sending a spoofed DNS reply to the server. To observe the transaction IDs an attacker needs to control a DNS server that is authoritative for some domain and to be able to send a recursive queries to the caching Microsoft DNS server.
When an attacker sends a recursive query to a caching name server, the caching server will find the server authoritative for the zone and send the request to the authoritative name server. If the attacker can predict the transaction ID of the request that the caching server sends, he can generate spoofed replies. The caching server will accept spoofed reply as coming from authoritative name server and cache the fake data.
The attack scenario is as follows. The attacker controls the authoritative name server for some zone, in our example cache-poisoning.net. The victim has a recursive DNS server that the attacker can query (ns.victim.com). Victim's server runs Microsft DNS server. Attacker wants victim's DNS cache to think that www.hotmail.com has IP address 127.0.0.1 (or any other).
First the attacker gathers a sample of DNS transaction IDs that ns.victim.com uses for outgoing queries. He makes a number of recursive queries to ns.victim.com for hosts in cache-poisoning.net zone. Ns.victim.com will query the name server for cache-poisoning.net. The attacker records the transaction IDs of the requests sent to the name server of cache-poisoning.net by ns.victim.com.
Microsoft DNS transaction IDs follow a certain pattern. There seems to be 8 independent counters that are randomly incremented. Each transaction ID is taken from a randomly chosen counter. So, there are 8 sequences of randomly incrementing numbers. A sample of transaction IDs below illustrates that:
15222 - sequence 1 13177 - sequence 2 2944 - sequence 3 13197 - sequence 2, 13197 > 13177 increment=20 9108 - sequence 4 13208 - sequence 2, 13208 > 13197 increment=11 15268 - sequence 5 9131 - sequence 4, 9131 > 9108 increment=23 7094 - sequence 6 15291 - sequence 5, increment = 23 960 - sequence 7 15309 - sequence 5, increment = 18 980 - sequence 7, increment = 20 3032 - sequence 8 992 - sequence 7, increment = 12 ...
Having gathered a small sample of transaction IDs (50 to 100 is enough) used by the cache, the attacker can record the state of each of the 8 counters on the victim server.
The attacker will then query the victim server for the record he is trying to spoof, for example www.hotmail.com. The victim cache will send a query to the authoritative name server for hotmail.com. At the same time the attacker will send a number of spoofed DNS replies. The replies will have spoofed source address (appearing to come from the nameserver for hotmail.com), fake data (saying that www.hotmail.com is 127.0.0.1) and DNS transaction IDs starting from the recorded values of counters up to counter+500 (or more). In our testing, the attacker has a very good chance of hitting the right transaction ID. If the reply with the right transaction ID spoofed by the attacker will arrive before the reply from the real server, the victim cache will believe the spoofed reply and cache it.
The attack is made easier because Microsoft DNS server uses fixed source port for the queries (so the attacker doesn't need to guess the source port) and usually queries the first nameserver for the domain (so the attacker only has to spoof the replies from one IP address).
In our testing we were able to reliably inject spoofed replies into the cache.
The success of the attack depends on how busy a DNS cache is. If it is performing a lot of queries (using up transaction IDs) the attacker will only see a small fraction of IDs. It will be more difficult for the attacker to figure out the state of the counters and to predict the value of the transaction IDs.
It is commonly believed that if a caching DNS server is behind a firewall and it is not possible to query it from the outside, it would not be possible to perform a cache poisoning attack like the one discussed above. Unfortunately, this is not the case. An attacker can create a web page and entice someone inside the firewall to surf to this page. The page will contain images located at hosts in attacker-controlled domain. For example:
<img src="http://h1.cache-poisoning.net/image.gif"> <img src="http://h2.cache-poisoning.net/image.gif"> ... <img src="http://h100.cache-poisoning.net/image.gif">
When the victim browser's renders the page, it will make DNS queries to the DNS cache. The DNS cache will make queries to the name server for cache-poisoning.net, which is controlled by the attacker. The attacker can observe the transaction IDs used for the queries and predict the next transaction IDs. Adding an image pointing to hotmail.com will make the victim cache query for hotmail.com. The attacker can send a spoofed reply using the guessed value for the transaction ID. This attack only works if the caching Microsoft DNS server does not use a forwarder. If a forwarder is used the attacker will observe the transaction IDs generated by the forwarder.
To demonstrate this kind of attack and to make testing DNS server transaction IDs easier we created a web-based DNS TX ID analyzer (http://www.scanit.be/dns-tx-id-test.html). That web page makes your browser send queries to your DNS server for hosts in cache-poisoning.net domain. Your DNS server will send the queries to our DNS server which is authoritative for cache-poisoning.net domain. Our DNS servers records the transaction IDs that it received and they get displayed back to you by the web page. The page also analyzes the transaction IDs to check if they follow the MS DNS pattern discussed above.
Amit Klein's excellent paper (http://www.trusteer.com/docs/windowsdns.html) discusses the web-based scenario in more detail and also provides the algorithm for predicting the DNS transaction IDs for Microsoft DNS more precisely with only 8 spoofed packets.
Gather a sample of about a hundred DNS transaction IDs generated by an MS DNS server. Feed them to this script: http://www.scanit.be/uploads/analyze_ids.pl. If you get an output looking like this: 12168 : 0 3984 : 1 6044 : 2 12192 : 0 6056 : 2 16308 : 3 16316 : 3 6080 : 2 ... your server generates predictable transaction IDs. If you get output like this: 45087 : 0 65108 : 1 30613 : 2 60689 : 3 58308 : 4 38744 : 5 21461 : 6 51872 : 7 Id out of sequence: 55029 Id out of sequence: 61733 Id out of sequence: 34790 Id out of sequence: 13829 Id out of sequence: 24207 Id out of sequence: 8518 ...
with a lot of lines saying "Id out of sequence", then your server's transaction IDs do not follow MS DNS pattern.
If you get some of the lines saying "Id out of sequence" but not most of them, then your server is probably vulnerable, but is under some load. Try gathering transaction IDs when the server is not handling any other requests.
Alternatively, use use the web-based test to check the transaction IDs of the DNS server your computer is configured to use: http://www.scanit.be/dns-tx-id-test.html.
We have also provided a proof of concept script (http://www.scanit.be/uploads/spoofer-ms.pl) demonstrating DNS cache poisoning. The script has to be run on a server that is authoritative for some zone. The script listens on port 53 UDP, so it will require root privileges to run.
4) Historical Notes
Predictable DNS transaction IDs are a common and rather well researched problem.
It was first noticed that BIND 4.9.6 and below use sequential transaction IDs (http://www.cert.org/advisories/CA-1997-22.html). Microsoft fixed sequential DNS transaction IDs in a post-SP3 hotfix for Windows NT 4.0 (http://support.microsoft.com/kb/167629/EN-US/).
After that a birthday attack against BIND was published by Vagner Sacramento (http://www.rnp.br/cais/alertas/2002/cais-ALR-19112002a.html) again allowing efficient prediction of DNS transaction IDs and cache poisoning. In 2003 Joe Steward published an attack methodology using phase space analysis (http://www.lurhq.com/dnscache.pdf). It allowed predicting the next transaction ID of BIND 8 using the 3 previous values. For BIND 9 about 5000 spoofed packets required to achieve 20% probability of success.
Our approach to predicting MS DNS transaction IDs is different from the birthday attack (we don't need send multiple requests for the host we want to spoof) and different from phase space analysis.
Microsoft has released a patch to correct this problem: Microsoft Security Bulletin MS07-062 (http://www.microsoft.com/technet/security/bulletin/MS07-062.mspx)
6) Time Table
2006/10/24 Vendor was informed 2006/10/26 Vendor confirmed the problem 2007/11/13 Patch is made available by Microsoft 2007/11/14 Scanit publishes the advisory
7) Additional Information
The original advisory can be found here: http://www.scanit.be/advisory-2007-11-14.html
8) About Scanit
Scanit is a security company located in Brussels, Belgium. We specialize in security assessments, offering services such as penetration tests, application source code reviews, and risk assessments. More information can be found at http://www.scanit.be/
Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/