Re: 2 forwarded messages...DNSEXT discussion of Day and Kaminsky

On Sat, Feb 28, 2009 at 12:13:49PM -0700, Andy Bradford wrote:

> This may  be a bit  rhetorical, but here  is Bruce Schneier's  model for
> evaluating the security of any given solution:

I'll try to answer these, because I think it gives a good summary of
this giant thread.

> 1. What assets are you trying to protect?

The validity of cache results from your dnscache server.

> 2. What are the risks to those assets?

There is an attack in which the attacker triggers a large number of
query lookups by dnscache, then floods dnscache with spoofed packets in
an attempt to poison the cache; the attacker has a low chance of success
but can repeat the attack over and over until they succeed.

For a single query, we expect the attacker to require around 2 billion
packets. For a 10Mbps link, this would take about 40 hours of sustained
attack. However, if the attacker triggers multiple identical queries,
then they require only about 16 million packets, requiring only 18
minutes on the same link.

So you are at risk if:

  1. Somebody can trigger an arbitrary number of queries on your
     dnscache server. Obviously if you are serving untrusted clients,
     that is one method. However, an attacker may be able to trigger
     other network services to do a lookup (e.g., attempting to submit
     mail may trigger an SPF lookup).

  2. 16 million packets to your cache will not be detected by any
     existing monitoring system which might shut down the attack.

Your risk may be amplified if the attacker can send packets to you
faster (because you have less time to respond).  Your risk is amplified
if you have patched dnscache to have a higher value for MAXUDP (because
fewer packets are required).

The exact numbers are given in Kevin Day's paper:

  http://www.your.org/dnscache/djbdns.pdf

Dean insists that the expected number of packets with this attack is
actually 28 million. I think his math is suspect. See:

    http://article.gmane.org/gmane.network.djbdns/13820

> 3. How well does the security solution mitigate those risks?

It brings the expected number of packets back up to 2 billion.

> 4. What other risks does the security solution cause?

Dean insists that the qmerge patch opens up new attacks. I have yet to
see him describe any such attack in detail or provide any detailed
mathematical analysis about an attacker's chance of success.

Paul Jarc described a potential attack based on what Dean had said, but
my calculations suggest it is not a problem. See:

    http://article.gmane.org/gmane.network.djbdns/13817

At this point, I am of the opinion that Dean's concerns are without
merit (because I haven't seen a concrete attack described). However, the
patches are relatively new, and it is not clear how many people are
actually looking carefully at them. It is possible there are other
security side effects that have not been considered. It is also possible
that Dean has an attack which he will describe in the future.

I haven't looked closely, but it is my understanding that BIND does
similar suppression of duplicate outgoing queries. And I don't want to
argue that "if BIND does it, it must be good"; but there is a good
chance that any attack that does not work against stock dnscache but
does work against the dnscache+qmerge is going to also work against
BIND. Which means that although these _patches_ haven't been looked at
for years, the _concept_ of duplicate suppression has.

> 5. What costs and trade-offs does the security solution impose?

There is an extra O(MAXUDP+MAXTCP) array iteration for every outgoing
query. I don't think anybody has calculated or measured the additional
CPU load. For stock dnscache, it probably doesn't matter (since it is
already doing a O(MAXUDP+MAXTCP) iteration to select on I/O). It might
make a difference if you have patched dnscache to avoid this loop in
stock dnscache.

A qmerge-patched dnscache will not, upon receiving a duplicate query
request, send an extra packet. This means that:

  - dnscache may use less upstream bandwidth than before

  - if a packet to an authoritative server is lost, dnscache will time
    out before sending another one. With stock dnscache, an impatient
    client may query dnscache again, which will trigger another query,
    which, if it is not also lost, may generate a response. With
    qmerge, dnscache will refuse to send the second packet until it hits
    its timeout, which may mean a longer wait for the client.

> Finally: Is the trade-off worth it?

That is really up to each dnscache administrator, based on their risk in
(2) above, and their comfort level with (4) and (5).

I think there is one thing Schneier is missing from his list, which is:
are there _better_ solutions available? That is, even if a security
trade-off is worth it, there may be another solution which also
mitigates the risk but has fewer costs.

Dean has proposed falling back to TCP in the case of a detected attack;
to the best of my knowledge there are neither patches nor a detailed
analysis of the drawbacks (if any) for such a scheme. But it is possible
that it could be a better solution; I'm waiting to see if patches
materialize before forming my own opinion.

-Peff