（计算机应用技术专业论文）组播密钥管理算法研究.pdf

沈阳航空工业学院硕士学位论文 摘要 大多数的网络应用采用单播传输数据包。随着i n t e r n e t 的普及和发展，产生了许多 新的网络应用，这些网络应用基于组播通信模型。组播传输不仅提高了数据传送效率， 而且减少了网络出现拥塞的可能性。 然而，目前的组播协议缺乏必要的安全机制保证数据传输的安全性，因此安全组通 信将成为当前网络研究的重点之一。为解决组播安全问题，先后出现了多种组播密钥管 理方案。主要功能包括两个方面：一是密钥的分发，另一方面是对密钥进行管理以适应 组成员关系的动态变化。 本文分析总结了组播密钥管理需要解决的主要安全问题，介绍了组播密钥管理方案 的分类情况，列举了几种典型方案，并对不同类型的方案进行了比较和分析。其中重点 阐述了逻辑密钥树和批次密钥更新方法。 在分析逻辑密钥树和批次密钥更新方法性能的基础上，本文提出了改进批次密钥更 新方法，设计了相应的标记算法和模拟实验模型，分析了算法的性能。研究结果表明改 进算法相比批次密钥更新方法在服务器计算开销和密钥树的平衡性方面有所提高。 关键词：安全组通信；组播密钥管理；逻辑密钥树：批次密钥更新；改进批次密钥更新 - i - 沈阳航空工业学院硕士学位论文 a b s t r a c t m o s tn e t w o r ka p p l i c a t i o n sm a k eu s eo fu n i c a s tp a c k e td e l i v e r y m a n ye m e r g i n g a p p l i c a t i o n sa r eb a s e do nag r o u pc o m m u n i c a t i o n sm o d e lw i t ht h ed e v e l o p m e n to fi n t e m e t ， w h i c hi m p r o v e st h ed a t at r a n s p o r tr a t ea n dd e c r e a s e st h ep o s s i b i l i t yo f n e t w o r kc o n g e s t i o n b u tt h ec u r r e n tm u l t i c a s tp r o t o c o l sa r es h o r to ft h es e c u r i n gd a t at r a n s p o r tm a c h a n i s m ， s e c u r i n gg r o u pc o m m u n i c a t i o n sw i l lb e c o m e a l li m p o r t a n ti n t e r a c td e s i g ni s s u e m a n yg r o u p k e ym a n a g e m e n ts c h e m e sa r ee m e r g i n gt os o l v ei t ，w h i c hi si n c l u d i n gt w of u n c t i o n s ：o n ei s h o wt od i s t r i b u t eg r o u pk e y , t h eo t h e ri sh o wt om a n a g eg r o u pk e ya c c o r d i n gt ot h eg r o u p m e m b e r s h i p c a l lc h a n g eo v e rt i m e m a i ns e c u r i t yp r o b l e m so fg r o u pk e ym a n a g e m e n ta r ea n a l y z e d ，t h e ng r o u pk e y m a n a g e m e n ts c h e m e sa r ei n t r o d u c e d ，s o m ea d v a n t a g e sa n dd i s a d v a n t a g e so fe v e r y s c h e m ea r e a n a l y z e d l o g i c a lk e yh i e r a r c h ya n db a t c hr e k e y i n ga r em a i n l ya n a l y z e d ，w h i c ha r et y p i c a l s c h e m e s t h em o d i f i e db a t c hr e k e y i n gi sp r o p o s e db a s e du p o nl o g i c a lk e yh i e r a r c h ya n db a t c h r e k e y i n g r e l a t i v em a r ka l g o r i t h ma n ds i m u l a t i o na t ed e s i g n e dt oa n a l y z et h ep e r f o r m a n c e t h er e s u l t ss h o wt h el a t t e rc o m p a r e dt ot h eb a t c hr e k e y i n gs a v e ss e r v e rc o s ta n db a l a n c e st h e k e yt r e e k e y w o r d s ：s e c u r eg r o u pc o m m u n i c a t i o n s ；g r o u pk e ym a n a g e m e n t ；l o g i c a lk e yh i e r a r c h y ； b a t c hr e k e y i n g ；m o d i f l e db a t c hr e k e y i n g 原创性声明 本人郑重声明：所呈交的学位论文是本人在导师的指导下独 立完成的。除文中已经注明引用的内容外，本论文不包含其他个 人或集体己经发表或撰写过的作品或成果，也不包含本人为获得 其他学位而使用过的成果。对本文研究做出重要贡献的个人或集 体均已在论文中进行了说明并表示谢意。本声明的法律后果由本 人承担。 论文作者签名：否j j ；乙移 忉年月2 ，日 版权授权说明 本人授权学校“有权保留送交学位论文的原件，允许学位论文被 查阅和借阅，学校可以公布学位论文的全部或部分内容，可以影印、 缩印或其他复制手段保存学位论文”；愿意将本人学位论文电子版提交 给研究生部指定授权单位收录和使用。学校必须严格按照授权对论文 进行处理，不得超越授权对毕业论文进行任意处置。 授权人：冶l i ( 桫 7 年月) ，日 沈阳航空工业学院硕士学位论文 第1 章绪论 i n t e r n e t 是一个面向大众的开放系统，系统设计之初主要考虑的是数据传送的可靠 性，而对于信息的保密性和系统的安全性考虑得并不完备，因而导致目前的网络不断地 遭受各种各样的安全威胁。如何使涉及到企业、个人秘密及商业利益的信息在网络上传 输时受到机密性、完整性和真实性的保护，以避免他人利用窃听、冒充、篡改、抵赖“1 等手段对企业或个人的利益造成损害和侵犯，如何使计算机上的信息不受到来自网络的 非法访问和破坏等等，已经成为广大计算机网络用户越来越关注的问题，引起世界上各 个国家的高度重视。目前，对计算机网络安全技术的研究已经成为计算机网络和通信界 的一个热点，已经成为信息科学的一个重要研究领域。 当今社会人们对网络技术的要求越来越高，实时信息服务，付费电视、协同工作等 多媒体技术应用的发展，都依赖于主机传送数据的能力，有时候一台主机需要同数十万 台主机进行多媒体数据通信，这对现有网络宽带的承载能力提出了挑战。采用单播技术 构建的传统网络已经无法满足新兴网络应用在带宽和网络服务质量方面的要求，这直接 导致了组播技术的出现。随之而来的安全问题也备受人们的关注。 i 1 组播 “组播”也称为“多路广播”( 简称“多播”) 。它是基于u d p i p 协议面向多接 收者的数据分发方式。图1 1 是组播源s 向成员m l m 5 组播数据的示意图，s 传至路由器 r 1 的每一份u d p 报文都被复制为3 份，一份给m 1 ，一份送至m 2 和m 3 所在的网段( 广播链 路) ，一份给路由器r 2 ，r 2 再将报文生成两份拷贝分发给m 4 和m 5 。组播数据仅在执行组 播路由协议的路由器处进行最小次数拷贝( 组播树的“分叉”) ，与单播相比，组播能 有效地节省服务器资源和网络带宽。 s 图i i 组播网络模型 组播以其独特的优越性，得到越来越广泛的应用。“”，主要应用领域如下： 沈阳航空工业学院硕士学位论文 多媒体应用：目前已开发出一些多媒体应用程序，通过组播实现多对多的音频或视 频会议。视频点播和多媒体远程教学等多媒体业务也可以很好地应用组播技术。 数据分发：数据分发是组播应用的另一个领域。使用组播，公司可以采用“下推” 的模式进行文件和数据库更新。通过这项技术公司每天向他们的远程办公室发布新的信 息，比如价格和产品信息。企业可使用软件通过卫星链路向所属分公司分发软件升级和 数据更新消息，一次性向所有的分公司传送一种数据，而不是依次向每个分公司重发， 节省了时间和通信费用。 实时数据组播：实时数据传送是组播的又一主要应用领域。一个典型的例子是将股 票信息发送到交易大厅的工作站。目前组播在该领域已获得了一定范围的商业应用。 网络游戏和仿真：组播非常适合于网络游戏或者仿真应用。虽然很多游戏和仿真支 持联线方式，事实上所有这些应用使用的都是单播技术，即点对点的连接。组播可用于 有大量参与者的游戏和仿真。参与的计算机只需进入组播组就开始发送和接收游戏及仿 真数据。 组播的概念很早就被提出，但是直到现在它的优势才被充分认识。目前组播技术应 用增长快速，但作为一项新出现的技术，和所有新技术一样有其自身的局限性，因此在 这一领域里还需要进行大量的工作。 1 2 组播密钥管理 虽然组播可以极大地节省计算机的资源和网络带宽，但它所面i | 每的一个最大问题是 安全性问题。传统组播是根据u d p i p 协议来传递数据包的，该协议只负责数据包的投 递而不保障数据包的安全，它既不提供数据源的验证、保证数据的完整性和机密性，也 不能防范数据受到来历不明的攻击，所以在数据包的投递过程中，难免被伪造、篡改或 窥视。如何保证组通信的机密性和数据的完整性，怎样保证只有组成员才能解密数据包， 怎样解决数据源的认证问题及组成员的动态访问控制问题等等，所有这些都是组播应用 必须解决的安全问题”一。基于单播通信的安全技术可以直接扩展到组播中胁埘，但这样 的扩展不适用于规模较大的组，因此组播比单播具有更大的复杂性n 1 1 。 解决组播通信安全问题的一个有效方法是对组播数据进行加密，组成员( 这里也称 为用户) 共享一个用于加密传输报文的对称密钥n 2 “4 ，称为组密钥( g r o u pk e y ) 。 沈阳航空工业学院硕士学位论文 组密钥由具有组密钥管理功能的密钥服务器分发给组中的每个成员。组成员发送报文 时，用组密钥加密，由于密钥只有组成员才知道，因此仅仅组成员们能够解密并读取组 播报文n 1 1 。 与双方通信相比，组播通信的重要特性就是组成员关系的动态变化：不断的有新用 户加入组或当前组中用户离开。这样就给组播密钥管理带来了困难，当一个新的用户加 入组播组，密钥服务器必须为新用户发送组密钥；当组播组中的用户离开时，离开用户 使用过的密钥必须更换。安全有效的组密钥管理成为组播安全问题的焦点。 1 3 组播密钥管理发展现状 9 0 年代初期开始涉及对组播密钥分配的研究，但主要局限于静态的或规模很小的群 组。近年来为解决动态性较强较大的组密钥分配问题，一些文献做了很好的探索，这些 文献主要着眼于解决动态组安全性问题。 在组密钥管理协议( g r o u pk e ym a n a g e m e n gp r o t o c 0 1 ) 肌埘方案中，每个节点都与组 密钥管理者( r o o t ) 预先共享一个密钥，用来确保和r o o t 通信时的安全。当新成员加 入时，r o o t 生成组密钥报文( g r o u pk e yp a c k e t ) 。g k p 中包含：组密钥t e k ( g r o u pt r a f f i c e n c r y p t i o nk e y ) 和用于将来加密t e k 的密钥k e k ( g r o u pk e ye n c r y p t i o nk e y ) 。r o o t 用 它与组成员的共享密钥加密g i ( p ，发送给每个组成员。如果当前组密钥到期，r o o t 生成 新的g i ( p ，用当前l ( e k 加密后通过组播发送给所有组成员。这种方法的通信效率与组成 员数量呈线性关系。其优点在于r o o t 需要较小的密钥存贮空间，无需了解组成员所在的 位置，然而，由于这种密钥更新方式，离开的组成员仍然能够解密g k p ，解决这个问题 的办法就是重新创建一个组。因此难于处理成员动态安全性问题。 为实现密钥更新的可扩展性，w o n g 和w a l l n e r 分别提出了密钥图和逻辑密钥层次 ( l k h ) 树“”方法，其基本思想是通过建立逻辑密钥树，将成员离开时的密钥更新的开销 降低到o ( 1 0 9 n ) ，其中n 代表组成员的数量。这种方案在密钥管理方面的确具有相当的高 效性和安全性，但同时也具有一定的局限性，它不适合处理大型的动态群组( 成员关系 变动频繁的群组) 。 对逻辑密钥树的改进包括以下几个方面：降低组控制器需要保存的密钥数量，降低 密钥更新延迟和网络带宽占用，提高对频繁的组成员关系变化的适应性。 沈阳航空工业学院硕士学位论文 降低根节点保存密钥的数量：l k h + n 。1 和l k h + 2 n 9 1 分别对组成员加入和离开进行了优 化，减少了根节点保存密钥的数量。 降低密钥更新延迟和带宽占用：减少密钥更新所需要发送的信息量，可以降低密钥 更新延迟和带宽占用。文献 2 0 ，2 1 分别给出的两种方案都能使二叉密钥树的密钥更新 网络流量由o ( 2 1 0 9 n ) 降为o ( 1 0 9 n ) 。这类方案的思路是：逻辑密钥树在密钥更新时所需 发送给每个组成员的信息并不是所要更新的密钥，而是一个统一的密钥更新方式所需参 数，每个组成员只需收到一次更新报文，得到相应的参数，就可以自行计算出它所要更 新的所有密钥；文献( 2 2 提出了一种利用伪随机函数计算密钥更新的方法，文献 2 3 提 出基于组成员变化概率构造密钥树的方法，当组成员加入组播组时，需要按照局部最优 和全局最优方式计算插入代价，对组成员变化概率的获得，文献给出了一种基于统计的 计算方法；文献 2 4 提出了在组成员离开组播组时，只需要更新组密钥，余下的密钥可 以暂缓更新，这样一方面减少了组管理者生成密钥的数量，另一方面也减少了组管理者 的计算开销。 增强对组成员关系变化的适应性：组成员的加入和离开导致密钥更新。如果这种组 员关系变化频繁发生，或在某个短的时问内大量发生，会对系统的性能造成很大的影响。 对于这种情况，改进的思路是：批量或定时处理成员的关系变化，不是在每次组成员关 系变化时立即生成新密钥并更新，而是在一定的时间后或成员关系改变的数量达到一定 值后生成并更新密钥。这种策略牺牲了安全性，但增强了系统对组成员关系变化的承受 能力。文献 2 5 ，2 6 提出了批次密钥更新方法，对定时处理成员的关系变化作了深入的 分析。 上述几种方法都是针对组中存在组管理者“2 ”的情况，实际上可以根据系统本身 的特性采用相应的密钥管理方案。 组密钥协商协议c l i q u e s 啪1 适用于分散的、没有领导的组结构。组中没有固定的组管 理员，由所有组成员共同参与建立组密钥，也称为组密钥协商( g r o u pk e ya g r e e m e n t ) 。 在这种分散式密钥管理方案中，所有组成员视为同等的。 m i t t r a 的l o l u s 方案油1 适用于分层分组的结构。它将一个大型的群组分解成若干个子 群组，并定义了一个层次型的组安全代理来管理，从而解决了可扩展性问题，但这种管 理需要大量的资源开销，子组间的信息传输多了一次加密和解密操作，最高级节点成了 - - 4 - - 沈阳航空工业学院硕士学位论文 系统可靠性和安全性的瓶颈。 组播安全领域还是一个比较年轻的学术领域，尤其它的密钥管理机制，还有很多问 题有待研究和解决。 i 4 研究内容及结构安排 本文研究是基于集中式组密钥管理，即存在组播密钥服务器负责组成员加入与离开 时的组密钥更新。在分析逻辑密钥树和批次密钥更新方法性能的基础上，提出了改进的 批次密钥更新方法，设计了相应的标记算法和模拟实验模型，分析了算法的性能。研究 结果表明改进算法相比原批次密钥更新方法在服务器计算开销和密钥树的平衡性方面 有所提高。 在组播应用中，一些应用( 例如电信会议) 对组成员请求的响应时间要求并不苛刻 洲。针对这一类问题，对组播密钥管理的批次密钥更新方法进行了改进。由于在组成立 后和组撤销前有相对集中的用户请求，频繁的密钥更新造成不必要的资源浪费，而一些 应用对组成员请求的响应时间要求并不苛刻，可以考虑延长密钥更新间隔。对于用户请 求分散的阶段，保持密钥更新间隔不变；论文在分析原批次密钥更新标记算法的基础上， 提出了新的标记算法。改进算法的主要思想是：当用户的加入和离开请求数达到预定值 时，调整密钥更新间隔，否则密钥更新按照初始密钥更新间隔进行；在不增加组控制器 加密次数的前提下，为了尽量使树的深度减少和保持树的平衡，对密钥树调整策略也进 行了探讨。论文结构安排如下： 第l 章为概论，简要介绍课题研究的主要内容是集中式组播密钥管理中的密钥更新算 法，研究集中在组播密钥管理的批次更新算法。 第2 章针对组播的安全需求，分析组播密钥管理需要解决的问题；阐述当前存在的组 密钥管理方案，并分析每种方案的优点以及局限性； 第3 章介绍批次密钥更新方法，着重阐述标记算法和分析性能； 第4 章提出了一种改进批次密钥更新方法，该方法基于l k h 密钥管理方法，在批次密 钥更新的基础上加入了请求数的约束，并对该方法的性能进行了分析； 第5 章是实验部分，详细介绍了实验环境，实验过程，并对实验结果进行了分析。 最后，本文进行了总结，并对未来的工作进行了讨论。 一卜 沈阳航空工业学院硕士学位论文 第2 章组播密钥管理 为保护组通信的安全，可以采用加密技术：用选定的密钥( 即组密钥) 加密组报文。 仅那些拥有组密钥的成员才能通过解密获得原文。组播密钥管理问题的复杂性在于当组 成员动态变化时，如何把组密钥分发给合法的组成员。当新组成员加入时，组密钥的更 新开销较少( 组管理者用旧组密钥加密新组密钥分发给原有组成员，用新组成员与密钥 服务器共享的私钥加密新组密钥分发给新组成员) ，但有成员离开时，组密钥的更新分 发却复杂得多。由于离开成员知道旧的组密钥，所以不能用它加密分发新组密钥，因为 这样离开成员可以解密获取新组密钥。因此组管理者必须提供其他的可扩展机制来更新 组密钥。 本章第1 部分分析总结组播的安全需求及解决方法，第2 部分阐述当前存在的组密 钥管理方案，并分析每种方案的优点以及局限性，第3 部分总结本章内容。 2 1 组播的安全需求 组播的安全需求归纳为如下几点： 保密：只有拥有解密密钥的节点才能解读组播报文的内容； 组成员认证：非组成员无法生成有效的认证信息，进而无法冒充组成员发送组播报 文： 源认证( 抗抵赖，不可否认) ：组成员无法生成其他组成员的认证信息，进而无法冒 充其他组成员发送组播报文。另一方面，组成员也无法否认其发送的信息。 匿名性：为组成员提供匿名发言的机制，也就是说，接收方无法从接收到的组播报 文推断出发送方的身份。 完整性：提供验证收到的组播报文是否被篡改的手段。 对组播报文加密传输是实现组播数据保密性的一种方法，即组成员共享组密钥。组 成员认证也可以利用组密钥来实现，因为只有拥有密钥的组成员才能正确地生成加密的 组播报文。利用多方共享的组密钥来解决安全问题的关键是组密钥的生成和分发。这种 生成和分发必须是排外的，即非组成员无法获得组密钥。 除保密性外，数字签名和报文摘要这些标准技术也可以满足认证性、不可否认性， 卜 沈阳航空工业学院硕士学位论文 完整性的需求。由于本文重点阐述组密钥管理，因此对这些技术不再详细描述。 组播密钥管理的重点是如何为组成员生成、发布和更新组密钥( 组密钥是所有组成 员共享的密钥，用来对组播报文进行加密和解密等安全操作) ，以及由此产生的扩展性、 健壮性和可靠性问题。 相比单播的密钥管理，前向安全性、后向安全性和同谋破解是组播密钥管理特有 的问题。前向安全性要求退出的节点( 包括主动退出的节点或被强制退出的恶意节点) 无法继续参与组播，即无法利用它们以前获得的组密钥解密后继组播报文和生成有效的 加密报文。为实现前向安全性，可以重新生成并更新组密钥，但要注意的是，密钥更新 报文同样可以被前组成员获得，必须防止前组成员解密密钥更新报文获取新的密钥。后 向安全性要求新加入的节点无法破解它加入之前的组播报文。为实现后向安全性，当新 成员加入时可以重新生成并更新组密钥。 组播密钥管理不仅要防止某个节点破解系统，还要防止某几个节点联合起来破解。 如果几个恶意节点联合起来，掌握了足够多的密钥信息，使得无论系统如何更新密钥， 这些节点都可以获得更新的密钥，导致组播密钥管理的前向安全性和后向安全性失败， 或者使得恶意节点可以冒充其他节点进行欺骗( 破解系统的认证功能) ，这种情况称为同 谋破解。组播密钥管理要杜绝同谋破解或降低同谋破解的概率。 除此之外，组播密钥管理在设计时还要考虑如下因素的影响： 差异性：组播密钥管理涉及到多个通信实体，这些通信实体之间存在着各种差异。 这些差异包括是否可信任、是否愿意为其他实体提供服务、是否具有足够的计算能力、 是否具有足够的带宽和适当的网络延迟、是否接收组播报文( 允许存在只发送不接收的 实体) 、是否发送组播报文( 允许存在只接收不发送的实体) 等等。在设计组播密钥管理 方案时要考虑这些差异的影响。 可扩展性：可扩展性也是组播密钥管理所要考虑的重点。组播的规模从几个节点到 上万个节点甚至更多，随着组播规模的扩大，保存密钥所占用的节点存储空间、密钥生 成所需要的计算量、密钥发送所占用的网络带宽、密钥更新的时间延迟和密钥更新的频 率都会相应增加。 健壮性：对于单播来说，通信的任一方失败都会使会话终止，而组播中部分节点的 失败不应该影响整个组播会话的继续进行。这就对组播密钥管理提出了健壮性的要求。 沈阳航空工业学院硕士学位论文 可靠性：可靠性也是一个确保组播密钥管理正确而有效工作的重要因素。组播密钥 管理的控制报文( 包括密钥更新报文、组成员关系变动的通知报文等) 通常利用不可靠的 组播进行传输。这种传输存在丢包、乱序、重复等情况。设想如果缺乏确保可靠性的机 制，一个组成员没有收到密钥更新报文，它将无法参与后继的组播通信。 因此，设计一个组播密钥管理方案，需要统筹考虑通信实体间的差异、系统的可扩 展性、健壮性和可靠性等诸多因素。与组播的安全需求综合起来，我们把组播密钥管理 所要解决的基本问题归纳如下： ( 1 ) 前向安全性：确保组成员在退出组后，除非重新加入，否则无法再参与组播， 包括获知组播报文的内容和发送加密报文。 ( 2 ) 后向安全性：确保新加入的组成员无法破解它加入前的组播报文。 ( 3 ) 同谋破解：避免多个组成员联合起来破解系统( 或减少发生的概率) 。 ( 4 ) 密钥生成计算量：通常，协同的密钥生成需要较大的计算量，当节点的计算资 源不充足或密钥更新频繁时，要考虑密钥生成给节点带来的负载。 ( 5 ) 密钥发布占用带宽；密钥更新报文不应占用过多的网络带宽。 ( 6 ) 密钥发布的延迟：密钥更新时要使所有组成员都能及时地获得新的密钥。问题 ( 4 ) 与问题( 6 ) 同属可扩展性问题。 ( 7 ) 健壮性：当部分组成员失效时，安全组播仍然能够继续工作。 ( 8 ) 可靠性：确保密钥分发更新在不可靠的网络环境中的正确执行。 针对不同的应用，上述问题的必要性和重要性都会有所不同口1 1 。 2 2 组播密钥管理方案 目前，已有多种组密钥管理方案，它们采用不同的组密钥更新方案处理组密钥重新 分配问题。 根据拓扑结构的不同，可以把组播密钥管理方案分为3 大类：集中控制式、分布式和 分层分组式。 在这3 类方案中，前两类是基本形式，分层分组式通过糅合这两种形式，使得在某 些方面的性能有所改进，更能适应某些特殊应用，但并没有从根本上解决集中式或分布 式所存在的问题。 一 沈阳航空工业学院硕士学位论文 2 2 1 集中式组播密钥管理 在集中式密钥管理( c e n t r a l i z e dk e ym a n a g e m e n t ) 中，存在一个节点负责全组的密 钥生成、分发和更新。这个节点通常被称为根( r o o t ) ，组控制器( g r o u pc o n t r o l l e r ) ， 密钥服务器( k e ys e r v e r ) ，密钥分发中心( k e yd i s t r i b u t i o nc e n t e r ) 等。这种方法 有利于组播的管理，可以方便地施加身份认证等措施，很多组播应用在本质上存在着集 中控制，适合采用集中式密钥管理。但是这类方案对根的依赖性导致了单一失效点问题； 对特定节点的依赖也使得集中控制方式难以应用于p 2 p ( p e e rt op e e r ) 的模式。 图2 1 集中式密钥管理 1 9 9 9 年w a l l e rd 等人提出了逻辑密钥分层( l o g i c a lk e yh i e r a r c h y ) 结构“” ( 2 0 0 0 年w o n gc z 等人提出了密钥图结构1 ) 。采用l k h ，密钥分配中心维护一棵密钥 树。在一棵密钥树中，根是组密钥，叶子节点是用户的私钥，其它的节点是辅助密钥。 图2 2 是度为3 的密钥树。考虑组中有u l ，u 2 ，u 9 这样9 个用户，在图2 2 和图 2 3 中，方框代表u 型节点，即用户，圆圈代表k 型节点，即密钥。用户u 9 拥有从u 9 到k l - 9 路径中的所有节点的密钥：k 9 ，k 7 8 9 和k l _ 9 。其中k 1 - 9 是组密钥，k 9 为用户 u 9 的私钥，它为u 9 和密钥服务器共享，k 7 8 9 是用户u 7 ，u 8 ，u 9 共享的辅助密钥。在 平衡树中，每个成员存储l o g m + 1 个密钥，其中n 代表成员数，d 代表树的度。在更新 密钥时，这种层次结构获得较好的性能。 假设u 9 要离开组( 从图2 2 到图2 3 ) ，密钥服务器就要改变u 9 所拥有的密钥，即 将k l _ 9 变为k l - 8 ，k 7 8 9 变为k 7 8 ( 如图2 2 所示) 。对其余的用户有三种分发密钥的方 式：面向用户，面向密钥，面向组1 。为简单起见，在本章中仅仅考虑面向组的密钥更 新。使用面向组密钥更新，密钥服务器构建如下r e k e y 消息并把它组播到整个组： 沈阳航空工业学院硕士学位论文 图2 2u 9 加入图2 3u 9 离开 s u i ，u 8 ：( k 7 8 k 7 ， k 7 8 k 8 ， k l _ 8 k 1 2 3 ， k l - 8 lk 4 5 6 ， k l - 8 lk 7 8 ， 其中 k7 】k 表示用k 加密密钥k7 在r e k e y 消息中我们把每项称为一个加密的密钥。一 旦收t | r e k e y 消息，用户解开它所需要的密钥。例如，u 7 仅需要f k l 一8 ) k 7 8 和 k 7 8 ) k 7 。 类似地，假设u 9 要加入到已有8 个用户的组( 从图2 3 到图2 2 ) 密钥服务器为新用 户找到加入点( 例如k 7 8 ) ，密钥服务器构建两条r e k e y 消息并把它组播到整个组，一条 组播到整个组，另一条单播到新加入的用户： s 一u l ， u 8 ： k l - 9 k l - 8 ， k 7 8 9 k 7 8 s u 9 ： k l - 9 k 7 8 9 k 9 从上面的例子可以看出，服务器的计算开销和通信开销都和加密的次数成正比。因 此，我们用密钥服务器所执行的加密次数表示服务器开销。当密钥树度为d ，用户为n 时，假设树是平衡的，一个成员加入时服务器开销为2 1 0 9 , , n ，一个成员离开时d o n 一1 。 文献 2 6 ，3 2 中证明离开时d - - 4 是最理想的。 星型密钥结构是密钥树的特例，根的度等于组规模。星型密钥模拟了一种简单的方 法。在星型密钥中，每个用户有两个密钥：它的私钥和组密钥。没有辅助密钥。圈2 4 表示有4 个用户的星型密钥。假设u 4 要离开组( 从图2 4 到图2 5 ) ，密钥服务器用 每个用户的私钥加密新组密钥k l - 3 ，构建r e k e y 消息并组播到整个组： s u 1 u 2 ，u 3 ： k l 一3 ) k l ，f k l 一3 k 2 ， k l 一3 1 k 3 假设u 4 要加入组( 从图2 5 到图2 4 ) ，密钥服务器发送如下消息： s u l ，u 2 ，u 3 ；i k 卜4 】k 1 _ 3 s u 4 ： k l 4 ) k 4 显然，星型密钥中。一个成员加入时服务器开销为2 ，一个成员离开时为n _ l 。1 。 沈阳航空工业学院硕士学位论文 鑫鑫 图2 4u 4 加入图2 5u 4 离开 2 2 2 分布式组播密钥管理 在分布式的组播密钥管理中，参与通信的节点是对等的，通过某种密钥协商算法生 成组密钥。这类方案不存在集中控制中单一失效点的问题，并且很适合p e e rt op e e r 的 应用模式。但是缺少集中控制给管理带来了困难。 图2 6 分布式密钥管理 c l i q u e 噙1 是一种分布式的组播密钥管理算法。它利用d i f f i e - h e l l m a n ( d h ) 呻1 密钥 协商算法的一种变体来实现组密钥的生成和发布。d h 算法通常被用来在通信双方之间 协商密钥。假设节点a 和b 要生成共享密钥k ，阴算法的密钥协商过程如下： ( 1 ) a 和b 事先选定两个数q 和a ，q 是一个很大的素数，而a 具有这样的性质： 对从1 到a - 1 的所有整数n ，存在k 使得n = a im o dq 。q 和a 不需要保密。 ( 2 ) a 选择一个大的随机数x ，计算x - - a 。m o dq 。 ( 3 ) b 选择一个大的随机数y 。计算y = a rm o dq 。 ( 4 ) a ，b 交换x ，y 。 ( 5 ) a 计算k 兰1 im o dq 。 ( 6 ) b 计算k = rm o dq 。 d h 密钥交换算法的安全性来自于；对于第三方c 来说，即使它获得q ，a ，x 和y ， 推算出k 的计算量也是非常大的。 在c li q u e 中，拥有n 个组成员的组通过如下步骤协商组密钥k ：所有组成员事先选 沈阳航空工业学院硕士学位论文 定q 和a ，然后各自选定一个随机数x i ，并计算幂值a i i 。第1 个组成员将集合s l ( a 1 1 ) 传 递给第2 个组成员。第2 个组成员生成新的s 2 f a n ，a 皿，a i ”) ，传递给第3 个组成员。s k 中含 有从a 1 1 到矿的累乘和从a 1 1 到a 吐中任选k - 1 个幂值的累乘。第n 个( r p 最后一个组成员) 收 到s n 一1 并计算s n ，然后将s n 用组播发送给所有其他节点。这样，所有节点都可以计算 k = a i ”“m o d q 。 c l i q u e 的密钥传输时间延迟的复杂度为口( 面( 集合s i 的生成必须串行进行) ，密钥 计算的总计算量为口( 孑) ，密钥传输所占用的带宽为口( 彳) 。因此c l i q u e 扩展性很差阱1 。 2 2 3 分层分组式播密钥管理 分层分组式的管理方案将参与组播的成员进行分组。每个小组( s u b g r o u p ) 存在一个 控制节点。这些控制节点组成了组播密钥管理的层次i 。小组内部的密钥管理属于层次 i i 。这两个层次可以独立地选择采用集中控制的管理方式或是分布式的管理方式。在每 个层次上采用何种方式都会继承这些方式的优缺点。在层次i i 上，通常小组内部成员 个数较少，可以采用集中控制式。如果小组规模仍然较大，可以对其进一步分组，生成 新的层次。 p9r 管理 |f i 承& 人 员层 图2 7 分层分组式密钥管理 i o l u s 嘲是一种分层分组式的组播密钥管理算法。i o l u s 对组成员进行分组，每个 子组有一个组安全代理( g r o u ps e c u r i t ya g e n t ) ，负责管理该子组，所有g s a 组成一 个更高一级的组，由组安全控制器( g r o u ps e c u r i t yc o n t r o l l e r ) 管理。l o l u s 的特点 是各个子组采用独立的组密钥，组播报文在从子组a 传播到子组b 时要被组安全代理翻 译，即用a 的组密钥解密，再用b 的组密钥加密。这种设计使得密钥更新被限制在所在 子组内部，但另一方面，g s a 要负责子组的管理和组播报文的翻译，容易成为系统的瓶 颈和失效点。 沈阳航空工业学院硕士学位论文 为了消除或减轻集中控制和分布式控制固有的缺陷，存在一种折衷的思路：对于集 中控制来说，通过降低r o o t 节点所承担的责任，将r o o t 节点的功能分布化，或增加备用 节点，以减轻r o o t 节点的负载，降低单一失效点的风险；对于分布式控制来说，利用 目录服务来集中发布信息，缓解因缺乏集中控制而形成的管理难度。 一个实际的系统采用何种拓扑结构取决于系统本身的特性。分布式的结构通常应用 于p 2 p ；具有集中管理特性的应用可以采用集中控制的结构。分层分组的结构适用于具 有层次性结构的系统。 2 。3 小结 本章分析了组播的安全需求，总结了组播密钥管理需要解决的主要问题。阐述当前 存在的组密钥管理方案，包括集中式密钥管理方案密钥管理方案、分布式和分层分组式 密钥管理方案，分析每种方案的优点以及局限性。重点介绍了在集中式密钥管理方案中， 成员加入和离开组时密钥的分发过程。 1 3 一 沈阳航空工业学院硕士学位论文 第3 章批次密钥更新 组播密钥更新是保证组播安全的有效方法，早期的研究一直集中在单次密钥更新 中，也就是说，每收到一个组成员的加入或离开请求，就进行密钥更新。 文献 1 1 给出了单次密钥更新( 在每个加入或者离开请求之后立即更新密钥) 的全 面性能分析。可是单次密钥更新存在两个问题。首先，相对来说效率低下。其次，在密 钥传输和数据传输之问存在不同步问题。 本章介绍批次密钥更新方法，这种方法不仅提高了效率，而且缓解了不同步问题。 在批次密钥更新中，密钥服务器收集一段时间内的加入和离开请求，等待一段时间再进 行密钥更新。为了处理成批的请求，文献 2 6 中设计了相应的标记算法，同时对批次密 钥更新中服务器的处理开销做了最坏和平均情况下的性能分析。结果表明批次密钥更新 相比单次密钥更新，极大地节省了服务器的开销。批次密钥更新中的组成员的加入与离 开请求数不是很大时( 大体上，加入的请求数小于当前组规模的i 2 ，离开请求数小于 当前组规模的1 4 ) ，树的度为4 时性能最好艟1 ；否则，星型密钥结构( 密钥树的特 例，根的度等于组规模) 的性能超过了度很小的密钥树结构的性能。 本章结构安排如下：第1 部分说明单次密钥更新存在的两个问题，第2 部分阐述批 次密钥更新的主要思想，第3 部分阐述相应的标记算法，第4 部分分析批次密钥更新中 服务器的处理开销，第5 部分总结本章内容。 3 1 单次密钥更新存在的问题 理想情况下，离开的用户应该尽早从组中驱逐，加入的用户应该尽早为组接受。因 此，密钥服务器在每收到一个加入或者离开请求时应立即进行密钥更新，这种处理方法 称为单次密钥更新( i n d i v i d u a lr e k e y i n g ) 。可是单次密钥更新存在两个问题：效率低 下和密钥传输和数据传输之间的不同步问题。 3 1 1 效率低 单次密钥更新效率低下有两个原因。第一，由于服务器要对每次发送的r e k e y 消息 进行数字签名( 否则恶意组用户能够分发假r e k e y 消息，从而使整个系统瘫痪) ，而签 沈阳航空工业学院硕士学位论文 名算法大概比公钥加密算法要慢两个数量级，那么仅仅对r e k e y 消息进行签名就会给服 务器造成非常大的负担m 】，当密钥更新请求频繁时问题更为突出。 第二，假设两个l e a v e 请求相随而至，它们之间的间隔非常小。因此可能出现第一 套密钥还没有使用过就会被第二套密钥代替的情况，造成系统资源的浪费。 3 1 2 不同步问题 单次密钥更新存在不同步问题：即一个用户收到用已经作废的组密钥加密的数据； 或者收到用自己还未收到的新密钥加密的数据。这些情况都会导致用户不能解密出收到 的数据。产生这种情况的原因是服务器向用户发送r e k e y 消息时会有延迟，而且各个用 户的延迟不尽相同。在进行密钥更新时，保存前面的一个或多个组密钥，缓冲多个时间 段中收到的数据，可以使问题得到缓解。详细分析参照3 2 2 。 3 2 批次密钥更新 为解决上述问题，2 0 0 1 年x i a o z h o ul i 等人提出了批次密钥更新( b a t c hr e k e y i n g ) 方法。在批次密钥更新中，密钥服务器收到组成员的加入或离开请求后，不立即进行密 钥更新操作，丽是等待一段时间后，把这段时间收到的所有请求一起处理，产生一套 新的密钥和r e k e y 消息，发给整个组，这段等待时间叫做密钥更新间隔( r e k e y i n t e r v a l ) ，也叫做密钥更新周期。相比单次密钥更新，批次密钥更新有以下优点： 3 2 1 效率高 由于在批次密钥更新中，服务器对一批请求只需签名一次，因此减轻了服务器的负 担；同时也减少了密钥未使用就被覆盖的可能性，因此提高了效率。 3 2 2 缓解不同步问题 对于不同步问题，使用b a t c hr e k e y i n g 也有所改进。设d k 是发送r e k e y 消息时 的最大延迟，d d 是发送数据消息时的最大延迟，i 是更新间隔，g k ( i ) 是第i 个组密钥。 如果用户收到了一个r e k e y 消息，那么它的组密钥就会从g k ( i ) 变成g k ( i + i ) 。易得以 下结论：如果i d k + d d ，且用户当前的组密钥是g k ( i ) ，那么将只会收到用g k ( i _ 1 ) 、 6 k ( i ) 、g k ( i + 1 ) 加密的数据。这样每个用户只需要保存上一个组密钥，缓冲一个更新间 隔中收到的数据，就可以解决单次密钥更新中的不同步问题。因为更新间隔通常比较大， 沈阳航空工业学院硕士学位论文 l y d k + d d 也很容易满足。 3 2 3 安全问题 b a t c hr e k e y i n g 是性能和安全性的折衷：服务器不立即进行密钥更新，需要删除 的用户就会多留在组播组里一段时间，而要加入的用户也必须等待一段时间。从用户发 出加入或离开请求到用户收到r e k e y 消息的这段时间叫做脆弱时段( v u l n e r a b i l i t y w i n d o w ) ，如图3 1 ( a ) 。之所以叫做脆弱时段，因为在这段时间里，组内的通信内容可 以被理论上已经离开的用户获取。 w i n 印崎l 畸w i n d o w 岱i + 1 产谤、 n 、。t4 吐“一- v m b i l i 竹w 砌a _ 融_ 攀型掣 7 声n。、 m l t 4 、 “州哪厂、 吐 bg i t ，( i l 一l e a v e 请求 数据消息 o k ( i ) 第i 个组密钥 - 一- 可靠传输的r e k e y ( a ) 单次更新( b ) 批次更新 图3 1 脆弱时段 3 3 标记算法 x i a o z h o ul i 等人在文献 2 6 中提出的批次密钥更新是基于l i 【 i 密钥管理算法，在 批次密钥更新中，密钥服务器的主要任务是判断填加，删除，改变哪些密钥。虽然服务 器无法控制组成员在哪些节点处离开，但它可以决定在密钥树中放置新的节点的位置， 服务器需要将新节点放到合适的位置以使它所进行的加密操作次数最少。 在每一个密钥更新周期内，密钥服务器收集所有的加入和退出请求，为叙述方便， 把加入请求数记为j ，离开请求数记为l ，根据以下四种可能的情况( 如图3 2 所示) 进行处理： 情况1 ：j _ l ，用加入的节点替换离开的节点。从替换位置到根的这条路径的所有 节点标记为“u p d a t e ”； 情况2 ：j ( l ，在离开节点中挑出j 个最浅的节点，用加入的节点替换这些节点， 沈阳航空工业学院硕士学位论文 从替换位置到根的所有节点标记为“u p d a t e ”；其余的离开节点直接删除，如果一个非 叶子节点的所有叶子节点均被删除，则该节点也被删除； 情况3 ：j l 且l = o ，查找最浅的叶子节点v ，把它从树中删除，构建一棵完全但不 一定平衡的树t ，把所有的新用户及v 作为它的叶子，t 的其余节点对应新密钥。将t 附加到原树中位置v 。t 的所有内部节点标记为“n e w ”，从