基于DoS攻擊的隨機(jī)數(shù)據(jù)包標(biāo)記源跟蹤算法

1、原創(chuàng)基于DoS攻擊的隨機(jī)數(shù)據(jù)包標(biāo)記源跟蹤算法文章標(biāo)題:原創(chuàng)基于DoS攻擊的隨機(jī)數(shù)據(jù)包標(biāo)記源跟蹤算法頂部 饑餓加菲貓 發(fā)布于:2005-11-0101:39 樓主原創(chuàng)基于DoS攻擊的隨機(jī)數(shù)據(jù)包標(biāo)記源跟蹤算法文章作者：饑餓加菲貓（QQ120474）摘要:針對互聯(lián)網(wǎng)上Ri益猖獗的拒絕服務(wù)攻擊（DoS），分析了傳統(tǒng)的隨機(jī)數(shù)據(jù)包標(biāo)記算法的性能缺陷，提出一種新的基于散列消息鑒別碼的返回跟蹤算法HPPM，通過分析其性能指標(biāo)，說明該算法提高了返回跟蹤DoS攻擊的效率和準(zhǔn)確性。1引言 拒絕服務(wù)攻擊，簡稱DoS(Denial-of-Service)，是一種常見的黑客攻擊行為。這種攻擊行為通過發(fā)送帶有虛假源地址的數(shù)

2、據(jù)包請求，使網(wǎng)絡(luò)服務(wù)器充斥大量等待回復(fù)的信息,消耗網(wǎng)絡(luò)帶寬或系統(tǒng)資源,使網(wǎng)絡(luò)或系統(tǒng)服務(wù)負(fù)載過重，服務(wù)質(zhì)量下降，直至癱瘓而停止正常的服務(wù)。有時,黑客為了提高攻擊的效果,往往會聯(lián)合多個攻擊站點(diǎn)向受害者發(fā)動進(jìn)攻。由于DoS攻擊易于實(shí)施、難于防御，而且很難返回跟蹤攻擊源，使之成為一個嚴(yán)重侵?jǐn)_網(wǎng)絡(luò)服務(wù)提供商、G0vernment機(jī)關(guān)和金融證券等機(jī)構(gòu)正常運(yùn)作的安全問題。2IP返回跟蹤相關(guān)技術(shù)為了徹底消除DoS攻擊，必須追根溯源，找到真正的攻擊機(jī)器或攻擊者。這種方法被稱為IP返回追蹤技術(shù)（IPTraceback）。由于DoS攻擊者在發(fā)送攻擊數(shù)據(jù)包時往往會偽造源地址，使得IP返回追蹤的難度很大。常用的IP返回

3、追蹤方法有：入口過濾（IngressFiltering）、連接測試（LinkTesting）、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)入過濾 中等 低 中等 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ù)的性能比較23HPP

4、MIP返回跟蹤算法 3.1 PPM算法（ProbabilisticPacketMarking）隨機(jī)數(shù)據(jù)包標(biāo)記算法PPM的主要原理如下：路由器以一定的概率p（通常是1/25）2，用其IP地址或IP地址的一部分隨機(jī)標(biāo)記經(jīng)過它的數(shù)據(jù)包。當(dāng)發(fā)生DoS攻擊時，受害者根據(jù)其收到的攻擊數(shù)據(jù)包中的標(biāo)記信息，重建攻擊路徑。使用PPM算法，路由器負(fù)擔(dān)較小，采用標(biāo)記邊壓縮和分片技術(shù)大大降低了額外的網(wǎng)絡(luò)流量。而且，該方法可以在攻擊結(jié)束以后對攻擊源進(jìn)行追蹤。PPM對單源DoS攻擊，有較好的追蹤效果。但是，由于其自身缺陷，PPM算法無法很好地返回跟蹤DDoS攻擊（DistributedDenialofService）。首

5、先，由于路由器以概率p隨機(jī)標(biāo)記數(shù)據(jù)包，就給攻擊者以可乘之機(jī)，將偽造的標(biāo)記信息寫入攻擊數(shù)據(jù)包的報(bào)頭中（一般是Identifier字段），只要該數(shù)據(jù)包一直不被其經(jīng)過的路由器標(biāo)記，直至目標(biāo)主機(jī)，就能在攻擊路徑中偽造一條邊路徑，阻止受害者跟蹤真正的攻擊源。其次，為了節(jié)省存儲空間，減小網(wǎng)絡(luò)負(fù)擔(dān)，PPM采用了邊標(biāo)記壓縮和分片存儲技術(shù)。但是，分片存儲可能導(dǎo)致受害者將本不屬于同一數(shù)據(jù)包的分片組合在一起，從而生成錯誤的邊路徑。而標(biāo)記的邊壓縮方法主要依據(jù)(a+b)+b=a(a、b分別是攻擊路徑上相鄰兩個路由器的IP地址)，將顯著加劇這一效果，進(jìn)一步生成錯誤的攻擊路徑。當(dāng)發(fā)生DDoS攻擊時，由于同一距離存在多個攻擊

6、者，而產(chǎn)生爆炸效果，影響將更加嚴(yán)重2。3.2 HPPM算法針對PPM算法的上述缺陷，我們提出了一種基于散列消息鑒別碼HMAC的數(shù)據(jù)包標(biāo)記算法HPPM，并采用新的標(biāo)記重疊分片策略，以提高IP返回跟蹤DoS攻擊（特別是DDoS攻擊）的性能。在該算法中，路由器Ri以概率p隨機(jī)對經(jīng)過它的數(shù)據(jù)包進(jìn)行標(biāo)記，標(biāo)記信息包括Ri的IP地址和下一跳路由器Rj的IP地址，總共64位。為了節(jié)省標(biāo)記存儲空間，不給用戶帶來過多影響，算法使用IPv4首部中的16位標(biāo)識符字段（Identifier），1位閑置的標(biāo)志位（Flags）1和13位片位移字段（據(jù)統(tǒng)計(jì)，目前少于0.25%的數(shù)據(jù)包需要分片2），以及一般很少使用的8位TO

7、S字段（Type-of-Service）1,總共38位，來存儲標(biāo)記分片信息。64位標(biāo)記信息被分成k8片，每片占用8位，分片偏移值占log2k3位，Ri到目標(biāo)主機(jī)的距離值占5位（25131跳，適用于目前絕大多數(shù)網(wǎng)絡(luò)2），用于驗(yàn)證的HMAC值占22位。散列消息鑒別碼，簡稱HMAC，是一種基于消息鑒別碼MAC（MessageAuthenticationCode）的鑒別機(jī)制。使用HMAC時,消息通訊的雙方，通過驗(yàn)證消息中加入的鑒別密鑰K來鑒別消息的真?zhèn)危籋MAC還引人了一個散列函數(shù)H，對消息進(jìn)行加密，進(jìn)一步確保消息鑒別的安全性和有效性。HMAC的具體計(jì)算方法如下：HMAC(M,K)=H(K+opad,

8、H(K+ipad,M)其中，ipad=字0x36重復(fù)B次，opad=字0x5C重復(fù)B次，M=待加密的消息字符串，B=消息字符串的字長。關(guān)于HMAC更詳細(xì)的內(nèi)容，請參考文獻(xiàn)RFC21046。在HPPM算法中，我們采用一次性口令機(jī)制OTP（One-TimePassword）45，先讓每個路由器Ri生成一組私有密鑰序列Kij（j=0、1、2）。這組私有密鑰序列通過單向散列函數(shù)f生成，并具有以下規(guī)則：Kij-1=f(Kij)。由于函數(shù)f是單向的，所以由最新的密鑰Kij可以依次推出在它以前生成的所有Kij-1、Kij-2Ki0，但根據(jù)已有的密鑰卻推不出下一個密鑰，這就確保了他人無法偽造Ri的密鑰。路由器

9、Ri每經(jīng)過一段固定的時間間隔，就根據(jù)上述方法更換一次私有密鑰Ki，然后將剛剛停止使用的密鑰通過可靠的方式發(fā)布出去。當(dāng)數(shù)據(jù)包P通過Ri時，Ri使用HMAC函數(shù)H和當(dāng)前私有密鑰Ki，對Ri的IP地址和P的目的地址進(jìn)行加密，即：H(M,Ki),其中，M=IP(Ri)+IP(destination)。具體的標(biāo)記步驟如下：MarkingprocedureatrouterRi:letmbethemarkingmassageip(Ri)+ip(Rj)letkbethenumberoffragmentsinmletHbetheHMACfunctionletKibetheprivatekeyofRiatcurr

10、enttimeinterval foreachpacketwletxbearandomnumberfrom0.1)ifx<pthenlethmacbetheHMACvalueofIP(Ri)+IP(w.destination) hmac:=H(IP(Ri)+IP(w.destination),Ki)letobearandomintegerfrom0.k-1letfbethefragmentofmatoffsetowritefintow.fragwrite0intow.distancewriteointow.offsetwritehmacintow.hmacelseincrementw.d

11、istance以下將討論受害者重建攻擊路徑的過程。當(dāng)受到DoS攻擊時，受害者開始收集標(biāo)記分片，并記錄其到達(dá)時間。我們假設(shè)攻擊者發(fā)送大量的攻擊數(shù)據(jù)包，那么受害者就能收集到足夠多的標(biāo)記分片，然后根據(jù)分片的偏移值，將具有相同攻擊距離d和hmac值的分片重組，生成邊路徑，進(jìn)而生成整個攻擊路徑。由于攻擊者可能偽造標(biāo)記數(shù)據(jù)包，干擾返回跟蹤過程，因此需要對生成的邊路徑鑒別真?zhèn)?。具體鑒別方法是：受害者與路由器Ri（服務(wù)提供商）聯(lián)系，取得Ri最新的私有密鑰K，然后根據(jù)K和數(shù)據(jù)包P到達(dá)時間（需要考慮延時），使用相同散列函數(shù)f計(jì)算出Ri標(biāo)記P時使用的私有密鑰Ki；再根據(jù)Ri和自身的IP地址，以及Ki，計(jì)算出HMAC

12、值與標(biāo)記數(shù)據(jù)包中的HMAC值進(jìn)行比較，一致則說明該邊路徑有效，否則將其丟棄。重建攻擊路徑的具體過程如下：Pathreconstructionprocedureatvictimv:letFragTblbeatableoftuples(frag,offset,distance,hmac,time)letGbeatreewithrootvletedgesinGbetuples(start,end,distance,hmac,time)letmaxd:=0letlast:=vforeachpacketwfromattackerletrectimebethetimewhenvreceivesthepac

13、ketwFragTbl.Insert(w.frag,w.offset,w.distance,w.hmac,rectime)ifw.distance>maxdthenmaxd:=w.distanceford:=0tomaxdforallorderedcombinationsoffragmentshavingthesamehmacvalueatdistancedconstructedgez(IP(Ri),IP(Rj),w.distance,w.hmac,rectime)/StartofHMACauthenticationletKbetheprivatekeyofRiatcurrenttime

14、intervalletKibetheprivatekeyofRiatthetimeintervalwhenRimarkedthepacketwletfbethefunctiontogetKiaccordingtoKandrectimeKi:=f(K,rectime)ifw.hmac=H(IP(Ri)+IP(v),Ki)insertedgez(IP(Ri),IP(Rj),w.distance)intoG /EndofHMACauthenticationremoveanyedge(x,y,d,hmac,time)withddistancefromxtovinGextractpath(Ri.Rj)b

15、yenumeratingacyclicpathsinG4HPPM算法性能分析4.1 攻擊收斂包數(shù)根據(jù)2，受害者收到距離為d的路徑上最遠(yuǎn)處路由器發(fā)來的標(biāo)記數(shù)據(jù)包的概率是：p(1-p)d-1。保守假設(shè)受害者收到該路徑上任一路由器發(fā)來標(biāo)記數(shù)據(jù)包的概率都與最遠(yuǎn)距離d處相同，并且相互獨(dú)立，因此受害者收到的任一數(shù)據(jù)包被該數(shù)據(jù)包途經(jīng)路徑上某些路由器標(biāo)記過的概率，將具有期望值：1/dp(1-p)d-1。根據(jù)coupon-collector問題8，受害者收到的從距離為d的路徑上發(fā)來的數(shù)據(jù)包中，包括所有d個路由器中每個路由器發(fā)出的至少一個標(biāo)記數(shù)據(jù)包，所需要接收的數(shù)據(jù)包數(shù)，具有以下期望值：1d/(d-1)+d/(d

16、-2)+d/2+d=d(ln(d)+O(1)?？紤]到每個標(biāo)記數(shù)據(jù)包被分成k片，總共有kd片，則上述值為kd(ln(kd)+O(1)。因此，重建距離為d（包含d個路由器）的攻擊路徑所需要的數(shù)據(jù)包數(shù)N，具有期望值：E(N)<kd(ln(kd)+O(1)1/dp(1-p)d-1kln(kd)/p(1-p)d-1因此，該算法攻擊收斂包數(shù)與PPM邊標(biāo)記算法相同2。4.2 健壯性 在PPM算法2中，對于輸出長度為h的散列隨機(jī)函數(shù)，受害者接受任一候選邊路徑的概率是1/2h。假設(shè)有m個攻擊者，則在一定距離d處，最壞情況下將有m個獨(dú)立的路由器。因此，在距離受害者d處，本不在實(shí)際攻擊路徑中的任意候選邊路徑被

17、受害者接受（即：產(chǎn)生了正誤差3）的最大概率將是：1-(1-1/2h)n（其中n=mk）2。因?yàn)?，最壞情況下，距離d處將有mk個標(biāo)記分片。當(dāng)k值或m值很大時，這一概率也將變得很大。而HPPM算法使用的HMAC鑒別機(jī)制，可以十分有效地鑒別攻擊者偽造的邊路徑，將偽造的邊路徑從候選邊路徑中過濾掉，從而充分減小了算法產(chǎn)生的正誤差，提高了返回跟蹤的準(zhǔn)確性。4.3 路由器負(fù)擔(dān)由于采用HMAC和一次性口令機(jī)制來加密攻擊數(shù)據(jù)包中的邊標(biāo)記，因此中間路由器無須承擔(dān)PPM算法中每個路由器對其IP地址和已有邊標(biāo)記進(jìn)行的異或運(yùn)算(a+b)+b。而HMAC的計(jì)算過程簡單，擴(kuò)展性也很好，當(dāng)發(fā)現(xiàn)或需要運(yùn)算速度更快或更安全的散列

18、函數(shù)時，幾乎不用修改，就可以很容易地實(shí)現(xiàn)底層散列函數(shù)的替換，參閱文獻(xiàn)6。為了使數(shù)據(jù)包標(biāo)記過程更加安全，路由器需要周期性更換其用于加密邊標(biāo)記的私有密鑰。這個周期需要進(jìn)行適當(dāng)選擇，周期太短將給路由器帶來額外負(fù)擔(dān)，且不利于與受害者的同步，周期太長又影響算法安全性，可以考慮把10秒作為其數(shù)量級3。4.4 受害者負(fù)擔(dān)由于使用了一次性口令機(jī)制，受害者需要獲取上游路由器加密邊標(biāo)記時使用的私有密鑰。一種可行的方法是，上游路由器將最新密鑰通過可信渠道發(fā)布（如：發(fā)布在網(wǎng)站上），受害者鑒別邊標(biāo)記真?zhèn)螘r，只需下載該路由器的最新密鑰，根據(jù)最新密鑰就能推算出該路由器以前加密邊標(biāo)記時使用的所有密鑰。這一過程可以在常數(shù)時間內(nèi)

19、完成。4.5 算法局限性HPPM算法，要求受害者掌握網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，具有其上游路由器的地圖，這在一定程度上限制了算法的發(fā)展。受害者與中間路由器關(guān)于密鑰的同步過程還需要進(jìn)一步考慮。5總結(jié)及未來工作本文描述了一種新的基于散列消息鑒別碼HMAC的隨機(jī)數(shù)據(jù)包標(biāo)記算法HPPM，該算法用于返回跟蹤DoS攻擊的攻擊源，能夠充分減小由于攻擊者偽造數(shù)據(jù)包標(biāo)記而帶來的誤差，提高了返回跟蹤的安全性和準(zhǔn)確性。然而，該算法還有不完善的地方，比如：與大多數(shù)返回跟蹤算法一樣，HPPM算法是一種反應(yīng)型跟蹤算法，即：只有確實(shí)發(fā)生了攻擊，才能進(jìn)行跟蹤。并且，該算法實(shí)際上無法跟蹤到真正的攻擊源，只能返回跟蹤到最接近攻擊源的邊界路由器。這些問題都有待進(jìn)一步研究。參考文獻(xiàn)1W.RichardStevens著，范建華胥光輝張濤等譯，謝希仁校，TCP/IP詳解卷1：協(xié)議M，第1版，北京：機(jī)械工業(yè)出版社，2000年4月，第2427、111112頁.4N.Haller,TheS/KEYOne-TimePasswordSystemZ,InternetRFC1760,February1995.5N.Haller,AOne-TimePasswordSystemZ,InternetRFC