Re: djbdns/dnscache poisoning weakness

On Feb 9, 2009, at 8:25 PM, Dean Anderson wrote:
> On Mon, 9 Feb 2009, Kevin Day wrote:
>>
>> 1) Dnscache treats "SOA" requests as uncacheable.
>>
>> There are several types of DNS query types, used to ask for different
>> information about a domain. The "Start of Authority" (SOA) type is
>> used to ask for certain data about the management and cache policies
>> for the domain. When receiving a reply from the real server about an
>> SOA request, it tells the client who requested it everything it  
>> found,
>> then immediately forgets the reply. This makes the "Kaminsky" attack
>> (described above) much simpler, and improves its efficiency slightly.
>>
>>
> SOA should not be cached; if it is cached, one can't find out if the  
> SOA
> has changed promptly, and zone transfers won't work in a timely  
> manner.
> There is no reason to cache SOA records.
>

Zone transfers don't occur through a caching name server. Dnscache  
should never sit between two servers doing zone transfers. Even if  
they are, the TTL on a SOA record works no differently than any other  
record. If you don't want it to be cached for a long time, say so.  
This isn't a problem.

>> 2) Dnscache makes no attempt to prevent simultaneous identical  
>> queries
>> from going out at once.
>>
>> By default, dnscache allows up to 200 queries to be "in progress" at
>> once. However, it doesn't check to see if it's already waiting for a
>> response for a query before asking the same question again. Using the
>> SOA weakness above, the attacker can make the same SOA request over
>> and over until they succeed in poisoning the server. An attacker can
>> take advantage of this by requesting the same query 200 times, then
>> send a flood of forged replies.
>
> We have already analyzed this. This attack requires some 20 million
> packets to succeed. Reducing the number of outstanding queries  
> increases
> the effort.  The proposed changes made the dnscache server much  
> weaker,
> exploitable in about 1000 messages instead of 20 million.
>

I really wish you would detail how this makes anything WEAKER.

To poison a DNS server in the traditional method, you need to guess  
(roughly) two 16 bit numbers. The total space is 32 bits (4 billion),  
with roughly half needed to win an attack on average (2 billion). 2  
billion attempts is the "gold standard" for poisoning prevention right  
now, without applying techniques such as 0x20.

Using the technique I described in the original email, attackers can  
make use of dnscache's weakness to open 200 identical queries at once.  
In this situation, dnscache has 200 queries open with identical type,  
class and name, the only difference is the source port and query ID.  
Each forged packet (also containing the same type, class and name) is  
checked with all 200 open queries. Instead of each forged packet  
having a 1 in 4 billion chance of success, it now has a 200 in 4  
billion chance of success, or roughly one in 16.3 million.

The patch we've offered does nothing more than look to see if a client  
is requesting an EXACT duplicate of a query that dnscache is already  
waiting for a reply for. If so, it doesn't open up another request to  
the authoritative server, but "merges" the two client queries together  
so that the reply from the first also answers the second. By doing so,  
the attacker can only make his forged packets potentially collide with  
1 open query instead of 200.

How does this weaken the server? Please, please, please explain the  
scenario where this harms anything.

>>
>> Step 1: Through some careful timing analysis, the attacker can
>> determine how long it takes the victim to receive a reply from the
>> real server. Assume the attacker determines that it takes no less  
>> than
>> 1/10th of a second(100ms) for the real reply to reach the victim.
>> Step 2: The attacker sends a flood of queries to the victim, filling
>> all 200 slots.
>> Step 3: Due to the lack of duplicate query checking mentioned in #2
>> above, the victim rushes to send the real server 200 queries.
>> Step 4: The attacker floods the victim with forged responses, hoping
>> to guess the random numbers correctly.
>> Step 5: Just before the oldest query in the 200 slot window reaches
>> 100ms in age, the attacker sends a new query to the victim.
>> Step 6: The victim throws away the oldest query, and issues a brand
>> new request.
>> Step 7: When the real reply from the real server comes in for the
>> query that was just thrown away, the victim doesn't recognize it and
>> discards it.
>> Step 8: Go back to Step 4 until success.
>
> Without careful analysis, I'm quite dubious of this claim. Once an
> oustanding queryid is dropped, so is the record of its queryid. One
> still has a 1 in 20 million chance of hitting the right port and right
> queryid.

I've done this. I've done it in a lab, on our production network, and  
even across the internet to a willing guinea pig.

Let me try to explain it in a different way, because what you're  
saying is also what I think I'm saying - so we're missing each other  
somewhere.

Dnscache keeps a list of all open queries, in order from newest to  
oldest. When the list is full (200 queries are open and waiting for  
replies from the authoritative servers), the query on the bottom of  
the list gets thrown off to make room for a new query at the top.

Now, imagine that the attacker is sending new queries, every 0.25ms.  
Every new query pushes the oldest query off the list. At this rate, no  
query ends up on the list for more than 50ms. The "real" server is  
100ms away. Its replies never make it to dnscache before the query  
that initiated the request is shoved off the list. Dnscache is getting  
lots of replies from the real server, but none are matching up with  
the queries it has open. So, the attacker is keeping a window of 200  
open queries for the same resource open, and the real server is never  
getting heard. The attacker can forge packets as long as he wants  
until he succeeds.

(from the top of your post:)


> When the 'DNS cache scare' started last summer, Kaminsky tried to get
> people to convert to David Ulevitch's OpenDNS service. The scare also
> prompted efforts to promote DNSSEC.  These are "scare" scams, not
> legitimate threats for which people should change DNS software.

I don't care if people use OpenDNS or DNSSEC. Nowhere do I recommend  
that anyone switches to OpenDNS. I'm not Dan Kaminsky or David  
Ulevitch. They did nothing here other than help verify what I thought  
I was seeing.

DNSSEC is not ready for prime time, and dnscache doesn't support it  
anyway. We're entirely djbdns/dnscache users in my organization. I'm  
not trying to make anyone switch, I'm trying to make sure dnscache is  
as secure as it possibly can be, with the limitations that the DNS  
protocol exposes.

> Previous analysis of the Kevin Day/Dan Kaminsky proposed changes to
> DNSCACHE revealed that they would ADD EXTREME WEAKNESS not fix  
> weakness,
> making it possible to poison a cache in about 1000 messages. I have  
> not
> yet analyzed the BIND changes, and do not know if they suffer the same
> weaknesses as the DNSCACHE changes.

Dean, I have to say I'm disappointed.

Back when news of this first leaked out back in August, you  
(justifiably so) basically told me to disclose the vulnerabilities or  
shut up about it. I wasn't able to discuss this then, so the talk  
moved to a private series of emails between you, me and Dan Kaminsky.  
Dan really has no involvement in this other than that I went to him  
saying "I think I found this, it's very similar to your BIND findings,  
is this new to you?" While I credit him greatly with planting the  
original idea in my head, attaching this mess to his name is unfair to  
him. :)

We *privately* tried to reassure you that there was no conspiracy,  
that I really did find something, and gave you a peek at what I was  
working on. You turned around and posted a reply (quoting things that  
were said to you with the understanding of confidence) while cc:'ing  
this list. I wasn't happy, you saw no problem with posting what you'd  
learned publicly, our discussion ended.

To try to prevent exactly this kind of email from happening now, I  
extended the olive branch to you offering to give you an advance copy  
of everything I was going to post today so we could at least attempt  
to get on the same page before this was released. After a whole lot of  
back and forth, you agreed to confidentially review our findings in  
exchange for an early peek. I sent you a copy almost two weeks ago,  
with no reply. I sent a follow-up on the 2nd and 5th reminding you of  
our release schedule, and again offering to make time to address any  
concerns you had before we went recommending our patches to people. I  
heard nothing other than a "I'll look at it soon", until today.

The whole point of us extending you the trust of an early peek at the  
document was to avoid EXACTLY THIS SITUATION, where we've had dozens  
of people inspecting and verifying things only to have one person  
AFTER it's made public saying they think there's something wrong. If  
you really thought these patches were flawed and actually weakening  
security, why wait until now to talk to me? I have complete faith in  
what we're offering as being a safe and effective fix.

Additionally, I don't think we gave you a copy of the patches before,  
just the paper itself. Are you positive you're looking at the right  
dnscache patches? This is honestly the first I've heard that you  
believed these patches aren't effective, so to say I'm confused is a  
bit of an understatement.

Please, Dean. I've given you my phone number a dozen times. I've  
offered to listen to any concerns you had and spend as much time with  
you as you wanted until we at least agreed to disagree, but I honestly  
don't know what I can do here. We tried desperately to make you a part  
of the solution.

-- Kevin