Efficient Group Rekeying Based on Application-Layer Multicast Tree

　　CHEN Xu-dong1，DU Yu-yang2

　　(1.Institute of  Command Automation, PLA Univ.of  Sci&Tech., Nanjing, 210007, China,
　　2.PLA Institute of Communication, Xi’an, 710106, China)

　　Abstract: In secure group communications, there are both rekey and transpont. We propose to use application-layer multicast to support concurrent rekey and data transport. Rekey traffic is bursty and requires fast delivery. It is desired to reduce rekey bandwidth overhead as much as possible since it competes for bandwidth with data traffic. Towards this goal, we propose a multicast scheme that exploits proximity in the underlying network,and We further a rekey message splitting scheme to significantly reduce rekey bandwidth overhead at each user access link and network link. We formulate and prove correct for the multicast scheme and rekey message splitting scheme. having conducted extensived simulations to evaluate our approach, Our simulation results show that our approach can reduce rekey bandwidth overhead from several thousand encrypted new keys (encryptions, in short) to less than ten encryptions for more than 90% of users in a group of 1024 users.

　　Keywords: security communication; rekye; group; application-layer multicast

　　1  引 言

　　在许多已有的因特网应用中，在网络应用中网格计算、电话会议、多方游戏,以及分布联机模拟等，都得益于安全组通讯模型。该模型中，有一个密钥服务器，组成员共享一个对称密钥,即“组群密钥”，该密钥只对组成员公开，每个用户是一个终端主机。组群密钥用于组成员间加密数据传输，限制一些只对组成员公开资料的接入。组群密钥由组群密钥管理系统分发，该系统能够不间断的改变组群密钥，即对组群密钥进行更新。

　　近年来，组群密钥管理设计研究取得许多成果，尤其是密钥树方法。该方法能够将服务器处理组群密钥更新的时间复杂度从O(N)降低到O(logd (N))(这里N是组群的大小，d是密钥树的层)。

　　为了进一步降低服务器处理时间和带宽开销，提出了周期分批密钥更新方案。在分批密钥更新中，密钥服务器将一个密钥更新间隔内出现的加入或离开请求作为一批来处理，并且在密钥更新间隔结束时，产生一个密钥更新消息。该密钥更新消息将被立即发送给所有用户，该过程要求尽可能快地完成，以确保整个组群的接入控制。但是这样，就会产生突发密钥更新流量。

　　使用应用层多播(ALM)技术来支持密钥更新和数据传输产生新问题，即突发的密钥更新流量会与数据传输竞争有限的带宽， 增加链路的负担。例如，位于应用层多播树根部用户的接入链路，该段链路拥塞会引起下游用户的数据丢失。因此，这就需要尽可能地降低密钥更新的带宽开销。

　　使用应用层多播技术支持组群密钥更新，可以进行重新命名和选路。方案中，每个用户都分配由D个数字组成的全局惟一的ID。所有用户ID和他们的前缀被组织成树结构，称为ID树。此外，每个用户维护一个用以支持选路的“邻居表”，嵌入在多播树中的邻居表是建立在密钥服务器和每个用户之上的。因此，不论是密钥服务器还是用户都可以通过多播向其他任何一个节点发送消息。同时，提出的多播方案对数据传输也适用。

　　为了支持密钥更新消息的快速分发，用户ID分配遵循底层网络相似性原则。该方案使每个建立在“邻居表”上的多播树具备了拓扑意识，即在相同多播子树上的用户在同一拓扑逻辑区域内。因此，在一个多播过程中，当一个消息从多播源向用户转发时，它只会向用户的方向转发，而不会沿原路返回。

　　为了降低密钥更新的带宽开销，在密钥更新中，用户需要的仅是一个由密钥服务器产生的密钥子集，而不是全部密钥。因此，只需对用户自身或它的下游用户加密。

　　用户如何知道谁是它的下游用户，哪些加密才是需要的呢？为了解决这个问题，对密钥树进行了修改，使它的结构与ID树的结构相匹配。这样，通过检查加密的ID，用户就能够确定一个加密是否是它自身以及它的下游用户所需要的。进一步提出了消息分离方案，可以让用户仅接受它自身或下游用户所需要的加密。这种分离方案能够在用户的接入链路和网络链路上，有效的降低密钥更新的带宽开销。

　　为证明多播方案与密钥更新消息分离方案的正确性，进行广泛的模拟。结果显示，在一个有226个用户的组中，通过多播路径，向每一个用户发送消息，发现78%的用户的时延不到单播时延的一半。而且，运用密钥更新消息分离方案，在一个有1024个用户的组中，超过90%的用户能够有效降低密钥更新带宽开销。

　　2  系统设计

　　此处对系统的设计进行说明。假设一个固定的由N个用户组成的组。表1显示了本文使用的一些符号。

　　2.1 ID树

　　组中的每个用户都分配了一个基于B的由D位数字组成的全局惟一的ID(B>0,D>0)。数字从左到右，最左边的数字位编号为0。本文中D=5，B=256，所有的用户ID号和他们的前缀都被组织成相应的树结构。

　　定义1 给定的一组用户，其相应的ID树定义如下：

　　第0层是一个单独的节点，即根节点，它的ID号是一个空字符，记为“[ ]”；

　　在第i层，1≤i≤D，每个节点都有一个全局惟一的ID号(由i位数字组成的字符串)。如果在组中存在一个用户u，x是u.ID的前缀，那么该节点ID为x，并存在于第i层。在第i层ID号为x的节点是位于第i-1层节点的儿子，其ID是x为前缀。

　　ID树中，一个子树如果它的根位于i(0≤i≤D)层的节点上，那么它就是一个i层ID子树。子树ID号的定义为子树根节点的ID号。如果用户的ID号等于ID子树上某叶节点的ID号，则该用户从属于该ID子树。
　　定义2 给定的一个用户和一个ID树，如果一个子树根的父节点是一个叶节点的祖先，该叶节点的ID号等于u.ID，并且子树ID号的最后一个数字是j，则第(i+1)层的子树就是u的(i,j)-ID子树。0≤i≤D-1,0≤j≤B-1。

　　由定义2可以得出，对于每个从属于u的(i,j)-ID子树的用户w，w.ID必须和u.ID共用前i位，并且w.ID的第i位(即，w.ID[i])为j。

　　5个用户组成的ID树，用户的ID号分别为“[0，0]”，“[0，1]”，“[2，0]”“[2，1]”，“[2，2]”，在这棵ID树中，用户，从属于(1，1)-ID子树。这里，ID树并不是由密钥服务器或用户维护的数据结构。

　　用户的ID号分配遵循在底层网络中的相似性，即用户的ID分配应使得在同一层ID子树上的任意两个用户之间的往返时延小于或等于某一时延阈值，i=1，2，...，D-2。这样，属于同一层ID子树上的所有用户将会在一个以时延为直径的拓扑逻辑区域内。这些用户被隔离在i层ID子树的众多儿子(i+1)层中，这样，所有属于相同子层(i+1)的用户都在同一个以时延为直径的拓扑逻辑区域中。

　　2.2 邻居表