Cache poisoning vulnerability found in BIND

Domain Name System (DNS) cache poisoning has been a problem, on and off, for years. There has been a kind of an arms race with security researchers periodically finding problems in DNS server implementations and the vendors racing to fix them. Amit Klein of Trusteer recently released a vulnerability report for the Berkeley Internet Name Daemon (BIND) showing a rather reliable means to poison the cache of a nameserver that runs it. The consequences of this poisoning can be quite severe, invisibly rerouting traffic bound for a given host to one under an attacker's control.

We will dispense with the usual overview of DNS, it was briefly described in an April LWN article - the vulnerability executive summary and Wikipedia article have useful descriptions as well.

There are essentially two types of DNS servers: those that directly reply to queries about a particular zone (zone servers) and those that cache query results (caching servers). An internet service provider or company will typically set up a few caching DNS servers that actually talk to the zone servers, and configure all client machines to make their DNS requests to the caching servers. Once an entry has been entered into the cache of those servers, it will not be requested again until the time-to-live (TTL) of the entry expires. If an attacker can get an incorrect entry put into the cache, especially one with a very long TTL, he can redirect traffic to servers under his control. This is the "poison" in the cache.

DNS uses User Datagram Protocol (UDP), which is stateless rather than connection-oriented. This allows attackers to send "answers" to DNS queries that they never received. They can forge the IP address of the nameserver that would be queried; if the bogus response is received before the real response, it will be used and the real one dropped. Several steps are taken to make it more difficult for an attacker to forge a response, but one of those countermeasures was not correctly implemented in BIND, leading to this most recent vulnerability.

The DNS protocol contains a 16-bit transaction ID field that must be matched between the query and the response in order to be considered valid. Early DNS implementations just incremented those transaction IDs for each new query, making it trivial for an attacker's program to predict which was coming next. The obvious fix is to randomize the transaction IDs, which is exactly what BIND did, unfortunately not quite as randomly as they might have hoped.

Random number generation (RNG) is one of those things that seems like it should be blindingly simple, but turns out to be incredibly difficult to do correctly. For things like games or simulations, it is relatively straightforward to create an RNG with reasonable properties, but for security and cryptography, it is much more difficult. One of the key properties that a crypto-strength RNG must have is unpredictability. One way to look at that is to determine how much RNG output an attacker must see before they can make informed guesses about the next "random" number. This is where the BIND algorithm was found to be lacking.

By studying the code used to generate the transaction IDs, Klein noticed that if the transaction ID was even (least significant bit was zero), there were only ten possible values that could be generated as the next transaction ID. Other techniques had been able to reduce the search space to around 5000 possibilities, but forging and sending that many bogus DNS responses before the real reply reaches the recipient is not a very reliable poisoning technique. With only ten responses to send, it is quite possible to get the bogus response there first, especially if the real DNS server is busy and responds a little slowly.

If an attacker (at attacker.com) wanted to poison the cache entry of financial-site.com for the users at randomisp.com, they would need to lure a user of randomisp.com's caching DNS server to visit attacker.com. When the DNS server at randomisp.com queries the attacker.com DNS server, that server looks at the transaction ID, if it is odd, it sends back a redirection to itself (using a DNS feature called CNAME chaining). If the transaction ID is even, it quickly calculates the ten possible values for the next transaction ID and starts sending responses for financial-site.com using those IDs. In addition, it redirects the query to financial-site.com. If that site is not in the cache, or its cache entry has expired, randomisp.com's DNS server will make a query, probably using one of the ten transaction IDs (unless an intervening query has gone out), to financial-site.com. It is very likely that one of the bogus responses will be picked up and the attacker now controls the mapping of financial-site.com to an IP address, for all users of randomisp.com.

Normally, the invitation to visit attacker.com would go out as spam or by some other means that tricks users into going places that they probably should not. No particular ISP is targeted, the poisoning is used as part of a pharming attack. Pharming is typically used to get credentials, usernames and passwords, for financial and other sites by spoofing a well-known website on an attacker's server. Because of the cache poisoning, the user could use a bookmark or even type in the financial-site.com address, but still end up at the attacker's site. The website graphics and login process are duplicated there which causes the user (or his browser's password manager) to type in the credentials and hit submit.

The full report makes for quite an interesting read. Klein describes several other means of attack and weaknesses in the BIND RNG, including ways to completely recover the internal state of the RNG. Internet Systems Consortium (ISC), the maintainers of BIND have released an updated version, with a new RNG, though there was very little description of the problem or the fix in their advisory. The problem has been assigned CVE-2007-2926 but, as of this writing, that is just a placeholder.

This is quite a serious vulnerability and should be rather embarrassing to the folks at ISC. The problems with transaction IDs and the need for their unpredictability have been known for many years. It is not at all beyond the realm of possibility that the analysis done by Klein, was done by the attacker community some time ago, and has been used already. Widespread usage would likely have been detected, but if used judiciously, it could have been exploited for quite some time.

Another technique that could help avoid these kinds of attacks would be to randomize (crypto-strength RNG, of course) the source UDP port on each query. BIND currently chooses a single random UDP source port at startup time and uses that throughout its life. If an attacker could not predict the port to send a bogus response to, it almost would not matter that they could predict what response to send.