基于Hash链的高效组播源认证协议*

林 庚，乔占西，于 昕

（1.北京科技大学信息工程学院 北京100083；2.河南科技大学 洛阳471003；3.北京科技大学土木与环境工程学院 北京100083）

1 引言

2 相关组播源认证方案介绍

组播通信作为一种高效的数据传输方式近年来得到了广泛的关注[1]。它的优势在于发送方只需向组播组发送一份数据，所有组内接收方都可以得到该数据，其中的数据拷贝工作由组播路由器负责，这极大地减轻了组播发送方的计算开销，并节省了宝贵的网络带宽。软件在线分发与升级、股市信息发布、IPTV、多媒体会议、视频点播、多方网络游戏等都是组播通信应用的例子[2]。但组播通信的安全机制还不完善，组播源认证是组播安全的热点问题之一。在组播源认证过程中涉及大量的发送方和接收方，而且组播数据传输过程中可能产生数据包丢失。基于上述分析，该文提出了一种能够实时进行认证并且仅产生低通信和计算开销、容忍丢包、具有抗抵赖性的组播源认证协议。

目前的组播源认证协议可分为以下两类：

· 基于MAC的源认证方案[3～5]，虽然MAC不提供抗抵赖性，但MAC可高效地生成和认证数据，从而达到提高效率的目的；

· 基于Hash的源认证方案[6～10]，采用数字签名提供抗抵赖性，但组播通信是对大量接收方和发送方而言的，考虑到通信和计算开销问题，大多数机制使用Hash链分摊数字签名技术来减少这两种开销。

Gennaro和Rohatgi[7]在1997年首先提出原始Hash链方案，基本设计思想如图1所示。首先将要发送的数据分成m份。将最后发送的数据包Pm的Hash值H(Pm)附加到前一个数据包 H(Pm-1)上，形成 P/m-1；然后将 P/m-1的 Hash值H(P/m-1)附加到 Pm-2上形成P/m-2，依此类推，把新形成数据包的Hash值加到前一个数据包上形成新数据包，最后对 P/1求 Hash值，得到 H(P/1)，将 H(P/1)数字签名；最后，将Hash链发送出去，接收方检查数字签名的正确性，如果正确就保存其包含的Hash值以认证后面的数据包，如果不正确就丢掉它。

但原始Hash链协议在有丢包发生的网络中并不适用。因此，组播安全领域的专家又提出了EMSS[7]、H2A[8]等组播源认证协议，其中H2A组播认证协议是较优化的一种，其设计思想如图2所示。首先，发送方把要发送的数据分成m份，将 H(P/a+2)，…，H(P/m-a)值添加到其后 K个数据包上（K是发送方根据接收方周期性返回的接收状况反馈信息而确定的可动态调整的Hash链冗余度），其中，一个Hash值放在与原数据包邻近的下一个数据包上，另K－1个Hash值放在其后一定范围内任意K－1个数据包上；然后，把最后发送的数据包和加在其上的Hash值当作一个新数据包对其求Hash值，把求得的值按前面的方式附在其后K个数据包上，每处理完一个数据包就向接收方发送一个，对最后发送的数据包签名；最后，接收方保留收到的其他数据包，检验签名包的真实性，根据Hash链与签名包的关联关系认证其他数据包。

H2A方案虽然提高了抗丢包性，计算和通信开销适度，但仍有以下几个不足：

·H2A方案接收方在认证数据包时产生认证延迟，并且需要缓存空间来保存先到达的数据包直到接收到签名包才能进行认证，这样易遭受DoS攻击，浪费缓存资源；

·从接收方发送反馈信息的方式看，在大规模组播组中采用这种反馈方式可能浪费网络资源引起网络拥塞，并增加发送方计算负担，而且，敌对的攻击方可以假冒接收方发送大量虚假的反馈信息，影响K值选择；

·在目标包（某数据包承载其他数据包的Hash值，该数据包就是其他数据包的目标包）选取上，仍有进一步优化的可能，以提高抗丢包鲁棒性。

为了解决上述问题，下文结合原始Hash链和H2A协议的思想，设计了一种新的更为高效的组播源认证协议。

3 基于Hash链的高效组播源认证协议

3.1 协议描述

发送方将缓存的数据分成m个数据包，然后按照发送顺序将数据包从1～m编号，将最后发送的数据包Pm的Hash值H(Pm)附加到数据包Pm-1上形成新数据包P/m-1，另外，将K－1个H(Pm)随机地附加到前方任意K－1个数据包上（K是根据接收方反馈的网络状况计算出的冗余度），其中，必须有一个H(Pm)附加到前方与Pm相距至少a－1的数据包上（a－1是间隔数据包的个数，可根据网络丢包情况动态调节）。P/m-1的Hash值 H(P/m-1)即为 H(Pm-1+H(Pm))。依照上面的方法，把P/m-1的Hash值H(P/m-1)附到数据包P/m-2上，形成新的数据包P/m-2（前方被选定来附加Hash值的数据包和这个新附加的Hash值形成了一个新的数据包），另外将K－1个H(P/m-1)随机地附加到前方任意 K－1个数据包上，同样，其中必须有一个H(P/m-1)附加到前方与P/m-1相距至少a－1的数据包上。其他数据包的组成形式依此类推（如图3所示）。最后对第一个要发送的，也是最后形成的数据包P/1的Hash值H(P/1)数字签名。发送方按照签名包，P/1，P/2，…，P/m-1，P/m的顺序发送数据包。由于第一个数字签名包是认证过程的关键，应多发送几次签名数据包以避免其丢失。每隔多少个数据包产生一个签名包可根据接收方在应用层可容忍的最大延迟而定。

数据包到达接收方时，接收方将首先认证签名包的真实性，签名包通过认证后缓存签名包中的Hash值，当随后接收到其他数据包时接收方立即利用其先前保存的Hash值，通过Hash链认证其他数据包的真实性，如果认证成功保存其他数据包携带的Hash值，以便认证随后接收到的数据包。如果数据包在传输过程中有丢包，可利用协议设计中存在的冗余度特性对其他数据包进行认证。例如，数据包P/a的值放在其前面的P/a-1、P/a-10、P/a-12这3个数据包上，如果P/a-1、P/a-10丢失了，接收方还可以根据P/a-12中保留的Hash值对数据包P/a进行验证。K值的选取由发送方根据接收方反馈的网络丢包率计算得出。预先在接收方设定好变化阈值和采样周期，每个采样周期对网络状况进行一次采样，接收方计算网络丢包率变化值（网络丢包率指丢失的数据包占发送数据包的比率，网络丢包率变化值指当前采样得到的网络丢包率同前一次反馈的网络丢包率相减产生的绝对值），将这个网络丢包率变化值与预定的变化阈值相比较。如果网络丢包率变化值大于预定的变化阈值，向发送方反馈当前的网络丢包率信息；如果网络丢包率变化值小于变化阈值就不发送反馈任何信息；等待下一个采样周期继续采样比较，然后再决定是否发送反馈信息。接收方在发送反馈信息时需要将反馈信息用组密钥进行对称加密。发送方接收到反馈信息后，解密反馈信息并根据反馈信息决定如何调整冗余度K，同时K值还可以根据要发送的数据包的重要性进行适当增大或减小，以保证抗丢包鲁棒性或减小协议的通信开销。突发损失数据包长度，由接收方用对称密钥加密处理后，反馈给发送方。

3.2 性能分析

在协议中先发送签名数据包，由接收方认证。如通过认证保留其中包含的Hash值，这样通过保留的Hash值，可对随后接收到的数据包进行实时认证。在没有网络丢包的情况下K=1，接收方的认证缓存需求为1，认证延迟时间为0。因为前一个接收到的数据包已包含了下一个数据包的Hash值，可以通过该Hash值对下一个数据包进行实时认证，实时认证节约了接收方的缓存资源，避免了浪费缓存的恶意攻击。该设计思想的安全性已由参考文献[3]证明。如果网络中有丢包现象产生，则设K>1，由于接收方先得到后面数据包的Hash值，其同样可以较及时地认证接收到的数据。

该协议改变了接收方周期地发送反馈信息的方式，并对反馈信息进行加密传输。该协议在原来周期性返回反馈信息的基础上，增加了在接收方将网络丢包率变化值同预定变化阈值比较的过程。接收方根据预定好的采样周期，每隔一段时间对网络状况进行采样，计算网络丢包率变化值，将这个网络丢包率变化值与预定的变化阈值相比较。如果网络丢包率变化值大于预定的变化阈值就向发送方发送反馈信息；如果网络丢包率变化值小于变化阈值就不发送反馈信息，等待下一周期继续采样比较，再决定是否发送反馈信息。发送方根据接收到的反馈信息决定如何调整冗余度K。采用这种方法避免了在网络传输状况稳定条件下，接收方周期性返回反馈信息所造成的网络带宽和发送方计算资源的浪费。还可以根据具体情况做进一步改进，冗余度K是根据反馈的网络丢包率计算出来的数值，对于有些接收方也许K是合适的，另外一些也许稍大或稍小，因此对同一Hash链中的数据包，其中十分重要的数据包冗余度可以大于K，不重要的数据包冗余度可以适当小于K。这样在总计算开销和认证开销大体不变的前提下，提高了重要信息的抗丢包性。网络情况变化较大时，接收方的采样周期和变化阈值需要做相应的调整（采样周期变小，变化阈值增大。周期变小可以实时监测网络变化情况，变化阈值增大可以避免在网络情况持续变化较大时频繁地返回反馈信息而增加接收方计算负担和网络带宽）。另外，为了防止攻击方假冒接收方发送大量虚假反馈信息，影响发送方正确选择K值，该协议中采用了对称密钥加密反馈信息方法，即接收方用组密钥加密反馈信息。发送方接收到反馈信息后，解密反馈信息并根据反馈信息来决定如何调整冗余度K。

表1 各种基于Hash链的组播源认证协议性能比较

该协议在目标包选取上做了进一步优化，如图3所示。将Pm的Hash值H(Pm)附加到数据包Pm-a上形成新数据包P/m-a，将K－1个H(Pm)随机地附加到前方任意 K－1个数据包上（根据参考文献[4]在突发丢包模型中采用这种随机选取目标包的方法可以产生很高的认证率），其中必须有1个H(Pm)附加到前方与Pm相距至少a－1的数据包上。这种安排出于如下考虑：H(Pm)附加到数据包Pm-a上可以在网络无丢包情况下，直接对数据包实时认证（K=1），避免浪费缓存资源。根据参考文献[4]，将K－1个H(Pm)随机地附加到前方任意K－1个数据包上，在突发丢包模型中采用这种随机选取目标包的方法可以产生很高的认证率。将H(Pm)附加到前方与Pm相距至少a－1的数据包上，是由于如果网络中有突发丢包损失，突发丢包损失长度L小于a时，利用这个剩余的Hash值能够继续认证数据包。另外，协议中的a值必须根据网络丢包情况动态改变，如果丢包情况严重，a值必须增加，否则a值可以相应减小。网络中丢包损失突发特性像参考文献[8]中叙述的一样。突发丢包开始于流中的任意位置，并且一直持续到流中的任意一个数据包。为了抗丢包，突发损失包的长度L必须小于a。a应仔细选择，选小了可能导致L值大于a；选大了则会浪费较多的缓存资源。通过采用这种选择目标包的方式可以增加协议的抗丢包鲁棒性。

该方案同几种相关的基于Hash链的组播源认证协议各项性能比较结果见表1。

通过比较可以看出，该协议接收方在认证数据包时没有延迟（无丢包情况）时，抗丢包鲁棒性强，为了认证而附加在数据包上的Hash随网络变化状况而改变，较为灵活。接收方返回的网络状况信息通常少于H2A协议，在一定程度上减轻了网络负担和发送方的计算开销。

4 结束语

本文提出了一种基于Hash链的高效组播源认证协议，它借鉴了原始Hash链和H2A组播源认证协议的设计优点，从发送方发送签名数据包的先后顺序、接收方发送反馈信息的方式及目标数据包选取等三个方面进行设计，提高了接收方认证速度，减少了发送方计算开销和网络带宽损耗，增强了协议的抗丢包鲁棒性。通过比较分析证明该协议是高效的。

1 Xu Zhiming， Wang Yu， Zhu Jingguo.A reliable multicast routing protocolforhigh-speed mobile ad hoc networks：R-ODMRP.Journal of Software，2010，5(1)：20～27

2 Singh K， Yadav R， Shankar S.Adaptive multicast source authentication.In：2009 IEEE International Advance Computing Conference，IACC，Patiala India，March 2009

3 Obana S，Kurosawa K.Bounds and combinatorial structure of(k，n)multi-receiver a-codes.Designs，Codes and Cryptography.2001，22（1）：47～63

4 Perrig A，Canetti R，Tygar J D，et al.The TESLA broadcast authentication protocol.RSA CryptoBytes，2002（5）

5 Ruiying D， Song W.An improved scheme of μTESLA authentication based trusted computing platform.In： 2008 International Conference on Wireless Communications，Jhalwa India，December 2008

6 Yacine C，Abdelmadjid B，Yoann H.RLH：receiver driven layered Hash-chaining for multicast data origin authentication.Computer Communications，2005（28）：726～740

7 Perrig A，Canetti R，Tygar J D， et al.Efficient authentication and signingofmulticaststreamsoverlossychannels.In：ProceedingsoftheIEEE ComputerSocietySymposium on Research in Security and Privacy，Berkeley California USA，May 2000

8 Yacine C， Abdelmadjid B， Hatem B.H2A： hybrid hashchaining scheme for adaptive multicast source authentication of media-streaming.Computers&Security，2005（24）：57～68

9 Younis M，Farrag O.Tiered authentication of multicast traffic in wirelessad hoc networks.In： 2009 IEEE GlobalTelecommunications Conference，Hawaii USA，Nov 2009

10 Eltaief H，Youssef H.MLCC：a new hash-chained mechanism for multicast source authentication. International Journal of Communication Systems，2009，22（9）：1069～1087