[转]关于TCP/IP序列号生成方法的研究(一)

◆ 关于TCP/IP序列号生成方法的研究(一)
　　
　　作者：黄兆勤 < [e-mail] >
　　日期：2001-6-12
　　 [摘要]
　　这篇文章是从TCP/IP协议层一个广为人知的TCP Spoof攻击方法说起，深入地讨论伪随机数PRNG原理及其设计方法，其中，涉及了关于网络层协议，密码学，统计学，数学模型，随机数等一系列问题。本文假定读者已经具有一定的TCP/IP协议和网络编程方面的知识，而且对加密和统计学由一定程度的了解。
　　[Abstract]
　　 This paper starts with a widely known attack method---TCP Spoof, and deeply discuss the theory of PRNG. At the end , I design a new PRNG using IDEA and MD5. This paper involves many concept such as network protocol, encryption, statistics, delay coordinates, random number etc. This paper assumes that the reader has some knowledge about TCP/IP and Network programming, however, with a background knowledge of encryption and statistics, one will find it easy to understand my PRNG.
　　[目录]
　　1.TCP Sequence Number 的预测
　　2.针对TCP ISN的现行解决方案
　　 2.1 配置和使用密码安全协议
　　 2.2 使用RFC1948
　　 2.3 其它一些方法
　　3.对各种TCP ISN生成器的构造方法的安全性评估
　　 3.1 ISN与PRNGs(伪随机数生成器)
　　 3.2 Spoofing 集合
　　 3.3 一种称为“delay coordinates”的分析方法
　　 3.4 各种操作系统的TCP ISN生成器的安全性比较
　　4.对ISN的数学分析
　　5.关于SYN攻击
　　6.IDEA和MD5算法
　　7.随机数的分析
　　 7.1介绍
　　 7.2 一个好的PRNG 应该具备的条件
　　 7.3 随机种子的重要性
　　 7.4 传统的PRNG
　　8.一个基于IDEA算法和MD5算法的ISN PRNG Generator
　　
　　附录
　　A. 一个基于IDEA算法和MD5算法的PRNG源代码
　　B. 正态分布表
　　1. TCP的Initial Sequence Number(ISN)的预测

　　正常的TCP连接基于一个三次握手(3-way handshake)，一个客户端(Client)向服务器(Server)发送一个初始化序列号ISNc，随后，服务器相应这个客户端ACK(ISNc),并且发送自己的初始化序列号ISNs，接着，客户端响应这个ISNs（如下图），三次握手完成。
　　 C ---〉S: (ISNc)
　　 S ---〉C: ACK(ISNc)+ ISNs
　　 C ---〉S: ACK(ISNs)
　　 C ---〉S: data
　　 and / or
　　 S ---〉C: data
　　下面，我以Windows2000 Advanced Server为例，来说一下两台主机是如何进行三次握手。


　　我们可以看到，
　　1) Smartboy首先发送一个seq:32468329的包给服务器202.116.128.6。
　　2) 然后, 202.116.128.6响应主机Smartboy, 它送给Smartboy自己的
　　 seq:3333416325 而且响应Smartboy的ack:3240689240。
　　3) Smartboy再响应服务器202.116.128.6, seq:3240689240, ack:3333416326。
　　 三次握手完毕，两台几建立起连接。
　　 可以看出，在三次握手协议中，Clinet一定要监听服务器发送过来的ISNs, TCP使用的sequence number是一个32位的计数器，从0-4294967295。TCP为每一个连接选择一个初始序号ISN，为了防止因为延迟、重传等扰乱三次握手， ISN不能随便选取，不同系统有不同算法。理解TCP如何分配ISN以及ISN随时间变化的规律，对于成功地进行IP欺骗攻击很重要。
　　在Unix系统里，基于远程过程调用RPC的命令，比如rlogin、rcp、rsh等等，根据/etc/hosts.equiv以及$ HOME/.rhosts文件进行安全校验，其实质是仅仅根据源IP地址进行用户身份确认，以便允许或拒绝用户RPC。这就给与了那些攻击者进行IP地址欺骗的机会。
　　 让我们看X是如何冒充T来欺骗S，从而建立一个非法连接 ：
　　 X---->S: SYN(ISNx ) , SRC = T
　　 S---->T: SYN(ISNs ) , ACK(ISNT) （*）
　　 X---->S: ACK(ISNs+1 ) , SRC = T （**）
　　 X---->S: ACK(ISNs +1) , SRC = T, 攻击命令（可能是一些特权命令）
　　 但是，T必须要在第（**）中给出ISNs, 问题是ISNs在第（*）步中发给了T(X当然很难截取到)，幸运的是，TCP协议有一个约定: ISN变量每秒增加250,000次，这个增加值在许多版本比较旧的操作系统中都是一个常量，在FreeBSD4.3中是125000次每秒，这就给X一个可乘之机。
　　 看一下X是如何猜出ISNs :
　　 a、首先，X发送一个SYN包来获取服务器现在的ISNs
　　 X ---〉S: (ISNx)
　　 S ---〉X: ACK(ISNx)+ ISNs# (1)
　　 b、紧接着，X冒充T向服务器发送SYN包
　　 X ---〉S: SYN(ISNx ) , SRC = T (2)
　　 c、于是，服务器发出一个响应包给T(这个包X是收不到的)
　　 S ---〉T: SYN(ISNs$) , ACK(ISNT ) (3)
　　 d、X计算ISNs$:
　　ISNs$=ISNs#+ RTT×Increment of ISN(4)
　　 其中，RTT(Round Trip Time),是一个包往返X和S所用的时间,可以通过Ping 来得到。

　　 上图显示了round trip times (RTT) 大概是０。
　　 Increment of ISN是协议栈的初始序列号每秒钟增加的值，以Unix为例，当没有外部连接发生时，服务器的ISN每秒增加128,000,有连接的时候，服务器的ISN每秒增加64,000。
　　 e、于是，
　　 X ---> S : ACK(ISNs$) （冒充可信主机成功了）
　　 X ---> S : 恶意的命令或窃取机密消息的命令
　　2．针对TCP ISN的现行解决方案
　　TCP协议（RFC793 by Jon Postel）特别指出：

　　在评价以下的解决方案时有几点要注意：
　　 1.该解决方案是否很好地满足TCP的稳定性和可操作性的要求？
　　 2.该解决方案是否容易实现?
　　 3.该解决方案对性能的影响如何?
　　 4.该解决方案是否经得起时间的考验？
　　以下的几种方案各有各的优点和缺点，它们都是基于增强ISN生成器的目标提出的。
　　2.1 配置和使用密码安全协议
　　 TCP的初始序列号并没有提供防范连接攻击的相应措施。TCP的头部缺少加密选项用于强加密认证，于是，一种叫做IPSec的密码安全协议的技术提出了。 IPSec提供了一种加密技术（End to end cryptographic），使系统能验证一个包是否属于一个特定的流。这种加密技术是在网络层实现的。其它的在传输层实现的解决方案（如 SSL/TLS和SSH1/SSH2）, 只能防止一个无关的包插入一个会话中，但对连接重置（拒绝服务）却无能为力，原因是因为连接处理是发生在更低的层。IPSec能够同时应付着两种攻击（包攻击和连接攻击）。它直接集成在网络层的安全模型里面。
　　上面的解决方案并不需要对TCP协议做任何得修改，RFC2385(“基于TCP MD5签名选项的BGP会话保护)和其他的技术提供了增加TCP头部的密码保护，但是，却带来了收到拒绝服务攻击和互操作性和性能方面的潜在威胁。使用加密安全协议有几个优于其它方案的地方。TCP头部加密防止了Hijacking和包扰乱等攻击行为，而TCP层仍然能够提供返回一个简单增加ISN的机制，使方案提供了最大程度的可靠性。但实现IPSec非常复杂，而且它需要客户机支持，考虑到可用性，许多系统都选择使用RFC 1948。
　　2.2 使用RFC1948
　　 在RFC1948中，Bellovin提出了通过使用4-tuples的HASH单向加密函数，能够使远程攻击者无从下手（但不能阻止同一网段的攻击者通过监听网络上的数据来判断ISN）。
　　 Newsham 在他的论文 [ref_newsham]中提到:
　　RFC 1948 [ref1]提出了一种不容易攻击（通过猜测）的TCP ISN的生成方法。此方法通过连接标识符来区分序列号空间。每一个连接标识符由本地地址，本地端口，远程地址，远程端口来组成，并由一个函数计算标识符分的序列号地址空间偏移值（唯一）。此函数不能被攻击者获得，否则，攻击者可以通过计算获得ISN。于是，ISN就在这个偏移值上增加。ISN的值以这种方式产生能够抵受上面提到的对ISN的猜测攻击。
　　 一旦全局ISN空间由上述方法来生成，所有的对TCP ISN的远程攻击都变得不合实际。但是，需要指出的，即使我们依照RFC 1948来实现ISN的生成器，攻击者仍然可以通过特定的条件来获得ISN(这一点在后面叙述).
　　 另外，用加密的强哈希算法(MD5)来实现ISN的生成器会导致TCP的建立时间延长。所以，有些生成器（如Linuxkernel ）选择用减少了轮数的MD4函数来提供足够好的安全性同时又把性能下降变得最低。削弱哈希函数的一个地方是每几分钟就需要对生成器做一次re-key 的处理，经过了一次re-key的处理后，安全性提高了，但是，RFC793提到的可靠性却变成另一个问题。
　　 我们已经知道，严格符合RFC1948的ISN生成方法有一个潜在的危机：
　　 一个攻击者如果以前合法拥有过一个IP地址，他通过对ISN进行大量的采样，可以估计到随后的ISN的变化规律。在以后，尽管这个IP地址已经不属于此攻击者，但他仍然可以通过猜测ISN来进行IP欺骗。
　　以下，我们可以看到RFC 1948的弱点:
　　 ISN = M + F(sip, sport, dip, dport, <some secret>)
　　其中
　　 ISN 32位的初始序列号
　　 M 单调增加的计数器
　　 F 单向散列哈希函数 (例如 MD4 or MD5)
　　 sip 源IP地址
　　 sport 源端口
　　 dip 目的IP地址
　　 dport 目的端口
　　<some secret> 哈希函数可选部分，使远程攻击者更难猜到ISN.
　　 ISN自身的值是按照一个常数值稳定增加的,所以F()需要保持相对的稳定性。而根据Bellovin 所提出的，<some secret>是一个系统特定的值（例如机器的启动时间，密码，初始随机数等），这些值并不 会经常变。
　　但是，如果Hash函数在实现上存在漏洞（我们无法保证一个绝对安全的Hash函数，况且，它的实现又与操作系统密切相关），攻击者就可以通过大量的采样，来分析<some secret>，其中，源IP地址，源端口，目的IP地址，目的端口都是不变的，这减少了攻击者分析的难度。
　　 Linux TCP的ISN生成器避免了这一点。它每５分钟计算一次<some secret>值,把泄漏<some secret>的风险降到了最低。
　　有一个办法可以做的更好：
　　 取M = M + R(t)
　　 ISN = M + F(sip, sport, dip, dport, <some secret> )
　　 其中
　　 R(t) 是一个关于时间的随机函数
　　很有必要这样做，因为它使攻击者猜测ISN的难度更大了（弱点在理论上还是存在的）。
　　2.3 其它一些方法
　　 构造TCP ISN生成器的一些更直接的方法是：简单地选取一些随机数作为ISN。这就是给定一个32位的空间，指定ISN = R(t)。(假设R()是完全的非伪随机数生成函数)
　　固然，对于完全随机的ISN值，攻击者猜测到的可能性是１／２32是，随之带来的一个问题是ISN空间里面的值的互相重复。这违反了许多RFC(RFC 793, RFC 1185, RFC 1323, RFC1948等)的假设----ISN单调增加。这将对TCP协议的稳定性和可靠性带来不可预计的问题。
　　 其它一些由Niels Provos（来自OpenBSD 组织）结合完全随机方法和RFC 1948解决方案：
　　ISN = ((PRNG(t)) << 16) + R(t) ３２位
　　 其中
　　 PRNG(t) ：一组随机指定的连续的１６位数字0x00000000 -- 0xffff0000
　　 R(t) ：16位随机数生成器（它的高位msb设成０）0x00000000 -- 0x0000ffff
　　 上面的公式被用于设计OpenBsd的ISN生成器，相关的源代码可以从下面的网址获得
　　http://www.openbsd.org/cgi-bin/cvsweb/src/sys/netinet/tcp_subr.c
　　 Provos的实现方法有效地生成了一组在给定时间内的不会重复的ISN的值，每两个ISN值都至少相差32K,这不但避免了随机方法造成的ISN的值的冲突，而且避免了因为哈希函数计算带来的性能上的下降，但是，它太依赖于系统时钟，一旦系统时钟状态给攻击者知道了，就存在着系统的全局ISN状态泄密的危机。
　　3. 对各种TCP ISN生成器的构造方法的安全性评估
　　3.1 ISN与PRNGs(伪随机数生成器)
　　我们很难用一台计算机去生成一些不可预测的数字，因为，计算机被设计成一种以重复和准确的方式去执行一套指令的机器。所以，每个固定的算法都可以在其他机器上生成同样的结果。如果能够推断远程主机的内部状态，攻击者就可以预测它的输出；即使不知道远程主机的PNRG函数，但因为算法最终会使ISN回绕，按一定的规律重复生成以前的ISN,所以，攻击者仍然可以推断ISN。幸运的是，目前条件下，ISN的重复可以延长到几个月甚至几年。但是，仍然有部分 PRNG生成器在产生500个元素后就开始回绕。解决伪随机数的方法是引入外部随机源，击键延时，I/O中断，或者其它对攻击者来说不可预知的参数。把这种方法和一个合理的HASH函数结合起来，就可以产生出32位的不可预知的TCP ISN的值，同时又隐蔽了主机的PNRG的内部状态。不幸的是，很少的TCP ISN产生器是按这种思路去设计的，但即使是这样设计的产生器，也会有很多的实现上的漏洞使这个产生器产生的ISN具有可猜测性。
　　 RFC1948的建议提供了一种比较完善的方法，但是，对攻击者来说，ISN仍然存在着可分析性和猜测性。其中，PRNG的实现是个很关键的地方。
　　3.2 Spoofing 集合
　　需要知道一点是，如果我们有足够的能力能够同时可以发出２32个包，每个包由不同的ISN值，那么，猜中ISN的可能性是100%。但是，无论从带宽或计算机的速度来说都是不实际的。但是，我们仍然可以发大量的包去增加命中的几率，我们把这个发出的攻击包的集合称为Spoofing集合。通常，从计算机速度和网络数据上传速率两方面来考虑，含5000个包的Spoofing的集合对众多的网络用户是没有问题的，5000-60000个包的Spoofing 集合对宽带网的用户也是不成问题的，大于60000个包的Spoofing集合则超出一般攻击者的能力。网络的速度和计算机性能的不断增加会提高那种使用穷尽攻击方法猜测ISN的成功率。从攻击者的立场，当然希望能够通过定制一个尽可能小的Spoofing集合，而命中的几率又尽可能高。我们假定我们攻击前先收集50000个包作为ISN值的采样，然后，我们把这些ISN用作对将来的ISN的值猜测的依据。
　　3.3一种称为“delay coordinates”的分析方法
　　在动态系统和非线性系统中，经常使用一种叫做“delay coordinates”的分析法，这种方法使我们可以通过对以前的数据的采样分析来推想以后的数据。
　　我们试图以建立一个三维空间（x,y,z）来观察ISN值（seq[t]）的变化，其中t取0,1,2, ……

　　方程组（E1）
　　
　　 现在，对采样了的50000个ISN序列seq[t] 按照上面的三个方程式来构建空间模型A。这样，就可以通过A的图像特征来分析这个PNRG生成的ISN值的规律。Ａ呈现的空间模型的３D特性越强，它的可分析性就越好。
　　 接着，我们根据这个模型，去分析下一个ISN值seq[t],为此，我们用一个集合K(5000个)去猜测seq[t]。
　　如果我们知道seq[t-1],要求seq[t],那么，可以通过在这个三维空间中找出一个有良好特性的节点P(x,y,z)，将P.x+seq[t- 1],我们就可以得到seq[t]。现在，我们将注意力放到怎样在这个三维空间中选择一些点来构成Spoofing集合，也就是怎样通过seq[t- 1],seq[t-2],sea[t-3]来推知seq[t]。
　　 由于seq[t-1],seq[t-2],seq[t-3]都可以很容易地在远程主机上探测到，于是，P.y和P.z可以通过以下的公式求出

　　 而对于P.x=seq[t]-seq[t-1], 由于seq[t-1]已知，所以，我们可以把它当作是空间的一条直线。如果，在对以前的ISN的采样，通过上面提到的构成的空间模型A呈现某种很强的特征，我们就可以大胆地假设，seq[t]在直线与A的交点上,或者在交点的附近。这样，seq[t]就这样确定了，于是，seq[t+1],seq[t+ 2]……,我们都可以推断出来。

　　 于是，我们大致将构造Spoofing集合分成3个步骤：
　　3.3.1 先选取L与A交点之间的所有点。如果，L与A没有交点，我们则选取离L最近的A的部分点。
　　假设现在 seq[t-1]=25
　　 seq[t-2]=50
　　 seq[t-3]=88
　　 于是，我们可以计算出
　　 y = seq[t-1] - seq[t-2]=25
　　 z = seq[t-2] - seq[t-3]=33
　　 而我们在集合A中找不到满足y=25,z=33这个点，但是，我们找到y=24,z=34和y=27,z=35这两个点，所以，我们要把它们加入Spoofing集合。
　　3.3.2 我们按照上面的方法，把在A附近（半径<=R1的空间范围内）点集M找出来，然后，我们根据这些点的相应的x值去推导相应的seq[t]（按照一定的算法，后面会提到）,于是，我们就得到很多的seq[t]。
　　3.3.3 根据点集M(j),我们在一定的变化浮动范围U里（-R2<=U<=+R2）处理其x值，得出以下的集合K：
　　 M(j).x+1 M(j).x-1 M(j).x+2 M(j).x-2 M(j).x+3 M(j).x-3 …… M(j).x+R2 M(j)-R2
　　3.3.4 接着我们确定R1和R2的值
　　R1值的选取的原则：使M不为空集，一般为1-500个。
　　R2值的选取的原则：使K的个数为5000。
　　 对TCP ISN的PRNG分析的总体流程：

　　相关系数的意义：
　　R1 radius: 影响搜索速度。
　　R2 radius: 影响猜测ISN的成功率， R2越大，成功率越高，但代价越大。
　　Average error: 反映了在3.3.2中找出的点集的平均距离。一个过分大的平均距离是不需要的。可以通过是否有足够的正确的猜测值来计算Average error。
　　3.4 delay coordinates分析法的意义
　　 站在攻击者的立场，他是千方百计地想缩小搜索空间，他希望先搜索一些最可能的值，然后再去搜索其它可能性没那么大的值。通过delay coordinates，他可以看去观察ISN数列的特征，如果，按照上面的方法构造的空间模型Ａ呈现很明显的空间轮廓，如一个正方体，一个圆柱体，或者一个很小的区域，那么ISN很可能就是这个空间模型Ａ中的一点，搜索空间就会可以从一个巨大的三维空间缩小到一个模型Ａ。看一下一个设计得很好的PRNG （输出为32位）：...2179423068, 2635919226, 2992875947, 3492493181, 2448506773, 2252539982, 2067122333, 1029730040, 335648555, 427819739...

　　 RFC 1948要求我们用31位的输出，但是，32位的搜索空间比31位的要大一倍，所以，在后面的PRNG的设计中，我采用了32位的输出。
　　下面，我们来看一下各种典型的空间模型以及对它们的评价。

　　 从空间特性可以看出，某些区域的值互相重叠，某些地方的空间形状很明显，呈针状型，这种PRNG设计得不好，重叠特性很强，攻击者可以从左图分析推断可能性比较大的重叠区域去搜索，这样可以大大减少搜索的难度。

　　 这种PRNG参杂了一些可以预测的随机种子，导致空间模型呈现很明显的片状。攻击者可以根据前面的一些ISN来推测后面的ISN。

　　 这种PRNG产生的随机数序列之间的差值非常小，但是，它的分布特性非常好。所以，虽然，它并没有扩展到整个空间，但是，它比上面几种模型要好的多。攻击者攻击的成功率要少得多。

　　 这个PRNG是以计算机时钟为随机源的。它的ISN值都分布在三个很明显的面上。三个面都在模型的中间有一个汇聚点。这样的PRNG设计的非常差，所以，我们在设计PRNG的时候，不能只是以时钟作为随机源。
　　3.4 各种操作系统的TCP ISN生成器的安全性比较
　　3.4.1 Windows 95 和Windwos 98 SE

　　 Windows 95 的序列号产生算法非常的弱，但很难明白为什么Windows 98的算法更弱。我们看到R1为0，也就是说，A的空间特性太明显，以致M集只需要一个点就可以算出seq[t]。我们看到，Windows 98的R2小于Windows 95的R2，换言之，Windows 98的seq[t]的搜索代价更少。
　　3.4.2 Windows NT4 SP3，Windows SP6a和Windows 2000

　　 Windows NT4 SP3在ISN的PNRG算法也是非常弱的，成功率接近100%。Windows 2000和Windows NT4 SP6a的TCP 序列号有着相同的可猜测性。危险程度属于中到高的范围。虽然，我们在图上看不到很明显的3D结构化特征，但是，12%和15%对攻击者来说，已经是一个很满意的结果。
　　3.4.3 FreeBSD 4.2,OpenBSD 2.8和OpenBSD-current

　　 OpenBSD-current的PRNG 输出为31-bit,也就是说，△seq[t]的值域范围可以是231 –1，意味着,y,z值域也很大，这对使我们很难确定M集，经过我们的处理后，可以看到一个云状物(见上图)，它的R1半径很大，而且分布均匀，不呈现任何的空间结构化特性，很难对它进行分析。
　　3.4.4 Linux 2.2

　　 Linux 2.2的TCP/IP序列号的可分析性也是很少，比起OpenBSD-current,它的PRNG的输出宽度只有24bit，但是，对抵御攻击已经足够了。Linux是按照RFC 1948规范的。它的HASH函数从实现来说，应该是没有什么的漏洞，而且，它应该是引入了外部随机源。
　　3.4.5 Solaris
　　 Solaris的内核参数tcp_strong_iss有三个值，当tcp_strong_iss=0时，猜中序列号的成功率是100%；当 tcp_strong_iss=1时，Solaris 7和Solaris 8一样，都能产生一些特性相对较好的序列号。

　　 tcp_strong_iss=2时，依据Sun Microsystem的说法，系统的产生的ISN值非常可靠，不可预测。通过观察采样值的低位值的变化，可以相信它的PRNG的设计采用了RFC 1948规范，正如Solaris的白皮书所提到的。

　　但是，我们观察到，Solaris7(tcp_strong_iss=2)虽然使用了RFC 1948,但是，仍然相当的弱，究其原因，是因为Solaris没有使用外部随机源，而且也没有在一段时间之后重算<some secret>。由一些Solaris系统动态分配IP地址的主机群要特别小心，因为Solaris在启动之后，<some secret>一直都不会变(这一点与Linux不同)，于是，攻击者在合法拥有某个IP地址的时候，他可以在TCP会话期间对序列号进行大量的采样，然后，当这个IP地址又动态地分配给其他人的时候，他就可以进行攻击（在Clinet-Server结构的网络系统中要尤为注意，因为，许多应用都是分配固定的端口进行通讯）。