抗数据包插入的高效群组数据源认证协议.doc

第11A期唐宏等：抗数据包插入的高效群组数据源认证协议99抗数据包插入的高效群组数据源认证协议唐宏1，祝烈煌1，李剑2，曹瑞强1（1. 北京理工大学 计算机科学与技术学院 智能信息技术北京市重点实验室，北京 100081;2. 北京邮电大学 计算机学院, 北京100876）摘 要：为了解决SAIDA、eSAIDA等协议不能抵制数据包恶意插入和PRABS协议的通信荷载太大等问题，提出了一种能抵抗数据包插入的高效群组数据源认证协议（EPJRSA）。通过merkle散列树，EPJRSA协议可以在验证纠删码和数字签名之前就能检验出非法插入的数据包。EPJRSA的通信代价大约是PRABS的7%9%,计算和验证认证消息的计算代价也比PRABS少。结果表明，EPJRSA既能抵抗数据包插入，其性能又优于PRABS。关键词：群组通信；数据源认证；纠删码；merkle散列树中图分类号：TP393.08 文献标识码：B 文章编号：1000-436X(2008)11A-0096-05Efficient packet-injection resistant data source authentication protocol for group communicationTANG Hong1, ZHU Li-huang1, LI Jian2, CAO Rui-qiang1(1. Laboratory of Intelligent Information Technology, School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081,China;2. School of Computer, Beijing University of Posts and Telecommunications, Beijing 100876, China)Abstract: In order to resolve of the problem that SAIDA and eSAIDA cannot resistant packet injection and PRABSs communication cost is too large, an efficient packet-injection resistant multicast source authentication protocol (EPJRSA) was proposed. Using merkle hash tree, EPJRSA can find packets injected by attacker before verifying erasure codes and signature. EPJRSAs communication cost is about 7%9% of PRABS. The cost of computing and verifying authentication information in EPJRSA is also less than in PRABS. The result shows that EPJRSA has better performance than PRABS and can resistant packet injection.Key words: group communication; data source authentication; erasure code; merkle hash tree1 引言收稿日期：2008-07-01基金项目：国家自然科学基金资助项目(90604012); 教育部博士点青年基金项目(20070007071)Foundation Items: The National Natural Science Foundation of China(90604012); The Research Fund for the Doctoral Program of Higher Education(20070007071)随着IP组播、应用层组播、无线网络、网格计算、P2P计算、普适计算等网络技术和分布式计算技术的飞速发展，各种群组通信应用（如网络视频会议、视频点播和直播、手机数字电视、分布式网络存储、付费新闻、计算机支持的协同工作、网络游戏等）正悄然兴起，具有广泛的应用前景。由于群组通信数据更容易受到窃取、篡改、伪造、重放等攻击，群组通信的安全问题也越来越受到重视。其中，群组通信的数据源认证协议是群组安全的主要研究内容。群组数据源认证保证组员接收到的数据包确实是由组内的某个特定的组员发送的，它不但保证了非组员不能伪造或修改据，而且还保证了组内其他组员不能伪造或修改该数据包。TESLA1 及其改进方案2,3通过推迟发送计算消息认证码的密钥，实现群组数据源认证。由于TESLA协议具有计算速度快、认证荷载少、实时性好等特点。但是TESLA协议的安全条件是发送方和接收方之间进行时间同步，这在分布式网络环境是很难达到的。通过将前面数据包的散列值嵌入后面消息包中，并对最后消息包进行数字签名，可以有效提高源认证协议的性能，该协议存在不能抵抗数据报的丢失的问题。EMSS1及其改进方案4,5通过将数据包的散列值添加到多个数据包后面提高了协议的可靠性，通过增加数字签名包的个数减少了接收方的认证延迟。这些协议最大问题就是一旦签名包丢失，则由该签名包所认证的所有数据包将不能被验证，这在丢包率高的无线网络或者被攻击者控制的开放网络中是很容易发生的。为了解决签名包丢失问题，SAIDA6，eSAIDA7使用纠删码将认证信息（包括散列值和签名）分成N小段，只要接收方接收到其中的m（mN）段就可以恢复认证信息。然而协议不能处理攻击者恶意攻击，只要攻击者伪造一个消息包，接收方将恢复错误的认证信息，从而不能完成对数据包的源认证。PRABS8,9协议结合纠删码和单向累计函数（one-way accumulator）使得接收方只需要计算常数次签名验证操作就能验证解码得到的认证信息，有效解决了伪造数据包插入问题。PRABS最大的问题就是认证荷载太大，通信代价太高。Tartary等10,11使用纠删码将数据包和认证信息作为一个整体进行编码和解码，不但可以认证数据包还可以恢复丢失的数据包，但是它们需要增加更多的冗余信息。2 EPJRSA群组数据源认证协议EPJRSA将整个认证消息分成连续的数据，每个数据块B包含N个数据包P1,P2,PN。我们又将每个数据包P1,P2,PN分成Ns组(G1,G2,GNs),每组数据包含N/Ns个数据包，其中N/Ns是2的指数方。首先对每组数据构造merkle散列树获得根节点的散列值(h1,h2,hNs)。然后计算h1,h2,hNs的数字签名,并对h1|h2|hNs|进行纠删编码。最后把编码结果和merkle散列树认证信息附在数据包后面。接收方只需要接收到部分消息就可以恢复出每组数据的根节点散列值以及数字签名，并使用merkle散列树8认证信息验证接收到数据包是否被修改或伪造。2.1 merkle散列树构造设Gi=P(i1)*N/Ns+1,P(i1)*N/Ns +2,Pi*N/Ns为第i组数据，则对Gi构造的merkle散列树过程如下。1) 计算P(i1)*N/Ns+1,P(i1)*N/Ns +2,Pi*N/Ns的散列值H(i1)*N/Ns+1,H(i1)*N/Ns +2,Hi*N/Ns，其中H(i1)*N/Ns+j =H(P(i1)*N/Ns+j)，H()为散列函数，1jN/Ns。2) 每个散列值对应一颗完全二叉树的叶子节点。3) 设二叉树的中间节点以及根节点的值为左右孩子节点散列值分别为Hl和Hr,则该节点的值为H(Hl|Hr)。设N=64,Ns=8,则G2对应的merkle散列树如图1所示。G2根节点散列值h2=h9-16。图1 组数据merkle散列树2.2 根节点散列值和签名信息的纠删编码通过构造每组数据的merkle散列树计算得到每组数据根节点的散列值，我们就可以对根节点散列值和签名信息进行纠删编码。设纠删编码算法Disperse(F,m,n)表示将消息F分成大小为|F|/m的n个纠删码F1, F2,Fn，表示使用发送方sender的私钥对消息M进行签名，则根节点散列值和签名信息的纠删码S计算如下:(1)(2)(3)2.3 认证消息包构造认证消息包包括数据包原始信息、merkle散列树认证信息以及纠删码信息。设数据包Pi对应认证消息包为，则(4)其中为对应第i块纠删码，为对应的merkle散列树认证信息。由从对应散列树的叶子节点到根节点的所有兄弟节点的散列值组成。设为对应散列树的叶子节点到根节点的所有兄弟节点的下标，则(5)如图1中，P10对应的叶子节点为n10，从n10到根节点n9-16的节点有n10、n9-10、n9-12，它们对应的兄弟节点分别为n9、n11-12、n13-16。所以， ,。2.4 消息认证算法接收方接收到部分消息后,其中，,为最大允许攻击伪造的数据包比例，开始执行如下消息认证算法。1) 分组。根据中的下标，将接收到的数据分组。2) 计算各组根节点散列值。根据接收到消息包中的merkle散列树认证信息计算根节点散列值。由于数据包有可能被修改，可能算出多个根节点散列值。取计算出相同根节点散列值的数据包个数最多的散列值为该组的散列值。如果计算出相同散列值的数据包个数最大值小于，则中断算法。3) 认证消息纠删解码。剔除个组中计算出散列值不相同的数据包，如果剩余数据包个数小于m,则中止算法；否则，执行解码算法 恢复出。4) 验证散列值的签名。使用发送方的公钥验证各组散列值的签名(6)如果验证通过则表示数据包没有被修改或伪造。3 性能分析衡量群组数据源认证协议性能的主要指标有发送方延迟、接收方延迟、计算认证消息速度、验证认证消息速度、认证消息长度以及抵抗数据包丢失和插入能力。这些性能指标相互冲突，在很多情况下不能同时满足，在具体应用时需要进行权衡。如果接收方的存储空间有限或者实时性要求高的视频应用，就要求使用接收延迟小的认证协议；如果网络带宽资源非常有限，就需要控制认证消息的长度；如果接收方的计算能力有限，就要求使用验证认证消息速度快的认证协议。TESLA协议需要接收方和发送方进行时间同步，不适用于分布式网络环境。EMSS协议的签名包不能丢失，并且在丢包率高的群组应用中,为了接收方能有较好的认证概率增加的通信荷载太大。EPJRSA、SAIDA、eSAIDA、PRABS协议都将消息进行分块，并使用纠删码使得认证消息分散到整块数据包中，能较好地抵制数据包丢失。在相同的假设下，我们将本文提出的EPJRSA协议和SAIDA、eSAIDA、PRABS等协议进行性能比较。假设EPJRSA、SAIDA、eSAIDA、PRABS四个协议的分块大小都是N，使用相同的纠删算法、散列算法和数字签名算法。3.1 发送方和接收方延迟由于需要进行纠删编码和解码，EPJRSA、SAIDA、eSAIDA、PRABS四个协议的发送方延迟和接收方延迟都是N。在EPJRSA协议中由于接收方可以根据接收到消息包中的merkle散列树认证信息计算同一组数据包的merkle散列树根节点的散列值，如果散列值相等的数据包个数超过某个阈值，可以初步验证数据包没有被修改，并由最后的数字签名进行认证确认。在这种情况下，EPJRSA协议的接收延迟是N/Ns。3.2 计算和验证认证消息速度设分别表示一次散列运算Hash()，数字签名计算Sign()，数字签名验证运算Verify()需要的时间， 分别表示执行一次纠删编码运算Disperse(F,m,n)和纠删解码算法Disperse(s,m,n)所需要的时间，和|表示散列长度和签名长度，则EPJRSA、SAIDA、eSAIDA、PRABS四个协议计算和验证认证一块数据包消息所需要的计算时间如表1和表2所示。表1认证消息计算时间对比协议认证消息时间SAIDAeSAIDAPRABSEPJRSA表2认证消息验证时间对比协议认证消息时间SAIDAeSAIDAPRABSEPJRSA从表1可知，EPJRSA、SAIDA、eSAIDA、PRABS四个协议都需要执行一次签名运算。EPJRSA 比SAIDA、eSAIDA执行的散列运算次数略大，但是比PRABS小。EPJRSA执行的纠删编码算法的消息长度比SAIDA、eSAIDA、PRABS都小。从表2可知，EPJRSA、SAIDA、eSAIDA、PRABS四个协议都需要执行一次签名验证运算。EPJRSA 比SAIDA、eSAIDA执行的散列运算次数大，但是比PRABS小。EPJRSA执行的纠删解码算法的消息长度比SAIDA、eSAIDA、PRABS都小。 3.3 认证消息长度设、分别表示散列和数字签名的长度, EPJRSA、SAIDA、eSAIDA、PRABS四个协议的认证消息长度如表3所示。取N=512, m=256,=160,=1024, SAIDA、eSAIDA和PRABS的认证消息长度分别为41472字节、20992字节和42912字节。EPJRSA中取Ns分别为16和32时，认证消息长度分别为3232字节和3712字节，大约为PRABS认证消息的长度的7%9%。表3认证消息长度对比协议认证消息时间SAIDAeSAIDAPRABSEPJRSA3.4 抵抗数据包丢失和插入能力通过纠删码使得接收方只需要接收到m个消息包就可以恢复出认证消息，从而四个协议都具有比较好的抵抗数据包丢失的能力。但是SAIDA和eSAIDA协议不能抵抗数据包插入，因为接收方接收到包括插入数据的消息包序列将恢复出错误认证消息，并且不能通过数字签名的验证。PRABS通过单向累计函数，可以在数字签名验证之前发现被插入的数据包，从而就有抵抗数据包插入的能力。EPJRSA通过merkle散列认证信息计算每组数据包的根节点的散列值，可以剔除被插入的数据包，也具有抵抗数据包插入能力。4 结束语本文结合纠删码和merkle散列树提出一种高效的能抵抗数据包插入的群组数据源认证协议（EPJRSA），并给出了EPJRSA协议的性能分析。通过merkle散列树，EPJRSA协议可以在验证纠删码和数字签名之前就能检验出非法插入的数据包，具有抵抗数据包插入的能力。相比PRABS，EPJRSA的通信代价是PRABS的7%9%，计算和验证认证消息的时间也比PRABS短。参考文献：1PERRIG A, GANETTI R, TYGAR J, et al. Efficient authentication and signing of multicast streams over lossy channelsA. Proceeding of 21st IEEE Symposium on Security and PrivacyC. Berkeley, California, USA, 2000. 56-73.2LIU D, NING P. Multi-level TESLA: Broadcast authentication for distributed sensor networksJ. ACM Transactions in Embedded Computing Systems, 2004, 3(4): 800-836.3WANG C K, CHAN A. Immediate data authentication for multicast resource constrained networksA. Proceedings of ACISP 2005C. Brisbane, Australia,2005. 113-121.4MINER S, STADDON J. Graph-based authentication of digital streamsA. Proceedings of 22nd IEEE Symposium on Security and PrivacyC. Oakland, California, USA, 2001. 232-246. 5CHALLAL Y, BOUABDALLAH A, BETTAHAR H. H2A: hybrid hash-chaining scheme for adaptive multicast source authentication of media-streamingJ. Computer & Security , 2005, 24(1): 57-68.6PARK J M, CHONG E K P, SIEGEL H J. Efficient multicast packet authentication using signature amortizationA. Proceedings of 23rd IEEE Symposium on Security and PrivacyC. Oakland, California, USA, 2002. 227240. 7PARK Y, CHO Y. The eSAIDA stream authentication schemeA. Proceedings of ICCSA 2004C. Assisi, Italy, 2004. 799-807.8LYSYANSKAYA A, TAMASSIA R, TRIANDOPOULOS N. Multicast authentication in fully adversarial networksA. Proceedings of 24th IEEE Symposium on Security and PrivacyC. Berkeley, CA, USA , 2003. 241