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

On Thu, Feb 12, 2009 at 01:02:42AM -0500, Dean Anderson wrote:

> Actually, one of the first problems I see is that your patch discards
> repeated queries from multiple hosts that ask the same question.  You

No, it doesn't. Each incoming query still gets a slot in udplient (or
tcpclient). When an outgoing query is made on behalf of a slot, we avoid
sending out a packet if there is already an identical query outstanding;
When the answer comes back, _all_ slots get the answer and proceed with
their resolution.

You can see this easily by doing:

  dnsqr a name-which-will-take-a-second-to-resolve &
  dnsqr a name-which-will-take-a-second-to-resolve

You should see in the log:

  txpb 1 name-which-will-take-a-second-to-resolve some-bailiwick

and both dnsqr's will receive the appropriate response (note that this
is timing related -- if you choose a name that is too quick to resolve,
the first query may actually finish before dnscache gets the second one,
and the second one just ends up reading the cached answer from the
first).

And this works exactly the same from multiple hosts:

  ssh other-host-on-your-network 'dnsqr a ...' & dnsqr a ...

I tested it. Really. If you have an experiment where a repeated query is
discarded, please let me know, because that would be a bug.


Note that there is one behavior you might notice with the patch. Imagine
this happens:

  1. Client sends dnscache a query.

  2. Dnscache sends query to authoritative server. Query is lost by
     network.

  3. Client times out, sends another query to dnscache.

  4. Dnscache sends another query to authoritative server. Authoritative
     server answers, dnscache responds to client.

  5. Original query sent by dnscache times out. dnscache reports
     servfail.

With the patch, step (4) is different. dnscache does _not_ send another
query to the authoritative server, but waits for the original query to
finish, which in this case is a time-out. So before this patch, eager
clients with a timeout smaller than dnscache's could get an answer
involving a lost packet more quickly by asking again. But now they are
subject to dnscache's timeout.

> What I'm also concerned about, is that your change may fix a problem
> that an attacker may have. Day describes the oldest queries being
> dropped. The effect this has is to restart the birthday attack before
> the required packets have been received, or rather reduce the number of
> urns, mid-attack. That makes it harder for the single birthday attack to
> succeed. Reducing the number of ports in MAXUDP increases the number of
> packets necessary to spoof dnscache.  If queries come in, and knock out
> attacker's queries, this is the same (very nearly) as reducing the size
> of MAXUDP. Kind of like accidentally hitting the reset button...

One, my understanding is that the attacker in Kevin's test setup can
actually do the timing to keep MAXUDP filled properly, and this was done
experimentally. So while such a change might make it easier for an
attacker, it is already something an attacker can deal with. But I don't
know the details, so maybe he can comment more.

But more importantly, my patch does not have that behavior. It does not
change how udpclient slots are expired at all. So you will still be
dropping oldest queries as usual.

There is one difference: a query we sent on behalf of an older client
that has been expired will still be "valid" to receive an answer, if and
only if there is still another client interested in that answer. So now
a stupid attacker who is overflowing MAXUDP won't accidentally push out
that window of opportunity (instead, it will close when the actual
response comes from the server and is cached). But balance that against
the fact that there is only _one_ window of opportunity, instead of
MAXUDP windows.

> At 200 MAXUDP, it takes 28 million packets to spoof dnscache. You'd
> notice that, so changing DNScache doesn't appear to be necessary.

I think Kevin's number was 16 million, but the same order of magnitude.

> So far, I haven't seen anything in any of these changes that makes
> DNScache stronger, nor anything that fixes a weakness.

That's because you have already written off the weakness as "you
would notice that [many packets coming in]." Maybe some installations
would. If yours does, then using these patches probably doesn't make
sense, since you have other defenses for the same attacks.

-Peff