I thought it would be helpful, given things going on out there, to write up a guide to the attack that people could provide to their management. A lot of people are going to have to violate procedure and work extra hours. Maybe this will get a few pizzas approved :)
DNS is a system for, among other things, finding out what number to use when “calling” somebody on the Internet. Since there’s lots of people, in lots of places, there can’t just be one directory. Often, when you ask one server for a number, it tells you to go somewhere else. And when you go there, you might be sent to a third destination. This process — “recursion” — is repeated over and over, until you finally have the number for that name.
Of course, on the Internet, you aren’t really going anywhere. What’s actually happening is that you’re sending messages out, and receiving replies back. What prevents a bad guy from providing his own replies, with his own fake numbers for whatever you were looking for?
Not much — but not nothing.
DNS can be thought of as a race: A request is sent. A good guy and a bad guy both want to get their replies to be trusted. The good guy has an advantage: He sees the request, and inside of it he can find a secret number, somewhere between zero to sixty five thousand. The race is not won until someone crosses the finish line with the secret number, and while the bad guy could guess the number, he has only a 1/65,536 chance of guessing correctly. Worse, the winner of the race gets to say how long it will be until the next race! The numbers can work out that it would take months, even years for the bad guy to finally win a race.
However, there are three problems. The first two were somewhat known. The second is very new.
First, the bad guy holds the starter pistol. He decides when the request goes out — meaning, he may not know *what* the secret number is, but he actually knows the race has started before the good guy does.
Second, the bad guy is not alone. He can have as many “runners” in the race as he likes — the race is only over when someone arrives with the correct secret number. The bad guy can try wrong number after wrong number, and until the good guy shows up with the right one, he can keep trying again and again. If he can squeeze a hundred numbers in, the odds drop from one in sixty five thousand to one in six fifty five.
But those are still long odds, and if he loses, he might have to wait a day to try again.
Or he might not.
What’s new is that the bad guy doesn’t actually have to wait to start another race. DNS is actually more of a relay race than a sprint. Remember, you send a request to a server, and you might get a reply that says “www.foobar.com? Sure, here’s the IP address to use.” Or, you might get a message that says, “www.foobar.com? I don’t know, ask ns1.foobar.com, here’s its address.” That’s recursion. It’s not a bug, or a rarely used feature. DNS is always sending you to different servers to find a record — this is how the servers that run .com work.
Now, there is a limit: Not just any other name will work — or else, I could return to you “www.foobar.com? Oh, that’s hosted at http://www.google.com, and here’s its address”, and you’d believe me. (Eleven years ago, that actually worked.) But names near http://www.foobar.com — 1.foobar.com, 2.foobar.com, 3.foobar.com — are referred to as “in-bailiwick”. A referral to a name in-bailiwick must be trusted.
And so, the attack. If someone’s trying to attack www.foobar.com, he doesn’t pull out the starter pistol for that particular name. After all, the server might not be willing to go out looking for http://www.foobar.com for hours. No, he declares races for 1.foobar.com, 2.foobar.com, 3.foobar.com, and so on.
The bad guy will probably lose these races. The odds, even with a hundred-to-one advantage in the number of “runners”, are against him.
But he can run as many races as he wants. And eventually, he’ll win one of them. And when he does win — when the bad guys guesses the secret number from 0 to 65536 — he won’t just provide an answer for the random name that won. He’ll simply feign ignorance: “83.foobar.com? I don’t know, ask www.foobar.com, here’s its address. Oh, and remember this for the next week.”
He won the race. He gets his say.
Now, there have been some problematic DNS attacks in the past. Amit Klein was able to guess the secret number the good guy would return with. Joe Stewart was able to cause many secret numbers to be accepted. But neither of the attacks could override a race that had already been won. Once a name server is storing — caching — the number for a given name, it simply won’t run another race for that name. Why should it? It knows the number!
In my attack, we never race for http://www.foobar.com. We race for another name entirely. It’s a problem. It required a lot of work to address.
Incidentally, some people wanted more details on the numbers. Here’s what I can say:
1) Sweeping the net’s open recursive name servers — yeah, that ain’t great. But if nobody’s using ‘em, nobody’s vulnerable. And if it’s an open recursive name server on the Internet, there’s a good chance nobody’s managed it for several years. I’m working on load measurement hacks for these.
2) Lots and lots of important places haven’t patched.
3) I still haven’t gotten my testing script to correctly handle iptables and pf randomization. This is getting worked on — damn you creative people and your tricks! :)
4) From July 8th to July 9th, 4242 of 5000 tests actively run by users behind unique name servers showed that server to be vulnerable. That’s about 85%. Today, July 25th, the last 5000 tests (about the last six hours) from unique name servers show only 2503 of 5000 vulnerable — just above 50%. Now, I’m not going to deny. There’s selection bias. It’s a limited sample. There are tons and tons of unpatched ISPs. This is all true.
You know what? A lot of people did a lot of work to make that number drop. More needs to be done, but 13 days made a difference, and it’s awesome to see it.