Thursday, July 24, 2008

Hindsight analysis of the infamous DNS bug

If you read Dan Kaminsky's researchs over the past few years, you'd probably know that Dan knows many DNS tricks. One of these is the CNAME trick that Dan mentioned in the Wired interview. He has talked about this trick back to 2007 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

$ dig 111 IN A

$ dig 120 IN CNAME 120 IN A

$ dig 118 IN A
As you can see, this trick, Dan called it "CNiping", can be used to overwrite whatever is 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 (

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 ( 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 have
only one opening query to guess its QID.

No comments: