（计算数学专业论文）无线传感器网络安全研究.pdf

摘要 分布式传感器网络是由许多密集部署的传感点组成，它广泛应用 于国防军事、国家安全、环境监测、交通管理、医疗卫生、制造业、 反恐抗灾等领域。随着传感器网络研究的深入和不断走向实用，安全 问题引起了人们的极大关注。由于传感器节点的计算速度、电源能量、 通信能力和存储空间非常有限，且一般配置在恶劣环境、无人区域或 敌方阵地中，因此确保传感器网络的安全通信尤为重要。在传感器网 络的安全通信中，信息的保密性及完整性至关重要，这就使得密钥管 理和消息认证成了传感器网络安全研究中的一个重要问题。本文根据 无线传感器网络的安全需求，在几种传感器网络密钥预分配方案基础 上，对传感器网络的预分配方案进行了较深入的探讨和研究，并通过 使用三维网格空间预分配多项式，提出了一种基于三维网格的密钥预 分配方案。试验结果表明，相对于已有的几种传感器网络密钥预分配 方案，本文提出的方案具备更好的安全性能，能显著地提高网络节点 的抗攻击能力。通过对几种基本密钥预分配方案分析，本文对密钥预 分配方案的各项性能衡量标准作了综述。最后本文从消息认证的理 论、模型及消息认证码的构造方面对消息认证作了分析。 关键词：密钥预分配，传感器网络，对称多项式，消息认证 a b s t r a c t ad i s t r i b u t e ds e n s o rn e t w o r ki sc o m p o s e do fal a r g en u m b e r o fs e n s o rn o d e st h a ta r ed e n s e l y d e p l o y e d t h e y a r eb e i n g d e p l o y e df o raw i d ev a r i e t yo fa p p l i c a t i o n s ，i n c l u d i n gm i i i t a r y ， s e c u r i t y ，e n v i r o n m e n tm o n i t o r i n g ，t r a f f i cc o n t r o l ，p a t i e n t m o n i t o r i n ga n dt r a c k i n g ， m a n u f a c t u r i n gi n d u s t r y ， o p p o s i n g t e r r o rn e t w o r k sa n d f i g h t i n gn a t u r a lc a l a m i t i e s w i t ht h e r e s e a r c hf u r t h e ra n da p p li e d w i d e l yo f s e n s o r n e t w o r k s ， s e c u r i t yh a sa r o u s e dg r e a tc o n c e r n b e c a u s et h eli m i t a t i o no f s e n s o rn o d e s c a l c u l a t i o ns p e e d ，p o w e re n e r g y ，c o m m u n i c a t i o n s c a p a c i t ya n ds t o r a g es p a c e ，a n du s u a ll yd e p l o y e di nh a r s h ， u n a t t e n d e do r e v e nh o s t il ee n v i r o n m e n t ，s e c u r i t yc o m m u n i c a t i o n i ns e n s o rn e t w o r kb e c o m e se x t r e m e l yi m p o r t a n t i ns e c u r i t y c o m m u n i c a t i o no fs e n s o rn e t w o r k ，t h ec o n f i d e n t i a li t ya n d i n t e g r i t yo fi n f o r m a t i o na r ec r i t i c a l l yi m p o r t a n t t h i sm a k e s k e ym a n a g e m e n ta n da u t h e n t i c a t i o ni n f o r m a t i o n i nas e n s o r n e t w o r ks e c u r i t yr e s e a r c hb e c o m ea ni m p o r t a n tis s u e b a s e do n t h es e c u r it yn e e d so fw i r e l e s ss e n s o rn e t w o r k ，a n ds e v e r a lk e y p r e d is t r i b u ti o ns c h e m ef o rw i r e l e s ss e n s o rn e t w o r k s ，t h i s p a p e rm a d ea ni n t e n s i v es t u d yo fk e yp r e d is t r i b u t i o ns c h e m e ， a n db ym e a n so fp r e d i s t r i b u t e dp o l y n o m i a li n3 - d i m e n s i o ng r i d i i s p a c e ，p r o p o s e d3 一d i m e n s i o ng r i d b a s e dk e yp r e d i s t r i b u t i o n s c h e m e ，w h i c hn o to n l yh a st h ep r o p e r t i e so fh i g hc o n n e c t i v i t y a n dlo wo v e r h e a d ，b u ta ls op e r f o r m sm u c hb e tte rt h a na n yo t h e r s c h e m e si nt e r m so fr e s i l i e n c ya g a i n s tc o a l i t i o na t t a c k 巾1 1 ，一 一 一一 l h r o u g ht h ea n a l y s l so 士s e v e r a lk e yp r e d l s t r l b u t l o ns c h e m e t h i sp a p e rg a v eas u r v e yo np e r f o r m a n c ec r i t e r i o n i nt h ee n d ， t h ep a p e ra n a ly z e dt h et h e o r y ，m o d elsa n dt h ec o n s t r u c ti o no f a u t h e n ti c a ti o nc o d e s 。 k e yw o r d s ：k e yp r e d i s t r i b u t i o n ，s e n s o rn e t w o r k ，s y m m e t r i c p o l y n o m i a l ，m a s s a g ea u t h e n t i c a t i o n i i i 无线传感器网络安全研究 第1 章引言 微电子技术、计算技术和无线通信等技术的进步，推动了低功耗 多功能传感器的快步发展，使其在微小体积内能够集成信息采集、数 据处理和无线通信等多种功能。无线传感器网络( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 就是由部署在监测区域内大量廉价微型传感器节点 组成，通过无线通信方式形成的一个多跳的白组织的网络系统，其目 的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发 送给观察者。传感器、感知对象和观察者构成了传感器网络的三个要 素。美国商业周刊和m i t 技术评论在预测未来技术发展的报告中， 分别将无线传感器网络列为2 1 世纪最有影响的2 1 项技术和改变世界 的1 0 大技术之一。 1 1 无线传感器网络概述n 1 1 1 1 传感器网络结构 传感器网络结构如图1 1 所示，传感器网络系统通常包括传感器 节点( s e n s o rn o d e ) 、汇聚节点( s i n kn o d e ) 和管理节点。大量传感器 节点随机部署在监测区域( s i n kf i e l d ) 内部或附近，能够通过白组织 方式构成网络。传感器节点监测的数据沿着其他传感器节点逐跳地进 行传输，在传输过程中监测数据可能被多个节点处理，经过多跳后路 由到汇聚节点，最后通过互联网或卫星到达管理节点。用户通过管理 硕士学位论文 节点对传感器网络进行配置和管理，发布监测任务及收集监测数据。 监测区域传感器节点 图1 - 1 传感器网络体系结构 1 1 2 传感器节点结构 传感器节点由传感器模块、处理器模块、无线通信模块和能量供 应模块四部分组成，如图1 2 所示。传感器模块负责监测区域内信息 的采集和数据转换；处理器模块负责控制整个传感器节点的操作，存 储和处理本身采集的数据以及其他节点发来的数据；无线通信模块负 责与其他传感器节点进行无线通信，交换控制消息和收发采集数据； 能量供应模块为传感器节点提供运行所需的能量，通常采用微型电 池。 无线传感器网络安全研究 图1 - 2 传感器节点体系结构 1 1 3 传感器网络的网络协议栈 随着传感器网络的深入研究，研究人员提出了多个传感器节点上 的协议栈。如图1 3 所示，这个协议栈包括物理层、网络层、传输层 和应用层，与互联网协议栈的五层协议相对应。此外，协议栈还包括 能量管理平台、移动管理平台和任务管理平台。这些管理平台使得传 感器节点能够按照能源高效的方式协同工作，在节点移动的传感器网 络中转发数据，并支持多任务和资源共享。 传感器网络协议栈 硕士学位论文 各层协议和平台的功能如下： 物理层提供简单但健壮的信号调制和无线收发技术； 令数据链路层负责数据成帧、帧检测、媒体访问和差错控制； 网络层主要负责路由生成与路由选择； 传输层负责数据流的传输控制，是保证通信服务质量的重要 部分； 今应用层包括一系列基于监测任务的应用层软件； 令能量管理平台管理传感器节点如何使用能源，在各个协议层 都需要考虑节省能量； 移动管理平台检测并注册传感器节点的移动，维护到汇聚节 点的路由，使得传感器节点能够动态跟踪其邻居的位置； 任务管理平台在一个给定的区域内平衡和调度监测任务。 1 2 传感器网络的安全 无线传感器网络作为任务型的网络，不仅要进行数据的传输，而 且要进行数据采集和融合、任务的协同控制等。如何保证任务执行的 机密性、数据产生的可靠性、数据融合的高效性以及数据传输的安全 性，就成为无线传感器网络安全问题需要全面考虑的内容。 为了保证任务的机密布置和任务执行结果的安全传递和融合，无 线传感器网络需要实现一些最基本的安全机制：机密性、点到点的消 息认证、完整性鉴别、新鲜性、认证广播和安全管理。 无线传感器网络安全研究 无线传感器网络s p i n s 安全框架在机密性、点到点的消息认证、 完整性鉴别、新鲜性、认证广播方面定义了完整有效的机制和算法。 安全管理方面目前以密钥预分配模型作为安全初始化和维护的主要 机制，其中随机密钥对模型、基于多项式的密钥对模型等是目前最有 代表性的算法。 1 3 传感器网络安全协议s p in s 传感器网络安全协议( s p i n s ：s e c u r i t yp r o t o c o l s f o rs e n s o r n e t w o r k ) 是传感器网络的基本安全协议2 1 。它建立在对称密钥体系 的基础上，由安全网络加密协议( s n e p ：s e c u r i t yn e t w o r ke n c r y p t i o n p r o t o c 0 1 ) 和广播认证协议( 1 at e s l a ) 组成3 1 。前者用于实现点 到点通信的机密性、完整性、新鲜性，后者实现网络广播消息的验证 【4 】 o 1 3 1 安全网络加密协议s n e p 假定d s n 中的节点a 和b 已通过密钥协商互相知道会话密钥 k n 。和校验密钥k m a c ，节点a 向节点b 安全发送消息的过程如下： a _ b ：( d ) ( k 。n 。c ) ，m a c ( k m a c ，c i ( d ) ( k 。n 。c ) ) 其中d 是明文消息，c 是节点a ，b 保持同步的一个时钟计数值。 发送的内容包括两部分：一是经过k n 。和c 加密的密文，二是使用 k m a c 对c 和密文生成的消息鉴别码。 通过以上方式加密，s n e p 具备如下特性： 硕士学位论文 ( 1 ) 高度保密性。 ( 2 ) 完整性。 ( 3 ) 抗重播攻击。 ( 4 ) 新鲜性。 ( 5 ) 低功耗。 1 3 2 广播认证协议1 tt e s l a ut e s l a 使用了一种延迟公布校验密钥的思想【5 1 ，并且要求发 送方和接收方保持时钟同步。图1 4 显示了1 tt e s l a 协议发送带鉴 别码的数据的基本过程【6 】o ffff 图1 - 4 延迟公布鉴别密钥链 发送方将整个消息的发送过程分为若干时间间隔，每个间隔内发 送的消息使用同一个校验密钥生成校验码。如图1 - 4 所示，第一个时 间间隔内发送分组p 。，p 2 ，使用k l 为其生成鉴别码，第二个时间间 隔内发送分组p 3 ，使用k 2 为其生成鉴别码。所有的校验密钥k i ( i = 0 ，1 ，2 ) 构成一个密钥链，链上的校验密钥存在如下关系： k i _ f ( k i + 1 ) ，其中f 是某个公开的单向函数。发送方发送数据前先随 机生成链上最后一个密钥，比如k 4 ，使用单向函数f 生成密钥链， 无线传感器网络安全研究 并将第一个鉴别密钥k o 用安全方式( 比如s n e p ) 发送给各接收方。 接收方收到一个广播分组时，并没有相应的鉴别密钥，要等到经 过某个时延后，发送方才会广播这一鉴别码。比如，接收方在第一个 时间间隔内收到p 2 ，会将其缓存起来，经过两个时间间隔后，在第三 个时间间隔内，发送方广播k ，因为接收方与发送方保持了时钟同 步，并且知道，f ，所以可以先鉴别k 的正确性，然后使用它鉴 别先前缓存的广播分组p 2 。 1 4 传感器网络密钥预分配方案的关键性能指标 要在传感器网络中使用基于对称密钥体系的安全协议s p i n s ，必 须有相应的密钥管理方案为基础。密钥分配是密钥管理中的第一步， 也是非常重要的一个环节。传感器网络使用对称密钥体系，密钥的分 配采用预分配的方式进行。图1 5 显示了密钥预分配方案在整个传感 器网络安全体系内所处的位置。 s e c u r i t ya p p l i c a t i o n s p i n s ( s n e p + l at e s l a ) s y m m e t r i cc r y p t o g r a p h y k e ym a n a g e m e n ts c h e m e d i s t r i b u t i o n a g r e e m e n t r e v o c a t i o n 图1 5 密钥预分配在传感器网络安全体系中的位置 硕士学位论文 从图1 5 中可以看出，密钥预分配方案对于传感器网络安全体系 起着基础性作用，研究和设计性能良好的密钥预分配方案具有十分重 要的意义。 传感器网络密钥预分配方案的安全性能，通常存在以下几个主要 的性能指标。 1 4 1 网络安全的连通概率p 。 传感点部署以后，如果两个节点能够协商建立用户会话的共享密 钥，则称这两节点间存在安全边【7 1 ，由安全边构成的拓朴图称为密钥 共享图。如果任意两个节点间都能建立共享密钥，则密钥共享图为完 全图，整个网络都是安全的。 在传感器网络中，称任意两个邻节点( 互相处于通信范围内的节 点) 间能协商建立共享密钥的概率为安全连通概率p i 。l 。我们只需要 p l o 。l 达到一定值，保证整个密钥共享图成为连通图( 而非完全图) ， 就可以保证网络中的任意一对节点安全通信。 1 4 2 共享密钥协商负担 两个相邻节点要建立密钥，必须进行密钥协商。协商过程中需要 双方交换某些信息，也可能还要进行某些计算。评价密钥预分配方案 的性能，除了考虑安全性能高低之外，还要考虑协商密钥过程中的负 担。如果方案的安全性能很好，但是密钥协商负担过大，甚至超出了 传感器网络节点的承受能力，就不是现实可行的方案。反之，如果付 出些节点可以承受的额外协商负担，能换来安全性能的较大提高， 则是可以接受的现实方案。传感器网络密钥协商负担一般包括三个方 无线传感器网络安全研究 面：密钥存储负担、密钥协商的通信负担和相关的计算负担。 1 4 3 抗攻击能力 抗攻击能力是评价一个传感器网络密钥预分配方案安全性能的 关键指标。传感器网络的抗攻击能力不是指敌手攻破传感器网络中使 用的对称密钥算法的能力，而是指方案对敌手物理捕获节点的安全耐 受性，即在一定数量的节点被捕获后，剩余网络中任意一对节点间共 享密钥被泄漏的概率。 1 5 消息认证蚴 消息认证是使意定的消息接收者检验收到的消息是否真实的一 种方法。检验内容包括：( 1 ) 证实报文的源和宿；( 2 ) 报文的内容是 否曾受到偶然的或有意的窜改；( 3 ) 报文的序号和时间性。这种认证 只在相互通信的双方之间进行，并且认证不一定是实时的。 消息认证的基本方法有两种：一是采用消息认证码( m e s s a g e a u t h e n t i c a t i o nc o d e ) ，简称为m a c ；二是采用消息检测码( m e s s a g e d e t e c t i o nc o d e ) ，简称为m d c 。m a c 方法是利用带密钥的单向杂凑 函数( o nw a yh a s hf u n c t i o n ) f ( k ，) ，这里k 是密钥，将要传送的 消息x 变换成一个固定r 比特的消息认证码f ( k ，x ) 附在要传送的消 息x 后送出，以x l if ( k ，x ) 表示，其中符号“旷表示数字的连接。 一般而言单向函数是公开的，密钥k 是发方和收方在次通信中随机 选取的。当主动攻击者在不知道密钥的情况下，随机选取r 比特碰运 硕士学位论文 气，其成功的概率为2 ，当然，敌手也可以用单向杂凑函数的特点进 行攻击，例如“生日问题”攻击等。m d c 是利用不带密钥的杂凑函 数将要传送的消息变换成固定的r 比特长的消息检测码，附在消息后 面一起传送。有时也将他们加密后传送，以实现保密认证。 在通信中，发信者向收信者发送的消息可能会被敌方或窜扰者截 获并更改，甚至敌方可能会假冒发信者的身份向收信者发送假情报。 收信者要想能判别出收到的信息是否来自真正的发信者而不是敌方， 就需要在通信过程中使用消息认证技术。消息认证的过程可由图1 - 6 描述。 图1 - 6 一般消息认证系统模型 在这个系统中，通信双方在通信开始前就要通过安全信道( 或等 同于安全信道的密钥分配方案) 约定一个密钥，并在一段时间以后更 换密钥。 无线传感器网络安全研究 1 6 本文的工作 ( 1 ) 对基于随机概率的密钥预分配方案、基于有限域对称多项 式的密钥预分配方案进行分析，并对它们的性能作了评价，分别指出 了方案安全性能上的不足之处。 ( 2 ) 对b e r k e l e y 大学的c h a n ，p e r r i g 和s o n g 提出的有限域上对 称二元多项式基于网格的密钥预分配方案进行扩展，利用三维网格的 空间特点预分配多项式给节点，提出了一种基于三维网格的密钥预分 配方案。 ( 3 ) 对几种基本密钥预分配方案的各项性能衡量标准作了综述。 ( 4 ) 在消息认证理论基础上，对消息认证码的构造进行了分析。 硕士学位论文 第二章密钥预分配方案分析 传感器网络中的节点部署以后，一方面可通过预分配的密钥进行 共享密钥协商 8 1 ，另一方面可不直接分配共享密钥。通过预分配密钥， 邻节点间能协商共享密钥的概率，即安全通信概率p j o c 。l 达到一定的 值，使密钥共享图成为连通图，就可以实现整个网络的安全通信【9 】【1 0 】。 这类方案的数学模型是随机图论，p 1 0 c a j 是一个随机概率，我们称这类 方案为基于随机概率的预分配方案。e s c h e n a u e r g l i g o r 方案( 简称e g 方案) 和c h a n - p e r r i g s o n g 方案( 简称c p s 方案) 都是基于随机概 率的密钥预分配方案。不直接分配共享密钥，而分配可计算共享密钥 的有限域上的对称二元多项式给节点。节点部署前只有部分密钥信 息，需要通过和邻节点进行多项式计算才能生成共享密钥。该方案密 钥协议负担会因多项式计算而有所增加，但此计算是一次性的，并且 计算负担能被传感器节点所接受，以此代价换取安全阀值是可行的。 基于随机子集合的密钥预分配方案和基于网格密钥预分配方案都属 此类密钥预分配方案。 2 1 基于随机概率的密钥预分配方案分析 2 1 1 基于随机概率的密钥预分配方案的特例 有两种朴素的密钥预分配方案是基于概率密钥预分配方案的特 例。一是s i n g l em a s t e rk e y 方案，二是n - 1 方案1 1 1 ，两种方案的基本 无线传感器网络安全研究 思想如下： ( 1 ) s i n g l em a s t e rk e y 方案：该方案对传感器网络中的所有节 点预分配同一个公共主密钥m a s t e rk e y ，任意一对节点都使用该主密 钥通信。 ( 2 ) n 1 方案：该方案要求传感器网络中任意一对节点间都使 用不同的密钥通信。如果传感器网络中节点数量为n ，则每个节点要 预分配n 一1 个不同的密钥，故名为n 1 方案。由于任意一对节点的通 信密钥互异，理论上该方案可使传感器网络的安全性能达到最佳。 这两种朴素的密钥预分配方案是基于随机概率密钥预分配方案 的特殊情况，两者都使得邻节点间的安全连通概率p 。o 。a 1 = 1 ，而且这两 种方案下的密钥共享图还将成为完全图，任意两个节点都可以直接协 商共享密钥。然而，这两种朴素的密钥预分配方案对传感器网络而言 不是现实可行的。s i n g l em a s t e rk e y 方案非常容易实现，但基本不具 备安全性，只要主密钥泄漏，则整个传感器网络的通信都不安全。 n 1 方案要求每个节点预分配n 1 个密钥，整个网络需要预分配n x ( n 1 ) 2 个密钥。由于传感器网络的节点数量很大( n 很大) ，维护 和管理如此大的密钥量对于节点非常有限的存贮资源和计算能力来 说是不现实的。更重要的是，n 1 方案不具备灵活性。因为传感器网 络具有动态特性，可能需要向网络动态增减节点。如果采用n 1 方案， 往传感器网络中加入新的节点时，新密钥分配和协商将变得十分困 难。 硕士学位论文 2 1 2 基本密钥预分配方案e s c h e n a u e r - gl ig o r 方案 2 1 2 1 方案概要 e s c h e n a u e r - g l i g o r 方案的密钥预分配和协商过程分为以下三个 主要阶段： ( 1 ) 密钥预分配阶段( k e y p r e d i s t r i b u t i o np h a s e ) 。 密钥预分配在节点部署前完成。系统预先随机构造一个密钥池， 其中含有个互异的密钥( 很大) ，每个密钥有一个唯一的标识符。 传感器网络中的每个节点都随机从密钥池中抽取t 个密钥存贮在自己 的e p r o m 中( t ) ，抽取的密钥仍然放回密钥池，此过程称为密 钥分配。 ( 2 ) 共享密钥直接协商阶段( s h a r e d k e yd i s c o v e r yp h a s e ) 。 节点部署后，可以通过和邻节点互相交换预分配密钥的标识符知 道是否和某个邻节点有公共密钥1 2 】。如果两个邻节点至少有一个公共 密钥，则简单的选择其中一个作为共享密钥。此时，在密钥共享图中 这两个邻节点间就存在一条安全边，此过程称为共享密钥直接协商 1 3 】 o ( 3 ) 共享密钥间接协商阶段( p h t l l 一k e ye s t a b l i s h m e n tp h a s e ) 。 如果两个邻节点没有任何公共密钥，则可通过与二者都有公共密 钥的第三个节点作为中介进行密钥协商建立共享密钥，此过程称为共 享密钥间接协商。只需确保密钥共享图为连通图，则任意一对邻节点 都可以通过直接或间接的方法协商建立共享密钥。 2 1 2 2 性能评价 无线传感器网络安全研究 e s c h e n a u e r - g l i g o r 方案的数学模型是e r d 6 s 关于随机图论的理 论。随机图是指任意两点间存在边的概率为p ，且p 是独立等概随机 变量的图。当p = 0 时，随机图没有任何边，当p = l 时，随机图是完全 图。e r d 6 s 的随机图论理论指出：若随机图的节点数量为n ，当n 很 大时，如果整个随机图要至少以概率p r 成为连通图，则存在以下极限 式： p 。= l i mp ( g ( n ，p ) 。c t 。d ) = e e 。c ( 2 1 ) 其中p 为任意两点连通的概率，c 为常数，且存在关系式： p = i n ( n ) n + c n ( 2 2 ) 当给定传感器网络节点数量n ，期望的整体连通概率p ，时，可求 得任意两点连通的概率p ，从而求得节点的平均度d 。综合公式( 2 1 ) ， ( 2 2 ) ，有： p = ( i n ( n ) 一i n ( i n ( p r ) ) ) n ( 2 3 ) d = p ( n 1 ) ( 2 4 ) 安全连通概率p l 。a 。是节点与其通信范围内的邻节点之间安全连 通的概率，而p 是密钥共享图中任意两点之间的连通概率，使用传感 器网络节点的分布密度作为中介可将二者建立联系。设传感器网络的 部署密度n 为任意节点的邻节点数量( 对于均匀分布n 是一定的， 且r l q ) ，则k 。h 。他a = h a s h ( k i i i k 2 1 1 ir kq ，) ， h a s h 为某个公开的哈希函数。 2 1 3 2 性能评价 和e s c h e n a u e r - g l i g o r 方案类似，为确保密钥共享图为连通图， c h a n p e r r i g s o n g 方案也需要使安全连通概率p 1 蝴1 达到一定值，根据 概率论的知识进行推导，有如下结论： 硕士学位论文 p ( i )一， 暇) ) ( 2 8 ) 其中，p ( i ) 为从个密钥中抽取t 个预分配给节点时，两个邻 节点有i 个公共密钥的概率。由全概率公式，两个邻节点能直接建立 共享密钥的概率为： p l o c a l = 1 ( p ( o ) + p ( 1 ) + - i - p ( q 1 ) ) ( 2 9 ) c h a n p e r r i g s o n g 方案的密钥协商负担和e s c h e n a u e r - g l i g o r 方案 基本相同，唯一不同的是，c h a n - p e r r i g s o n g 方案需要进行一次哈希 计算得到共享密钥，哈希计算的能量消耗对传感器网络来说是很小 的，而且广播密钥标识符只进行一次，因此这部分的负担并不大。 c h a n - p e r r i g s o n g 方案的抗攻击能力计算和e s c h e n a u e r - g l i g o r 方 案类似，但不同在于要考虑t q + 1 种可能性。由全概公式，x 个节点 被捕获时，任意一对未被捕获的节点间共享密钥泄漏的概率为： p c o m p r o m i z e d = 童( 1 - ( 1 刮训粤 ( 2 1 0 ) 2 2 基于有限域对称多项式的密钥预分配方案分析 2 2 1 有限域g f ( q ) 上对称二元多项式的安全特征 系统随机在有限域g f ( q ) 上构造t 阶对称二元多项式，多项式 形如f ( x ，y ) = 2 i j ：o a i j x l 夕( q 为与密钥长度相适应的大素数) 。节点部 署前，系统为每个节点预分配多项式，对于节点i ，预分配f ( i ，y ) ， 无线传感器网络安全研究 对于节点j ，预分配f ( j ，y ) 。节点部署后需通过多项式计算协商共享 密钥，如果节点i 和节点j 预分配有相同的多项式f ( x ，y ) ，则可通过 f ( x ，y ) 计算共享密钥。计算方法为：节点i 对节点j 计算f ( i ，j ) ， 节点j 对节点i 计算f ( j ，i ) 。由多项式的对称性有f ( i ，j ) = f ( j ，i ) ， 即为节点i 与节点i 的共享密钥。 g f ( q ) 上t 阶二元多项式f ( x ，y ) 具有安全阀值t ，只要被捕 获的携带f ( x ，y ) 的节点数量不大于t ，则被捕获节点不会泄漏有关 f ( x ，y ) 的信息。敌手无法获知f ( x ，y ) 的信息，就无法通过f ( x ，y ) 计算共享密钥。多项式的安全阀值使整个传感器网络存在系统安全阀 值，当被捕获的节点数量不大于该安全阀值时，整个网络的安全通信 不受影响。 2 2 2 基于随机子集的密钥预分配方案 2 2 2 1 方案概要 节点部署前，系统在g f ( q ) 上随机生成含个对称二元多项 式的多项式池，每个节点从中随机抽取t 多项式存储，被抽取的多项 式仍放回池中。如果节点的密钥容量为m ，每个节点预分配t 个多项 式，由于每个多项式的密钥量为t + 1 ，则有： m = ( t + 1 ) 百 ( 2 1 1 ) 节点部署后，两个邻节点如果至少有一个相同的公共多项式，则 可直接协商共享密钥。如果两个邻节点没有公共多项式，则通过与二 者都有关公共多的第三个邻节点间接协商密钥。整个过程和 硕士学位论文 e s c h e n a u e r - g l i g o r 方案中的密钥协商过程类似。 2 2 2 2 性能评价 基于随机子集合的密钥预分配方案和e s c h e n a u e r - g l i g o r 方案在 构造安全连通概率p 。咖i 上的方法是相同的，都是通过密钥池大小 和每个节点预分配密钥百来构造随机变量，所以方案安全连通概率的 有关分析和e s c h e n a u e r - g l i g o r 方案类似。 基于随机子集合的密钥预分配方案的共享密钥需要通过多项式 计算得到，该计算需要一定的能量，由于邻节点间广播自己的多项式 编号的通信负担很小，所以基于随机子集合的密钥预分配方案的主要 密钥匙协商负担是两个邻节点间协商共享密钥时进行的多项式计算。 由于基于随机子集合的密钥预分配方案采用了g f ( q ) 上对称二 元多项式计算共享密钥，每个节点只有部分共享密钥信息，所以方案 具备安全阀值。多项式池中的多项式是随机生成的，每个节点随机地 从中抽取多项式预分配，当x 个节点被捕获时，任意一对未被捕获的 节点间共享密钥被泄漏的概率是相等的，都等于多项式池中任意一个 多项式被泄漏的概率，设任意一对未被捕获的节点间共享密钥为c ， x 个节点被捕获的事件为c x ，多项式池中的多项式为p ，p 2 ，p ， x 个节点被捕获的条件下，任意一对未被捕获的节点间共享密钥被泄 漏的概率为： p ( c c 。m p ，。m i z e d l c x ) = p ( p l c 。m p m m i ：。d ) = 2 喜。( ；! ) ( 云) 。( 一考) 。一。 ( 2 1 2 ) 无线传感器网络安全研究 2 2 3 基于网格的密钥预分配方案 2 2 3 1 方案概要 首先构造如图2 1 所示的网格。网格的每行( 列) 对应于一个事 先随机生成的g f ( q ) 上的对称多项式，等待部署的节点随机分布在 网格上。各节点根据自己的坐标位置，预分配对应的两个多项式( 行 与列方向对应的多项式) ，同时节点也存储自己的网格坐标( 行列坐 标) 每个节点都有自己的编号( 可由网格坐标计算得到) 。 节点部署后，一个节点可以和自己的邻节点通过广播交换自己的 坐标来确定能否直接建立共享密钥。如果不能直接建立共享密钥，则 寻找与二者都有公共多项式的第三个节点作为中介进行间接密钥协 商。在图2 1 中，节点1 和节点3 没有公共多项式，则可以通过节点 2 和节点4 作为中介间接协商共享密钥。 f i ( x ，y ) f o 。( x ，y ) j _ _厂 _ _ _ _ _ _ _ _ _ 剖引 f o 。( x ，y ) f i 。( x ，y ) f - m 1 。( x ，y ) 图2 - 1 基于网格的密钥预分配 2 2 3 2 性能评价 若网格大小为m m ，则任意两个邻节点间的安全连通概率为： 硕士学位论文 p l o c a l - 掣：三 ( 2 1 3 ) m m 一1m - i - 1 基于网格的密钥预分配方案的密钥协商负担和基于随机子集合 的密钥预分配方案类似，都是多项式计算的负担。 相对于基于随机子集合的密钥预分配方案，基于网格的密钥预分 配方案具有更好的安全耐受性。由于方案通过网格预分配多项式，多 项式池大小比基于随机子集合的密钥预分配方案有较大增加，从而可 获得更大的安全阀值，但是方案在通过网格增大多项式池大小的同 时，也使得安全连通概率大大下降。网格大小为m m ，则整个传感 器网络共有节点n = m m 个，x 个节点被捕获的条件下，一个二元多 项式中恰好有i 份分享被泄漏的概率为： p ( i )= 志( 斯一圹 似聊一f ) ! l l ( 2 1 4 ) 因此，一个二元多项式被泄漏的概率为： f p c o m p r o m i ：。d2 1 一p ( f ) ( 2 1 5 ) 2 3 本章小结 在本章中，我们对基于随机概率和基于有限域对称多项式的密钥 预分配方案进行了分析，并对各方案的主要性能指标进行了评价。综 合各节的分析，有以下结论：e s c h e n a u e r - g l i g o r 方案是 c h a n p e r r i g s o n g 方案的特殊情况，他们都具备灵活性，可适应传感 器网络节点增减的动态特性，但方案的整体安全性能都随被敌手捕获 无线传感器网络安全研究 的节点数量增加而很快下降。基于随机子集合的密钥预分配方案和基 于网格的密钥预分配方案使用了有限域上的对称二元多项式，这使得 方案具备安全阀值，提高了方案的抗攻击能力。当敌手捕获的节点数 量不大于安全阀值时，网络通信安全几乎不受影响；当敌手捕获的节 点数量大于安全阀值时，网络的安全性会快速下降。因此，方案的安 全耐受性很大程度上取决于安全阀值的大小。 硕士学位论文 第三章基于三维网格的密钥预分配方案 本章对基于网格的密钥预分配方案进行扩展，提出了一种基于三 维网格的密钥预分配方案。该方案在三维网格的立体空间上预分配多 项式给节点，实现了增大密钥共享图安全连通概率的目的。该方案具 备良好的抗攻击能力，由于使用三维网格可获得较大的预分配多项式 空间，相对于二维网格方案，该方案具在更大的安全阀值。 3 1 基于三维网格密钥预分配方案概要 设一个传感器网络最多有n 个传感点，构造带有3 m 个多项式集 合 f 。h ( x ，y ，z ) ，f ；讣( x ，y ，z ) ，f 。m ( x ，y ，z ) ) 瑚1 m - 河 的一个m m x m 三维网格。如图3 - i 所示，每一水平面i 与多项式f ；h ( x ，y ，z ) 相对应，每一竖面i 与多项式f 。礼( x ，y ，z ) 相对应，每_ 侧面i 与多项 式f ；m ( x ，y ，z ) 相对应。为方便起见，我们将一个点的坐标编码为一个 单值传感点的i d ，即用i d 表示坐标( i ，j ，k ) 。其中，i d i 表 示第i 个水平面，i d j 表示第j 个竖面，i d k 表示第k 个侧面( 水平 面1 w 由长和宽构成，竖面w h 由宽和高构成，侧面h 1 由高和长构成) 。 子集分配：安装服务器随机生成3 m 个有限域f 。上的t 次多项式 f = f 。h ( x ，y ，z ) ，f ；讪( x ，y ，z ) ，fi m ( x ，y ，z ) ) ；：0 j l ，。，对于每个传感点， 安装服务器选择三维网格中一个未被占用的交点( i ，j ，k ) 与之对应， 因此这个传感点的i d 为 ，之后，安装服务器把( i d ， 无线传感器网络安全研究 f ；h ( x ，y ，z ) ，f 。娟( x ，y ，z ) ，fi h l ( x ，y ，z ) ) ；：，。) 分配给传感点。为了 便于路径发现，我们要求交点从三维网格的一个长方体区域密集地选 择。 多项式共享发现：点 要与 建立成对密钥，先 检验是否有i = i ，j = j 或k = k ，若i = i ，表示这两个点位于同一平 面i 上，参考二维网格方案n 3 3 可建立成对密钥，再检验是否有j = j 或 k = k ，若j = j ，表示两个点不仅位于同一平面，还位于同一竖面，即 它们位于同一条直线上，这样它们有共享多项式f ，h ( x ，y ，z ) ，利用 基于多项式的密钥预分配方案n 3 儿1 4 3 就可建立成对密钥。其它的情况可 类似地讨论。 f i l w ( x ，y ，z ) f 0 1 ”( x ，y ，z ) 图3 - 1 三维网格 图3 2 路径发现 路径发现：若i i ，j j ，k k ，则点 幂f l 需要发现路径 。如 图 3 2所示， 点 ， ， ， ， ， 台邑 帮助 和 建立成对密钥。事实上，在没有点被破坏 2 5 硕士学位论文 的情况下，由分配算法，任两个点之间都存在至少两个点作为中间结 点。由此，从点 到 有至少六条路径。 3 2 性能评价 连通性：由于每个点与三个多项式相联系，且每个多项式被m 个 不同的的传感点共享，因此，每个点能与其它点直接建立成对密钥的 概率为等瓮半= 荸三等。进步，由路径发现方法知，在没有点被 破坏的情况下，任两个点能建立成对密钥。 负担：由存储要求，每个点需存储3 个t 次的有限域f 。上的多项 式以及能与之直接建立成对密钥的点的工d 。因此，每个点的总存储 负担最多为3 ( m + 1 ) l o g 。+ 3 ( t + 1 ) t 比特。对于能直接建立密钥的点之 间没有通信负担，而在只有两个中间结点的点之间，由于已知哪个中 间点可通信，在路径发现的情况下，则有一些依被破坏点数多少而定 的广播信息。此方案的计算负担则是必要的一个或多个t 次多项式值 的计算。 安全性：设敌手随机捕获了x 个传感点，则在整个网络中点被 破坏的比例为见= x ，一个特殊的多项式中恰好有k 个共享被泄露的 概率为p ( 尼) = 西高与p k ( 1 - - p 。广。因此，链路部分被破坏的概率为 尸( x ) ：1 一t 尸( f ) 。图3 3 显示了被破坏点数x 与未被破坏点中链路受 影响的概率p ( x ) 之间的关系，其中每个点存储2 0 0 个密钥。n = 2 0 ，0 0 0 ， 无线传感器网络安全研究 由图3 3 可知，就算有9 5 ( i e ，1 9 ，0 0 0 个点) 被破坏，链路受影 响的可能性也只有大约3 0 2 8 ，因此，我们的方案在大部分点被破 坏的情况下仍有较高的安全性。 图3 3 抗攻击能力 3 3 本章小结 x1 0 4 通过对三维网格密钥预分配方案各项性能指标的分析，我们可将 它的优点归纳如下：1 ) 较好的连通性，即点之间建立成对密钥的高 概率性：2 ) 较少的存储、通信及计算负担；3 ) 有较高的安全性，即 有较强的抗攻击能力。由参考文献 1 4 中的图( 5 a ) 可知，二维网格 方案n 副、基本概率方案3 、随机成对密钥方案n5 i 、q 复合方案n 5 1 及随 机子集分配方案在多于1 4 ，0 0 0 个点被破坏时都不能保证足够的安全 ( 链路部分被破坏的概率超过6 0 ) ，而三维网格方案就算有9 5 ( i e ， 1 9 ，0 0 0 个点) 被破坏，链路受影响的可能性也只有大约3 0 2 8 ，由 此可见，三维网格方案较之以上这五种方案有更高的安全性。 硕士学位论文 第四章密钥预分配方案性能衡量标准综述 由于传感网络布署在敌方区域时，易受到不同类型的恶意攻击， 因此确保传感网络的安全通信尤为重要。然而传感点在存储资源和计 算能力方面有限，使用传统的密钥管理技术如公共密钥预分配方案n 们 是不可行的。为了解决传感网络密钥管理问题，研究者们提出了各种 密钥预分配方案，其中大部分是在传感器位置信息未知的假设下提出 的。这些方案按密钥的预先选取方式来分，可分成随机性( 即概率性) 和确定性密钥预分配方案两类。随机性密