抗代间污染攻击的网络编码同态签名方案

李世浩，梅中辉

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

抗代间污染攻击的网络编码同态签名方案

李世浩，梅中辉

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

由于网络编码极易遭受网络中攻击者对数据包的恶意修改，从而使信宿节点对正确数据包的解码造成影响，如果攻击者不断重发与正确数据无关的恶意信息又会造成网络资源的极大浪费，所以为防止该种污染攻击，提出了一种基于代标识符的网络编码同态签名方案。该方案在基于RSA的同态签名方案可防止污染攻击的基础上，通过对每代数据包引入代标识符，从而可进一步防止攻击者的重放攻击。由于方案不需额外安全信道并且采用线性运算，故可降低对节点计算能力的要求及方案安全开销。重点对方案的攻击模式进行了详细分析，并证明了其安全性。最后通过开销分析证明了该方案与基于RSA同态签名方案在开销近似相等的前提下还可有效解决代间污染攻击造成的消息串扰问题。

网络编码；污染攻击；同态签名；重放攻击

0 引 言

与传统的直接存储转发的路由方法相比，网络编码可让网络中的中继节点对数据包进行编码，这样可大幅提高网络吞吐量。另外网络编码还可提高网络的鲁棒性、安全性等[1-4]。然而网络编码在带来收益的同时也存在很多安全传输问题[5]。其中一类主要的安全问题就是易受到恶意节点的污染攻击，最后导致目的节点无法正确解码。针对污染攻击问题，Ho等利用简单多项式散列函数在接收(用户)节点处要验证消息的完整性[6]，但是中间节点却没有参与消息完整性的验证，这样会相对应地使得污染数据包在网络中大幅度扩散。Gkantsidis C等提出的同态哈希方案[7]改进了Ho方案的缺点，即使得中间节点可参与消息完整性验证，但是却需要另加一安全信道来传输源数据包的哈希值。Charles等在文献[7]的基础上设计出了一种同态签名的方案[8]，该方案不需要额外的安全信道，但由于复杂的韦伊配对操作会增加运算复杂度，故其应用受到了限制。Krohn等[9]首次提出同态哈希函数的方法，该方法可检测出被修改的编码分组，但却无法实现数据包的即时传输。之后Yu等提出了一种基于RSA的同态签名方案[10]，可大幅降低同态签名的运算复杂度。

上述网络安全方案均针对同一代内数据包抗污染攻击所提出。针对代间污染攻击问题并受到R方案[11]和文献[12-14]的启发，文中提出一种抗代间污染攻击的网络编码同态签名方案。该方案一方面可抵御代内污染攻击，另一方面在运算复杂度上与Yu方案相近的前提下，还可预防代间污染攻击。

1 理论性研究

1.1 随机线性网络编码

随机线性网络编码主要是在编码时将所有消息进行线性组合，所采用的系数均由给定有限域中随机选取；解码时采用高斯消元法求解线性方程组从而恢复出原始消息。文中的网络拓扑如图1所示，一个源节点s要将传输消息分为l代，每代消息有m条消息。在将这m条消息分发到t个目的节点d1,d2,…,dt时，源节点首先将每条原始消息Mi(i=1,2,…,m)设定为选自有限域Zq的长度为n的向量，那么原始消息Mi可表示为Mi=(vi1,vi2,…,vin),v∈Zq。

图1 网络拓扑

IM(α1,α2,…,αm)

图2 编码后的消息格式

(M1,M2,…,Mm)=PC-1

(1)

1.2 同态性质

同态性质分为乘法同态和加法同态。给定变量m1和m2，若对于函数H，存在函数F使式(2)成立，则称函数H满足加法同态。

H(m1+m2)=F(H(m1)+H(m2))

(2)

若对于函数H，存在函数F使式(3)成立，则称函数H满足乘法同态。

H(m1·m2)=F(H(m1)·H(m2))

(3)

正是利用同态性质，中间节点收到消息签名后在未知源节点私钥的前提下便可对发送的消息生成有效签名，之后会详细说明。

2 主要方案

该方案由选取参数阶段、对数据包生成签名、对收到消息进行组合、对签名进行检测四部分组成。

(1)源节点选取参数。参数选取过程简述如下：

①源节点生成用于签名的RSA的公钥(r,e)和私钥d。其中，r=uv,u和v都为素数，长度为512bit,r为1 024bit。令Φ=(u-1)(v-1)，公钥e满足gcd(e,Φ)=1,私钥d满足ed=1modΦ。因此对任意整数t∈Zr，有ted=tmodr。

②二次剩余群QRr为剩余群，其中g1,g2,…,gm+n-1为二次剩余循环群QRr的生成元。选取一个单向抗碰撞Hash函数H{0,1}*→Zq。

(2)签名：给定代I的一组扩展消息向量，将I带入H求得H(I),然后源节点利用私钥d对消息向量签名(如式(4))，然后将签名附于消息后。

(4)

(3)验证签名。中间节点收到消息组合后先进行验证，然后生成新签名。具体过程如下：

中间节点首先判断式(5)是否成立。

(5)

若该式成立，可认为该消息没有遭受污染攻击。原因是若消息未遭受污染攻击，则式(6)成立。

式(6)成立是因为对任意整数t∈Zr，有ted=tmodr。由上知式(5)成立，故消息未遭受污染攻击。

(7)

证明:

(8)

式(8)显示输出消息的有效签名可由输入消息签名与相关系数直接生成，无需源节点私钥。这样即便是被攻击者俘获的中间节点也不可能为污染消息生成有效签名。

3 方案分析

3.1 安全性分析

文中假设原节点总是安全的，而中间节点不可信。所以攻击者可通过控制中间节点进而对数据包进行破坏。设攻击者伪造的消息代数为I*,伪造的消息及签名为m*和σ*。下面证明其安全性。

(1)I*=Ii，即为代内攻击。此时，攻击者有两种攻击方式：在攻击方式一中攻击者可将收到的数据包伪造为m*，并意图为伪造数据包生成有效签名，但由于攻击者不知道源节点的私钥，所以无法对m*生成有效的签名，攻击方式一失效。在攻击方式二中攻击者意图通过截获的数据包的有效签名生成与之匹配的伪造数据。下面将证明其难度等于解决离散对数问题。

命题：已知有效消息E及有效签名σ(E)，找到一消息E'使得σ(E)=σ(E')但E≠E'的困难程度等同于解决离散对数问题。

(2)I*≠Ii，由于攻击者不可对伪造消息生成有效签名，故会将Ii代的消息及签名在其他代转发，从而对该代的消息解码造成污染。下面将说明其不可行。

若要通过中间节点的签名验证则要求满足式(5)，由于仅仅是将Ii代的消息及签名转发，故只需在转发时将代标识符修改为I*，使得H(I*)=H(Ii)成立，即可通过验证。但是在随机预言模式下，哈希函数H被看成一随机预言机，故攻击者没有能力在多项式时间内找到I*≠Ii，使得H(I*)=H(Ii)成立，故不可行。

由以上安全性分析可知，该方案可有效防止代内及代间污染攻击。

3.2 开销分析

将该方案与Yu的基于RSA的同态签名方案进行分析，Yu的方案称为方案1，文中方案称为方案2。

(1)参数初始化的比较。

方案1在参数选取阶段要产生m+n+1个模指数运算底数和一个公私钥对。由于公私钥对的生成过程就是模乘模加运算，其运算开销远小于模指数运算，所以只考虑模指数运算所造成的开销。参数选取阶段耗时近似正比于方案中gi个数，故两者的耗费时间比值为(m+n+1)/(m+n)，且随着m和n值的增大，该比值近似为1。

(2)签名计算。

两个方案中签名计算的消息均取值于有限域Zr，其随机系数αi均取自有限域Zq，由此知两者此处的模指数运算开销近似为1。

(3)签名验证。

中间节点的主要作用是对收到的签名进行验证，故对比方案的主要指标为算法对签名验证所需时间。与其他简单运算相比，两种方案运算中所采用的模指数运算无疑是算法效率的主要牵制因素，故主要考虑模指数运算。方案2中验证一条消息需m+n+2次模指数运算而方案1需m+n+1次，两者比值为(m+n+2)/(m+n+1)，同样随着m和n值增大，该比值近似为1。故由上述分析可知，方案2与方案1的效率基本一致，但是方案2在方案1的基础上还可有效防止代间污染攻击。

4 仿真结果

中继节点需对签名的有效性进行验证，所以网络传输效率的关键是中继节点的验证时效，进而中间节点的验证速度影响着整个网络的传输速率。下面将对两种算法的运行时间进行对比。将源节点产生的消息向量中的元素个数作为自变量，运行时间作为因变量，所得运行时间对比图如图3所示。

由图中分析知，随着源节点的消息向量元素个数m的上升，两方案的运行时间都呈线性增长趋势，最后曲线基本重合。这与3.2节的理论分析一致，即RSA方案和文中方案的算法耗时基本相同，但由于文中方案可抵抗代内和代间污染攻击，而RSA方案仅能抵抗代内污染攻击，故综合考虑算法复杂度与安全性能，文中方案相比RSA方案更佳。

图3 方案运行时间对比

5 结束语

文中提出一种具有同态性质的网络编码签名方案来抵御网络中的污染攻击。中间节点在未知源节点私钥的前提下便可对输入消息生成有效签名，而不需与源节点联系的额外安全信道。对污染攻击方式进行了详细分析并证明了其安全性。分析表明，该方案与Yu的方案的开销近似为1，除具有Yu方案的特性外还可有效解决代间污染攻击造成的消息串扰问题。

[1]AhlswedeR,CaiN,LiSYR,etal.Networkinformationflow[J].IEEETransactionsonInformationTheory,2000,46(4):1204-1216．

[2]LiSYR,YeungRW,CaiN.Linearnetworkcoding[J].IEEETransactionsonInformationTheory,2003,49(2):371-381.

[3] 黄佳庆,李宗鹏.网络编码原理[M].北京:国防工业出版社,2012:31.

[4]FragouliC,BoudecJ,WidmerJ.Networkcoding:aninstantprimer[J].ACMSIGCOMMComputerCommunicationReview,2006,36(1):63-68.

[5] 曹张华，唐元生.安全网络编码综述[J].计算机应用，2010,30(2):499-505.

[6]HoT,LeongB,KoetterR.Byzantinemodificationdetectioninmulticastnetworksusingrandomizednetworkcoding[C]//ProceedingsofIEEEinternationalsymposiumoninformationtheory.Massachusetts,USA:IEEE,2008:2798-2803.

[7]GkantsidisC,RodriguezP.Cooperativesecurityfornetworkcodingfiledistribution[C]//Proceedingsofinternationalconferenceoncomputercommunications.Barcelona,Spain:[s.n.],2006:367-380.

[8]MenezesA,OkamotoT,VanstoneS.Reducingellipticcurvelogorithmstologorithmsinafinitefield[J].IEEETransactionsonInformationTheory,1993,39(5):1639-1646.

[9]KrohnMN,FreedmanMJ,MazieresD.Onthe-flyverificationofratelesserasurecodesforefficientcontentdistribution[C]//ProcofIEEEsymposiumonsecurityandprivacty.[s.l.]:IEEE,2004:226-240.

[10]YuZ,WeiY,RamkumarB.Anefficientsignature-basedschemeforsecuringnetworkcodingagainstpollutionattacks[C]//Proceedingsofinternationalconferenceoncomputercommunications.Arizona,USA:[s.n.],2008:1409-1417.

[11]GennaroR,KatzJ,KrawczykH,etal.Securenetworkcodingovertheintegers[C]//Procofpublickeycryptography.[s.l.]:[s.n.],2010:142-160.

[12] 彭天丽,尚 涛,刘建伟.抗代间污染攻击的网络编码签名方案[J].北京航空航天大学学报,2015,41(4):721-726.

[13]LiuGuangjun,WangBin.Securenetworkcodingagainstintra/inter-generationpollutionattacks[J].ChinaCommunications,2013,10(8):100-110.

[14]ShwetaA,DanB.HomomorphicMACs:MAC-basedintegrityfornetworkcoding[C]//ProceedingofACNS.[s.l.]:[s.n.],2009:292-305.

Homomorphic Signature Scheme for Network Coding Against Inter-generation Pollution Attacks

LI Shi-hao，MEI Zhong-hui

(College of Telecommunication & Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Because network coding is vulnerable in the network attacker to malicious modification of packet,affecting the correct packet decoding for obtaining-information node.If an attacker continually resends malicious information without relation to correct data,it will lead to enormous waste of network resources.In order to prevent the pollution attack,a generation-identifier based homomorphic signature scheme for network coding is proposed.On the basis of preventing pollution attacks for the RSA-based homomorphic signature scheme,it can prevent the replay attack further by using generation-identifier into packets.This scheme does not need any extra secure channel and uses linear calculation,so it can reduce the requirements of computing ability of the node and the cost of the scheme.The attack mode of the scheme is analyzed in detail,and its security is proved.Finally,the cost analysis proves that on the premise of approximately equal cost between this scheme and the homomorphic signature scheme based on RSA,it also can effectively solve the crosstalk problems caused by inter-generation pollution attack.

network coding;pollution attack;homomorphic signature;replay attack

2015-12-25

2016-04-19

时间：2016-09-19

国家科技重大专项(2010zx03003-003)

李世浩(1990-)，男，硕士研究生，研究方向为网络编码技术、网络安全等；梅中辉，副教授，研究生导师，研究方向为网络编码技术、协助通信技术等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0841.022.html

TP301

A

1673-629X(2016)10-0073-04

10.3969/j.issn.1673-629X.2016.10.016