一种安全的多层移动自组网密钥管理方案

施荣华，袁倩

(中南大学 信息科学与工程学院，湖南 长沙，410083)

摘  要：针对移动自组网群通信中的安全问题，提出1种多层移动自组网安全分层密钥管理方案(HKMS)。其具体内容是：首先，为了简化群结构的管理，基于多层结构模型提出双层密钥管理方案，采用节点间的交换密钥和群密钥对数据包进行双重加密，提高网络通信的安全性；针对移动自组网拓扑结构频繁变化导致群结构维护复杂问题，对节点加入和节点离开2方面进行讨论；其次，从前向安全和后向安全2方面对方案的安全性进行分析；最后，与类似方案的性能进行比较分析。研究结果表明：该方案对节点的存储量要求较低，节点加入退出相关操作的执行效率等较高，简化了群管理与维护，能有效地减少群密钥重分发数。

关键词：移动自组网；群密钥；密钥管理；网络安全

中图分类号：TP309          文献标志码：A         文章编号：1672-7207(2010)01-0201-06

A secure hierarchical key management scheme in mobile ad hoc networks

SHI Rong-hua, YUAN Qian

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: In order to insure the security of communication in MANETs (Mobile ad hoc networks), a secure hierarchical key management scheme (HKMS) in MANETs was proposed. The real procedures were as follows. Firstly, in order to make the management of group structure much easier, a two-layer key management scheme was introduced using the multi-layer structure model. This scheme suggests encrypting a packet twice with session keys between nodes and group keys respectively to improve the security of communication in MANETs. Secondly, due to the frequent changes of the network’s topology, it is complex to maintain a group structure, the group maintenance on the view of a node’s join and leave was discussed. Then the scheme’s security on forward and backward security were analyzed, The results show that HKMS has lower requirement of node storage ability and higher implementation efficiency when nodes join or leave the MANNETs, and it also simplifies the group management and maintenance and reduces the key redistribution cost.

Key words: mobile ad hoc networks; group key; key management; network security

移动自组网MANET(Mobile ad hoc networks)是由多个移动节点通过无线链路连接，具有时变拓扑结构的多跳、临时性自治系统^[1-2]，被广泛应用于军事战场和交互式信息共享等。由于其应用的特殊性，移动自组网的安全性能越来越受到人们的关注。移动自组网又分单层和多层2种结构，其中，单层移动ad hoc网络的网络规模受限且维护路由的网络开销太大，使得网络的效率较低和可扩展性较差^[3-5]。与此相比，多层移动ad hoc网络中包含具有不同功能的多种节点。可以根据节点的自身特点赋予不同的网络角色。这使得多层结构除了具有较好的扩展性外，网络的路由开销也大大减少，从而具有较高的效率。此外，引入多层结构还便于实施网络管理。针对动态网络的密钥管理，研究者们提出了很多方案及相关通信协议^[6-9]，且这些方案中有许多应用分级结构^[10]，基本的密钥重分发算法和分级架构常把密钥管理范围分为较小的模块，再分别进行管理。另外，公钥密钥体系^[11]、多点传送及基础树算法在相关方案中得到应用。Steiner  等^[12]提出了一个名为CLIQUES的方案，该方案采用了密钥协商和一个顺序传递密钥信息的线性逻辑结构。在该方案中，每2个节点间必须有1个交换密钥，这样对每个节点的存储量要求太高，且群密钥的生成步骤太多，安全性较低；Tseng等^[13]提出了一个名为SGCP的方案，有利于移动自组网中的安全通信。该方案中的通信以群结构为基础并应用了无线架构，在这个架构中，每个节点的传送能力都是1跳节点，负荷量最大即1跳邻居节点数最多的节点被选为多点传送中的路由器，这些被选出来的节点是以后构建的群的中心。群建好以后，路由器能自己生成群密钥并能在数据传送过程中对相关的加密数据进行解密操作。但由于在方案中所有节点加解密用的是统一的群密钥，所以，一旦有节点加入或退出，架构必须重新生成群密钥，以保证安全性，重分发密钥次数较多，资源浪费较大。为此，本文作者提出1个利于群安全通信的多层移动自组网密钥管理方案。该方案采用双层架构将网络划分为2层。根据节点信息，各层又被分为不同的子群，每个子群都有1个群首来管理该子群中所有节点的信息，并生成与传递该子群的群密钥，由此而简化了群结构的管理，降低了对节点存储量的要求，减少了密钥重分发的次数。此外，方案中对1个将要被传送的数据包可先后用节点间的交换密钥及群密钥进行双重加密，有效地解决了网络通信中前向安全与后向安全的问题，提高了网络通信的安全性。

1  分层密钥管理方案

移动自组网中频繁变动的拓扑结构会引起节点不断移动，如何构造及维护一个群是一项复杂的问题。假设1个节点要传送1个信息给1个2跳邻居节点，这时，该节点便会收集它所有2跳节点的相关信息，然后，根据这些相关信息来设计传送路径及构造群结构。

1.1  密钥管理

本方案构建了1个两层架构。第1层(称为L1子群)由所有节点构成；第2层(称为L2子群)则在形成L1子群后根据存储在L1子群的所有剩余节点的信息划分而成。方案在各子群中都会选出负荷量最大的节点作为该子群的群首^[10]，以管理群信息以及生成和传送群密钥。第1层中子群的群首记为L1-head，第2层中子群的群首记为L2-head。图1所示为节点间群密钥的传输过程。

图1  节点间群密钥的传输

Fig.1  Subgroup key transmission operation between nodes

下面分别讨论L1-head和L2-head的生成过程。

L1-head的生成过程为：

(1) 每个节点向2跳范围内的邻居节点传送信息的同时，附带传送各自负荷量。

(2) 收集各个节点的负荷量，选出负荷量最大的节点为L1-head。

(3) 其余节点向L1-head发送所有相关信息，并到L1-head注册。

L2-head的生成过程为：

(1) 所有节点把本地信息发送给L1-head。

(2) 收到所有的信息后，L1-head根据相关信息把除自身外的其他节点分成子群，标为L2子群。

(3) 每个L2子群中的节点再分别比较各自的负荷量，负荷量最大的被选为该L2子群的群首，标为L2-head，负责与L1-head及其他的L2-head进行通信。

当群关系建立好以后，所有的节点将注册信息发送给L1-head。L1-head存储好 L1子群中所有节点的信息后，采用RSA算法生成L1子群群密钥L1GK，并将L1GK传送给子群中的所有节点，节点可用它来加密所要传递的信息。

为了提高子群中信息传输的安全性，将除L1-head外的所有节点分成几个L2子群，每个L2子群都含有1个群首L2-head，且子群中的节点由L2-head进行管理。每个L2子群都拥有它们各自的群密钥(L2GK)。其中，L2GK由已知的L1GK经计算而得到。因此，只有L2-head及它下面管理的各普通节点知道本子群的L2GK。对于子群之间的通信，利用DH协议获取安全性。首先利用子群中的通信节点来联系邻居子群，在此过程中通信节点先将信息传送给L1-head以得到2个不同子群中的节点i和节点j之间的通信密钥K_c，然后，K_c将被用来加解密需在不同子群中传送的信息。当L2-head知道目的节点的位置后，便会利用DH协议生成1个只属于源节点和目的节点的交换私钥K_DH，K_DH被用于对所要传递的信息进行最初加密。

图2所示为数据包传递过程中的加密和解密操作过程。在图2中，假设节点A要传送1个数据包给节点D，路径及目的节点都已知。首先，A将利用DH协议生成1个交换密钥K_DH，并用它先加密数据包；接着，利用L2GK_{1, 1}对数据包进行第2次加密，并把加密后的数据包传送给L2-head即H_{1, 1}。H_{1, 1}将先用L2GK_{1, 1}对收到的数据进行解密，然后，用L1GK₁对数据进行加密，最后，将它传送给H_{1, 2}。H_{1, 2}收到数据包后，先用L1GK₁对数据进行解密，再用L2GK_{1, 2}对数据进行加密，然后，数据包传送给节点B。节点B收到数据包后先用L2GK_{1, 2}对数据进行解密，再用交换密钥K_c对数据进行加密，然后，传送给节点C。经过一系列重复加密与解密操作后，数据包最终被传到目的节点D。收到数据包后，节点D先用 L2GK_{1, 2}解密，然后，用K_DH解密以获得最初的信息。

图2  数据传输中的加密与解密过程

Fig.2  Encryption and decryption operation during data transmission

1.2  群密钥的维护

下面讨论当移动自组网的网络拓扑变化引起节点移动时群密钥的维护过程。

1.2.1  子群中新节点的加入过程

移动自组网中节点会频繁地进行移动。假设每个新加入的节点都是安全节点。当1个新节点要加入某个子群时，群首只需要重新生成1个群密钥，然后，分发给各节点。

1个新节点加入某个子群的具体过程为：

(1) 新节点发送加入的请求信息给子群中的邻居节点。

(2) 相关邻居节点收到请求信息后再把它转发给群首L2-head。

(3) L2-head发送1个回复信息给新节点。

(4) 新节点收到回复信息并被允许加入子群。

(5) L2-head在更新子群信息的同时将重新生成L2子群群密钥，并把新的群密钥发送给子群中所有的  节点。

1.2.2  子群中节点的离开过程

普通节点的离开过程较简单，只需它所在的子群L2-head重新生成1个L2GK，而其他子群的节点密钥都没有改变。具体步骤如下：

(1) 普通节点的离开过程。

① 在普通节点离开子群以前，先发送1个离开信息给它所属子群的L2-head。

② L2-head收到节点的离开信息后，发送1个回复信息给将要离开的节点，然后更新子群信息，同时重新生成1个群密钥，再将新的群密钥发送给子群中剩余的节点。

(2) 节点L2-head 的离开过程。

对于L2-head的离开，方案将从子群中剩余的普通节点中选出负荷量最大的节点作为新的群首L2-head。接着，子群中所有的其他节点会到新的L2-head进行注册，并将自身的相关信息发送给新的L2-head。具体步骤如下：

① 在离开以前，L2-head分别向子群中的所有节点和所属的L1-head发送1个离开信息。收到L2-head的信息后，普通节点和L1-head都会发送回复信息给L2-head。若L2-head在某段时期内没有收到回复信息，则会向没有反应的节点重新发送。

② L2子群中由L2-head管理的普通节点将会通过比较各自的负荷量来选出新的L2-head，将负荷量最大的节点作为新的L2-head。

③ 新的L2-head将L2子群的更新信息发送给所属管理的L1-head。

④ L1-head收到新的L2-head发送来的群更新信息后，生成1个新的群密钥L1GK，并发送给它所管理的所有L2-head。

⑤ 每个L2-head从L1-head处收到新的L1群密钥后，也会在本地生成1个新的群密钥，并发送给本子群中的所有节点。

对于L1-head的离开，方案先从该群所有的L2-head中选出负荷量最大的节点作为新的L1-head，然后，其余的L2-head到新的L1-head处注册，并将相关信息发送给L1-head。而被选为新的L1-head的L2-head以前所管理的L2子群则按上述节点L2-head离开的情况重新进行组织。

(3) 节点L1-head 的离开过程。

① L1-head发送离开信息给它所管理的L2-head，收到信息后L2-head发送回复信息。若L1-head在某段时期内没有收到某些L2-head的回复信息，则对这些节点进行重发。

② 收到L1-head的离开信息后，所有L2-head比较各自的负荷量，最大的那个被选出来作为该群的新L1-head。

③ 新的L1-head节点以前管理的L2子群中的普通节点，比较各自的负荷量，选出负荷量最大的节点作为该L2子群的新L2-head。

④ L1子群中所有的L2-head将各自管理的L2子群信息发送给新的L1-head，进行注册。

⑤ 新L1-head在收到所有的L2-head信息后，生成1个新的L1群密钥L1GK，然后，将它发送给该群中所有的L2-head。

⑥ 各L2-head在收到新的L1GK后，重新生成1个群密钥，发送给群中的各普通节点。

上面讨论的是节点正常离开的情形，在移动自组网中，节点移动频繁，甚至会突然消失，这会使群维护困难且不能有效地传送数据。下面讨论发生特殊情况时方案采取的措施。

情况1：离开节点没有发送任何离开信息而突然消失。在本方案中，L1-head会在固定的时间内向群内的L2-head发送相关信息以取得联系，L2-head也会向群内的普通节点发送相关信息取得联系。若某个节点突然没反应，则该子群便会进行重组织，生成新的群密钥。

情况2：节点在不同的子群间不断移动。节点的频繁移动会引起子群不断地生成不必要的新的群密钥，造成资源浪费。为了防止这种情况，当1个节点加入或者离开某个子群时，采取让子群群首过一段时间再生成新的群密钥的措施。

2  安全性与时间复杂度分析

现阶段快速的计算能力及现存的各种各样的攻击方法都会威胁到节点的安全，从而影响整个网络的安全。保证网络通信的安全性是密钥管理方案的必备性能。

2.1  安全分析

2.1.1  前向安全

方案提出新节点在加入群以前不会收到群中以前传送的任何信息。在群的维护中，新节点加入后，L2-head将生成新的群密钥并传送给新节点，新节点能用它来加密或者解密以后要传递的信息，但不能用于解密在节点加入群以前传送的数据。因此，该方案很好地保证了网络通信的前向安全。

2.1.2  后向安全

当1个节点离开后，该方案保证它再不能收到与子群有关的任何信息。这里分3种情况讨论节点的  离开。

(1) L2子群中普通节点的离开。节点离开后，L2-head重分发新的群密钥，这样，离开后的节点便不能对新的信息解密。

(2) L2-head的离开。L2子群不但选出了新的L2-head，而且L1-head也生成了新的L1群密钥，最后，所有的L2-head在收到新的L1群密钥后又为本子群生成新的L2群密钥，即所有的群密钥都发生了变化，离开后的L2-head根本无法获取后来会传送的信息。

(3) L1-head的离开。对于这种情况，方案从L1-head管理的L2-head中选出新的群首，然后，所有的密钥都重新生成，与情况(2)一样，离开后的节点无法再对网络中传送的信息解密。因此，该方案很好地保证了后向安全。

2.2  时间复杂度分析

设m表示1个L2子群的总成员数，k为架构中L2-head的总个数，p为1个L1子群中的所有节点数。假设每个L2子群拥有相同的成员数，那么p=km+1。

2.2.1  L1-head中的密钥存储量

在方案提出的2层架构中，L1-head先生成1个L1GK并存储，当L2子群结构布置好并生成L2子群密钥L2GK后，L2-head把L2GK发送给L1-head进行存储。因此，L1-head中存储的密钥总数为k+1个，其时间复杂度为O(m)。然而，CLQUES利用DH协议来生成密钥，每2个节点间必须有1个交换密钥，然后，由这些密钥联合生成群密钥，所以，其时间复杂度为O(p)。与其他2个方案比较，这个方案中节点所需的存储量是最大的。在SGCP方案中，加解密都用同一个群密钥，所以，它的L1-head中存储的密钥数是最小的，时间复杂度为O(1)。

2.2.2  L2-head中的密钥存储量

在CLQUES和SGCP方案中，L2-head中没有存储任何密钥。而在本方案中，L2-head存储了2个密钥：一个是用于联系L1-head和其他的L2-head的L1GK，另一个是该L2子群群密钥L2GK，用于子群内部通信。在这部分，方案的时间复杂度为O(1)。

2.2.3  普通节点的密钥存储量

在HKMS和SGCP中，普通节点只存储了1个群密钥。而在CLQUES中，每2个节点都有交换密钥便于通信。群密钥由这些通信密钥联合生成，因此，存储在普通节点中的密钥明显比前2种方案的密钥   要多。

2.2.4  新节点加入

当1个新节点加入群时，HKMS只需生成1个新的L2子群群密钥(L2GK)，即只有该子群的成员数会发生变化，对其他子群没有任何影响，时间复杂度为O(m)。然而，在其他2种方案中，一旦有新节点要加入群，则必须生成1个新的群密钥并将它发送给所有的节点，时间复杂度为O(p)。

表1  时间复杂度比较

Table 1  Time complexity comparison

2.2.5  节点离开

对于节点的离开，HKMS分3种情况：第1种是普通节点的离开，方案需为剩下的节点生成1个新群密钥并分发，时间复杂度为O(m)；另外2种情况是L1-head和L2-head的离开，无论哪种情况，网络中的第1层和第2层所有的群密钥都需更新，时间复杂度都为O(p)。在CLQUES和SGCP方案中，无论哪个节点离开，整个网络都必须生成新的群密钥并分发给剩下的节点，时间复杂度也都为O(p)。

2.2.6  群内部通信

在CLQUES和SGCP方案中，对传输的数据包只需进行1次加密和解密。而在HKMS中，当数据在不同的L2子群中进行传输时，需进行2次加解密操作，耗费的时间比前2种所耗费的时间都要多。

在CLQUES中群密钥的生成需经历的步骤较多，与其他2种方案相比，其安全性较低。

3  结论

(1) 提出了1个安全的分层移动自组网密钥管理方案。该方案采用了1个双层架构，将网络节点分为2层，根据节点信息，各层又被分为不同的子群，每个子群都由1个群首来管理该子群中所有节点的信息，并负责生成与分发该子群的群密钥，而简化了群结构的管理。

(2) 该方案通过双重加密传送信息来保证安全。当1个节点要传送数据给另一节点时，相互之间能生成交换密钥，在传送数据的过程中，先用交换密钥加密数据，再用群密钥加密，提高了数据传输的安全性。

(3) 所提出的方案可以有效地减少移动自组网的网络拓扑频繁变化所引起的群密钥重分发数，节省资源。

(4) 本方案与Tseng方案及Steiner方案相比，有效地简化了群管理，对节点的存储要求较低，且能有效地保证网络通信的安全性。

参考文献：

[1] Macker J P, Corson M S. Mobile ad hoc networking and the IETF[J]. ACM Sigmobile Mobile Computing and Communications Reviews 1998, 2(2): 9-14.

[2] Marwaha S, Chen K T, Srinivasan D. A novel routing protocol using mobile agents and reactive route discovery for ad hoc wireless networks[C]//Proceedings of the 10th IEEE International Conference on Networks. Singapore, 2002: 311-316.

[3] Kim Y, Perrig A, Tsudik G. Group key agreement efficient in communication[J]. IEEE Transactions of Computers, 2004, 53(7): 905-921.

[4] Mishra A, Nadkni K, Patcha A. Intrusion detection in wireless ad hoc networks[J]. IEEE Wireless Communications, 2004(2): 48-60.

[5] LIAO Li-jun, Manulis M. Tree-based group key agreement framework for mobile ad hoc networks[J]. Future Generation Computer Systems, 2007, 23(6): 787-803.

[6] Steiner M, Tsudik G, Waidner M. Diffie-Hellman key distribution extended to group communication[C]//Proceedings of the Third ACM Conference on Computer and communications Security. New Delhi, India: ACM Press, 1996: 31-37.

[7] Pieprzyk J, LI C H. Multiparty key agreement protocols[C]//IEE Proceedings Computers and Digital Techniques. America, 2000: 229-236.

[8] CAO Jian-nong, WANG Guo-jun, Keith C C. A fault tolerant group communication protocol in large scale and highly dynamic mobile next-generation networks[J]. IEEE Transactions on Computers, 2007, 56(1): 80-94.

[9] WANG Guo-jun, CAO Jian-nong, Keith C C. A novel group communication protocol using the ring net hierarchy in mobile internet[J]. International Journal of Parallel, Emergent and Distributed Systems (Taylor & Francis), 2005, 20(4): 253-280.

[10] Dhurandher S K, Singh G V. Weight based adaptive clustering in wireless ad hoc networks[C]//Proceedings of the 2005 IEEE International Conference on Personal Wireless Communications. New Delhi, India: IEEE, 2005: 95-100.

[11] 施荣华. 一种基于复合问题的公钥密码系统[J]. 计算机工程与科学, 1998, 20(1): 39-42.
SHI Rong-hua. A public key cryptosystem based on complex problems[J]. Computer Engineering & Science, 1998, 20(1): 39-42.

[12] Steiner M, Tsudik G, Waidner M. CLIQUES: A new approach to group key agreement[C]//Proceedings of the 18th IEEE International Conference on Distributed Computing System, Amsterdam, Netherlands, 1998: 380-387.

[13] Tseng Y M, Yang C C, Liao D R. A secure group communication protocol for ad hoc wireless networks[C]// Advances in Wireless Ad Hoc and Sensor Networks and Mobile Computing. Springer, 2007: 385-390.

收稿日期：2008-11-25；修回日期：2009-03-07

基金项目：国家自然科学基金资助项目(60773013)；湖南省自然科学基金资助项目(07JJ5078)

通信作者：施荣华(1964-)，男，湖南安乡人，教授，从事密码学和信息安全的研究；电话：0731-88830962；E-mail: shirh@mail.csu.edu.cn

(编辑 陈灿华)