牛淑芬,王彩芬,張玉磊,曹素珍

(西北師范大學計算機科學與工程學院,蘭州730070)

多源網絡編碼數(shù)據(jù)完整性驗證方案

牛淑芬,王彩芬,張玉磊,曹素珍

(西北師范大學計算機科學與工程學院,蘭州730070)

基于同態(tài)向量哈希函數(shù)和向量合并算法,提出一種能夠抵御污染攻擊的多源網絡編碼數(shù)據(jù)完整性驗證方案。通過信源節(jié)點計算發(fā)送向量的哈希值,利用私鑰對該哈希值進行簽名,并將消息向量、哈希值以及哈希值的簽名發(fā)送至中間節(jié)點。中間節(jié)點和信宿節(jié)點基于系統(tǒng)公鑰,驗證來自不同信源節(jié)點的線性編碼消息的完整性。實驗結果表明,當信源節(jié)點數(shù)大于200時,該方案的計算效率優(yōu)于現(xiàn)有多源網絡編碼方案,更適用于大規(guī)模分布式網絡數(shù)據(jù)的安全驗證。

多源網絡編碼;數(shù)據(jù)完整性;聚合簽名;同態(tài)哈希函數(shù);向量合并算法;離散對數(shù)問題

1 概述

Ahlswede和Cai等人［1］于2000年提出網絡編碼理論,網絡編碼允許網絡中間節(jié)點在傳統(tǒng)數(shù)據(jù)轉發(fā)的基礎上參與數(shù)據(jù)處理,已成為提高網絡吞吐量、魯棒性和安全性的有效方法,但網絡編碼易遭受系統(tǒng)污染攻擊,一旦網絡中的某個信息被某蓄意節(jié)點惡意篡改,或在傳輸過程中由于外界原因發(fā)生變異,該污染信息將在整個網絡中迅速繁殖,使目的節(jié)點無法恢復源信息,導致網絡傳輸失敗。在密碼學中,通常用基于同態(tài)哈希函數(shù)的簽名［2］和同態(tài)數(shù)字簽名技術［3］解決線性網絡編碼中的污染問題。利用簽名函數(shù)或者同態(tài)哈希函數(shù)的同態(tài)性,中間(信宿)節(jié)點用公鑰驗證數(shù)據(jù)的真實性。文獻［4］系統(tǒng)地討論了線性網絡編碼的安全問題,提出一個層次式抵御污染攻擊的安全協(xié)議,該協(xié)議能夠實現(xiàn)污染節(jié)點的具體定位。

然而,現(xiàn)有算法大多是針對單源網絡編碼設計,而在多源網絡編碼中,該問題就會變得復雜,主要原因在于:現(xiàn)有單源網絡編碼簽名算法只需一個私鑰對消息進行簽名,而在多源網絡編碼中,這個唯一的私鑰顯然不能被多用戶共享,且用不同的私鑰簽名

會破壞現(xiàn)有某些算法中的簽名同態(tài)性。針對多源網絡編碼,學者們提出了一系列簽名算法。文獻［5］利用簽名函數(shù)同態(tài)性提出一個安全的簽名算法,該方案每個源節(jié)點用自己的私鑰簽名,中間節(jié)點用每個源節(jié)點的公鑰驗證,該方案的缺點是每個信源節(jié)點要計算一組簽名,計算量相對大。文獻［6］提出一個安全高效的多源網絡編碼簽名算法來預防網絡中的污染攻擊,并討論了算法的安全性。文獻［7］提出一個有效抵抗污染攻擊的多源網絡編碼簽名算法,但不足之處在于僅能供信宿節(jié)點進行驗證。文獻［8］給出一個針對多源網絡編碼的數(shù)字簽名,對于來自不同信源節(jié)點(不同子空間)的向量,提出向量合并算法,設計一個多源網絡編碼的簽名體制,并給出算法安全模型定義。文獻［9］為多源網絡編碼構建一個無條件安全的認證碼技術,保證消息的完整性。文獻［10］提出一個在標準模型下可證明安全的簽名算法。從以上文獻可以看出,雖然學者們對多源網絡編碼的簽名算法做了很多研究,但都存在較多的局限性。

本文基于文獻［8］提出的向量合并算法,利用文獻［11］的同態(tài)哈希函數(shù)構建一個數(shù)據(jù)完整性驗證方案。每個信源節(jié)點首先計算消息的向量哈希值,然后用BGL聚合簽名算法［12］對哈希值進行簽名。中間(信宿)無需知道信源節(jié)點的私鑰即可驗證收到消息的完整性。該方案的安全性取決于向量哈希函數(shù)和BGL聚合簽名的安全性。

2 相關知識

2.1 雙線性映射

設q是一個大素數(shù),G1,G2是2個有著相同素數(shù)階q的乘法循環(huán)群,g是G1的生成元。假設在群G1,G2中的離散對數(shù)問題是難解的。一個雙線性映射e:G1×G1→G2在G1上滿足下列性質:

(1)雙線性:對任意的a,b∈Zq、g,h∈G1,存在e(ga,hb)=e(g,h)ab。

(2)非退化性:存在a,b∈Zq,使得e(ga,gb)≠1。(3)可計算性:對所有的g,h∈G1,存在有效算法計算e(g,h)。

2.2 困難問題假設

定義2(Diffie-Hellman(DH)問題) 設G1是階為q的循環(huán)群,g是G1的生成元,已知g,gα,h∈G1,計算hα。

2.3 同態(tài)向量哈希函數(shù)

定義3(向量哈希函數(shù)) 設G是一個階為p的循環(huán)群,隨機選擇公共參數(shù)g1,g2,…,gd∈G,則向量v=(v1,v2,…,vd)∈Zp的哈希函數(shù)為:

容易證明,向量哈希函數(shù)滿足以下性質:

(1)同態(tài)性:對任意2個向量m1,m2和2個實數(shù)w1,w2,滿足H(w1m1+w2m2)=H(m1)w1H(m2)w2。

(2)免碰撞性:不存在一個多項式時間的攻擊者偽造一個向量m3,同時滿足m3≠w1m1+w2m2且H(m3)=H(m1)w1H(m2)w2。

定理1 同態(tài)向量哈希函數(shù)在離散對數(shù)問題是困難問題假設下是安全的［11］。

2.4 多源線性網絡編碼

隨機線性網絡編碼的隨機性體現(xiàn)在網絡編碼的局部編碼系數(shù)是有限域內的隨機數(shù),線性表示網絡編碼節(jié)點的輸入和輸出之間的關系是線性的［13］。多源網絡用一個無環(huán)有向圖G=(V,E)來表示,其中,E為網絡中鏈路的集合;V為網絡中所有節(jié)點的集合［14］。網絡中有l(wèi)個信源節(jié)點S=(s1,s2,…,sl)?V向網絡中另一個節(jié)點集合T?V中的所有信宿節(jié)點傳輸消息,其中,每個源節(jié)點都獨立地傳輸消息,且不知道任何其他節(jié)點的傳輸行為［15］。信源節(jié)點在傳輸前對它要發(fā)送的信息進行分塊處理,把要發(fā)送的文件分成m個分塊,每個分塊用一個n(n≥m)維的行向量來表示,行向量的元素為有限域內的數(shù)據(jù),文件可以表示為向量v=(v1,v2,…,vn)。每個信源節(jié)點在發(fā)送消息前,先對消息進行如下預處理:

3 多源網絡編碼的數(shù)據(jù)完整性驗證

本文方案能夠組合來自不同信源節(jié)點的向量,同時也能夠利用公鑰對來自不同私鑰簽名的消息進行驗證,所以,在基于同態(tài)向量哈希函數(shù)的基礎上,本文方案利用聚合簽名和向量合并算法［8］。

計算出βij=yn+(i-1)m+j,即可以計算出組合的編碼系數(shù)。

在本文驗證方案中有三方:信源節(jié)點,中間節(jié)點和信宿節(jié)點。完整性驗證技術由5個算法組成: Setup,KeyGen,Sign,Combine,Verifying。記NS= (Setup,KeyGen,Sign,Combine,Verifying),算法具體描述如下:

(1)Setup:給定安全參數(shù)1k:

1)產生一個四元對(G1,G2,GT,e),其中,G1,G2,GT是階為素數(shù)p的3個循環(huán)群,e:G1×G2→GT為一個有效的雙線性映射。隨機產生gi←G1{1} (i=1,2,…,n)和g←G2{1}。

2)H1:{0,1}?→G1是一個哈希函數(shù)。

(2)KeyGen:源節(jié)點Si隨機選擇xi∈Zp,計算pi=gxi。源節(jié)點的公私鑰對為(pi,xi)。

(5)Verify:給定消息向量,向量的哈希值hi以及向量的簽名σi,y∈Fp:

2)如果以下2式均成立:

則輸出0(接受),否則輸出1(拒絕)。

正確性證明:

(1)驗證消息哈希值:

(2)驗證數(shù)據(jù)完整性:

4 安全性分析

在本文算法中,無需一個安全通道來發(fā)送每個向量的哈希值,哈希值的正確性通過聚合簽名算法驗證,而數(shù)據(jù)完整性通過向量哈希函數(shù)性質來驗證。

定理2數(shù)據(jù)完整性驗證算法NS是安全的,假設哈希函數(shù)VH和聚合簽名算法BGL是安全的。特別地,假設存在一個多項式時間的攻擊者A攻破NS算法,則存在一個多項式時間攻擊者B對BGL算法偽造一個簽名以及存在一個多項式時間攻擊者C能攻破向量哈希算法VH,使得:

其中,NS_Adv［A,NS］是攻擊者A攻破算法NS的概率。

4.1 簽名偽造

數(shù)據(jù)完整性是通過同態(tài)哈希函數(shù)驗證的,中間

4.2 哈希碰撞

攻擊者對給定的哈希值偽造一個消息使其通過驗證,即攻擊者選定一個消息,攻擊想偽造一個哈希值h()使得對已知消息w≠及其哈希值h(w),有h(w)=h()。由定理1可知,對任何一個攻擊者來說,偽造一個消息向量使其通過驗證相當于求解離散對數(shù)問題。

由以上分析可知,在本文方案中,在計算性Diffie-Hellman困難問題假設下,攻擊者不可能偽造消息向量的哈希值;在離散對數(shù)困難問題假設下,攻擊者不可能偽造一個向量使其通過驗證。

5 實驗結果與分析

從理論上分析本文方案在驗證階段計算開銷方面的優(yōu)勢,給出具體數(shù)值結果。在所有表及圖中:d表示信源節(jié)點的個數(shù);n表示消息向量的唯數(shù);c表示中間節(jié)點編碼的消息向量的個數(shù)。

5.1 計算開銷

本節(jié)比較本文方案與文獻［3,7］方案在計算開銷方面的執(zhí)行效率,Cme表示執(zhí)行一次指數(shù)運算花費的時間,Cpar表示執(zhí)行一次對運算花費的時間,Cmul表示執(zhí)行一次乘法運算花費的時間,MSP表示算法支持多源網絡編碼。為簡單起見忽略所有計算負擔輕的加法運算。假設驗證者收到c個來自不同源節(jié)點的消息向量,按照多源線性網絡編碼理論:n≥d,n≥candd≥c。

表1表明本文方案需要執(zhí)行對運算時間與文獻［7］方案相同,但執(zhí)行乘法和指數(shù)運算的時間優(yōu)于文獻［7］方案。

表1 驗證階段的計算開銷

5.2 實驗結果

表2 對參數(shù)的主要性質

5.2.1 運行效率

本文分別運行了在不同對參數(shù)下信源節(jié)點簽名與中間或者信宿節(jié)點驗證的時間。對每一個信源節(jié)點來說,簽名時間主要決定于消息向量的大小。在這種情況下,可信源節(jié)點個數(shù)為d=50,消息向量維數(shù)分別為n=10,50,150,200,在2種對參數(shù)Type a和Type e下分別運行信源節(jié)點簽名與中間或者信宿節(jié)點驗證的時間。對每一個驗證節(jié)點(中間節(jié)點或者信宿節(jié)點)來說,驗證的計算效率主要取決于文件的個數(shù)和消息向量的大小。因此,本文假設消息向量的長度為3 200 Byte,同時消息向量的個數(shù)分別設為10,50,100,200,300。

算法簽名階段和驗證階段的運行時間分別如圖1、圖2所示,可以看出,對固定的對參數(shù),算法運行時間隨著消息向量大小的增加而增加。在對參數(shù)Type a下,當信源節(jié)點的個數(shù)為200時,算法運行時間為1 500 ms。

圖1 驗證時間比較

圖2 簽名時間比較

5.2.2 分析比較

從數(shù)據(jù)實驗角度比較本文方案與文獻［7］方案在驗證階段的計算效率。本文選擇對參數(shù)類型為Type a,向量維數(shù)為50。由表3可以看出,當信源節(jié)點個數(shù)d＞200時,本文方案運行時間優(yōu)于文獻［7］方案。

表3 算法運行時間比較s

6 結束語

本文提出一個多源網絡編碼數(shù)據(jù)完整性驗證方案,利用向量合并算法計算來自不同信源節(jié)點的向量的線性組合,其作用是能夠計算出線性編碼系數(shù)。方案的數(shù)據(jù)完整性由同態(tài)向量哈希函數(shù)驗證,哈希函數(shù)的正確性通過聚合簽名算法進行驗證。通過理論分析和數(shù)據(jù)測試結果表明,本文方案是可行有效的,具有良好的擴展性。隨著全同態(tài)密碼算法研究的深入,今后將設計基于全同態(tài)密碼函數(shù)的多源網絡編碼簽名算法,進一步提高算法的安全性及數(shù)據(jù)完整性驗證的效率。

［1]Ahlswede R,CaiN,LiSYR,etal.Network Information Flow［J］.IEEE Transactions on Information Theory,2000,46(4):1204-1216.

［2]Gkantsidis C,Rodriguez P.Cooperative Security for Network Coding File Distribution［C］//Proceedings of the 25th IEEE International Conference on Computer Communications.Washington D.C.,USA:IEEE Press, 2006:1-13.

［3]Boneh D,Freeman D,Katz J,et al.Signing a Linear Subspace:Signature Schemes for Network Coding［C］// Proceedingsof2009ConferenceonPublicKey Cryptography.Berlin,Germany:Springer,2009:68-87.

［4]Adeli M,Liu H.On the Inherent Security of Linear Network Coding［J］.Communications Letters,2013, 17(8):1668-1671.

［5]羅 蛟.安全多源網絡編碼環(huán)簽名方案［EB/OL］.(2012-04-12).http://www.paper.edu.cn.

［6]彭 勇,陳愈強,嚴文杰.一種安全的多源網絡編碼簽名算法［J］.計算機工程與應用,2012,48(30): 135-139.

［7]Vajda I.SignaturesforMulti-sourceNetwork Coding［EB/OL］.(2010-06-04).http://eprint.iacr.org/2010/328.

［8]Agrawal S,Boneh D,Boyen X,et al.Preventing Pollution AttacksinMulti-sourceNetworkCoding［C］// Proceedingsof2010ConferenceonPublicKey Cryptography.Berlin,Germany:Springer,2010:161-176.

［9]Yang H,Yang M.An Unconditionally Secure Authentication CodeForMulti-sourceNetworkCoding［J］.InternationalJournalofWirelessandMicrowave Technologies,2012,2(1):45-49.

［10]Shao Jun,Zhang Jinlin,Ling Yun,et al.Multiple Sources Network Coding Signature in the Standard Model［M］// Pathan M,Wei Guiyi,Fortino G.Internet and Distributed Computing Systems.Berlin,Germany:Springer,2013: 195-208.

［11]Krohn M N,Freedman M J,Mazieres D.On-the-fly Verification of Rateless Erasure Codes for Efficient ContentDistribution［C］//ProceedingsofIEEE Symposium on Security and Privacy.Oakland,USA: IEEE Press,2004:226-240.

［12]Boneh D,Gentry C,Lynn B,et al.Aggregate and VerifiablyEncryptedSignaturesfromBilinear Maps［C］//Proceedings of EUROCRYPT’03.Berlin, Germany:Springer-Verlag,2003:416-432.

［13]牛淑芬,王彩芬.多源線性網絡編碼的同態(tài)簽名算法［J］.計算機工程,2012,38(2):126-128.

［14]牛淑芬,王彩芬,劉雪艷.抵御污染攻擊的雙源網絡編碼簽名算法［J］.計算機應用,2011,31(6):1512-1514.

［15]嚴文杰.網絡編碼簽名算法［D］.武漢:武漢理工大學,2010.

［16]The Pairing-basedCryptographyLibrary［EB/OL］.(2010-07-15).http://crypto.stanford.edu/pbc/.

編輯 陸燕菲

Data Integrity Verification Scheme for Multi-source Network Coding

NIU Shufen,WANG Caifen,ZHANG Yulei,CAO Suzhen
(College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

Taking advantage of vector merging algorithm and homomorphic Hash function,this paper proposes a data integrity scheme for multi-source network coding against pollution attacks.Each source node computes raw massage’s Hash values and uses a secure mechanism to sign the Hash values,then appends the Hash values and its signatures to each message which sends to forward nodes and sink nodes.The forwarder can verify the integrity of network coded data from different source nodes without knowing the sources private keys and generating the Hash for the combined messages.Experimental results show that the computation efficiency of the proposed scheme is better than the existing multi-source network coding scheme,and it is more suitable for the large-scale distributed network data security verification.

multi-source network coding;data integrity;aggregate signature;homomorphic Hash function;vector merging algorithm;discrete logarithm problem

牛淑芬,王彩芬,張玉磊,等.多源網絡編碼數(shù)據(jù)完整性驗證方案［J］.計算機工程,2015,41(3):21-25.

英文引用格式:Niu Shufen,Wang Caifen,Zhang Yulei,et al.Data Integrity Verification Scheme for Multi-source Network Coding［J］.Computer Engineering,2015,41(3):21-25.

1000-3428(2015)03-0021-05

:A

:TP309.7

10.3969/j.issn.1000-3428.2015.03.004

國家自然科學基金資助項目(61163038);西北師范大學青年教師科研提升計劃基金資助項目(NWNU-LKQN-13-12)。

牛淑芬(1976-),女,副教授、博士,主研方向:網絡編碼,云計算,無線傳感器網絡;王彩芬,教授、博士生導師;張玉磊,副教授;曹素珍,副教授、碩士。

2014-04-01

:2014-06-03E-mail:sfniu76@nwnu.edu.cn