Hole in Bind name server might affect whole Internet

The consequences of the vulnerability in the Bind 9 DNS server is much more serious than one might expect, based on the "medium" severity rating by vendor ISC. Although affected name servers run no immediate risks, users of such servers do. When asked by heise Security, Amit Klein, who has detected this hole, estimates that about half of all name servers run on Bind 9 and that consequently, the latest vulnerability might affect the whole Internet. This means that a significant part of the DNS infrastructure is vulnerable to cache poisioning attacks, which could redirect a large number of unsuspecting users to incorrect IP addresses, including phishing sites.

Johannes Ullrich of the Internet Storm Center also considers this vulnerability a "big deal". He expects that it can take months to immunize the DNS network against this bug, depending on speedy updates being provided by the distributors. Meanwhile, Red Hat, Fedora and Debian have responded and offer upgraded packages of the software.

The primary protection against DNS cache poisoning is that it should be practically impossible to predict the correct 16-bit transaction ID, which could be used to foist on name servers an incorrect IP address for an uncached host name. Since IP and host name are then stored in the cache, a poisoned name server will respond to subsequent queries to the host name with the wrong address. Due to the implementation bug in the random number generator in the old Bind 9 version, transaction IDs which are even numbers are followed by at most ten IDs which can be calculated based on the even-numbered ID.

A method known as CNAME chaining allows attackers to determine a specific transaction ID quite quickly and efficiently. The attacker queries the name server to be poisoned for the IP address of a host name in a domain that is resolved by a DNS server under his control. The attacker's authorative DNS server receives a query including transaction ID from the target DNS server. If this ID is uneven, a response is sent that the queried host name is only an alias (CNAME) for another host in the attacker's domain. This will automatically generate another query with a new ID in the attacked DNS server.

This game is repeated until the attacking server receives a suitable ID. After having received an even transaction ID, speed is important, since the target server must be poisoned before it processes any other queries. According to Ullrich, this complicates attacks on DNS servers with a high workload, but will not prevent them.

To protect servers against such attacks, users are advised to upgrade to the new version. Potential workarounds for DNS servers that cannot be updated at present have certain disadvantages. The most viable option is to set up internal DNS servers as forwarders, which only send queries to a (preferably patched) master DNS server, managed, for instance, by a service provider. This will, however, increase latency for name resolutions, that are not in the cache. Switching off the caching, as to have nothing to poison, is not an option in most cases for performance reasons.

The vulnerability results from a gross implementation error. Bind 9 uses a Bilateral Stop/Go LFSR Generator (one of the family of linear feedback shift registers based on the exclusive OR function) as its pseudo random number generator. However, instead of using only the lowest bit of the XOR of its two 32-bit state registers, as is common practice, the developers used 16 bits as the transaction ID; consequently, the DNS server discloses a large part of the state of its internal random number generator with each transaction ID. The special thing about even transaction IDs is that, with this generator, the values of the next transaction ID value can be predicted. Instead of having 16 bits of randomness, which yields some 65000 possible IDs, the randomness breaks down to a mere 10 different possible values.

Considering the critical importance of the Internet, realizing that the software that is deemed the foundation of the Internet struggles with such major quality problems gives one the creeps. No wonder that vendor ISC remains silent and is not responding to questions on this issue. Interestingly, the OpenBSD project, which explicitly focuses on security, chose a different path and already addressed the issue ten years ago. According to it's lead developer Theo De Raadt, the OpenBSD Bind was patched in 1997 during the migration to version 9, to use a Linear Congruential Generator (LCG) for its transaction IDs, which are not vulnerable to the attack. De Raadt also claims that back then there were discussions with the Bind developers, on the questionable security of their LFSR implementation, but "they did not listen".