抗合谋攻击能力可调的有状态组密钥更新协议

敖 丽，刘 璟*，姚绍文，武 楠

(1．云南大学 软件学院，昆明650500; 2．云南大学 信息学院，昆明650500)

(*通信作者电子邮箱liujing@ynu．edu．cn)

0 引言

组密钥更新作为组播安全研究中的关键，用于解决成员动态变化(加入或离开)时，组控制器(Group Controller，GC)如何高效和安全地分发一个新的组密钥(Group Key，GK)给合法用户的问题，并保证密钥更新过程中的前向安全性和后向安全性［1］。在有状态的组密钥更新协议［2－4］中，大多数协议是基于逻辑密钥分层(Logical Key Hierarchy，LKH)协议发展而来的。最早的LKH协议是由Wong等［5］和Wallner等［6］分别提出。文献［7］中证明了LKH协议在抗完全合谋攻击时，通信开销的下界是O(log n)，n为组规模大小。所以，不折中安全性和其他性能(存储开销、密钥更新效率)，使通信开销低于O(log n)是不可能的。抗合谋攻击主要针对组密钥管理中安全威胁提出的系统需求［8］。在一些高度敏感的数据中，抗完全合谋攻击是一种较强的安全性要求，但是，在一些资源受限(无线传感器网络［9－10］)或者商业应用(付费电视［11］、即付即看(Pay Per View，PPV)［12］)场景中，对安全性要求相对较弱，而对通信开销更为敏感，组成员频繁的加入(离开)，会给GC带来巨大的通信开销，所以，为了节省通信开销，这些应用场景中的用户愿意容忍一定级别的安全性，通过牺牲抗合谋攻击能力来降低通信开销。

基于此，Fan等［11］提出了一种混合的组密钥更新协议(Hybrid Structuring Of Receivers，HySOR)。HySOR 协议在LORE(Linear Ordering Of Receivers)协议的基础上结合LKH协议，实现了通信开销和抗合谋攻击之间的权衡。但是，LORE是基于双哈希链设计的协议，HySOR协议的计算复杂度随着组规模n呈线性变化。在文献［13］中，利用多密钥分发(Multicast Key Distribution，MKD)协议和LKH协议构成的混合方案中，MKD仍然是基于双哈希链的协议。Liu等［14］基于“子集－覆盖”框架提出了排外子集覆盖框架(Exclusive Complete Subtree，ECS)，在此框架上，构造一个混合的无状态组密钥更新协议，该协议适合于资源受限或者商业应用场景。

本文在文献［14］的基础上，针对有状态的组播通信，设计并实现了一种混合的组密钥更新协议(Hybrid Stateful Exclusive Complete Subtree，H-SECS)。H-SECS协议是基于LKH协议和有状态的完全排外子树(Stateful Exclusive Complete Subtree，SECS)协议设计的，可以在 LKH协议和SECS协议之间进行调整，达到抗合谋攻击能力和通信开销之间的权衡。H-SECS协议的一个极端是LKH协议，具有完全抗合谋攻击的特点;另外一个极端是SECS协议，具有常量通信开销但是只能抵抗一个用户攻击。本文对H-SECS协议的抗合谋攻击能力、通信开销进行了仿真实验分析，结果证明了H-SECS协议的通信开销和抗合谋攻击能力可以在LKH与SECS之间进行调控。

1 SECS协议

Liu 等［14］基于排外密钥［15－16］设计了 SECS 协议。SECS是一种有状态的组密钥更新协议，通信开销为O(1)，但是只能抵抗单用户攻击。SECS协议主要包括两个算法:个人密钥分配算法和组密钥更新算法。

1．1 个人密钥分配算法

个人密钥分配算法满足正确性和密钥的不可区分性，所以用3个伪随机生成器(Pseudo-Random Number Generator，PRNG)［17］(GL，GR，GM) 来生成密钥。根据组播中 n个成员组成的集合 U={u1，u2，…，un}，经过(GL，GR，GM) 自顶向下生成一棵平衡二叉树。二叉树的叶子节点与成员u直接相连。在平衡二叉树中，密钥的分配如下:任意中间节点i，有一个种子节点S。则S2i=GL(Si)代表i节点的左孩子(2i)的种子;S2i+1=GR(Si)代表 i节点的右孩子(2i+1)的种子;Ki=GM(Si)代表i节点的排外密钥。将二叉树中从叶子节点回溯到根节点所经过路径上的排外密钥称为路径密钥。成员u的排外密钥集为u的路径密钥的集合;用Iu表示GC为u分配的个人密钥集，则Iu是所有路径密钥上的兄弟密钥。根据排外密钥的定义，u不能计算出它的路径密钥，但是，u可以推导出这棵密钥二叉树上其余的密钥。

1．2 组密钥更新算法

定义t时刻合法成员的集合为St(StU)，撤销者集合Rt(Rt=USt)。S(t+1)表示(t+1)时刻成员动态变化后的集合;GKt表示当前的组密钥;GK(t+1)表示更新过的组密钥;“”表示“组播”;EK(text)表示用密钥K加密 text。对于SECS协议，成员的加入(离开)，组密钥都需要进行更新。

1)成员加入。当成员u'在t时刻加入集合U时，有两种方案。第一种方案是GC通过安全渠道给合法用户广播密文块，即:GCS(t+1):EGKt(GK(t+1))，只有知道GKt的用户可以对密文块进行解密，得到GK(t+1)。本文为了保证信息的机密性，采用了哈希函数的消息认证码(Hash-based Message Authentication Code，HMAC)函数［18］，使得用于组通信的密钥和用于加密的密钥不是同一个密钥，本文后面提到的GK是已经处理过，用于加密的GK。第二种方案是通过一个公开的单向哈希函数(SHA-1)［19］来更新 GK(t+1)，合法成员在收到GC广播的更新消息时，直接通过哈希函数计算出新的组密钥GK(t+1)。

2)成员离开。假设t时刻离开的成员集合是L={i1，i2，…，im}，GC首先计算出离开成员的排外密钥{Ki1，Ki2，…，Kim}，然后将这些排外密钥和GKt异或后作为会话密钥来加密GK(t+1)，GC将密文广播给合法成员，密文结构如下:

用C表示密文块，DK(C)表示用K来解密密文块C。当用户 u∈ S(t+1)接收到更新消息〈i1，i2，…，im，C〉，根据排外密钥的定义，u根据密钥集Iu中推导出排外密钥Kij;所有的排外密钥进行异或运算:Ki1⊕Ki2⊕…⊕Kim⊕GKt计算出新的会话密钥。最后解密得到组密钥 GK(t+1)，解密结构如下:

2 H-SECS协议

结合LKH协议抗完全合谋攻击的特点和SECS协议具有常量通信开销的优势，设计并实现了一种混合的组密钥管理协议(H-SECS)。该协议的密钥管理是一个两层的树型结构，为了描述方便，第一层称为LKH协议树;第二层称为子组树(Division Tree，DT)，DT沿用SECS协议树的设计规则。HSECS协议可以分为成员初始化、成员加入和成员离开3个阶段。表1列出H-SECS协议中用到的部分符号。

表1 H-SECS协议中符号说明Tab．1 Symbol definition of H-SECS protocol

2．1 成员初始化

假设n个成员建立组通信。首先，GC建立一棵LKH协议树，包含d个叶子节点，树中每个节点对应一个密钥，树的叶子节点与子组一一对应。然后，在每个子组里建立一棵SECS协议树，简称DT。DT中包含m(m=n/d)个叶子节点，其中，如果n不能整除d，则前几个子组里DT的叶子节点为m，最后一个子组叶子节点不足m。DT中每个叶子节点与组成员一一对应。在建树的过程中，采用哈夫曼编码为树的每个节点进行编号，规定从根节点开始，左分支为0，右分支为1，根节点的编号为0。对于DT中的每个成员，在叶子节点编号的前面加上子组号Di(Division)，其中Di的数值范围是0～ 232－1。

由于H-SECS协议的密钥管理是一个两层的树型结构，所以，在DT中的每个成员存储两组密钥:一组是所在子组对应的LKH协议树上的辅助密钥;另外一组是成员对应的DT中的私人密钥。辅助密钥是子组Di对应的LKH协议树上叶子节点到根节点路径上所有节点对应的密钥;私人密钥是成员u所对应的叶子节点到DTi树上根节点路径上所有节点对应的兄弟节点的密钥，其中，LKH协议树中根节点的密钥为GK，组通信中所有合法成员共享GK。如图1所示，H-SECS结构图中共有15 个成员。分为5 个子组:D0、D1、D2、D3、D4;每个子组中包含一棵 DT，分别为 DT0、DT1、DT2、DT3、DT4;DT的叶子节点对应3个成员 u1、u2、u3。组密钥GK是K1。u2D1表示D1子组中的u2用户，它的ID号是1|001，第一位的1代表子组号，后面是成员对应的叶子节点的编号。u2D1用户有两组密钥:一组是 LKH 协议树上的辅助密钥 {K1，K2，K4，K9}，辅助密钥被该D1子组里成员共享;一组是对应的私人密钥{SK3，SK4}。

图1 H-SECS结构示例图Fig．1 Schematic of H-SECS protocol

2．2 成员加入

加入组播的成员有两种:一种是新加入组播中的成员;另一种是由于网络故障或者其他原因被撤销的成员，重新请求加入组播通信。新成员请求加入组通信时，步骤如下:

1)GC为加入成员在整个密钥树中分配对应位置。

重新请求加入组播通信的成员，GC为这个成员分配到以前的节点位置，并且将节点对应的身份、私有密钥、辅助密钥分配给该成员。如果子组有成员加入，那么这个子组变为活跃的子组;否则，称为不活跃的子组。对于新加入组播的成员，为了使通信开销小并且提高抗合谋攻击能力，GC随机选择LKH协议树中叶子节点对应的子组Di时，有以下两种情况:

①如果选择的Di是对应的LKH协议树中最小深度的叶子节点，则将这个叶子节点分裂成两个节点并且新创建一个子组，子组中包含一棵DTi树。其中，左孩子节点与Di相连，右孩子节点与新创建的DTi树相连。将新成员插入到这个新的子树DTi中，并且将插入成员所在的子组标记为活跃的子组。

②如果选择的Di对应的不是LKH协议树中最小深度的节点，为了保证子组中对应的DTi树平衡，GC从所选子组中对应DTi树中深度最小的叶子节点中随机选择一个叶子节点，将这个叶子节点进行分裂，左边的节点与原来的成员相关联，右边的节点对应的是新插入成员的位置。如果选择到的Di为不活跃的子组，由于新成员的加入，子组Di变成活跃子组。图2是在图1中加入一个成员，GC选择到D3子组后HSECS结构图对应的LKH协议树变化。此时，D5子组被标记为活跃的子组，D5子组下面对应DT5树，DT5树只有一个节点，这个节点与新插入的成员对应。

2)GC生成GKt+1并且广播密钥更新消息。

假设t时刻要求加入组播通信的节点集合用J表示，St+1(St+1=St∪J)表示加入成员后合法成员的集合。为了保证后向安全性，需要更新加入成员所影响的节点密钥并且分发私人密钥给加入的新成员。

图2 加入子组D5后LKH协议树变化Fig．2 LKH tree view of joining subgroup D5

组密钥更新步骤如下:

①为活跃子组生成密文块。为了保证信息的机密性，GC需要为活跃子组中的成员分发两种密文块:逻辑密文块和SECS对应的密文块。

发送逻辑密文块 GC首先统计每个活跃子组对应的辅助密钥，然后使用活跃子组对应的LKH协议树中儿子节点加密父节点的方式生成密钥加密密钥(Key Encryption Key，KEK);最后，将加密节点的身份ID、被加密节点的身份ID和对应的KEK封装成逻辑密文块(Logical Key Hierarchy Cipher Text Block，LKHCB)发送给组播中合法成员。

发送SECS协议对应的密文块 GC使用以前的组密钥GK来加密活跃子组对应的LKH协议树上的叶子节点密钥，即:EGK(Ki)，然后将EGK(Ki)发给合法成员。在图2中，活跃的子组为D5，对应LKH协议树上所影响节点的密钥是{K1，K3，K6}，本文用{K1'，K3'，K6'} 表示已经更新过的密钥。则密钥的更新产生密文块LKHCB为:

LKHCB1={0100，010，EK6(K6')}

LKHCB2={0101，010，EK10(K6')}

LKHCB3={010，01，EK6'(K3')}

LKHCB4={011，01，EK7(K3')}

LKHCB5={00，0，EK2(K1')}

LKHCB6={01，0，EK3'(K1')}

K1'为更新过后的组密钥GK(t+1)。GC将逻辑密文块信息和SECS对应的密文信息封装成密文(Cipher Text，CT)，发送给活跃子组中合法成员。密文结构如下:

②为不活跃子组生成密文块。对于不活跃子组中的成员，GC发送的密文遵循SECS协议成员加入的密文更新规则。GC使用以前的组密钥GK来加密更新过的组密钥，即:EGK(GK(t+1))，然后将EGK(GK(t+1))发给不活跃子组中成员。

3)成员解密密文更新消息。

组播里合法成员到密文CT。对于非活跃组里的成员，利用其知道的GK，直接解密出GK(t+1)。对于活跃子组的成员，根据其所知的GK，解密出对应的LKH协议树叶子节点更新过的密钥，依次根据接收到的密文块解密出GK(t+1)。假设在图2中，成员解密，则解密信息如下:根据GK密钥K10;根据K10，解密密文块 LKHCB2，获取 K6';根据 K6'，解密 LKHCB3，获取 K3';根据 K3'解密 LKHCB6，获取到 GK(t+1)，即 K1'。

2．3 成员离开

假设t时刻离开的成员用集合L={i1，i2，…，im}表示。为了保证前向安全性，需要更新离开成员所影响的H-SECS结构树中的密钥。如果成员离开时，则更新处理步骤如下:

1)根据退出成员的ID定位到退出成员所在子组里的位置，删除DTi树中代表该成员的叶子节点，并且将这个节点标记为不可用的节点，由于成员的离开，这个子组变成不活跃的子组。如果DTi树中的所有叶子节点都为不可用的节点，则删除LKH协议树中代表DTi组的叶子节点。GC对LKH协议树进行调整，使LKH协议树保持最优状态。图3所示是图1中LKH协议树删除组D1后调整后的图。

图3 删除组D1后LKH协议树图Fig．3 LKH protocol tree after deleting subgroup D1

2)成员退出密钥更新可以分为两个步骤:

更新子组对应LKH协议树上影响节点的密钥，过程遵循LKH协议的密钥更新过程。更新退出成员所在DTi树上密钥，这个过程遵循SECS密钥更新规则，步骤如下:

①建立 Steiner树［13］。对 (UL) 建立 Steiner树，用ST(UL)代表Steiner树。假设图4中是某个子组中离开成员集为L={u1，u2，u3}，ST(UL)树是由虚线相连的节点组成;

②查找覆盖子树。对比活跃的DTi树和ST(UL)树，覆盖子树为当前组的DTi树除去当前组的ST(UL)，即DTi－ST(UL)。图4中覆盖子树由实线相连的节点组成。

③更新与分发密钥树中相关节点的密钥。覆盖子树所对应的排外密钥与组密钥异或后形成会话密钥，用会话密钥来加密DTi树中对应LKH协议树的叶子节点Kω。将排外密钥的ID，加密形成的密文封装成密文块(Division Cipher Text Block，DCB)，其结构如下:

将活跃子组形成的密文块DCB和对应的子组号Di以及形成的逻辑密文块封装成密文(Division Cipher Text，DCT)。GC将DCT发给组播通信中合法成员。

图4 子组里的完全排外子树图Fig．4 Complete exclusion subtree in the subgroup

3)组成员解密密文更新消息。

组播里合法成员接收到密文DCT。对于活跃子组里的成员，组成员根据LKH协议树的密钥检索出密文块，获取相关的密钥，最终解密出GK(t+1)。而对于不活跃子组里的合法成员，解密GK(t+1)有以下两个步骤:首先对DCB解密，根据排外密钥的定义，对于每个ij(j=1，2，…，m)，u可以从个人密钥集Iu中推导出Skij，根据这些Skij计算出DCB的会话密钥，即Sk1⊕Sk2⊕…⊕Skm⊕GKt;然后解密出对应LKH协议树上新更新过的叶子节点的密钥 Kω，解密结构为:DSk1⊕Sk2⊕…⊕Skm⊕GKt(C); 最后对逻辑密文块解密，根据 LKH 协议树的解密规则来依次解密。最终，获取到组密钥GK(t+1)。

2．4 抗合谋攻击能力分析

对于SECS协议，两个恶意的撤销用户可能就会破坏组的前向安全性，而在H-SECS协议中，k个合谋者成功攻破组密钥的条件是当且仅当k个合谋者中至少有两个合谋者被分在同一个子组中。用Pk表示k个合谋者中至少有两个合谋者被分配在同一个子组中的概率，根据文献［11］有式(1):

其中:n是组规模，d是子组数目。在给定n和k时，Pk随着d的增大单调递减，即:d越大，至少有两个合谋者被分配在同一个子组中的概率Pk就越小。在组规模一定时，d越大，安全性越好，但是d的增大，会导致带宽的增大。本文提出的H-SECS方案中，用户可以根据不同的安全性要求，调整d的大小，在合谋攻击和通信开销之间进行一个最优化的权衡:当d=1时，H-SECS协议变成SECS协议，此时每个成员加入(离开)的通信开销是O(1)，但是只能抵抗一个用户攻击;当d=n时，H-SECS协议变成LKH协议，此时每个成员加入(离开)的通信开销是O(log n)。

3 性能仿真实验

在Microsoft Visual Studio 2013环境下，利用OpenSSL(版本号:1．0．1t)加密库中的高级加密标准128位(Advanced Encryption Standard-128 bit，AES-128)和安全散列算法256位(Secure Hash Algorithm-256 bit，SHA-256)来对 H-SECS 方案进行仿真。在H-SECS协议中，成员的加入(离开)时，组密钥更新是影响通信开销的主要因素;而对于抗合谋攻击能力则是由子组数目决定;首先，对子组数目和Pk之间变化进行仿真;然后，在加入(离开)成员不同时，对LKH、SECS、H-SECS三种协议的通信开销进行仿真实验。

在仿真实验中，参数的配置k=5;n=32768;P5代表5个合谋者至少有两个合谋者被分在同一个子组中的概率。P5=0代表完全抗合谋攻击;P5=1代表只能抵抗单用户攻击。图5是子组数目d与P5之间的关系图，可以看出当子组d逐渐增大时，H-SEC协议的抗合谋攻击能力逐渐增强。当d=n时，H-SECS协议是完全抗合谋攻击的，此时，H-SECS协议变成LKH协议。当d=1时，H-SECS协议变成SECS协议，安全性最弱。

测试加入(离开)成员不同时，LKH、SECS和H-SECS三种方案的通信开销。为了更好地体现成员变化的随机性，对于加入(离开)成员数目不同时，本文均进行20次计算，然后取算数平均值作为最终的测试结果。测试中的Pk、d、k、n如2．4节所述。测试参数配置如表2所示:其中P5=0．147 6(d=64，m=512) 和 P5=0．0094(d=1024，m=32) 代表H-SECS协议的两个中间点。成员加入测试的结果如图6所示，成员离开测试的结果如图7所示。

图5 H-SECS协议中P5与子组的关系Fig．5 Relationship between P5and subgroups in H-SECS protocol

表2 测试参数配置说明Tab．2 Test parameter configuration instruction

图6 三种协议中成员加入通信开销的对比Fig．6 Communication overhead comparision of three protocols when users join

图7 三种协议中成员离开通信开销的对比Fig．7 Communication overhead comparision of three protocols when users depart

由图可以看出，无论是成员加入还是成员离开，LKH协议的通信开销最大，而SECS协议的通信开销最小。对于H-SEC协议的通信开销可以随着子组数目d在SECS协议和LKH协议之间进行调控，即:可以在O(1)和O(log n)之间进行调控。

仿真实验中，子组数目d越大，H-SEC协议抗合谋攻击的能力就越强，通信开销就越接近LKH方案的通信开销;而子组数目d越小，H-SEC协议抗合谋攻击能力就越弱，通信开销就越接近SECS方案的通信开销。所以，根据不同应用场景的安全级别，H-SEC协议可以通过设置子组的数目，将抗合谋攻击能力在SECS协议和LKH协议之间进行调整，最终达到抗合谋攻击能力和通信开销之间的权衡。

4 结语

本文基于SECS协议和LKH协议提出并实现了一种有状态的组密钥更新协议(H-SECS)。从理论分析和仿真结果中可以看出该协议的通信开销可以在LKH协议和SECS协议之间进行调整。因为在频繁组密钥更新的场景中，LKH协议所产生的通信开销也是不容小觑的，所以在权衡安全性的条件下，H-SECS协议可以在抗合谋攻击能力和通信开销上作出最优的权衡，实现通信开销在SECS协议和LKH协议通信开销之间的调整。