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

On Thu, Feb 12, 2009 at 04:27:42PM -0500, Dean Anderson wrote:

> > 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.
> 
> I'd like to see the exploit code. Working on an unloaded server for an
> experiment and working on a loaded server are far different tasks.

I don't have that code, so you will have to ask Kevin if he wants to
share it.

> > 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.
> 
> Under no load, that's true. But there is no change to u_new, so the
> oldest query will still get removed as new queries come in and there are
> more than 200 outstanding queries.

No. Look at qmerge.c.

In unpatched dnscache, each udpclient has its own query struct, which in
turn has a dns_transmit struct. It is this dns_transmit that represents
a response from an authoritative server that we are willing to accept.
When the udpclient is dropped, the dns_transmit struct is reset and the
window of opportunity for receiving that response (whether from an
attacker or from the legitimate server) is closed.

In the merge-outgoing patch, qmerge.c contains a separate list (of size
MAXUDP + MAXTCP) of qmerge structs, each of which has a dns_transmit
struct. Each udpclient then has a pointer to a qmerge struct instead of
a dns_transmit struct itself; the qmerge structs are reference-counted.

So when a udpclient is dropped, we decrement the reference count. If it
hits zero, the qmerge and dns_transmit structs are reset and the window
of opportunity for the response is closed. But if there is another
client, then the reference count remains above zero, and we keep the
window open until either a valid response comes in, or all of the
remaining clients drop.

> > 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.
> 
> One window could indeed mean that it takes a smaller number of packets
> to spoof. BIND previously had just one window.

We are not using the term "window" in the same way. dnscache will accept
a response that matches in (server IP, qtype, query, queryid, port). The
first three are predictable. So by "one window" I mean that for a given
(server IP, qtype, query) triple that there is exactly one (queryid,
port) pair that will allow a response to be accepted at any given time.
As opposed to the current behavior, where you can have MAXUDP such
pairs. In other words, the very definition of closing the birthday
attack. So you need a larger number of packets to spoof.

> This appears to increase the vulnerability, particularly if the UDP
> ports can be predicted because they don't change as often. In that case,
> the attack is reduced to number of probable UDP ports * 64k packets to
> run though the QIDs.

Why do you think the ports don't change as often? They change on every
transmitted packet, just as before.

> I think your patch weakens DNScache to attacks based UDP port
> prediction.  Your work is good, and your code is respectable, but it
> just isn't based on cryptographically sound analysis.  There is no
> question that all of us were duped.

I'm sorry, but I just don't believe you. I haven't seen compelling
evidence, analysis, or argument on your part to show that dnscache has
been weakened. If the system is weaker), can you empirically show it via
an exploit?

-Peff