Cache poisoning vulnerability found in BIND [LWN.net]

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.

(Log in to post comments)

Cache poisoning vulnerability found in BIND

Posted Jul 26, 2007 2:15 UTC (Thu) by elanthis (guest, #6227) [Link]

Fortunately, SSL solves this problem for secure sites. Even if you end up at the attacker's site, you will get an invalid cert warning.

One of the things IE7 does far, far better than Firefox is the invalid SSL cert dialog. On Firefox, you get a popup. Users just hit OK. On IE7, you get a big huge scary warning page that makes it very clear something is wrong.

One of our support guys asked me the other day what the weird popup he was getting was all about. He'd been getting it for a few weeks, but had always hit OK and never bothered reading it. He got a phone call from a user on IE7 who was freaking out about a funny page that always came up before the site that said his site was insecure and broken. The SSL cert on the client's site had expired. Our relatively experience tech hadn't realized because he, like 99% of users, ignore popups and hit OK, where-as the client on IE7 was given a very visible and difficult to ignore warning.

Firefox should be doing the same thing as IE7. I'd go so far as to say that it should even just refuse to access sites with invalid SSL certs unless the user manually adds it to a white-list, and even then it should give the IE7 warning. The only reason you should ever have to use an invalid cert is for testing, and if you're just testing you can put up with the hassle.

Cache poisoning vulnerability found in BIND

Posted Jul 26, 2007 13:13 UTC (Thu) by nix (subscriber, #2304) [Link]

SSL solves it? Not hardly, given that huge numbers of sites use outdated certs and a lot use self-signing. Most people just click 'accept' when asked: they certainly don't look at the cert's content, and even if they did, would they be able to spot a false one, what with VeriSign and others doing minimal verification of applicant identity beyond `do they have a credit card'. (Credit cards are, after all, so very had to get: my friend's daughter could have half a dozen by now, and she's less than a year old).

Cache poisoning vulnerability found in BIND

Posted Jul 26, 2007 13:15 UTC (Thu) by tialaramex (subscriber, #21167) [Link]

Ah, you're not thinking like a security professional.

Suppose we make it so that _invalid_ certificates just don't work

Attackers may be able to obtain an _expired_ certificate, but that's OK we'll make sure those don't work either.

Or they can create a _self-signed_ certificate just as easily. Maybe we should make those not work?

At this point users will refuse to use your browser, because lots of sites that are concerned about snooping, but not about impersonation, use SSL with certificates that are self-signed (or signed by an unknown CA) to avoid the high cost of a "real" SSL certificate. Users will go to great lengths to bypass security that they regard as excessive or unwieldy.

Since, to an attacker, invalid and self-signed certificates are just as easy to make / obtain, there is no point to what IE did here AFAICT.

Cache poisoning vulnerability found in BIND

Posted Jul 29, 2007 23:49 UTC (Sun) by dlang (✭ supporter ✭, #313) [Link]

as for avoiding the "high cost of 'real' SSL certs", they are only really expensive if you buy them from the wrong place. you can get 'real' ssl certs for <$100 individually, and if you are a company that needs a lot of them you can get them in quantity for <$50 (you also don't have to get certs that expire after one year either)

the fact that some people think it's necessary to pay $900 per year for a cert is a testimate to stupidity and marketing.

and frankly if you consider $50 or $100 too expensive then I question if what you are protecting is worth bothering with SSL in the first place.

Self signed certs are not a problem if you use them properly and have the users tell their browsers to install it as a valid cert, but just using them without giving the users a way to do this and expecting them to click through the cert warning is bad for everyone and provides little security to your users.

SSL Certificate costs...

Posted Jul 30, 2007 15:28 UTC (Mon) by cdmiller (subscriber, #2813) [Link]

If you have 50 FQDN's that need SSL, your looking at a $2500 - $5000 per year expense. Is that a lot to pay given the questionable trustworthiness of the major cert vendors, and the ease of generating a self signed certificate? For $5000 one can easily find hardware capable of hosting 50 domains, an additional $5k can make this redundant, so the current cost of a "browser approved" SSL cert is exorbitant in many situations.

Cache poisoning vulnerability found in BIND

Posted Jul 31, 2007 11:26 UTC (Tue) by cortana (subscriber, #24596) [Link]

... lots of sites that are concerned about snooping, but not about impersonation, use SSL with certificates that are self-signed (or signed by an unknown CA) to avoid the high cost of a "real" SSL certificate.

But the assurance that one is not being snooped strictly requires the assurance that one is not being impersonated.

Cache poisoning vulnerability found in BIND

Posted Jul 31, 2007 16:02 UTC (Tue) by zlynx (subscriber, #2285) [Link]

Using a self-signed SSL cert still raises the bar considerably. Especially if you immediately save it in your cert DB. Just like using SSH and saving the remote system key for the first time.

SSL doesn't solve everything

Posted Jul 31, 2007 16:17 UTC (Tue) by kevinbsmith (guest, #4778) [Link]

SSL doesn't quite solve the problem for "normal" end-users. How many people bother to type in https when they go to paypal (or ebay, or their bank)? Most just navigate to the non-SSL site, which automatically redirects them to the SSL version.

The attacker can redirect them to a non-SSL site that looks like the real SSL site, or to an SSL site with a different domain and therefore a valid cert.

Bookmarks (to the SSL site) can avoid that problem, but users won't always use their bookmarks.

Cache poisoning vulnerability found in BIND

Posted Jul 26, 2007 4:49 UTC (Thu) by flewellyn (subscriber, #5047) [Link]

No, the only thing that would matter to the firewall is the destination port, which, since DNS is a
Well Known Service, is always the same. The source port for the querying machine could be
anything; unless the firewall is configured to block outgoing ports, which is just silly, the DNS
server can respond on any port. If the port in question is randomized for each query, it makes
no difference.

Cache poisoning vulnerability found in BIND

Posted Jul 26, 2007 14:36 UTC (Thu) by jond (subscriber, #37669) [Link]

Isn't relying on an unpredictable source port a bit like relying on the current PID as an unguessable number? I.e. couldn't an attacker just forge 65,000-odd UDP packets, one per possible source address?

Cache poisoning vulnerability found in BIND

Posted Jul 26, 2007 19:06 UTC (Thu) by flewellyn (subscriber, #5047) [Link]

Not in a time-sensitive exploit like this one. Remember, cache-poisoning only works if the attacker's phony DNS reply can reach the querying machine prior to the legitimate one.