基于组群的有限路长破断式破理机

基于组群的有限路长破断式破理机

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取到上界时,它的后者若是泄密者,可以准确地判断前者是发起者.我