关于DNS生日攻击的成功概率

bedreaming.cublog.cn 原创。

前几天看了一下用DNS生日攻击进行缓存投毒（Cache Poisoning）方面的东西，一直没太明白生日悖论（Birthday Paradox）是如何在对DNS的攻击中起作用的。

最开始时看到的是http://www.secureworks.com/research/articles/dns-cache-poisoning，这篇文章貌似很经典，很多地方都引用了它。它里面给出了基本的用生日攻击进行DNS缓存投毒的方法，而且给出了关于ID碰撞成功率的公式：

但正如另一篇文章（被盾了的，需要翻墙看，至少里面的公式图片是没法直接看到的） http://lukenotricks.blogspot.com/2008/11/on-dns-birthday-probability.html
所说的，这个公式最大的一个漏洞就是：当我发送的假回应的包的数量（含有不同TID）大于等于所有可能的值的数量（仅猜测TID时，是65535）时，那必定会有一个包能够命中，也就是可能性应该为1，但显然这个公式得出的可能性不为1。因此作者在文中也给出了另一个成功率的计算公式（n为发出的查询包和回应包的数量，t为可能值的数量）：

开始觉得这个公式是合理的，但仔细一想，又想不通了：DNS的攻击方式是先发n个针对同一域名的查询包，然后再发n(其实也有可能不是n，n的话是文中的方式)个有不同TID假回应，这样就变成计算两个元素数量为n的集合中有相同TID的包的概率。而文中给出的上述公式计算的应该是在在一个元素数为n的集合中，有至少两个数相同的概率。

其实该问题可以抽象为以下模型：从t个互不相同的数中，先取n个不同的数记为集合A，再取n个不同的数组记为集合B，那A和B中至少有一个数值相同的概率是多少？这个概率的计算就简单了，考虑A和B中完全没有重合的概率，为C(t,t-n)/C(t,n)，则有至少两个数值相同的概率则为P=1-C(t,t-n)/C(t,n)，这个是我得出的结果。

因为一直没想明白自己考虑的对不对，郁闷了几天，今天终于在看CERT #457875()的时候找到了跟自己的结果一致的说法，考虑的角度不同，但得出的结果是一致的。它得出的概率是P=[1-n/t]*[1-n/(t-1)]*....[1-n/(t-n-1)]，跟1-C(t,t-n)/C(t,n)展开后结果是一样的。

先发个帖，做个笔记在这。