基于組群的有限路長破斷式破理機(jī)

基于組群的有限路長破斷式破理機(jī)

1crowds的研究匿名通信是指在業(yè)務(wù)流程中隱藏通信關(guān)系的方式，防止監(jiān)聽者直接了解或泄露雙方的通信關(guān)系或通信關(guān)系。眾所周知,在當(dāng)前Internet上進(jìn)行數(shù)據(jù)傳輸,對(duì)信息本身的保密已有相應(yīng)的網(wǎng)絡(luò)服務(wù)和很好的數(shù)據(jù)加密算法,但一些協(xié)議所需的包頭信息很難隱藏,例如源地址和目的地址、包長等.攻擊者通過獲得通信雙方的地址,可以推斷出一些有價(jià)值的信息.例如根據(jù)傳輸信包的控制信息部分以及信息特征等可見部分,推斷出信息的來源、去向、數(shù)據(jù)量和一些隱含的意義.隨著一些特殊部門,例如軍事、國防、政府部門對(duì)網(wǎng)絡(luò)安全性要求的提高,以及民用上對(duì)網(wǎng)絡(luò)個(gè)人隱私要求的提高,迫切需要更安全的網(wǎng)絡(luò).匿名通信的一個(gè)重要目的就是隱藏通信雙方的身份或通信關(guān)系,從而實(shí)現(xiàn)網(wǎng)絡(luò)用戶的個(gè)人通信隱私及對(duì)涉密通信的更好的保護(hù).目前,有關(guān)網(wǎng)絡(luò)匿名通信技術(shù)的研究已越來越引起了網(wǎng)絡(luò)安全研究人員的重視.從目前的研究現(xiàn)狀來看,在基于因特網(wǎng)的匿名通信技術(shù)的研究方面,早期針對(duì)電子郵件系統(tǒng)提出了匿名郵件系統(tǒng),隨后又出現(xiàn)了一些有代表性的匿名通信協(xié)議和原型系統(tǒng),這些系統(tǒng)都在一定程度上保證了匿名連接,能抵抗一定程度的業(yè)務(wù)流分析.這些系統(tǒng)從技術(shù)上來說,可分為3類:第1類是基于簡單代理(Simple-Proxy)的系統(tǒng),Anonymizer,ProxyM(LucentPersonalWebAssistant,BellLabs)就屬于這一類.第2類是基于MIX概念的,MIX是指網(wǎng)絡(luò)上的一些特殊的機(jī)器,它完成存儲(chǔ)轉(zhuǎn)發(fā)功能,其基本作用是改變信息的編碼、順序和長度,使得用戶無法推知輸出與輸入之間的關(guān)系.即偷聽者即使在鏈路上獲得了MIX的輸入數(shù)據(jù)包和輸出數(shù)據(jù)包,也無法推知哪個(gè)是哪個(gè)的輸出,從而無法推知數(shù)據(jù)流的來源,使通信關(guān)系得到隱藏.DavidChaum的無法跟蹤電子郵件系統(tǒng)、OnionRouting,Freedom,WebMixes等是這類系統(tǒng)中有代表的實(shí)現(xiàn).第3類系統(tǒng)則是基于組群思想的,即由多個(gè)用戶形成一個(gè)組群,每個(gè)用戶使用一個(gè)代理,當(dāng)要傳輸數(shù)據(jù)包時(shí),代理在組內(nèi)成員的代理中任選一個(gè)將請(qǐng)求傳給它,通過這種轉(zhuǎn)發(fā)關(guān)系達(dá)到隱藏發(fā)送者的目的.Crowds就是其中有代表性的實(shí)現(xiàn).本文基于組群的思想提出了一種新的改進(jìn)的匿名通信協(xié)議,克服了Crowds系統(tǒng)中路徑長度無界的問題,保證了與Crowds同級(jí)別的匿名度,并且在相同路徑長度期望下與Crowds相比具有更好的抗泄密能力.本文的第2節(jié)簡單介紹了Crowds系統(tǒng)的特點(diǎn)和一些結(jié)論;第3節(jié)給出了有限長度匿名通信協(xié)議的實(shí)現(xiàn)思想和方法,證明了在固定路徑長度下,匿名度與路徑長度k、泄密者比例、組群大小之間的關(guān)系;第4節(jié)討論了路徑長度的隨機(jī)選取問題,給出了一種隨機(jī)選取的方法;第5節(jié)給出了在該方法下抗泄密能力的計(jì)算結(jié)果,并在相同路徑長度期望下與Crowds做了比較;第6桔是結(jié)論.2crowds的匿名特性AT&T的Crowds系統(tǒng)是基于組群的思想來實(shí)現(xiàn)匿名的.系統(tǒng)中每個(gè)成員用戶有一個(gè)代理,稱做jondo.當(dāng)用戶發(fā)出請(qǐng)求時(shí),jondo充當(dāng)請(qǐng)求代理,將請(qǐng)求以等概率隨機(jī)發(fā)給組中任一jondo.之后,路徑上每個(gè)jondo以概率決定是轉(zhuǎn)發(fā)給下一個(gè)jondo還是將請(qǐng)求直接給server,即發(fā)給組中任一jondo的概率是pf,發(fā)給server的概率是1-pf.從匿名特性來講,Crowds系統(tǒng)主要實(shí)現(xiàn)了發(fā)送者匿名.Crowds證明了在系統(tǒng)中有c個(gè)泄密者的情況下,只要滿足n≥Pf(c+1)/(Pf-1/2),路徑發(fā)送者就能做到probableinnocence(即猜測對(duì)象比其他對(duì)象更像發(fā)起者,但猜測對(duì)象是發(fā)起者的概率不比不是發(fā)起者的概率高).其中,n是組群中的成員數(shù),c是泄密者個(gè)數(shù),Pf是轉(zhuǎn)發(fā)概率.從Crowds的實(shí)現(xiàn)方式來看,路徑長度是沒有制約的,Crowds中采用概率的方法決定是傳給下一jondo還是傳給server.這使得路徑長度沒有上界,極端的情況下會(huì)達(dá)到無限長,可能造成請(qǐng)求應(yīng)答時(shí)間無限長(盡管概率非常小),使得Crowds的應(yīng)用受到服務(wù)質(zhì)量的限制.3根據(jù)組的有限長度，雙方應(yīng)簽署可靠的通信協(xié)議針對(duì)Crowds路徑長度的問題,我們提出了有限長度匿名通信協(xié)議,并對(duì)協(xié)議的匿名度進(jìn)行了分析.3.1ross公司的程序有限長度匿名通信協(xié)議的工作過程:當(dāng)用戶要發(fā)送信息時(shí),將請(qǐng)求交給它的用戶路由代理(routeproxy),代理以一定方式隨機(jī)產(chǎn)生一路徑長度(pathlength),然后任選一組員代理傳送,該轉(zhuǎn)接代理將pathlength減1,若pathlength不為0,該代理按同樣的方式將請(qǐng)求轉(zhuǎn)交給其他代理,直到某個(gè)代理發(fā)現(xiàn)pathlength降為0,就將請(qǐng)求直接交給接收方(server).下面是routeproxy的程序代碼描述.3.2正確的概率為了研究在保證發(fā)起者匿名的情況下,路徑長度、組的大小及允許泄密數(shù)之間的關(guān)系,我們先研究長度為K的情況下,通信協(xié)議的匿名度問題.假設(shè)組群共有n個(gè)routeproxy成員,在這些成員中有c個(gè)泄密者(compromisedmember),由于每個(gè)路徑上的成員都可以看到接收者的地址,所以接收者對(duì)于任何路徑上的routeproxy是暴露的,因此這里主要討論發(fā)起者是否能隱藏的問題.我們?nèi)匀焕肅rowds的討論模型,對(duì)于任何路徑上的routeproxy來說,它所知道的是它的前一個(gè)和后一個(gè)routeproxy,而它能做的猜測是它的前者比其他任何一個(gè)routeproxy更像發(fā)起者,假設(shè)路徑上有泄密者,泄密者猜測發(fā)起者的做法是路徑上的第1個(gè)泄密者的前者是發(fā)起者.這種假設(shè)是合理的,因?yàn)閺臄硨?duì)方來看第1個(gè)泄密者的前者最有可能是發(fā)起者.為了便于分析匿名度,我們先對(duì)一些事件作定義:I表示路徑上第1個(gè)泄密者的前者確實(shí)是發(fā)起者的事件;Hk,k≥1表示第1個(gè)泄密者在路徑上占據(jù)第k個(gè)位置的事件(假設(shè)發(fā)起者位置是0);Hk+=Hk∨Hk+1∨Hk+2∨…代表路徑上第k個(gè)位置及以后有泄密者的事件;P(I|Hk+)表示路徑上有泄密者的情況下,敵對(duì)方猜測正確的概率;p=(n-c)/n表示組群中非泄密者比例.p的大小可以用來衡量系統(tǒng)的抗泄密能力,在保證同樣匿名程度的前提下,所要求的p越大,表示抗泄密能力越弱,反之,抗泄密能力越強(qiáng).根據(jù)文獻(xiàn)中的關(guān)于匿名度的定義,如果P(I|H1+)≤1/2,則路徑發(fā)起者的匿名度是probabalinnocence(猜測對(duì)象比其他對(duì)象更像發(fā)起者,但猜測對(duì)象是發(fā)起者的概率不比不是發(fā)起者的概率高).定理1.當(dāng)組群成員數(shù)為n,非泄密者比例是p,路徑長度為k+1(即經(jīng)過k個(gè)中間路由代理.路徑長度是指從發(fā)起者到接收者之間所經(jīng)過的路段數(shù)),則當(dāng)滿足k-1∑i=0∑i=0k?1pi≥2+4n-2pi≥2+4n?2情況下,路徑發(fā)起者的匿名度可達(dá)到probableinnocence.證明.首先計(jì)算第1個(gè)泄密者位于路徑上第i個(gè)位置的概率,即路徑的前i-1次取到了非泄密者,第i個(gè)選到了泄密者的概率:Ρ(Ηi)=(n-cn)i-1cn=pi-1(1-p).P(Hi)=(n?cn)i?1cn=pi?1(1?p).第1個(gè)泄密者位于路徑上第2個(gè)位置或之后的概率:P(H2+)=k∑i=2∑i=2kP(Hi)=k∑i=2pi-1(1-p)=(1-p)(1-pk1-p-1)=p-pk.第1個(gè)泄密者位于路徑上第1個(gè)位置或之后的概率:P(H1+)=k∑i=1P(Hi)=k∑i=1pi-1(1-p)=(1-p)(1-pk1-p)=1-pk.當(dāng)?shù)?個(gè)泄密者位于路徑上第1個(gè)位置時(shí),它的前一個(gè)肯定是發(fā)起者,事件I是成立的,即H1→I.所以條件概率P(I|H1)=1.但當(dāng)?shù)?個(gè)泄密者位于路徑上第2個(gè)位置或之后時(shí),它的前一個(gè)是發(fā)起者的概率是1/(n-c),因?yàn)槌霈F(xiàn)任何非泄密成員的概率是相等的,即P(I|H2+)=1/(n-c).所以:Ρ(Ι)=Ρ(Η1)Ρ(Ι|Η1)+Ρ(Η2+)Ρ(Ι|Η2+)=cn+(p-pk)1n-c=1-p+(p-pk)1np?Ρ(Ι|Η1+)=Ρ(Ι∧Η1+)Ρ(Η1+)=Ρ(Ι)Ρ(Η1+)=1-p+(p-pk)1np1-pk=1-p+(1-pk-1)1n1-pk.(1)又因?yàn)閜≤1,所以1-pk-1<1-pk,所以:Ρ(Ι|Η1+)＜1-p+(1-pk)1n1-pk=1k-1∑i=0Ρ?i+1n.所以,當(dāng)k-1∑i=0pi≥2+4n-2時(shí),P(I|H1+)≤1/2,即路徑發(fā)起者的匿名度可達(dá)到probableinnocence.證畢.從定理我們可以看到路徑長度、組群成員數(shù)及非泄密者比例對(duì)發(fā)送者匿名度的影響.k,n,p中任何一個(gè)值增加,能使不等式更容易滿足,從而更容易保證發(fā)起者的匿名度達(dá)到probableinnocence.當(dāng)路徑k趨于∞時(shí),上述不等式為∞∑i=0pi≥2+4n-2?11-p≥2+4n-2?p≥12+1n＞12?由此可以得到結(jié)論,無論路徑長度取多長、組員數(shù)取多大,要使發(fā)起者的匿名度達(dá)到probableinnocence,非泄密者比例必須大于1/2.以p=(n-c)/n代入得n≥2(c+1),這個(gè)結(jié)論與Crowds中Pf取1(意味著路徑無限長)時(shí)的匿名條件n≥(Pf/(Pf-1/2))(c+1)=2(c+1)是一致的.表1計(jì)算了在n,p一定的條件下,要使發(fā)送者匿名所需的最短路段數(shù)以及在n一定的情況下能達(dá)到的最小p值和相應(yīng)路段數(shù).例如當(dāng)組員數(shù)為20時(shí),非泄密比例在85%以上時(shí),路段數(shù)為4(k=3)即可滿足發(fā)送者probableinnocence,而要使系統(tǒng)中非泄密者降到65%(即容忍泄密者比例為35%),路段數(shù)至少為5,而當(dāng)路段數(shù)為6時(shí),非泄密者比例可以降到60%.在組員數(shù)為20情況下,能達(dá)到的p的下界是56%,此時(shí)要求路段數(shù)至少是8(即k=7).4路徑長度隨機(jī)取定值得注意的是,由于每個(gè)路由代理都知道路徑長度的取值規(guī)則,有限路徑長度可能給攻擊者提供了反向跟蹤發(fā)起者的線索,從而縮小猜測范圍.當(dāng)取路徑長度為固定值M時(shí),則如果某個(gè)泄密者得到數(shù)據(jù)包的pathlength為M-1時(shí),該泄密者能確切地判定它的前者是發(fā)起者,另外,泄密者可以根據(jù)pathlength的值知道反向跟蹤M-pathlength條鏈路就能找到發(fā)起者.這對(duì)發(fā)起者匿名是極為不利的,因此,不能取路徑長度為固定值.若假設(shè)路徑長度在某一區(qū)間(M1,M2)等概率隨機(jī)取值,當(dāng)某個(gè)泄密者得到數(shù)據(jù)包的pathlength為M2-1時(shí),該泄密者仍然能確切地判定它的前者是發(fā)起者,而這種情況的概率是1/(M2-M1+1).但隨機(jī)取值帶來了一個(gè)好處,即路徑上其他代理無法確切知道路徑長度,因此無法從pathlength知道反向跟蹤確切路段數(shù).我們發(fā)現(xiàn)只要路徑長度在有限范圍內(nèi)取值,當(dāng)取到區(qū)間上界時(shí),路徑上它的后者總能確切地知道前者為發(fā)起者.因此在取路徑長度時(shí),我們只能設(shè)法使取到上界的概率盡量小,從而使確切知道前者為發(fā)起者的概率變小.因此,我們定義函數(shù)W(k)作為取值k的權(quán)值,k的取值范圍是(M1,M2),W(k)=1(mid-k+1)2,當(dāng)k≤mid時(shí),W(k)=1(k+1-mid)2,當(dāng)k>mid時(shí),其中,mid∈(M1,M2),代表權(quán)值最大的k.因此,取到路徑長度k的概率是ρ(k)=W(k)Μ2∑k=Μ1W(k).這時(shí),由式(1):根據(jù)固定k情況下的測試結(jié)果,我們發(fā)現(xiàn),當(dāng)k=2時(shí),是達(dá)不到發(fā)送方匿名要求的,我們可以取M1≥3.同時(shí),表1的計(jì)算數(shù)據(jù)表明,盡管路徑的增長可以使得系統(tǒng)抗泄密性提高,但對(duì)于一定大小的組群,p有一個(gè)下界,接近下界時(shí),路段數(shù)繼續(xù)增加,抗泄密能力p基本不變.一般情況下,k在10以內(nèi)就可以使p達(dá)到最小.因此我們考慮取M2在10～20之間.5“雙路徑”期望下的抗泄漏能力分析為了與Crowds進(jìn)行比較,我們讓k在(3,20)間取值,取mid=3,4,5,6,7,8.然后比較在同樣平均路徑長度下,兩者在保證匿名情況下的抗泄密能力,比較結(jié)果如表2所示.每個(gè)路徑長度期望下給出了兩列,分別是有限長度協(xié)議和Crowds協(xié)議在該期望值下要達(dá)到匿名條件對(duì)p的要求.其中路徑長度期望值可以由公式Μ2∑k=Μ1(k+1)×ρ(k)計(jì)算.根據(jù)文獻(xiàn)中路徑長度期望值公式可以反推出相同路徑長度期望值下的Pf,再由匿名條件不等式可以得到要求的p值.從表2的計(jì)算數(shù)據(jù)可以看出,在相同路徑長度期望情況下要達(dá)到發(fā)送者匿名,有限長度協(xié)議要求的p值小于Crowds系統(tǒng).即有限長度協(xié)議與Crowds系統(tǒng)相比具有更好的抗泄密能力.這可以解釋為,在上述有限長度協(xié)議中,根據(jù)固定長度情況下的測試結(jié)果,對(duì)路徑長度在一定范圍內(nèi)做了制約,并且在分布概率上做了有意的調(diào)整.在選取路徑長度時(shí),一方面去掉了不能滿足發(fā)送者匿名的長度為3的情況(k=2).另一方面,根據(jù)路徑長度在增長到一定長度情況下,繼續(xù)增長對(duì)匿名度影響很微小的測試結(jié)果,路徑長度選擇了20為上界.在概率分布上,按照在固定長度下的測試結(jié)果,分別取k=3～8為最大概率.但必須指出的是,有限長度路由協(xié)議的一個(gè)不足就是無法避免當(dāng)k取到上界時(shí),它的后者若是泄密者,可以準(zhǔn)確地判斷前者是發(fā)起者.我