Details of the DNS flaw revealed

Dan Kaminsky spoke to a packed house at Black Hat on 6 August to outline the fundamental flaw he found in the Domain Name System (DNS). Contrary to his hopes, though, the flaw was discovered and publicized before his presentation. The vulnerability is interesting in its own right, but the implications of what can be done with it are staggering. In addition, the "fix" has well understood shortcomings that can still potentially be exploited to poison DNS caches.

We reported on the vulnerability in early July, including Kaminsky's request that security folks not publicly speculate about the flaw. As one might guess, that request was largely ignored. When security researcher Halvar Flake published his speculation, another researcher, who was known to have the details of the flaw, publicly confirmed it, but just as quickly removed the confirmation. While it sounds a bit like a security community soap opera, it was fairly clearly caused by the attempt to contain the vulnerability information.

An important part of DNS is the ability to delegate to another nameserver. When looking up example.net, first one of the root nameservers is consulted; it does not know the answer so it delegates to one of the nameservers that handles .net addresses. The delegation response includes the names of the servers being delegated to, but also helpfully includes the IP address of those servers as well. It is this helpful addition, which is meant to reduce DNS traffic, that can be exploited.

The key to DNS cache poisoning is that the first good answer wins. If an attacker can send a packet with all of the proper information, but with his own IP address substituted for the correct one, and that packet reaches the querying server first, the attacker wins. In order for that to happen, the attacker needs to arrange or know that the victim will be making a particular query as well as be able to create a response that will be considered "good".

Each DNS query has a 16-bit transaction ID; early implementations just had an incrementing counter, but since that time random transaction IDs have been used. In order for a DNS response to be accepted, it must have the same transaction ID as the request. Just over a year ago, we wrote about a cache poisoning vulnerability in BIND that was caused by a predictable random number generator. When an attacker can narrow down the possible values for transaction IDs, it reduces the number of responses they must generate commensurately.

Absent any method to predict transaction IDs, an attacker must send 32K responses on average before the correct response arrives—which is difficult, at best, to do. If the attacker can cause the victim to make multiple requests, though, they can increase their chances. Because DNS servers cache the results of their queries, repeated requests for the same host information will not generate additional lookups.

Kaminsky observed that if you make the victim request information about multiple, probably non-existent names in a domain, it will have to make a request to the nameserver responsible for that domain multiple times. If the victim queries for foo1.example.net, foo2.example.net, etc., it will use a different, random transaction ID for each request. The attacker can flood the victim with packets purporting to delegate the request to another server, ns.example.net say, but include an IP address under its control as the IP for that server.

The net result is that if one of the attacker's responses gets accepted, because it finally guessed the right transaction ID, the victim's nameserver cache has been poisoned. The attacker can control all lookups in the entire example.net domain because it has substituted its own server as the nameserver for that domain. Because of the birthday paradox, the attacker does not need to generate anywhere near 32K responses to have a high probability of having one with a correct transaction ID. In his testing, Kaminsky found that he could poison a cache like this in less than 10 seconds.

This technique works all the way up the hierarchy of DNS servers, potentially allowing top-level-domain or root nameservers to be poisoned. It is clearly a very serious flaw that can be exploited in a huge number of ways. Kaminsky's Black Hat slides [Powerpoint format, but viewable in OpenOffice], detail many different implications and are well worth a read. Also, for an excellent description of how DNS works as well as more details on the flaw Kaminsky found, see Steve Friedl's illustrated guide.

The "fix" that was rolled out in a coordinated fashion by many different vendors is to randomize the source UDP port for each query. This is a technique that was implemented years ago in Daniel Bernstein's djbdns and has been recommended by various cache poisoning researchers (notably Amit Klein) for some time. By doing this, an attacker must also guess the proper UDP port to send the response to, which can provide up to an additional 16 bits of randomness to the query. In the best case, where all possible UDP source ports are used, that increases the number of possible responses from 64K to over 4 billion.

That seems like it would take the attack out of the realm of possibility, but that clearly isn't the case. Kaminsky and the vendors all knew that adding source port randomization only made it harder—not impossible. Linux kernel hacker Evgeniy Polyakov has done some experiments with the patched version of BIND on a gigabit ethernet LAN, finding that he could poison a cache in under ten hours. As he points out: "So, if you have a GigE lan, any trojaned machine can poison your DNS during one night."

Other solutions are actively being sought, but it is a difficult problem because backward compatibility with countless DNS installations needs to be maintained. As always when a DNS problem is publicized, DNSSEC is touted as the solution. There are numerous technical and political problems that have stood in the way of DNSSEC adoption; those seem unlikely to just disappear.

This DNS flaw is serious, but there are plenty of serious internet security issues as Kaminsky points out in his blog:

While there may be bigger problems in our internet infrastructure, there are few things that are as pervasive as DNS. Kaminsky points out a number of non-obvious places where it is used—and could be abused—such as mailer lookups of HELO strings to try and decide whether to accept email or web servers doing reverse lookups for logfile messages. It is a little surprising that something so integral had such an obvious, in retrospect, flaw in its design that went undetected for around 25 years. It makes one wonder what else is lurking out there.