裴恒利，尚濤，劉建偉

（北京航空航天大學 電子信息工程學院，北京 100191）

1 引言

網(wǎng)絡編碼技術[1]因有利于無線多跳網(wǎng)絡傳輸性能的提升而成為近年的研究熱點，但同時它也帶來了許多安全問題。例如，在無線多跳網(wǎng)絡中，網(wǎng)絡編碼特別容易受到惡意節(jié)點的污染攻擊[2]，同時也會遭受傳統(tǒng)網(wǎng)絡中存在的重放攻擊、假冒攻擊、篡改攻擊、拒絕服務攻擊、中間人攻擊等[3]。針對污染攻擊，Ho等利用簡單多項式散列函數(shù)（simple polynomial hash function）在目的節(jié)點處對消息的完整性進行驗證[4]，然而，中繼節(jié)點并未參與完整性驗證，因此相應地會增加受攻擊的數(shù)據(jù)分組在網(wǎng)絡中的傳輸數(shù)量。Gkantsidis和Rodriguez提出的同態(tài)散列方案(homomorphic hashing scheme)[5]實現(xiàn)了中繼節(jié)點對消息完整性的驗證，但卻需要額外的安全信道來傳輸原始消息的散列值。隨后，Charles等在同態(tài)散列方案的基礎上設計了一種同態(tài)簽名方案(homomorphic signature scheme)[6]，該方案不需要額外的安全信道，但由于復雜的韋伊配對操作（weil pairing operation）會增加運算的復雜度，因此，其應用受到了限制，而Yu等提出的基于RSA的同態(tài)簽名方案[7]則大大降低了同態(tài)簽名的運算復雜度。Rosario等[8]對Yu的方案進行了改進，將基于RSA的同態(tài)簽名方案設計在整數(shù)域中，并通過隨機預言模型（random oracle model）證明了該方案的安全性。

雖然同態(tài)簽名方案能夠抵御污染攻擊，但由于網(wǎng)絡中攻擊形式的多樣性，設計可同時抵御包含污染攻擊在內的多種攻擊網(wǎng)絡編碼簽名方案非常重要。尤其是對能量受限的無線傳感器網(wǎng)絡而言，節(jié)點的能量是制約網(wǎng)絡性能提升的主要因素，而重放攻擊因會大量消耗節(jié)點能量而成為此類網(wǎng)絡所面臨的最棘手的攻擊之一。因此，針對能量受限的無線多跳網(wǎng)絡，本文在基于RSA同態(tài)簽名方案的基礎上設計了一種融合時間戳和同態(tài)簽名的可同時抵御污染攻擊與重放攻擊的網(wǎng)絡編碼簽名方案——該方案將對時間戳和對數(shù)據(jù)的簽名有效地結合起來，保證了網(wǎng)絡中各節(jié)點可以同時認證數(shù)據(jù)的完整性和時間戳的真實性；并進一步分析了引入時間戳對網(wǎng)絡編碼解碼概率的影響以及對網(wǎng)絡開銷的影響。

2 相關研究

2.1 隨機線性網(wǎng)絡編碼

網(wǎng)絡編碼按照編碼系數(shù)產(chǎn)生方式的不同可分為隨機性網(wǎng)絡編碼和確定性網(wǎng)絡編碼，按照編碼方式的不同可分為線性網(wǎng)絡編碼和非線性網(wǎng)絡編碼[9]。根據(jù)無線多跳網(wǎng)絡的分布式特點，以下重點介紹隨機線性網(wǎng)絡編碼的具體過程。

網(wǎng)絡拓撲如圖1所示。其中，A為源節(jié)點，(t1,…,tk)為目的節(jié)點，其他各節(jié)點為中繼節(jié)點。源節(jié)點將要發(fā)送的每一條原始消息設定為選自有限域Zq的長度為n的向量，其中，q是預先定義的素數(shù)。因此，原始消息Mi可表示為

圖1 網(wǎng)絡拓撲

在隨機線性網(wǎng)絡編碼中，每一個中繼節(jié)點將收到的消息線性組合，生成編碼消息E并轉發(fā)。因此，E可表示為該中繼節(jié)點所收到的消息的線性疊加，即

相應地，中繼節(jié)點收到的消息向量E’記為

其中，Mi’、E’可統(tǒng)稱為擴展消息或擴展向量（augmented message）[10]。為防止攻擊者截獲從源節(jié)點發(fā)出的原始消息，源節(jié)點對其所要發(fā)送的消息也要進行編碼，即對要發(fā)送的 m條擴展消息進行m次線性組合，獲得m條編碼消息并轉發(fā)。

目的節(jié)點在收到m條線性無關的消息(E1’, …,Em’)后，即可得矩陣 ′U為

將矩陣 U ′的前 m列構成的矩陣記作 U，后 n列構成的矩陣記作V，則由式(5)便可將源節(jié)點發(fā)送的m條原始消息解碼恢復。

2.2 同態(tài)簽名

同態(tài)分為加法同態(tài)和乘法同態(tài)[11]。給定變量X1和X2，若對于函數(shù)Φ，存在函數(shù)f使得式(6)成立，則稱函數(shù)Φ滿足加法同態(tài)。

若對函數(shù)Φ，存在函數(shù)f使得式(7)成立，則稱函數(shù)Φ滿足乘法同態(tài)。

同態(tài)簽名便是利用了同態(tài)函數(shù)保持運算的性質。節(jié)點接收的消息與相應簽名分別記作和若當前節(jié)點要對接收到消息的線性組合生成簽名S，如果Φ具有加法同態(tài)性，則當前節(jié)點可直接由式(8)生成簽名。其中，由式(8)計算出的簽名S與相等，這樣便實現(xiàn)了中繼節(jié)點在未知源節(jié)點私鑰的情況下對所要發(fā)送的消息進行簽名。本文安全網(wǎng)絡編碼方案中的簽名函數(shù)具有加法同態(tài)性，詳見第 3節(jié)中命題1的證明。

3 安全網(wǎng)絡編碼方案

在安全網(wǎng)絡編碼方案中，時間戳信息可以起到兩方面作用：一是網(wǎng)絡中各節(jié)點可以利用時間戳來識別重放消息，以抵御網(wǎng)絡中的重放攻擊；二是以時間戳為源產(chǎn)生網(wǎng)絡編碼的隨機系數(shù)，可以保證網(wǎng)絡中各節(jié)點能夠利用簽名函數(shù)的加法同態(tài)性對編碼后的消息產(chǎn)生簽名。因此，本文在利用基于RSA同態(tài)簽名方案抵御污染攻擊的基礎上，引入時間戳設計新型同態(tài)簽名方案以抵御網(wǎng)絡中的重放攻擊，并以時間戳為源生成網(wǎng)絡編碼的隨機系數(shù)。

網(wǎng)絡拓撲如圖1所示。A為源節(jié)點，不規(guī)則區(qū)域內的節(jié)點為中繼節(jié)點，為目的節(jié)點，表示由原始消息生成的擴展消息，由長度為m + n 的向量表示。全網(wǎng)采用同步時鐘，且所有中繼節(jié)點均對收到的消息編碼。方案中的相關參數(shù)如表1所示。

方案仍采用傳統(tǒng)的基于RSA的同態(tài)簽名方案，但由于在簽名方案中引入了時間戳機制，為保證簽名仍具有同態(tài)屬性，方案考慮以時間戳為源生成網(wǎng)絡編碼的隨機系數(shù)，具體過程如下。

Step1 源節(jié)點選取參數(shù)。與基于RSA的同態(tài)簽名方案相類似，參數(shù)選取過程簡述如下。

表1 相關參數(shù)

Step2 源節(jié)點生成簽名。在源節(jié)點的簽名生成過程中引入了時間戳，對消息和時間戳的組合生成簽名。

源節(jié)點產(chǎn)生 m條擴展消息并附上當前時刻作為該條消息的時間戳（需將時間戳 Ti轉換為 Zq中的數(shù)值），然后用私鑰d對m條消息簽名，其中，簽名 SIGNd(Mi’||Ti)如式(9)所示。

Step3 中繼節(jié)點驗證簽名并生成新的簽名。具體過程如下。

如果式(10)成立，則可斷定該消息組合沒有受到污染攻擊，這是因為：若該消息組合在傳輸過程中的數(shù)據(jù)部分沒有遭到破壞，則式(11)成立。

然后由消息組合中的時間戳部分判斷該消息組合是否被重放，如果為重放消息則丟棄。若消息組合在時效范圍內，則該節(jié)點在收到k條消息組合k)后，為保證能夠利用同態(tài)性質對此k條消息組合中數(shù)據(jù)部分的線性組合進行簽名，則需根據(jù)當前時刻T以及收到的k條消息組合中的時間戳由式(12)計算出隨機系數(shù)

利用該組隨機系數(shù)對收到的k條消息組合中的數(shù)據(jù)進行線性疊加，得到編碼數(shù)據(jù) E’||T：即，并利用簽名的同態(tài)性質，由k條消息組合中的簽名生成與E’||T對應的簽名 SIGNd(E’||T)。

命題1函數(shù)SIGNd具有加法同態(tài)性。

證明設是長度為m+n+1的向量，則由式(9)可得

因此

命題得證。

因此可利用同態(tài)性質生成對消息 E’||T的簽名SIGNd(E’||T)，式(15)給出了該簽名的計算式。

然后，節(jié)點將消息組合{E’||T, SIGNd(E’||T)}轉發(fā)。

Step4目的節(jié)點驗證簽名并對源節(jié)點發(fā)送消息解碼恢復，具體過程如下。

目的節(jié)點在收到一條消息組合后，首先通過式(10)來判斷消息是否受到污染攻擊，然后等待。當接收到 m條線性無關的消息組合后，利用式(5)對源節(jié)點發(fā)送的消息解碼恢復。

4 安全性分析

本文的安全網(wǎng)絡編碼方案中假設源節(jié)點總是安全的，只有中繼節(jié)點不可信。攻擊者可能會控制中繼節(jié)點，破壞其所要發(fā)送的消息，對網(wǎng)絡實施污染攻擊；另外，攻擊者也可能會控制中繼節(jié)點，使其重復發(fā)送已經(jīng)發(fā)送過的消息，對網(wǎng)絡實施重放攻擊。

4.1 污染攻擊的安全性分析

攻擊者的污染攻擊方式分為2種：一是產(chǎn)生偽造消息數(shù)據(jù)并對其生成有效簽名；二是根據(jù)攻擊者所截獲的消息組合中的簽名產(chǎn)生與之相匹配的消息數(shù)據(jù)。

在第一種攻擊方式中，攻擊者污染中繼節(jié)點接收到消息組合中的數(shù)據(jù)部分或直接將偽造的消息數(shù)據(jù)注入網(wǎng)絡，中繼節(jié)點編碼后的消息因此遭到污染。將攻擊者污染后的消息記作，則中繼節(jié)點編碼后的消息與未受攻擊時所產(chǎn)生的編碼消息E'T不同，即

但由于攻擊者未知源節(jié)點私鑰，因此無法對該污染消息生成有效簽名，所以攻擊無效。

在第二種攻擊方式中，攻擊者依照截獲的消息組合中的簽名生成與之匹配的數(shù)據(jù)，即希望根據(jù)所截獲的消息組合中的簽名推出與之相應的數(shù)據(jù)因此，該方案的安全性等同于是否可以找到不同于E'T的數(shù)據(jù)E?'T?，使得，下面將證明其困難度等價于解決離散對數(shù)問題。

命題2給定消息E'T和相應簽名找到不同于E'T的消息E?'T?，使得的困難度等價于解決離散對數(shù)問題。

證明為簡化說明，考慮 m = n =1的特殊情況，此時，

固定 e? 1'和 e?2'，令 x = e?3'，式(18)變換為

則問題轉化為希望找到 x使其滿足式(19)?？梢钥闯鲇墒?19)求解x是一個離散對數(shù)困難問題，命題2得證。

4.2 重放攻擊的安全性分析

在重放攻擊中，攻擊者截獲網(wǎng)絡中的消息組合并不斷轉發(fā)或通過控制中繼節(jié)點使其重復發(fā)送已發(fā)送過的消息組合，從而達到消耗網(wǎng)絡節(jié)點能量、占用網(wǎng)絡帶寬和降低網(wǎng)絡吞吐量等目的。

在該攻擊中，攻擊者有2種攻擊方式：直接重放所截獲的消息組合或修改所截獲消息組合中的時間戳并對其生成有效簽名。

第二種攻擊方式相當于污染攻擊中的第一種攻擊方式：對偽造數(shù)據(jù)生成有效簽名。攻擊者由于未知源節(jié)點的私鑰，因此無法對截獲的消息組合中的數(shù)據(jù)部分進行簽名，所以攻擊無效。

由以上安全性分析可知，本文提出的安全網(wǎng)絡編碼方案可同時抵御污染攻擊和重放攻擊，且攻擊成功的困難度等同于解決離散對數(shù)困難問題。

5 性能分析

5.1 開銷分析

為了分析安全網(wǎng)絡編碼的性能，本節(jié)重點考慮簽名算法所引發(fā)的開銷，不考慮引入同步計時機制帶來的開銷。網(wǎng)絡中傳送的消息組合以{E ' T ,的形式出現(xiàn)，其中，E'T為數(shù)據(jù)，以向量形式表示，為簽名。由于時間戳T的引入使網(wǎng)絡開銷相較于基于RSA的同態(tài)簽名方案有所增加，現(xiàn)將增加的開銷類型分類如下（下文中為敘述簡便，稱基于 RSA的同態(tài)簽名方案為方案 1，本文的引入時間戳的同態(tài)簽名方案為方案2，且開銷均指算法耗費時間）。

1) 參數(shù)初始化開銷

參數(shù)初始化階段耗費時間近似正比于方案所需 gi的個數(shù)，與方案1相比兩者的耗費時間比值近似等于，且m和n數(shù)值越大該比值越接近于1。

2) 編解碼與求解線性方程組的開銷

3) 計算簽名的開銷

網(wǎng)絡中有2類節(jié)點產(chǎn)生簽名：源節(jié)點和中繼節(jié)點。由于源節(jié)點僅有1個，而中繼節(jié)點數(shù)目較多，因此簽名開銷主要產(chǎn)生在中繼節(jié)點。其中，中繼節(jié)點生成簽名的運算如式(9)所示，將方案 1中的簽名記作SIGNd(E ') ，方案2中的簽名記作，由于兩者均取值于有限域 Zr中，且隨機系數(shù)均選自有限域Zq，因此，對兩者作k次模指數(shù)運算的開銷比值近似接近于1。

4) 驗證簽名的開銷

中繼節(jié)點的主要功能是對收到的簽名進行驗證。驗證過程應保證盡可能地快速。然而，由于簽名采用基于 RSA的公鑰簽名體制，使得簽名的驗證時間成為了制約網(wǎng)絡性能提升的主要因素。因此，衡量方案性能的最重要指標是簽名算法的驗證時間。

模指數(shù)運算是算法效率的制約因素。由式(10)可知，方案2的簽名驗證過程（驗證一條消息）需經(jīng)過次模指數(shù)運算，而方案1的簽名驗證過程僅需運算次，因此兩者的簽名驗證時間的比值為，且m與n的值越大，該比值越接近于1。

由以上分析可知，與方案1相比，方案2僅在參數(shù)初始化與簽名驗證部分增加了網(wǎng)絡的開銷，而簽名、編解碼與求解線性方程所引起的網(wǎng)絡開銷與方案1基本一致。

5.2 網(wǎng)絡編碼解碼概率分析

隨機線性網(wǎng)絡編碼中隨機系數(shù)的生成和選取對目的節(jié)點的解碼概率有一定影響，而本文網(wǎng)絡編碼方案中的隨機系數(shù)通過求解 k元一次方程組產(chǎn)生，與傳統(tǒng)的隨機系數(shù)的產(chǎn)生方式有所不同，究竟對解碼概率有多大影響，需要進一步詳細分析。

其中，d表示網(wǎng)絡中目的節(jié)點的個數(shù)，q為有限域的大小，η為源節(jié)點所發(fā)消息的個數(shù)。

證明 在隨機線性網(wǎng)絡編碼網(wǎng)絡中，若隨機系數(shù)滿足 Zq中的均勻分布且相互獨立，則目的節(jié)點解碼概率P的取值范圍為因此，命題3可轉化為證明式(12)的k個解滿足獨立均勻分布。

由上述分析可得a1滿足均勻分布且與(a2,…,ak)相互獨立，命題3得證。

6 仿真分析

6.1 時耗分析

利用 NS2網(wǎng)絡仿真軟件對本文所介紹的安全網(wǎng)絡編碼方案進行仿真。其中，傳輸層采用UDP數(shù)據(jù)流，網(wǎng)絡層協(xié)議采用洪泛協(xié)議，編碼尺寸設定為2，網(wǎng)絡拓撲如圖2所示。A表示源節(jié)點，D表示目的節(jié)點，1、2、3、4、5節(jié)點表示中繼節(jié)點。

圖2 網(wǎng)絡拓撲

改變源節(jié)點消息向量中元素的個數(shù)m，將基于RSA的同態(tài)簽名方案記為RSA方案，所得的算法運行時間對比如圖3所示。

圖3 本方案和RSA方案的運行時間對比

從圖3中可以看出，隨著消息向量中元素個數(shù)的增加，2方案的算法運行時間基本呈線性增長。另外，隨著m的增大，2方案的曲線基本重合，這是因為算法中引入的時間戳T可以看作消息向量m中的一個元素，隨著m值的增大，引入時間戳帶來的時耗在整個算法時耗中所占的比重越小。

由上述分析可知，同5.1節(jié)中的理論分析結果相一致，本方案和RSA方案的算法時耗基本一致，并且由于本方案能夠同時抵御污染攻擊和重放攻擊，因此綜合考慮算法時耗與安全性能，本方案優(yōu)于RSA方案。

6.2 能耗分析

本小節(jié)分析了當網(wǎng)絡遭遇重放攻擊時，本方案、RSA方案以及未引入安全機制的網(wǎng)絡編碼方案（簡記為編碼方案）的節(jié)點能耗。

網(wǎng)絡中節(jié)點所處理的數(shù)據(jù)分組類型分為2種：重放數(shù)據(jù)分組和非重放數(shù)據(jù)分組。

對于重放數(shù)據(jù)分組，3種方案中節(jié)點的處理過程可分為以下3點。

1) 本方案。判斷其是否為重放分組（表2中簡記為判斷），如果為重放分組，則將其丟棄。

2) RSA方案。驗證簽名、編碼、計算簽名（表2中簡記為驗證編碼簽名）。

3) 編碼方案。編碼。

對于非重放數(shù)據(jù)分組，3種方案中節(jié)點的處理過程可分為以下3點。

1) 本方案。驗證簽名、編碼、計算簽名。

2) RSA方案。驗證簽名、編碼、計算簽名。

3) 編碼方案。編碼。

利用 MATLAB計算上述不同處理過程的運行時間，當消息向量中元素個數(shù)m=256時，得到處理過程的運行時間如表2所示。

表2 不同處理過程的運行時間

利用公式 W ( 能 量) = P ( 功 率) × T (時 間) 可計算出每種處理過程對應的能耗。固定網(wǎng)絡中非重放數(shù)據(jù)分組的個數(shù)為10，改變重放數(shù)據(jù)分組的個數(shù)，結合表2中的數(shù)據(jù)，可得3種方案中節(jié)點的能耗對比如圖4所示。

圖4 本方案、RSA方案以及編碼方案的能耗對比

從圖4中可知，RSA方案的能耗遠遠高于其他2種方案，因此，在網(wǎng)絡遭遇重放攻擊時，相較于僅可抵御污染攻擊的 RSA方案，本方案能夠很好地節(jié)省節(jié)點能量，延長節(jié)點的生存時間。

圖5為排除RSA方案后，本方案與編碼方案的算法能耗對比。

圖5 本方案和編碼方案的能耗對比

由圖5可知，當重放數(shù)據(jù)分組的個數(shù)較小時，相較本方案，編碼方案的能耗較??；隨著重放數(shù)據(jù)分組個數(shù)的增加，編碼方案能耗呈線性增長，而本方案的能耗基本不變。

由上述分析可知，相較于未引入安全機制的網(wǎng)絡編碼方案，本方案更能夠抵御惡意節(jié)點重放攻擊所帶來的能耗，可以更好地延長節(jié)點的生存時間。

7 結束語

本文的安全網(wǎng)絡編碼方案利用融合時間戳的同態(tài)簽名來抵御網(wǎng)絡中的污染攻擊和重放攻擊，為保證中繼節(jié)點能夠利用同態(tài)性質對編碼后的消息生成新的簽名，需要以時間戳為源來生成網(wǎng)絡編碼的隨機系數(shù)。文中重點分析了本方案產(chǎn)生隨機系數(shù)的方式對網(wǎng)絡編碼解碼概率的影響，并建立攻擊模型證明方案可同時抵御污染攻擊和重放攻擊，性能分析表明該方案與基于 RSA的同態(tài)簽名方案開銷比值接近于 1，因此，網(wǎng)絡中各節(jié)點并不會因為增加了對時間戳的處理步驟而增長數(shù)據(jù)處理時間。

[1] AHLSWEDE R, CAI N, LI S. Network information flow[J]. IEEE Transactions on Information Flow, 2000, 46(4)∶1204-1216.

[2] 曹張華, 唐元生. 安全網(wǎng)絡編碼綜述[J]. 計算機應用, 2010, 30(2)∶499-505.CAO Z H, TANG Y S. Survey on secure network coding[J]. Journal of Computer Application, 2010, 30(2)∶499-505.

[3] PERVAIZ M, CARDEI M, WU J. Routing security in ad hoc wireless networks[J]. Network Security, 2010, 117-142.

[4] HO T, LEONG B, KOETTER R. Byzantine modification detection in multicast networks using randomized network coding[A]. Proceedings of IEEE International Symposium on Information Theory(ISIT)[C].Massachusetts, USA, 2008. 2798-2803.

[5] GKANTSIDIS C, RODRIGUEZ P. Cooperative security for network coding file distribution[A]. Proceedings of International Conference on Computer Communications(INFOCOM)[C]. Barcelona, Spain, 2006.367-380.

[6] MENEZES A, OKAMOTO T, VANSTONE S. Reducing elliptic curve logorithms to logorithms in a finite field[J]. IEEE Transactions on Information Theory, 1993, 39(5)∶1639-1646.

[7] YU Z, WEI Y, RAMKUMAR B. An efficient signature-based scheme for securing network coding against pollution attacks[A]. Proceedings of International Conference on Computer Communications (INFOCOM)[C].Arizona, USA, 2008. 1409-1417.

[8] GENNARO R, KATZ J, KRAWCZYK H. Secure network coding over the integers[J]. Public Key Cryptography, 2010, 60(56)∶142-160.

[9] LIM S H, KIM Y H. Noisy network coding[J]. IEEE Transactions on Information Theory, 2011, 57(5)∶3132-3152.

[10] LIM S H, GERLA M, KRAWCZYK H. Performance evaluation of secure network coding using homomorphic signature[A]. Proceedings of International Symposium on Network Coding(NetCod)[C]. Beijing,China, 2011. 1-6.

[11] SUTAR S G, PATIL G A. Privacy management in cloud by making use of homomorphic functions[J]. International Journal of Computer Applications, 2012, 37(2)∶13-16.

[12] CAI N, SHI X, MEDARD M. Localized dimension growth in random network coding∶ a convolutional approach[A]. Proceedings of IEEE International Symposium on Information Theory(ISIT)[C]. St Petersburg, USA, 2011. 1156-1160.

[13] 劉鳳梅, 李世取, 黃曉英. 取值于有限域上的獨立隨機變量和的極限分布定理[J]. 河北工業(yè)大學學報, 1999, 1(28)∶98-102.LIU F M, LI S Q, HUANG X Y. Limit distribution theorem for a sum of independent random variables whose values belong to a finite field[J].Journal of Hebei University of Technology, 1999, 1(28)∶98-102.