基于攻擊方的網絡匿名性概率分析

虎 勇，李鑌劍，陳紫煜，茍俊卿，陳瑞東

(1.官地水力發電廠,四川 西昌 615000；2.北京信息科技大學 自動化學院,北京 100192；3.電子科技大學 網絡空間與安全研究院，四川 成都 611731)

0 引言

隨著網絡的快速發展，人們越來越注重在互聯網上的個人隱私，一些具有嚴格隱私要求的應用程序需求(如網頁瀏覽、即時消息傳遞和電子投票等)，迅速增加了研究人員和從業人員對開發可靠隱私增強技術 (例如匿名通信網絡) 的興趣。設計此類網絡的主要目的是通過在公開網絡上建立匿名通信來隱藏通信方(即消息的發送方或接收方)的真實身份。自1981年Chaum[1]提出不可追蹤郵件問題和Mix解決方法,設計了匿名傳輸的新概念。對匿名系統提供的匿名性進行量化，從概念提出開始一直就是重要挑戰，Chaum[2]提出利用匿名集大小來度量匿名性。Reiter和Rubin[3]從用戶角度單獨考慮匿名性，從絕對隱私到可證明暴露，提出6級匿名。Sarjantov[4]和Diaz[5]利用熵的方法來度量匿名性。關永等[6]利用攻擊方角度對匿名性進行度量，提供了匿名性度量的新角度[7]。迄今為止，此類網絡所提供最重要的匿名屬性是消息發送方的匿名性，它們通過重路由機制利用多個中間節點來隱藏消息發送方的真實身份，但要實現完全匿名的交流很難[8]。針對匿名通信問題，提出了不同解決方案，這些方案可為用戶提供多少匿名性？為了評判匿名通信網絡給用戶帶來了多少安全性，有必要通過一些定量指標來評測此類網絡所提供的匿名度，即希望可以通過一些指標區分可靠的匿名通信網絡和不可靠的匿名通信網絡[9]。為評估重路由機制匿名通信網絡的匿名度，本文提出一種用于匿名通信網絡安全性分析的概率模型。

1 建模

在建模過程之前，需要聲明潛在的假設，以便能夠基于這些假設構建模型。因為并不希望該度量方法僅局限于特定網絡，其應該適用于各類匿名通信網絡，故假設時考慮更一般化的條件。而從攻擊方來評估匿名網絡，必須同時考慮匿名通信網絡和攻擊者兩方面。

1.1 匿名通信網絡子模型

一個典型的匿名通信網絡由多個節點組成，這些節點之間彼此協作形成從源到目的地的隨機路徑，以便向用戶提供匿名屬性。在本文設置中，匿名通信網絡的主要任務是隱藏消息發送者的身份。這項研究處理的是“多跳”匿名通信網絡，而不是“單跳” 網絡。從匿名的角度來看，單跳網絡只有一個中繼節點，重路由路徑沒有不確定性，達不到匿名通信的需求。

為研究“多跳”網絡[10-12]，假設有一組潛在發送者、一組中繼節點和一個特定的接受者，其中S代表發送者，I代表中繼節點，R代表接受者。由于本文只對量化發送者的匿名感興趣，同時又不失一般性，假定接收方已被攻擊者所控制。在許多重要的應用中，這是一個現實的假設[13]。例如，考慮諸如匿名電子郵件和網頁瀏覽等應用程序,大多數訪問特殊網頁的人都希望對網頁服務器(即接收者)隱藏他們的身份(即IP地址)。在這種情況下，網絡服務器被假定為受到威脅[14]。

將匿名通信網絡建模為無向圖G=(V,E)，其中V=S∪I∪R，是潛在發送者、中間節點和接收者的頂點集，E?V×V是這些頂點對的邊集，代表頂點之間的直接聯系[15]。本文更傾向通過鄰接矩陣來表示的相應圖G(為方便起見，假設S∩I=φ)。假設有n個中間節點和m個潛在發送者，并且匿名通信網絡的中間節點被標記為1,2,…,n,并且潛在發送者被標記為n+1,n+2,…,n+m。I和S的集合定義如下:I={I1，I2，…，In}，S={sn+1，sn+2，…，sn+m}。

圖1展示了一個無向圖，表示由5個中間節點、3個潛在發送者和1個接收機組成的匿名通信網絡。假設在任何2個頂點之間都有一條邊，為簡單起見，在圖中未示出邊緣。

圖1 匿名通信網絡示意圖Fig.1 Diagram of anonymous communication network

對其進行概率分析，有必要描述匿名通信網絡如何根據某些概率分布隨機選擇重路由路徑的中間節點。由于匿名通信網絡在逐個節點的基礎上構建重路由路徑，因此“選擇概率”是分配給它們相應圖形的邊。因此，將圖G=(V,E)的鄰接矩陣P=(pij)稱為重路由矩陣。當兩節點為同一節點時，pij=0；當兩節點不同且都為兩節點連線屬于邊集E時，pij為邊集中選定該連線的概率；當兩節點連線不屬于邊集E時，pij=∞，即為:

(1)

任何匿名通信網絡的核心都是其重路由路徑選擇策略，只能根據特定的網絡路徑選擇策略來選擇特定的網絡，即如果攻擊者可以識別傳輸過程中所選路徑，則通過此路徑進行的所有通信都將暴露給攻擊者。同時，任何路徑選擇策略都必須滿足一些約束條件。本文從匿名的角度來看問題，可以對策略施加許多約束，最關鍵的約束條件是“網絡拓撲”“路徑拓撲”“路徑長度”，通過過去對匿名通信網絡的研究可知，這些約束條件可以被識別和確定[16]。

網絡拓撲匿名通信網絡的拓撲結構與標準計算機網絡的拓撲結構有很大不同，對網絡匿名級別具有重要影響。對于匿名通信網絡的拓撲結構，需要各節點之間鏈接更密集，避免攻擊者輕易識別各節點通信狀態。

路徑拓撲路徑的拓撲結構可以反映路徑的復雜程度,最重要的是確定預定路徑是否有重復。將不經過同一節點的路徑認定為簡單路徑，即一條簡單路徑上的所有節點必須是不同的；將多次經過同一節點的路徑認定為自由路徑，即該路徑不止一次地遍歷某些節點。相比簡單路徑，訪問者更傾向于使用自由路徑的拓撲方式，因其更難被攻擊者所識別，匿名性更高。

路徑長度路徑長度定義為路徑頂點序列中的頂點總數減去1，在未確定完整路徑時，路徑長度可變。設L是一條均勻分布的可變路徑的長度，并假設M和m分別是L的上界和下界，其概率質量函數為：

(2)

1.2 攻擊者子模型

為了對匿名通信網絡進行安全性分析，決定用潛在攻擊者的視角來分析匿名通信網絡，并盡可能真實地描述攻擊者的能力。攻擊者的主要任務是預測重路由路徑，從而識別消息的真正發送者。因此，“匿名集”被定義為所有可能發送者的集合。潛在的攻擊者可以通過各種方式獲得大量有效信息來縮小該集合[17]。因此，希望擁有一個強大的匿名通信網絡，這里“強大”是指攻擊者知道該網絡的路徑選擇策略，并且破壞了它的一個或多個中間節點，卻不能精準地確定它的實際重路由路徑。

設計的初衷是希望該網絡可以廣泛部署并使用，因此，假設攻擊者能夠利用現有的方法和工具推斷出路徑選擇策略(即網絡拓撲、路徑拓撲和路徑長度)。同時，假設攻擊者將能夠控制部分中間節點和潛在發送者，并利用已破壞的中間節點和潛在發送者所捕獲的信息來揭示真正發送者身份。已知在通信網絡中，每個路由節點都知道它在該路徑上的前一節點和后一節點。因此，如果某一被控節點是路徑的一部分，攻擊者至少可以識別該路徑上的3個節點。但此時，攻擊者只能捕獲通信通道上的流量，卻無法更改這些信息，故該攻擊者模型只考慮被動攻擊。如果在進行某一信息傳輸時多次遍歷被破壞節點，攻擊者可以利用節點的相對順序創建一個遍歷節點的排序列表，并實時更新該匿名通信網絡的初始信息。

攻擊者的最終目標是利用所捕獲到的信息，重構從發送方到接收方的消息重路由的實際路徑。例如，考慮圖2中的重路由路徑(6,5,3,R)，由于接收方已經被攻擊，攻擊者只知道路徑上的節點3。假設攻擊者已經破壞了節點3，攻擊者可以根據節點3所得到的信息知道節點5也在該傳輸路徑上。另一個例子，考慮重路由路徑(7,1,2,3,1,4,R)，假設攻擊者已經破壞了節點1，他知道節點2、3、4和7也在該路徑上。根據消息到達和離開的時間，可以得到路徑上節點的正確順序，即7、1、2、3、1、4。

圖2 路徑拓撲Fig.2 Path topology

2 模型的概率分析

到目前為止，已經給出了該模型的基本假設。該模型由一個匿名通信網絡子模型和一個攻擊者子模型組成。對于該模型，將演示匿名通信網絡的概率分析及其匿名損失的量化過程。通過以下幾個步驟進行評估：

第一步，定義匿名指標，來量化匿名通信網絡提供的發送者匿名級別。為了計算度量，需要計算潛在發送者的概率分布。

第二步，構造一種尋徑樹。尋徑樹表示滿足匿名通信網絡路徑選擇策略約束的所有重路由路徑，它可以系統地生成所有感興趣的路徑。

第三步，用重路由概率參數化尋徑樹，并利用其計算潛在發送者的概率分布，再利用概率分布計算其他指標。

2.1 定義匿名指標

設S為消息M的潛在發送者的離散隨機變量，對其進行評估，主要定量匿名度量定義是潛在發送者為真正發送者的概率。首先，在沒有任何信息的情況下，考慮潛在發送者為離散均勻分布：

(3)

通過分析匿名網絡的行為，攻擊者可以得到更準確的潛在發送者分布。這個分布將描述每個候選者成為真正的發送者的概率[18]：

p′(S=si)=p′i，

其中，

(4)

首先計算隨機變量S的初始熵：

(5)

攻擊者通過捕獲信息后得到新的分布：

(6)

為了表示初始分布和通過利用先驗知識得到的新分布之間的區別，利用“相對熵”來量化。

(7)

對于該問題：

(8)

這種度量是一種描述偏差的度量，表明攻擊者的估計與事實的差距。一些研究已引入了這種度量方法[19]。本文的主要新穎之處在于建模方法的基本假設和度量標準的過程評估。

假設消息M從潛在的發送方發送到特定的接收方。為了識別消息真正的發送方，攻擊者嘗試重建從源到目的地的路徑，將概率地選擇潛在的路徑。攻擊者的成功主要取決于兩個因素：被攻擊者攻擊節點的數量和節點之間的鏈路信息的數量。假定基礎圖是完整的，攻擊者必須考慮所有可能的路徑。事實上，攻擊者需要解決兩個主要問題：表示一個匿名通信網絡的兩個指定節點之間有多少條路徑?如何系統地生成這些路徑?

2.2 尋徑樹

攻擊者將猜測消息的潛在發送者并通過執行窮舉搜索得到概率分布，再考慮其中滿足所有約束條件的路徑，然后確定潛在發送者的理想分布。如果要計算路徑的數量，將面臨兩個嚴重的障礙：① 路徑的數量可能會隨著圖的大小呈指數增長；② 生成所有路徑并非易事。本文通過使用一種類型的狀態空間樹來克服，將其稱為尋徑樹。

推導概率分布的思想是基于構造狀態空間樹的變體，其節點反映了重路由路徑的節點所做的特定選擇，它可以系統地生成所有感興趣的路徑。因此沒有必要生成一個完整的尋徑樹，只要保證考慮節點的后續節點不可能存在完整路徑，便進行“剪枝”，不再考慮其后續節點的情況以減小任務量。尋徑樹的根代表在開始搜索可能路徑之前被破壞的消息接收方，從根到葉的任何路徑都是候選路徑；樹中第一級節點代表路徑第二個中間節點的選擇(由于攻擊者是要揭露發送方的身份，從接收方反向溯源，故節點選擇為反向選擇)。將以寬度優先搜索的方式構建樹，如果當前節點是有希望的，則將路徑的下一跳備選節點作為其子節點。如果當前節點被證明是沒有希望的，算法回溯到節點的父節點，為它的父節點考慮下一個可能的選項;如果沒有這樣的選項，它將回溯到樹的上一級，以此類推。最后，算法在獲得從源到目標的完整路徑后，繼續搜索其他可能的路徑。預計路徑搜索方法將能夠根據網絡拓撲和路徑的信息，修剪足夠多的路徑查找樹的分支。

2.3 概率分布計算

利用尋徑樹可以得到潛在發送者的概率分布。由于路徑是基于概率分布構造的，所以攻擊者可以為任意給定的一對頂點之間的網絡鏈路分配選擇概率。也就是說，通信鏈路的選擇是基于這些概率的，這些概率可以根據一些觀察得到，例如利用一些指標，如中間節點的地理位置和網絡鏈路的帶寬來確定這些值。這些轉移概率可以簡單地表示為(m+n) × (m+n)轉移概率矩陣S:

(9)

式中，m和n分別為潛在發送者和中間節點的數量。對于所有i,j∈V，在這個矩陣的第i行和第j列中，元素0≤sij≤1表示節點i在重路由路徑上是節點j的“直接后繼”的概率。由于圖是完整的，因此在圖的任意一對頂點之間均存在一條邊。設隨機變量Yn是從目的地到源的“反向”路徑上的第n個節點。因此，sij可以表示為:

sij=P(Yn=j|Yn-1=i)。

(10)

在這樣的矩陣中，有些行和列是統一的。也就是說，矩陣S的元素滿足以下約束條件:

(11)

顯然，被破壞的頂點的存在改變了矩陣的某些元素。設C為被妥協的潛在發送者和中間節點的集合，有C?V，設j∈C為妥協頂點。如果j不在路徑上，矩陣S對應的元素保持不變。如果j在路徑上，相應的元素被更新，這意味著頂點j不再有不確定性了。尋徑樹用重路由概率參數化，概率值被分配到樹的邊緣。從根到葉的路徑是滿足約束的重路由路徑，且重路由路徑計算的所有概率值加起來為1。對于一般情況下的尋徑樹，設X和Y為兩個離散隨機變量，分別表征在尋徑樹的第1層和第2層中所做的選擇。根據定義，在樹的第1層，有:

(12)

設P(x,y)為這些隨機變量的聯合概率質量函數。根據定義，在樹的第2層，Y(X)的條件概率質量函數為：

且

(13)

將其推廣到整個樹，則在樹的最底層(葉節點)可得：

(14)

假設路徑L=(si,nj,…,nr,ns,R)，長度為L的路徑是從發送方si到接收方R的路徑。為了計算該算法溯源找到路徑L的概率,可以將條件概率P(A∩B)=P(B)P(A|B)推廣得到路徑選擇的概率:

P(Yl=R,Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)=

P(Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)×

P(Yl=R|Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)=

P(Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)×pRs=

P(Yl-2=nr,…,Y1=nj,Y0=si)×psr×pRs=

?

pji×…×psr×pRs。

(15)

樹的每個分支都被標記為特定的選擇概率，這樣從根到任何葉的所有分支概率的乘積就等于選擇相應路徑的概率。因此，可以為每條可能的路徑L分配一個選擇概率，其組成邊的概率的乘積為：

(16)

對于尋徑樹的定義，網絡的中間節點和潛在發送者分別是樹的內部節點和葉節點。由于樹的葉子部分代表消息的潛在發送者，所以在使用尋徑樹指定新的分布時，需要將潛在發送者分成兩組，屬于樹葉的發送者頂點和不屬于樹葉的發送者頂點(即被妥協的發送者)。假設i是一個潛在的發送端頂點，它是樹的葉子，可能出現多次。為了得到該節點為真正發送者的相應概率，需要考慮該節點從根到該葉的所有對應路徑。設L(i)={L1(i),L2(i),…,Lt(i)}為發送端頂點i對應的路徑集合，其中t為這樣路徑的個數，故有:

(17)

最后，利用了全概率定理的一種形式。設L(T)=[L(1),L(2),…,L(k)]為發送者的“路徑向量”，其中T為尋徑樹。所有葉節點對應的概率之和必須是1，因為它們覆蓋了選擇路徑的所有可能性：

(18)

式中，k為所有潛在發送者的數量。

至此，攻擊方可得到任意路徑被選擇的概率，并可以通過此概率計算潛在發送者的概率，定量分析該網絡的匿名性。

3 結論

本文引入一個概率模型來測量匿名通信網絡提供的匿名性水平,其主要目的是提出一種用于評估匿名度量的建模方法，而不是對模型進行精確的參數化。換句話說，主要關注的是發展一種定量分析匿名通信網絡匿名性的理論方法，而不是精確分析模型的評估。該模型可以簡單地進行擴展，用于量化匿名通信網絡的其他匿名屬性(如接收者匿名)。尋徑樹可以系統地搜索所有可能的重路由路徑，故肯定能找到感興趣的路徑,從而保證分析方法的正確性。