一种高效的防窃听和抗污染的安全网络编码方案

刘光军

（西安文理学院信息工程学院，陕西西安710065）

网络编码能有效提高网络的吞吐量和安全性，增强网络的健壮性和稳定性，降低网络的能耗，具有重要的理论和潜在应用价值[1-3]。但是，网络编码传输具有信息融合的特性，致使其容易遭受污染和搭线窃听攻击。当前，设计高效的抗污染和防窃听策略是当前网络编码领域中的重要研究热点。

文献[4]首次从信息理论意义上考虑了网络编码传输中的抗污染检测问题，但该方案通信开销极大。后来出现的较实用的安全方案大部分结合同态密码学的代数性质，并能有效地整合网络编码的传输特性，代表性方案包括基于同态签名的方案[5]，基于同态Hash的方案[6]，基于同态MAC的方案[7]和基于推迟分发密钥的策略[8-9]。这类方案虽然实现了对被污染数据包实时过滤功能，但基本上都不能有效解决共谋以及代间污染问题。虽然文献[10-11]可以有效解决这种问题，但它们却存在着计算复杂度过高和通信开销过大、网络拓扑依赖的问题。

与此同时，对防窃听方面的研究也取得了一些较突出的工作成果。文献[12-14]利用代数安全预编码技术实现了对全局编码信息的保护，有效阻止了攻击者对机密内容的析取和网络流量的分析。文献[15]提出了P-Coding方案。Cheng等[16]利用信息不等式，给出了P2P网络任意信道子集被窃听时的安全网络编码构造。进一步地，笔者在文献[17]利用纠错编码的系统构造方法，提出一种具有安全可度量属性的编码方案。然而，现有的这些研究工作只是片面地考虑了抗污染问题。

综上所述，现有研究不仅普遍存在着通信效率不高、安全性能不足的共性问题，而且由于大部分方案只关注单一安全目标的实现，难以适应网络编码多目标安全通信场景中的安全应用，因而缺乏一种对多种安全功能的系统性设计策略。虽然文献[18-19]中同时考虑了抗污染和防窃听问题，但综合性能很不理想。这些基于信息论的方案都需要一个充分大的编码域，致使其付出了高昂的通信开销和计算代价，而且难以抵御代间污染攻击。

文中首先利用最大距离可分码的系统构造技术来实现网络安全码，然后给出一种逐代动态变化的代数密钥分配机制。借助于这种密钥更新策略，本文设计了一种高效的网络编码多目标安全通信需求中的系统化安全方案，有效克服了多种安全机制的简单组合（松耦合）设计的低效性。

1 网络与攻击模型

文中考虑单源无圈网络中网络编码传输情形。信源首先把信源消息进行预编码，生成一个由连续的代序列组成的信息流。在下文中，统一采用文献[1]中的随机网络编码协议模型。在传输中，各代消息均用不同的标识符来标记。每代消息用一个定义在有限域Fq上的符号矩阵来表示。这里|Fq|=q。

假设信源是可信实体，且攻击者的计算资源有限，即攻击者最多能执行概率多项式时间的攻击算法。攻击者可以监控网络传输中的所有消息，并可以从中析取有价值的机密信息。同时，它可实时地在网络各处注入经过伪造或篡改的污染消息，试图使其最终能通过检验节点的合法验证。网络攻击者可能来自网络内部或外部的一个或多个实体，也可与网内的节点进行共谋。

2 基本方案

为简单起见，本文只描述网络编码系统对一代消息的安全通信处理过程。

令该代消息的标识符为id，信源将其扩展编码为符号矩阵

2.1 系统配置

KDC给信源秘密发送t个随机向量且矩阵可逆。对于其它非信源节点，KDC也给其秘密发送一个随机向量，计算其私有密钥并发送给该节点，其中

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

2.2 信源编码

步骤1：信源us利用f1、f2生成两个公开向量：

步骤3：信源利用向量a和b，计算生成两个Vandermonde矩阵At×(m+n)和Bm×m，其第i行分别为和；

步骤4：信源生成其私有密钥

计算并构造矩阵

这里r=(ε1,ε2,...,εm)，其中ε1=Ek(b1)，其余的εi均为Fq中的随机数。

步骤5：信源计算代认证信息

在此阶段中，信源采用了构造最大距离可分系统码的思想，结合代消息标记的动态性，利用两个Vandermonde矩阵对信源信息代进行线性编码，同时实现了通信的机密性和对信源消息的合法性保护机制。

2.3 消息检测

步骤1：节点N利用id和us生成公开矩阵A，计算

是否成立。若成立，则该数据包合法；否则，将其丢弃。

2.4 信宿译码

合法的信宿收到足够多的代id的数据包后，将借助于相应的全局编码信息使用高斯消元法解出消息矩阵D。然后，它通过解密恢复b1并计算b′和矩阵B，进而解出代id的明文符号矩阵V。

3 方案合理性

进一步，根据公式（6）-（8），可知

故公式（6）成立。

4 安全性分析

4.1 抗污染安全性

如果在上述安全方案的运行过程中，一个攻击者可以构造一个消息向量且能通过某个节点ℕ的认证，即成立，则称该攻击者成功实施了一次污染攻击。

定理1：本方案可以容忍t-1个网内合法节点的共谋。

证明：假设当前共谋合法节点拥有的密钥对分别为 (e1,y1),(e2,y2),...,(eσ,yσ)。利用公式（7），这些恶意节点将要联立等式ei=yiK(i=1,2,...,σ)来推导信源密钥K。显然，当σ≥t时，矩阵将会以很高的概率可逆，从而能使这些节点恢复出信源密钥K。

为保证最大强度的安全性，下面的分析均考虑这种t-1个恶意节点共谋的最坏情形。

定理2：任何一个污染攻击者能成功地实施一次污染攻击的概率最多为。

证明：若上述t-1共谋者构造了一个非法的向量欲通过方案的认证检测，则必然要求其满足公式（6），从而可得如下等式

由此，可以讨论如下：

②若攻击者先给定w=w0，则关于hˉ的线性方程 组的解空间的维数为m+n-t+1。类似（a）中的讨论，即攻击者污染成功的概率最大也为。

定理3：对于代间污染攻击，该方案也是安全的。

证明：由于不同的代具有不同的id，故在认证过程中必然使用了不同的公开认证矩阵A=Aid。

任取代id1中的数据包，根据公式（5）（6），必有

攻击者在代id2的传输过程中，欲用数据包p1去污染代id2的信息。假设p1能成功污染代id2，则必有

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

对攻击者来说，向量c为随机向量，欲使公式（13）成立，必需使。这显然与前述矛盾。

由于矩阵A的生成依赖于各代标识符，不同代消息在传输时都将使用不同的矩阵A，这将保证信源认证密钥的动态性，而这种动态性使得方案具有抗代间污染的能力。

4.2 防窃听安全性

信源编码步骤4中公式（3）是笔者在文献[17]中的方案2的特例，故定理4的证明方法与文献[17]中的思路相同。

定理4：针对任意具有多项式计算能力的窃听者，该方案都不可能泄露信源明文消息的任何有意义信息。

步骤4和5中都涉及到了Vandermonde矩阵的乘法，其在实现防窃听和抗污染安全功能中发挥了关键性作用。矩阵B实现了信源明文向量的随机混淆，窃听者在通信过程中不能完整地构造矩阵B，故任意窃听者都无法恢复信源机密消息。对于不同的代消息，方案在矩阵B的构造中实时引入了随机参数b1，可以保证多代通信的安全性。此外，矩阵A实现了消息向量之间的充分组合，确保了方案抗污染的能力。

5 方案性能评价

5.1 计算开销

方案运行过程中主要计算操作是矩阵的乘法运算。下面将以乘法计算量来分析各阶段的计算开销。

1）信源认证编码

步骤1和2中的计算开销较小，故可忽略。由于矩阵B的使用与代标识符无关，故步骤3中的计算量主要来自于构造矩阵A，其计算量为t(m+n-1)。步骤4需要执行一次加密运算以及构造矩阵K和D，其总计算量为t2(m+n)+m2(n-1)。步骤5的乘法计算量为mt(m+n)。由于t＜m，故该阶段总的计算复杂度为O(m2(m+n))。进一步地，利用Vandermonde矩阵乘法的优化计算技术，可以将该复杂度进一步降低为O(m(m+n)log2m)。

2）消息检测

该阶段每个认证节点需要执行一次PRF操作、矩阵构造和等式判别运算，其计算复杂度为O(t2(m+n))。

3）信宿译码算法

信宿节点需要对接收消息进行验证，复杂度为O(t2(m+n))。信宿节点译码需要执行高斯消元运算，其计算开销来自于网络编码协议运行本身，故可以忽略。

综合而言，方案总体运行计算复杂度为O(m(m+n)log2m)。

5.2 带宽开销

该方案除了为传输全局编码信息所带来的带宽开销m（网络编码协议运行本身所决定）外，付出的通信开销为t（用于各数据包认证信息的传输），故方案的有效传输容量达到n-m-t，与现有方案相当。

5.3 方案比较

表1将本方案与一些有代表性的单安全目标方案进行比较，如下所示。

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

文中提出的方案有效地实现了防窃听和抗污染两种安全性能，并能很好地解决代间污染和节点共谋问题。相比之下，文献[12-17]仅关注于网络防窃听的安全性能，没有考虑与当前抗污染方案的系统融合设计。除此之外，表1中部分方案虽然实现了抗污染安全功能，但这些方案仅能实现点对点的污染检测能力，且存在代间污染问题。

其次，与现有单安全目标方案相比，本文方案没有显著增加在信源编码和节点认证方面的计算复杂度。从表1看出，本文方案的编码效率仍然具有一定的优势。虽然仍有个别其它方案的信源编码复杂度较小，例如文献[8]，但这种效率上的优势却是以安全强度的降低换来的。

再者，为了在保证效率和安全强度的前提下同时实现防窃听和抗污染功能，现实可行的策略只能将这些单安全目标机制进行简单的组合设计。实验证明，这种方法运行的计算开销将大大高于本文方案。我们通过Matlab R2010a平台利用Intel Core2-2.80 GHz处理器对本文方案（记为S0）与现有可有效实现的组合方案的信源编码时间性能进行测试对比。对比方案选择文献[7，17]的组合方案（基于对称密码体制，记为S1，文献[17]中仅采用方案2）以及文献[5，13]的组合方案（基于混合密码体制，记为S2）。这种选择的原因在于这些方案组合运行中具有突出的低编码复杂度。测试参数取m=20，n=1024。方案S1和S2中的编码域分别取q=216和q=397。在编码过程中，数据的加解密操作均采用AES算法。

图1 方案信源编码时间测试对比

图1给出了在信源待传输消息代序列规模数量逐渐增大的情况下，方案S0，S1和S2信源编码时需要的时间开销t（单位：秒）与代序列规模呈正比例关系。这种线性特征最合理的解释是每种方案对各代消息的处理时间相同。测试结果验证了本文方案的性能优势。由于方案S2的设计基于公钥密码体制，其实现依赖于较大的编码域，导致了该方案的编码时间将会远高于其它两个基于对称密码体制的方案S0和S1。进一步地，由于文献[7]在运行中需要不断地更新密钥，其信源编码时间必然多于本文方案。

最后，为了达到与本方案同等的安全性，文献[7，8，10]中密钥分配及更新的通信开销将随消息代规模线性递增，导致这些方案的通信开销很大。本方案的密钥需求规模为常数级，且采用较小的编码域，在编码效率方面远高于文献[5]。尽管在传输方面的带宽开销比文献[7，10]略高，但比其他方案要低。此外，本文方案认证带宽开销略高于其它抗污染方案，但相对于密钥分配的通信量，这些额外开销比例很低，可以忽略。

6 结束语

文中设计了一种适用于网络编码系统的高效抗污染和防窃听方案。该方案异于传统意义上的安全系统的简单组合策略（松耦合设计），致力于研究如何将最大距离可分码的构造与信源密钥动态化技术相结合，实现了一种能保证多目标安全需求的融合策略。与现有简单组合方案相比，该方案在编码效率上获得了较大的性能增益，同时在综合性能上也具有突出优势。

文中初步探究了如何利用传统编码技术实现网络编码多目标安全融合机制，在一定程度上提升了系统性安全的实现效率。同时，这也为当前网络系统安全机制的最优组合设计提供了一种新的方法思路，具有重要的参考价值和研究意义。

参考文献：

[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.