基于DoS攻击的随机数据包标记源跟踪算法

作者：饥饿加菲猫（QQ120474） 
      iojhgfti@hotmail.com 

摘要: 针对互联网上日益猖獗的拒绝服务攻击（DoS），分析了传统的随机数据包标记算法的性能缺陷，提出一种新的基于散列消息鉴别码的返回跟踪算法HPPM，通过分析其性能指标，说明该算法提高了返回跟踪DoS攻击的效率和准确性。 
感谢帮过我的几个高手袁哥[nsfocus], sunwear[E.S.T] , isno[xfocus] , scz[nsfocus] 
1．引言 
    拒绝服务攻击，简称DoS(Denial-of-Service)，是一种常见的黑客攻击行为。这种攻击行为通过发送带有虚假源地址的数据包请求，使网络服务器充斥大量等待回复的信息,消耗网络带宽或系统资源,使网络或系统服务负载过重，服务质量下降，直至瘫痪而停止正常的服务。有时,黑客为了提高攻击的效果,往往会联合多个攻击站点向受害者发动进攻。由于DoS攻击易于实施、难于防御，而且很难返回跟踪攻击源，使之成为一个严重侵扰网络服务提供商、政府机关和金融证券等机构正常运作的安全问题。 
2．IP返回跟踪相关技术 
为了彻底消除DoS攻击，必须追根溯源，找到真正的攻击机器或攻击者。这种方法被称为IP返回追踪技术（IP Traceback）。由于DoS攻击者在发送攻击数据包时往往会伪造源地址，使得IP返回追踪的难度很大。常用的IP返回追踪方法有：入口过滤（Ingress Filtering）、连接测试（Link Testing）、ICMP追踪[7]、登录分析（Logging）、源路径隔离引擎（SPIE）、IPSec追踪，以及随机数据包标记追踪（PPM）[2]。各种追踪技术之间的性能比较，如表1所示。 
    管理负担     网络负担     路由器负担     分布式能力     事后追踪能力     预防/反应 
进入过滤     中等     低     中等     N/A     N/A     预防 
输入调试     高     低     高     好     差     反应 
控制流     低     高     低     差     差     反应 
登陆分析     高     低     高     极好     极好     反应 
ICMP追踪     低     低     低     好     极好     反应 
数据包标记     低     低     低     好     极好     反应 
表1 几种IP返回追踪技术的性能比较[2] 
3．HPPM IP返回跟踪算法 
    3.1     PPM算法（Probabilistic Packet Marking） 
随机数据包标记算法PPM的主要原理如下：路由器以一定的概率p（通常是1/25）[2]，用其IP地址或IP地址的一部分随机标记经过它的数据包。当发生DoS攻击时，受害者根据其收到的攻击数据包中的标记信息，重建攻击路径。使用PPM算法，路由器负担较小，采用标记边压缩和分片技术大大降低了额外的网络流量。而且，该方法可以在攻击结束以后对攻击源进行追踪。PPM对单源DoS攻击，有较好的追踪效果。 
但是，由于其自身缺陷，PPM算法无法很好地返回跟踪DDoS攻击（Distributed–Denial–of–Service）。首先，由于路由器以概率p随机标记数据包，就给攻击者以可乘之机，将伪造的标记信息写入攻击数据包的报头中（一般是Identifier字段），只要该数据包一直不被其经过的路由器标记，直至目标主机，就能在攻击路径中伪造一条边路径，阻止受害者跟踪真正的攻击源。其次，为了节省存储空间，减小网络负担，PPM采用了边标记压缩和分片存储技术。但是，分片存储可能导致受害者将本不属于同一数据包的分片组合在一起，从而生成错误的边路径。而标记的边压缩方法主要依据(a○+b)○+b=a(a、b分别是攻击路径上相邻两个路由器的IP地址)，将显著加剧这一效果，进一步生成错误的攻击路径。当发生DDoS攻击时，由于同一距离存在多个攻击者，而产生爆炸效果，影响将更加严重[2]。 
3.2     HPPM算法 
针对PPM算法的上述缺陷，我们提出了一种基于散列消息鉴别码HMAC的数据包标记算法HPPM，并采用新的标记重叠分片策略，以提高IP返回跟踪DoS攻击（特别是DDoS攻击）的性能。 
在该算法中，路由器Ri以概率p随机对经过它的数据包进行标记，标记信息包括Ri的IP地址和下一跳路由器Rj的IP地址，总共64位。为了节省标记存储空间，不给用户带来过多影响，算法使用IPv4首部中的16位标识符字段（Identifier），1位闲置的标志位（Flags）[1]和13位片位移字段（据统计，目前少于0.25%的数据包需要分片[2]），以及一般很少使用的8位TOS字段（Type-of-Service）[1],总共38位，来存储标记分片信息。64位标记信息被分成k＝8片，每片占用8位，分片偏移值占log2k＝3位，Ri到目标主机的距离值占5位（25－1＝31跳，适用于目前绝大多数网络[2]），用于验证的HMAC值占22位。 
散列消息鉴别码，简称HMAC，是一种基于消息鉴别码MAC（Message Authentication Code）的鉴别机制。使用HMAC时,消息通讯的双方，通过验证消息中加入的鉴别密钥K来鉴别消息的真伪；HMAC还引人了一个散列函数H，对消息进行加密，进一步确保消息鉴别的安全性和有效性。HMAC的具体计算方法如下： 
HMAC(M,K) = H(K○+opad, H(K○+ipad, M )) 
其中，ipad = 字0x36重复B次，opad = 字0x5C重复B次，M = 待加密的消息字符串，B = 消息字符串的字长。关于HMAC更详细的内容，请参考文献RFC 2104[6]。 
在HPPM算法中，我们采用一次性口令机制OTP（One-Time Password）[4][5]，先让每个路由器Ri生成一组私有密钥序列{Kij}（j=0、1、2……）。这组私有密钥序列通过单向散列函数f生成，并具有以下规则：Kij-1 =f(Kij)。由于函数f是单向的，所以由最新的密钥Kij可以依次推出在它以前生成的所有Kij-1、Kij-2……Ki0，但根据已有的密钥却推不出下一个密钥，这就确保了他人无法伪造Ri的密钥。路由器Ri每经过一段固定的时间间隔，就根据上述方法更换一次私有密钥Ki，然后将刚刚停止使用的密钥通过可靠的方式发布出去。当数据包P通过Ri时，Ri 使用HMAC函数H和当前私有密钥Ki，对Ri 的IP地址和P的目的地址进行加密，即：H(M,Ki),其中，M = IP(Ri)+IP(destination)。具体的标记步骤如下： 
Marking procedure at router Ri: 
let m be the marking massage ip(Ri) + ip(Rj) 
let k be the number of fragments in m 
let H be the HMAC function 
let Ki be the private key of Ri at current time interval    
for each packet w 
let x be a random number from [0..1) 
if x < p then 
let hmac be the HMAC value of IP(Ri)+IP(w.destination) 
    hmac := H( IP(Ri)+IP(w.destination), Ki) 
let o be a random integer from [0..k-1] 
let f be the fragment of m at offset o 
write f into w.frag 
write 0 into w.distance 
write o into w.offset 
write hmac into w.hmac 
else 
increment w.distance 
以下将讨论受害者重建攻击路径的过程。当受到DoS攻击时，受害者开始收集标记分片，并记录其到达时间。我们假设攻击者发送大量的攻击数据包，那么受害者就能收集到足够多的标记分片，然后根据分片的偏移值，将具有相同攻击距离d和hmac值的分片重组，生成边路径，进而生成整个攻击路径。由于攻击者可能伪造标记数据包，干扰返回跟踪过程，因此需要对生成的边路径鉴别真伪。具体鉴别方法是：受害者与路由器Ri（服务提供商）联系，取得Ri最新的私有密钥K，然后根据K和数据包P到达时间（需要考虑延时），使用相同散列函数f计算出Ri标记P时使用的私有密钥Ki；再根据Ri和自身的IP地址，以及Ki，计算出HMAC值与标记数据包中的HMAC值进行比较，一致则说明该边路径有效，否则将其丢弃。重建攻击路径的具体过程如下： 
Path reconstruction procedure at victim v: 
let FragTbl be a table of tuples (frag, offset, distance, hmac, time) 
let G be a tree with root v 
let edges in G be tuples (start,end,distance,hmac,time) 
let maxd := 0 
let last := v 
for each packet w from attacker 
let rectime be the time when v receives the packet w 
FragTbl.Insert(w.frag,w.offset,w.distance,w.hmac,rectime) 
if w.distance > maxd then 
maxd := w.distance 
for d := 0 to maxd 
for all ordered combinations of fragments having the same hmac value at distance d 
construct edge z( IP(Ri), IP(Rj), w.distance, w.hmac, rectime) 
// Start of HMAC authentication 
let K be the private key of Ri at current time interval 
let Ki be the private key of Ri at the time interval when Ri marked the packet w 
let f be the function to get Ki according to K and rectime 
Ki := f(K, rectime) 
if w.hmac = H(IP(Ri)+IP(v), Ki) 
insert edge z( IP(Ri), IP(Rj), w.distance) into G 
        // End of HMAC authentication 
remove any edge (x,y,d,hmac,time) with d ≠ distance from x to v in G 
extract path (Ri..Rj ) by enumerating acyclic paths in G 
4．HPPM算法性能分析 
4.1     攻击收敛包数 
根据[2]，受害者收到距离为d的路径上最远处路由器发来的标记数据包的概率是：p(1-p)d-1。保守假设受害者收到该路径上任一路由器发来标记数据包的概率都与最远距离d处相同，并且相互独立，因此受害者收到的任一数据包被该数据包途经路径上某些路由器标记过的概率，将具有期望值：1/dp(1-p)d-1。 
根据coupon-collector问题[8]，受害者收到的从距离为d的路径上发来的数据包中，包括所有d个路由器中每个路由器发出的至少一个标记数据包，所需要接收的数据包数，具有以下期望值：1＋d/(d-1)+d/(d-2)+……+d/2+d = d(ln(d)+O(1))。考虑到每个标记数据包被分成k片，总共有kd片，则上述值为kd(ln(kd)+O(1))。因此，重建距离为d（包含d个路由器）的攻击路径所需要的数据包数N，具有期望值： 
E(N)<kd(ln(kd)+O(1)) 
1/dp(1-p)d-1≈k 
ln(kd)/p(1-p)d-1 
因此，该算法攻击收敛包数与PPM边标记算法相同[2]。 
4.2     健壮性 
    在PPM算法[2]中，对于输出长度为h的散列随机函数，受害者接受任一候选边路径的概率是1/2h。假设有m个攻击者，则在一定距离d处，最坏情况下将有m个独立的路由器。因此，在距离受害者d处，本不在实际攻击路径中的任意候选边路径被受害者接受（即：产生了正误差[3]）的最大概率将是：1-(1-1/2h)n（其中n=mk）[2]。因为，最坏情况下，距离d处将有mk个标记分片。当k值或m值很大时，这一概率也将变得很大。而HPPM算法使用的HMAC鉴别机制，可以十分有效地鉴别攻击者伪造的边路径，将伪造的边路径从候选边路径中过滤掉，从而充分减小了算法产生的正误差，提高了返回跟踪的准确性。 
4.3     路由器负担 
由于采用HMAC和一次性口令机制来加密攻击数据包中的边标记，因此中间路由器无须承担PPM算法中每个路由器对其IP地址和已有边标记进行的异或运算(a○+b)○+b。而HMAC的计算过程简单，扩展性也很好，当发现或需要运算速度更快或更安全的散列函数时，几乎不用修改，就可以很容易地实现底层散列函数的替换，参阅文献[6]。为了使数据包标记过程更加安全，路由器需要周期性更换其用于加密边标记的私有密钥。这个周期需要进行适当选择，周期太短将给路由器带来额外负担，且不利于与受害者的同步，周期太长又影响算法安全性，可以考虑把10秒作为其数量级[3]。 
4.4     受害者负担 
由于使用了一次性口令机制，受害者需要获取上游路由器加密边标记时使用的私有密钥。一种可行的方法是，上游路由器将最新密钥通过可信渠道发布（如：发布在网站上），受害者鉴别边标记真伪时，只需下载该路由器的最新密钥，根据最新密钥就能推算出该路由器以前加密边标记时使用的所有密钥。这一过程可以在常数时间内完成。 
4.5     算法局限性 
HPPM算法，要求受害者掌握网络拓扑结构，具有其上游路由器的地图，这在一定程度上限制了算法的发展。受害者与中间路由器关于密钥的同步过程还需要进一步考虑。 
5．总结及未来工作 
本文描述了一种新的基于散列消息鉴别码HMAC的随机数据包标记算法HPPM，该算法用于返回跟踪DoS攻击的攻击源，能够充分减小由于攻击者伪造数据包标记而带来的误差，提高了返回跟踪的安全性和准确性。然而，该算法还有不完善的地方，比如：与大多数返回跟踪算法一样，HPPM算法是一种反应型跟踪算法，即：只有确实发生了攻击，才能进行跟踪。并且，该算法实际上无法跟踪到真正的攻击源，只能返回跟踪到最接近攻击源的边界路由器。这些问题都有待进一步研究。 

参考文献 
[1] W.Richard Stevens著，范建华 胥光辉 张涛 等译，谢希仁校，《TCP/IP详解——卷1：协议》[M]，第1版，北京：机械工业出版社，2000年4月，第24－27、111－112页. 
[2] S.Savage, D.Wetherall, A.Karlin and T.Anderson. Practical network support for IP traceback[C]. In ACM SIGCOMM, Stockholm, Sweden, 2000, 295-306. 
[3] D.X.Song and A.Perrig. Advanced and authenticated marking schemes for IP traceback[C]. In IEEE INFOCOMM, April 2001. 
[4] N.Haller, The S/KEY One-Time Password System[Z], Internet RFC 1760, February 1995. 
[5] N.Haller, A One-Time Password System[Z], Internet RFC 2289, February 1998. 
[6] H.Krawczyk, M.Bellare, and R.Canetti, HMAC: Keyed-Hashing for Message Authentication[Z], Internet RFC 2104, February 1997. 
[7] S.M.Bellovin. ICMP Traceback Messages[Z]. Internet Draft:draft-bellovin-itrace-00.txt.March 2000. 
[8] W.Feller. An Introduction to Probability Theory and Its Applications[M]. 2nd edition, volume 1. Wiley and Sons. 1966. 
[9] K.Park, H.Lee. On the Effectiveness of Probabilistic Packet Marking for IP Traceback under Denial
 of Service Attack[C]. In IEEE INFOCOM, 2001.