网络编码的安全检测

第五期通信集汇密码学与信息安全·PAGE218··PAGE217·网络编码的安全检测周玉涂晓东（电子科技大学光纤通信与宽带网络实验室成都610054）摘要：在随机分布式网络中引入网络编码技术，会在信息传递过程中产生新的安全问题。本文针对网络编码的安全检测方法做了一个全面的综述。首先，介绍在信息传递过程中受到拜占庭攻击采取的拜占庭修改检测法；接着，详细论述拜占庭修改检测法中的一个关键技术—同型哈希函数，并给出了相关算法和证明；最后，文章详尽地介绍了一种效率更高的合作型安全措施，并在此基础上提出了一种改进方法。关键词：拜占庭修改检测；同型哈希；合作型安全措施SecuredetectionofNetworkCodingZhouYuTuXiaodong（BroadbandCommunicationNetwoksLab,UESTCChengdu610054）Abstract：TheintroductionofNetworkCodingintorandomizeddistributionnetworks,willbringaboutnewsecureissueintheinformationtransmission.Thethesismakesacomprehensivesummarizationofsecuredetectiononnetworkcoding.Firstly,itpresentsByzantinemodificationdetectionwheninformationtransmissionsuffersByzantineattack.Secondly,itdetailedlydescribesakeytechnologyinByzantinemodificationdetection—HomomorphicHashingfunction,thenitgivesrelatedarithmeticandproof.Lastly,itmakesanelaborateexplationofamoreefficientmethod—cooperativesecuritytechniqueandbringupanimpromentonit.Keywords：Byzantinemodificationdetection;HomomorphicHashing;Cooperativesecurity1引言在多数需要承载广播业务的网络中，网络编码技术的引入可以提高和改善多项网络性能指标，给网络技术的发展带来巨大的影响。网络编码是在各个节点处对接收的信息进行线性组合后发送出去，因此数据包在传递的过程中很容易被篡改，即遭到拜占庭攻击，信息的安全性遇到了严重的考验。网络编码的安全检测就是及时地分析和检测出被篡改的数据包，尽早地清除错误包，以确保新的正确包被接收。2拜占庭修改检测[1]在多源组播网络中，分布式网络编码能够灵活和稳定的传递和压缩信息。当信息传递中遭到拜占庭攻击而使接收端受到欺骗时，使用简单的哈希检测，就能够得到很高的检测效率。再通过传输路径的多样化和使用网络编码，使得攻击方不能较好地得到接收接点的相关正确信息。从而能够进行拜占庭修改检测。拜占庭修改检测法的第一个关键之处在于传递路径的多样性，以及随机分布式选择码字。因此攻击方很难获得或预测在接受节点收到的所有其他数据包中的源信息的确切组合。只要这些修改不是基于了解接收节点所收到的其他数据包信息而设计的，那么接收节点使用这种方法就具有很高的可能性检测出拜占庭修改。要使该机制有效，必须保证如果一个拜占庭攻击方完全了解其他节点收到的其他数据包信息，则不能设计和提供修改包。在该机制中，将在检测可能性和开销间做一个折中——开销增加，则检测可能性也随之增加，且在接受节点收到的内容不被攻击方知晓的没有被修改的数据包数量也随之增加。在该检测法中，另一个关键之处就是使用简单的多项式哈希函数代替传统的密码学哈希函数。在每个数据包中加入一个简单的哈希数值，仅仅增加少量的计算量和通信开销。由于数据包中加入了哈希数值，增加了检测数据包错误的可能性。通常情况下，用一个哈希符号就能保护多个数据符号。这种在多源组播网络中检测拜占庭修改的新颖的、低开销的方法就是基于分布式随机网络。它的有效性在于拜占庭攻击方不能根据对其他节点收到的所有数据包信息的了解而设计插入修改的数据包，也不依赖哈希设计的复杂度。因此，这种方法对于拜占庭攻击具有很高的检测效率。3同型哈希函数3.1现存模型用哈希函数对接收到的文件进行确认，有两种方法：哈希所有的输入符号和哈希控制包。在介绍这种方法之前，我们先介绍一下在线编码。在线编码里包含三部分逻辑元素：预编码、编码和解码。发送方首先通过预编码初始化编码系统，即：输入文件F有n个信息包，输出有nδk个辅助包。k是数值比较小的常数，例如3。δ是一个常量，一般大小在0.005左右。预编码所做的就是给每个信息包加上k个截然不同的随机选择的辅助包。这个过程在实际操作中并不是随机的，信息包和辅助包之间的关系可以用函数表示：。是输出文件的大小。用在线编码完成预编码后，就对计算Merkle哈希树。发送方把文件F和哈希树一起发至网络，哈希树比原始文件小很多，且其大小是n的线性比例。服务器把n(F)映射为H(F)，H(F)即哈希树的根部，接收节点从网络中恢复哈希树的其余部分，并以此判断是否与根部线性相关。一旦度为一（度：从发送方到接收方有多级节点，根据信息传递的先后顺序，多传递一级节点，度增加一个单位）的控制包到达，立即在哈希树中队相关叶进行确认。同样，解码器从较高度的控制包＜,＞恢复输入符号，接收方对恢复后的进行确认。如果接收的包被确认为正确的，则可以判断＜,＞为正确的，并标记为“正确”，反之，则标记为“伪造”。以上介绍的方法是哈希输入符号。第二种方法是哈希输出的控制包。发送方产生n/r个控制包，计算其哈希树。每次就直接对控制包进行确认。3.2同型哈希函数同型哈希函数结合了以上两种方法，以同型抗碰击哈希函数为基础提出两种可以证明的协议。3.2.1全局同型哈希函数首先设立一组哈希参数G=(p,q,g),其余参数如表1所示。表1参数表名称特征描述举例离散对数安全参量1024离散对数安全参量257随机素数，1续表名称特征描述举例随机素数，，1包的大小16KBm，子包的大小512bitsg基本参量G哈希参量n原始文件的大小1GBk预编码参量3未被恢复的信息包片断0.005预编码后的文件大小，1．015GBe编码消耗0.01d确认包的平均度8.17算法如下：1>PickGroup(,,m,s)SeedPRNGGwiths.DoqGen()ppGen(,)Whilep=0doneFori=1tomdoDoxG(p-1)+1(modp)While=1doneDoneReturn(p,,g)2>qGen()doG()WhileisnotprimedoneReturn3>pGen(,)Fori=1to4doXG()cX(mod2q)pX–c+1//Notep1(mod2q)ifpisprimethenreturnpdonereturn0文件表述为：矩阵，矩阵为的原始文件矩阵，为的辅助矩阵。令。哈希函数的定义：文件的哈希函数，即的行向量：哈希函数满足线性相关性，即：证明：编码包：，其哈希函数..指数可以用另一种方式表示为：（是除以的整数）因此：由费马小定理：（是可以被整除或可整除的自然数）得出：3.2.2总通同型哈希函数总通哈希系统是全局哈希系统的优化，在全局里各种参数是由算法产生的，且g是已知的。总通里选取了全局里的p和q，随机产生一个r，计算。文件的哈希函数即：。首先计算，然后对每个文件包进行一次模块指数运算即可。这种方法大大减少了计算量。证明：，，3.2.3提高计算效率的方法代替对每个控制包进行精确确认，提出了对一批包进行概率性确认。的矩阵C代表t个控制包为一批，即算法如下：1.令，随机选择，令矢量2.计算矢量3.计算，.如果发送方受到攻击，则4.计算，那么5.确认还有一种方法是令为所有L编码包的线性组合，即，，。这种方法的好处是节点只要确认一个包而不是L个包。但这种方法会受到拜占庭攻击，解决方法是定义一个因子，令，。3.2.4哈希树哈希树是根据密码学里的迭代哈希函数演变出来的。算法如下：,对，对最小j存在4合作型安全措施点对点的分布网络能够抵抗内容的恶意破坏，而现行系统都是用传统的密码学的签名技术和哈希函数进行确认。可是这些技术计算复杂，不适合效率更高的系统。文献[7]中提出了合作型安全措施。4.1安全机制首先假设节点确认包的概率为p，通过确认的包被标记为“安全”，未通过确认的包被放在“不可靠”窗口。包的确认是以前提到的“一批”为单位的。一旦某节点确认它的“不可靠”窗口，正确的包标记“安全”，然后重置“不可靠”窗口。每个节点是独立的对收到的包进行确认。但是侦查受攻击的包就需要节点之间的合作。一旦某节点侦查到一个遭到攻击的包，立即向其他邻节点发送警报。为避免未被攻击的节点操作警报信息，每个节点拥有一个带有ID的“不安全活动”工作台：a>这些节点下载在“不可靠”窗口进行编码的信息包；b>这些节点在“不可靠”窗口中传送信息包。如果接收的警报不是从哪个窗口发出的，则应该删除这个警报。警报信息在相邻节点间传送，直至所有受感染节点得到警报。如果窗口为空，警报则停止传送。然而，发送警报前必须确认已经检测到受攻击包。如果拓扑结构里含有环，可能发生一个节点收到多次同一个警报。为避免这种情况，碰到以下两种情况：a>“不可靠”窗口为空；b>重复的警报不是从“不安全”工作台发出的，则删除此警报。节点还采取了以下辅助措施：a>节点把信息包放在窗口，把确认的包放在后台，两者隔离；b>位于窗口里的信息包不被用于网络编码；c>以概率1对包进行检测，直至窗口被完全检查。4.2防止伪造警报机制合作型安全机制的一个潜在缺点是节点可能受到DOS攻击，即发送和收到伪造警报。文献[7]中提出了随机去效验和的方法。它能有效地阻止伪造警报进入分布式网络，同时确保正确包的传送速度不会降低。首先定义随机矢量为，那么每个包的效验和为，那么.注意到每个效验和都是由一个随机矢量产生的。每个效验包的大小和原始包的大小一样。将这种方法和哈希结合在一起，节点可以快速的在传送过程中对警报确认。节点下载信息前，先选取一个随机矢量，计算相应效验和。每个节点独立的选取自己的随机矢量和计算效验和。一旦节点收到警报，看它是否是从“不可靠”窗口发出，或者用效验和进行确认。至此，节点产生所有编码包德线性编码组合包e，，是组合因子。为确认包是否遭到攻击，进行以下检查：4.3改进方法在防止伪造警报机制里提及了运用随机去效验和确认和检测接收包的方法，此种机制实际上是将全局哈希函数中的原理运用在合作型安全措施里。如果能在此基础上结合总通同型哈希函数的方法，不是只对单个数据包计算效验和，而在接收方对整个文件再进行一次模块指数运算。这样既在接收的同时加强了系统的安全性，又没有增加过多的计算量。5结束语本文介绍的方法都充分利用了网络编码的特性，很好的降低信息在传递的过程中遇到的恶意攻击的可能性。对于后面研究网络编码的安全检测会有一定的帮助。参考文献[1]T.Ho,B.Leong,R.Koetter,M.Medard,M.Effros,andD.R.Karger.Byzantinemodificationdetectioninmulticastnetwoksusingrandomizednetworkcoding[J].IEEEInter-ISIT2004,June.[2]R.C.Mekle,Adigitalsignaturebasedonaconventionalencryctionfunction[J].AdvancesinCryptology-CRYPTO87,SantaBarbara,[3]M.Bellareand,D.Micciancio.Anewparadigmforcollision-freehashing[J]:Incrementalityatreducedcost.AdvancesinCryptologyEUROCRYPT97,1997.[4]NationalInstituteofStandardsandTechology.DigitalSignatureStandard（DSS)[J].FederalInformationPrecessingStandardsPublication182-2,U.S.Dept.ofCommerce/NIST,2004.[5]M.Krohn,M.Freedman,D.Mazieres.On-the-flyverificationofratelesserasurecodesforefficientcontentdistribution[J].IEEESymposiumonSecurityandPrivacy,Berkeley,[6]NielsFerguson,BruceSchneie.PracticalCryptography[M].PublishingHouseofElectronicsIndustry.[7]C.Gkantsidis,P.Rodriguez.Cooperativesecurityfornetworkcodingdistribution[J].IEEEIntel.Symp.Inf.Theory,2004.第五期通信年会密码学与信息安全·PAGE346··PAGE223·EncryptionRevisited:ConsistencyProperties,RelationtoAnonymousIBE,andExtensions.InAdvancesinCryptology–Crypto2005,volume3621ofLNCS,pages205–222.Springer-Verlag,2005[9]DanBoneh,GiovanniDiCrescenzo,RafailOstrovsky,andGiuseppePersiano.Publickeyencryptionwithkeywordsea