李世浩，梅中輝

(南京郵電大學 通信與信息工程學院，江蘇 南京 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