基于哈希密钥链的无线传感器网络密钥预分配方案

刘海英，熊俊俏，戴璐萍，郑宽磊

(武汉工程大学电气与信息学院，湖北 武汉 430073)

基于哈希密钥链的无线传感器网络密钥预分配方案

刘海英，熊俊俏，戴璐萍，郑宽磊

(武汉工程大学电气与信息学院，湖北 武汉 430073)

目前，主要通过研究密钥管理来保证无线传感器网络的安全。在基于密钥预分配的方案中，当前研究的热点是随机密钥预分配模型，但它面临一个潜在的挑战，即无法同时获取理想的网络安全连通性和网络抗毁性。为此，提出一种基于哈希密钥链的随机预分配方案，利用密码学的哈希函数提高方案的抗节点俘获能力，增强网络的安全性，且在与E-G方案同等网络连通概率下具有较小的存储消耗和通信消耗。

无线传感器网络；密钥管理；密钥预分配；哈希密钥链

无线传感器网络是由传感器节点以自组织方式构成的无线网络，其目的是感知、采集和处理网络覆盖地理区域中感知对象的信息，并传递给观察者。无线传感器网络广泛应用于军事、环境、健康、家庭和其他商业领域等各个领域[1]。随着无线传感器网络受到越来越多的关注，其安全问题也变得越来越重要。无线传感器网络密钥管理是无线传感器网络安全的一个基础问题。因此，无线传感器网络管理问题的研究非常有意义，能有效解决无线传感器网络安全，促进无线传感器网络的广泛应用。

在无线传感器网络的密钥管理方案中，随机密钥预分配方案模型因其具有的诸多优势而成为研究热点，基本的随机密钥预分配方案(E-G方案) 首次将随机图理论应用到密钥管理方案中，在E-G方案中，每个传感器节点都存储一定数目的密钥，且会以一定的概率与其他节点存在共享密钥，当某些传感器节点被俘获后，攻击者可以提取出它们所存储的密钥，这就威胁到其他也使用这些密钥作为通信密钥的节点。被俘获的节点数越多，网络的安全性越差，当被俘获的节点数占据整个网络中传感器节点数目的一定比例时，整个网络的安全就不存在了。虽然可以通过增大密钥池来减小被俘节点对网络中其他节点的影响，但是同时又会降低网络的安全连通概率。

笔者在E-G方案的基础上，利用哈希函数[2]的单向计算，设计一种基于哈希密钥链的密钥管理方案，提高网络的连通概率及抗节点俘获能力，同时降低通信密钥建立时的通信能耗。

1 基于哈希密钥链的密钥预分配方案

符号说明：S为密钥池；|S|为密钥池的大小；m为节点密钥环的大小，能存放密钥的个数；p′为邻居节点内能建立安全链接的期望概率；L为密钥池中形成的密钥链集合；S′为密钥池中形成的密钥链的数量；l为密钥池中形成的密钥链的长度；a为传感器节点A的标识符；a|b为a与b的连接；IDk为密钥k的标识符；Kab为邻居节点A和B之间的通信密钥(其中，a和b是字母)；Kij为密钥链i中的第j个密钥(其中，i和j是数字)；Kai为节点A的密钥环中的某个密钥(其中，a为字母，i为数字)；A→*为节点A向网络中广播信息；A←B为节点A接收B广播的信息。

1.1网络通信密钥的建立

该方案设计有4个阶段：密钥预分配阶段、共享密钥发现阶段、路径密钥建立阶段和密钥增强阶段，具体描述如下：

1)密钥预分配阶段 首先从密钥池中随机选取1个密钥作为1组密钥链的首密钥。设H(x)是单向密钥生成函数，利用该哈希函数可以生成1个长度为L的密钥链，并为其中每个密钥分配1个ID标识符，其标识符是连续的；第2条密钥链依然是随机从密钥池中选取1个密钥作为首密钥，利用H(x)哈希函数生成密钥链中的其他密钥，其首密钥的标识符为IDl+1，其余标识符依次加1；依次类推，在密钥池中生成S′条密钥链(S′=|S|/l)，密钥标识符为ID1到IDs′L。

2)共享密钥发现阶段 这一阶段主要完成区域内邻居节点直接建立通信密钥的过程，每个节点都需要发现周围可以与其进行密钥匹配的节点，若2个节点拥有相同的密钥，或者都拥有的密钥其中一个可以由另一个经过哈希函数计算出来，即在同一条密钥链上，则将这2个节点看成拥有匹配的密钥，可以直接建立通信密钥。

3)路径密钥建立阶段 在网络部署后，若通信范围内的某2个节点之间不能直接建立通信链接，则利用中间节点建立通信密钥。

若约定由二者中节点标识符较大者生成它们的通信密钥，通过第3方传递给节点标识符较小的节点。例如，节点alt;c，二者在彼此的通信范围内，但是节点所存储的密钥中没有共享密钥，那么节点a发现c标识符大于自己的，就不去计算通信密钥，等着接收由中间节点发来的带有与c节点的通信密钥的信息;节点c发现自己的标识符大于节点a，则从自身存储的密钥中随机抽取一个，利用哈希函数计算通信密钥Kac=H(K|a|c)，并将该密钥及目标节点a的标识符一起传给其与a共同都存在通信密钥的节点b(信息是经Kac=H(K|a|c)加密后的)，节点b接收到该信息解密后，发现是要传送给节点a的，就将该信息利用Kac=H(K|a|c)加密后传给节点a，a解密后即可得到与节点c的通信密钥[3]。

4)密钥增强阶段 在邻居节点间建立了通信密钥后，利用哈希函数对每个节点存储的每个密钥分别进行计算K′=H(K|节点标识符)，计算后，删除节点的密钥环中的每个原密钥K，此时，即使节点被俘获，攻击者也无法通过解密K′获取节点的原始密钥K，因此未被俘获的节点间的任一通信密钥仍是安全的。由此可以看出，哈希函数的单向性可以有效的保护密钥信息[4]。

1.2网络节点加入

在该方案中，因为通信密钥建立后要对密钥环中的密钥进行哈希计算，之后删除节点中存储的原密钥K，所以在加入新节点时，要重新设计新节点如何与网络中的其他节点建立通信密钥。

假设要部署一个新的节点w，其密钥环中带有密钥K，为了与其邻居节点共享对密钥，节点收集其邻居节点的ID以及密钥ID，同样判断邻居节点中的密钥ID是否大于自身的密钥ID，若大于，则根据其ID号进行差值次数的哈希计算得到邻居节点中存储的K′=H(K|u)的原密钥，然后与接收到的节点ID标识符进行同样的哈希计算，进而计算出每个邻居节点u的可能的密钥K′=H(K|u)[5]，通过使用K′的通信密钥发现阶段，建立了对密钥Kuv=H(K′|u|w)。路径密钥建立阶段后，w利用密钥环中的每个密钥K计算K′=H(K|w)，并删除K。

2 性能分析

从邻居节点间的连通概率和传感器节点的能耗2方面对改进方案进行评价。

所以，邻居节点间可建立链路的概率为:

利用阶乘近似计算公式Stirling公式可将其化简为:

2)传感器节点的能耗分析 由以上分析可知，因为在该方案中同属于一条密钥链上的密钥可以通过哈希函数计算，所以在达到可形成通信密钥概率的同等情况下，该方案中存储的密钥数m小于E-G方案中存储的密钥数，即需要存储的密钥数小于E-G方案[7]。

E-G方案的存储量为密钥环的大小，但该方案因为邻居节点建立的通信密钥是利用二者公共的密钥经过哈希计算而得到的，所以每个节点除了需要存储m个密钥(虽然原密钥在计算过K′=H(K|u)后被删除，但是还是需要存储计算后的密钥)、每个密钥的ID号、节点标识符、哈希函数外，还需要额外为每个节点与邻居节点建立n′个对密钥。下面给出在p′相同时，该方案与E-G方案分别所需存储的密钥环大小m，假设|S|=105，l=5。

表1 p′相同时E-G方案和基于哈希函数的预分配方案所需存储的密钥数m

由表1可以很清楚的看出，若要得到与E-G方案情况下相等的概率p′， 基于哈希函数的预分配方案节点所需存储的密钥数是E-G方案的一半以下。由前面的分析可知，邻居节点数n′在数值上不会很大，这也由部署区域性质决定，所以总的来说，在同等邻居连通概率p′下，该方案中节点需存储的信息加上与邻居节点建立的通信密钥，依然比E-G方案中节点需要存储的密钥信息要少。在同等邻居连通概率p′下，该方案中节点需存储的信息加上与邻居节点建立的通信密钥，比E-G方案中节点需要存储的密钥信息要少[8]。

该方案若邻居节点间可建立安全通信链路的概率等同于E-G方案，因其节点中需要存储的密钥数小于E-G方案，所以在共享密钥发现阶段，每个传感器节点需要广播的密钥标识符也要少于E-G方案，即该方案在安全链路建立阶段的通信开销要小于E-G方案；若该方案中的传感器节点同E-G方案存储同样多的密钥，则其可形成通信密钥的概率一定高于E-G方案。

与E-G方案相比，对于相同的m，该方案增加了计算量。因为该方案中需要额外的哈希函数操作来计算节点间通信密钥以及m次哈希函数操作来重新计算密钥环。

3 安全性分析

在该方案中，每个节点与邻居节点建立通信密钥之后，将密钥环中原密钥K计算成K′=H(K|节点标识符)，用于与新加入的节点建立通信密钥，即密钥建立是从建立通信密钥到计算密钥环中的原密钥的过程。如果一个节点在其密钥建立之前被俘获，那么则节点中的原密钥将暴露给攻击者，否则如果一个节点在其密钥建立后被俘获，攻击者获得的是经过计算后的密钥K′=H(K|节点标识符)，而不是原密钥K，所以也就不会威胁到网络中的其他节点间的通信[9]。

该方案中节点在通信密钥建立后被俘是不会泄露网络中已经建立的通信密钥的原密钥，即不会影响先前的通信，具有很好的安全性，所以该方案在密钥建立后，有效的利用哈希函数重新计算每个节点密钥环中的密钥，以防止攻击者发现通信密钥使用的某些密钥因子，减少了被俘节点泄露密钥的机会，有效的提高了网络的抗节点俘获能力，增强了网络的安全性[10]。

4 结 语

无线传感器网络自身的特点使其安全机制面临严峻挑战。密钥管理机制则是构建安全的无线传感器网络的核心技术。笔者提出了一种基于哈希密钥链的随机密钥预分配方案，利用哈希函数对基本的随机密钥管理方案进行改进。分析结果表明，对密钥池的处理提高了网络连通性，使得方案可以支持较大的密钥池，对节点存储的密钥进行处理提高了方案的安全性，同时，降低了节点间建立通信密钥时的通信能耗，支持节点的加入，可以用于大型传感器网络。

[1]任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14(7):1282～1291.

[2]孙利民，李建中，陈渝，等.无线传感器网络[M].北京:清华大学出版社，2005.4～10.

[3]戴宁江，邱惠敏.无线传感器网络的安全问题及对策[J].中国无线电，2006,(10):47～49.

[4]王殊，阎毓杰，胡富平，等.无线传感器网络的理论及应用[M].北京:航空航天大学出版社，2007.4～7.

[5]王明辉.无线传感器网络密钥管理方案研究[D].杭州：浙江大学，2006.

[6]李平，林亚平，曾玮妮.传感器网络安全研究[J].软件学报，2006，17(12):2577～2588.

[7]Neuman B C，Tso T.An authentieation service for computer networks[J].IEEE Communications September,1994，32(9):33～38.

[8]陈菲，宋志高，陈克非.无线传感器网络中对密钥管理评估指标研究[J].计算机仿真，2005，22(5):134～140.

[9]苏忠，林闯，封富君，等.无线传感器网络密钥管理的方案和协议[J].软件学报，2007，5(18):1218～1231.

[10] Liu Feng，Cheng Xu Zhi.Location-aware Key Eatablishment in Wireless Sensor Networks[J].In Proeeeding of IWCMC’，2006，3(6):21～26.

[编辑] 易国华

2009-07-12

刘海英(1976-)，女，1999年大学毕业，讲师，现主要从事电子技术方面的教学与研究工作。

TP393

A

1673-1409(2009)04-N069-04