MANET节点不相交多路径安全源路由协议(

9冯涛 等: MANET节点不相交多路径安全源路由协议MANET节点不相交多路径安全源路由协议收稿日期:2008- - .本课题得到国家“八六三”高技术研究发展计划项目基金(2007AA01Z429)、国家自然科学基金(60573036、60633020、60702059)、甘肃省自然科学基金（2007GS04823）、兰州理工大学博士基金资助.冯涛,男,1970年生,博士,教授,主要研究兴趣为安全协议复合理论,无线传感器网络安全,Email:fengt;郭显,男,1971生,博士生,讲师,主要研究兴趣为Ad hoc网络安全,Email:iamxg;马建峰,男,1963生,博士生导师,教授,主要研究领域为计算机安全,密码学，移动与无线网络安全。冯 涛1，2) 郭 显1，3) 马建峰2) 李兴华2)1)（兰州理工大学计算机与通信学院，兰州，730050）2)（西安电子科技大学计算机网络与信息安全教育部重点实验室，西安，710071）3)（甘肃联合大学数学与信息科学学院，兰州，730010）摘 要：多路径路由实现是移动Ad hoc网络(MANET)可靠运行的有效保证。现有MANET节点不相交多路径路由协议主要关注节点不相交多路径的可实现性和效率问题。针对节点不相交多路径路由协议MNDP协议在主动攻击者安全模型中的安全缺陷，提出了可证明安全的MANET节点不相交多路径动态源路由协议SMNDP协议。SMNDP协议路由请求算法中，建立了中间节点路由请求消息传播策略的检错机制、SMNDP协议路由应答算法中建立了消息防篡改机制和身份认证机制。基于攻陷的网络拓扑模型，扩展了可模糊路由概念，提出了多路径可模糊路由集合概念和节点不相交多路径源路由协议的安全定义，并应用于SMNDP协议的安全分析。SMNDP协议的安全性可以归约为消息认证码和签名机制的安全性。关键词：MANET；MNDP；可证明安全；可模糊路由；SMNDP中图法分类号:TP 309Multiple Node-Disjoint Paths Secure Source Routing For MANETFeng Tao1,2), Guo Xian1,3), Ma Jian-feng2), Li Xing-hua2)1) (School of Computer and Communication, Lanzhou University of Technology, Lanzhou, 730050, China)2) (Ministry of Education Key Laboratory of Computer Networks and Information Security, Xidian University, Xian 710071, China)3) (School of Computer and Math, Gansu Lianhe University, Lanzhou 730010, China)Abstract: The implementation of multipath routing provides guarantee for reliable running of mobile ad hoc network (MANET). Most of existing node-disjoint multipath routing focuses mainly on establishment issues of multiple node-disjoint paths and efficiency issues of identifying multiple node-disjoint paths. Multiple Node-Disjoint Paths (MNDP) has secure faults in the secure model of active adversary. To address this issue, a provably Secure Multiple Node-Disjoint Paths source routing (SMNDP) is proposed in this paper. Error-check scheme is used for the transmission of the route quest in the alogrithm of route request for SMNDP. In addition, the schemes such as the message authentication and the digital signature are used in the algorithm of route reply for SMNDP. The concept of plausible route is extended in this paper, and the definition of plausible-route set is given. And then, security definition of multiple node-disjoint paths routing is presented. The security of SMNDP can be reduced to the security of the message authentication code and the digital signature.Key words: MANET, MNDP, provably secure, plausible route, SMNDP.1 引言 多路径路由实现是移动Ad hoc网络（MANET）可靠运行的有效保证。为改进网络的可靠性和吞吐量，多路径路由协议成为近几年MANET邻域的研究热点。多路径路由可以分为3种：节点不相交（Node-Disjoint）多路径、链路不相交（Link-Disjoint）多路径和相交多路径。节点不相交多路径因其各条路径中除源节点和目的节点之外没有其他任何共用节点，因此与链路不相交多路径和相交多路径相比具有更强的容错能力和负载平衡能力。基于流网络（flow network）理论，Liu等1提出了实现MANET节点不相交多路径集合的新方法，利用多次路由发现协议，设计了k条节点不相交路径的动态源路由协议MNDP（Multiple Node-Disjoint Paths）协议。然而，MNDP协议主要关注节点不相交多路径的可实现性和效率问题而没有考虑安全问题，如果存在主动攻击者，该协议不能抵抗active-n-m攻击2。安全路由是MANET重要的安全需求，目前提出的几个多路径“安全”路由算法试图解决安全问题，如SecMR3、SRP4等。然而，都没有用严格的数学方法分析这些协议的安全性而关注的仍是多路径实现问题。文献4虽用形式化方法（BAN逻辑）分析了SRP协议的安全性，但文献5对SRP协议分析发现，SRP仍存在安全缺陷，并且已证明，路由协议的安全性不经过严格的数学证明是不可靠的。针对无线Ad hoc 网络，基于攻陷的网络拓扑模型，本文扩展了可模糊路由概念5-6，提出了多路径可模糊路由集合概念和节点不相交多路径路由协议的安全定义；基于MNDP协议，提出了MANET节点不相交多路径动态安全源路由协议SMNDP协议。SMNDP协议计算辅助路径的路由请求算法中，建立了中间节点路由请求消息传播策略检错机制；SMNDP协议路由应答算法中，建立了消息的防篡改机制和认证机制。SMNDP协议的安全性可以归约为消息认证码和签名机制的安全性。2 节点不相交多路径源路由协议的安全定义2.1 攻击者的能力模型通过控制攻陷节点，攻击者能够阻止路由协议完成协议需求的功能。本文假设攻击者能力模型为：1、节点之间用身份相互认证， Sybil攻击无效；2、节点仅能够接收到通信信号强度范围内的其他节点传输的信息，Wormholes攻击无效；3、路由发现过程的源节点和目标节点未被攻陷。攻击者不能修改或控制未攻陷节点之间的所有通信消息；4、攻击者通过攻陷节点实施攻击，并可以使用攻陷节点的所有秘密信息；5、当攻陷节点相邻时，攻击者能用任意攻陷身份假冒这些相邻节点。2.2 基于攻陷的网络拓扑模型讨论MANET路由协议之前，假定网络节点通过邻居发现协议已建立了网络拓扑，实现了MANET的安全自举7。基于攻击者能力模型，MANET拓扑模型的无向图G(V,E)可以定义为一个构造(Configrations)5-6，简称构造conf，如图1。图1 网络构造根据无线通信链路特点和邻居发现协议，如果能在两个未攻陷节点之间建立无线链路，那么与这两个未攻陷节点相对应的顶点u和v之间有一条边；如果能在一个未攻陷节点和攻陷节点集合V*中的某攻陷节点之间建立一条无线链路的话，那么未攻陷节点和攻陷节点相对应的顶点u和v*之间也有一条边。两个相邻攻陷节点u*和v*之间没有边，它们被看成了攻陷顶点集合V*中的单一顶点。用L表示身份集合，L*表示攻陷身份集合，用身份分配函数D：V2L（2L是L的幂集）给V中的每个顶点分配身份标识。身份分配函数D定义如下：vV D(v)=，其中lLL*用三元组(G(V,E),V*,D)表示构造conf，假设存在攻击者，那么实黑顶点表示V*中的攻陷顶点（V*中的顶点在图G中不相邻），每个顶点用函数D分配给它的身份集合作标记。实际上，路由协议是该静态网络构造conf上的分布式算法，由于相邻攻陷节点看成了单一攻陷节点，构造conf上的顶点不相交多路径路由协议实际上是指未攻陷节点和不相邻攻陷节点不相交多路径路由协议。2.3 可模糊路由集合图1中的身份序列A,X,E,D，A,X,Y,E,D，A,X,Y,Z,E,D等是顶点a,d之间同一条路径路由a,u*,e,d，主动攻击者能够使用L*中的所有身份，使身份序列路径路由与顶点序列路径路由不一致。为实现conf上的身份序列路径路由与真实存在的路径路由一致，文献5-6建立了可模糊路由概念，本文扩展了可模糊路由概念，提出了多路径可模糊路由集合概念。定义1：可模糊路由（plausible route）：假设构造conf =(G(V,E),V*,D)，l1，l2，ln是身份序列，如果存在V中的顶点序列v1，v2，vk（2kn）和正整数序列j1，j2，jk使得 j1+j2+jk=n；，D(Vi)（1ik），如果i=1，Ji=0，如果i1，Ji= j1+j2+ji-1；(vi，vi+1)E（1ik）。则称身份序列l1，l2，ln是一条可模糊路由。图1中的身份序列l1, l2, l3, l4, l5, l6=A,X,Y,Z,E,C是可模糊路由，因为该序列可被划分成A，X,Y,Z ，E和C四部分，使得AD(a)，X,Y,Z D(u*)，ED(e)，CD(c)，顶点序列a，u*，e和c构成图G中一条简单路径，该例中k=4，j1=1，j2=3，j3=1，j4=1；那么J1=0，J2=j1=1，J3=j1+j2=4，J4=j1+j2+j3=5，因此该身份序列路由l1,l2,l3,l4,l5,l6满足可模糊路由的定义。定义2：可模糊路由集合（plausible-route set）：对任意构造conf=(G(V,E),V*,D），假设P是图G中任意一对顶点u，v之间多路径路由的集合，如果P满足以下条件：任意piP，pi是一条可模糊路由；任意pi，pjP（ij），与pi和pj对应的顶点集合分别是Vi和Vj，并且(ViVj)u，v=，即pi和pj是两条除顶点u、v外，顶点不相交的可模糊路由。则称P是顶点u，v之间的可模糊路由集合。如图1中，A,G,H,X,Y,Z,F,D，A,X,Y,Z,E,D，A,B,C,D是顶点a和d之间的可模糊路由集合，除源顶点a和d外，它们分别与图1中顶点不相交路径a,g,h,v*,f,d、a,u*,e,d、a,b,c,d对应。2.4 路由协议的安全定义定义3：如果对任意构造conf=(G(V, E), V* ,D)和任意攻击者A，一个节点不相交多路径源路由协议仅以可以忽略的概率返回非可模糊路由集合，则称该协议是一个节点不相交的多路径安全源路由协议。节点不相交多路径源路由协议的安全意味着，任何攻击者不能使路由发现的发起者以不可忽略的概率接受非可模糊路由集合。就是说，节点不相交多路径安全源路由协议仅以可以忽略的概率返回一个非可模糊路由集合，与这个“可以忽略概率”相关的事实是：攻击者伪造密码学原语（如签名机制，消息认证码）的可能是小概率事件。消息发送者 p ,消息接收者 tt策略策略序号节点p，t与rpx关系节点p，t在同一rpx中的位置关系传播身份P,trpip是t后续广播追加1p是t前驱不传播不追加2rpi中非邻居单播给rpi前驱追加3Prpi，trpj无单播给rpi前驱追加4Prpi，trpx无广播追加5prpx，trpi无单播给rpi前驱追加6P,trpx无广播追加7表1 MNDP协议辅助路径路由请求传播策略3 MNDP协议概述假设源节点为B, 目的节点为E, MNDP协议主要步骤是：首次路由发现中，使用动态源路由协议DSR8计算首条参考路径（Reference Path）；第二次路由发现中，基于流网络计算最大流的Ford-Fulkerson 方法9，中间节点根据首条参考路径和路由请求传播策略计算辅助路径（Auxiliary Path）；节点E生成路由应答并单播得到的辅助路径给源节点B；节点B根据参考路径和新辅助路径，重组生成两条节点不相交路径。后续路由发现中，协议将前次获得的k条节点不相交路径作为参考路径，计算新辅助路径，直到某次路由发现找不到新的辅助路径为止。此时得到的节点不相交路径集合就是节点不相交的最大路径集合。再假设中间节点为t，节点p是路由请求消息的发送者（p有可能是源节点B），t 是路由请求消息的接收者（t有可能是目的节点E），当节点t接收到节点p的路由请求消息RREQ时，根据节点t是否是属于参考路径rpi上的节点，分别执行不同的消息传播策略。传播策略如下表1，其中rpx（1xn，n是参考路径集合中的路径条数）表示参考路径集合rp中的某条参考路径。4 SMNDP协议及其安全分析4.1 SMNDP协议MNDP协议没有采用任何安全机制和检错机制，主动攻击者可以通过攻陷中间节点违反计算辅助路径的路由请求传播策略，修改路由请求消息中的参考路径信息，修改节点lm-1，lm，lm+1与rp*关系节点与rpx关系节点在同一rpx中的位置关系lm+1策略消息接收者lm+1ap中后两节点lm-1，lm传播身份编号lm+1rp*lm-1rp*,lmrp*无无广播RREQ追加1lm-1rp*,lmrp*lm-1rpi;无广播RREQ追加2lm-1rp*,lmrp*lmrpi;无不传播（7）不追加3lm-1rp*,lmrp*lm-1rpi;lmrpj无不传播（5）不追加4lm-1,lmrpilm-1是lm后续广播RREQ追加5lm-1是lm前驱不传播（3）不追加6lm-1，lm非邻居不传播（4）不追加7lm+1rp*lm-1rp*,lmrp*lm+1rpi;无单播给rpi上lm+1前驱追加8lm-1rp*,lmrp*lm+1rpi不需考虑单播给rpi上lm+1前驱追加9lm-1rp*,lmrp*lmrpi;lm+1rpj无不传播（7）不追加10lm，lm+1rpilm是lm+1后续广播RREQ追加11lm是lm+1前驱不传播（7）不追加12lm，lm+1非邻居不传播（7）不追加13lm-1rp*,lmrp*lm-1,lmrpi ，lm+1rpjlm-1是lm后续单播给rpj上lm+1前驱追加14lm-1是lm前驱不传播（3）不追加15lm-1，lm非邻居不传播（4）不追加16lm-1rpi ，lm,lm+1rpjlm是lm+1后续广播RREQ追加17lm是lm+1前驱不传播（5）不追加18lm，lm+1非邻居不传播（5）不追加19lm-1,lm+1rpi ，lmrpj不需考虑不传播（5）不追加20lm-1，lm ，lm+1rpilm-1是lm后续lm是lm+1后续广播RREQ追加21lm-1是lm前驱或lm是lm+1前驱不传播（3）不追加22lm-1，lm非邻居或lm，lm+1非邻居不传播（4）不追加23lm-1rpi，lmrpj，lm+1rpk无不传播（5）不追加24表2 SMNDP协议辅助路径路由请求传播策略路由应答消息中的辅助路径信息，使得MNDP协议建立节点不相交多路径路由的协议需求难以实现。在此情况下得到的路径本文称为非辅助路径（nonauxiliary path）。本文提出的SMNDP协议与MNDP协议不同的是：（1）基于第二节提出的网络拓扑模型，SMNDP协议利用构造conf中攻陷顶点不相邻这一事实，计算辅助路径的路由请求算法中引入了检错机制；（2）SMNDP协议的路由应答算法中引入了身份签名认证机制和消息认证码（MAC）防篡改机制。4.1.1 SMNDP协议路由请求算法SMNDP协议路由请求算法包括首条参考路径路由请求算法和辅助路径路由请求算法。类似MNDP，采用DSR协议路由请求算法计算首条参考路径，本文不作详述，重点讨论根据参考路径计算辅助路径的路由请求传播策略。假设源节点为B, 目的节点为E, 身份为lm+1的中间节点收到的路由请求包含ap=（l1，lm-1，lm）的辅助路径，lm有可能是源节点B，lm+1有可能是目的节点E。当节点lm+1接收到该路由请求消息RREQ时，根据节点lm-1，lm，lm+1是否属于参考路径rp*上的节点和它们在参考路径上的位置关系，分别执行不同的消息传播策略，传播策略如上表2。表2中rp*表示参考路径集合中任意一条路径，传播策略括号中的编号表示，SMNDP的检错机制检测到lm违背了MNDP传播策略的某条规则。引理1：基于攻陷的网络拓扑模型，如果消息认证机制（MAC）是安全的，那么SMNDP协议返回conf上一条非辅助路径的概率是可以忽略的。证明：假设ap是SMNDP协议本次路由发现找到的非辅助路径，ap=（li，li+1，li+q，li+q+1，），其中li，li+q+1是未攻陷节点的身份，分别分配给了conf中的顶点u，w。li+1，li+q是攻击者A拥有的攻陷身份的任意一个序列，分配给了conf中的攻陷顶点v*，为计算该辅助路径ap节点li+q+1收到的路由请求消息是：那么，在路由发现过程中，当节点li+q+1收到该RREQ是，对每条参考路径rpxrp（1xn，n是参考路径条数），节点li+q+1要做如下验证和处理：l v*rpx（1xn），即v*在某条参考路径rpx上，根据SMNDP协议中辅助路径发现协议的传播策略3-7以及10-24，节点li+q+1能够检测出攻击者A在顶点v*上是否遵循SMNDP协议中辅助路径路由请求传播策略的要求转发或删除路由请求消息RREQ。如果攻击者A未按SMNDP协议要求转发路由请求，节点li+q+1将删除由攻击者A在顶点v*上转发给它的路由请求RREQ，如表2中的传播策略3，由于v*在某条参考路径rpx上，u和w都不在参考路径上，则攻击者A在顶点v*上应把RREQ单播给参考路径rpx上顶点v*的前驱，因此当节点li+q+1在顶点w上收到来自顶点v*的RREQ时删除该RREQ而不转发。也就是说，如果攻击者控制的攻陷节点在参考路径上，未攻陷节点li+q+1根据未攻陷顶点u、w与攻陷顶点v*在参考路径集合rp上的位置关系转发RREQ，而没有直接根据攻击者在v*上转发的RREQ转发RREQ，这样，由于这种错误检测机制的引入，节点li+q+1能够检测出攻击者不按SMNDP协议要求转发RREQ的错误行为并取消其转发的RREQ。攻击者要使本次路由发现得到的ap是非辅助路由的唯一可能是修改参考路径集合rp。然而，源节点B收到的来自目的节点E的路由应答消息RREP中，包含目的节点E对收到的路由请求中参考路径集合rp和路由发现标识符ID的消息认证码MAC，源节点B根据MAC和路由缓存表中已发现节点不相交路径集合，能够检测到攻击者在某攻陷节点上修改参考路径集合的攻击并删除该路由应答消息。因此，如果消息认证机制是安全的，SMNDP协议返回conf上一条非辅助路径的概率是可以忽略的。l v*rpx（1xn），即v*不在任何参考路径上在这种情况下，当RREQ到达w时，根据未攻陷顶点u、w和攻陷顶点v*在参考路径上的位置关系（表2中的传播策略1，2，8，9），节点li+q+1无法判断攻击者是否按协议要求转发RREQ，因为攻击者收到的RREQ可能是u的广播消息（u不在任何参考路径上，或u在某条参考路径rpx（1xn）上并且给u转发消息的顶点是路径rpx上顶点u的后继），也可能是窃听到的u单播给它的直接前驱的单播消息（u在某条参考路径rpx（1xn）上，但给u转发消息的顶点既不是路径rpx（1xn）上顶点u的前驱，也不是u的后继），需ap中的节点li-1协助才能做出正确判断。不过，如果顶点v*不在参考路径上，即使攻击者不按照SMNDP协议执行，得到的ap与路由表中的可模糊路由集合在源节点重组不会出现相交路由。因此，出现这种情况得到的路由如果是可模糊路由，重组仅产生可模糊路由集合的要求仍能满足，我们把该ap仍当作辅助路径。4.1.2 SMNDP协议路由应答算法（a）目的节点E处理路由请求RREQ：目的节点E收到路由请求RREQ目的节点E对源与目标节点的身份lB，lE，和ap生成签名，并且用与B协商的密钥KB，E生成对ID，rp的消息认证码以及生成路由应答消息随后，目的节点E把该RREP单播给ap中的最后一个节点ln，并删除RREQ其他副本。（b）中间节点i处理路由应答消息RREP：节点i收到路由应答消息RREP时，验证自己的身份li是否属于ap，li的前驱（源节点在ap中没有前驱）和后继（目的节点在ap中没有后继）是li的邻居以及验证ap中li后面的节点和目标节点的签名，如果验证失败，节点i删除该RREP，否则节点i对lB，lE，ap生成签名以及生成路由应答消息（c）源节点B收到如下RREP时（1）rp=，验证ap中第一个节点是否是它的邻居以及RREP中的所有签名，如果这些验证成功，B接受ap作为第一条参考路径，否则删除RREP；（2）如果rp，除验证ap中第一个节点是否是它的邻居以及RREP中的所有签名外，源节点B还根据当前参考路径集合rp验证消息认证码是否正确，如果这些验证成功，B接受ap作为一条新的辅助路径，否则删除RREP并启动新的路由发现。图2 SMNDP协议路由应答算法SMNDP协议在路由应答算法中引入了节点身份认证机制（签名机制）和消息认证机制（MAC）。身份认证机制是SMNDP协议返回可模糊路由的保证，消息认证机制是SMNDP协议返回辅助路径的保证。假设当前参考路径集合为rp ，SMNDP协议的路由应答算法如下图2所示。引理2 基于攻陷的网络拓扑模型，如果签名机制对选择消息攻击是安全的，那么SMNDP协议返回conf上一条非可模糊路由的概率是可以忽略的。证明：假设SMNDP协议某次路由发现返回的路由ap=（lB，l1，ln，lE）是构造conf中的一条非可模糊路由，并且源节点B收到的与路由ap相对应的路由应答消息msg=进一步假设在源节点B中msg通过了由SMNDP协议路由应答算法要求的所有验证，这意味着msg中的所有签名都是正确的，攻击者没有伪造未攻陷节点的签名，源节点B有一个身份为l1的邻居。由构造conf的定义，攻陷顶点不可能是邻居，每个未攻陷顶点有一个分配给它的未攻陷的唯一身份，那么包括（lB，l1，ln，lE），每个路由都可以这样分割：每个未攻陷的身份形成一个分割，每个连续的攻陷身份序列形成一个分割。让P1，P2，Pk是路由（lB，l1，ln，lE）的分割并且是唯一分割，身份序列（lB，l1，ln，lE）是非可模糊路由意味着至少下面两种情况之一成立： 1 存在两个相邻分割Pi=lj和Pi+1=lj+1，lj和lj+1是未攻陷的身份，但是与lj和lj+1相对应的未攻陷的顶点u，v不相邻； 2 存在三个相邻分割Pi=lj，Pi+1=lj+1，lj+q和Pi+2=lj+q+1，其中lj和lj+q+1是未攻陷身份，lj+1，lj+q是攻陷身份，但是与身份lj和lj+q+1相对应的未攻陷顶点u，w没有共同的相邻攻陷顶点。 我们说明在以上两种情况中，攻击者肯定伪造了一个未攻陷节点的签名。第一种情况中，因为身份为lj+1的节点未被攻陷，并且它发现路由表中它前面身份为lj的节点不是它的邻居，因此身份为lj+1的节点不会对路由应答消息签名。这样，攻击者肯定在msg中伪造了签名。 第二种情况中，假设攻击者没有伪造任何未攻陷节点的签名，那么身份为lj的节点肯定在顶点u上收到了攻击者A在攻陷顶点v*（v*与顶点u相邻）上转发给它的消息：msg=又因为lj+1是已攻陷节点身份，这样未攻陷节点不可能发送具有签名的路由应答消息msg。攻击者A要在攻陷顶点v*上生成消息msg，它肯定收到了来自与攻陷顶点v*相邻的另一顶点（某攻陷或未攻陷的顶点）转发的消息msg=由假设，身份为lj+q+1的节点未攻陷，攻击者A不可能伪造身份为lj+q+1的节点签名，那么只有身份为lj+q+1的节点在与其对应的未攻陷顶点w上生成并转发消息msg，即与攻陷顶点v*相邻的顶点就是未攻陷顶点w，也就是说，攻陷顶点v*是与未攻陷顶点u和w都相邻的攻陷顶点，这与第二种情况的假设矛盾。由以上两种情况说明，“攻击者没有伪造未攻陷节点签名”的假设不可能成立，攻击者A肯定伪造了一个未攻陷节点的签名。但是，如果SMNDP协议签名机制对选择消息攻击是安全的，攻击者A伪造一个未攻陷节点的签名的概率是可以忽略的，即SMNDP协议返回一条非可模糊路由的概率是可以忽略的。4.2 SMNDP协议安全性分析SMNDP协议的每次路由发现主要由四个步骤组成：(a)为启动一次路由发现过程，源节点B广播路由请求：,其中 lB，lE是源与目的节点身份，ID是路由请求标识符，rp是节点B得到的节点不相交路径集合，ap为空；(b)中间节点i处理路由请求RREQ：如果中间节点i已处理过该RREQ，删除该RREQ；否则，如果rp=，按DSR的路由请求算法向目的节点转发RREQ；如果rp，如表2处理路由请求；(c)目的节点E生成路由应答RREP和中间节点i处理路由应答RREP:如图2；(d)源节点处理路由应答RREP（图2）并重组：重组算法与MNDP协议的重组算法类似，参见文献1。定理1：如果签名机制和消息认证机制是安全的，那么SMNDP协议是可证明安全的MANET节点不相交多路径源路由协议。证明：仅给出主要的证明思路。对任意构造conf=(G(V,E),V*,D)和任意攻击者A，说明路由发现过程启动者B收到非可模糊路由或非辅助路径的概率是可以忽略的即可，即说明：（1）某次路由发现得到的辅助路径ap是conf上的一条非可模糊路由的概率是可以忽略的。见引理2。（2）某次路由发现得到的ap是conf上的一条非辅助路径的概率是可以忽略的；SMNDP协议返回非辅助路径的唯一可能是攻击者修改参考路径集合rp，见引理1。SMNDP协议路由应答算法中对参考路径集合rp使用了防篡改机制（消息认证码MAC），路由发现的启动者B根据MAC能够发现这种攻击并删除包含非辅助路径的路由应答。因此，只要消息认证机制是安全的，本次路由发现得到的ap是conf上的一条非辅助路径的概率是可以忽略的。由（1）、（2）可见，SMNDP协议本次路由发现返回非辅助路径和非可模糊路由的概率是可以忽略的，因此，源节点B重组产生非可模糊路由集合的概率也是可以忽略的，SMNDP协议是可证明安全的MANET节点不相交多路径源路由协议。证毕5 总结建立节点不相交多路径是MANET的困难问题，基于MNDP协议本文提出了节点不相交多路径安全源路由协议SMNDP协议。与MNDP协议不同的是，该协议的路由发现算法中采用了检错机制和密码学机制，并且证明SMNDP协议满足提出的安全定义。本文主要讨论了节点不相交多路径源路由协议的安全问题，以后将用类似方法讨论其他类型多路径路由协议（如距离适量多路径路由协议）的安全性。再者，以后将对SMNDP协议的效率进行优化，如中间节点使用单一聚合签名（aggregate signature）机制降低网络开销等。参考文献1Changwen Liu, Mark Yarvis, W. steven Conner, Xingang Guo.Guaranteed On-Demand Discory of Node-Disjoint Paths in Ad hoc Networks. Computer communications, 2007, Vol 30:2917-2930.2Y.-C. Hu and A. Perrig.A Survey of Secure Wireless Ad Hoc Routing. IEEE Security and Privacy Magazine, 2004, Vol 2(3): 28-39.3Panayiotis Kotzanikolaou, Rosa Mavropodi, Christos Douligeris. Secure Multipath Routing for Mobile Ad hoc Networks. Ad hoc networks, 2007,Vol 5(1): 87-994P. Papadimitratos and Z. Haas. Secure Routing for Mobile Ad Hoc Networks. In Proceedings of Communication Networks and Distributed Systems Modeling and Simulation Conference, San Antonio, Texas, 2002, 2731.5G. Acs, L. Buttyan, and I. Vajda. Provably secure on-demand source routing in mobile ad hoc networks. Technical Report 159, International Association for Cryptologic Research, 2004.6Gergely Acs, Levente Buttyan, and Istvan Vajda. Provably secure on-demand source routing in mobile ad hoc networks. IEEE Transactions on Mobile Computing, 2006 , Vol 5(11):1533-1546. 7 FengTao, Ma Jianfeng, Universally Composable Security Concurrent Deniable Authentication Based on Witness Indistinguishable,Journal of Software,2007, Vol 18(11):2871-2881.8David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks . Mobile Computing, 1996, vol 12(6): 10-23.9T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to algorithms, Second Edition, Cambridge, MA,The MIT Press, 1993附中文参考文献7 冯涛，马建峰，无线传感器网络密钥种子管理和分配模型及应用J，计算机研究与发展，2008，45(1)，146-153.Feng Tao , born in 1970 , Ph. D. , professor. His major research interests include wireless sensor networks security; Universally Composable of protocols security.Guo Xian, born in 1971, Ph. D. candidate，lectuer. His major research area is mobile ad hoc networks security.Ma jian-feng, born in 1963, professor, Ph.D. supervisor. His major research interests include computer security, cryptography, mobile and wireless networks security. 作者名 等:题目9Background Routing is a basic functionality for multi-hop mobile ad hoc networks (MANETs). These networks are decentralized, with nodes acting both as hosts and routers, forwarding packets for nodes that are not in transmission range of each other. Generally, routing is classified into two main classes: single-path routing and multi-path routing. Compared with single-path routing, multi-path routing has advantages in fault-tolerance and load sharing etc. So, multi-path routing has recently attracted extensive attentions. We are mainly concerned with the security of multiple node-disjoint paths, because security is also one of important problems for MANETs. There is no algorithm till date that claims to identify a maximal set of node-disjoint paths between a given source and a destination in a single route discovery. In fact, Ash et al. have proved that computing a maximal set of node-disjoint paths, from a list of paths traversed by different copies of a route request query, either at the source or at the destination, is an NP-complete problem. Based on flow-network theory, liu et al. proposed a new method that identifies the maximal set of node-disjoint paths and designed a Multiple Node-Disjoint Paths routing called MNDP. MNDP computes node-disjoint paths in multiple route discoveries and in an incremental fashion. However, if there exists the active adversary, MNDP cant defend against active-n-m attack, it focuses mainly on efficiency problem and implement of multi-path routing. To address the security issue, we propose a provably Security Multiple Node-Disjoint Paths (SMNDP) source routing based on MNDP. In SMNDP, we introduce error-check and cryptographic mechanisms. These two schemes provide guarantees to identify node-disjoint paths even if there exists the active adversary in the network. We analyze the security of SMNDP with a rigorous mathematical method.This work is supported by the National Natural Science General Foundation of China under Grant No. 60573036,60702059, Chinese National Programs for High Technology Research and Development (863) No. 2007AA01Z429 and the Natural Science Grand Foundation of Gansu No. 2007GS0482.