Thread-topic: Predictable DNS transaction IDs in Microsoft DNS Server
> -----Original Message-----
> From: full-disclosure-bounces@xxxxxxxxxxxxxxxxx
> [mailto:full-disclosure-bounces@xxxxxxxxxxxxxxxxx] On Behalf
> Of Alla Bezroutchko
> Sent: Wednesday, November 14, 2007 3:07 PM
> To: bugtraq@xxxxxxxxxxxxxxxxx; full-disclosure@xxxxxxxxxxxxxxxxx
> Subject: [Full-disclosure] 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:
>
> <img src=";>
> <img src=";>
> ...
> <img src=";>
>
> 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
> (). 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
> () 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:
> . 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:
> .
>
> We have also provided a proof of concept script
> () 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 ().
> Microsoft fixed sequential DNS transaction IDs in a post-SP3
> hotfix for
> Windows NT 4.0 ().
>
> After that a birthday attack against BIND was published by Vagner
> Sacramento
> ()
> again allowing efficient prediction of DNS transaction IDs and cache
> poisoning. In 2003 Joe Steward published an attack methodology using
> phase space analysis (). 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
> ()
>
> 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:
>
>
> 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
>
> _______________________________________________
> Full-Disclosure - We believe in it.
> Charter:
> Hosted and sponsored by Secunia -
>
