作者：饑餓加菲貓（QQ120474） 
      iojhgfti@hotmail.com 

摘要: 針對(duì)互聯(lián)網(wǎng)上日益猖獗的拒絕服務(wù)攻擊（DoS），分析了傳統(tǒng)的隨機(jī)數(shù)據(jù)包標(biāo)記算法的性能缺陷，提出一種新的基于散列消息鑒別碼的返回跟蹤算法HPPM，通過(guò)分析其性能指標(biāo)，說(shuō)明該算法提高了返回跟蹤DoS攻擊的效率和準(zhǔn)確性。 
感謝幫過(guò)我的幾個(gè)高手袁哥[nsfocus], sunwear[E.S.T] , isno[xfocus] , scz[nsfocus] 
1．引言 
    拒絕服務(wù)攻擊，簡(jiǎn)稱DoS(Denial-of-Service)，是一種常見(jiàn)的黑客攻擊行為。這種攻擊行為通過(guò)發(fā)送帶有虛假源地址的數(shù)據(jù)包請(qǐng)求，使網(wǎng)絡(luò)服務(wù)器充斥大量等待回復(fù)的信息,消耗網(wǎng)絡(luò)帶寬或系統(tǒng)資源,使網(wǎng)絡(luò)或系統(tǒng)服務(wù)負(fù)載過(guò)重，服務(wù)質(zhì)量下降，直至癱瘓而停止正常的服務(wù)。有時(shí),黑客為了提高攻擊的效果,往往會(huì)聯(lián)合多個(gè)攻擊站點(diǎn)向受害者發(fā)動(dòng)進(jìn)攻。由于DoS攻擊易于實(shí)施、難于防御，而且很難返回跟蹤攻擊源，使之成為一個(gè)嚴(yán)重侵?jǐn)_網(wǎng)絡(luò)服務(wù)提供商、政府機(jī)關(guān)和金融證券等機(jī)構(gòu)正常運(yùn)作的安全問(wèn)題。 
2．IP返回跟蹤相關(guān)技術(shù) 
為了徹底消除DoS攻擊，必須追根溯源，找到真正的攻擊機(jī)器或攻擊者。這種方法被稱為IP返回追蹤技術(shù)（IP Traceback）。由于DoS攻擊者在發(fā)送攻擊數(shù)據(jù)包時(shí)往往會(huì)偽造源地址，使得IP返回追蹤的難度很大。常用的IP返回追蹤方法有：入口過(guò)濾（Ingress Filtering）、連接測(cè)試（Link Testing）、ICMP追蹤[7]、登錄分析（Logging）、源路徑隔離引擎（SPIE）、IPSec追蹤，以及隨機(jī)數(shù)據(jù)包標(biāo)記追蹤（PPM）[2]。各種追蹤技術(shù)之間的性能比較，如表1所示。 
    管理負(fù)擔(dān)     網(wǎng)絡(luò)負(fù)擔(dān)     路由器負(fù)擔(dān)     分布式能力     事后追蹤能力     預(yù)防/反應(yīng) 
進(jìn)入過(guò)濾     中等     低     中等     N/A     N/A     預(yù)防 
輸入調(diào)試     高     低     高     好     差     反應(yīng) 
控制流     低     高     低     差     差     反應(yīng) 
登陸分析     高     低     高     極好     極好     反應(yīng) 
ICMP追蹤     低     低     低     好     極好     反應(yīng) 
數(shù)據(jù)包標(biāo)記     低     低     低     好     極好     反應(yīng) 
表1 幾種IP返回追蹤技術(shù)的性能比較[2] 
3．HPPM IP返回跟蹤算法 
    3.1     PPM算法（Probabilistic Packet Marking） 
隨機(jī)數(shù)據(jù)包標(biāo)記算法PPM的主要原理如下：路由器以一定的概率p（通常是1/25）[2]，用其IP地址或IP地址的一部分隨機(jī)標(biāo)記經(jīng)過(guò)它的數(shù)據(jù)包。當(dāng)發(fā)生DoS攻擊時(shí)，受害者根據(jù)其收到的攻擊數(shù)據(jù)包中的標(biāo)記信息，重建攻擊路徑。使用PPM算法，路由器負(fù)擔(dān)較小，采用標(biāo)記邊壓縮和分片技術(shù)大大降低了額外的網(wǎng)絡(luò)流量。而且，該方法可以在攻擊結(jié)束以后對(duì)攻擊源進(jìn)行追蹤。PPM對(duì)單源DoS攻擊，有較好的追蹤效果。 
但是，由于其自身缺陷，PPM算法無(wú)法很好地返回跟蹤DDoS攻擊（Distributed–Denial–of–Service）。首先，由于路由器以概率p隨機(jī)標(biāo)記數(shù)據(jù)包，就給攻擊者以可乘之機(jī)，將偽造的標(biāo)記信息寫入攻擊數(shù)據(jù)包的報(bào)頭中（一般是Identifier字段），只要該數(shù)據(jù)包一直不被其經(jīng)過(guò)的路由器標(biāo)記，直至目標(biāo)主機(jī)，就能在攻擊路徑中偽造一條邊路徑，阻止受害者跟蹤真正的攻擊源。其次，為了節(jié)省存儲(chǔ)空間，減小網(wǎng)絡(luò)負(fù)擔(dān)，PPM采用了邊標(biāo)記壓縮和分片存儲(chǔ)技術(shù)。但是，分片存儲(chǔ)可能導(dǎo)致受害者將本不屬于同一數(shù)據(jù)包的分片組合在一起，從而生成錯(cuò)誤的邊路徑。而標(biāo)記的邊壓縮方法主要依據(jù)(a○+b)○+b=a(a、b分別是攻擊路徑上相鄰兩個(gè)路由器的IP地址)，將顯著加劇這一效果，進(jìn)一步生成錯(cuò)誤的攻擊路徑。當(dāng)發(fā)生DDoS攻擊時(shí)，由于同一距離存在多個(gè)攻擊者，而產(chǎn)生爆炸效果，影響將更加嚴(yán)重[2]。 
3.2     HPPM算法 
針對(duì)PPM算法的上述缺陷，我們提出了一種基于散列消息鑒別碼HMAC的數(shù)據(jù)包標(biāo)記算法HPPM，并采用新的標(biāo)記重疊分片策略，以提高IP返回跟蹤DoS攻擊（特別是DDoS攻擊）的性能。 
在該算法中，路由器Ri以概率p隨機(jī)對(duì)經(jīng)過(guò)它的數(shù)據(jù)包進(jìn)行標(biāo)記，標(biāo)記信息包括Ri的IP地址和下一跳路由器Rj的IP地址，總共64位。為了節(jié)省標(biāo)記存儲(chǔ)空間，不給用戶帶來(lái)過(guò)多影響，算法使用IPv4首部中的16位標(biāo)識(shí)符字段（Identifier），1位閑置的標(biāo)志位（Flags）[1]和13位片位移字段（據(jù)統(tǒng)計(jì)，目前少于0.25%的數(shù)據(jù)包需要分片[2]），以及一般很少使用的8位TOS字段（Type-of-Service）[1],總共38位，來(lái)存儲(chǔ)標(biāo)記分片信息。64位標(biāo)記信息被分成k＝8片，每片占用8位，分片偏移值占log2k＝3位，Ri到目標(biāo)主機(jī)的距離值占5位（25－1＝31跳，適用于目前絕大多數(shù)網(wǎng)絡(luò)[2]），用于驗(yàn)證的HMAC值占22位。 
散列消息鑒別碼，簡(jiǎn)稱HMAC，是一種基于消息鑒別碼MAC（Message Authentication Code）的鑒別機(jī)制。使用HMAC時(shí),消息通訊的雙方，通過(guò)驗(yàn)證消息中加入的鑒別密鑰K來(lái)鑒別消息的真?zhèn)?；HMAC還引人了一個(gè)散列函數(shù)H，對(duì)消息進(jìn)行加密，進(jìn)一步確保消息鑒別的安全性和有效性。HMAC的具體計(jì)算方法如下： 
HMAC(M,K) = H(K○+opad, H(K○+ipad, M )) 
其中，ipad = 字0x36重復(fù)B次，opad = 字0x5C重復(fù)B次，M = 待加密的消息字符串，B = 消息字符串的字長(zhǎng)。關(guān)于HMAC更詳細(xì)的內(nèi)容，請(qǐng)參考文獻(xiàn)RFC 2104[6]。 
在HPPM算法中，我們采用一次性口令機(jī)制OTP（One-Time Password）[4][5]，先讓每個(gè)路由器Ri生成一組私有密鑰序列{Kij}（j=0、1、2……）。這組私有密鑰序列通過(guò)單向散列函數(shù)f生成，并具有以下規(guī)則：Kij-1 =f(Kij)。由于函數(shù)f是單向的，所以由最新的密鑰Kij可以依次推出在它以前生成的所有Kij-1、Kij-2……Ki0，但根據(jù)已有的密鑰卻推不出下一個(gè)密鑰，這就確保了他人無(wú)法偽造Ri的密鑰。路由器Ri每經(jīng)過(guò)一段固定的時(shí)間間隔，就根據(jù)上述方法更換一次私有密鑰Ki，然后將剛剛停止使用的密鑰通過(guò)可靠的方式發(fā)布出去。當(dāng)數(shù)據(jù)包P通過(guò)Ri時(shí)，Ri 使用HMAC函數(shù)H和當(dāng)前私有密鑰Ki，對(duì)Ri 的IP地址和P的目的地址進(jìn)行加密，即：H(M,Ki),其中，M = IP(Ri)+IP(destination)。具體的標(biāo)記步驟如下： 
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 
以下將討論受害者重建攻擊路徑的過(guò)程。當(dāng)受到DoS攻擊時(shí)，受害者開(kāi)始收集標(biāo)記分片，并記錄其到達(dá)時(shí)間。我們假設(shè)攻擊者發(fā)送大量的攻擊數(shù)據(jù)包，那么受害者就能收集到足夠多的標(biāo)記分片，然后根據(jù)分片的偏移值，將具有相同攻擊距離d和hmac值的分片重組，生成邊路徑，進(jìn)而生成整個(gè)攻擊路徑。由于攻擊者可能偽造標(biāo)記數(shù)據(jù)包，干擾返回跟蹤過(guò)程，因此需要對(duì)生成的邊路徑鑒別真?zhèn)?。具體鑒別方法是：受害者與路由器Ri（服務(wù)提供商）聯(lián)系，取得Ri最新的私有密鑰K，然后根據(jù)K和數(shù)據(jù)包P到達(dá)時(shí)間（需要考慮延時(shí)），使用相同散列函數(shù)f計(jì)算出Ri標(biāo)記P時(shí)使用的私有密鑰Ki；再根據(jù)Ri和自身的IP地址，以及Ki，計(jì)算出HMAC值與標(biāo)記數(shù)據(jù)包中的HMAC值進(jìn)行比較，一致則說(shuō)明該邊路徑有效，否則將其丟棄。重建攻擊路徑的具體過(guò)程如下： 
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     攻擊收斂包數(shù) 
根據(jù)[2]，受害者收到距離為d的路徑上最遠(yuǎn)處路由器發(fā)來(lái)的標(biāo)記數(shù)據(jù)包的概率是：p(1-p)d-1。保守假設(shè)受害者收到該路徑上任一路由器發(fā)來(lái)標(biāo)記數(shù)據(jù)包的概率都與最遠(yuǎn)距離d處相同，并且相互獨(dú)立，因此受害者收到的任一數(shù)據(jù)包被該數(shù)據(jù)包途經(jīng)路徑上某些路由器標(biāo)記過(guò)的概率，將具有期望值：1/dp(1-p)d-1。 
根據(jù)coupon-collector問(wèn)題[8]，受害者收到的從距離為d的路徑上發(fā)來(lái)的數(shù)據(jù)包中，包括所有d個(gè)路由器中每個(gè)路由器發(fā)出的至少一個(gè)標(biāo)記數(shù)據(jù)包，所需要接收的數(shù)據(jù)包數(shù)，具有以下期望值：1＋d/(d-1)+d/(d-2)+……+d/2+d = d(ln(d)+O(1))。考慮到每個(gè)標(biāo)記數(shù)據(jù)包被分成k片，總共有kd片，則上述值為kd(ln(kd)+O(1))。因此，重建距離為d（包含d個(gè)路由器）的攻擊路徑所需要的數(shù)據(jù)包數(shù)N，具有期望值： 
E(N)<kd(ln(kd)+O(1)) 
1/dp(1-p)d-1≈k 
ln(kd)/p(1-p)d-1 
因此，該算法攻擊收斂包數(shù)與PPM邊標(biāo)記算法相同[2]。 
4.2     健壯性 
    在PPM算法[2]中，對(duì)于輸出長(zhǎng)度為h的散列隨機(jī)函數(shù)，受害者接受任一候選邊路徑的概率是1/2h。假設(shè)有m個(gè)攻擊者，則在一定距離d處，最壞情況下將有m個(gè)獨(dú)立的路由器。因此，在距離受害者d處，本不在實(shí)際攻擊路徑中的任意候選邊路徑被受害者接受（即：產(chǎn)生了正誤差[3]）的最大概率將是：1-(1-1/2h)n（其中n=mk）[2]。因?yàn)?，最壞情況下，距離d處將有mk個(gè)標(biāo)記分片。當(dāng)k值或m值很大時(shí)，這一概率也將變得很大。而HPPM算法使用的HMAC鑒別機(jī)制，可以十分有效地鑒別攻擊者偽造的邊路徑，將偽造的邊路徑從候選邊路徑中過(guò)濾掉，從而充分減小了算法產(chǎn)生的正誤差，提高了返回跟蹤的準(zhǔn)確性。 
4.3     路由器負(fù)擔(dān) 
由于采用HMAC和一次性口令機(jī)制來(lái)加密攻擊數(shù)據(jù)包中的邊標(biāo)記，因此中間路由器無(wú)須承擔(dān)PPM算法中每個(gè)路由器對(duì)其IP地址和已有邊標(biāo)記進(jìn)行的異或運(yùn)算(a○+b)○+b。而HMAC的計(jì)算過(guò)程簡(jiǎn)單，擴(kuò)展性也很好，當(dāng)發(fā)現(xiàn)或需要運(yùn)算速度更快或更安全的散列函數(shù)時(shí)，幾乎不用修改，就可以很容易地實(shí)現(xiàn)底層散列函數(shù)的替換，參閱文獻(xiàn)[6]。為了使數(shù)據(jù)包標(biāo)記過(guò)程更加安全，路由器需要周期性更換其用于加密邊標(biāo)記的私有密鑰。這個(gè)周期需要進(jìn)行適當(dāng)選擇，周期太短將給路由器帶來(lái)額外負(fù)擔(dān)，且不利于與受害者的同步，周期太長(zhǎng)又影響算法安全性，可以考慮把10秒作為其數(shù)量級(jí)[3]。 
4.4     受害者負(fù)擔(dān) 
由于使用了一次性口令機(jī)制，受害者需要獲取上游路由器加密邊標(biāo)記時(shí)使用的私有密鑰。一種可行的方法是，上游路由器將最新密鑰通過(guò)可信渠道發(fā)布（如：發(fā)布在網(wǎng)站上），受害者鑒別邊標(biāo)記真?zhèn)螘r(shí)，只需下載該路由器的最新密鑰，根據(jù)最新密鑰就能推算出該路由器以前加密邊標(biāo)記時(shí)使用的所有密鑰。這一過(guò)程可以在常數(shù)時(shí)間內(nèi)完成。 
4.5     算法局限性 
HPPM算法，要求受害者掌握網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，具有其上游路由器的地圖，這在一定程度上限制了算法的發(fā)展。受害者與中間路由器關(guān)于密鑰的同步過(guò)程還需要進(jìn)一步考慮。 
5．總結(jié)及未來(lái)工作 
本文描述了一種新的基于散列消息鑒別碼HMAC的隨機(jī)數(shù)據(jù)包標(biāo)記算法HPPM，該算法用于返回跟蹤DoS攻擊的攻擊源，能夠充分減小由于攻擊者偽造數(shù)據(jù)包標(biāo)記而帶來(lái)的誤差，提高了返回跟蹤的安全性和準(zhǔn)確性。然而，該算法還有不完善的地方，比如：與大多數(shù)返回跟蹤算法一樣，HPPM算法是一種反應(yīng)型跟蹤算法，即：只有確實(shí)發(fā)生了攻擊，才能進(jìn)行跟蹤。并且，該算法實(shí)際上無(wú)法跟蹤到真正的攻擊源，只能返回跟蹤到最接近攻擊源的邊界路由器。這些問(wèn)題都有待進(jìn)一步研究。 

參考文獻(xiàn) 
[1] W.Richard Stevens著，范建華 胥光輝 張濤 等譯，謝希仁校，《TCP/IP詳解——卷1：協(xié)議》[M]，第1版，北京：機(jī)械工業(yè)出版社，2000年4月，第24－27、111－112頁(yè). 
[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. 

最新評(píng)論