Poison That Cache!

By Sarah Jacobus –

Introduction:

DNS (Domain Name System) is an essential part of the internet, and is therefore subject to a wide variety of attacks. This article will focus on one of the many attacks that can target DNS: Cache Poisoning. I will discuss two types of Cache Poisoning attacks – one that targets DNS and one that targets HTTP.

What is Cache Poisoning?

Cache is where a computer stores frequently accessed information.

Where a human can remember certain pieces of useful information, a computer stores material into its cache. Like most of us, a computer does not remember everything forever; there is a time limit on how long a computer stores information in its cache. If cache equates to memory, then Cache Poisoning is the process of making the computer remember something incorrectly.

Let’s use your cell phone as an example. When you want to call your mother, how do you do this? You probably go into your phone’s contacts and click the contact name “mom” instead of dialing her number directly (because who remembers that, anyway?).

Now let’s say you have a mean friend who is trying to pull a prank on you. When you’re not looking, your friend takes your phone and goes to edit your “mom” contact. He changes the phone number to be his phone number instead of your mom’s phone number.

So, that night when you’re running late for dinner and you go to call your mom to tell her, you go into your contacts and click on her name. You think you are dialing your moms number but in reality, you are calling your friend.

Web Cache Poisoning

Web Cache Poisoning is achieved through HTTP Request Smuggling (HRS). The idea here is to make a user go to a certain webpage (say google.com) and have the cache store or ‘remember’ a malicious website behind the scenes. When you go back to google.com it will actually go to the attacker’s malicious web page.

When you send an HTTP request, your computer will resolve the request and you will be directed to the webpage. This is how it should work, and how HTTP operates. When trying to poison the web cache however, we are going to send two requests within one HTTP request by playing around with the content length. Your computer will send you to the website outlined in the first request (as it should), but your cache will store the website outlined in the second request. This is where the problem lies, since you will be going to one site but remembering a completely different one.
*Note! This attack does not work with all web browsers/servers.

1x

Figure 1: Web Cache script

From the script in Figure 1, the Content Length of 0 is going to direct you to the malicious site while the Content Length of 44 is going to direct you towards the vulnerable site. If executed, this script will have your computer resolve the vulnerable_site but cache the malicious_site.

 

Birthday Attack

(*Warning, this attack involves math!)

If you are in a room with N number of people, what are the odds that one randomly selected person will have the same birthday as you?

 

This logic is applied to attacking vulnerable name servers. Using BIND, and attacker is able to send false resolutions to a name server in order to poison a user’s cache.

The major concern with an attack like this is the fact that once one client’s cache is poisoned, it can spread to any computer that contacts the vulnerable DNS server.

How does this work, you ask? An attacker can make requests to the vulnerable name server and then reply to that request with false information.

2x

Figure 2: Birthday Attack 

The “Birthday” math comes in when you consider that BIND allows simultaneous requests for the same name. In order to have a false response accepted, the attacker must guess the 16-bit unique identifier chosen by the user. Since a 16-bit ID can have at most 65,536 unique values, the attacker would have to send N recursive requests for the same domain and N replies with random identifiers.

 

The formula used to test the probability for such an attack is as follows:

Probability of collision =  1 – (1- 1/t)^(n*(n-1)/2)

Where N is the number of requests/responses the attack would send.

 

Based on this math, we can expect there to be a 50% chance of a collision after about 280 queries. (sqrt(65536))

To successfully perform this attack, you must generate enough equal false requests and replies to a vulnerable name server. When distributing domains, BIND will generate multiple of the same replies as the same time.
Mitigations:
Web Cache Poisoning:

Since Web Cache Poisoning is a form of HTTP Request Smuggling, in order to prevent such attacks from happening it is important to look into several of these options:

  • Use HTTPS instead of HTTP
    • Make sites un-cachable
  • Use web servers that have a better HTTP parsing method (IIS, Apache)

 

DNS Cache Poisoning (Birthday attack):

  • Check Validity
    • Check the validity of response packets to avoid false responses to false queries
  • Remove duplicate queries

 

Conclusion

There are many ways to go about poisoning a computer’s cache. DNS cache poisoning is one of the most popular, as it can be widely spread. The HRS Web Cache Poisoning example outlined in this post assumes you are using a web server like SunONE, because other web servers like Apache and IIS have protected themselves against these types of attacks. The Birthday Attack is by far more complex, and requires a fair amount of brute-forcing and guessing on the attacker’s part. If successful however, it can be spread to more than one computer.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s