移动ad hoc网络预分配非对称密钥管理方案

韩磊，刘吉强，韩臻，魏学业

（1. 北京交通大学 电子信息工程学院，北京 100044；

2. 北京交通大学 计算机与信息技术学院，北京 100044）

1 引言

移动ad hoc 网络（MANET, mobile ad hoc network）是一种由移动节点组成的无固定网络基础设施和中心信任机构的自组织网络，广泛应用于军事通信和灾难救援等没有固定网络基础设施的环境。MANET具有如下特点[1]：移动性、网络拓扑结构动态变化、有限的节点计算资源、多跳无线通信、无固定网络基础设施等。这些特点在保障MANET灵活应用的同时也使MANET面临诸多挑战[2]，尤其随着MANET组网技术的发展及应用环境对网络安全需求的提高，增强MANET安全已经成为一个亟待解决的问题。

基于身份的加密(IBE, identity-based encryption)思想[3]由Shamir于1984年提出，主要目标是寻找一种非对称加密算法使得公钥可以为任意的字符串以简化密钥管理过程。2000年，Boneh和Franklin提出了使用Weil来实现IBE的一个实用方案[4]。此后，在MANET中出现了大量基于IBE的密钥管理方案[5～9]。在基于IBE的MANET密钥管理方案中，公钥是标识节点身份的信息(如地址、名字等)，不依赖可信认证机构(CA, certification authority)为节点颁发公钥证书。所以，从方法上简化了MANET中节点的密钥管理过程，但基于IBE的MANET密钥管理方案还存在以下主要问题。1)现有基于 IBE的非对称密钥管理方案主要采用分布式私钥生成(PKG, private key generation)中心结合门限密码学的方式，将PKG的功能分散到网络的多个节点中，这种方式从本质上改善了传统非对称密钥管理中基于CA或分布式CA系统的复杂性，也有效避免了密钥服务的单点失败。但是，网络中需要密钥服务的节点需要和多个节点通信，带来了大量的网络带宽和节点能量损耗。因此，在MANET中设计高效、低能耗的密钥管理方案是增强MANET安全性和可用性的一个重要问题。2)密钥托管问题。基于IBE的密钥管理方案由于PKG能够计算出节点的私钥，所以PKG可以解密发向节点的密文或冒充该节点。因此，密钥托管是MANET中增强网络安全的另一个需要考虑的问题。

本文从以上2个问题着手，借鉴组合公钥(CPK,combined public key)思想[10]在MANET中提出一种基于身份的预分配非对称密钥管理方案(PAKMS,identity-based pre-distribution asymmetric key management scheme)。该方案通过私钥生成中心为节点预分配主密钥子集及通过基于时间获得节点密钥更新的方式，从方法上降低了移动ad hoc网络中非对称密钥管理的通信开销；私钥生成中心为节点预分配主密钥子集的方式也使节点在网络运行阶段不再依赖私钥生成中心为节点分配和更新密钥。由此，弱化了基于身份密钥管理中的私钥托管问题对网络安全的影响。与MANET中典型基于对称加密系统的预分配密钥管理方案比较[11,12]，只需每个节点预分配一个向量密钥，避免了通过提高预分配密钥数量提高对偶密钥建立概率的缺陷，减少了预分配密钥的存储空间；同时，由于采用了基于身份的密钥管理方案，在源节点能获得目标节点身份标识的前提下保证了密钥的成功建立。与典型基于身份的分布式门限PKG密钥管理方案[5,6]比较，减小了密钥服务中的通信次数，从而降低了节点获得密钥服务的通信开销和能量损耗。

2 基于身份的预分配非对称密钥管理方案的定义及安全模型

2.1 方案描述

定义 1 基于身份的预分配非对称密钥管理方案Γ由 Setup、Predistribute、Extract、Encrypt和Decrypt 5部分组成，构成一个关于算法的五元组Γ=(G en,P re,E xt,E nc,D ec)，具体描述如下。

1) 算法Gen：在 Setup阶段 PKG运行算法Gen，输入安全参数生成系统参数Params和主密钥 XPri。

2) 算法Pre：在Predistribute阶段PKG运行算法Pre，在主密钥 XPri矩阵中输出子集 XID，预分配到节点集合I中。

3) 算法Ext：在 Extract阶段节点运行算法Ext，输入节点密钥标识 S tr = (I D|T ime) ∈ { 0,1}*，输出对应节点的公钥 yStr和私钥 xStr。

4) 算法Enc：在 Encrypt阶段节点运行算法Enc，输入待加密的消息M，公钥 yStr和系统参数Params，输出关于明文M的密文C。

5) 算法Dec：在 Decrypt阶段节点运行算法Dec，输入密文C和私钥 xStr，输出密文C所对应的明文消息M。

2.2 安全模型与假设

定义 2 在基于身份的预分配非对称密钥管理方案中，根据方案基于身份和预分配主密钥子集的特点，定义2种类型的敌手模型。

类型Ⅰ：在攻击过程中敌手具有适应性选择身份及查询节点私钥的能力，以获取待攻击节点之外的节点私钥。

类型Ⅱ：敌手除了具有类型Ⅰ敌手具有的能力外，还具有查询节点预分配主密钥子集的能力，以获取待攻击节点之外的节点预分配主密钥子集。

定义3 一个函数f:R→R是可忽略的，对于∀d ≥ 0 ，d为常数，都存在一个整数N，使得对于∀k≥N，有

定义4 如果任何多项式时间IND-ID-CPA敌手 A(类型Ⅰ)赢得 IND-ID-CPA 游戏的优势概率AdvΓ,A(k)是可忽略的，则称基于身份的预分配非对称密钥加密方案在适应性选择身份和明文的攻击下是安全的。

IND-ID-CPA游戏[4,13]由5个步骤构成。

1) Setup：挑战者B运行算法Gen产生系统参数和主密钥，并将系统参数发送给敌手A。

2) Phase1：敌手A通过节点ID向B发起提取私钥请求，B向A返回对应节点ID的私钥。

3) Challenge：A向B发送在Phase1阶段没有请求过的节点 I D0及明文 M0、 M1，B随机选取b∈ { 0,1}运行算法Enc加密明文 Mb得到密文C，并将C发送给A。

4) Phase2：A继续发起除 I D0外的私钥提取请求，

B向A返回对应节点的私钥。

5) Guess：A输出 b '∈ { 0,1}猜测明文 Mb。如果b ' = b 输出1，否则输出0，敌手攻击成功的优势概率为

定义 5 在基于身份的预分配非对称密钥管理方案中，对于能够适应性提取x个节点主密钥预分配子集的敌手(类型Ⅱ)能以概率 p (x)获得待攻击节点密钥的方式，称为选择节点概率攻击，攻击成功的概率为 p (x)。

本文假设节点具有GPS(global position system)模块，能够通过GPS模块获得精确的时间信息并且敌手只具有定义2中描述的攻击能力。

3 基于身份的预分配非对称密钥管理方案

3.1 具体方案

基于身份的预分配非对称密钥管理方案由以下5个部分构成。

1) Setup阶段

由PKG生成系统参数和主密钥对。

S-Step1 PKG生成阶数为素数q的循环群G，任意选择生成元g∈G。其中，Zq-1为模 q - 1 的整数集合,Z+为正整数集合。

S-Step3 选择强密码杂凑函数 H:{0,1}*→ { 0,1}l×n，其中，l满足 m = 2l。

S-Step4 公开系统参数 (G ,g,q, YPub,H)。

2) Predistribute阶段

PKG根据节点的身份为节点预分配主密钥子集后离线。

P-Step1 I = { I D1, I D2, …, I DN}为节点身份集合，其中，IDu(0＜u≤N)由节点唯一身份标识idu和物理地址 M ACu构成，。计算 I Du的散列值其中是长度为l的二进制串。先分配到节点 I Du中。

3) Extract阶段节点通过预分配的主密钥子集生成节点私钥，通过公开的系统参数生成目标节点公钥。

X-Step1 节点身份标识 I Du与当前密钥时间Time构成节点密钥生成标识(0＜u≤N)。计算Stru散列值

X-Step2 设目标节点为 I Du(目标节点可以为任意节点，只需通过应用获得其节点身份信息)，通

4) Encrypt阶段

任意节点IDv(0＜v≤N,v≠u)需要向节点IDu更新后， I Dv加密需要利用 X-Step2阶段计算节点IDu的公钥)，随机数 r ∈ Zq-1及 ElGamal算法[14]计算明文M∈G的密文C = ( c1,c2)并发送给节点 I Du，其中， c = M (y )r，c = gr。1Stru2

3.2 节点密钥更新

密钥更新的目标是变换节点在 Extract阶段为节点使用而生成的公私钥。该过程能够更新节点当前使用的密钥而无需改变节点中预分配的主密钥子集。若系统当前时间t ( ti≤t＜ti+1)时刻节点IDu，其中， T ime = ti，节点 I Du需要间间隔为Δt，满足ti+1=ti+Δt ，其中，Δt可以根据系统不同的应用需求来设定(如24h、12h、2h等)，则节点 I Du需要如下过程。

R-Step1 由节点身份标识 I Du与更新密钥时间Time = ti+Δt构成节点新的密钥生成标识 S tru={ I Du|T ime}(0＜u≤N)。计算Stru散列值H(Stru)=，由X，H(Str)生成节点更新的私IDuu钥

4 方案分析

4.1 安全性分析

分析方案的安全性之前，先回顾一下本文方案基于的困难假设。

定义6 判定Diffie-Hellman假设(DDH假设)：在阶数为素数q的循环群G中，g为G的任意生成元，随机选择a,b,c ∈ Zq*,τ ∈{0,1}。如果τ=1输出四元组(g,ga,gb,gab)；否则τ=0，输出四元组(g,ga,gb,gc)。输出 τ '∈ { 0,1}猜测τ成功的概率是可忽略的，即在G中解决DDH问题是困难的，其成功的优势概率定义为

定理1 在DDH假设和随机预言机模型下，本文方案对于类型Ⅰ敌手 A在选择身份和明文攻击下是安全的。

证明 假设存在敌手A在k (0＜k＜n)次请求后，能够以ε的优势攻破方案，则构建算法B调用敌手A的攻击能力，在概率多项式时间内解DDH问题。B模拟 A的挑战者以四元组作为输入与A进行IND-ID-CPA游戏。

1)Setup：B模拟算法Gen利用四元组(g,Ga=ga,G = gb,Z)构建系统参数Params和主密钥 X 。bPri

S-Step1 生成阶数为素数q的循环群G，任意选择生成元g∈G。选择矩阵

S-Step4 B向敌手公开系统参数 (G ,g,q,YPub)。

2)Random Oracle请求：敌手 A以 I Du， S tru值，这样的假设与一个密钥更新周期内Time为定值是一致的)向B提出Random Oracle请求，B为了回答 A的 Random Oracle请求需要维持一个列表Hlist=(I Du, S tru, H (I Du),H (S tru))，0＜u＜k，列表初始为空。B做出以下回答：

如果 I Du，S t ru在 Hlist中，B向A返回 H (I Du)，H(S tru)；

如果 I Du， S tru不在 Hlist中，B选择 H (I Du)=素使，将 H (IDu)， H (Stru)返回给A，并把 H (S tru)， H (I Du)加入 Hlist。

3) Phase1:敌手 A发起提取私钥请求 S tr1,Str2,… ,S tru(0＜u＜k)。B从Stru中得到IDu，如果IDu， S tru不在 Hlist中，以 Random Oracle请求中b)方式选择 H (I Du)和 H (Stru)，将 H (I Du)，H(S tru)返回给 A，并把 H (S tru)， H (I Du)加入 Hlist。对于H(I Du)中每个 hIjDu从 XPri中选择第 j列的第 ij+1个值xijj，其中，ij(0≤ij＜m)为hIjDu的十进制表示。则

由XIDu，H(Stru)生成节点私钥为

4) Challenge：敌手A选择在Phase1阶段没有查询过的ID， S tr = {I D|T ime}及明文消息 M0，

其中。B选择 b ∈ { 0,1}，将密文 C = ( c1,c2)发送给敌手A，其中如果是 H 中所有listH(S tru) (0＜u＜k)的线性组合，则B出错。

5) Phase2：敌手继续发起提取私钥请求。

6) Guess：B根据A对 Mb的猜测 b'，输出四元组(g,G = ga,G = gb,Z)是否为 DH元组的猜测

a b τ'。如果b'=b，则τ'=1；否则τ'=0。

假设Error是B在仿真挑战A过程中出错的事件，则B调用A的能力解决DDH问题的成功概率为

其中，仿真过程出错后，B猜测成功概率Pr[S uc|Error]为；仿真过程顺利进行，B调用A的能力解决DDH问题成功的概率等于A攻破方案的概率，这与假设是一致的。

B在仿真挑战A过程中出错概率Pr[E rror]为挑战过程中 H (S tr)是 Hlist中所有 H (S tru)(0＜u＜k)的线性组合。在挑战前，敌手A通过提取私钥请求已经拥有一个包括 H (S tru)的规模不超过k×n的矩阵Mk×n，由此可知矩阵Mk×n的秩rankMk×n≤min(k,n)。Mk×n中最多有k个向量线性无关，则线性相关的概率最大为，即出错概率Pr[E rror]满足：

由式(10)和式(11)可知：

如果存在敌手能够以ε的优势攻破方案的假设成立，则构建算法B调用敌手A的攻击能力，在概率多项式内解决DDH问题的概率为其优势概率不可忽略，由此，定理1得证。

在选择节点概率攻击过程中，类型Ⅱ敌手除了具有类型Ⅰ敌手具有的能力外，还具有查询节点预分配主密钥子集的能力，能够获取待攻击节点之外的节点预分配主密钥子集。由此，类型Ⅱ敌手可以通过捕获其他节点来获取待攻击节点的预分配主密钥子集。例如，当主私钥(m = 4 ,l = 2 ,n = 4 )，节点身份标识为 I D0及其散列值为 H (I D0) = 0 1111000时，节点 I D0预分配主密的预分配主密钥子集 XID0，可以通过查询 I D1，ID2， I D3， I D4的预分配主密钥子集得到。其中，ID1， I D2， I D3， I D4的预分配主密钥子集为

假设类型Ⅱ敌手已经查询到k个节点预分配主密钥子集，则该敌手获取节点 I D0预分配主密钥子集的概率为

通过图 1分析式(14)可以看出随着主密钥规模的增大，类型Ⅱ敌手查询k个节点预分配主密钥子集以获取特定节点预分配主密钥子集的概率会逐渐减小。如果类型Ⅱ敌手要以80%以上的概率获得待攻击节点的预分配主密钥子集，当主密钥规模为(2l×n,l=8,n=20)时，类型Ⅱ敌手至少查询1 150个节点的预分配主密钥子集；当主密钥规模增加到(2l×n,l =10,n=64)时，类型Ⅱ敌手查询的节点预分配主密钥子集个数增加到 5 851个。由此，类型Ⅱ敌手查询k个节点预分配主密钥子集获取特定节点预分配主密钥子集的攻击在实际MANET中是不可行的。

4.2 节点密钥更新对比分析

在典型的基于身份的MANET密钥管理中，节点密钥更新过程产生的通信开销主要与分布PKG的门限值和网络规模有关。以n表示PKG主私钥分布到网络中节点的个数，t(t＜n)表示分布 PKG 的门限值，以N表示网络规模，将本文方案PAKMS和2种典型方案进行分析对比(如表1所示)。

图1 类型Ⅱ敌手查询k个节点预分配主密钥子集获取特定节点预分配主密钥子集的概率

从表1中可以看出以上3种方案在节点密钥更新过程中网络通信开销与门限值和网络规模的关系， Khalili[5]和TIDS[6]方案密钥更新过程中的通信次数相同且与 PKG分布门限值与网络规模的乘积有关，并会随着门限值的提高和网络规模的增大而增多，如图2所示。本文方案PAKMS在节点密钥更新过程中与 PKG分布门限值和网络规模无关，仅依赖于时间参数，在能够获得系统精确时间的条件下，不会产生通信开销，从根本上节省了节点能量的消耗。

从表1和图2综合分析可以得出，网络中的所有节点获得一次密钥更新服务时，PAKMS方案比Khalili和TIDS方案在节点间通信次数方面少2×tN次。例如，当 t=51，n=100，N=1 000时，Khalili和TIDS方案中所有节点通过分布式门限PKG更新一次密钥的通信次数为102 000次，网络能量开销为28 743.6W(其中节点收发一次所需的能量消耗以NS2[15]中MANET节点能量模型的典型值281.8mW计算)，平均单节点消耗能量为28.7W。由此，网络中所有节点获得一次密钥更新服务，本文 PAKMS方案中节点消耗功率比以上2种典型方案中节点消耗功率少28.7W。

图2 节点密钥更新中网络所有节点的通信次数

4.3 移动ad hoc 网络密钥管理方案综合比较

从表 2可以看出 PAKMS方案结合了移动 ad hoc 网络密钥管理中基于身份和预分配密钥的方式，在密钥更新、节点密钥存储空间方面更具有优势。与典型的移动ad hoc 网络中基于身份的分布式门限PKG方案[5,6]相比较，在密钥更新方面的优势可以从4.2节得出，而与典型对称预分配密钥管理方案[11,12]比较，本文方案采用预分配主密钥子集不变而更新节点当前使用密钥的非对称密钥管理方式，在密钥功能和节点密钥更新方面具有优势。在密钥存储空间方面，本文方案具有基于身份密钥管理的优点，即无需存储所有节点公钥，只需存储系统参数和获得节点的身份，同时每个节点预分配一个主密钥子集的方式也改善了对称预分配密钥中需要大量存储对偶密钥的缺陷。

表1 PAKMS与典型基于身份的密钥管理方案节点密钥更新对比

表2 密钥管理方案综合比较分析

4.4 方案局限性及下一步工作

1) 本文方案中节点密钥更新过程相对典型基于身份的分布式PKG密钥管理方案降低了网络整体的通信开销，这种性能上的改善是由于密钥更新过程中保持了预分配主密钥子集不变而仅根据时间参数变化节点密钥的方式。由此，本文所提的密钥管理方案需要节点在时间上满足密钥更新需要，由此需要节点能够通过 GPS模块获得精确的时间信息。同时，节点预分配主密钥子集是节点密钥的基础，当敌手具有超过类型Ⅱ敌手能力直接能够读取节点预分配主密钥子集时(比如节点被捕获时)，节点预分配主密钥子集的安全性受到威胁。这时可以采用PTPM[16,17]硬件来存储节点预分配主密钥子集，通过 PTPM 的安全存储能力保护节点预分配主密钥子集的安全性，这种方法是可信计算技术在移动ad hoc 网络中的一种应用，是下一步工作中的第一个着眼点。

2) 本文方案最多允许敌手获取某一节点更新密钥产生的 1n-个私钥，以保证该节点预分配主密钥子集的安全。如果敌手能够获取某一节点更新密钥产生的n个节点私钥，该节点的预分配主密钥子集可以由式(1)计算出来，但此时根据4.1节对选择节点概率攻击的分析可知，敌手获得一个节点预分配主密钥子集几乎不会影响到其他节点预分配主密钥子集的安全性。同时因为敌手已经能够获得节点私钥来解密消息，也就没有再获得节点预分配主密钥子集的意义。由此，这个问题回归到了所有加密系统私钥安全性这个基本问题上来。为了从根本上解决这个问题，可以利用PTPM构建密钥链式结构，通过节点密钥的父密钥加密节点密钥并存储于PTPM中，通过PTPM来增加方案的私钥安全性，这将是下一步工作的另一着眼点。

5 结束语

本文提出了基于身份的预分配非对称密钥管理方案，方案利用私钥生成中心为节点预分配主密钥子集的方式及通过基于时间获得节点密钥更新的方法解决了现有基于身份的密钥管理过程带来的大量通信开销；同时也通过私钥生成中心为节点预分配主密钥子集的方式使节点在网络运行阶段不再依赖私钥生成中心为节点分配和更新密钥，弱化了基于身份密钥管理中存在的私钥托管问题对网络安全的影响。文中详细描述了基于身份的预分配非对称密钥管理方案，并给出了方案的安全性证明，由此表明：1)本文方案在DDH和随机预言机模型假设下，关于选择身份和明文攻击(IND-ID- CPA)是安全的；2)选择节点概率攻击在实际 MANET中是不可行的。同时本文通过对比分析给出了方案的性能评价及下一步的工作重点。

[1] 易平, 蒋嶷川, 张世永. 移动 ad hoc网络安全综述[J]. 电子学报,2005, 33(5):893-899.YI P, JIANG N C, ZHANG S Y. A survey of security for mobile ad hoc networks[J]. Acta Electronica Sinica, 2005, 33(5):893-899.

[2] 华平,胡光明,董攀. 大规模移动自组网络安全技术综述[J]. 计算机研究与发展, 2007, 44(4):545-552.HUA P, HU G M, DONG P. Survey of security technology for large scal manet[J]. Journal of Computer Research and Development, 2007,44(4):545-552.

[3] SHAMIR A．Identity-based cryptosystems and signature schemes[A].Proceedings of the Advances in Cryptology-CRYPTO’84[C]. Berlin:Springer, 1984.47-53.

[4] BONEH D, FRANKLIN M. Identity-based encryption from the weil pairing[J]. SIAM Journal of Computing, 2000, 32(3): 586-615.

[5] KHALILI A, KATZ J, ARBAUGH W A. Toward secure key distribution in truly ad hoc networks[A]. International Symposium on Applications and the Internet[C]. Orlando,USA, 2003. 342-346.

[6] DENG H, AGRAWAL D. TIDS: threshold and identity-based security scheme for wireless ad hoc networks[J]. Ad Hoc Networks, 2004, 2(3):291-307.

[7] SILVA E, SANTOS A L, ALBINI L C P. Identity-based key management in mobile ad hoc networks: techniques and applications[J]. IEEE Wireless Communications, 2008, 15(5):46-52.

[8] CHIEN H Y, LIN R Y. Improved ID-based security framework for ad hoc network[J]. Ad Hoc Networks, 2008, 6(1):47-60.

[9] SUN J Y, ZHANG C, ZHANG Y C. An identity-based security system for user privacy in vehicular ad hoc networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(9):1227-1239.

[10] 南湘浩. CPK密码体制与网际安全[M]. 北京：北京国防工业出版社, 2008.NAN X H. CPK-Crypotosystem and Cyber Security[M]. Beijing:National Defence Industry Press, 2008.

[11] ESCHENAUER L, GLIGOR V D. A key-management scheme for distributed sensor networks[A]. Proceedings of the 9th ACM Conference on Computer and Communication Security[C].Chicago, USA, 2002. 41-47.

[12] RAMKUMAR M, MEMON N. An efficient key predistribution scheme for ad hoc network security[J]. IEEE Journal on Selected Areas in Communications,2005, 23(3):611-621.

[13] 胡亮, 刘哲理, 孙涛. 基于身份的密码学的安全性研究综述[J]. 计算机研究与发展, 2009, 46(9):1537-1548.HU L, LIU Z L, SUN T. Survey of security on identity-based cryptography[J]. Journal of Computer Research and Development, 2009, 46(9):1537-1548.

[14] ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1985, 31(4):469-472.

[15] The NS manual (formerly ns notes and documentation)[EB/OL].http://www.isi.edu/nsnam/ ns/doc/, 2011.

[16] HAN L, LIU J Q, ZHANG D W. A portable TPM scheme for generalpurpose trusted computing based on EFI[A]. MINES'09: International Conference on Multimedia Information Networking and Security[C].Wuhan, China, 2009.140-143.

[17] HAN L, LIU J Q, HAN Z. Design and implementation of a portable TPM scheme for general-purpose trusted computing based on EFI[J].Frontiers of Computer Science in China, 2011,5(2):169-180.