一種高效的防竊聽和抗污染的安全網(wǎng)絡(luò)編碼方案

劉光軍

（西安文理學(xué)院信息工程學(xué)院，陜西西安710065）

網(wǎng)絡(luò)編碼能有效提高網(wǎng)絡(luò)的吞吐量和安全性，增強(qiáng)網(wǎng)絡(luò)的健壯性和穩(wěn)定性，降低網(wǎng)絡(luò)的能耗，具有重要的理論和潛在應(yīng)用價值[1-3]。但是，網(wǎng)絡(luò)編碼傳輸具有信息融合的特性，致使其容易遭受污染和搭線竊聽攻擊。當(dāng)前，設(shè)計高效的抗污染和防竊聽策略是當(dāng)前網(wǎng)絡(luò)編碼領(lǐng)域中的重要研究熱點(diǎn)。

文獻(xiàn)[4]首次從信息理論意義上考慮了網(wǎng)絡(luò)編碼傳輸中的抗污染檢測問題，但該方案通信開銷極大。后來出現(xiàn)的較實用的安全方案大部分結(jié)合同態(tài)密碼學(xué)的代數(shù)性質(zhì)，并能有效地整合網(wǎng)絡(luò)編碼的傳輸特性，代表性方案包括基于同態(tài)簽名的方案[5]，基于同態(tài)Hash的方案[6]，基于同態(tài)MAC的方案[7]和基于推遲分發(fā)密鑰的策略[8-9]。這類方案雖然實現(xiàn)了對被污染數(shù)據(jù)包實時過濾功能，但基本上都不能有效解決共謀以及代間污染問題。雖然文獻(xiàn)[10-11]可以有效解決這種問題，但它們卻存在著計算復(fù)雜度過高和通信開銷過大、網(wǎng)絡(luò)拓?fù)湟蕾嚨膯栴}。

與此同時，對防竊聽方面的研究也取得了一些較突出的工作成果。文獻(xiàn)[12-14]利用代數(shù)安全預(yù)編碼技術(shù)實現(xiàn)了對全局編碼信息的保護(hù)，有效阻止了攻擊者對機(jī)密內(nèi)容的析取和網(wǎng)絡(luò)流量的分析。文獻(xiàn)[15]提出了P-Coding方案。Cheng等[16]利用信息不等式，給出了P2P網(wǎng)絡(luò)任意信道子集被竊聽時的安全網(wǎng)絡(luò)編碼構(gòu)造。進(jìn)一步地，筆者在文獻(xiàn)[17]利用糾錯編碼的系統(tǒng)構(gòu)造方法，提出一種具有安全可度量屬性的編碼方案。然而，現(xiàn)有的這些研究工作只是片面地考慮了抗污染問題。

綜上所述，現(xiàn)有研究不僅普遍存在著通信效率不高、安全性能不足的共性問題，而且由于大部分方案只關(guān)注單一安全目標(biāo)的實現(xiàn)，難以適應(yīng)網(wǎng)絡(luò)編碼多目標(biāo)安全通信場景中的安全應(yīng)用，因而缺乏一種對多種安全功能的系統(tǒng)性設(shè)計策略。雖然文獻(xiàn)[18-19]中同時考慮了抗污染和防竊聽問題，但綜合性能很不理想。這些基于信息論的方案都需要一個充分大的編碼域，致使其付出了高昂的通信開銷和計算代價，而且難以抵御代間污染攻擊。

文中首先利用最大距離可分碼的系統(tǒng)構(gòu)造技術(shù)來實現(xiàn)網(wǎng)絡(luò)安全碼，然后給出一種逐代動態(tài)變化的代數(shù)密鑰分配機(jī)制。借助于這種密鑰更新策略，本文設(shè)計了一種高效的網(wǎng)絡(luò)編碼多目標(biāo)安全通信需求中的系統(tǒng)化安全方案，有效克服了多種安全機(jī)制的簡單組合（松耦合）設(shè)計的低效性。

1 網(wǎng)絡(luò)與攻擊模型

文中考慮單源無圈網(wǎng)絡(luò)中網(wǎng)絡(luò)編碼傳輸情形。信源首先把信源消息進(jìn)行預(yù)編碼，生成一個由連續(xù)的代序列組成的信息流。在下文中，統(tǒng)一采用文獻(xiàn)[1]中的隨機(jī)網(wǎng)絡(luò)編碼協(xié)議模型。在傳輸中，各代消息均用不同的標(biāo)識符來標(biāo)記。每代消息用一個定義在有限域Fq上的符號矩陣來表示。這里|Fq|=q。

假設(shè)信源是可信實體，且攻擊者的計算資源有限，即攻擊者最多能執(zhí)行概率多項式時間的攻擊算法。攻擊者可以監(jiān)控網(wǎng)絡(luò)傳輸中的所有消息，并可以從中析取有價值的機(jī)密信息。同時，它可實時地在網(wǎng)絡(luò)各處注入經(jīng)過偽造或篡改的污染消息，試圖使其最終能通過檢驗節(jié)點(diǎn)的合法驗證。網(wǎng)絡(luò)攻擊者可能來自網(wǎng)絡(luò)內(nèi)部或外部的一個或多個實體，也可與網(wǎng)內(nèi)的節(jié)點(diǎn)進(jìn)行共謀。

2 基本方案

為簡單起見，本文只描述網(wǎng)絡(luò)編碼系統(tǒng)對一代消息的安全通信處理過程。

令該代消息的標(biāo)識符為id，信源將其擴(kuò)展編碼為符號矩陣

2.1 系統(tǒng)配置

KDC給信源秘密發(fā)送t個隨機(jī)向量且矩陣可逆。對于其它非信源節(jié)點(diǎn)，KDC也給其秘密發(fā)送一個隨機(jī)向量，計算其私有密鑰并發(fā)送給該節(jié)點(diǎn)，其中

ez的生成方法見下文公式（5）。

2.2 信源編碼

步驟1：信源us利用f1、f2生成兩個公開向量：

步驟3：信源利用向量a和b，計算生成兩個Vandermonde矩陣At×(m+n)和Bm×m，其第i行分別為和；

步驟4：信源生成其私有密鑰

計算并構(gòu)造矩陣

這里r=(ε1,ε2,...,εm)，其中ε1=Ek(b1)，其余的εi均為Fq中的隨機(jī)數(shù)。

步驟5：信源計算代認(rèn)證信息

在此階段中，信源采用了構(gòu)造最大距離可分系統(tǒng)碼的思想，結(jié)合代消息標(biāo)記的動態(tài)性，利用兩個Vandermonde矩陣對信源信息代進(jìn)行線性編碼，同時實現(xiàn)了通信的機(jī)密性和對信源消息的合法性保護(hù)機(jī)制。

2.3 消息檢測

步驟1：節(jié)點(diǎn)N利用id和us生成公開矩陣A，計算

是否成立。若成立，則該數(shù)據(jù)包合法；否則，將其丟棄。

2.4 信宿譯碼

合法的信宿收到足夠多的代id的數(shù)據(jù)包后，將借助于相應(yīng)的全局編碼信息使用高斯消元法解出消息矩陣D。然后，它通過解密恢復(fù)b1并計算b′和矩陣B，進(jìn)而解出代id的明文符號矩陣V。

3 方案合理性

進(jìn)一步，根據(jù)公式（6）-（8），可知

故公式（6）成立。

4 安全性分析

4.1 抗污染安全性

如果在上述安全方案的運(yùn)行過程中，一個攻擊者可以構(gòu)造一個消息向量且能通過某個節(jié)點(diǎn)?的認(rèn)證，即成立，則稱該攻擊者成功實施了一次污染攻擊。

定理1：本方案可以容忍t-1個網(wǎng)內(nèi)合法節(jié)點(diǎn)的共謀。

證明：假設(shè)當(dāng)前共謀合法節(jié)點(diǎn)擁有的密鑰對分別為 (e1,y1),(e2,y2),...,(eσ,yσ)。利用公式（7），這些惡意節(jié)點(diǎn)將要聯(lián)立等式ei=yiK(i=1,2,...,σ)來推導(dǎo)信源密鑰K。顯然，當(dāng)σ≥t時，矩陣將會以很高的概率可逆，從而能使這些節(jié)點(diǎn)恢復(fù)出信源密鑰K。

為保證最大強(qiáng)度的安全性，下面的分析均考慮這種t-1個惡意節(jié)點(diǎn)共謀的最壞情形。

定理2：任何一個污染攻擊者能成功地實施一次污染攻擊的概率最多為。

證明：若上述t-1共謀者構(gòu)造了一個非法的向量欲通過方案的認(rèn)證檢測，則必然要求其滿足公式（6），從而可得如下等式

由此，可以討論如下：

②若攻擊者先給定w=w0，則關(guān)于hˉ的線性方程 組的解空間的維數(shù)為m+n-t+1。類似（a）中的討論，即攻擊者污染成功的概率最大也為。

定理3：對于代間污染攻擊，該方案也是安全的。

證明：由于不同的代具有不同的id，故在認(rèn)證過程中必然使用了不同的公開認(rèn)證矩陣A=Aid。

任取代id1中的數(shù)據(jù)包，根據(jù)公式（5）（6），必有

攻擊者在代id2的傳輸過程中，欲用數(shù)據(jù)包p1去污染代id2的信息。假設(shè)p1能成功污染代id2，則必有

綜合公式（12）（13），必有

對攻擊者來說，向量c為隨機(jī)向量，欲使公式（13）成立，必需使。這顯然與前述矛盾。

由于矩陣A的生成依賴于各代標(biāo)識符，不同代消息在傳輸時都將使用不同的矩陣A，這將保證信源認(rèn)證密鑰的動態(tài)性，而這種動態(tài)性使得方案具有抗代間污染的能力。

4.2 防竊聽安全性

信源編碼步驟4中公式（3）是筆者在文獻(xiàn)[17]中的方案2的特例，故定理4的證明方法與文獻(xiàn)[17]中的思路相同。

定理4：針對任意具有多項式計算能力的竊聽者，該方案都不可能泄露信源明文消息的任何有意義信息。

步驟4和5中都涉及到了Vandermonde矩陣的乘法，其在實現(xiàn)防竊聽和抗污染安全功能中發(fā)揮了關(guān)鍵性作用。矩陣B實現(xiàn)了信源明文向量的隨機(jī)混淆，竊聽者在通信過程中不能完整地構(gòu)造矩陣B，故任意竊聽者都無法恢復(fù)信源機(jī)密消息。對于不同的代消息，方案在矩陣B的構(gòu)造中實時引入了隨機(jī)參數(shù)b1，可以保證多代通信的安全性。此外，矩陣A實現(xiàn)了消息向量之間的充分組合，確保了方案抗污染的能力。

5 方案性能評價

5.1 計算開銷

方案運(yùn)行過程中主要計算操作是矩陣的乘法運(yùn)算。下面將以乘法計算量來分析各階段的計算開銷。

1）信源認(rèn)證編碼

步驟1和2中的計算開銷較小，故可忽略。由于矩陣B的使用與代標(biāo)識符無關(guān)，故步驟3中的計算量主要來自于構(gòu)造矩陣A，其計算量為t(m+n-1)。步驟4需要執(zhí)行一次加密運(yùn)算以及構(gòu)造矩陣K和D，其總計算量為t2(m+n)+m2(n-1)。步驟5的乘法計算量為mt(m+n)。由于t＜m，故該階段總的計算復(fù)雜度為O(m2(m+n))。進(jìn)一步地，利用Vandermonde矩陣乘法的優(yōu)化計算技術(shù)，可以將該復(fù)雜度進(jìn)一步降低為O(m(m+n)log2m)。

2）消息檢測

該階段每個認(rèn)證節(jié)點(diǎn)需要執(zhí)行一次PRF操作、矩陣構(gòu)造和等式判別運(yùn)算，其計算復(fù)雜度為O(t2(m+n))。

3）信宿譯碼算法

信宿節(jié)點(diǎn)需要對接收消息進(jìn)行驗證，復(fù)雜度為O(t2(m+n))。信宿節(jié)點(diǎn)譯碼需要執(zhí)行高斯消元運(yùn)算，其計算開銷來自于網(wǎng)絡(luò)編碼協(xié)議運(yùn)行本身，故可以忽略。

綜合而言，方案總體運(yùn)行計算復(fù)雜度為O(m(m+n)log2m)。

5.2 帶寬開銷

該方案除了為傳輸全局編碼信息所帶來的帶寬開銷m（網(wǎng)絡(luò)編碼協(xié)議運(yùn)行本身所決定）外，付出的通信開銷為t（用于各數(shù)據(jù)包認(rèn)證信息的傳輸），故方案的有效傳輸容量達(dá)到n-m-t，與現(xiàn)有方案相當(dāng)。

5.3 方案比較

表1將本方案與一些有代表性的單安全目標(biāo)方案進(jìn)行比較，如下所示。

表1 代表性安全方案性能比較

文中提出的方案有效地實現(xiàn)了防竊聽和抗污染兩種安全性能，并能很好地解決代間污染和節(jié)點(diǎn)共謀問題。相比之下，文獻(xiàn)[12-17]僅關(guān)注于網(wǎng)絡(luò)防竊聽的安全性能，沒有考慮與當(dāng)前抗污染方案的系統(tǒng)融合設(shè)計。除此之外，表1中部分方案雖然實現(xiàn)了抗污染安全功能，但這些方案僅能實現(xiàn)點(diǎn)對點(diǎn)的污染檢測能力，且存在代間污染問題。

其次，與現(xiàn)有單安全目標(biāo)方案相比，本文方案沒有顯著增加在信源編碼和節(jié)點(diǎn)認(rèn)證方面的計算復(fù)雜度。從表1看出，本文方案的編碼效率仍然具有一定的優(yōu)勢。雖然仍有個別其它方案的信源編碼復(fù)雜度較小，例如文獻(xiàn)[8]，但這種效率上的優(yōu)勢卻是以安全強(qiáng)度的降低換來的。

再者，為了在保證效率和安全強(qiáng)度的前提下同時實現(xiàn)防竊聽和抗污染功能，現(xiàn)實可行的策略只能將這些單安全目標(biāo)機(jī)制進(jìn)行簡單的組合設(shè)計。實驗證明，這種方法運(yùn)行的計算開銷將大大高于本文方案。我們通過Matlab R2010a平臺利用Intel Core2-2.80 GHz處理器對本文方案（記為S0）與現(xiàn)有可有效實現(xiàn)的組合方案的信源編碼時間性能進(jìn)行測試對比。對比方案選擇文獻(xiàn)[7，17]的組合方案（基于對稱密碼體制，記為S1，文獻(xiàn)[17]中僅采用方案2）以及文獻(xiàn)[5，13]的組合方案（基于混合密碼體制，記為S2）。這種選擇的原因在于這些方案組合運(yùn)行中具有突出的低編碼復(fù)雜度。測試參數(shù)取m=20，n=1024。方案S1和S2中的編碼域分別取q=216和q=397。在編碼過程中，數(shù)據(jù)的加解密操作均采用AES算法。

圖1 方案信源編碼時間測試對比

圖1給出了在信源待傳輸消息代序列規(guī)模數(shù)量逐漸增大的情況下，方案S0，S1和S2信源編碼時需要的時間開銷t（單位：秒）與代序列規(guī)模呈正比例關(guān)系。這種線性特征最合理的解釋是每種方案對各代消息的處理時間相同。測試結(jié)果驗證了本文方案的性能優(yōu)勢。由于方案S2的設(shè)計基于公鑰密碼體制，其實現(xiàn)依賴于較大的編碼域，導(dǎo)致了該方案的編碼時間將會遠(yuǎn)高于其它兩個基于對稱密碼體制的方案S0和S1。進(jìn)一步地，由于文獻(xiàn)[7]在運(yùn)行中需要不斷地更新密鑰，其信源編碼時間必然多于本文方案。

最后，為了達(dá)到與本方案同等的安全性，文獻(xiàn)[7，8，10]中密鑰分配及更新的通信開銷將隨消息代規(guī)模線性遞增，導(dǎo)致這些方案的通信開銷很大。本方案的密鑰需求規(guī)模為常數(shù)級，且采用較小的編碼域，在編碼效率方面遠(yuǎn)高于文獻(xiàn)[5]。盡管在傳輸方面的帶寬開銷比文獻(xiàn)[7，10]略高，但比其他方案要低。此外，本文方案認(rèn)證帶寬開銷略高于其它抗污染方案，但相對于密鑰分配的通信量，這些額外開銷比例很低，可以忽略。

6 結(jié)束語

文中設(shè)計了一種適用于網(wǎng)絡(luò)編碼系統(tǒng)的高效抗污染和防竊聽方案。該方案異于傳統(tǒng)意義上的安全系統(tǒng)的簡單組合策略（松耦合設(shè)計），致力于研究如何將最大距離可分碼的構(gòu)造與信源密鑰動態(tài)化技術(shù)相結(jié)合，實現(xiàn)了一種能保證多目標(biāo)安全需求的融合策略。與現(xiàn)有簡單組合方案相比，該方案在編碼效率上獲得了較大的性能增益，同時在綜合性能上也具有突出優(yōu)勢。

文中初步探究了如何利用傳統(tǒng)編碼技術(shù)實現(xiàn)網(wǎng)絡(luò)編碼多目標(biāo)安全融合機(jī)制，在一定程度上提升了系統(tǒng)性安全的實現(xiàn)效率。同時，這也為當(dāng)前網(wǎng)絡(luò)系統(tǒng)安全機(jī)制的最優(yōu)組合設(shè)計提供了一種新的方法思路，具有重要的參考價值和研究意義。

參考文獻(xiàn)：

[1]Bassoli R，Marques H，Rodriguez J，et al.Network coding theory:A Survey[J].IEEE Communications Surveys&Tutorials，2013，15（4）:1950-1978.

[2]Matsuda T，Noguchi T，Takine T，et al.Survey of network coding and its applications[J].IEICE Transactions on Communications，2011，94（3）:698-717.

[3]Talooki V N，Bassoli R，Lucani D E，et al.Security concerns and countermeasures in network coding based communication systems:A survey[J].Computer Networks，2015（83）:422-445.

[4]Huang W，Ho T，Yao H，et al.Rateless resilient network coding against byzantine adversaries[C]//Proceedings of the IEEE Conference on Computer Communications（INFOCOM） ， Turin:IEEE Press，2013:265-269.

[5]Jiang Y X，Zhu H J，Shi M H，et al.An efficient dynamic-identity based signature scheme for secure network coding[J].Computer Networks，2010，54（1）:28-40.

[6]Li Q M，Lui J，Chiu D-M.On the security and efficiency of content distribution via network coding[J].IEEE Transactions on Dependable and Secure Computing，2012，9（2）:211.

[7]Liu G J，Wang X.Homomorphic subspace MAC scheme for secure network Coding[J].ETRI Journal，2013，35（1）:173-176.

[8]Li Y，Yao H，Chen M，et al.RIPPLE Authentication for network coding[C]//Proceedings of The IEEE Conference on Computer Communications（INFOCOM），San Diego:IEEE Press，2010:1-9.

[9]Wu X H，Xu Y L，Yuen C，et al.A tag encoding

scheme against pollution attack to linear network coding[J].IEEE Transactions on Parallel and Distributed Systems，2014，25（1）:33-42.

[10]Liu G J，Wang B.Secure network coding against intra/inter-generation pollution attacks[J].China Communications，2013，10（8）:100-110.

[11]Kim M J，Médard M，Barros J.Algebraic watchdog:mitigating misbehavior in wireless network coding[J].IEEE Journal on Selected Areas in Communications，2011，29（10）:1916-1925.

[12]Lima L，Gheorghiu S，Barros J，et al.Secure network coding for multi-resolution wireless video streaming[J].IEEE Journal on Selected Areas in Communications，2010，28（3）:377-388.

[13]Liu G J，Liu X M，Xiong J B，et al.A lightweight secure network coding scheme against wiretapping[J].Wuhan University Journal of Natural Sciences，2014，19（2）:156-160.

[14]Fan Y F，Jiang Y X，Zhu H J，et al.Network coding based privacy preservation against traffic analysis in multi-hop wireless networks[J].IEEE Transactions on Wireless Communications，2011，10（3）:834-843.

[15]Zhang P，Lin C，Jiang Y X，et al.A lightweight encryption scheme for network-coded mobile ad hoc networks[J].IEEE Transactions on Parallel and Distributed Systems，2014，25（9）:2211-2221.

[16]Cheng F，and Yeung R.W.Performance bounds on a wiretap network with arbitrary wiretap sets[J].IEEE Transactions on Information Theory，2014，60（6）:3345-3358.

[17]Liu G J.Practical schemes for tunable secure network coding[J].KSII Transactions on Internet and Information Systems，2015，9（3）:1193-1209.

[18]Guo Q，Luo M，Li L，et al.Secure network coding againstwiretapping and Byzantine attacks[J].EURASIP Journal on Wireless Communications and Networking，2010:17.

[19]Yao H，Silva D，Jaggi S，et al.Network codes resilient to jamming and eavesdropping[J].IEEE/ACM Transactions on Networking（TON），2014，22（6）:1978-1980.