What is Cache Poisoning?

9 October 2019

EfficientIP

DNS cache poisoning is a DNS attack that installs a specific incorrect record in the cache of a recursive DNS server. Any client requesting this information from this recursive server will then get the wrong answer. This attack is mainly used to direct user browsers to a fake server in order to perform phishing or extortion. The main targets are well known online services like bank, insurance and government.

How to perform a DNS cache poisoning attack?

The main idea behind the attack is to imitate an answer from server upper in the DNS hierarchy and provide fake content. This attack takes advantage of the fact DNS service uses the UDP protocol and accepts an answer as soon as the returning packet contains the appropriate technical information (source and destination port and same transaction identifier). The DNS protocol has been defined to be transported on top of UDP from the very beginning and since it was easy to implement, most DNS servers are using this non connected transport protocol. Unfortunately, this also allows cache poisoning attacks. But as new DNS implementations are using TCP, this attack would be far more complex to carry out.

1- performing the DNS query

In order to populate the cache with fake information, the attacker should perform a request to the recursive server. Either the recursive server is open to all requests or the attacker is authorized. When the attacker is not authorized at the DNS level, he may use another service which can perform the request on his behalf, such as a web server or a mail server.

2- providing fake answers

Once the query hits the recursive server, if the answer is not in its cache, the query is sent towards an upper DNS server. It is now time for the attacker to flood the attacked DNS server with fake answers. Two main criteria must be met during this flood:

  • the UDP port of the answer should match the one used in the query. On earlier TCP/IP implementation the entropy in the port number generation was very low, meaning the answer was easier to predict
  • The DNS identifier of the answer should match the query. This number is encoded using a 16 bit value, which is insufficient for effectively protecting the transaction. In the past it occurred that the entropy of the random number generator was not high enough. Today, it is difficult to predict the next value output from a random generator. With a high entropy on the ID number, the birthday paradox helps understand that collision may occur with a relatively low number of fake answers. It is then possible to push enough DNS answer packets to the attacked DNS server with different values of the ID. Even with the 16 bit encoding number (65 536 possibilities), the probability to blindly push the same identifier is evaluated at 302 frames for 50%, 560 frames for 90% and 776 frames for 99%.

If the answer matches the criteria (ports, id, …) it is accepted and populates the cache of the recursive server. Any further request for this FQDN on the recursive server will be answered with the information present in the cache allowing the attacker to capture the traffic.

3- adding a record in the answer

The DNS protocol authorizes multiple queries and answers in the same packet. The Eugene Kashpureff’s attack uses this feature to add specific records in the answer of a legitimate query in order to populate the cache of recursive DNS servers. This attack is really easy to perform. The attacker just needs to own a DNS server on a domain and propose some content requiring readers to perform a query on it. If the DNS recursive server is not verifying answers and the query is matching, the cache is populated and spoofing can occur.

How to protect from DNS cache poisoning?

  • Randomness of UDP source port: check entropy of the system hosting the recursive DNS server for maximum UDP port generation entropy. It could also be interesting to check if this entropy is conserved when crossing a NAT/PAT device like a perimeter firewall that may change the UDP port.
  • Multiple records: validate answers with request, only insert in the cache the answer that matches
  • Query ID: validate randomness
  • Use TCP for recursion to upper DNS server
  • Apply strict patch management on your DNS infrastructure, DNS software is evolving quickly, most of the time to correct bugs
  • Use DNS cookies (see RFC7873) to identify each single transaction without any impact from NAT or anycast

The most advanced solution is to implement DNSSEC everywhere, whereby records are signed with digital certificate and public key mechanism making it is mathematically impossible to usurp (for now). This is really complex and requires that all the domain owners and DNS infrastructure services are compliant.

Annex: birthday paradigm calculator

Here is a small piece of python code to calculate the probability of collision on the 16 bits identifier used in DNS queries for probabilities of 50%, 90% and 99%.

from scipy import log, exp
from scipy.special import gammaln as gln


def prob_unique(days, persons):
	"""returns the probability of x persons sharing the same birthday over
   	a year of y days"""
	return exp(gln(days+1) - gln(days-persons+1) - persons*log(days))


for pers in (302, 550, 776):
	prob = (1 - prob_unique(65536, pers)) * 100
	print("65535 days / {} persons: prob = {:.2f}%".format(pers, prob))