对一种混合结构洋葱路由方案的密码学分析

李龙海，付少锋，苏锐丹，车向泉

（西安电子科技大学 计算机学院，陕西 西安 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.