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

On Wed, Feb 18, 2009 at 11:15:48PM -0500, Paul Jarc wrote:

> Ok, I think I see what you're saying.  If I'm right, a description
> like this would have been far, far clearer:
> 1. An attacker floods a qmerge-patched dnscache with 200 identical
>    queries.
> 2. dnscache forgets all previous outgoing queries, and sends just one
>    new outgoing query.
> 3. The attacker probes the dnscache box to see what UDP ports are in
>    use.
> 4. The attacker uses only those ports in their forged responses.
>    Since the attacker has reduced the number of ports to choose from
>    by possibly as many as 199, the odds are better of guessing the
>    right port.
> 
> Is this the attack you have in mind?

Thanks for posting this, Paul; it let me finally figure out what Dean
was talking about.

I don't think qmerge behaves any worse than stock dnscache under such an
attack. Below is my analysis of the probabilities for both
implementations. I just wrote it and it hasn't been reviewed by anyone,
so please let me know if there are any mathematical or logic errors.

Here's the short version for those that are impatient:

  The number of possible ports from which an attacker must choose is
  lower with qmerge, which intuitively means their chance of success is
  better. But the number of ports which grant success is _also_ lower,
  which reduces their chances.

And the long version:

An attacker stimulates a query, port-scans the resolver, and then sends
a spoof packet for some (qtype, query, dest) triple Q that matches the
stimulated query.  The queryid is guessed randomly, and the port is
guessed randomly from the set of open ports. Assume the spoof arrives
before the real response.

Let X be the number of active queries that want to know Q.

Let N be the number of active queries that care about something other
than Q.

Let O be the number of other UDP ports open on the system, not due to
dnscache.

We want to know the probability P that the spoof succeeds.

With stock dnscache, each of the X+N active queries opens a new port. So
the chances of hitting a port which belongs to dnscache and matches our
Q is X/(X+N+O). The chances of hitting the queryid correctly for that
port are 2^-16. So

  P = X / (X+N+O) * 2^-16

Furthermore, we know that X+N <= MAXUDP, and N >= 0. So we can
substitute for high and low N to see the bounds:

For N=0,

  P <= X / (X+O) * 2^-16.

For N=MAXUDP-X,

  P >= X / (X+MAXUDP-X+O) * 2^-16
    or
  P >= X / (MAXUDP+O) * 2^-16

With the qmerge patch, all of the X use only a single port. So the
chance of hitting a spoofable port is 1/N+O. So the probability is:

  P = 1 / (1+N+O) * 2^-16

For N=0,

  P <= 1 / (1+O) * 2^-16

For N=MAXUDP-X,

  P >= 1 / (1+MAXUDP-X+O) * 2^-16

Now let's assume the best case for such an attack to succeed: nothing
else is running on the system (or the attacker builds a profile over
time of which ports are long-running and therefore unlikely to be
dnscache), so O=0.

Therefore:

  X / MAXUDP * 2^-16 <= P(stock) <= X / X * 2^-16
  X / MAXUDP * 2^-16 <= P(stock) <= 2^-16

and

  1 / (1+MAXUDP-X) * 2^-16 <= P(qmerge) <= 1 / 1 * 2^-16
  1 / (1+MAXUDP-X) * 2^-16 <= P(qmerge) <= 2^-16

So the upper bounds are equal: port guessing always works when there is
only one port, and we just have to guess the queryid. For the lower
bound, consider that X can vary from 1 to MAXUDP. If it's 1, then in
both cases the probability is simply 1/MAXUDP (which makes sense,
because qmerge does nothing if there are no queries to be merged). If
it's X=MAXUDP, then they are _also_ the same.  This makes sense, too. In
the qmerge case, there is only one query, since they were all qmerged.
In the stock dnscache case, that are X ports, but if we guess _any_ of
the X ports, we succeed. So the ports don't help at all.

But what happens in between? Let's consider MAXUDP=200, and X=100 (and
remember that since we are doing the lower bound, we are always assuming
that N=MAXUDP-X, which hurts the attacker the most). With stock
dnscache, the attacker can guess the port with probability 1/2. But with
qmerge, they can do so with only 1/101.

Try graphing the two lower bounds, and it is easy to see that qmerge
always is lower than or equal to stock dnscache. Which again, makes
sense: this is basically a birthday attack on the ports. Stock dnscache
does worse than qmerge because even though there are more ports to
choose from, there are more ports which yield success.

Now all of that being said, it should be kept in mind that the attacker
can manipulate X and N pretty easily. Stimulating MAXUDP identical
queries will cause everything else to be kicked out of the queue, so you
can easily get X=MAXUDP, N=0, which reaches the upper bound. And in both
implementations, that bound is identical: you know exactly which port to
choose.

So my conclusion is that for a stupid attacker, qmerge does no worse and
sometimes better in this attack. For a smart attacker, they behave the
same.

-Peff