基于重路由匿名通信系统的负载分析

Vol.15,No.2©2004JournalofSoftware软件学报1000-9825/2004/15(02)0278基于重路由匿名通信系统的负载分析∗眭鸿飞+,陈松乔,陈建二,王建新,王伟平(中南大学信息科学与工程学院,湖南长沙410083)PayloadAnalysisofRerouting-BasedAnonymousCommunicationSystemsSUIHong-Fei+,CHENSong-Qiao,CHENJian-Er,WANGJian-Xin,WANGWei-Ping(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)+Correspondingauthor:Phn:[phone],E-mail:[e-mail],(2):278~285.:Reroutingmechanismisadoptedbyrerouting-basedanonymouscommunicationsystemssuchasMixes,OnionRouting,andCrowds,tostoreandforwarddatainapplicationlayer.Withthis,userscancommunicateinanindirectway.Thus,identityinformationsuchasIPaddressescanbeeffectivelyhiddenagainsteavesdropper.Thismechanism,however,canresultinextraoverheadinperformancesuchascommunicationdelayandparticipantpayload,whichmayaffecttheapplicationsofanonymouscommunicationsystems.Inthispaper,theparticipantpayloadinducedbythereroutingmechanismisstudiedquantitatively.Byinvestigatingtheestablishmentofreroutingpathsindetail,aprobabilityformulaforcalculatingtheparticipantpayloadisderived,whichprovesthattheparticipantpayloadisdeterminedbythenumberofparticipants,thenumberofreroutingpaths,andtheprobabilitydistributionoflengthofthereroutingpaths.Byapplyingthisformulatoapracticalanonymouscommunicationsystem,Crowds,apreciseexpectedparticipantpayload1/(1−pf)+1canbederived,whichsignificantlyimprovesReiterandRubin’soriginalanalysisO((n+1)/((1−pf)2n)),anddemonstratesthattheparticipantpayloadinCrowdsremainsconstantandisindependentofthevariationofthenumberofparticipantsinCrowds.Simulationresultsarepresentedtotestifythetheoreticalanalysis.Theconclusionscanprovideatheoreticalsupportforthedesignandimplementationofanonymouscommunicationsystems.Keywords:networksecurity;informationhiding;anonymouscommunication摘要:基于重路由匿名通信系统,如Mixes,OnionRouting,Crowds等,采用重路由机制在应用层转发数据,使实体之间的通信以间接的方式进行,从而有效地隐藏通信实体的身份信息,如主机的IP地址等.在性能方面,这种机制∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.90104028(国家自然科学基金);theNationalScienceFoundationforDistinguishedYoungScholarsofChinaunderGrantNo.69928201(国家杰出青年科学基金)作者简介:眭鸿飞(1973－),男,湖南衡阳人,博士生,主要研究领域为网络安全,信息隐藏;陈松乔(1941－),男,教授,博士生导师,主要研究领域为软件工程;陈建二(1954－),男,教授,博士生导师,主要研究领域为计算机网络,优化理论;王建新(1969－),男,博士,副教授,主要研究领域为计算机网络;王伟平(1969－),女,博士生,副教授,主要研究领域为网络安全,信息隐藏.眭鸿飞等:基于重路由匿名通信系统的负载分析279导致系统中产生额外的开销,如通信延时、负载等.着重从理论上分析了系统中的成员负载.通过深入考查基于重路由匿名通信系统的重路由机制,推导出了基于重路由匿名通信系统中成员负载的概率公式,证明了成员负载由系统中成员数目重路由路径数目以及重路由路径长度的概率分布所决定.应用该公式计算Crowds系统中成员的负载,得出精确的负载期望值为1/(1−pf)+1,改进了Reiter等人的分析结果O((n+1)/((1−pf)2n)),证明了Crowds系统的成员负载不受系统中成员数目n的影响,具有良好的可伸缩性.并通过仿真实验验证了该分析结果.其结论为设计和规划匿名网络提供了理论依据.关键词:网络安全;信息隐藏;匿名通信中图法分类号:TP393文献标识码:AInternet作为通信与信息传播的工具,正快速发展并且广为人们所接受.其中的安全与隐私问题也越来越突出.在一些应用中,如电子投票(e-voting)、电子银行(e-banking)、电子商务(e-commerce),保护用户的隐私信息已成为一种基本需求.匿名通信主要保护网络应用中通信实体的身份标识,如通信者的IP地址等,使其无法为外部观察者获知.匿名保护的形式有3种:发送方匿名(senderanonymity),即报文无法被关联到其发送者;接收方匿名(recipientanonymity),即报文无法被关联到其接收者;通信关系匿名(relationshipanonymity),即无法关联报文的发送者与接收者[1].目前的研究主要集中在发送方匿名服务方面.目前已有的匿名通信系统包括DC-Net[2,3],Mixes[4,5],AnonymousRemailer[6],LPWA[7],OnionRoutingI[8~11],OnionRoutingII[11],Crowds[12]以及Hordes[13]等.这些系统均采用重路由机制(rerouting)与/或通信流填充机制(padding),以提供匿名保护[14].重路由机制是一种应用层路由机制.它为用户提供间接通信.包含在一次通信中的多个主机在应用层存储转发数据,从而形成一条由多个安全信道组成的虚拟路径,称为重路由路径(reroutingpath).从安全信道上传送的IP数据包首部,外部攻击者无法获得真实的发送者和/或接收者的IP地址信息.因而,通信实体的身份信息被有效地隐藏.基于重路由的匿名通信系统通常提供发送者匿名和通信关系匿名服务.例如,Mixes隐藏邮件发送者的身份信息.OnionRouting隐藏实时通信中通信实体之间的通信关系.Crowds则保护Web浏览用户的身份信息,使其不被正在浏览的Web站点利用.重路由机制的引入导致在系统性能,如通信延时、成员负载方面产生额外的开销.必须从理论上对系统性能进行定量分析,以便于在实际应用中作出权衡.Guan等人采用信息熵作为匿名性度量,探讨了匿名通信系统的匿名性与重路由路径长度的关系,隐含地给出了匿名性与通信延时的关系[14].Reiter等人计算了Crowds系统中成员负载的近似值[12].Wright等人比较了几种主要匿名通信系统的匿名性及性能[15].Wang等人则提出了一种改进的重路由算法,以限制重路由路径的长度,降低通信延时[16].本文分析了基于重路由匿名通信系统中的成员负载.推导出了成员负载的概率计算公式.将该公式与Crowd系统中的重路由策略相结合,精确地计算出了Crowds系统中成员负载的数学期望值,并通过仿真系统对该结果进行了验证.1基于重路由的匿名通信系统[14]Guan等人建立了基于重路由匿名通信系统模型[14].为了便于讨论,本节给出该模型的简要描述,并引入一些新的概念.1.1系统模型基于重路由的匿名通信系统可被视为一个多代理通信系统,通信数据经过多个代理存储转发至接收者,以达到匿名保护的目的.我们的讨论将主要针对发送者匿名形式的保护,关系匿名与此类似.一个基于重路由的匿名通信系统是由网络中若干个提供匿名服务的主机组成的集合,设为V={vj|0≤jn},其中的主机vj称为成员(participant),系统中成员数为|V|=n(n≥1).在系统运行期的某一间隔时间内,如1小时,成员数目n固定为一个常数.通过安全通信信道,两两成员之间可进行直接通信.需要匿名通信服务的用户选择一个成员s∈V作为其代理成员,并将接收者地址传送给该代理成员.由该代理成员发起建立一条由多个成员组成的到达接收者的重路由路径,以用于用户和接收者之间的间接通信.形式化地,一条重路由路径Г可以表示为280JournalofSoftware软件学报2004,15(2)〈s,I1,I2,...,It,...,IL,r〉,其中,s∈V称为通信的发送者(sender),r∉V为通信的接收者(recipient),It(It∈V,1≤t≤L)为中继节点(intermediator).L(L=1,2,...)为重路由路径所经过的中继结点数目,称为路径长度.L为独立的离散随机变量,服从概率分布:{},...2,1,1)(,1)(0),(Pr1==≤≤==∑∞=kkfkfkfkLk在一个运行周期内,系统中将建立多条重路由路径.重路由路径一经建立,将被保持至该周期内结束.令P(P=1,2,...)为重路由路径的数目.某成员在一条转发路径上的一次出现称为一个转发任务.成员负载(participantpayload)为单个成员vj所承担的转发任务总数,也即vj在所有重路由路径上作为中继结点出现的总次数[15],记为Fj.如图1所示为一个基于重路由匿名通信系统.可以看到,系统中成员数目n=16,重路由路径数P=2,重路由路径分别为Г1=〈0,5,2,7,11,8,r1〉和Г2=〈5,10,3,9,r2〉.其中,成员0与5分别为Г1,Г2的发送者,路径长度分别为L1=5和L2=3.成员10在系统的重路由路径上出现1次,承担1个转发任务,故其负