文章快速检索  
  高级检索
抗代间污染攻击的网络编码签名方案
彭天丽, 尚涛, 刘建伟    
北京航空航天大学 电子信息工程学院, 北京 100191
摘要:为适应实时应用的需求,网络编码中引入了代的概念.针对网络编码易受代间污染攻击导致消息发生串扰的问题,提出了基于代标识符的网络编码签名方案.首先,方案中设置了依据代标识符生成的两级私钥,包括代私钥以及在此基础扩展成的消息私钥,以便节点判断消息的代属性来决定是否对它继续进行编码;其次,利用双线性对构造了具有同态性质的签名算法,通过分离两级私钥进行批验证,节点可同时验证同一代的所有消息.最后,通过随机预言模型分析,证明了该方案在适应性选择消息攻击下是安全的.通过开销分析表明方案能有效减少验证开销,提高系统性能.
关键词网络编码     代间污染攻击     同态签名     批验证     双线性对    
Signature scheme for network coding against inter-generation pollution attacks
PENG Tianli , SHANG Tao , LIU Jianwei     
School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China
Abstract:The concept of generation is introduced into network coding so as to adapt to the needs of real-time application. Considering that network coding is vulnerable to inter-generation pollution attacks and causes message crosstalk, a generation-identifier based signature scheme for network coding was proposed. Firstly, the two-level private keys, including the generation private key and the message private key, both derived by the generation identifier were set. This procedure enabled nodes to judge the generation attribute of messages and decided whether to continue coding. Secondly, a signature algorithm was constructed with homomorphic property by using the bilinear pairing. Meanwhile the two-level private keys were separated to verify signatures by batch, which made nodes verify all the massages of the same generation simultaneously. Finally, through the analysis of random oracle model, the scheme was proved secure against adaptively chosen message attack. The result indicates that the scheme can reduce computation cost and improve performance of the system.
Key words: network coding     inter-generation pollution attacks     homomorphic signature     batch verification     bilinear pairing    

网络编码[1]可使组播网络中的信息传输达到最大流最小割这一理论上界,也可提高网络鲁棒性和安全性,所以在实际网络中得到了广泛的应用.但是网络编码在带来收益的同时存在许多的安全传输问题[2].其中一类主要安全问题就是网络编码容易受到恶意节点的污染攻击[3],导致目的节点无法正确解码.对于网络中的攻击者篡改网络中传输的数据或向网络中输入随机数据来干扰网络通信的污染攻击,Yu等[4]提出了基于RSA的同态签名方案,裴恒利等[5]在基于RSA同态签名方案的基础上设计了一种融合时间戳和同态签名的网络编码签名方案,它可同时抵御污染攻击与重放攻击,随后Shang等[6]在格上通过计算消息与其签名的距离提出了一种基于距离的安全网络编码算法,它的安全性可规约为格上固定长度向量问题(FLVP),同时格的特性使得它比基于RSA的签名方案更加安全.Chou等[7]提出了应用于实际无线网络中的分代网络编码方法,它能更好地满足信息实时传输的需求,然而这样的分代网络编码不仅面临代内污染攻击问题也存在着代间污染攻击问题.上述已有方案可以有效地解决代内污染攻击的问题,然而对于不同消息子空间的消息发生串扰引起的代间污染攻击问题并未加以讨论.针对这个问题,Zhao等[8]与Kehdi等[9]提出了验证每个消息向量是否属于源消息向量张成的线性子空间的方法,方法主要思想是通过生成源消息张成线性子空间的零空间,由于零空间的任意向量与传输的消息向量正交,因而给中间节点分发零空间的消息向量即可验证消息的完整性.然而,此方法一方面需预先知道整个文件信息,一方面公钥信息需频繁更新.接着Boneh等[10]提出了一种利用双线性对构造的只需常数级规模公钥的网络编码签名方案,它通过对线性子空间进行签名,可抵御代内和代间污染并在随机预言模型中被证明可满足CDH假设.

针对代间污染攻击问题并思及Boneh方案在验证过程中需对每个接收的消息执行双线性对操作带来了很大的网络开销,本文受到Tseng等[11]的启发,将批验证[12]与网络编码相结合,提出了一种结合批验证的抗代间污染攻击的同态网络编码签名方案.该方案一方面能够抵御代间污染攻击,另一方面与Boneh等的方案相比提高了节点验证效率,减少了系统开销.

1 相关研究 1.1 随机线性网络编码

随机线性网络编码的基本思想是,编码时将所有消息进行线性组合,所采用的系数均为随机选取;解码时,采用高斯消元法求解线性方程组从而恢复出原始消息[13].

随机线性网络编码的具体步骤如下:

1) 网络模型如图 1,一个源节点S将要传输的消息分为l代,每代拥有m条消息,将这m条消息发送到t个目的节点d1,d2,…,dt时,源节点首先将每条原始消息Mi(i=1,2,…,m)设定为选自有限域Zq的长度为n的向量,则原始消息Mi可表示为Mi=(vi1,vi2,…,vin),vijZq.

图 1 网络模型图Fig. 1 Network model

然后将每条原始消息向量用长度为m的单位向量进行扩展生成扩展向量[14]Mi':

m个扩展向量进行随机网络编码,编码后向量为,N=m+n,其中ai是从有限域中随机选取的.将代标识符I随着消息一起传输,则编码后消息格式如图 2所示.
图 2 编码后的消息格式Fig. 2 Message format after network coding

2) 中继节点收到k个消息向量w1,w2,…,wk,将它们进行线性组合,得新的编码向量W=.

3) 目的节点收到m个线性无关的消息向量后,可得到一个mm+n列的矩阵,将其前m列构成的矩阵记为C,后n列构成的矩阵记为P,则可由式(1)恢复得到原消息.

1.2 网络编码代间污染攻击

代标识符的主要作用就是区分不同的编码向量所张成的消息子空间,如果不同消息子空间的消息发生了串扰就产生了代间污染.造成代间污染有两种攻击方式[15],具体代间污染攻击模型如图 3所示.在模型中,n1n2是普通节点,n3n4是恶意节点,n5是污染节点.

图 3 代间污染攻击模型Fig. 3 Model of inter-generation pollution attack

一种攻击方式是对消息的攻击.节点n1输出代I1的消息,节点n2输出代I2的消息.当恶意节点n3收到来自代I1的消息m1和代I2的消息m2时,将其编码得到消息组合m′=m1+m2,通过同态签名,可得到消息m′的合法签名σ′=σ12.但是由于新产生的消息组合m′既不属于代I1也不属于代I2,所以该消息属于污染消息,当其参与目的节点解码时将导致解码错误.

另一种攻击方式是对代标识符的攻击.恶意节点n4转发代I2消息m2到节点n5的过程中,随意伪造或篡改I信息,消息将指向错误的消息子空间,则节点n5也会受到污染.

上述两种攻击方式均会导致线性子空间的消息发生串扰,使目的节点无法正确解码.

1.3 双线性对

相对于有限域乘法群上的离散对数问题,椭圆曲线加法群上离散对数问题的求解更难,它可用更小的密钥保证更高级别的安全性.所以在Boneh等[16]借助椭圆曲线上的双线性对给出了基于身份的加密体制后,双线性对被用来构造各种密码协议.

G1是阶为大素数q的加法循环群,生成元为P.令G2是阶为q的乘法循环群.假设G1,G2上的离散对数问题都是困难的.若映射e:G1×G1→G2满足如下性质则为双线性对.

1) 双线性性:对于任意的P,Q∈G1,a,bZq*,都有e(aP,bQ)=e(P,Q)ab.

2) 非退化性:存在P,Q∈G1使得e(P,Q)≠1.

3) 可计算性:对于任意的P,Q∈G1,存在多项式时间算法能够计算e(P,Q).

对双线性映射e的性质1)进行推导可得如式(2)的等式:

2 签名方案 2.1 定 义

网络编码同态签名方案由下列四元组概率多项式时间算法构成.

1) 系统参数建立(Setup).输入安全参数1τ,输出素数q、源节点公钥以及私钥.

2) 签名(Sign).输入私钥,一个随机选取的代标识符I∈{0,1}*,一个消息向量w,输出消息的签名σ.

3) 消息组合(Combine).输入一个代标识符,k个消息向量Zi,k个随机编码系数aiZq,输出消息组合W及其签名σ.

4) 批验证(Batch Verify).输入一组待验证的消息向量wi,公钥和当前传输的代标识符I∈{0,1}*,经验证算法输出有效或者无效.

2.2 具体构造

对于四元组算法的具体构造如下.

1) 系统参数建立(Setup):给定系统参数1τ,系统选取参数G1,G2,P,q,e,HG,其中HG是一个单向抗碰撞hash函数HG:{0,1}*G1.然后系统选取随机数αZq*riZq*(i=1,2,…,N)作为系统私钥.计算Di=αri·P(i=1,2,…,N)作为系统公钥.假设源节点要发送l个代的消息,那么给每个代随机选取一个代标识符I,计算Gpk=HG(I).源节点公开公共参数{G1,G2,e,q,P,{Di}Ni=1,Gpk,HG}.

2) 签名(Sign):给定代I的一组扩展后的消息向量M′=(M1,M2,…,Mm),其中Mi=(v1,v2,…,vN).计算Gsk=α·Gpk.

计算签名为

式中,Gsk可看成代对应的私钥,Gsk·ri可看成消息对应的私钥.所以同一代的消息对应着相同的代私钥和消息私钥.

3) 消息组合(Combine):当接收到k个属于代I的消息向量后,节点对其进行随机线性网络编码操作得到新的消息向量为,并利用签名的同态性质,由k条消息组合中的签名直接生成新消息对应的签名sign(W).

性质1 方案具有同态性质.

证明wi=(vi1,vi2,…,viN)(i=1,2,…,k)是长度为N的向量,则由式(4) 可得:

那么中间节点收到k个消息向量后,进行随机线性网络编码得到向量.对其进行签名计算有

因此证明了方案具有同态性质.从而得到新消息向量的签名计算式为

4) 批验证(Batch Verify):在对代I的消息进行批验证时,借鉴文献[7]中对分代网络编码的缓冲模式,假设节点对一个代消息的缓冲时间为t,则节点在缓冲时间结束前对所有代标识符为I的消息进行验证.设节点在代I缓冲时间结束前收到了k个代I的数据包,其形式分别为(I,w1,σ1),(I,w2,σ2),…,(I,wkk),其中,wi=(v′1,v′2,…,v′N).那么首先计算HG(I),验证HG(I)=Gpk是否成立,然后验证式(7)是否成立:

若式(7)成立则所有消息都属于代I的消息,不存在代间污染攻击.否则再对每一个消息向量进行单独验证确定哪一个是污染消息向量,验证方式与式(7)类似:

3 方案分析 3.1 正确性分析

对方案中的两个验证公式进行正确性的分析.

1) 节点验证单个签名的情况.

2) 节点批验证的情况.

由以上两个推导过程可证明方案的正确性.

3.2 安全性分析

1) 安全定义.

定义1 在随机预言模型下,如果一个概率多项式时间的攻击者在以下的安全游戏中的优势是可忽略的,则网络编码同态签名方案是安全的.

① 初始化:挑战者运行Setup算法生成公开参数和系统私钥,并把系统公开参数发送给攻击者,保存私钥.

② 询问:攻击者指定一系列的消息子空间ViZqN.对于每一个i,挑战者从{0,1}*任意选择一个代标识符Ii与之对应,通过签名算法Sign生成代Ii中每个消息向量的签名σi,并将签名σi和代标识符Ii发送给攻击者.

③ 伪造:攻击者输出I*∈{0,1}*,非零消息向量m*(m*不属于代Ii),以及签名σ*.若I*=Ii,或者I*≠Ii时验证Verify(I*,m**)合法,则说攻击者赢得了本次游戏.

2) 安全性证明.

① 在I*=Iim*不属于代Ii的消息的情况下证明方式与文献[15]类似.

在询问阶段,攻击者选择由向量(M1,M2,…,Mm)张成的消息子空间V并向挑战者询问该消息子空间中各消息向量的签名.挑战者收到询问请求后通过随机预言机进行应答.挑战者首先选取I作为V的代标识符,然后通过签名算法生成各向量Mi的签名σi,并将签名σi和代标识符I发送给攻击者.由此攻击者可获得式(11)的方程组:

式中

攻击者输出伪造消息向量(I,m**),m*V.如果此伪造消息量能够通过验证,那么以下方程组成立:

假设式(11)的系数矩阵与增广矩阵的秩为λ,则其解的个数为qn-λ,式(12)的秩为λ+1,解为qn-λ-1,同时也可知式(11)中将有q个解满足式(12).当q足够大时,攻击者赢得游戏的概率1q可忽略不计.

I*≠Ii时,在随机预言模型下,哈希函数HG被看成是一个随机预言机,而攻击者没有能力在多项式时间内找到I*≠Ii使得HG(I*)=HG(Ii),所以Gpk*≠Gpk,验证时不能通过.

3.3 开销分析

将本方案与Boneh方案的验证开销进行比较分析.两个方案开销的比较分析分为对验证计算开销的比较以及验证时对数据包等待时间的比较.

1) 验证计算开销的比较.

在比较验证计算开销时,不考虑数据包等待带来的开销.

Boneh方案中,其签名形式为

验证形式为

式中,α为系统私钥;u=hα为系统公钥.

本方案和Boneh方案中均采用了双线性对来构造网络编码签名方案.由于在两个方案验证过程中的模加、模乘以及哈希操作的开销远小于双线性对操作的开销,所以以下的验证计算开销分析中只考虑双线性对操作的开销比较.

对两个方案的验证计算开销进行比较之前先假设中间节点收到同代的消息条数平均为λ.令Ce为执行双线性对操作所需时间.

① 不存在代间污染攻击的情况下,Boneh方案对每条消息进行验证时需进行两次双线性对操作,其所需时间为(2×λ)Ce.由于不存在代间污染攻击,所以本方案下只需要进行一次批验证即可,由验证式(7)可知本方案进行批验证只需两次双线性对操作,所需时间为2×Ce.

② 当存在代间污染攻击的情况下,Boneh方案所需时间与不存在代间污染攻击下所需时间一样为(2×λ)Ce.使用本方案先进行批验证,确定存在代间污染攻击后,还需对每条消息进行逐一验证确定哪一个是污染消息,所以需要时间为批验证时间加上所有单个验证的时间,其总耗时为(2×λ+2)Ce.此种情况下两方案所需时间之比为

综合两种情况考虑,假设节点受到污染攻击的概率为p.则采用本方案验证所需的平均时间为p(2λ+2)Ce+(1-p)2Ce=2Ce(pλ+1),此时两方案验证时间之比为.当λ≥2,即至少有两条同代的消息到达验证节点,且节点受到代间污染攻击概率p<1/2时,ξ始终大于1,即本方案的验证开销更小.

由以上分析可知,本方案和Boneh方案相比,节点在有多条同代消息到达且发生代间污染概率p<1/2情况下的计算开销更小.

2) 数据包等待时间比较.

在比较数据包等待时间带来的开销时,不考虑验证计算开销.图 4图 5分别为单验证模型和批验证模型.单验证时,节点收到数据包立刻开始验证,数据包不需要等待;批验证时,数据包等待直到缓冲时间结束前,节点进行批验证.由图 4图 5可见,在相同的时间内,因为数据包到达速率一样,所以二者缓冲数据包数量相同,数据包等待时间不影响批验证开销.

图 4 单验证模型Fig. 4 Individual verification model
图 5 批验证模型Fig. 5 Batch verification model

综上考虑,结合批验证的方案与普通的单验证方案相比能够有效地节省验证开销,提高系统效率.

4 结 论

1) 提出一种具有同态性质的网络编码签名方案,解决网络编码中存在的因代间污染攻击造成的消息串扰问题.

2) 在节点有多条同代消息到达且发生代间污染攻击概率p<1/2情况下,本方案与Boneh方案相比,验证效率更高.

参考文献
[1] Ahlswede R, Cai N,Li S.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.
Click to display the text
[2] He M,Chen L, Wang H,et al.Survey on secure transmission of network coding in wireless networks[C]//International Conference on Computer Science and Service System.Washington,D.C.:IEEE,2012:1216-1219.
Click to display the text
[3] 曹张华,唐元生. 安全网络编码综述[J].计算机应用,2010,30(2):499-505. Cao Z H,Tang Y S.Survey on secure network coding[J].Journal of Computer Applications,2010,30(2):499-505(in Chinese).
Cited By in Cnki (13) | Click to display the text
[4] Yu Z,Wei Y, Ramkumar B,et al.An efficient signature-based scheme for securing network coding against pollution attacks[C]//Proceedings of International Conference on Computer Communications(INFOCOM).Washington,D.C.:IEEE,2008:1409- 1417.
Click to display the text
[5] 裴恒利,尚涛, 刘建伟.融合时间戳和同态签名的安全网络编码方法[J].通信学报,2013,34(4):28-35. Pei H L,Shang T,Liu J W.Secure network coding method merged with timestamp and homomorphic signature[J].Journal on Communication,2013,34(4):28-35(in Chinese).
Cited By in Cnki (3) | Click to display the text
[6] Shang T, Pei H L,Liu J W.Secure network coding based on lattice signature[J].China Communication,2014(1):138-151.
Click to display the text
[7] Chou P A, Wu Y,Jain K.Practical network coding[C]//Proceedings of the Annual Allerton Conference on Communication Control and Computing,2003.
Click to display the text
[8] Zhao F, Kaller T,Medard M,et al.Signatures for content distribution with network coding[C]//IEEE International Symposium on Information Theory.Washington,D.C.:IEEE,2007:556-560.
Click to display the text
[9] Kehdi E, Li B.Null keys:limiting malicious attacks via null space properties of network coding[C]//Proceedings of International Conference on Computer Communication(INFOCOM).Washington,D.C.:IEEE,2009:1224-1232.
Click to display the text
[10] Boneh D, Freeman D,Katz J,et al.Signing a linear subspace:signature schemes for network coding[C]//12th International Conference on Practice and Theory in Public Key Cryptography.Berlin:Springer,2009:68-87.
Click to display the text
[11] Tseng Y M, Wu T Y,Wu J D.Towards efficient ID-based signature schemes with batch verifications from bilinear pairing[C]//International Conference on Availability,Reliability and Security.Washington,D.C.:IEEE,2009:935-940.
Click to display the text
[12] Camenisch J, Hohenberger S,Pedersent M Q.Batch verification of short signatures[C]//Advances in Cryptology-Eurocrypt 2007.Berlin:Springer,2007:246-263.
Click to display the text
[13] 黄佳庆,李宗鹏. 网络编码原理[M].北京:国防工业出版社,2012:31. Hang J Q,Li Z P.Network coding principles[M].Beijing:National Defense Industry Press,2012:31(in Chinese).
[14] Lee S H, Gerla M,Krawczyk H,et al.Performance evaluation of secure network coding using homomorphic signature[C]//International Symposium on Network Coding(NetCod).Piscataway,NJ:IEEE,2011:1-6.
Click to display the text
[15] Liu G J, Wang B.Secure network coding against intra/inter-generation pollution attacks[J].Communications,China,2013,10(8):100-110.
Click to display the text
[16] Boneh D, Franklin M.Identity-based encryption from the Weil pairing[C]//Advances in Cryptology-CRYPTO 2001.Berlin:Springer,2001:213-229.
Click to display the text
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0478
北京航空航天大学主办。
0

文章信息

彭天丽, 尚涛, 刘建伟
PENG Tianli, SHANG Tao, LIU Jianwei
抗代间污染攻击的网络编码签名方案
Signature scheme for network coding against inter-generation pollution attacks
北京航空航天大学学报, 2015, 41(4): 721-726
Journal of Beijing University of Aeronautics and Astronsutics, 2015, 41(4): 721-726.
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0478

文章历史

收稿日期:2014-07-30
录用日期: 2014-10-11
网络出版日期: 2014-12-22

相关文章

工作空间