[dns-operations] Predictable DNS transaction IDs in Microsoft DNS Server (fwd)

Wed Nov 14 21:42:33 UTC 2007

---------- Forwarded message ----------
Date: Wed, 14 Nov 2007 13:07:28 +0100
From: Alla Bezroutchko <alla at scanit.be>
To: bugtraq at securityfocus.com, full-disclosure at lists.grok.org.uk
Subject: Predictable DNS transaction IDs in Microsoft DNS Server

1) Summary

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:

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.

3) Verification

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.

5) Solution

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/