Introduction
The old problem of DNS cache poisoning has again reared its ugly head. While some would argue that the domain name system protocol is inherently vulnerable to this style of attack due to the weakness of 16-bit transaction IDs, we cannot ignore the immediate threat while waiting for something better to come along. There are new attacks, which make DNS cache poisoning trivial to execute against a large number of nameservers running today. The purpose of this article is to shed light on these new attacks and recommend ways to defend against them.

A Brief History of Cache Poisoning
In 1993, Christoph Schuba released a paper entitled "Addressing Weaknesses in the Domain Name System Protocol". In it, he outlined several vulnerabilities, including the technique of DNS cache poisoning. In the earliest incarnation, it was possible to provide extra information in a DNS reply packet that would be cached by the daemon. This allowed an attacker to inject false information into the DNS cache for a network, allowing them to perform man-in-the-middle attacks or other mayhem.

In 1997, CERT released advisory CA-1997-22, describing a vulnerability in BIND, the Berkeley Internet Name Domain software which is used by nearly all of the nameservers on the Internet. This time a very basic principle was finally realized: BIND did not randomize its transaction IDs - they were purely sequential. Aside from layer 3 and 4 protocol checking (source and destination IP addresses and ports must match), the transaction ID is the sole form of authentication for a DNS reply. Because an attacker could easily predict the next transaction ID after making their own request, a cache poisoning attack could be carried out using a spoofed query followed by a spoofed answer. To solve this, all new versions of BIND were updated to use randomized transaction IDs.

In 2002, Vagner Sacramento released an advisory showing another problem with BIND's implementation of the DNS protocol. He found that BIND would send multiple simultaneous recursive queries for the same IP address. Because of this a mathematical phenomenon comes into play known as the "Birthday Paradox". This causes the probability of a successful attack to rise to near 100% with only a few hundred packets instead of the tens of thousands previously believed to be needed.

While researching Sacramento's findings, the CERT team also realized there might be another attack possible, based on the work of Michal Zalewski in the area of TCP sequence numbers and phase space analysis of the psuedo-random number generators used by different operating systems to generate them. Zalewski found that using a certain type of analysis it was often trivial to guess the next sequence number in certain implementations. The CERT team felt that this might also apply to the random number generators in BIND. This article will attempt to show that their assumption was correct.