對一種混合結構洋蔥路由方案的密碼學分析

李龍海，付少鋒，蘇銳丹，車向泉

（西安電子科技大學 計算機學院，陜西 西安 710071）

1 引言

隨著 Internet應用范圍的不斷擴大和信息量的爆炸性增長，對用戶隱私性的保護已經成為一個至關重要的問題。在很多應用中，隱私不僅意味著通信內容的秘密性，而且意味著不能泄漏“誰和誰”、“在什么時間”、“通信量大小”等通信上下文信息。匿名通信技術主要研究如何隱藏消息發送者和接收者的身份以及通信雙方的對應關系，即如何實現發送者匿名性、接收者匿名性和不可關聯性。該技術被廣泛應用在匿名電子郵件、匿名Web瀏覽、電子商務、電子選舉等對隱私保護要求較高的Internet應用系統中。

匿名通信技術的研究可以追溯到 1981年Chaum發表的開創性論文[1]，其中，提出了混合網絡(Mix-net)的概念。目前已提出的大多數匿名通信系統都是基于 Mix-net思想設計的。一個 Mix-net包含若干個Mix服務器。發送者的消息首先被多層加密形成類似于“洋蔥”的結構，然后經過多個Mix服務器的轉發傳遞給接收者。每個Mix服務器對收到的報文進行單層解密并轉發給下一個Mix服務器。接收者最終獲得消息的明文。根據轉發路徑構成方式的不同，Mix-net可以分為固定路由和自由路由2種。自由路由式Mix-net中的發送者隨機選取若干個Mix服務器構成轉發路徑，并將這些服務器的網絡地址依次封裝在洋蔥報文的各個層中，最內層是接收者的地址和消息明文。發送者首先將報文發送給第一個Mix服務器。該服務器對收到的報文進行單層解密之后即可獲得第二個Mix服務器的網絡地址，并繼續將解密后的報文發送給下一個服務器。依此類推，直至最終的接收者。該轉發過程類似于剝洋蔥的過程，因此也被稱為“洋蔥路由”系統。其中，每個轉發節點僅知道自己上一跳和下一跳的地址。只要轉發路徑中有一個以上的節點是誠實的(不泄露自己上一跳和下一跳的地址)，攻擊者就無法將所截獲消息的發送者和接收者關聯到一起。

重放攻擊是一種針對洋蔥路由系統的十分有效的攻擊。攻擊者將截獲的洋蔥報文復制多次發送給目標Mix服務器，則在該服務器的某個輸出鏈路上必然出現多個內容重復的報文。攻擊者由此可追蹤該報文的流動方向，直至接收者。早期的洋蔥路由系統一般采用檢查重復輸入并丟棄的方法對抗重放攻擊[2]，其缺點是需要緩存大量的歷史數據，并且每個輸入都要與緩存數據比對，造成報文處理時間的逐漸增長。另外一些系統采用了定期更換密鑰[3]、加入時間戳[4]等方法，但分別存在密鑰管理復雜、需要嚴格時間同步等問題。2004年Gomulkiewicz等提出了一種新型的基于通用重加密(URE, universal re-encryption)算法[5]的洋蔥路由方案URE-Onion[6]。URE-Onion服務器對收到的報文除了進行部分解密，還要實施隨機化重加密。該方法能夠保證重復的報文輸入同一Mix服務器之后輸出也是不同的，使得攻擊者無法繼續追蹤下去，因此不再需要緩存歷史記錄。但不久Danezis等提出了一種針對 URE-Onion的繞路攻擊(detour attack)[7]表明該方案存在嚴重安全漏洞。隨后Klonowski等對URE-Onion進行了改進[8]，利用為每個服務器分配雙重密鑰的方法阻止攻擊者隨意修改轉發路徑，使其無法實施繞路攻擊。然而，Borisov等在文獻[9, 10]中又給出了針對URE-Onion改進方案的多種攻擊，并分別提出了基于上下文敏感加密(context sensitive encryption)和基于標簽加密(tag-based encryption)的2種改進方法。陸天波等也指出了基本的通用重加密算法對于選擇密文攻擊的脆弱性，并設計了基于ElGamal算法重加密特性的匿名系統WGRe[11]。

URE-Onion及其多種改進方案雖然能夠抵御重放攻擊，但由于完全基于非對稱加密算法，效率都很低。如果匿名轉發路徑長度為λ，則每個服務器收到報文之后都要進行 O(λ)次大素數群上的指數運算，并且長度為O(λ)的報文中只有1/λ被真正用于加密用戶消息，而其他的部分都被用來加密路由信息。針對上述缺點，時金橋等[12]設計了一種混合結構洋蔥報文機制 HS-Onion。該設計僅用 URE算法加密路由信息部分，而消息正文部分采用更高效的對稱加密算法加密，因此在傳送長消息時具有很大的優勢。該方案的另一個創新點是采用了2種代數結構不同的公鑰加密算法對路由信息部分進行雙層加密，以實現對報文的完整性保護進而防止攻擊者修改路由并實施繞路攻擊。

本文發現時金橋等提出的洋蔥路由方案[12]存在的安全漏洞，主要表現在報文結構具有可展性(malleability)，攻擊者可以改變洋蔥消息的路由或在其中嵌入標簽以追蹤消息路由。由于沒有對惡意行為的調查機制，Mix服務器很容易被攻擊者用作解密預言機(decryption oracle)以獲取有利信息。本文展示了基于這些安全漏洞的 3種不同的攻擊方法，這些攻擊都能夠將消息的發送者和接收者以不可忽略的概率關聯到一起。最后本文給出了針對原方案的修正方法，并對修正后系統的安全性和效率進行了討論。

2 HS-Onion方案回顧

2.1 通用重加密算法

ElGamal算法是一種具有同態特性的概率性公鑰加密算法。在已知接收者公鑰的條件下任何人都可以對ElGamal密文進行重加密(re-encryption)，重加密得到的密文與原密文對應相同的明文。在不知道私鑰的情況下，攻擊者能夠將重加密前后的2個密文匹配到一起的難度等同于解 Diffie-Hellman Decision問題。

通用重加密算法(URE)[5]是對 ElGamal算法的改進。在不知道接收者公鑰的情況下，URE密文也可以被重加密。該算法的詳細描述如下。

系統建立 構造q階循環群G，滿足q為素數，且在群G上離散對數及Diffie-Hellman Decision問題難解。隨機選取G的一個生成元g。最后將G和g作為公共參數向所有用戶公布。

密鑰生成 Alice任取 x ∈Zq作為其私鑰，計算y = gx作為其公鑰。

加密 設明文為m，為構造針對Alice的密文，Bob任取 k0,k1∈Zq，然后計算四元組作為輸出。

下文中用符號UREx(m)表示關于消息m的URE密文，解密密鑰為x。由于URE是概率性加密算法，所以UREx(m)實際表示對應m的密文集合中的某一個成員。

可以用多個用戶的公鑰對同一消息 m進行多層URE加密。令xi表示用戶Si的私鑰，yi為對應的公鑰，則表示密文。

顯然，經過S1部分解密后得到的密文可表示為

2.2 URE-Onion方案

基于URE的洋蔥路由方案[6,8]主要利用了URE的2個特性：1)在不知道接收者公鑰的情況下也可以對URE密文進行重加密；2)可利用多個接收者的公鑰對同一消息m進行多層加密，每個接收者可以對密文進行部分解密以去除相應的加密層(類似于剝洋蔥)。這些方案的基本思想為：設接收者為Sλ+1，匿名消息發送者首先構造一條到達目的主機的匿名路徑其中，為中間Mix服務器。發送者構造如下格式的洋蔥報文：該報文由 λ+1個URE密文塊組成，前λ塊保存了路由信息，最后一塊保存了消息m。發送者將這λ+1個密文塊的順序隨機打亂，然后發送給 S1。匿名路徑上第個服務器Sj收到報文后進行如下操作。

1) 部分解密。利用自己的私鑰xj將報文中每一個密文塊進行部分解密，正常情況下必有一個密文塊解密結果為可識別的Mix服務器地址Sj+1，即Sj的下一跳路由地址。該密文塊在下一步被重加密之前被Sj替換成隨機數。

2) 重加密。Sj生成新的隨機因子并對報文中的每個密文塊進行重加密，最后將重加密結果發送給Sj+1。

以為S1例，S1對輸入報文解密后獲得下一跳路由地址S2，再進行隨機數替換和重加密操作獲得輸出報文 ：該報文經過的處理和轉發最后到達接收者Sλ+1時具有如下格式：{random, random, …, random, U RExλ+1(m)}。Sλ+1利用私鑰xλ+1將各個密文塊解密，只有最后一塊解密結果為消息m，其他為⊥。

在上述URE-Onion方案中，每個中間Mix服務器僅知道自己的上一跳和下一跳的地址，只要轉發路徑中有一個以上的節點是誠實的，就可以實現發送者和接收者之間的不可關聯性。由于 Sj每次都生成新的隨機因子對報文進行URE重加密，之后再輸出，因此相同的報文輸入同一服務器之后的輸出也是不同的。這是該方案能抵御重放攻擊的關鍵所在。

2.3 HS-Onion方案

2.3.1 符號與假設

由于URE-Onion方案存在效率和安全性問題，文獻[12]提出了基于混合結構報文的改進方案HS-Onion。其主要創新點是在報文格式設計上引入對稱加密機制，提高了報文處理效率，并且在不同密文塊之間引入鏈式加密，使得攻擊者無法隨意篡改密文塊，因此避免了針對原方案的繞路攻擊[7]。現將該方案所定義的相關符號及攻擊者模型總結如下。

相關符號 HS-Onion系統由N個Mix服務器構成，分別用符號S0, S1,…,SN-1表示。每臺服務器既充當用戶，又為其他節點提供匿名轉發服務。任意服務器 Si生成 2 對密鑰—(yi, xi)和(yi′,xi′)，并發布公鑰部分。其中， yi= gxi為URE公鑰， yi′為另一種具有CCA安全性的非對稱加密算法E的公鑰。Ex′(m )表示利用該非對稱加密算法對消息 m加密所生成的密文，解密密鑰為x′。H表示一個偽隨機數生成器，以輸入參數r為種子生成偽隨機數H(r)。ek(m)表示利用對稱加密算法對 m加密所生成的密文，解密密鑰為k。tag和tag′為2個約定好的標記字符串，如果Mix服務器對某個密文塊的解密結果以tag或tag′作為前綴，則表明該密文塊解密成功。

攻擊者模型 HS-Onion方案假設攻擊者能夠監聽所有網絡鏈路并且能夠控制部分Mix服務器，即采用了全局攻擊者模型。

2.3.2 HS-Onion機制描述

設匿名消息發送者為S0，接收者為Sλ+1。發送者從Mix服務器集合中任選λ個構成匿名轉發路徑中的節點，不妨設這些節點為。

洋蔥報文結構 為匿名發送消息 m，S0構造一個包含λ+3個密文塊的洋蔥報文P。為方便表示，定義函數其中，為S0選取的長度合適的隨機數。當s=t時，定義。報文P的具體格式如下：

該報文中前λ塊用于加密路由信息，第λ+1塊包含了對稱加密密鑰k，第λ+3塊包含了用密鑰k加密的消息m。第λ+2塊的作用見下面“路由協議”的5)。

路由協議 S0將上述報文的前λ+1塊的順序打亂，然后發送給 S1。匿名路徑上第個服務器Sj收到報文后進行如下操作。

1) 利用私鑰xj對前λ+2塊密文進行部分解密，正常情況下會從其中的一個密文塊中得到稱該塊為屬于服務器Sj的密文塊Bj。

2) 利用私鑰 x ′j解密獲得下一跳路由地址Sj+1及隨機數Rj。

3) 用Rj作為解密密鑰對除Bj之外的前λ+2塊密文進行部分解密。

4) 隨機生成種子rj，計算偽隨機串H(rj)并與第λ+ 3 塊進行異或，因此，最后一個密文塊等于

6) 將前λ+2塊密文進行重加密。

7) 將前λ+1個密文塊的順序隨機打亂，最后將報文發送給下一跳Mix服務器Sj+1。

接收者的處理 Sλ+1收到報文之后用私鑰xλ+1對前λ+1塊密文進行解密，正常情況下會從其中的一個塊中得到，從其他塊中得到 λ個隨機種子用x′j解密Ex′λ+1( k )獲得對稱密鑰k。利用k及很容易對最后一個密文塊進行解密獲得消息m。

本節將首先描述HS-Onion方案的2個主要安全漏洞，然后展示基于這些漏洞的4種攻擊方法。其中，解密預言機攻擊用作其他攻擊的基本手段，而另外3種攻擊的目標是破壞HS-Onion的基本安全屬性——通信雙方的不可關聯性，即以不可忽略的概率將所截獲報文的發送者和接收者匹配到一起。

3.1 HS-Onion的安全漏洞

下面所展示的攻擊主要利用了 HS-Onion方案的2個安全性漏洞。

1) 報文中包含路由信息的URE密文塊具有可展性。攻擊者在不知道明文m和私鑰x的情況下，可以利用生成關于消息m′的有效密文，即令實際上，2.3.2節HS-Onion路由協議的5)也利用了該特性。同理，攻擊者還可以由生成密文UREx(Rm)=，其中，R為攻擊者者選定的值。攻擊者可以利用該特性在報文中嵌入標簽以追蹤報文的路由。

2) HS-Onion的Mix服務器對輸入報文進行解密之前沒有對其效性做任何驗證，并且解密結束后發現非法報文也沒有相應的反向追蹤機制，因此，誠實服務器很容易被攻擊者用作解密預言機以獲取有利信息。

3 對HS-Onion的攻擊

3.2 解密預言機

假設惡意服務器 Sa截獲到的報文中含有密文URExb(m′)，則Sa可以通過如下攻擊方法把誠實服務器Sb用作解密預言機，將解密獲得m′。

Step1 Sa任取隨機數R′，并用作為公鑰對 U RExb(m′)進行加密，即將其轉化為密文，其中，xa為Sa的私鑰。

Step2 Sa任取隨機數并構造包含 λ+3個塊的報文，最后，Sa將該報文發送給Sb。

Step3 根據HS-Onion路由協議，Sb接收到該報文之后首先用私鑰xb對其進行解密，則必然從第一塊中得到，再用 xb′解密后得到下一跳路由地址Sa和隨機數R′。之后Sb按照2.3.2節協議規定步驟對該報文進行處理，并將處理后的報文重新發回給Sa。當然，為了避免Sb的懷疑也可以通過修改報文下一跳地址令Sb將報文發往Sa的同謀者。

Step4 上述報文回到服務器Sa時具有如下格式：（前λ+1個密文塊的順序可能是被打亂的）。Sa利用私鑰 xa對前 λ+1塊密文進行解密可得到即便這些解密結果的順序是隨機的，Sa也能從中識別出m′，因為都

是Sa已知的值。

3.3 數據指紋追蹤攻擊

3.3.1 前提條件

實施“數據指紋追蹤攻擊”要求攻擊者能夠監聽系統的所有鏈路，并且控制了匿名轉發路徑中的最后一個節點。HS-Onion定義的全局攻擊者模型完全可以滿足這些條件。

另外，對于基于 Internet的匿名通信系統，要求攻擊者能監聽系統所有鏈路是很難滿足的，因此，一般采用更實際的局部攻擊者模型，即假定攻擊者能夠控制系統的部分服務器，并且只能夠監聽惡意服務器自己的輸入和輸出鏈路。如果采用局部攻擊者模型，“數據指紋追蹤攻擊”則要求攻擊者能夠控制匿名轉發路徑中的第一個和最后一個節點。

3.3.2 攻擊過程

該攻擊的基本思想是攻擊者記錄每個發送者輸出報文的數據指紋(因為攻擊者可以監聽網絡的所有鏈路)，然后由匿名轉發路徑中的最后一個節點利用協議漏洞提取每個轉發報文的指紋，如果發現與此前記錄的某個指紋相等，那么就能將發送者和接收者匹配到一起。

設發送者為S0，接收者為Sλ+1，匿名轉發路徑由節點為構成且Sλ為惡意服務器。S0構造關于消息m的報文P，其格式如式(1)所示，然后發送給S1。攻擊者利用如下的攻擊過程將發送者S0、接收者Sλ+1和報文P關聯到一起。

Step1 攻擊者計算報文 P的最后一個密文塊ek(m)的數據指紋，即散列值 SHA1(ek(m))，并記錄二元組(S0, SHA1(ek(m)))。

上述記錄報文指紋的工作也可由惡意節點 S1完成。值得注意的是，S1此時無法確定自己是否為第一個轉發節點，因為其前驅S0既可能是源節點也可能是中間轉發節點。直到攻擊完成時，尾節點Sλ獲得路徑相關信息才能驗證S1是否為首節點。

Step2 攻擊者控制的惡意服務器Sλ每接收到一個報文P′，首先按照原協議規定對其解密獲得下一跳服務器地址Sλ+1，然后判斷自己是否為匿名路徑的最后一個轉發節點，具體采取的方法是將Sλ+1用作解密預言機將報文中第λ+2塊密文進行解密。如果解密結果為1，則證明自己為路徑尾節點。

下面解釋這樣做的原因。根據 HS-Onion路由協議，如果Sλ是關于報文P′的最后一個轉發節點，則P′經過Sλ處理之后必然具有如下形式：

因此，如果第λ+2塊密文URExλ+1(1)解密為1，則Sλ必為最后一個轉發節點。

Step3 如果發現自己是最后一個節點，則Sλ利用Sλ+1的解密預言機服務將式(2)所示報文的前λ+1個密文解密，獲得由隨機種子r1, r2,…,rλ和密文很容易計算出ek(m)及指紋SHA1(ek(m))。

Step4 Sλ從Step1中記錄的二元組集合中找到(S0, SHA1(ek(m)))就可以將報文P、P′以及發送者S0、接收者1λS+關聯到一起。λS在Step3中得到了λ個tag′的事實也說明S0與λS之間的路徑長度為λ，并且S1確實為第一個轉發節點。

3.3.3 分析

設構成系統的N個Mix服務器中被攻擊者控制的惡意服務器所占百分比為δ，并且構成轉發路徑的節點是發送者從全體服務器集合中隨機選取的，那么在全局攻擊者模型下，上述攻擊能夠成功匹配發送者和接收者的概率為δ。在局部攻擊者模型下，該攻擊要求轉發路徑的首節點和尾節點都是惡意的，因此，攻擊成功的概率為2δ。

3.4 標簽追蹤攻擊

3.4.1 前提條件

實施“標簽追蹤攻擊”要求攻擊者能夠控制匿名轉發路徑的第一個節點和最后一個節點。該攻擊在全局攻擊者模型和局部攻擊者模型下都適用。

3.4.2 攻擊過程

標簽追蹤攻擊的基本思想是由處于匿名轉發路徑上游的惡意節點Sa利用URE算法的可展性在報文中嵌入“標簽”。處于下游的另一惡意節點 Sb如果在收到的報文中發現了相同的標簽則可以判斷自己與Sa處于同一轉發路徑。如果Sa、Sb恰為該路徑的首尾節點，則該攻擊成功地將發送者和接收者匹配到一起。

設發送者為S0，接收者為1λS+，匿名轉發路徑由S1, S2,…,λS構成，且S1、λS為惡意服務器。S0將消息m包裝成洋蔥報文P，然后發送給S1，P的格式如式(1)所示。基于上述假設，標簽追蹤攻擊的具體攻擊過程如下。

Step1 S1接收到報文 P后，首先按原協議規定對其進行解密和再加密，獲得下一跳路由地址S2及如下格式的報文P′：

其中，前λ+1塊密文的順序是隨機的。S1從P′的前λ+ 1 個密文中除外)任取一塊，不妨設該塊為并在其中嵌入能唯一標識S1的標簽θ1∈G，即將其替換為。之后，S1將加入標簽的報文發送給S2。

Step2 惡意服務器Sλ每接收到一個報文P′，首先用私鑰xλ進行解密，如果在前λ+1個密文中發現某個解密結果具有形式則可以認定自己與上游的S1處于同一轉發路徑。

在上述攻擊中，雖然S1、Sλ還需借助其他手段確定自己是否為首尾節點，但處于S1與Sλ之間的其他Mix服務器的路由隱藏作用被完全抵消，這為關聯發送者和接收者提供了幫助。

3.4.3 分析

在Step1中，S1從報文P′中任取了一個密文塊并猜測該塊是關于某個下游惡意節點的路由信息塊。如果猜測失敗，則該報文到達某個誠實節點時會被解釋為非法報文而丟棄，但 HS-Onion并沒有反向追蹤機制，S1不用擔心受到懲罰。因此，為了提高成功率，S1可以將P′復制λ份，然后在每一份中任取一個不同的密文塊嵌入標簽，并將這些復制報文都發送給下一個服務器。處于下游的惡意節點識別出標簽后，還可以繼續嵌入自己的標簽，以方便更下游的惡意節點識別。以此類推，報文P轉發路徑上的多個惡意節點可以利用標簽追蹤攻擊確定它們在路徑中的相對位置和上下游關系。下面的定理給出了系統中所有節點協作，并利用這種更復雜的標簽追蹤攻擊能準確關聯特定消息發送者和接收者的概率。

定理1 假設Sa、Sb利用標簽追蹤攻擊確定它們分別為同一路徑中最上游和最下游的惡意節點，系統中惡意節點所占百分比為δ，轉發路徑采用固定長度λ。如果直接猜測Sa的前驅和Sb的后繼分別為發送者和接收者，則猜測正確的概率為

證明 已知整個轉發路徑中存在一個惡意節點 Sa，首先嵌入標簽，而 Sb是路徑中最后一個追蹤到標簽的惡意節點。該事件發生的概率等同于長為λ的路徑(不包括發送者和接收者)中包含2個及2個以上惡意節點的概率，即，其中，(1 - δ )λ和 λ δ(1 - δ )λ-1分別為“不包含任何惡意節點”和“僅包含一個惡意節點”的概率。如果直接猜測 Sa的前驅節點和 Sb的后繼節點分別為發送者和接收者，則存在一定的誤差，因為 Sa和 Sb未必是轉發路徑的第一個節點和最后一個節點。

轉發路徑首、尾節點都是惡意節點的概率為δ2，因此在存在2個惡意節點并利用標簽追蹤攻擊確定它們分別為最上游和最下游的惡意節點的條件下，它們的前驅節點和后繼節點分別為發送者和接收者的概率為

3.5 猜測接收者攻擊

3.5.1 前提條件

猜測接收者攻擊僅要求攻擊者能夠控制匿名轉發路徑的第一個節點，該攻擊同時適用于全局攻擊者模型和局部攻擊者模型。

3.5.2 攻擊過程

該攻擊的基本思想是攻擊者隨機猜測報文接收者的地址，然后利用誠實Mix服務器的無意識轉發服務和解密預言機服務驗證猜測是否正確。如此反復猜測直到找出真正的接收者。

設發送者為S0，接收者為Sλ+1，轉發路徑由S1,S2, …,Sλ構成，且S1為惡意服務器。S0發送報文P到S1，P的格式如式(1)所示。猜測接收者攻擊的具體攻擊過程如下。

Step1 S1接收到報文 P后首先對其進行解密和再加密，獲得下一跳路由地址S2及如式(3)所示的報文P′。S1將P′保存以備后面重復實施猜測攻擊。

注意此時S1并不能確定自己為第一個轉發節點。Step2 S1做2個猜測：1)P的接收者為St；2)從P′的前λ+1個密文中除外)任取一塊，不妨設為并假定該塊是關于St的密文。

基于以上猜測 S1對P′做如下修改：1)利用 URE算法的可展性，根據 Bj構造密文 U REK(2,j)(tag||，并用該密文替換Bj；2)將第λ+2個密文塊 U REK(2,λ+1)(1)替換為)將UREK(2,λ+1)( tag′||r1)替換為

最后，S1將修改過的P′發送給S2。

Step3 經過一段時間，如果 S1從某個服務器Sλ+1接收到報文P′，并且利用私鑰 x1將其解密后具有形式：，則證明Sλ+1是接收者。將P′解密獲得λ+1個tag′的事實也證明S1是第一個轉發節點，并且其前驅S0是發送者。至此，HS-Onion方案的不可關聯性被完全破壞。

如果 S1長時間內沒有收到任何符合上述條件的報文，則說明Step2的2個猜測中至少有一個是錯的。S1重新猜測接收者地址和相應密文塊 Bj并重復上述攻擊直至找到接收者。

實際上，上述攻擊經過修改后可以用于確定構成匿名路徑的任意節點。

3.5.3 分析

首先分析3.5.2節攻擊的原理。在Step2中如果S1猜測正確，即那么Step2中經過修改的P′必然具有如下形式：

這相當于將匿名路徑延長了一個節點，S1作為終點，Sλ+1被當作最后一個轉發節點。由于報文中不含路徑長度信息，因此這些修改不會被其他轉發節點發現。

如果 S1猜測錯誤，則P′在轉發過程中會被某個誠實節點視為非法報文而丟棄，但由于沒有反向追蹤機制，S1不用擔心受到懲罰。

下面分析“猜測接收者攻擊”的代價。假設系統包含N個Mix服務器，轉發路徑采用固定長度λ，則S1最多需要進行 λ(N - 2 )次猜測驗證過程。在N不算太大時，該攻擊是非常有效的。為了縮短攻擊時間，S1還可以將多個猜測驗證過程并行進行，但需要在P′中針對不同的猜測加入不同的標記，具體過程就不再詳細敘述了。

4 對HS-Onion的修正

4.1 兩點修正

為了避免所提的3種攻擊，在此提出對HS-Onion方案的兩點修正措施。在原協議框架下，很難完全消除 URE算法的可展性，因為該特性是報文能夠被隨機化重加密和中間轉發節點能夠將自己的對稱密鑰ri添加到報文的關鍵。因此，這些修正的主要目的是提高攻擊者隨意篡改報文的代價，盡量避免關鍵節點為攻擊者提供解密預言機服務器。

修正 1 限制 Mix服務器只提供匿名轉發服務，本身不作為通信用戶。類似于被廣泛使用的洋蔥路由系統Tor[13]，修正后HS-Onion由匿名路由核心網絡和外圍用戶群構成。N個Mix服務器構成核心網絡。發送者和接收者都屬于外圍用戶群，它們利用核心網能夠隱藏路由的轉發服務來實現匿名通信。在全局攻擊者模型下，匿名集合由同一時刻接入核心網的所有用戶構成。

修正 2 增加對惡意節點的反向追蹤機制。誠實Mix服務器在發現某個報文非法之后可以啟動反向追蹤機制，沿匿名路徑回溯查找制造非法報文的源頭。在調查過程中，從發現非法報文的節點Sj開始，沿路徑逆向依次要求其前驅節點Sj-1, Sj-2,…提交證據證明自己正確處理了被追蹤報文，直至找到惡意節點。每個節點的證明過程不能破壞其他報文的匿名性。目前已知的幾種URE洋蔥路由方案[6,8～10]都采用了基于零知識證明技術的反向追蹤機制，使得Mix服務器可以在不公開密鑰xi的條件下證明自己合法地處理了報文。由于HS-Onion采用了2種代數結構不同的公鑰算法，所以直接采用該方法較為困難。在此筆者設計了公開部分解密密鑰和零知識證明相結合的證明方法。

證明 修正協議要求Mix服務器為每個輸出報文增加數字簽名之后再轉發給下一個服務器，這樣可以防止惡意節點對自己的攻擊行為進行抵賴。設服務器 Sj從前驅節點 Sj-1接收到的報文，經過解密和再加密處理后轉發給下一級的報文為用符號ZK{x∶A(x)}表示關于秘密x的零知識證明，A(x)是一個關于x的斷言，該證明能夠在不暴露x的條件下證明斷言A(x)取真。下文的證明中x在A(x)中都以離散指數形式存在，構造該類證明主要用到基于離散對數的零知識證明技術，具體構造方法可以參考文獻[14]。

Sj證明自己正確處理了報文Pj-1的具體過程如下。

1) Sj公布如下內容：私鑰jx′，下一跳地址Sj+1，Rj，rj，Pj-1中屬于 Sj的密文塊 Bu,j-1，Pj中屬于 Sj的密文塊 Bv,j以及由 Pj-1生成 Pj時所使用的所有URE再加密隨機參數。

2) 為證明 x ′j、Sj+1和 Rj的合法性，Sj公布

4) 為證明 Bv,j和 rj的合法性，Sj公布密文并證明Bλ′+2,j經過URE再加密可以生成Bλ+2,j，且密文經過再加密可以生成Bv,j。

5) 針對Bλ+3,j的合法性，Sj需要證明成立。

在證明過程中，Sj只公開了私鑰 x′j而沒有公開 xj，因此并不會對Sj過去轉發報文的匿名性造成影響。

4.2 分析

4.2.1 安全性

下面具體分析修正措施對本文所提3種攻擊的防范作用。

1) 關于數據指紋追蹤攻擊。經過修正1之后，接收者Sλ+1不再提供匿名轉發服務，因此在數據指紋追蹤攻擊中惡意節點Sλ無法利用Sλ+1的解密預言機服務獲得ek(m)及其數據指紋。但僅有修正1是不夠的，攻擊者可以采用由轉發路徑首尾節點 S1和Sλ合謀實施的指紋追蹤方法：作為第一個轉發節點的惡意服務器S1從報文P的前λ+1個密文中任取一個并猜測它是屬于Sλ的密文S1由構造，并將第λ+2塊密文替換成。如果S1猜測正確，則在該報文到達惡意節點Sλ時，Sλ仍然可以從中獲得ek(m)，從而將S1和Sλ關聯到一起，S1的前驅和Sλ的后繼作為發送者和接收者也被關聯到一起。和改進之前比，指紋追蹤攻擊必須依賴于隨機猜測。如果猜測錯誤，則攻擊者將被反向調查機制捕獲。

設系統中惡意節點所占百分比為δ，轉發路徑采用固定長度λ，下面的定理描述了在局部攻擊者模型下修正方案抵抗指紋追蹤攻擊的能力。

定理 2 修正方案中攻擊者利用數據指紋追蹤攻擊能成功關聯發送者和接收者的概率為δ2/λ，而攻擊者被捕獲的概率為1-δ。

證明 基于隨機猜測的指紋追蹤攻擊能夠成功的條件是：① 路徑首尾節點S1和Sλ都是惡意節點；② S1能夠猜中對應Sλ的密文塊。這2個條件成立的概率分別為 δ2和1/λ，并且它們為相互獨立的隨機事件，因此，攻擊能夠成功的概率為δ2/λ。

在攻擊中，S1從前λ+1個密文塊中隨機選擇了并將第λ+2個密文塊替換成在該報文到達節點Sj時，Sj將發現第λ+2個密文的解密結果為1，因此很容易發現該報文為非法報文。如果Sj為誠實節點，將會觸發反向調查過程，惡意節點S1必然被捕獲。如果Sj為惡意節點，只會將該非法報文簡單丟棄。因此，S1是否被捕獲決定于它隨機選擇的密文Bj所對應節點Sj是否為惡意節點。因為構成轉發路徑的節點是發送者從全體服務器集合中隨機選取的，所以Sj為惡意節點的概率為δ，而S1被捕獲的概率為1-δ。

2) 關于標簽追蹤攻擊。在修正方案中，標簽追蹤攻擊也必須由轉發路徑的首尾節點合謀實施，即由第一個轉發節點嵌入標簽，由最后一個轉發節點從流經報文中提取標簽。另外，標簽追蹤攻擊也依賴于隨機猜測。如果猜測錯誤，則攻擊者將被反向調查機制捕獲。定理3描述了在局部攻擊者模型下修正方案抵抗標簽追蹤攻擊的能力。

定理 3 修正方案中攻擊者利用標簽追蹤攻擊能成功關聯發送者和接收者的概率為δ2/λ，而攻擊者被捕獲的概率為1-δ。

證明 標簽追蹤攻擊成功的條件是：1) 路徑首尾節點S1和Sλ都是惡意節點；2) S1嵌入標簽的密文塊恰好對應節點Sλ。這2個條件能夠成立的概率分別為 δ2和1/λ，因此，攻擊能夠成功的概率為δ2/λ。如果與嵌入標簽的密文塊相對應的節點Sj為誠實節點，則S1必然被反向調查機制捕獲。如果Sj為惡意節點，則只會將該非法報文簡單丟棄。因此，S1是否被捕獲決定于它隨機選擇的密文Bj所對應節點Sj是否為惡意節點，即S1被捕獲的概率為1-δ。

3) 關于猜測接收者攻擊。修正1使得攻擊者無法再利用接收者Sλ+1的匿名轉發服務驗證自己對接收者的猜測，但攻擊者可以利用類似的攻擊思想猜測和驗證構成轉發路徑的各個中間節點。這樣做同樣存在隨機猜測過程，即需要攻擊者隨機選擇密文塊Bj，并將其篡改為如果Bj對應的節點Sj是誠實的，攻擊者制造的非法報文將會被發現，因此，攻擊者被捕獲的概率同樣為1-δ。

由以上分析可以看出，對原方案的兩點修正雖然無法完全消除Mix服務器的解密預言機漏洞，但在很大程度上提高了攻擊者篡改密文和利用解密預言機的代價。在典型的 Internet分布式匿名系統中，一般認為惡意節點所占比例δ的上限為0.2[15]。在該條件下，根據定理2和定理3的結論，惡意節點在實施3種攻擊時被捕獲的概率不低于1-δ，即80%。為了進一步提高反向追蹤對攻擊的抑制作用，還可以采用制定嚴厲懲罰措施等非技術性手段。

4.2.2 效率

在正常情況下，每收到一個報文，修正方案中的Mix服務器除了需要進行原協議規定的2λ+3次URE解密、λ+2次URE再加密操作以及一次公鑰算法E的解密操作之外，只需額外進行一次數字簽名操作，因此服務器運算量增加很小。

在發現有非法報文的異常情況下，該報文轉發路徑上的部分節點時被迫參與反向追蹤過程。每個相關節點為構造自己的合法性證明，需要進行3(λ+2)次群G上的指數運算，而驗證該證明則需要進行10λ+24次指數運算和一次公鑰算法E的解密操作。在異常情況下，最大的額外開銷在于每個參與調查的服務器都要更換密鑰，并向系統其他節點廣播新密鑰。因此，為了防止頻繁攻擊行為對性能的影響，可以采用加重懲罰力度的方法來降低服務器作弊的概率。

另外，為了能夠在反向追蹤中證明自己在上一級輸出報文基礎上做了正確的處理，每個服務器還需對包含數字簽名的輸入報文進行緩存。如果要求誠實服務器發現非法報文后必須立即啟動反向追蹤機制，那么Mix服務器只需緩存較短時間段內收到的報文，因此修正方案中緩存數據量較小，并且不需要將輸入與緩存數據進行比對以檢查是否有重復報文。與傳統的基于緩存法對抗重放攻擊的洋蔥路由系統相比，基于HS-Onion仍然具有很大優勢。

5 結束語

基于通用重加密算法的洋蔥路由系統能夠有效抵御重放攻擊，但存在嚴重的效率問題。為此，時金橋等提出了一種綜合利用通用重加密和對稱加密算法的混合結構洋蔥路由方案HS-Onion，降低了傳輸長消息時的計算復雜度。本文指出了HS-Onion方案的2處安全漏洞，并展示了3種能夠完全破壞發送者和接收者不可關聯性的攻擊方法。這些攻擊采用了與匿名通信系統中一些典型攻擊類似的思想，如關系攻擊[16]、路徑猜測攻擊[9]、分組計數器攻擊[17]等，因此，對分析其他匿名通信系統的安全性具有一定的借鑒作用。近年來出現了很多針對匿名通信系統的關聯攻擊[15,18,19]，它們主要面向基于虛電路的低延時匿名通信系統(如Tor[13])，并且大都采用了基于時域或頻域的通信流量統計分析。與這些攻擊方法相比，本文的攻擊直接利用了 HS-Onion方案的密碼學漏洞，不需要連續緩存多個報文進行綜合分析，因此要準確和高效得多。本文另一貢獻是給出了針對 HS-Onion方案的修正方法。這些修正以較小的代價在很大程度上降低了攻擊者篡改密文和利用解密預言機獲得有利信息的概率。

HS-Onion及此前的所有基于通用重加密的洋蔥路由方案都采用了啟發式的安全性分析方法，而其中很多方案在提出后不久即被攻破，該事實表明在嚴格定義的模型下給出形式化安全性證明是十分必要的。這也是大多數匿名通信系統在進行安全性分析時所遇到的問題。因此，下一步的工作應該包括為混合結構洋蔥路由系統建立能夠正確反映系統安全屬性及敵手攻擊能力的安全模型，并在該模型下對方案的安全性進行證明。

[1] CHAUM D. Untraceable electronic mail, return addresses, and digital pseudonyms[J]. Communications of the ACM, 1981, 24(2)∶84-88.

[2] MOLLER U, COTTRELL L, PALFRADER P. Mixmaster protocol-version 2[EB/OL]. http∶//www.eskimo.com/rowdenw/crypt/Mix/draft-moeller-mixmaster2-protocol-00.txt, 2003.

[3] DANEZIS G, DINGLEDINE R, MATHEWSON N. Mixminion∶ design of a type III anonymous remailer protocol[A]. Proceedings of the 2003 IEEE Symposium on Security and Privacy[C]. Oakland, California, USA, 2003.2-15.

[4] KESDOGAN D, EGNER J, BUSCHKES R. Stop-and-go MIXes∶providing probabilistic anonymity in an open system[A]. Proceedings of Information Hiding Workshop (IH 1998)[C]. Portland, Oregon,USA, 1998.83-89.

[5] GOLLE P, JAKOBSSON M, JUELS A. Universal re-encryption for mixnets[A]. Proceedings of the 2004 RSA Conference, Cryptographer’s Track[C]. San Francisco, USA, 2004.163-178.

[6] GOMULKIEWICZ M, KLONOWSKI M. Onions based on universal reencryption anonymous communication immune against repetitive attack[A]. International Workshop on Information Security Applications(WISA04)[C]. Jeju Island, Korea, 2004. 400-410.

[7] DANEZIS G. Breaking four mix-related schemes based on universal re-encryption[A]. Proceedings of Information Security Conference 2006(ISC 2006)[C]. Samos, Greece, 2006.46-59.

[8] KLONOWISKI M, KUTYLOWSKI M, LAUKS A. Repelling detour attack against onions with re-encryption[A]. Proceedings of International Conference on Applied Cryptography and Network Security 2008 (ACNS 2008)[C]. New York, USA, 2008. 296-308.

[9] BORISOV N, KLONOWISKI M, MIROSLAW K. Attacking and repairing the improved ModOnions protocol[A]. Proceedings of the 12th International Conference on Information Security and Cryptology[C]. Seoul, Korea, 2009. 258-273.

[10] BORISOV N, KLONOWISKI M, MIROSLAW K. Attacking and repairing the improved ModOnions protocol-tagging approach[J]. KSII Transactions on Internet and Information Systems, 2010, 4(3)∶ 380-399.

[11] 陸天波, 秦寶山, 李洋. 重加密匿名通道WGRe[J]. 通信學報, 2009,30(4)∶66-73.LU T B, QIN B S, LI Y. WGRe∶ a re-encryption anonymous tunnel[J].Journal on Communications, 2009, 30(4)∶66-73.

[12] 時金橋, 方濱興, 郭莉. 抵御MIX重放攻擊的混合結構消息報文機制[J]. 通信學報, 2009, 30(3)∶21-26.SHI J Q, FANG B X, GUO L. Hybrid-structured onion scheme against replay attack of MIX[J]. Journal on Communications, 2009, 30(3)∶21-26.

[13] DINGLEDINE R, MATHEWSON N, SYVERSON P. Tor∶ the second-generation onion router[A]. Proceedings of the 13th USENIX Security Symposium[C]. San Antonio, USA, 2004. 303-320.

[14] CAMENISCH J, STADKER M. Efficient group signature schemes for large groups[A]. Proceedings of Crypto’97[C]. Santa Barbara, California, USA, 1997. 410-424.

[15] WANG Q Y, MITTAL P, BORISOV N. In search of an anonymous and secure lookup∶ attacks on structured peer-to-peer anonymous communication systems[A]. Proceedings of the ACM CCS 2010[C]. Chicago,Illinois, USA, 2010. 308-318.

[16] PFITZMANN B. Breaking efficient anonymous channel[A]. Proceedings of Eurocrypt'94[C]. Perugia, Italy, 1994. 332-340.

[17] LING Z, LUO J Z, YU W. A novel cell counter based attack against tor[A]. Proceedings of the ACM CCS 2009[C]. Chicago, Illinois, USA,2009. 578-589.

[18] ZHU Y, FU X W, RICCARDO B, et al. Analysis of flow-correlation attacks in anonymity network[J]. International Journal of Security and Networks, 2007, 2(1)∶137-153.

[19] STEFAN S, SEBASTIAN C. Using linkability information to attack mix-based anonymity services[A]. Proceedings of 9th International Symposium on Privacy Enhancing Technologies[C]. Seattle, WA,USA, 2009. 94-107.