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

摘要: 針對互聯網上日益猖獗的拒絕服務攻擊（DoS），分析了傳統的隨機數據包標記算法的性能缺陷，提出一種新的基于散列消息鑒別碼的返回跟蹤算法HPPM，通過分析其性能指標，說明該算法提高了返回跟蹤DoS攻擊的效率和準確性。 
感謝幫過我的幾個高手袁哥[nsfocus], sunwear[E.S.T] , isno[xfocus] , scz[nsfocus] 
1．引言 
    拒絕服務攻擊，簡稱DoS(Denial-of-Service)，是一種常見的黑客攻擊行為。這種攻擊行為通過發(fā)送帶有虛假源地址的數據包請求，使網絡服務器充斥大量等待回復的信息,消耗網絡帶寬或系統資源,使網絡或系統服務負載過重，服務質量下降，直至癱瘓而停止正常的服務。有時,黑客為了提高攻擊的效果,往往會聯合多個攻擊站點向受害者發(fā)動進攻。由于DoS攻擊易于實施、難于防御，而且很難返回跟蹤攻擊源，使之成為一個嚴重侵擾網絡服務提供商、政府機關和金融證券等機構正常運作的安全問題。 
2．IP返回跟蹤相關技術 
為了徹底消除DoS攻擊，必須追根溯源，找到真正的攻擊機器或攻擊者。這種方法被稱為IP返回追蹤技術（IP Traceback）。由于DoS攻擊者在發(fā)送攻擊數據包時往往會偽造源地址，使得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地址的一部分隨機標記經過它的數據包。當發(fā)生DoS攻擊時，受害者根據其收到的攻擊數據包中的標記信息，重建攻擊路徑。使用PPM算法，路由器負擔較小，采用標記邊壓縮和分片技術大大降低了額外的網絡流量。而且，該方法可以在攻擊結束以后對攻擊源進行追蹤。PPM對單源DoS攻擊，有較好的追蹤效果。 
但是，由于其自身缺陷，PPM算法無法很好地返回跟蹤DDoS攻擊（Distributed–Denial–of–Service）。首先，由于路由器以概率p隨機標記數據包，就給攻擊者以可乘之機，將偽造的標記信息寫入攻擊數據包的報頭中（一般是Identifier字段），只要該數據包一直不被其經過的路由器標記，直至目標主機，就能在攻擊路徑中偽造一條邊路徑，阻止受害者跟蹤真正的攻擊源。其次，為了節(jié)省存儲空間，減小網絡負擔，PPM采用了邊標記壓縮和分片存儲技術。但是，分片存儲可能導致受害者將本不屬于同一數據包的分片組合在一起，從而生成錯誤的邊路徑。而標記的邊壓縮方法主要依據(a○+b)○+b=a(a、b分別是攻擊路徑上相鄰兩個路由器的IP地址)，將顯著加劇這一效果，進一步生成錯誤的攻擊路徑。當發(fā)生DDoS攻擊時，由于同一距離存在多個攻擊者，而產生爆炸效果，影響將更加嚴重[2]。 
3.2     HPPM算法 
針對PPM算法的上述缺陷，我們提出了一種基于散列消息鑒別碼HMAC的數據包標記算法HPPM，并采用新的標記重疊分片策略，以提高IP返回跟蹤DoS攻擊（特別是DDoS攻擊）的性能。 
在該算法中，路由器Ri以概率p隨機對經過它的數據包進行標記，標記信息包括Ri的IP地址和下一跳路由器Rj的IP地址，總共64位。為了節(jié)省標記存儲空間，不給用戶帶來過多影響，算法使用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來鑒別消息的真?zhèn)?；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生成，并具有以下規(guī)則：Kij-1 =f(Kij)。由于函數f是單向的，所以由最新的密鑰Kij可以依次推出在它以前生成的所有Kij-1、Kij-2……Ki0，但根據已有的密鑰卻推不出下一個密鑰，這就確保了他人無法偽造Ri的密鑰。路由器Ri每經過一段固定的時間間隔，就根據上述方法更換一次私有密鑰Ki，然后將剛剛停止使用的密鑰通過可靠的方式發(fā)布出去。當數據包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攻擊時，受害者開始收集標記分片，并記錄其到達時間。我們假設攻擊者發(fā)送大量的攻擊數據包，那么受害者就能收集到足夠多的標記分片，然后根據分片的偏移值，將具有相同攻擊距離d和hmac值的分片重組，生成邊路徑，進而生成整個攻擊路徑。由于攻擊者可能偽造標記數據包，干擾返回跟蹤過程，因此需要對生成的邊路徑鑒別真?zhèn)巍＞唧w鑒別方法是：受害者與路由器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的路徑上最遠處路由器發(fā)來的標記數據包的概率是：p(1-p)d-1。保守假設受害者收到該路徑上任一路由器發(fā)來標記數據包的概率都與最遠距離d處相同，并且相互獨立，因此受害者收到的任一數據包被該數據包途經路徑上某些路由器標記過的概率，將具有期望值：1/dp(1-p)d-1。 
根據coupon-collector問題[8]，受害者收到的從距離為d的路徑上發(fā)來的數據包中，包括所有d個路由器中每個路由器發(fā)出的至少一個標記數據包，所需要接收的數據包數，具有以下期望值：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的計算過程簡單，擴展性也很好，當發(fā)現或需要運算速度更快或更安全的散列函數時，幾乎不用修改，就可以很容易地實現底層散列函數的替換，參閱文獻[6]。為了使數據包標記過程更加安全，路由器需要周期性更換其用于加密邊標記的私有密鑰。這個周期需要進行適當選擇，周期太短將給路由器帶來額外負擔，且不利于與受害者的同步，周期太長又影響算法安全性，可以考慮把10秒作為其數量級[3]。 
4.4     受害者負擔 
由于使用了一次性口令機制，受害者需要獲取上游路由器加密邊標記時使用的私有密鑰。一種可行的方法是，上游路由器將最新密鑰通過可信渠道發(fā)布（如：發(fā)布在網站上），受害者鑒別邊標記真?zhèn)螘r，只需下載該路由器的最新密鑰，根據最新密鑰就能推算出該路由器以前加密邊標記時使用的所有密鑰。這一過程可以在常數時間內完成。 
4.5     算法局限性 
HPPM算法，要求受害者掌握網絡拓撲結構，具有其上游路由器的地圖，這在一定程度上限制了算法的發(fā)展。受害者與中間路由器關于密鑰的同步過程還需要進一步考慮。 
5．總結及未來工作 
本文描述了一種新的基于散列消息鑒別碼HMAC的隨機數據包標記算法HPPM，該算法用于返回跟蹤DoS攻擊的攻擊源，能夠充分減小由于攻擊者偽造數據包標記而帶來的誤差，提高了返回跟蹤的安全性和準確性。然而，該算法還有不完善的地方，比如：與大多數返回跟蹤算法一樣，HPPM算法是一種反應型跟蹤算法，即：只有確實發(fā)生了攻擊，才能進行跟蹤。并且，該算法實際上無法跟蹤到真正的攻擊源，只能返回跟蹤到最接近攻擊源的邊界路由器。這些問題都有待進一步研究。 

參考文獻 
[1] W.Richard Stevens著，范建華 胥光輝 張濤 等譯，謝希仁校，《TCP/IP詳解——卷1：協議》[M]，第1版，北京：機械工業(yè)出版社，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. 

最新評論