WSN中基于指数算法的互愈组密钥分配方案∗

代紫梦 王方伟，2 王长广，2

（1.河北师范大学信息技术学院 石家庄 050024）（2.河北省网络与信息安全重点实验室 石家庄 050024）

1 引言

无线传感器网络采用微型传感器节点采集信息，各节点之间具有自组织和协同工作的能力，而且在网络内部采用无线多跳通信方式，因而具有精确度高、灵活性强、可靠性高、性价比高的优势。能够实现单一的传感器无法实现的密集空间采样及近距离监测功能，而且一经部署无需人为干预，可以避免单点失效问题。无线传感器网络在实际应用中发挥了十分重要的作用，但是由于节点由电池供电，资源受限，导致无线传感器网络面临安全威胁［1］。数据包丢失是其中不可避免的一个问题。在无线网络通信中，密钥更新消息可能无法到达一个指定节点，这样，该节点就不能正常参与小组通信。最直接的解决办法就是要求组管理器（Group Manager，GM）重新传输［2］，但是随之而来的就是网络通信负担的加重，占用较多的通信资源，甚至会造成网络阻塞。

Staddon等提出的自愈组密钥分配方案，在一定程度上解决了由于无线传感器网络的不可靠性而带来的上述问题，这也是自愈组密钥分配方案首次被提出［3］。在此机制中，由GM在广播消息中添加冗余信息，丢失会话密钥的节点能够根据冗余信息自主恢复密钥，不需要GM重新进行传输，这降低了通信开销，也降低了流量分析攻击的风险［4］。

在第一个自愈组密钥分配方案提出之后，陆续的又有更多方案被提出，目前，一共存在四种自愈组 密 钥 分 配 方 案［5～7］：基 于 多 项 式 的 SGKD（P-SGKD）方案，基于指数算法的SGKD（E-SGKD）方案，基于双线性配对的SGKD方案，基于向量空间的秘密共享SGKD方案。相比较而言，前两种方案存储开销和通信开销成本低，因此研究价值大。Blundo等提出了具有较少节点存储器的高效SGKD方案，以及改进的自愈机制，节点可以从广播中恢复丢失的会话密钥。Dutta［8］等提出了基于访问多项式的自愈组密钥恢复方案，在这些方案中使用的秘密多项式是恒定的，有效地将存储开销降低到常数，但同时也带来了安全性问题。近来，一些基于单向哈希链的自愈组密钥分配方案被提出［9］，但是有学者指出，大部分方案也不能抗共谋攻击［10～11］。

E-SGKD方案是基于P-SGKD方案的扩展，有学者指出大部分P-SGKD方案都可以转换成为E-SGKD 方案［12］。Staddon等首次将提出的P-SGKD方案转换为E-SGKD方案，随后Blundo等基于拉格朗日插值公式提出了新的E-SGKD方案，并简化了Staddon等的方案，但是此种方案没有保证后向保密特性。

而且，当节点丢失最后一次的密钥更新包时，无法利用已知的E-SGKD方案进行修复，Tian［13］等提出的互愈组密钥分配方案很好地解决了这一问题，在这一方案中在丢失最后一次的密钥更新后借助邻居节点来达到互助修复的目的，而节点仍然自我修复最后一次会话之前丢失的密钥更新包。但是这一方案只能在固定的传感器网络中发挥作用，无法完成无线传感器网络中的节点互助修复。

本文基于多项式的自愈组密钥分配方案进行转换，提出了一种基于指数算法的互愈组密钥分配方案，使用拉格朗日插值法进行设计，在降低通信开销的基础上，保证前向保密、后向保密以及抵抗共谋攻击。

2 基本模型

2.1 网络模型

为了更好地说明本方案，首先给出网络模型的一般介绍。在网络模型中通信组由一个GM和n个成员节点组成，n是由GM选择的，表示组中所有成员节点的总数。规定U是节点成员的集合，U={U1,U2,…,Ui…Un}，为每个节点分配身份ID号 si（0＜i＜n+1,n∈Z+）。规定G是所有会话的集合，Gj表示第 j次会话时通信组中所有合法成员节点集合，j是会话标识符。Kj表示由GM独立选择的会话密钥，Bj表示在会话期间GM发送的广播消息，当Ui在第 j次会话加入通信组时，GM通过安全信道为其发送私钥Si，每个节点使用私钥Si和广播消息Bj共同计算会话密钥Kj。为了方便后续描述，在表1中给出符号含义。

表1 符号含义

2.2 安全模型

为了更好地描述本文方案，使用安全模型来量化一些安全属性。

定义1（λ-撤销功能）如果对于Gj中的任何合法节点，Kj不能由广播消息Bj或者节点私钥Si单独确定，而是需要Bj和Si共同计算；且当Rj表示第 j次会话之前被撤销的节点集合，在集合中的节点都不能获取Kj的信息，而对于任意的Ui∉Rj都能够获取Kj的信息，那么该方案具有λ-撤销功能。

定义2（自愈功能）如果对于任意的会话 j，存在1≤j1≤j≤j2≤m ，节点Ui是会话 j1和 j2中的合法成员，且Ui丢失了会话 j中的密钥更新包，若它可以借助广播消息Bj1和Bj2恢复会话 j的密钥Kj，则该方案具有自愈功能。

定义3（互愈功能）如果对于任意节点Ui丢失了最后一次会话m的密钥更新包，它可以求助合法邻居节点Ui'来进行修复，如果通过邻居节点发送的消息能够恢复出最后一次的会话密钥，则该方案具有互愈功能。

定义4（λ-前向保密）R表示在会话 j及 j之前所有被撤销节点的集合，|R|≤t，如果R中的节点无论是单独或者共谋都无法获得Kj，则该方案具有λ-前向保密特性。

定义5（λ-后向保密）J表示第 j次会话之后加入的所有新节点的集合，|J|≤t，如果每个属于J的节点都不能获得会话密钥Kj11≤j1≤j，且即使共谋也无法获得，则该方案具有λ-后向保密特性。

定义6（抗λ-共谋攻击）Rj1表示在会话 j1之前和会话 j1被撤销的节点集合，Jj2表示在会话 j2之后加入的节点集合，其中 j1≤j≤j2，如果 Rj1和Jj2中的节点共谋无法获得会话 j的密钥Kj，则该方案具有抗λ-共谋攻击。

3 基于指数算法的MGKD方案

3.1 工作流程

组通信的生存期被划分为不同的会话，为了保证通信安全，在整个生存期中需要不断更换会话密钥，其中每个会话都有唯一的组密钥。GM通过广播密钥更新消息将新的会话密钥Kj分配给Gj中的节点，具体流程如图1所示［14～15］。

图1 工作流程图

3.2 方案描述

在本方案中主要包括五个步骤：初始化、广播、会话密钥自修复、会话密钥互助修复、节点加入和撤销。

1）初始化

GM从有限域Fq（q是大素数）中随机选择t次多项式 f(x)=a0+a1x+a2x2+...+atxt和 εj，其中j∈[1,m]。使用εj.f(si)来隐藏节点私钥，提高其保密性，这样Ui的节点私钥构造为Si={si,εj.f(si)}，GM通过安全信道为在会话 j加入的节点Ui分发节点私钥。

2）广播

从有限域Fq中随机选择k1（0＜j≤m）用来隐藏组会话密钥，进行如下计算：

GM从有限域中随机选择∂i和θj1，二者皆不能是节点的身份标识，使用节点身份构造如下多项式：

然后GM进行如下计算：

GM构造广播消息Bj，主要包含以下内容：

3）组密钥自修复

利用式（5）进行如下计算：

如果Ui是Gj1中的合法节点，则 Aj1(si)=0，否则Aj1(si)为随机值，即kj1≠ kj1-1·Hj-1()。

对于会话 j2（ j1≤j2≤j），节点Ui可以利用式（1）、（2）共同计算，得到 kj2，然后利用式（7）中的加密函数Ek(·)进行计算得到Kj2。

4）会话密钥互助修复

如果节点Ui丢失了最后一次会话m的密钥更新包，它可以求助合法邻居节点Ui'来修复密钥，主要包括以下三个步骤：

步骤一：发送请求消息

节点Ui在时间ti向节点Ui'发送请求消息，表示需要能够得到最后一次的密钥更新包；

步骤二：回复消息

节点Ui'在时间ti'

收到请求消息之后，首先判断|ti'-ti|≤Δt是否成立；

如果不成立，则不回复Ui的请求消息，因为时间过于久远；

如果成立，则向节点Ui发送自己的ID号i'和广播消息Bm。

步骤三：恢复密钥

节点Ui收到节点Ui'回复的消息之后，利用式（7）、（8）计算得到最后一次的会话密钥。

5）节点加入和撤销

如果一个节点Ui在会话 j-1加入通信组，那么GM通过安全信道秘密为其传送身份ID号si和节点私钥Si={si,εj-1.f(si)}。

如果一个节点Ui在会话 j1时加入，在会话 j时撤销，那么GM将(x-si)从Aj1(x)中剔除。

为了保证通信安全，在有节点加入和撤销之后，GM都会重新开始一个会话并重新构造广播消息。

4 性能分析

4.1 安全性能分析

定义1（λ-撤销功能）

证明 假设Ur∈R，且0≤r≤t，对于任意的Ur，因为Aj1(x)为任意值，因此无法从广播消息中恢复kj1，进而无法得到Kj，且由于从有限域中选择的 f(x)是t次多项式，因此被撤销节点若要共谋得到 Kj，则最少需要有t+1个节点，而0≤r≤t，因此具有λ-撤销功能。

定义2（自愈功能）

证明 会话组中的合法节点当丢失会话密钥之后不需要GM重新传输密钥更新包，而是会根据GM发送的广播消息和节点私钥进行计算，然后利用加密函数Ek(·)得到所丢失的会话密钥，因此具有自愈功能。

定义3（互愈功能）

证明 任意节点Ui丢失了最后一次会话m的密钥更新包，能够通过合法邻居节点发送的消息恢复出最后一次的会话密钥，而不需要GM重新传输，因此该方案具有互愈功能。

定义4（λ-前向保密）

证明 对于任意节点Ur∈R ，且0≤r≤t，若要恢复组密钥则需要，但是因为Ur是非法节点，则Aj1(sr)为任意值，因此Ur无法单独获取与密钥恢复相关的信息，而且被撤销节点的共谋需要至少t+1个节点才能恢复εj.f(x)，因此该方案具有前向保密特性。

定义5（λ-后向保密）

证明 对于J（J⊆U）中的所有节点，若想恢复Kj1

，则需要恢复εj1.f(x)，而 f(x)是t次多项式，因此需要至少t+1个节点，由于|J|≤t，即无法通过共谋恢复εj1.f(x)，也就证明了该方案保证了后向保密特性。

定义6（抗λ-共谋攻击）

证明 令Rj1表示会话 j1之前被撤销的节点集合，Jj2

表示在会话 j2之后加入的节点集合，且存在 j1＜j2，|Rj1∪Jj2|≤t，Rj1∩Jj2=Ø。令Ui表示在会话 j'加入的节点，令Ur表示在会话 j''撤销的节点，存在 j2＜j'，j''＜j1，因此 Ui能够得到εj'.f(si)，Ur能够得到 εj''.f(si)，而由于Ui和Ur是两个不同的会话，即无法通过共谋来获取有关 f(x)的信息，也就无法获得密钥Kj，因此该方案具有抗共谋攻击能力。

4.2 存储开销与通信开销

在本方案中，存储开销是2log2p，表2中各方案存储开销对比，展示了本方案与其他文献中的方案在存储开销方面的对比。

表2 各方案存储开销对比

在本方案中通信开销为[max{(t+1)v+j,|Gj|+3v+j}]log2p+log2q（1≤v＜j≤m），这主要是来源于广播包中的t次多项式。其中， ||Gj代表Gj中的节点总数，v代表在会话 j之前有新加入节点的会话数，m表示最大会话数。设m=50，t的取值为10到50，q为128bit，表3各方案通信开销对比所示为各方案通信开销对比。

表3 各方案通信开销对比

图2 广播包大小

图2 广播包大小所示为广播包大小随t值的变化情况，本文方案与文献［10］中的方案进行了对比，可见本文方案小于文献［10］中的方案。

图3 m和t的对比

图3 进一步验证了组管理器支持的最大会话数m和能够删除的最大节点数t之间的关系，并与文献［4］Blundo C等的经典方案进行了比较，假设广播消息量最大是64KB。

5 结语

本文针对现有的组密钥分配方案中存在的问题做出了改进，提出了新的基于指数算法的互愈组密钥分配方案。经仿真实验验证和性能分析，该方案具有λ-撤销功能、自愈功能、互愈功能、λ-前向保密特性、λ-后向保密特性以及抗λ-共谋攻击，能够适用于无线传感器网络。