Securebits Blog

Recently, a DNS implementation vulnerability has been discovered. Exploiting this vulnerability is a new clever way to do the old known attack, DNS Cache Poisoning. The credit goes to security researcher Dan Kaminsky who discovered the bug, demonstrated the exploit to a closed circle of professionals, and worked with some others to push vendors to release patches for their products. Although Dan has not disclosed the detail of the bug or the actual exploitation, the well-known reverse engineer Halvar Flake made a random speculation, according to him, about the bug which in fact turned out to be the actual description of the bug.

DNS Overview:
DNS is one of the essential protocols of the Internet. It is the protocol responsible for translating hostnames (e.g. www.securebits.org) to IP Addresses (e.g. 209.59.173.201). People can memorize ‘names’ but not IP Addresses while machines communicate using IP Addresses. DNS resolves the ‘name’ a person wants to use or access to an IP Address used by the machine to grant such access. DNS is a hierarchical protocol. Each domain holds the DNS records for the subdomains/servers directly under it. For example, “.com” domain DNS holds records that point to every domain under “.com”; it holds a record that says “microsoft.com” can be found at such DNS server, while “microsoft.com” domain DNS holds records about its servers and subdomains. The root of the DNS hierarchy is represented by “.” and it is composed of multiple known servers scattered worldwide.

When a client wants to resolve a name, it sends a DNS query to the DNS server; the DNS server IP address is already configured on the client machine, and thus, the client forwards all its DNS queries to that DNS server. The DNS server then looks at the query and sees if the name to be resolved is part of the record set the server is responsible for. If so, the server replies with the IP address. In this case, the DNS server is the authoritative server for this name. If the server is not the authoritative server for that name, the DNS server does a recursive query on the Internet; however, to do a recursive query, the server must be configured to allow DNS recursion. To do a recursive query for “www.securebits.org”, the server first asks the root DNS servers, i.e. “.”, about the Name Server(s) of “.org” domain. After getting the answer, the server asks “.org” about the Name Server(s) of “.securebits.org” domain. Finally after getting the answer, the server asks “.securebits.org” about the hostname “www.securebits.org”

An important field in the DNS header is called “Transaction ID” (TXID). It is meant to keep track of which reply corresponds to which query. It is a 16 Bit value and it is unique for every query. The reply has to have the same value; otherwise, the server will drop it.

Traditional DNS Attacks:
DNS attacks are centered on one thing: DNS cache poisoning. And the core of this attack is a successful guess of the TXID. Meaning, in order to successfully poison the DNS cache of a remote system, an attacker has to generate a fake DNS reply with the exact TXID of the query generated by the remote system. Another important factor is that the fake reply must reach the remote system before the legitimate reply. An example of this would be the following: let’s say system “A” wants resolve “www.securebits.org”, it sends a query to the forwarder DNS asking for the IP Address of “www.securebits.org” and such query holds an XTID, let’s say, 0xABCD. So, in order to poison the cache, an attacker needs to fake a reply that maps the name “www.securebits.org” to an IP address under his control, and such fake reply must also have the XTID 0xABCD. Also, the fake reply must arrive at system “A” before the legitimate answer arrives.

Originally, the TXIDs were sequentially incremented. Meaning, if the system sends a query with TXID 0x1111, the next query with have TXID 0x1112, and the third is 0x1113 and so on. Poisoning was quite easy. The attacker first sends a recursive query to the DNS server to find out the IP address of a name that is under the control of the attacker. The attacker knows the current TXID. After that, the attacker sends another recursive query to the DNS server, to be poisoned, asking to resolve a name which the attacker wants to fake its IP address. The attacker sends directly a fake reply with TXID + 1. If TXID + 1 was already used by the server, the attacker tries TXID+2, TXID+3, etc and eventually with catch the correct TXID.

To fix this problem, randomized TXIDs were used. Numbers are no longer in sequence. Some DNS implementations used a weak random number generator, a generator with a fixed sequence of randomization. Attacks against such DNS servers were trivial; an attacker would issue multiple recursive queries asking for IP addresses of names under his control, he collects TXIDs received and predict the sequence of randomization. The rest of the attack would be similar to the previous one but instead of sending incremented-by-one TXIDs, the attacker sends TXIDs predicted in the randomization. To solve this problem, all DNS servers implemented strong random number generator that is hard for someone else to predict the sequence.

It worth mentioning that the DNS reply contains a Time-to-Live (TTL) value which states how long the DNS server (the querying server) should cache the DNS entry (hostname-ip). As long as the TTL has not expired, the DNS server will look up the name from the cache. So, if the attacker wins in predicting the TXID and sends the fake reply before the legitimate reply, he wins the advantage of deciding how long such DNS entry will remain in the cache of the poisoned DNS server.

Modern DNS Attacks:
Couple of years ago, a new type of DNS cache poisoning attack surfaced, it is called ‘birthday attack’. Joe Stewart has written about it in "DNS Cache Poisoning - The Next Generation". This attack exploits the behavior that many DNS implementations would send multiple queries with unique TXID to resolve the same domain/host name. For example, if a user sends 10 DNS recursive queries at once to a DNS server asking to resolve the same hostname (e.g. www.securebits.org), the DNS server would send 10 queries to resolve the same name; such queries would be sent if the DNS server has not got a reply to the first query. Exploiting this implementation bug is like this: an attacker sends N queries along with N fake replies. According to the “Birthday” statistics, N can be a comparatively small number, like 700 packets for around 100% success, or 300 packets for around 50% success ratio.