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

Dean Anderson <[email protected]> wrote:
> By having DNScache use fewer ports, any non-random behavior of
> randombind has a greater impact on the fewer ports used by DNScache.
> DNScache becomes more predictable for a longer.  Attackers can
> exploit that non-randomness to their benefit.

How, exactly?  What is the algorithm the attacker would use?

Knowing the algorithm is absolutely crucial.  I understand the
algorithm for the birthday attack, but I haven't been able to figure
out what the algorithm would be for the attack(s) you're talking about.

>> If your dnscache has 200 active queries to a.ns.yp.to and b.ns.yp.to
>> asking for the A records for cr.yp.to, I only have to successfully
>> forge a response to one of those queries to give you poisonous MX
>> records for cr.yp.to that you'll save.  The other 199 queries can be
>> answered legitimately and your cache is still poisoned.
>
> No, if any of the other 199 are responded before the attack is
> successful, then the query is answered and the attack fails.

Ok, I think we've found a point where we have different understandings
of stock dnscache's behavior.  From my reading of the source, when the
first response arrives for an outgoing query, dnscache will stop
waiting for responses to that outgoing query, and it will send a
response for the incoming query that triggered it, if it now has
enough information to do so, but it will still continue waiting for
responses to any other identical outgoing queries - it will not answer
another incoming query until receiving a response for its associated
outgoing query.

dnscache responds to an incoming query using dnscache.c:u_respond().
(Also t_respond(), for an incoming TCP query, but it's handled the
same way.)  u_respond() is called in only two places: in
dnscache.c:u_new(), for the case of an incoming query for information
that's already cached; and in dnscache.c:doit() 355-359:
      if (u[j].active) {
        r = query_get(&u[j].q,u[j].io,&stamp);
        if (r == -1) u_drop(j);
        if (r == 1) u_respond(j);
      }

dnscache responds only if query_get() returns 1.  Let's assume that no
response for this outgoing query was received, and see what
query_get() returns in that case.  query.c:query_get() first calls
dns_transmit:dns_transmit_get().  dns_transmit_get() will be passed
the iopause_fd* from u[j] above, which by assumption did not receive a
response yet.  So u[j].io->revents will be 0, and in that case we
don't have to look too far into dns_trasmit_get().  If we haven't yet
reached the outgoing query's deadline, dns_transmit_get() will do
nothing and return 0 (in which case, query_get() will also return 0,
and so dnscache won't respond to the incoming query), and if we have
reached the deadline, it will move on to the next NS and retry the
query, still returning 0 (assuming no errors while creating/binding
the new socket), and so dnscache still won't respond.  (If there were
errors, then we dive into query.c:doit() and jump to SERVFAIL.  It
gets hairy after that, but I don't think it can end with returning 1
to send a response.)

As long as dnscache hasn't replied to or dropped the incoming query
for u[j], it'll keep waiting for a response to the associated outgoing
query.

> By contrast, under the Qmerge patch, the attacker _knows_ there is
> only one query/response pair, and they can conduct a DOS attack on
> either of those two packets, lengthening the time for their attack
> to succeed.

qmerge + 200 identical attack queries ->
  dnscache chooses a single new port for a new outgoing query

no-qmerge + 1 attack query ->
  dnscache chooses a single new port for a new outgoing query

I don't see any significant difference between these cases - in
particular, they seem equally vulnerable to port guessing and to DOS.
So qmerge doesn't seem to me to introduce any vulnerabilities that
aren't already there.  Can you give an algorithm for an attack on the
first situation that would be less effective against the second?

> But DNScache falls back to TCP in other circumstances, as do other
> nameservers, so I think such failure is already unavoidable if TCP
> is not supported.

Currently, dnscache only uses TCP after a truncated response, doesn't
it?  That's under the control of the domain owner, who can ensure that
no response from their data would be large enough to get truncated.
So they know that unpatched dnscache won't ever try TCP, and they
don't need to run axfrdns.

I don't know whether other resolvers might use TCP based on conditions
outside the control of the domain owner.


paul