About DNS Cache Poison

爽爽的过了个周末（我休息时间一般不上网），跑回来一看，发现互联网上还是铺天盖地的DNS漏洞。

炒作的太多了，本来不想写这个漏洞的。最近似乎所有人的blog都恨不得把这个漏洞写上一两笔，以表示自己对此的关注和重视。

目前exploit出来了三个，最早是ruby的，HD MOORE的metasploit 3 的一个模块，接下来是python的，最后才是今天出来的一个C的实现。

其实我想大家最关心的应该是成功率的问题。云舒写了很多文章分析，最后得出的结论是这是个YY漏洞。因为需要猜测real src port，还需要猜解QID，是一个类似竞争条件的问题，要抢在real name server作出应答前搞定，所以几率算下来不大。

不过由于搞定一次之后，就可以重新指定nameserver，从而可以poison整个域名，比如yahoo.com，所以价值还是非常大的。问题又回到了成功率上，哪怕几率再小，只要能成功一次就行，用长时间来提高成功率。

但是这几天看国外的讨论，好像情形要比云舒想象的好。

首先是DD上的关于计算成功率的方法。

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


然后是C语言版本exploit的作者说他的成功率也很高，基本在80秒内能搞定

So I rewrote the attack in C and was about to publish it when I noticed that Druid and HDM just released their metasploit module. I have not had the time to compare the 2 but in case anybody is interested, here it is:

$ ./kaminsky-attack q.q.q.q r.r.r.r a.a.a.a 1234 pwned example.com. 
1.1.1.1 8192 16

This should cause a pwned.example.com A record resolving to 1.1.1.1 to appear in r.r.r.r's cache. The chance of successfully poisoning the resolver with this example (8192 attempts and 16 replies/attempt) is 86% (1-(1-16/65536)**8192).
This example also requires a bandwidth of about 2.6 Mbit/s (16 replies/attempt * ~200 bytes/reply * 100 attempts/sec * 8 bits/byte) and takes about 80 secs to complete (8192 attempts / 100 attempts/sec).

Things could clearly be optimized, eg. by using label compression in the DNS packets (oh and don't comment on the quality of the code - it was rushed :P), but I am very interested to see how Kaminsky got it down to "10 secs on a fast Internet link" (does he mean 10+ Mbit/s, or is he using other more advanced tricks ?)

-marc


这个漏洞由于看的人太多了，所以和我一贯只搞YY的风格不符合，于是就没啥兴趣研究了。但我觉得不管Dan有没有新方法来快速猜解QID，我们都不应该过早下定论，严谨的态度是研究学问所必须的。