基于信息熵的MIX网络关系匿名度量

摘 要:关系匿名对于报文目的站的分布有着很高的敏感性,特别是网络浏览的齐夫分布斜率特征提供了弱关系匿名。文中对关系匿名给出一个正式的定义和度量方法,同时考虑到了路由选择算法,并结合了信息理论评估中的熵和最小熵的概念。最后,在几个仿真的MIX网络中,对关系匿名进行了计算,并以图解的方式呈现出来。

关键词:熵;匿名度量;秘密;Mix网络

中图分类号:TP309,TP393.08 文献标识码:A

Based on the information entropy, the measurement of MIX network anonymity

SONG Wei,LIU Jing-sen

(Henan university,Henan Kaifeng 475004)

Key words: Entropy;Anonymity;Privacy;Mix Networks

由Chaum[1]第一个提出来的MIX网络,使得我们能够在不太安全的网络中获得匿名通信。直观的说,MIX就是一个能够接受和转发报文的中继服务器,由它来重路由通信报文,使得攻击者不能够将进出服务器的报文进行有效的关联,从而保护了通信双方的匿名关系。在这里,我们将重点放在关系匿名的研究上。正如Pfitzmann et al定义的那样[2],“关系匿名意味着谁和谁正在通信将变得难以捉摸”。这个特性对于MIX网络中很多实际的应用是十分重要的。

发送者匿名和关系匿名并没有直接的可比性。假设有一个由发送者组成的集合,在某个时间段内同时访问一个敏感的网站,并且网络对这些发送者也提供了可靠的发送者匿名,在这种情况下,通过分析网络中的通信报文,攻击者就会很容易推断出这些访问有一个共同的目的站,这也就打破了发送者和网站之间的匿名关系。这个假设表明了:(A)仅仅发送者匿名不足以保证与接受者之间的关系匿名;(B)关系匿名对于报文的目的站分布是十分敏感的;(C)在某些目的站分布中,即使最完美的安全措施也不能保证关系匿名的可靠性。

对于“不可怀疑”(beyond suspicion[3])特性,即正在通信中的目的站机器不会表现出和其它的机器有什么不同。标准的度量方法并不能反映出这个特性,例如,在一个高熵的分布中,一些目的站就有可能以很高的概率被关联起来。因此就需要一个可供替代的匿名度量方法使得能够更好的反映出匿名集合中不同对象的概率比。

本文研究接关系匿名性的度量方法,给出了一种关系匿名的度量方法,着重用最小熵(min-entropy)来对匿名性进行度量。

1 定义和度量

假设在一个MIX网络中,有N个发送者S1,...SN和H个目的地D1,...DH。每一个发送者Si发送ni条报文Xil, . . . ,Xini,每一个消息Xik都有一个目的站,令RAMSGik为潜在目的站的概率分布。

1.1熵

给定一个报文以及这个报文的潜在目的站概率分布,标准的信息论匿名度量是这个分布的熵。Diaz等人在文献[4]和文献[5]中分别提出了以熵为匿名衡量标准,文献[6]也指出用熵比用匿名集能更好地衡量基于MIX的匿名系统的匿名性。从物理意义上来说,熵值是衡量匿名集平均信息量的标准,熵值越大,表示越难以区分,即匿名性越好。RAmsgik[1...H]的熵可以如下计算:

RAentx=-RAmsg[j]log(RAmsg[j])。

1.2最小熵

熵并不总是能够捕捉到正确的匿名特性,假设有100个目的站,其中99个目的站的概率分布都为0.009,1个目的站的概率分布为0.109,计算可得这个分布的熵就为6.40,接近理论的最大值6.64。然而,因为有一个目的站的概率是其它任何一个目的地的100倍,“不可怀疑”特性因此而被破坏了。因此,我们提出最小熵(min-entropy),最小熵能够捕捉到最有可能目的地的概率,定义如下:

RAmin=-log2((RAmsg[j])

2 计算匿名性

令m1,m2,…,MM为网络中的MIX结点,所有的路由长度都为L,MIX结点和目的站结点不同。每一个发送者Si发送报文Xi1,. . . ,Xini,并令N'=n。对于每一条报文Xi(1≤i≤N'),fi表示一个在网络中进行的M2M(MIX to MIX)消息传递的时间序列。

报文在MIX结点中传送时由对偶密钥对其进行加密,并假设攻击者能够观测到每条加密报文的源结点和目的站结点。在这里需要忽略一些主动攻击,如洪泛,长时间统计攻击以及流量分析等等,这些攻击会导致比我们实验所展示的更严重的匿名失败。

假设有L个离散的时间点t1, . . ,tl,每一个时刻代表消息路由中的一跳。在时间tj,攻击者观测到一个报文序列qj1,...qjN'到达了MIX中的某个子结点,每个qji和xi'都是一一对应的。

将这种传送定义为矩阵Flow:N'×LM,Flow[i,j]包含了报文qji的目的站结点。定义FlowCount[l,j]=count1≤k≤N',即在[tj,tj+1]时间段内进出结点ml的消息个数。

在时间t1,有报文x∈{x1,...xN'}进入了网络。令ix为报文指标,递归地计算概率Pmsgx[i,j],它表示报文qji在时间tj被发现的可能性。初始化,对于所有的i,Pmsgx[i,1]=1 i=i0 其它,在时间tj(2≤j≤L),报文qji(1≤i≤N')。对于每一个结点ml(1≤l≤M),定义:PthruMixx[l,j]= Pmsgx[i,j],它表示在时间tj通过结点ml的报文所携带的内容x的概率。攻击者不需要知道这条报文是哪一个。然后定义:

Pmsg[i,j]=Pmsg[i,j-1] m被破坏 m正常

直观地看,这意味着,相比之下,任何通过被破坏结点的序列对于攻击者来说都是可见的,并且也不会改变一个给定报文所含内容x的概率。

最后,对于任意的j,1≤j≤H(H为目的站个数),有PAmsgx[j]= pmsgx[k,L]

可以用这个分布计算关系匿名。令xi1, . . . ,xini是在时间t1由发送者Si发送的报文。那么发送者Si正在和目的站Dj通信的概率为:RAij=1-(1-RAmsg[j])

3 验证

验证试验用在第三部分描述的方法对几种MIX网络进行匿名关系的计算,假设目的站的数量和发送者的数量是相等的,并且目的站接收报文都是随机的。在每一个试验中,随机地为每条报文生成一个5跳的路由,所有的MIX结点被分成5组,第i跳的目的站从第i组中的MIX结点中随机选择。对于每一跳的设置,计算所有发送者的目的站熵和最小熵,并取得模拟的平均结果。

当使用最大熵做比较的时候,由于我们的目标就是要通过比较目的站的偏态分布和均衡分布下的匿名性来论证非均衡的目标选择的影响,所以不考虑非均衡的目的站选择。当一个使用者只知道其它使用者的数量,网络的拓扑结构,以及知道哪些MIX结点被对手所控制的时候,那么均衡目的地分布下的匿名性就提供一条基线使得实际的匿名性能够比较。

在先前的一些针对大型MIX网络的匿名研究中,都是假设在每一跳中所有的报文都是在网络中均衡分布的,但现实中的情况却不是这样,除非报文和MIX结点的比值非常大。因而不合理的路由选择对匿名失败起着决定性的作用。假如某个被选择的路由和其它用户选择的路由没有重叠的话,即使它路由上的所有MIX结点都是可以信赖的,那么这个路由也只能得到弱匿名。正如我们下面的实验所展示的,这种影响在网络中表现得尤其显著。

3.1目的站分布的影响

由于关系匿名对报文目的站分布很敏感。第一个试验考虑了在各种偏态参数下的一个均衡随机分布(每一个发送者从确定好的所有可用目标结点中随机均衡的选择目的站)。在齐夫分布中,第n个最流行元素产生的相对概率为,a为斜率。人们认为现实世界的WEB浏览模式是遵循一个齐夫分布的,例如,少部分的网站却占有通信目的站的绝大部分[7]。

在图一中, 展示了一个有50个结点的自由路由网络的试验结果,并且在这个网络中每一个结点都有四分之一的几率被破坏。发送者的数量从50到500依次递增。除了测量了关系匿名外,还为在网络中传输的每一条报文计算了发送者匿名。

3.1.1自由路由选择导致的匿名失败

在图1中我们发现了由于不考虑目的地分布而导致的一个明显的匿名失败。这可以由在一个自由路由网络中随机路由选择的统计学特性来解释。

例如,假设有一个由50个发送者和50个MIX结点组成的自由路由网络。即使每一条报文的目的站都是随机均衡选择的,那么能保证通常用户的有效匿名的结点数是8而不是50。产生这种情况最根本的原因并不是25%的MIX结点被破坏。为了更好的混淆这些报文,不同报文的路由必须有一些重叠结点,并且,报文还必须近似在同一时刻到达这些重叠结点,这在我们理想化的模型中意味着MIX结点必须在它们各自的路由通道中重叠一个相同的一跳。

3.1.2偏态目的地分布导致的匿名失败

弱关系匿名是和偏态匿名分布相关联的。例如,假如有500个发送者的话,那么偏斜率为1的齐夫分布所产生的关系匿名熵就为6。这也就意味着匿名集的有效大小为64。

假设大多数的用户和一个相对比较小的目的地子集通信,即便网络为每一条报文都提供了发送者匿名,那么对于攻击者来判断某个用户正在和谁通信也将很容易。换句话说,在遵循一个高偏态分布的WEB浏览模式中,即使最好的MIX网络也只是提供弱匿名。

3.1.3高熵并不能保证关系的“不可怀疑”特性

以熵度量匿名性和以最小熵度量匿名性之间有着本质的不同。在很多情况下,熵并不足以度量匿名性。例如,假设在有500个发送者的偏斜率为1的齐夫分布中,网络中平均报文的潜在目的站分布的熵大约为6,它和一个大小为64的有效匿名集合相当。这也表明潜在目的站分布具有很大的随机性,但是某些目的站的可能性要大于其它的结点,因而匿名的"不可怀疑"特性也就不再存在。

3.2路由选择算法的影响

在第二个试验中,对不同的路由算法进行比较,发现逐渐增多的可行路由数量有可能导致更差的匿名性,只有在同一个时间接收到倍增的报文的时候来增加一个路由结点才是有用的。当限制发送者对于每一跳的路由选择时,那么倍增的报文有可能在同一跳的时候通过相同的MIX结点,这也就导致了更好的匿名性。在一个分层网络中,每一跳的路由选择都是很严格的,极大降低了可行路由的数量。也就是说一个分层的网络能够比自由路由网络提供更好的匿名性。

在图2中,分别计算了自由路由和分层网络的关系匿名度。目的地结点的数量和发送者相等,并且发送者的目的地选择遵循偏斜率为1.2的齐夫分布。

当发送者数量和MIX结点的数量相当的时候,两种匿名度有着明显的不同。分层网络由于可行路由的数量更少而提供了更好的匿名性。这种不同会随着路由数量的增加而逐渐消失,并且由非均衡目的地选择导致的匿名失败影响了路由选择。

4 结束语

本文对任意路由配置的MIX网络的关系匿名给出了一个定义和计算方法。在遵循一个高偏态分布的WEB浏览模式中,当被破坏的MIX节点数相对较小的时候,最好的MIX网络也只是提供弱匿名。同时试验也验证了路由选择算法的重要性,除非路由的数量远大于MIX结点的数量,那么一个分层的网络还是比自由路由网络提供更好的匿名性。最后,试验呈现了匿名集的高熵并不需要网络提供匿名性的“不可怀疑”。甚至在高熵的网络中,不同的分布概率存在着明显的差别。这就需要有一个新的匿名性度量方法来更好的捕捉到更大匿名集中的“不可怀疑”特性。

参考文献:

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

[2]PFITZMANN, A., K¨OHNTOPP, M., AND SHOSTACK,A.Anonymity, unobservability, and pseudonymity - a proposal for terminology. Manuscript, June 2001.

[3]REITER, M., AND RUBIN, A. Crowds: Anonymity for web transactions. ACM Transactions on Information and System Security 1, 1 (1998), 66-92.

[4]Claudia Diaz,Jorls Claessens,Stefaan Seys,et a1.1nform ation theory and anonymity[A].B.Macq and J.-J.Quisquater (Ed.).Proceedings of the 23rd Symposium on Information Theory in the Beneluxl-C],Louvain la Neuve,Belgium,May,2002.179-186.

[5]Claudia Diaz,Stefaan Seys,Joris Claessens,et a1.Towards measuring anonymity[C].Privacy Enhancing Technologies 2002,San Francisco,CA,USA,April,2002,54-68.

[6]Andrei Serjantov,George Danezis.Towards an information theoreticmetric for anonymity [C].Privacy Enhancing Technologies 2002,San Francisco,USA,April,2002,41-53.

[7] BRESLAU, L., CAO, P., FAN, L., PHILLIPS, G., AND SHENKER, S. Web caching and Zipf-like distributions:evidence and implications. In Proc. INFOCOM (Volume 1)(1999), pp. 126-134.