传感器网络基于动态密钥池的密钥建立方案*

赵巾帼，周波清，朱凌志，李素君

（1.湖南工学院计算机与信息科学学院，湖南衡阳421002；2.湖南人文科技学院信息科学与工程系，湖南娄底417000）

传感器网络基于动态密钥池的密钥建立方案*

赵巾帼1，周波清2*，朱凌志1，李素君2

（1.湖南工学院计算机与信息科学学院，湖南衡阳421002；2.湖南人文科技学院信息科学与工程系，湖南娄底417000）

针对网络在整个生命周期内的可持续安全性问题，基于动态密钥池技术提出了一个新的对密钥建立方案（KES-D）。在此方案中，节点分n次部署，密钥池根据节点部署的次数分代。第i代密钥池由第i-1阶段的密钥池去除m条使用时间最长的二维反向密钥链再加上m条新二维反向密钥链组成。理论分析及模拟结果表明：与适用于多次部署的传感器网络密钥管理方案相比，该方案的抗毁密钥连通率显著提高。

传感器网络；密钥建立；动态密钥池；抗毁密钥连通率

在传感器网络中，单个节点的寿命一般远少于传感器网络的生命周期。为此，必须适时地向网络中添加节点。这样的网络也叫多次部署的传感器网络。同时，传感器网络通常被部署在户外甚至是敌对的环境中，较容易受到各种恶意的攻击［1-3］，凸显了安全问题的重要性。因此，提高由新、旧节点组成的传感器网络在整个生命周期内的安全性是必须解决的问题之一。为了提高传感器网络的安全性，近年来，相关学者提出了许多对称密钥管理方案［4-18］。

Durresi等人较早地注意到了传感器网络在整个生命周期内的安全性问题［8］。并提出了基于独立密钥池的密钥管理方案。在此方案中，相同阶段的节点通过E-G方案［4］或q-scheme［5］进行安全地通信，相邻阶段的节点通过桥节点进行通信。该方案虽然考虑了传感器网络的持续安全管理问题，但仍存在桥节点部署困难、抗毁性能较差等缺点。针对这些不足，Zhou等人基于部署知识和独立密钥池技术提出了一个新的密钥建立方案［9］，该方案能显著提高SCON方案的连通率和抗毁性。但此方案也存在扩展性能不佳，局部连通率下降过快等缺点。袁珽等人也提出了一个基于独立密钥池技术的方案［10］，与SCON方案的不同点是：部署前节点需从多个密钥池中选取密钥。此方案降低了SCON方案的部署难度和针对桥节点攻击的威胁，但增加了存储开销，且抗毁性也有所下降。

使用完全独立的密钥池技术，其抗毁性能显著提高。但是其局部连通率下降过快，最终可能导致全局连通率的下降。在Das所提的方案［11］中，密钥池被划分为两个的部分。第一阶段部署的节点同时从两个密钥池中选取密钥，后来部署的节点只从第二个密钥池中选取密钥。网络部署好后，第一阶段部署的节点一旦与邻居节点成功建立对密钥，就立即擦除来自第一个密钥池的密钥。与E-G方案［4］或q-scheme［5］相比，此方案在局部连通率保持不变的情况下提高了网络的可持续安全性。但是，此方案只适用于整个生命周期内以第一阶段部署的节点为主的传感器网络。对于其他情形，此方案将退化为E-G方案［4］或q-scheme［5］。Castelluccia等人提出了RoK方案［12］，此方案通过正向、反向密钥链技术构造局部关联密钥池。两节点如果存在共同的正反密钥链且代数之差不超过Gw，则可以建立共享密钥。针对多次部署的传感器网络，此方案增强SCON方案的连通率和DAS方案的抗毁性。但此方案存在如下缺陷：①由于存在正、反两个密钥池，节点的存储开销增加；②当敌手俘获较多的节点时，其正向密钥池失效。

Li和Zhou等人用一维反向密钥链和二维反向密钥链技术构建了全局关联的密钥池［13-15］。与Das方案相比，在节点存储开销相同的情况下，其局部连通率显著提高、抗毁性能显著增强。但是此方案随着在引导阶段妥协的节点数的增加，其抗毁性能下降较快。因此，提高网络在整个生存期内的抗毁性仍然是一个急需解决的问题。

本文针对传感器网络的可持续安全问题，提出了一个基于动态密钥池技术的密钥建立方案。在此方案中，密钥池分代，第i代密钥池由第i-1代密钥池中的密钥去除使用时间最长m条二维反向密钥链后再加入新的m条二维反向密钥链组成。第i次部署的节点只从第i阶段的密钥池中选取密钥。理论分析和模拟表明，与应用于多阶段的密钥管理方案相比，该方案的抗毁密钥连通率显著提高。

1 基于动态密钥池的密钥建立方案KES-D

1.1 网络及威胁模型

在本方案中，假设网络中的节点服从随机均匀分布，敌手随机地从网络中俘获节点。敌手在第i和第i+1次部署之间所有俘获行为都称为第i次俘获。假设敌手在第i次俘获中俘获的节点数为CNi，且一旦某节点被俘获，则此节点所携带的秘密信息敌手全部可知。但是，假设敌手在引导阶段俘获较少的节点。由于节点能够在引导阶段快速地建立与邻居节点的共享密钥，所以这一假设在传感器网络中是可行的，文献［11，13-15］同样使用了这一假设。

为了保持网络在整个生命周期内都能够正常的工作，当敌手俘获的节点数等于网络中节点总数的1/6时，需要向网络中部署新的节点。

1.2 二维反向密钥链

二维反向密钥链由一维反向密钥链和二维正向密钥链组成，其具体构造过程如下：

①一维反向密钥链的第i个密钥由如下方式产生：

在上述过程中，H1和H2为两个相互独立的Hash函数，如图1所示。由于第二维密钥链中的密钥可由相应的第一维密钥链中的密钥生成。如可以生成密钥（i1≤i,1≤l1≤L）。为了便于描述，第一维密钥称为生成密钥，第二维密钥称为普通密钥。

图1 二维反向密钥链

1.3 钥池的构造过程

密钥池划分为多代。第一代密钥池由M条二维反向密钥链及其身份标识组成。第i（i＞1）代密钥池由以下规则生成：①从第i-1代密钥池中去除使时间最长且密钥链ID最小的m条密钥链；②将剩余的M-m条密钥链中的密钥更新至下一代；③新加入m条密钥链第1代密钥。原密钥池替换成全新密钥池所需的代数为：

在本文中，假设M能被m整除。

由于密钥链中的密钥分为生成密钥和普通密钥。因此，第i代密钥链也分为生成密钥池和普通密钥池由如下密钥构成：

1.4 钥预分配信息

1.5 建立阶段

节点部署好后，通过广播自己密钥环中密钥的身份标识来建立相邻节点之间的共享密钥。在KES-D方案中，共享密钥建立结束后，密钥环中的第t个密钥kt（1≤t≤t1+t2）都经过如下Hash处理：，其中为节点ai的身份标识。下面以i1代的节点和i2代的节点为例来讲解密钥建立过程。

当i1=i2时，如果它们之间存在x（0≤x≤t1+t2）个共同密钥，则它们之间的共享密钥可以分为两部分（如图2（a）所示）：①x1个共同的生成密钥（来自生成密钥池）和x4个共同的普通密钥（来自普通密钥池）；②x2+x3个共同的普通密钥（来自普通密钥池）。不过这些密钥必须通过计算才能得出。下面详细地讲解这些共享密钥的计算过程：假设节点预分配了这些共同密钥链的如下密钥：，则节点必须预分配如下密钥使用1.2节所示的方法，和可以快速地计算出它们之间的共同的普通密钥：

当i1≠i2时，不失一般性，假设i1＞i2。在KES-D方案中，密钥池经过N代替换后全部进行了更新，因此，只有当i1-i2＜N，它们才有可能建立共享密钥。当i1-i2＜N时，假设它们之间存在x（0≤x≤t1）个共享密钥，则它们之间的共享密钥可以分为两部分（如图2（b）所示）：①x1个经过Hash处理过的生成密钥。假设这些生成密钥为：则这些密钥已经存储在中，同时节点必须预分配了这些共同密钥链的生成密钥；。使用1.2节所示的方法，ai1可以快速地计算出如下生成密钥：再通过Hash处理，即可以得出与节点的共享密钥；②x2个经过Hash处理过的普通密钥。其计算过程简要描述如下：首先通过共享的生成密钥计算出预分配给的普通密钥，然后通过Hash运算即可计算出它们之间的共享密钥。

图2 . 享密钥构成图

1.6 径密钥建立阶段

本方案路径密钥可以使用文献［4-5，11］中的方法建立。两个不能直接共享密钥的节点必须寻找一条连接这两个节点的密钥路径（密钥路径上的任意两相邻节点都已建立好共享密钥）。然后，其中一个节点产生一个随机密钥K，并将K通过这条密钥路径安全地发送给另一个节点。

2 能分析及模拟

定义1 相邻节点如果节点a和b都在对方的通信范围内，则称a和b为相邻节点。

定义2 局部连通率（local connectivity）网络中任意两相邻节点能够建立共享密钥的概率。

定义3 抗毁性（resilience）没有被俘获的相邻节点之间的对密钥被破译的概率（在本文的模拟过程中，没有考虑路径密钥被破译的概率）。

在这次模拟仿真中，KES-D主要参数设置如下：①第一次部署节点数为1 200，后续每阶段部署的节点数为200；②部署的区域为500×500；③敌手每次从网络中随机俘获的节点数为200；④密钥池中二维反向密钥链的条数为5 000（M=5 000）。在每条密钥链，第二维正向密钥链的长度为20（L=20）；⑤节点预分配的密钥数为100（t1+t2=100）；⑥部署的总次数为3，即n=3。

2.1 能够建立对密钥的概率

在KES-D方案中，两相邻节点能建立对密钥的概率与它们之间的部署代数有关。下面以为例详细地分析对密钥建立的概率。

当i1=i2时，建立对t1密钥的概率公式为：

当i1-i2≥N时，ai1和bi2能够建立对密钥的概率公式为：

2.2 KES-D性能模拟

在KES-D方案中，密钥池由生成密钥池和普通密钥池组成。从前面的分析可知，对于任意生成密钥，都可以生成i×L个普通密钥（1≤i′≤i， 1≤l≤L）。因此增加t1比增加t2更有利于局部连通率的提高。在图3中，t1+t2=100，t2的值随着t1的增加而减少，其局部连通率增加的事实验证了上述结论的正确性。

在KES-D方案中，假设在引导阶段妥协的节点数用CC表示。由于KES-D方案的密钥池由二维反向密钥链组成，而二维反向密钥链的第i代生成密钥可以生成i×L个普通密钥。因此，随着t1、 CC和阶段数的增加，节点因妥协而泄露的密钥信息也就显著增加。因此，KES-D的抗毁性能随着t1和阶段数的增加而下降。如当m=1 000，CC=30时，t1从30增加到50时，在第3阶段，没有被妥协的节点间建立的对密钥被破译的概率从0.27升高到0.37。

在KES-D方案中，在第一阶段后，其密钥池都用新的m条二维反向密钥链替换掉前一阶段使用时间最长、ID最小的m条二维反向密钥链。假设第i阶段和第i′（不失一般性，假设i≤i′）阶段存在共同密钥链组成的集合用 SCi-i′表示。为此，可以得出：

从式（5）可以得出，两相邻两节点能够建立对密钥的概率随着节点相差阶段数的增加而降低、随着m的增加而降低。如图3所示，当m=1 000，t1=50时，第1阶段到第3阶段的局部连通率分别约为：0.79、0.72、0.66；当t1=50时，m从1 000增加到2 000，第3阶段的局部连通率约下降了0.088。

图3 局部连通率与m、t1和t2之间的关系

假设第i阶段和第i′阶段不相同的密钥链组成的集合用NSCi-i′表示。当第i阶段部署的节点u和v使用中的密钥建立共享密钥时，妥协第i′阶段的节点不能破译u和v建立的共享密钥。从式（5）可以得出：

图4 抗毁性与m、t1和t2之间的关系

2.3 性能比较

在这次模拟中，RoK方案［12］和Li方案［13］密钥池的大小与KES-D方案相同，但在KES-D方案中，每阶段替换的二维反向密钥链的条数为2 000（m=2 000）。第i阶段部署的节点，预分配如下密钥：在RoK方案中，节点分别从第i阶段的正向密钥池和反向密钥池分别选取50个密钥；在Li和KESD方案中，节点分别从第i阶段的生成密钥池和普通密钥池分别选取50个密钥，即t1=t2=50。其他参数与图3和图4相同。

在RoK方案中，由于同时存在正、反密钥池，节点需要从这两个密钥池中选取数目相同的密钥，在三个方案存储开销和每个密钥池大小相同的条件下，RoK方案的局部连通率最低，如在第三阶段，其局部连通率约为0.17。KES-D中，相差I（I≤N）代的密钥池存在共同的密钥链的数目为M-m×I。因此，这个方案的局部连通率随着部署代数的增加有所下降。但其局部连通率远高于RoK方案。如在第三阶段，其局部连通率约为0.57。在Li方案中，每个阶段的密钥链不变，因此其局部连通率随着部署阶段的增加下降较慢。从图5可以得出，在第一阶段Li方案和KES-D方案的局部连通率相同，但在第三阶段，Li方案的局部连通率要好于KES-D方案。

RoK方案想通过双向密钥池来提高多阶段部署的传感器网络的安全性能。但是当妥协的节点较多时，其正向密钥池将失效。如当CC=50时，节点之间通信密钥被破译的概率与KES-D基本相同。在Li方案中，由于每阶段的密钥链保持不变，随着引导阶段俘获节点数的增加，其抗毁性能显著下降。如当CC=50时，在第1阶段和第3阶段，节点之间通信密钥被破译的概率分别约为0.24和0.64。

图5 RoK、Li和KES-D三方案的局部连通率对比

为了考察一个方案的综合性能，Gu等人提出了一个新的评价指标［16］：抗毁局部连通率，即，其中分另表示第i阶段的局部连通率和第i阶段共享密钥被破译的概率。这一参数比单一的局部连通率或抗毁性更有实际价值。因为如果一个方案的局部连通率很高，但是节点之间建立共享密钥基本上被破译，这个方案也就失效了。由图5和图6可以导出抗毁局部连通率的对比示意图（如图7所示）。RoK方案虽然具有较好的抗毁性，但是由于其局部连通率很低，因此其抗毁局部连通率最低。如当CC=50时，在第3阶段，其抗毁局部连通率约为：0.1。KES-D方案由于使用了动态密钥池，其局部连通率随着部署阶段的增加比Li方案下降得更快，但是，其抗毁性远好于Li方案。当CC较大时，其抗毁局部连通率明显好于Li方案。如当CC=50时，在第3阶段，Li方案和KES-D方案的抗毁密钥连通率分别为0.26和0.34。

图6 RoK、Li和KES-D三方案的抗毁性对比

图7 RoK、Li和KES-D三方案的抗毁局部连通率对比

3 结论

针对传感器网络的可持续安全问题，提出了一个基于动态密钥池的密钥建立方案。同时，也详细地分析了密钥预分配参数、密钥池更替参数与局部连通率和抗毁性能之间的关系。与应用于多阶段的密钥管理方案相比，该方案的抗毁密钥连通率显著提高。

［1］Wood A，Stankovic J.Denial of Srvice in Snsor Ntworks［J］.IEEE Computer Magazine，2002，35（10）：54-62.

［2］Karlof C，Wagner D.Secure Ruting in Wreless Snsor Ntworks：At⁃tacks and Cuntermeasures［C］//Proc IEEE International Work⁃shop on Sensor Network Protocols and Applications，2003.

［3］Perrig A，Szewczyk R，Tygar J D，et al.SPINS：Security Potocols for Snsor Ntworks［J］.Wireless Networks，2002（8）：521-534.

［4］Eschenauer L，Gligor V D.A Ky-Management Sheme for Dstribut⁃ed Snsor Ntworks［C］//Proc ACM CCS，2002：41-47.

［5］Chan H，Perrig A，Song D.Random Ky Pedistribution Shemes for Snsor Ntworks［C］//Proc IEEE S&P，2003.

［6］Du W，Deng J，Han Y S，et al.A Key Management Scheme for Wire⁃less Sensor Networks Using Deployment Knowledge［J］.IEEE Trans on Dependable and Secure Computing，2006，3（1）：62-77.

［7］Bechkit W.New Ky Mnagement Shemes for Rsource Cnstrained Wreless Snsor Ntworks［C］//Proc IEEE WoWMoM，Lucca，Italy，2011.

［8］Durresi A，Bulusu V，Paruchuri V.SCON：Secure Mnagement of Cntinuity in Snsor Ntworks［J］.Computer Communications，2006，29（13-14）：2458-2468.

［9］Zhou B，Li S，Li Q，et al.An Efficient and Scalable Pairwise Key Pre-distribution Scheme for Sensor Networks Using Deployment Knowledge［J］.Computer Communications，2009，32（1）：124-133.

［10］袁珽，马建庆，钟亦平，等.基于时间部署的无线传感器网络密钥管理方案［J］.软件学报，2010，21（3）：516-527.

［11］Das A K.An Eficient Rndom Ky Dstribution Sheme for Lrge-scale Dstributed Snsor Ntworks［J］.Security and Comm.Networks，2011，4（2）：162-180.

［12］Castelluccia C，Spognardi A.Rok：A Robust Ky Pe-Dstribution Po⁃tocol for Mlti-Pase Wreless Snsor Ntworks［C］//Proc Secure⁃Comm，Nice，2007：351-360.

［13］Li S，Zhou B，Dai J，et al.A Scure Sheme of Cntinuity Bsed on To-Dmensional Bckward Hsh Ky Cains for Snsor Ntworks［J］.IEEE Wireless Communications Letters，2012，1（5）：416-419.

［14］Zhou B，Wang J，Li S，et al.A Continuous Secure Scheme in Stat⁃ic Heterogeneous Sensor Networks［J］.IEEE Communicatons Let⁃ters，2013，17（9）：1868-1871.

［15］Zhou B，Li S，Wang J，et al.A Pirwise Ky Etablishment Sheme for Mltiple Dployment Snsor Ntworks［J］.International Journal of Net⁃work Security，2014，16（3）：221-228.

［16］Gu W，Chellappan S，Bai X，et al.Scaling Laws of Key Predistri⁃bution Protocols in Wireless Sensor Networks［J］.IEEE Trans on Information Forensics and Security，2011，6（4）：1370-1382.

［17］王秋华，汪云路，王小军，等.无线传感器网络中抗共谋的自愈组密钥分配方案［J］.传感技术学报，2013，26（2）：221-227.

［18］黄廷辉，杨旻，崔更申，等.基于LEACH协议的无线传感器网络密钥管理路由方案［J］.传感技术学报，2013，27（8）：1143-1147.

赵巾帼（1965-），女，毕业于中南工业大学。现任职于湖南工学院，最高学历为硕士，职称为副教授，主要担任数据库技术方面的教学工作。主要研究方向为语义Web，无线传感器网络；

周波清（1979-），男，博士毕业于湖南大学，现为中南大学博士后。副教授，主要研究方向为传感器网络安全、信息安全等；zbq_paper@163.com。

A Pairwise Key Establishment Scheme for Sensor Networks Based on Dnamic Ky Pols*

ZHAO Jinguo1，ZHOU Boqing2*，ZHU Lingzhi1，LI Sujun2
（1.Department of Computer and Information Science，Hunan Institute of Technology，Hengyang Hu’nan 421002，China；2.Deppartment of Information Science and Engineering，Hunan University of Humanities，Science and Technology，Loudi Hu’nan 417000，China）

To achieve continuous security throughout the lifecycle of sensor networks，a pairwise key establishment is proposed based on dynamic key pools（KES-D）.In our scheme，network deployment includes n phases；the key pool is divided into n generations according with the times of network deployment.The ithgeneration key pool con⁃sists of keys from the（i-1）thgeneration key pool except m two-dimensional backward hash key chains whose used time is the longest，and m two-dimensional backward hash key chains.The theoretical analysis and numerical exper⁃iment show that the proposed scheme can significantly improve the resilient key connectivity as compared with the schemes for multiphases deployment sensor networks.

sensor networks；key establishment；dynamic key pools；resilient key connectivity

TP393

A

1004-1699(2015)10-1537-08

��7230

10.3969/j.issn.1004-1699.2015.10.021

项目来源：国家自然科学基金项目（11471002）；湖南省教育厅优秀青年基金项目（13B057）

2015-05-24 修改日期：2015-07-20