Kara & Michael’s Blog

Warning: Geekery.

Also, an update (7/25): I was concerned when I initally posted this that what I describe as the last portion of my hypothetical attack (taking over as the authoritative NS for an entire domain) would not be possible. The most recent exploit for this vulnerability, published today, appears to do exactly this. At the same time, new reports indicate that only about half of DNS traffic appears to be coming from patched resolvers. Scary. You can check whether your ISP is affected by this issue at Dan Kaminsky’s site. If you are a home user and your ISP has not properly patched, consider OpenDNS. You are also invited to use 4d2.org (75.127.97.20) for your DNS resolution. We’re running djbdns and are not affected by this vulnerability. In addition, unlike OpenDNS, I don’t give a rat’s posterior what sites you’re visiting.

There’s been a lot of talk over the last few weeks, or at least there has been in the online circles I frequent, about a problem with the DNS system discovered by noted security researcher Dan Kaminksy. It’s been described as huge, earth-shattering stuff — stuff that could cause chaos on the Internet if it got into the wrong hands. Details were intentionally withheld from the public and have not yet been formally revealed, to allow software vendors time to release patches. Many people accused Kaminsky of being sensationalist and expressed doubts over the severity of the problem.

Then, two days ago, a modest man who calls himself Halvar Flake did some “speculating” and guessed most of it correctly. This prompted the premature disclosure of further details by another party. By this point the cat was pretty much out of the bag, and as it turns out it really is a huge problem. There’s plenty of technical information out there today. Here I’d like to give what’s hopefully a more “human-readable” description of the problem as well as an explanation of why this matters (and hopefully to show why it’s a pretty cool trick). I’m also going to speculate on some specific elements of a hypothetical attack. Large portions of this may prove to be inaccurate when Kaminsky finally does his disclosure, but I believe this would work as I describe.

First, the basics. DNS, as you are most likely aware if you’ve read this far, is responsible for mapping domain names to IP addresses. Here’s the way a typical DNS transaction might work:

1. I type “www.google.com” into my web browser. My computer doesn’t know the IP address of www.google.com, so it sends the request to the DNS server operated by my ISP.
2. My ISP maintains a cache of recently requested domain names for speedy service. If “www.google.com” is in its cache, it sends me the cached response and the process ends here. Otherwise, it makes a request to another DNS server. If it already knows the address of Google’s DNS server, it might ask that server. For this example, let’s assume that my ISP’s server has no idea where to go and asks one of the “root servers,” which are the points of last resort for a DNS lookup.
3. The root server sends a reply telling my ISP’s DNS server where to go to find information on “www.google.com.” For this example, let’s say that my ISP’s DNS server is instructed to ask “ns1.google.com” (a DNS server operated by Google). For this response to be useful, the root server also has to tell my ISP’s server the IP address of “ns1.google.com.” Remember this point, because it’s important later.
4. My ISP asks ns1.google.com for the address of “www.google.com”, using the IP address it received from the root server. It receives a reply and relays the information to my computer, caching the reply for later use. The amount of time my ISP is allowed to cache the reply is included in the response from Google’s DNS server.
5. My computer now has the IP address it needs to connect to www.google.com, and my web browser loads the page.

Now, what if I’m evil and I want people going to www.google.com to be sent to my evil web server instead of Google’s real web server? I might try to “poison” the DNS cache of a major ISP, say Comcast or Verizon. In other words, if I could get them to store an incorrect IP address for www.google.com, then for some number of hours they would send all of their customers this incorrect address. All of that traffic would come to me instead of Google.

This is what is meant by DNS cache poisoning and it’s been known about for many years. If I wanted to poison some ISP’s DNS cache, the most obvious way for me to do it would be to send that ISP’s DNS server a bunch of fake DNS responses that provide a bad IP address for “www.google.com”. There are some safeguards against this, though:

• The ISP’s DNS server will ignore the information I’m sending unless it has actually requested the IP address of “www.google.com.” If it caches this address for 3 or 6 hours at a time, the chances of me hitting it at the right time are tiny.
• This kind of attack has been imagined for a very long time, so outbound DNS requests all contain a random number, called a TXID. The response has to contain the same number or it will be ignored.

So the chances of me successfully doing any evil in this way are slim to none.

That brings us to subdomains. “google.com”, to use the same example as before, has multiple subdomains — that is to say, “www.google.com” and “mail.google.com” refer to different things. If you try to visit “zyzzybalubah.google.com” in a web browser you’ll get an error, because there is no such subdomain.

It’s important to understand the chain of events that leads to you getting that error. Your computer asks your ISP’s DNS server for the address of “zyzzybalubah.google.com”, your ISP’s server asks Google’s DNS server (possibly having to ask another source for the IP address of Google’s DNS server first), and Google’s DNS server replies that there is no such subdomain.

Time again for hypothetical evil. Assume for a moment that I have a domain (like 4d2.org), a web server and a DNS server — the DNS server being responsible for giving out the IP address for my domain, like ns1.google.com in the example transaction at the beginning of this article. This is a pretty typical setup. Let’s say I create an evil website that makes your web browser try to load some content (an image or some such) from a subdomain of my domain. It’s important that the subdomain be unique, randomly generated gibberish — let’s say it’s “ndxuhf.4d2.org.” So, for example, my webpage would instruct your browser to load http://ndxuhf.4d2.org/awesomepicture.jpg. Since the subdomain is unique, my evil web server knows that your computer is the only one looking for “ndxuhf.4d2.org”, and so when my evil DNS server receives a request for the IP address of “ndxuhf.4d2.org”, it knows it’s from your ISP. Now I know the address of your ISP’s DNS server — in other words, I have the target for my cache poisoning attack.

Now let’s say my evil webpage redirects your web browser to a second evil webpage. This page causes your browser to try to load something from thousands of randomly-generated subdomains of google.com — diweujdie.google.com, xnsdddscs.google.com, wjdiumdeh.google.com, and so on. Now I know with great certainty that your ISP’s DNS server is making thousands of requests, asking for the IP addresses for these made-up names.

While this is all happening, my evil server can be sending fake responses back to your ISP, giving bad IP addresses. I’ve overcome the first of the two problems I mentioned earlier, because I know I’m sending fake responses for something that’s actually being requested. However, I still have to get that random number (the TXID) correct for your ISP to trust my response.

This is where something called the birthday paradox becomes important. The birthday paradox concerns this question:

How many people need to be in a room in order for there to be a better than 50% chance that two of them share the same birthday?

The answer is 23: In a room of 23 people, there is a better than 50% chance that two of them share a birthday. To most people, this number is surprisingly low. The fact is that as the number of people in the room grows, the likelihood of any two of them sharing a birthday increases exponentially (OK, it actually asymptotically approaches 100%, but this isn’t math class).

This matters to my example cache poisoning attack because it’s a similar situation. Your ISP is sending a bunch of requests, and I’m sending a bunch of phony responses. Causing a bunch of requests to happen doesn’t make it proportionally easier for me to guess the right TXID for one of them; it makes it exponentially easier. I only have to guess right once, and on a modern internet connection this can all happen in seconds.

So let’s say that I’ve successfully forged a response with the correct TXID, and that it’s managed to get to your ISP before the legitimate response from Google. I’ve successfully supplied an evil IP address, but only for the one made-up subdomain where I happened to get the TXID right. How likely is it that anyone else is going to try to visit “mxeqwoi.google.com”?

This is where the little wrinkle described in point 3 at the top of this article becomes useful. In the example I gave, in order for the response “ask ns1.google.com” to be useful, the root server has to provide an address for “ns1.google.com”. In other words, the root server is allowed to say, “I know that the address you’re looking for is known by ns1.google.com, and I know that the address of ns1.google.com is A.B.C.D.” This extra information is part of the DNS standard because without it you’d never be able to find ns1.google.com. Attacks involving this extra information have been foreseen, and so there’s a security restriction here: The extra information won’t be saved unless it pertains to the same domain as what’s being requested (google.com in this example).

Back to my example, in which I caused your ISP to request the address of “mxeqwoi.google.com” and happened to guess the TXID correctly. What if the response I sent said:

“I know that the address you’re looking for is known by ns9.google.com, and I know that the address of ns9.google.com is W.X.Y.Z.”

…where W.X.Y.Z is the address of my evil DNS server? It’s meets the security standard I just described because both mxeqwoi.google.com and ns9.google.com are subdomains of google.com. Your ISP’s DNS server accepts the response and asks my evil DNS server for the address of mxeqwoi.google.com, and my evil DNS server responds, but that isn’t the important part. The important part is that your ISP’s DNS server now believes that my evil DNS server is the place to go for IP addresses for anything ending in “google.com”. Now the next time your ISP’s cached entry for www.google.com expires, it’ll ask my evil DNS server for the IP address, and I’ll start receiving traffic intended for www.google.com. The same goes for mail.google.com, labs.google.com, talk.google.com, and so on. As I mentioned much earlier in this article, my response can specify the amount of time your ISP is allowed to cache my evil address. If I set this to a very long time, say 72 hours, I’ll be receiving almost all of the traffic coming from your ISP’s customers for www.google.com for the next 72 hours, or until your ISP finds out what I’ve done.

This is a very simplistic example and I’m sure there is additional finesse possible here, but I hope this illustrates the magnitude of the DNS problem. Imagine what could happen if someone successfully poisoned cached DNS entries for, say, paypal.com.

Fortunately, the majority of the DNS servers out there have already taken precautionary measures against this problem.

Trackback URI | Comments RSS