安全组播中的密钥分配.doc

目 录摘要21. 引言32. 相关理论定义介绍33. 组播环境下的密钥管理43.1 SKDC密钥管理方法53.2基于密钥分级树的密钥管理方案53.3基于Huffman和布尔函数化简的密钥管理方案63.3.1 Huffman密钥二叉树的构建63.3.2基于Huffman密钥分层树进行密钥管理的分析73.3.3布尔函数在其中的应用84. 结束语9参考文献10安全组播中的密钥分配摘要：组播以其独特的优势，在网络通信方面的应用越来越广泛，但随之而来的就是安全问题，其中密钥管理是最基本的问题之一。本文研究了安全组播中的密钥管理问题。介绍了现有的两种主要解决方案，即SKDC方案和密钥树管理方案，并分析了它们的不足之处，指出基于密钥树的研究方向，在此基础上提出基于Huffman密钥分级树的密钥管理方案，将布尔函数的分析方法运用其中使管理简便化。并对该方案的性能从密钥管理的存储空间和密钥刷新通信量两个方面，给出了相应的分析。关键词：组播; 密钥管理; 赫夫曼树; 布尔函数Abstract: Because of the advantage of multicast, it becomes more and more popular in the network communication. This paper studies the problem of key management in secure multicast. It introduces two main schemes including SKDC and the key tree to solve this problem, and analyses their demerits. On the basis of the scheme of key tree, it puts forward a key management scheme using Huffman hierarchy and Boolean function minimization techniques. From the aspects of the number of keys held by each user and the cost of re-keying, this paper gives some analysis.Key words: multicast; key management; Huffman tree; Boolean function1. 引言在网络的传输中，主要采用了三种数据的传送方式：单播、广播和组播1。组播以其独特的优势，即带宽比传统的单播占用的要小，同时它可以在不同的网络结构上实现，也可以在不同的网络层次上实施，并且它比广播系统更易于管理，易于了解组员的应用情况，使其在应用范围上极其广泛，成为一种高效、快捷的数据传输方式。但是，随之而来的是网络安全问题，即如何为彼此互联的不同团体用户群组提供安全的访问机制。组播通信的安全性较比单播传播更为复杂。归纳起来，组播通信的安全性主要体现在三个方面：访问控制、数据源认证以及可用性维护。其中，访问控制是最基本的安全性保证。通常情况下，在所有的多播群组成员之间维护着一个不为非群组成员所知的公共密钥即组播密钥，群组成员之间的所有通信均使用该群组密钥加密，这样组播中的密钥管理问题随之产生了，在一个具有动态成员关系的群组中要保证当群组成员动态离开或者加入时，群组密钥更新到每个成员。本文重点研究了组播环境下的密钥管理问题，提出了基于Huffman型密钥二叉树以及布尔函数化简技术的密钥管理方案，讨论了如何建立密钥二叉树，并且对于此方案的特点和优势给出了相应的分析。2. 相关理论定义介绍安全组播通信是指在参与保密通信的所有组成员中构建一个公共密钥（即为组播密钥），该密钥是根据组播密钥管理协议（GKAP）建立起来的。GKAP2应该包含的属性有：（1） 保密性：由于组播成员“加入”和“离开”事件的发生，产生了“向后安全”和“向前安全”的问题。GKAP提供“向后安全”的关键是新成员接受的所有信息与加入前组中的任何信息无关，新成员和组外成员一样不能利用它所接收的新密钥获得以前的保密信息。同样，GKAP提供“向前安全”的关键是组成员离开后就和组外成员一样，不能再获得组播通信的保密信息。（2） 完整性：GKAP确保信息不被组外攻击者修改或伪造。即使组外用户无攻击企图时，也不能对构建组播密钥产生任何影响。（3） 安全认证：GKAP对组成员安全认证保证只有合法用户加入组播通信，这同时也实现了对组播密钥的认证。 安全组播环境下密钥管理的性能参数包括：密钥管理的存储空间、密钥刷新通信量、抗冲击性以及计算开销。本文主要讨论的核心是密钥管理中的密钥分配更新问题，因此本文讨论的方法也就侧重从前两个方面进行衡量3。 赫夫曼（Huffman）树，又称最优树，是一类带权路径长度即从树根到每一结点的路径长度之和最短的树。3. 组播环境下的密钥管理 对于组播的安全来说，密钥管理是一个重要却十分困难的问题。首先必须在通信主体之间建立一个或多个共享密钥，以对传送信息进行加密。而用户在进入或者退出时要求对密钥进行更新。依此，必须采用针对于组播的新的却有效的密钥管理技术。IKE是一种针对单播通信情况的点到点的密钥管理协议。单播通信双方在会话前通过IKE进行协商，一次完成会话密钥的安全分发，第三方不可能得知通信双方的会话密钥。通信中，其中一方的退出引起该会话的结束和会话密钥的失效。但是组播通信的情况与单播通信不一样，每一个成员的加入和退出都可能引起组会话密钥的重新更换，以保证组播通信的向前安全和向后安全，因此IKE不适合为组播通信提供密钥管理。目前，密钥管理的研究通常基于集中式管理和分布式管理两类基本模型。后者的特点是所有群组成员通过密钥协商来共同建立组播密钥，其缺点是计算复杂导致延时很大，故难以适用于成员关系频繁变化的大规模动态群组，因而不在本文的讨论范围之内。集中式密钥管理模型的特点是存在一个专门的组控制者负责生成组播密钥，并通过特定算法分发给规模为N的群组中的每个成员，是一种被广为采用的方法。下面就基于集中式模型进行讨论。3.1 SKDC密钥管理方法简单密钥分发中心SKDC3（simple key distribution center）是最为直观的密钥分配算法。它是一种简单的、单层的密钥管理方式。在SKDC中，每一个成员只有两个密钥自己的私钥和组播通信的组播密钥。当成员向组控制器申请加入组时，组控制器首先验证成员的身份，确认后为该成员产生一个新的成员节点并产生它自己的私钥，并通过单播的方式传送给该成员。然后，组控制器会产生一个新的组播密钥，用新成员的私钥加密后传送给新成员，新成员获得新的组播密钥后就可以解密组通信了。同时组控制器通过旧的组播密钥加密分发新的组播密钥，完成剩下成员的新组播密钥的更换。当成员退出时，原来的组播密钥既不能再继续使用，也不能用于新密钥的分发，这时候在组控制器产生了新的组播密钥以后就只能分别通过剩下成员各自的私钥加密后分发。这样，添加一个成员需要组控制器执行N+1次加密传送，排除一个成员需要执行N-1次加密传送。很容易对SKDC作算法渐进分析，它的存储复杂度和通信复杂度都是(N)，故只适合小规模的组通信。可以看出，rekey通信复杂度和密钥存储复杂度是密钥管理的两个重要方面，其中以降低rekey通信次数尤为重要，一方面是为了节省网络带宽，另一方面是为了减少密钥更新时的延时。通信复杂度是当前组播应用的最大瓶颈，降低通信次数是当前密钥分配研究所致力的目标。3.2基于密钥分级树的密钥管理方案密钥分级树方案是通过引入中介即密钥加密密钥来构造逻辑结构，故被称为逻辑密钥层次4，由此派生而出的一系列方案统称为树型密钥管理。它可以弥补SKDC方案的不足，大大减少密钥刷新的通信消耗，提高密钥更新效率。图1所示的是一棵拥有8个叶节点的二叉密钥树，对应于一个成员个数为8的群组：树根代表组控制器拥有的组播密钥，如图1中的sk；叶节点代表组成员各自拥有的私钥，每一个叶节点对应于一个群组成员，如图1中每一个Mi对应于keyi（i=1,28）；虚拟的内部节点对应于中介密钥加密密钥，如图1中带阴影的那些中间节点，用于组播密钥更新时向组内特定范围的成员传递新密钥，新密钥既包括组播密钥也包括那些需要更新的密钥加密密钥。每个成员拥有从叶子到根所经过的路径上的所有节点密钥，例如成员M1所拥有的密钥有：sk，key1234，key12，key1，其中sk为组播密钥，key1234和key12是从组控制器处获得，并用来限制密文消息只组播到包含M1在内的有限集合，key1为M1的私钥。采用这种技术，当成员加入时，密钥的更新与SKDC的情况基本相同。而当成员退出时，只需要对该成员相关的密钥加密密钥和组播密钥进行更新，以保证退出的成员不可能得知将来的组播内容。这时对于一课度数为d，深度为logdN的密钥树，更新组播密钥所需的通信次数为（d1）logdN，与SKDC相比，树型密钥管理牺牲密钥存储开销换来了通信开销8。3.3基于Huffman和布尔函数化简的密钥管理方案Huffman密钥二叉树是密钥分级树的一个特例。构建Huffman密钥二叉树并采用布尔函数化简，不仅可以保持密钥树在密钥更换时通信性能上的优势，还可以有效减少密钥存储空间并易于管理。3.3.1 Huffman密钥二叉树的构建Huffman密钥二叉树的构建主要是依据用户组的密钥概率分层结构。密钥概率分层结构5,6是根据用户在密钥更新周期里，以一定概率离开组播组而得以划分的。设组用户数为n，用户集U1,2,3 ,n代表组播用户全体，密钥更新周期内仅有用户Ui离开组的概率为pi，对于pi满足=1。本文利用Huffman编码方式构造密钥Huffman层次结构，在构造2维Huffman满树时，密钥树从根开始分裂可形成2个叶节点，叶节点每次再分裂可增加1个叶节点，因此如果分裂s次，Huffman满树的总叶片树m应满足公式：m(s-1)*1+2=s+1构造Huffman树，根据用户离开概率对用户进行分组，先将2个用户按离开概率大小排队，概率大的排在右边，概率小的排在左边，将离开概率最小的2个用户分成一组形成一个组节点，并将这2个用户的离开概率相加作为该组节点的概率，再将该组节点和其他用户重新排队，再取概率最小的2个节点或用户组成一个组节点，如此下去直到树根构成一个Huffman树，树根的概率为1，最后给节点安排密钥，这样就构成了密钥Huffman层次结构。这样分配密钥具有最小平均用户密钥量5。下面举例说明，假设存在一个8个用户的组播组。每个用户的离开概率分别为0.05，0.05，0.07，0.08，0.1，0.15，0.2，0.3，分别对应于用户Ui(i1，2，8)设计Huffman密钥分层树，如图2所示。其中方框为组结点，椭圆代表的是用户节点，图形中的值代表相应的概率。其特点是同一层只使用两个密钥，如果用同一符号ki表示，当该节点位于父节点的左树，则为ki（其二进制值标为0）；若位于右树，则为ki（其二进制值标为1）。其中sk表示的组播密钥。每一个成员根据其拥有的从树根到树叶的密钥取值，自动获得一个唯一的UID(Xn-1 Xn-2 X0)，其中Xi是根据相应层的密钥值ki的二进制取值，当密钥为ki时取1，否则为ki时取0，例如图2中用户U1的UID号为0100。3.3.2基于Huffman密钥分层树进行密钥管理的分析采用这种树型结构进行密钥管理的方案，既保留了基于一般密钥树管理时降低密钥刷新时的通信消耗这个优势，又进一步减少了密钥存储开销。对于这样一棵特殊的二叉树，如果树的深度用d表示，那么它可以容纳的成员数最多可达到N2d，由于每一层只有两个密钥，因此组控制器端所需保存的总密钥量2d+1。当d10时，成员最大可为1024，密钥总量为21；当d32时，成员最大数可达到2324G，而密钥总量只有65。下面将说明Huffman密钥分层树在密钥更换时的工作过程，显示出其有效降低密钥更换的通信量以及更换方便性的优势。当成员加入时，同样新成员获得从树根到树叶的所有节点处所代表的节点密钥，其他成员的密钥更新和前面的SKDC以及一般密钥分级树的方法一致，这里就不再重复。而当成员退出时密钥的更换更为简单了，新的组播密钥sk(r+1)只需通过与退出成员无关的中间密钥加密分发即可，而中间密钥的更新通过新组播密钥和旧密钥通过以下函数得到ki(r+1)=f(sk(r+1),ki(r)，通常f()是一个散列函数。下面通过一个实例说明具体过程。为便于说明，将做如下约定：x y:z代表如果y是一个成员，则z为从x到y的信息。如果y是多个成员，则z为从x到y的所有成员的信息（可以通过组播或单播传送）。keysx代表用密钥x加密keys，keys可以是多个密钥，此时用逗号隔开。以图2中的成员U1退出时的情况为例来说明，由于成员U1拥有密钥sk，k0，k1，k2，k3，因此，新组播密钥sk(r+1)只需分别通过k0，k1，k2，k3加密分发，成员U1就不能获得，而剩下其他成员至少可以解密其中一条密钥信息，从而所有剩下成员均可以正确获得新组播密钥sk(r+1)。图2中成员U1退出信息，其密钥更换的消息如下：（s代表组控制器）s U3, U4, U6, U8:sk(r+1) k0 s U7:sk(r+1) k1s U5:sk(r+1) k2s U2:sk(r+1) k33.3.3布尔函数在其中的应用根据上面的分析，我们知道每一个用户的UID值和它所拥有的密钥之间有着一一对应的关系，这样为组控制器分析新的组播密钥用什么进行加密分发时提供了便利，在知道了哪一个用户退出组时，根据其UID号取相反的一组密钥即可。Huffman密钥分层树型管理方案，可以方便地将布尔函数的有关理论加以应用，这所带来的便利，在多个用户同时退出时更为明显。在一般的密钥树中，如果有用户需要中途退出组播环境，组播控制器必须一个一个处理，其中有很多的消息是多次重复传送的，这加大了密钥更新时的通信量。在Huffman密钥分层树结构中，当有多个成员同时退出时，可以直接将它们的UID值用布尔函数的相关运算加以分析，既方便又快捷，而且避免了许多冗余信息的传送。下面还是以图2为例来说明，假设成员U1 和U2要同时退出该组。U1 和U2的UID分别为0100和0101，将其做同或运算得1110，就可以知道用来进行加密分发新组播密钥的密钥即是前面三位取反运算后相对应的k0，k1，k2。因为当多个成员退出时UID中相同位置上的值如果相异，则代表密钥树中相应层的两个密钥它们分别具有，就不能再使用该层的任一密钥进行加密传送；相反，如果相同，则代表两个用户都同时不具备某层上的一个密钥，此时该密钥就是所需的密钥之一。从另一个角度看，如果对剩下的成员分析，也非常方便。要解决多个组成员同时退出的问题，就是要找到剩下成员共有的一组密钥组合，任何一个退出的成员的密钥不可能拥有密钥组合中的任意一个，但任何一个剩下成员都能根据自己拥有的密钥计算出其中一个密钥组合来用于新组播密钥的加密分发，此时除了退出的成员以外所有剩下成员都能解密到新的组播密钥7。例如,图2中U1, U2, U5, U7同时退出，可以得到下列等式： m= k0k1k2k3 + k0k1k2k3 + k0k1k2+ k0k1 其中表示逻辑或，对上式进行布尔化简，可以分析得到k0为所需要的密钥。4. 结束语 本文研究在组播环境中的密钥管理问题，通过介绍传统的两种密钥管理方案即SKDC方案和一般密钥分级树管理方案，并分析存在的不足，如SKDC由于它使得密钥更新过程中随着组播规模的扩大通信量呈线性增长，导致它不适用于规模较大的组播环境；而密钥分级树的方案则通过牺牲部分密钥存储开销换来了通信开销。本文在一般密钥分级树的基础上提出了Huffman密钥分层树，引入密钥概率分层结构和布尔函数分析方法，使平均用户密钥量最小，并