基于組群的有限路長破斷式破理機

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