移动自组网的组密钥链更新算法

陈 蹊 ， 赵跃龙

（华南理工大学 计 算机科学与工程学院，广东 广 州510006）

网络数据的传输分为单播、广播、组播3种方式。单播传输方式在发送者和每一个接收者之间实现点对点的网络连接。如果一位发送者同时向多位接收者传输相同的数据，即使在相同的链路上也必须相应复制多份相同的数据包，每一个接收者接收一个数据包的副本。而广播传输是指在IP子网内广播数据包，所在子网内的主机都要收到一份数据包，不论这些主机是否愿意接收该数据包。近年来，随着网络和视频/音频技术的迅速发展，高带宽的应用和多媒体业务越来越多，诸如远程教学、视频会议、视频点播、网络游戏等新兴的网络应用。组播就是顺应这种需求产生的。组播通信是指在发送者和多个接收者之间实现点对多点的网络连接，是“一对一组”的通讯模式，它通过使用特定的IP组播地址，把同一数据包从一台主机传送到由若干台主机组成的组播组的每一个成员。组播传输不仅节省网络资源，还可有效控制子网中接收组播信息的用户[1]。

移动通信设备以及无线网络的高速发展为移动网络的应用提供了发展平台，例如：野外活动、救灾工作、军事行动等。而移动自组网更是成为快速建立通信网络的有效途径。移动自组网络 （Mobile Ad hoc Network，MANET）是一种不依赖于任何固定基础设施的新型无线网络。与需要中心控制的设备，如基站或访问服务点的蜂窝移动通信网络和无线局域网相比，移动自组网络具有自组性、多跳性、无基础设施要求、易铺设等特点。同时移动自组网也具有不稳定、不可靠、网络拓扑结构变化频繁、连接短暂等缺点[2-5]。

1 传统组密钥算法

组密钥管理为网络中的组成员生成、分发和更新组密钥。组密钥是所有组成员都知道的密钥，被用来进行加密/解密或者认证，以满足保密、组成员认证等需求。因此，组密钥管理可以看成是一种组成员会话权限控制技术。通过对组密钥的管理，能够有效地完成对组成员会话权限的动态授权与回收。组密钥管理至少需要具有前向安全、后向安全和抵抗合谋破解的能力。

根据拓扑结构的不同，可以把组密钥管理方案分为3大类：集中式、分布式和分层分组式[2]。集中式组密钥管理主要是由一个组管理器（group controller，GC）执行密钥的生成分发和更新。这种架构能够很好地管理组成员的密钥，实现诸如节点身份认证、密钥生成、实时监控等功能。但是集中式的管理方式对GC的依赖性太强，容易出现单点失效的问题。分布式组密钥管理中，参与组播的成员的关系是对等的，他们共同参与组密钥的生成和管理。克服了集中式单点失效的问题，是动态组播密钥管理的较好方案。而分层分组式组密钥管理则是前两者的结合，其架构是将各节点分成多组，组内进行分布式密钥管理，而组与组之间则采用集中式密钥管理。

移动自组网的拓扑结构具有多变性，一个节点的加入和退出都要引起组密钥的更新。本设计在分布式组密钥管理的基础上进行改进。运用密钥链以及左向性共享密钥与右向性共享密钥的设计减少密钥的更新次数，但这样需要一定的存储开销。

2 DKCGR组密钥算法设计

分布式密钥链更新算法（Distributed Key-chain Group Rekeying，DKCGR）的符号定义如下：n表示节点数；ID表示节点的唯一标识；keyij表示节点i和节点j之间的共享密钥，用DH算法生成[6]；Li和Ri分别表示左向性密钥和右向性密钥；K表示组密钥；{m}K是用密钥K加密消息m；

2.1 密钥链生成

基于移动自组网中的节点是分布式拓扑结构，节点彼此之间是对等关系，这里将这些节点按逻辑方式排列成一排并进行编号，即ID号。排列方式可按照地理分布排列[7]。由于移动节点不仅存在信号强弱问题，还存在功率、电量等不稳定因素。因此，组成员越集中，网络的信号将越强。在此，可以假设按照各节点在场景中心附近的移动概率来排列。相邻成员采用DH密钥协商，每2个成员之间共享1个密钥，从而可以通过成员之间的共享密钥作为传递信息的通道，该通道称为密钥链。密钥链的具体生成算法如下：节点IDi分别与左邻IDi－1右邻IDi+1用DH算法计算出key（i－1）i和keyi（i+1）（1＜i＜n）。而处于边界的节点，即ID1和IDn也进行一次DH算法生成Key1n，如此便生成一个循环的密钥链。因为密钥链的生成由各个节点共同完成，所以相当于是并行计算密钥链，故整条链的生成时间只用了一次DH算法的时间。图1所示是8个节点完成密钥链后的结构。

图1 8节点密钥链结构

2.2 左/右向性密钥生成

在一个组播组中，根据节点的个数n生成n个左向性共享密钥和n个右向性共享密钥，但并不是每个节点都保存这两组密钥。节点IDi保存的左向性密钥有Lj（j=i+2k，i＜j＜n，k=1，2，3…），同时保存Rj（j=i－2k，1＜j＜i，k=1，2，3…）。当j+2＞8或j－2＜1时，不生成密钥。以8个节点为例，如图2所示。

图2左/右向性密钥

2.3 初始组密钥生成

密钥链建立好后，将key12组密钥K。这里并不采用DH的传统算法，即将所有Keyij都作模指运算生成最终的组密钥。因为这样将消耗极大的计算时间，随着节点数的增多，扩展性便会降低。虽然采用Key12作为组密钥有可能会被破解，但在一定时间段内破解的可能性不大，因为要破解DH算法需要很长的一段时间；而考虑到移动自组网的动态性，每次节点的退出和加入都会引起组密钥的更新，所以，在还未破解原密码前，新密码就已产生了，从而大大加强了组播的安全性。

2.4 节点的加入与退出

新节点的加入比较简单。具体过程如下：假设新节点为IDm（m=n+1），则IDm与IDn生成共享密钥Keynm，再与ID1生成Key1m，并按照左右向性密钥算法给IDm生成左右向性密码；同时，Key1m便成为新的组播密码K′，ID1用K加密K′即{K′}K并组播给其他组员，从而保证了组密钥的向后保密性。

当有节点退出组播组时，假设在有8个成员的组播组，ID4号成员退出时如图3所示，将按以下步骤进行：1）把ID3和ID5用一次DH算法计算出它们的共享密钥Key35；同时废除Key34与Key45；2）将Key35作为新的组密钥K′；3）ID3节点执行的操作：{K′}L5，并进行组播；4）ID5节点执行的操作：{K′}R3，并进行组播；5）得到组密钥的节点，再通过与邻居的共享密钥，把K′传给邻居节点，从而完成组密钥更新。

图3 8节点密钥链结构

根据以上方案可知，若退出节点的ID号为偶数，那么在步骤3和5时，组密钥被组播到所有的奇数节点。各奇数节点再通过共享密钥把组密钥通过单播的方式传到相邻的偶数节点。这样就实现了所有组密钥的更新，因而保证了向前保密性。

3 方案实现

1）密钥链的生成n表示节点的个数；DH（i，j）为一次模指运算，计算出一个共享密钥；K为组密钥。

4 系统分析

在分析组播密钥管理方案中，主要要考虑的是：组密钥管理的安全性，密钥变更时的计算复杂度和通信量，节点的负载以及存储开销等。以下将对本设计的相关方面作具体的分析。

4.1 安全性分析

1）向前保密性确保组成员在退出组后，除非重新加入，否则无法再参与组播，包括获知组播报文的内容和发送加密报文[2]。如图3所示，当一个节点退出组后，首先断绝其与左右邻建立的共享密钥，这样左右邻都无法将新的组密钥传给退出的节点。接下来ID3用L5加密新的组密钥K′，ID5用R3加密K′。而ID4不具有这两个密钥，所以也就无法破解出新的组密钥。

2）向后保密性确保新加入的组成员无法破解它加入前的组播报文[2]。根据上文所述的节点加入方案，当节点加入时，该节点便与ID1共同生成一个新的组密钥K′。但是新节点并不具备原来的组密钥K，用K加密K′后组播给其他节点便可。

3）防御同谋破解避免（或减少发生的概率）多个组员联合起来破解系统[2]。在本设计中，能够进行同谋破解的关键在于左/右向性密码。一个组播组的左向性密钥和右向性密钥之和为2n个。一个节点保存有左右向性密码（n/2）－1个。以8节点为例，每个节点共保存有3个左或者右向性密码。见图2，要完全破解两组向性密钥，最理想的状态为ID1，ID2，ID7，ID8都是同谋才能破解组密钥，这已达到组成员的一半，而能够在这4个位置上的概率还不足0．6%，还不包括身份认证程序的失败率（身份认证在本设计中暂时不讨论）。

4.2 系统资源开销分析

首先考虑节点加入时，更新密钥所需的计算量。当IDm节点加入时，ID1与IDm需要用DH算法计算出组密钥K′，再用K加密K′。总共2次计算。而更新密钥所要进行的操作就是组播K′。当节点退出时，不仅要生成新的组密钥K′，还要对其分别用左右向性共享密钥加密。之后，再通过2次组播和1次与相邻节点的单播通信。本设计的特点是尽可能的减少了计算次数与通信消息数，同时将计算的负载和通信的负载都分布到各个节点上去，但也增加了密钥数的存储空间。在本方案中，每个节点都要存储n/2+2个密钥，其中包括组密钥，n/2－1个左右向性密钥，2个邻居密钥。但随着移动设备技术的发展，这些存储开销是可以接受的。

本设计与经典的LKH算法相比，在计算次数上是一个常数，而LKH的计算次数会因为节点的增多而增加。在存储开销上，LKH比DKGR需要的少。在通信量方面，LKH用的是树形结构，为组播节省了一些通信量。DKGR由于要进行n/2次单播，所以通信量稍大，但是本文会在后面提出改进的方法。

4.3 算法改进

目前流行的组密钥管理方法主要采用树形结构，也就是LKH密钥数结构。本设计受LKH结构的启发采用森林结构。具体结构是：将每4个节点分为一组作为一个根节点的叶子节点。每一子组有一个子组密钥，如图4所示。

图4 树形图密钥结构

当需要组密钥更新时，由产生新的组密钥的节点用Key14将新组密钥K′加密后组播给本组的成员。假设图中ID1节点组播K′后，由ID4用共享密钥把K′传给ID5。ID5再用Key58组播给子组成员。采用这种结构有2个好处：1）能够进一步减少同谋破解的概率，因为4个成员必须要在一个子组尽可能破解所有密钥；2）减少单播的次数，用2次组播代替n/4次组播代替n/2次，减少了通信量。

5 结束语

本文提出的DKGR算法是在密钥链[8]和左右向性密钥[9]的基础上进行了融合和改进，吸取了两者的优势，通过增加少量的存储成本减少通信量。本算法与传统的密钥链算法相比，增加少量的存储开销，从而减少网络通信量。在分布式自组网的环境下，针对网络拓扑结构的频繁改动，在快速更新组密钥的前提下，减少整个网络的通信量，提高整个网络的健壮性。因此，该算法在小型移动自组网中的组密钥管理是行之有效的。

[1]屈劲，葛建华，蒋铭.安全组播密钥批更新算法研究[J].电子学报，2003，31（7）：1046-1048.

[2]徐恪，徐明伟，董晓虎.组播密钥管理的研究进展[J].软件学报，2004，15（1）：141-150.

[3]Zhou L D，Hass Z J.Securing in ad-hoc networks[J].IEEE Networks，1999，13（6）：24-30.

[4]Wong C K，Gouda M，Lam S.Secure group communications using key graphs[J].IEEE/ACM Transactions on Networking（TON），2000，8（1）：16-30.

[5]Basagni S，Herrin K，Bruschi D，et al.Secure pebblenets[M].In:Proc.of the 2001 ACM Int'l Symp.on Mobile Ad Hoc Networking and Computing，New York:ACM Press，2001.

[6]Diffe W，Hellman M E.New directions in cryptography[J].IEEE Trans.Inform.Theory，1976，IT222:6442654.

[7]秦科，周明天，刘乃琦.组播密钥管理方案的新研究[J].计算机应用研究，2006（08）：142-154.

[8]林林，李学明，陈勇.无线网络中动态组密钥管理方案[J].计算机工程与应用，2007，43（5）：133-136.

[9]唐扬，兰巨龙.一种新的组密钥管理算法[J].计算机科学，2008，135（111）：89-93.