融合時間戳和同態簽名的安全網絡編碼方法

裴恒利，尚濤，劉建偉

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

1 引言

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

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

2 相關研究

2.1 隨機線性網絡編碼

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

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

圖1 網絡拓撲

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

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

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

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

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

2.2 同態簽名

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

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

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

3 安全網絡編碼方案

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

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

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

Step1 源節點選取參數。與基于RSA的同態簽名方案相類似，參數選取過程簡述如下。

表1 相關參數

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

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

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

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

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

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

命題1函數SIGNd具有加法同態性。

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

因此

命題得證。

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

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

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

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

4 安全性分析

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

4.1 污染攻擊的安全性分析

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

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

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

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

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

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

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

則問題轉化為希望找到 x使其滿足式(19)。可以看出由式(19)求解x是一個離散對數困難問題，命題2得證。

4.2 重放攻擊的安全性分析

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

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

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

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

5 性能分析

5.1 開銷分析

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

1) 參數初始化開銷

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

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

3) 計算簽名的開銷

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

4) 驗證簽名的開銷

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

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

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

5.2 網絡編碼解碼概率分析

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

其中，d表示網絡中目的節點的個數，q為有限域的大小，η為源節點所發消息的個數。

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

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

6 仿真分析

6.1 時耗分析

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

圖2 網絡拓撲

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

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

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

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

6.2 能耗分析

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

網絡中節點所處理的數據分組類型分為2種：重放數據分組和非重放數據分組。

對于重放數據分組，3種方案中節點的處理過程可分為以下3點。

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

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

3) 編碼方案。編碼。

對于非重放數據分組，3種方案中節點的處理過程可分為以下3點。

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

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

3) 編碼方案。編碼。

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

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

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

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

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

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

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

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

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

7 結束語

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

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

[2] 曹張華, 唐元生. 安全網絡編碼綜述[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]. 河北工業大學學報, 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.