Re: djbdns/dnscache poisoning weakness

On Feb 12, 2009, at 11:44 AM, Emilio Perea wrote:

> On Mon, Feb 09, 2009 at 01:41:37PM -0600, Kevin Day wrote:
>> 1) Dnscache treats "SOA" requests as uncacheable.
>>
>>
> The meaning of this may be obvious to people familiar with dnscache
> internals, but I'm confused.  If the reply is immediately forgotten,  
> how
> is the cache corrupted?
>
> Does dnscache forget only the SOA record but caches the glue?  Does  
> the
> glue address record for ns1.example.com obtained from the example.com.
> server override the cached address already obtained from the com.
> server?  If the answer to both these questions is "yes", then I can  
> see
> why this would be a problem for a public dnscache.  But then the  
> poison
> would be flushed by the first SOA query after the attack ends, right?
>
> This is all academic to most of us who run only local dnscaches, but I
> would still like to understand what the actual problem is.


Lemme back up a bit and explain how brute-force poisoning attempts  
work, which should make this a bit more clear. Before any of the  
nitpickers come out, I am intentionally simplifying this a bit.

Here's how a normal DNS request works:

Step 1: The client asks dnscache to look up a record.
Step 2: dnscache checks to see if the information the client wants is  
already cached, if so send it to the client and stop here.
Step 3: If not, dnscache connects to the authoritative server for that  
domain, passes on the request and waits for a reply.
Step 4: The authoritative server replies, dnscache checks to see if it  
appears authentic, caches that reply, and passes the result on to the  
client who requested it initially.

In step 4, I say "dnscache checks to see if it appears authentic". How  
does it do this? When dnscache made the request to the authoritative  
server, it included 5 important pieces of information. They are:

1) The IP address of the authoritative server it contacted.
2) The name of the resource it was looking up. ("example.com")
3) The type of query it was making. (A, PTR, MX, etc)
4) A randomly generated 16-bit number called a "query ID".
5) A randomly generated "source port", included in the UDP header.

When the reply comes back, all 5 must be correct or dnscache  
completely ignores the reply.


Now, pretend we're in the "pre-Kaminsky-attack" days. This is what an  
attacker would have to do to poison a server. There are three players  
in this scenario, the "victim" (a copy of dnscache running that the  
attacker wants to poison), the "attacker" (the bad guy sending spoofed  
packets), and the "client" (whoever is making requests to the victim -  
which might be the same system as the attacker). Assume the attacker  
wants to convince the victim that www.example.com is at 6.6.6.6  
instead of the real address.

Step 1: An attacker pretends to be a client of the victim, and asks  
the victim what the address is for "www.example.com".
Step 2: The victim looks to see if it already has the IP of "www.example.com 
" in its cache. If so, game over for the attacker. The attacker must  
wait for the cache to expire to even try once.
Step 3: If the attacker is lucky and "www.example.com" isn't cached,  
the victim makes a request to the authoritative server for  
"example.com" to find out its address.
Step 4: The attacker now has a very brief window to try to get very  
very lucky. The attacker has to send spoofed packets pretending to be  
from the authoritative server (item #1 above), containing A record  
responses (Item #2) for "www.example.com" (Item #3), and the attacker  
must correctly guess the query ID (#4) and source port (#5). The  
attacker can send packets as fast as he wants trying different  
combinations of #4 and #5, but as soon as the real reply from the  
authoritative server comes in, dnscache stops listening for more  
replies. Even at a 10mbps flood, the attacker is probably only going  
to get 1000-1500 attempts in before the real reply arrives. On  
average, it takes about 2 billion attempts, so this was very very  
unlikely.
Step 5: If the attacker did manage to guess correctly, the attacker's  
forged reply telling dnscache that www.example.com is at 6.6.6.6 is  
cached, and returned to any client who requests it later. If the  
attacker didn't guess correctly, he has to wait until the cache  
expires before trying again.

With caches lasting hours/days, this wasn't a very efficient method of  
attack, so it was mostly overlooked.


One of the things I discovered was that dnscache makes no attempt to  
stop duplicate outgoing queries from happening at once. Essentially,  
if 200 clients request the address for "www.example.com" all at once,  
and dnscache doesn't have "www.example.com" in its cache, it makes 200  
requests to example.com's authoritative servers to look it up. A tad  
inefficient, but usually a short lived phenomenon. From an attacker's  
point of view, this actually helps them though. Repeat the scenario  
above, modified to take advantage of this:

Step 1: An attacker pretends to be a client of the victim, and asks  
the victim what the address is for "www.example.com" 200 times, using  
back-to-back packets.
Step 2: The victim looks to see if it already has the IP of "www.example.com 
" in its cache. If so, game over for the attacker. The attacker must  
wait for the cache to expire to even try once.
Step 3: If "www.example.com" isn't cached, the victim makes 200  
requests to the authoritative server for "example.com" to find out its  
address.
Step 4: Now dnscache has 200 queries open. All 200 queries have items  
#1, #2 and #3 the same. The only difference is #4 and #5. The attacker  
sends a flood of spoofed packets, with varying #4 and #5. The  
difference here is that dnscache has 200 possible queries to match  
each one of those up with. The attacker sends one spoofed packet, and  
now has 200 times the odds of finding a matching query on dnscache's  
side. Instead of 2 billion attempts, it now requires around 10  
million. Not great, but the attacker now can succeed in around 200  
times less effort.
Step 5: If the attacker did manage to guess correctly, the attacker's  
forged reply telling dnscache that www.example.com is at 6.6.6.6 is  
cached, and returned to any client who requests it later. If the  
attacker didn't guess correctly, he has to wait until the cache  
expires before trying again.

This is bad, but still not the end of the world. 1500 packets per try,  
with 10 million packets before a 50% chance of success = almost 7000  
tries. With a few hours/days between each try, waiting for the cache  
to expire, this still isn't feasible.


Now look at what happens when the attacker makes SOA requests instead  
of A requests.

Step 1: An attacker pretends to be a client of the victim, and asks  
the victim what the SOA record is for "www.example.com" 200 times,  
using back-to-back packets.
Step 2: The victim looks to see if it already has the SOA of "www.example.com 
" in its cache. It doesn't, since SOA records are never cached.
Step 3: The victim makes 200 requests to the authoritative server for  
"example.com" to find out its address.
Step 4: Now dnscache has 200 queries open. All 200 queries have items  
#1, #2 and #3 the same. The only difference is #4 and #5. The attacker  
sends a flood of spoofed packets, with varying #4 and #5. The  
difference here is that dnscache has 200 possible queries to match  
each one of those up with. The attacker sends one spoofed packet, and  
now has 200 times the odds of finding a matching query on dnscache's  
side. Instead of 2 billion attempts, it now requires around 10 million.
Step 5: Eventually the real replies start coming back to the victim.  
No matter, the attacker just goes back to step 1 and sends more client  
requests. The attacker can now continue indefinitely until guessing  
correctly. At 10mbps of requests, this takes a little more than an  
hour to succeed.

Poisoning an SOA record itself is kinda useless, but because of "glue  
records" this becomes useful again. The attacker's spoofed packets say  
"The SOA record for www.example.com is (whatever). Also, you didn't  
ask for this, but the IP address of www.example.com is 6.6.6.6". Since  
that extra information came from a trusted source, dnscache believes  
it and starts handing out "6.6.6.6" to anyone who asks it what the IP  
address of "www.example.com" is.


Does that make more sense?

Our patches do two things.

#1 SOA records are now cacheable like any other record.

#2 If a client asks dnscache for something that's not already in its  
cache, dnscache checks to see if it's already waiting for a reply to  
that exact same question. If so, a second query isn't made, and both  
clients waiting for the response are sent answers as soon as the reply  
comes in.


-- Kevin