Hindsight analysis of the infamous DNS bug

["Thai Duong" <thaidn () gmail com>]

If you read Dan Kaminsky's researchs over the past few years, you'd probably
that Dan know many DNS tricks. One of these is the CNAME trick that Dan
mentioned in the Wired
interview<http://blog.wired.com/27bstroke6/2008/07/kaminsky-on-how.html>.
He has talked about this trick back to
2007<http://www.doxpara.com/slides/DMK_BO2K7_Web.ppt>as below:

1. CNAME Records: DNS Aliases

- Instead of returning an address, return what the "Canonical", or Official
Name was, and then the address of that Canonical Name

- If you are allowed to be the resolver for that canonical name, your
additional record overrides whatever's already in the cache, even if the TTL
hasn't expired yet

* It's not a bug.

* Works against most, but not actually all name servers

2. Demo

$ dig 1.foo.notmallory.com
;; ANSWER SECTION:
1.foo.notmallory.com. 120 IN CNAME bar.foo.notmallory.com
bar.foo.notmallory.com. 120 IN A 10.0.0.0

$ dig bar.foo.notmallory.com
bar.foo.notmallory.com. 111 IN A 10.0.0.0

$ dig 2.foo.notmallory.com
2.foo.notmallory.com. 120 IN CNAME bar.foo.notmallory.com.
bar.foo.notmallory.com. 120 IN A 10.0.0.1

$ dig bar.foo.notmallory.com
bar.foo.notmallory.com. 118 IN A 10.0.0.1

As you can see, this trick, Dan called it "CNiping", can be used to
overwrite whatever is www.yourwebsite.com. I guess when Dan talked to Paul
Vixie, Paul told him that not only CNAME can be used to overwrite cached
data but also NS, and probably other type of RRs as well. This is not new.
RFC3833 has told us about this DNS *feature* for years.

Okie so now, we have some ways to overwrite cached data in a DNS resolver,
the remained problem is how to force it to accept our packet. And you
probably know this already, so I don't repeat here.

The rest of this post to to emphasize on how easy to guess the QID if we
have a fast Internet connection. Much of the following part is derived from
this study (
http://www.faqs.org/ftp/internet-drafts/draft-hubert-dns-anti-spoofing-00.txt
).

Assume the following symbols are used:

I: Number distinct IDs available (maximum 65536)

P: Number of ports used (maximum around 64000, but often 1)

N: Number of authoritative nameservers for a domain (averages
around 2.5)

F: Number of 'fake' packets sent by the attacker

R: Number of packets sent per second by the attacker

W: Window of opportunity, in seconds. Bounded by the response
time of the authoritative servers (often 0.1s)

D: Average number of identical outstanding questions of a resolver
(typically 1, see Section 5)

A: Number of attempts, one for each window of opportunity

The probability of spoofing a resolver is equal to amount of fake packets
that arrive within the window of opportunity, divided by the size of the
problem space.

When the resolver has 'D' multiple identical outstanding questions, each
fake packet has a proportionally higher chance of matching any of these
questions. This assumption only holds for small values of 'D'.

In symbols, if the probability of being spoofed is denoted as P_s:

P_s = D*F/N*P*I

It is more useful to reason not in terms of aggregate packets but to convert
to packet rate, which can easily be converted to bandwidth if needed.

If the Window of opportunity length is 'W' and the attacker can send 'R'
packets per second, the number of fake packets 'F' that are candidates to be
accepted is:

F= R * W ---> P_s = D*R*W/N*P*I

To calculate the combined chance of at least one success, the following
formula holds:

P_cs = 1 - (1 - P_s)^A = 1 - (1 - D*R*W/N*P*I)^A

When common numbers (as listed above) for D, W, N, P and I are inserted,
this formula reduces to:

P_cs = 1 - (1 -R/1638400)^A

The different between this attack and the one described in the original
study (
http://www.faqs.org/ftp/internet-drafts/draft-hubert-dns-anti-spoofing-00.txt)
is in the number A.

In the original study, A = T/TTL, where T is the time taken to successful
poison target resolvers, and TTL is the number of seconds when the target
hostname expires. In other words, each time we fail to poison, we must have
to wait for TTL second before trying again.

In this case, A = N, which is the number of queries we send to target
resolvers. This is because we don't have to wait any second even if we fail
to poison in all previous attempts. Remember the CNAME trick above?

So all you must do now is to increase R and A. Suppose for each query, you
send F = 30 fake responses to target resolvers in W = 0.1, hence your
bandwidth should be R = F/W = 300 packet/s. If A = 4000, then you stand a
51% chance to be sucessful! It's that easy.

If you use Metasploit, you can use the following formula to calculate your
probability:

P_cs = 1 - (1 - xids/2^16)^A

where xids is the number of fake responses you want to send for each query.
Remember to consider your bandwidth capacity when choosing xids. If you
choose the default value, i.e. xids=10, then you can expect to poison
successful after A>4000.

One final note: this attack is not a birthday attack. because we only have
one opening query to guess its QID.

_______________________________________________
Dailydave mailing list
Dailydave () lists immunitysec com
http://lists.immunitysec.com/mailman/listinfo/dailydave