随着云计算技术的迅速发展,用户可以通过互联网享受到各种便捷的服务,越来越多的用户将个人数据外包存储于云服务器端.但是,数据所有权和管理权的分离使得用户数据面临泄露和被篡改的风险.为了保护用户的数据安全和个人隐私,需要安全的认证机制来实现对服务器的访问控制.认证密钥交换协议可以在认证用户身份的同时建立安全的共享密钥,进而实现安全的通信,因此在访问控制中有非常重要的应用.密钥交换协议的认证机制主要包括公钥、对称密钥和口令.口令由于其简单易记、使用便捷和代价低廉等优势成为当前网络中应用最广泛的认证机制.自Bellovin和Merritt提出著名的加密密钥交换协议(encrypted key exchange protocol)以来^[1],口令认证密钥交换协议(简称PAKE协议)得到了广泛的关注,很多两方PAKE协议被提出^[2-6].

两方PAKE协议适用于用户-服务器的认证框架,但是不满足大规模端到端通信的应用需求.假如某个用户想与n个不同的其他用户分别通过口令进行安全通信,那么就需要记忆n个不同的口令,这对于人脑来说是难以承受的负担.为了利用口令实现大规模的端到端通信,Lin等人提出了针对用户-服务器-用户框架下的三方PAKE协议^{[7, 8]}.三方PAKE协议允许分别与服务器共享口令的两个用户在服务器的协助下建立安全的共享密钥.与两方PAKE协议相比,三方PAKE不仅要抵抗在线字典攻击和离线字典攻击,还需要考虑一种特有的不可检测在线字典攻击,因此设计难度更大.2005年,Abdalla等人对可证明安全的三方PAKE协议开展了研究^[9].他们首 先提出了著名的ROR(Real-Or-Random)模型,然后设计了一种利用两方PAKE协议构造三方PAKE的通用构造方法,并在ROR模型下证明了其安全性.同年,Abdalla等人又设计了一个高效的三方PAKE协议,并且在随机预言模型下给出了安全性证明^[10].但是在2006年,Wang等人指出,Abdalla等人提出的三方PAKE协议^{[9, 10]}都不能抵抗不可检测在线字典攻击.Wang等人通过增加消息认证码的方式对Abdalla等人的协议进行了改进^[11].此后,有大量在随机预言模型下可证明安全的三方PAKE协议被相继提出^[12-18].

随机预言模型作为安全证明的一种重要模型,对于协议的安全性具有重要的检验作用.但是随机预言函数在现实中并不存在,随机预言模型下可证明安全的协议在实际应用时只能通过具有良好密码学性质的哈希函数来替代随机预言函数,但这样的替代可能会给协议带来安全隐患.例如,Canetti等人给出了一个在随机预言模型下安全,但通过哈希函数对随机预言函数进行实例化时却不安全的签名方案^[19].与随机预言模型相比,标准模型不需要将协议中使用的哈希函数理想化为真随机函数,是更为自然的协议分析模型.因此,尽管随机预言模型下可证明安全的协议通常具有更高的效率,人们还是更青睐标准模型下可证明安全的协议.2009年,Kwon等人^[20]提出了首个标准模型下可证明安全的三方PAKE协议,并且基于HDH假设证明了协议的安全性.2012年,Yang等人^[21]提出了标准模型下可证明安全的三方PAKE协议,然后在DDH假设下证明了协议的安全性.但是文献^{[20, 21]}中的协议都假设服务器拥有公钥,用户需要储存并验证服务器的公钥,因此用户不能仅仅通过记忆口令实现认证,违背了口令协议便捷性的优势.2014年,Nam等人^[22]利用两方PAKE协议设计了一个可证明安全的三方PAKE协议,但是该协议计算效率和通信效率都很低.到目前为止,标准模型下可证明安全的三方PAKE协议还很少,已有的协议或者假设服务器拥有公钥^{[20, 21]},或者效率较低^[22].针对已有协议存在的不足,我们以基于ElGamal加密的平滑投射哈希函数为工具设计了一个安全高效的三方PAKE协议,并且在标准模型下,基于DDH假设证明了协议的安全性.与已有的协议相比,我们的协议不需要假设服务器拥有公钥,并且具有较高的通信效率和计算效率,因此更符合大规模端到端通信的应用需求.

本文第1节回顾预备知识和证明所需的安全模型.第2节给出我们所设计的标准模型下的三方PAKE协议并证明其安全.第3节给出我们的协议与其他相关协议的安全性和效率比较.最后,第4节总结全文.

1 预备知识 1.1 平滑投射哈希函数

平滑投射哈希函数(smooth projective hash function)最早由Cramer和Shoup^[23]在设计CCA安全的公钥加密算法时提出.之后,平滑投射哈希函数作为一个密码学基本组件被广泛用于构造安全的PAKE协议、非延展的承诺体制以及不经意传输协议等.设X是平滑投射哈希函数的定义域,NP语言L是X的一个真子集.平滑投射哈希函数最重要的性质是对于子集L中的元素x,函数的输出可以分别通过全局密钥和公开的投射密钥这两种方式来计算.全局密钥可以用于计算整个定义域X上的所有函数输出;而投射密钥只对子集L中的元素有效,并且计算函数输出时还需要x∈L的一个证据w.

一个平滑投射哈希函数由以下5个算法(SPHFSetup;HashKG;ProjKG;Hash;ProjHash)组成:

· SPHFSetup(1^k):输入安全参数k,产生方案的全局参数param以及对NP语言L的描述;

· HashKG(L;param):输入全局参数param和NP语言L,生成全局密钥hk;

· ProjKG(hk;L;param;x):根据全局密钥hk和NP语言L中的元素x计算投射密钥hp;

· Hash(hk;L;param;x):根据全局密钥hk和元素x计算函数输出;

· ProjHash(hp;L;param;x;w):根据投射密钥hp、元素x以及证据w计算函数输出.

一个平滑投射哈希函数应该满足以下性质:

· 正确性:给定x∈L以及证据w,那么对于所有的全局密钥hk以及相应的投射密钥hp,我们有:Hash(hk;L;Param;x)=ProjHash(hp;L;Param;x;w);

· 平滑性:对于所有的x∈X\L,分布D₀={(L,param,x,hp,v):v=Hash(hk,L,param,x)}和D₁={(L,param,x,hp,v): v∈{0,1}^k}是统计不可区分的;

· 伪随机性:对于x∈L,在无证据w的条件下,分布D₀={(L,param,x,hp,v):v=Hash(hk,L,param,x)}和D₁={(L,param,x,hp,v):v∈{0,1}^k}是计算不可区分的.

1.2 安全模型

本节简单回顾Kwon等人提出的三方PAKE协议的安全模型^[20],我们将在第2节给出所设计协议在此模型下的安全性证明.

三方PAKE协议的参与者集合有两类,分别是用户集U和服务器集S.每个用户U∈U拥有一个与服务器共享的、从口令空间D中随机选择的口令pw_U.服务器持有一个口令向量$p{{w}_{S}}={{\langle p{{w}_{U}}\rangle }_{U\in \mathcal{U}}}$,其中每一项对应于在服务器端注册的某个用户的口令.每个用户可以并行地执行协议的多个会话实例,用Uⁱ表示用户U的第i个实例.我们通过谕示询问来模拟攻击者的能力.

·$Execute(U_{1}^{{{i}_{1}}},{{S}^{j}},U_{2}^{{{i}_{2}}})$:此询问模拟攻击者的被动攻击能力.攻击者通过此询问,可以获得用户实例$U_{1}^{{{i}_{1}}}$和$U_{1}^{{{i}_{1}}}$以及服务器实例S^j的协议运行的所有交互的消息;

· Reveal(Uⁱ):此询问模拟已知密钥攻击或会话密钥丢失.攻击者通过此询问,可以获得用户实例Uⁱ持有的会话密钥;

· SendClient(Uⁱ,m):此询问模拟攻击者对于用户实例Uⁱ的主动攻击.攻击者冒充服务器给用户实例Uⁱ发送消息m,并得到用户实例Uⁱ接收到消息m后返回的消息;

· SendServer(S^j,m):此询问模拟攻击者对于服务器实例S^j的主动攻击.攻击者冒充用户给服务器实例S^j发送消息m,并得到服务器实例S^j接收到消息m后返回的消息;

· Corrupt(U):此询问用于刻画前向安全.攻击者通过此询问,可以获得用户U的口令并且控制用户U;

· Test(Uⁱ):此询问不模拟攻击者的实际攻击能力,而是用于刻画协议会话密钥的语义安全.对于用户实例Uⁱ,如果该实例没有生成会话密钥,那么返回无定义的符号^;否则进行一次均匀的抛币:

如果抛币结果是1,则返回实例Uⁱ的真实会话密钥;

如果抛币结果是0,那么返回一个与会话密钥等长的随机数;

攻击者需要猜测抛币的结果,即猜测其获得的是真实的会话密钥还是随机数;

·$TestPair(U_{1}^{i},U_{2}^{j})$:此询问不模拟攻击者的实际攻击能力,而是用于刻画协议会话密钥针对服务器的密钥私密性.若用户实例$U_{1}^{i}$和$U_{2}^{j}$不共享会话密钥,那么返回无定义的符号^;否则进行一次均匀的抛币:

如果抛币结果是1,则返回真实会话密钥;

如果抛币结果是0,那么返回一个与会话密钥等长的随机数.

攻击者需要猜测抛币的结果,即猜测其获得的是真实的会话密钥还是随机数.

如果一个用户实例Uⁱ接受协议运行并生成会话密钥,那么我们称该实例接受(accepted).如果攻击者对一个接受的实例Uⁱ进行了Reveal(Uⁱ)查询,我们称该实例被打开(opened).我们定义会话标示sid为两个用户在协议完成时所交互消息中的共享消息的级联.我们称两个用户实例$U_{1}^{i}$和$U_{2}^{j}$是伙伴,如果以下条件成立:(1) 实例$U_{1}^{i}$和$U_{2}^{j}$都接受;(2) 实例$U_{1}^{i}$和$U_{2}^{j}$的会话标示sid相同;(3) 实例$U_{1}^{i}$的意定通信方是$U_{2}^{j}$,反之亦然;(4) 除了$和$U_{1}^{i}$之外,没有任何接受实例的意定通信方是$U_{1}^{i}$或者$U_{2}^{j}$.我们称一个诚实用户的实例 是新鲜的,如果以下的条件成立:(1) 实例$U_{1}^{i}$接受;(2) 攻击者没有对实例$U_{1}^{i}$或其伙伴实例(如果存在的话)进行Reveal查询;(3) 在实例$U_{1}^{i}$结束协议运行之前,攻击者没有对用户U₁及其伙伴(如果存在的话)进行Corrupt查询.

为了考虑协议会话密钥的语义安全性,我们给攻击者A所有谕示询问的能力,但限定攻击者只能对新鲜的会话进行一次Test询问.记Test询问中的抛币结果为b,如果攻击者正确猜测到b的值,则认为攻击者成功,记该事件为Succ.攻击者A破坏协议P的语义安全性的优势定义为$Adv_{\mathcal{P},\mathcal{D}}^{ake-fs}(\mathcal{A})=2\cdot \Pr [Succ]-1$.类似地,我们定义攻击者破坏协议P的语义安全性的优势函数为$Adv_{\mathcal{P},\mathcal{D}}^{ake-fs}(t,R)=\max \{Adv_{\mathcal{P},\mathcal{D}}^{ake-fs}(\mathcal{A})\}$,其中,最大值遍历所有攻击时间为多项式时间、所使用资源为R的攻击者A.我们称三方PAKE协议P是语义安全的,如果$Adv_{\mathcal{P},\mathcal{D}}^{ake-fs}(t,R)$至多比kn/|D|大一个可忽略的量,其中,n是敌手进行主动攻击的次数,|D|表示字典空间的规模,k为常数.

由于三方PAKE协议中用户之间的会话密钥是由服务器协助生成的,为了降低对服务器的信任程度,需要考虑会话密钥对于诚实而好奇的服务器的密钥私密性.即:服务器在没有进行主动攻击的条件下,会话密钥对于服务器来说仍然是不可区分的.考虑一个知道所有用户口令的攻击者A,我们给攻击者A所有谕示询问的能力,但是攻击者A不能对测试会话$TestPair(U_{1}^{i},U_{2}^{j})$进行主动攻击.类似地,我们可以定义攻击者A破坏协议P的会话私密性的优势$Adv_{\mathcal{P},\mathcal{D}}^{kp}(\mathcal{A})=2\cdot \Pr [Succ]-1$以及优势函数$Adv_{\mathcal{P},\mathcal{D}}^{kp}(t,R)=\max \{Adv_{\mathcal{P},\mathcal{D}}^{kp}(\mathcal{A})\}$.我们称三方PAKE协议实现了针对服务器的密钥私密性,如果优势函数$Adv_{\mathcal{P},\mathcal{D}}^{kp}(t,R)$是关于安全参数的一个可忽略的函数.

2 标准模型下的三方PAKE协议 2.1 协议描述

设G_q是一个阶为大素数q的循环群,g,h为随机选择的G_q的两个生成元,且h关于g的离散对数是难解的;pk是定义在群G_q上的一个CCA加密算法E的公钥.需要说明的是:在系统中,任何人都不知道pk对应的私钥.我们用E_pk[m,r]表示用公钥pk对消息m进行加密,其中,r是加密时所用的随机数.我们用Enc_k(m)和Dec_k(m)分别表示使用对称加密算法对消息m利用密钥k进行加密和解密操作.UH:G_q→{0,1}³ⁿ是从通用哈希函数簇UH中随机选择的通用哈希函数,H:{0,1}→{0,1}ⁿ是防碰撞的哈希函数,其中,n是安全参数.用户A和服务器S共享口令pw_A,用户B和服务器S共享口令pw_B.为了简便起见,我们假设口令空间被映射到 中,即,.协议共有3轮消息交互,具体的流程如下:

第1轮.用户A选择一个随机数$x\in Z_{q}^{*}$,然后计算X₁=g^x以及${{X}_{2}}={{h}^{x}}{{g}^{p{{w}_{A}}}}.$这里,X₁和X₂实质上是利用ElGamal加密算法对口令pw_A进行加密后的密文.用户A发送消息(A,X₁,X₂)给服务器S.类似的,用户B选择一个随机数$y\in Z_{q}^{*}$,计算Y₁=g^y以及${{Y}_{2}}={{h}^{y}}{{g}^{p{{w}_{B}}}},$并且发送消息(B,Y₁,Y₂)给服务器S.

第2轮.服务器S接收到来自用户A和B的消息后,首先选择两个随机数${{\lambda }_{1}},{{\lambda }_{2}}\in Z_{q}^{*}$,然后计算$\mu ={{g}^{{{\lambda }_{1}}}}{{h}^{{{\lambda }_{2}}}}$,$X{'_2} = {X_2}{g^{ - p{w_A}}},Y{'_2} = {Y_2}{g^{ - p{w_B}}},{\sigma _A} = X_1^{{\lambda _1}}X_2^{'{\lambda _2}}$和${\sigma _B} = Y_1^{{\lambda _1}}Y_2^{'{\lambda _2}}$.这里,λ₁和λ₂为基于ElGamal加密算法的平滑投射函数的全局密钥,m是对应的投射密钥.s_A和s_B则是服务器分别与用户A和B共享的平滑投射哈希函数的输出.此外,服务器S还选择随机数$z\in Z_{q}^{*}$并计算$X_{1}^{*}=X_{1}^{z}$以及$Y_{1}^{*}=Y_{1}^{z}$.服务器S计算通用哈希函数的输出r_A||t_A1||t_A2=UH(s_A)和r_B||t_B1||t_B2=UH(s_B).这里,r_A和r_B分别用于CCA加密算法的随机输入,t_A1和t_B1分别用作利用对称加密算法加密随机化后的密钥材料$X_{1}^{*}$以及$Y_{1}^{*}$时的密钥,而t_A2和t_B2则用于实现用户向服务器的认证.服务器S计算密文${{C}_{A}}=En{{c}_{{{\tau }_{A1}}}}(Y_{1}^{*})$和${{C}_{B}}=En{{c}_{{{\tau }_{B1}}}}(X_{1}^{*})$,并用r_A和r_B作为随机输入,对${{\sum }_{A}}=H({{X}_{1}},{{{X}'}_{2}},{{C}_{A}},\mu ,A,B,S)$和S_B=H(Y₁, 分别进行加密得到密文w_A 和w_B.最后,服务器S分别发送消息(S,C_A,m,w_A)和(S,C_B,m,w_B)给用户A和B.

第3轮.用户A接收到消息(S,C_A,m,w_A)后,首先利用投射密钥m计算平滑投射哈希函数的输出s_A=m^x,并计算通用哈希函数的输出${{{r}'}_{A}}||{{{\tau }'}_{A1}}||{{{\tau }'}_{A2}}=UH({{\sigma }_{A}});$用户A首先利用${{{\tau }'}_{A1}}$解密C_A得到$Y_{1}^{*}$,并验证w_A是否等于${{E}_{pk}}[{{\sum }_{A}},{{{r}'}_{A}}]$,如果不相等,则拒绝并结束协议运行;否则,用户A计算会话密钥$K=Y_{1}^{*x}$并发送消息$(A,{{{\tau }'}_{A2}})$给服务器S.用户B和用户A执行类似的操作,为了简便起见,这里略去该部分描述.

最后,服务器S接收到消息$(A,{{{\tau }'}_{A2}})$和$(B,{{{\tau }'}_{B2}})$后,验证${{{\tau }'}_{A2}}$和${{{\tau }'}_{B2}}$是否有效:如果有效,则服务器S接受协议运行;如果无效,则说明前面的接入请求来自敌手对某个用户进行的仿冒攻击.如果服务器没有收到消息$(A,{{{\tau }'}_{A2}})$或$(B,{{{\tau }'}_{B2}}),$则同样认为前面的接入请求来自敌手对某个用户进行的仿冒攻击,服务器将采取进一步的措施(如限制用户认证次数等)以保护用户口令(如图 1所示).

注:两个用户A和B在发送最后一轮消息时,已经建立了共享的会话密钥用于后续的安全通信.第3轮消息的目的在于用户向服务器证明其合法身份,从而达到双向认证和抵抗不可检测在线字典攻击的目的.

2.2 安全性证明

本节给出我们所设计的三方PAKE协议的语义安全性的证明.

定理1. 假设A是一个运行时间为t,并且进行了q_send次主动攻击的概率多项式敌手.假设DDH假设在循环群G_q中成立,协议中所使用的对称加密算法满足对于单次加密的CPA安全性,并且公钥加密算法E是CCA安全的,那么敌手A攻击本文的三方PAKE协议的语义安全的优势至多为

$Adv_{\mathcal{P},\mathcal{D}}^{ake-fs}(\mathcal{A})\le \frac{{{q}_{send}}}{|\mathcal{D}|}+neg(n),$

其中,neg(n)表示关于安全参数n的一个可忽略函数.

证明:本定理的证明由一系列混合实验组成:第1个实验从真实的攻击游戏开始,然后逐步对攻击游戏中的模拟规则进行修改,并估计两个相邻实验之间敌手优势差距的上界,直到敌手的攻击优势为0的实验结束.我们首先修改被动攻击的模拟规则,使得被动攻击中不泄露任何口令信息并且会话密钥完全随机,然后逐步修改主动攻击中的模拟规则,使得只有敌手正确猜测口令的条件下才有可能赢得攻击游戏.我们用Adv(A,P_i)表示敌手A在第i个混合实验中的优势.

实验P₀:这个实验模拟了攻击游戏在标准模型下的真实运行.根据敌手优势的定义有:

$Adv_{\mathcal{P},\mathcal{D}}^{ake-fs}(\mathcal{A})=Adv(\mathcal{A},{{P}_{0}}).$

实验P₁:从这个实验开始,我们开始修改对敌手进行的被动攻击Execute询问的模拟规则.对于敌手A进行的$Execute({{A}^{{{i}_{1}}}},{{S}^{j}},{{B}^{{{i}_{2}}}})$询问,我们令用户A正常计算X₁=g^x,但是在计算X₂时,使用在口令空间之外随机选择的一个虚假口令$pw_{A}^{*}$,即${{X}_{2}}={{h}^{x}}{{g}^{pw_{A}^{*}}}.$,类似地,用户B也用虚假口令$pw_{B}^{*}$计算${{Y}_{2}}={{h}^{y}}{{g}^{pw_{B}^{*}}}$.服务器S在模拟时直接令${{{X}'}_{2}}={{h}^{x}}$和${{{Y}'}_{2}}={{h}^{y}}$,并计算${{\sigma }_{A}}=X_{1}^{{{\lambda }_{1}}}{{h}^{x{{\lambda }_{2}}}}$和${{\sigma }_{B}}=Y_{1}^{{{\lambda }_{1}}}{{h}^{y{{\lambda }_{2}}}}.$其余的模拟规则与真实的攻击游戏完全相同.显然,如果存在敌手能够以不可忽略的概率区分实验P₁和实验P₀,那么我们可以构造算法以相同的优势攻破ElGamal加密算法的CPA安全性.这个规约非常直观,因此这里不再赘述.由ElGamal加密算法的CPA安全性,我们有:

$|Adv(A,{{P}_{1}})-Adv(A,{{P}_{0}})|\le neg\left( n \right).$

实验P₂:在这个实验中,我们继续修改对敌手进行的Execute询问的模拟规则.对于敌手A进行的$Execute({{A}^{{{i}_{1}}}},{{S}^{j}},{{B}^{{{i}_{2}}}})$询问,我们在实验P₁修改的基础上进一步从循环群G_q中随机选择s_A和s_B的值.由于在实验P₁中,对于Execute询问的模拟使用的是虚假的口令,因此由基于ElGamal加密算法的平滑投射哈希函数的平滑性保证了s_A和s_B的分布与G_q上的均匀分布是统计不可区分的.根据平滑投射哈希函数的平滑性,敌手区分实验P₁和实验P₂的优势是可忽略的.我们有:

$|Adv(A,{{P}_{2}})-Adv(A,{{P}_{1}})|\le neg\left( n \right).$

实验P₃:在这个实验中,我们继续修改对敌手进行的Execute询问的模拟规则.对于敌手A进行的$Execute({{A}^{{{i}_{1}}}},{{S}^{j}},{{B}^{{{i}_{2}}}})$询问,我们令服务器S随机选择适当长度的r_A||t_A1||t_A2和r_B||t_B1||t_B2,而不是通过通用哈希函数簇计算.相应地,我们令用户端的相应值与r_A||t_A1||t_A2和r_B||t_B1||t_B2一致.由通用哈希函数簇的性质可知:当其输入为G_q中的随机值时,通用哈希函数簇的输出与其值域中的均匀分布式统计不可区分的,因此有:

$|Adv(A,{{P}_{3}})-Adv(A,{{P}_{2}})|\le neg\left( n \right).$

实验P₄:在这个实验中,我们继续修改对敌手进行的Execute询问的模拟规则.对于敌手A进行的$Execute({{A}^{{{i}_{1}}}},{{S}^{j}},{{B}^{{{i}_{2}}}})$询问,我们进一步令服务器在计算CCA加密算法E的密文w_A和w_B时,将输入中的${{{X}'}_{2}}$和${{{Y}'}_{2}}$用G_q中的两个随机值来替代.由于在实验P₃中,我们随机选择了加密时所用的随机输入r_A和r_B,因此,实验P₄和上一个实验的差别至多是敌手攻破加密算法E的CCA安全的优势.其实,这里仅用到CCA加密算法E的CPA安全性.与实验P₁的分析类似,我们有:

$|Adv(A,{{P}_{4}})-Adv(A,{{P}_{3}})|\le neg\left( n \right).$

实验P₅:在这个实验中,我们最后一次修改对敌手进行的Execute询问的模拟规则.首先,在产生公共参数中的h时,我们随机选择$s\in Z_{q}^{*}$并令h=g^s.此外,对于敌手A进行的$Execute({{A}^{{{i}_{1}}}},{{S}^{j}},{{B}^{{{i}_{2}}}})$询问,我们选择G_q中的一个随机值作为会话密钥,而不是通过$K=Y_{1}^{*x}$或者$K=X_{1}^{*y}$来计算.实验P₅和上一个实验的差距至多是敌手攻破DDH假设的优势.给定一个DDH实例(U,V,W),我们利用DH问题的自归约性来证明上述结论.为了模拟$Execute({{A}^{{{i}_{1}}}},{{S}^{j}},{{B}^{{{i}_{2}}}})$询问,我们首先随机选择${{a}_{1}},{{a}_{2}},{{b}_{1}},{{b}_{2}}\in Z_{q}^{*},$然后令${{X}_{1}}={{U}^{{{a}_{1}}}}{{g}^{{{a}_{2}}}}$以及${{Y}_{1}}={{U}^{{{b}_{1}}}}{{g}^{{{b}_{2}}}}.$由于我们令h=g^s,因此可以按照实验P₄的规则正常模拟Execute询问的剩余步骤.最后计算会话密钥的时候,定义会话密钥$K={{({{W}^{{{a}_{1}}{{b}_{1}}}}\cdot {{U}^{{{a}_{1}}{{b}_{2}}}}\cdot {{V}^{{{a}_{2}}{{b}_{1}}}}\cdot {{g}^{{{a}_{2}}{{b}_{2}}}})}^{z}}$.显然,如果W=CDH(U,V),那么上述模拟与实验P₄完全一致;如果W≠CDH(U,V),那么上述模拟与实验P₅一致.如果存在敌手可以以不可忽略的优势区分实验P₄和P₅,那么我们可以以同样的优势攻破DDH假设.我们有:

$|Adv(A,{{P}_{5}})-Adv(A,{{P}_{4}})|\le neg\left( n \right).$

从实验P₅中,我们已经完成了对Execute询问的模拟规则的修改.敌手不能通过Execute询问获得用户口令的任何信息,因为在Execute询问的模拟中我们使用了虚假的无效口令,因此在Execute询问的会话模拟中不包含真实口令的任何信息;此外,由于Execute询问的会话密钥是随机选择的,因此敌手通过Execute询问进行攻击的优势是可忽略的.从下一个实验开始,我们对敌手进行的主动攻击的模拟规则进行修改.

在下一个实验开始之前,我们先进行一些预备工作.如果一条消息是诚实的参与者生成的,即使敌手转发了该消息,依然称该消息是实例产生的;否则,称该消息是敌手产生的.我们用Send₀(A,B,S)表示敌手要求用户开始执行协议的初始激活消息;用SendClient_i(U,m)表示敌手在某个会话的第i轮通信中冒充服务器给用户U发送消息m,用SendServer_i(S,m)表示敌手在某个会话的第i轮通信中冒充用户给用户S发送消息m.在产生公开参数时,除了令h=g^s外,我们还在产生公开参数中加密算法E的公钥pk的同时,记录其对应的私钥sk.

实验P₆:从这个实验开始,我们对敌手进行的主动攻击Send询问的模拟规则进行修改.对于敌手伪造服务器的消息并对诚实用户A(对于用户B的模拟类似)进行的$SendClien{{t}_{2}}({{A}^{{{i}_{1}}}},{{C}_{A}}||\mu ||{{\omega }_{A}})$询问,假设(A,X₁,X₂)是用户A上一轮通信中对应于$Sen{{d}_{0}}({{A}^{{{i}_{1}}}},{{B}^{{{i}_{2}}}},{{S}^{j}})$的回答,我们直接用密钥sk对w_A解密,并验证解密得到的消息是否等于$H({{X}_{1}},{{{X}'}_{2}},{{C}_{A}},\mu ,A,B,S)$,其中,.如果上述验证通过,则认为敌手攻击成功并结束攻击游戏的模拟;如果验证不通过,则拒绝该消息并停止对用户实例${{{X}'}_{2}}={{X}_{2}}{{g}^{-p{{w}_{A}}}}$的模拟.注意:对于敌手简单重放而没有进行修改的消息,这里的模拟规则与实验P₅相同.实验P₆和P₅相比,只是增加了敌手成功的一种方式,因此,敌手在实验P₆的优势将会增加.我们有:

$|Adv(A,{{P}_{5}})|\le Adv(A,{{P}_{6}}).$

实验P₇:在这个实验中,我们对敌手进行的$Sen{{d}_{0}}({{A}^{{{i}_{1}}}},{{B}^{{{i}_{2}}}},{{S}^{j}})$询问的模拟进行修改.对于未被腐化的用户A(或B)接收到$Sen{{d}_{0}}({{A}^{{{i}_{1}}}},{{B}^{{{i}_{2}}}},{{S}^{j}})$后,类似于实验P₁,我们在计算消息(A,X₁,X₂)(或消息(B,Y₁,Y₂))时采用虚假的口令$pw_{A}^{*}$(或$pw_{B}^{*}$).为了保证模拟的一致性,如果敌手在$SendClien{{t}_{2}}({{A}^{{{i}_{1}}}},{{C}_{A}}||\mu ||{{\omega }_{A}})$的询问中只是简单转发了服务器产生的消息,那么我们令用户A将服务器在模拟时产生的r_A||t_A1||t_A2作为自己通用哈希函数的输出;否则类似于实验P₆,我们对消息中密文w_A进行解密来判断敌手是否成功.实验P₇和P₆的差别和敌手攻破DDH假设的优势相等.与实验P₁的分析类似,我们有:

$|Adv(A,{{P}_{7}})-Adv(A,{{P}_{6}})|\le neg\left( n \right).$

实验P₈:在这个实验中,我们对敌手冒充诚实用户A进行的SendServer₁(S^j,A||X₁||X₂)询问的模拟进行修改(敌手冒充诚实用户B的模拟类似).我们直接利用h对应于g的离散对数s对X₂进行解密,如果解密得到正确的口令,那么结束整个攻击游戏,得模拟并认为敌手成功.与实验P₆类似,敌手在这个实验里面只是增加了一种赢得攻击游戏的方式,因此敌手的优势将增加:

$|Adv(A,{{P}_{7}})|\le Adv(A,{{P}_{8}}).$

实验P₉:在这个实验中,我们对敌手冒充诚实用户A进行的SendServer₁(S^j,A||X₁||X₂)询问的模拟继续进行修改(敌手冒充诚实用户B的模拟类似).我们利用s对X₂进行解密后,如果得到正确的口令,则认为敌手赢得了攻击游戏;如果解密得到的不是正确的口令,那么从循环群G_q中随机选择s_A的值.由于敌手对于诚实用户A的口令猜测错误,因此根据平滑投射哈希函数的平滑性,有:

$|Adv(A,{{P}_{9}})-Adv(A,{{P}_{8}})|\le neg\left( n \right).$

实验P₁₀:在这个实验中,我们对敌手冒充诚实用户A进行的SendServer₁(S^j,A||X₁||X₂)询问的模拟继续进行修改(敌手冒充诚实用户B的模拟类似).我们利用s对X₂进行解密后,如果得到正确的口令,则认为敌手赢得攻击游戏;否则在实验P₉的模拟规则的基础上,进一步随机选择r_A||t_A1||t_A2.由通用哈希函数簇的性质可知:当输入为G_q的随机值的时候,通用哈希函数簇的输出与其值域中的均匀分布是统计不可区分的.因此,我们有:

$|Adv(A,{{P}_{10}})-Adv(A,{{P}_{9}})|\le neg\left( n \right).$

实验P₁₁:在这个实验中,我们对敌手冒充诚实用户A进行的SendServer₁(S^j,A||X₁||X₂)询问的模拟最后一次进行修改(敌手冒充诚实用户B的模拟类似).在实验P₁₀模拟规则的基础上,我们在在计算CCA加密算法的密文w_A时,采用在G_q中随机选择的值来替代${{{X}'}_{2}}$,从而保证在敌手没有猜测到正确口令的主动攻击中得不到关于用户口令的任何信息.实验P₁₁与实验P₁₀的差别至多是敌手攻破公钥加密算法E的CCA安全的优势.

与实验P₄的分析类似,但是这里我们需要用到公钥加密算法E的CCA安全性.原因在于:根据我们对敌手进行的$SendClien{{t}_{2}}({{A}^{{{i}_{1}}}},{{C}_{A}}||\mu ||{{\omega }_{A}})$的模拟规则,需要利用CCA攻击游戏中的解密谕示帮助我们解密消息中密文w_A,从而判断敌手是否成功.根据公钥加密算法E的CCA安全性,我们有:

$|Adv(A,{{P}_{11}})-Adv(A,{{P}_{10}})|\le neg\left( n \right).$

实验P₁₂:在这个实验中,我们对敌手冒充诚实用户A进行的$SendServe{{r}_{3}}({{S}^{j}},A||{{{\tau }'}_{A2}})$询问的模拟进行修改(敌手冒充诚实用户B的模拟类似).如果敌手伪造的${{{\tau }'}_{A2}}$与我们随机选择的t_A2相等,那么我们认为敌手成功.

显然,如果敌手在SendServer₁(S^j,A||X₁||X₂)在猜测到正确的口令,我们已经令敌手获胜;如果敌手发送$SendServe{{r}_{3}}({{S}^{j}},A||{{{\tau }'}_{A2}})$,说明敌手在第1轮消息中没有猜到正确的口令.根据模拟规则,我们将从值域中随机选择r_A||t_A1||t_A2,因此,敌手正确猜测到t_A2的概率是可忽略的.我们有:

$|Adv(A,{{P}_{12}})-Adv(A,{{P}_{11}})|\le neg\left( n \right).$

实验P₁₃:在这个实验中,我们最后一次对敌手冒充诚实用户A进行的Send询问的模拟进行修改.如果敌手没有发送$SendServe{{r}_{3}}({{S}^{j}},A||{{{\tau }'}_{A2}}),$但是敌手从服务器在第2轮发送的消息(S,C_A,m,w_A)利用对称加密算法的密文C_A得到了$Y_{1}^{*}$,那么我们认为敌手成功.显然,在这个实验里面,敌手多了一种获胜的方式.但是,由于我们所使用的对称加密对于单次加密是CPA安全的,而我们随机选择通用哈希函数簇的输出,因此随机选择的输出(即对称加密算法的密钥)发生碰撞的概率是可忽略的.根据对称加密的CPA安全性,我们有:

$|Adv(A,{{P}_{13}})-Adv(A,{{P}_{12}})|\le neg\left( n \right).$

现在我们来分析敌手在这个实验里面赢得攻击游戏的几种方式:

· 方式1:对于敌手产生的SendServer₁(S^j,A||X₁||X₂)询问(对于敌手冒充用户B的模拟类似),如果对X₂解密后发现敌手猜测口令正确,则认为敌手赢得攻击游戏;

· 方式2:对于敌手伪造服务器的消息并对诚实用户A进行的$SendClien{{t}_{2}}({{A}^{{{i}_{1}}}},{{C}_{A}}||\mu ||{{\omega }_{A}})$询问(对于敌手冒充用户B的模拟类似),如果对密文w_A解密后发现该密文包含了正确的口令信息,则认为敌手赢得攻击游戏;

· 方式3:敌手在没有正确猜测到口令的条件下,通过$SendServe{{r}_{3}}({{S}^{j}},A||{{{\tau }'}_{A2}})$询问正确猜测到了t_A2的值,同样认为敌手获胜;

· 方式4:敌手没有通过上述的3种方式获胜,但是从密文C_A中得到了$Y_{1}^{*}$,那么我们认为敌手获胜;

· 方式5:敌手成功猜测到Test询问中所使用的随机比特.

显然,敌手通过方式3和方式4获胜的概率是可忽略的.我们用PwGuess表示事件敌手通过方式1或方式2正确猜测到口令;用Success表示事件敌手通过方式5猜测到Test询问中所使用的随机比特而获胜.由于我们在模拟协议运行时,在敌手没有猜测到正确口令的条件下不会在模拟中用到任何口令的信息,因此有:

$\Pr [PwGuess]\le \frac{{{q}_{send}}}{|\mathcal{D}|}$

如果事件PwGuess不发生,那么由于敌手通过方式3和方式4获胜的概率是可忽略的,因此敌手只能通过方式5赢得攻击游戏.但是,由于在敌手进行的主动攻击中,诚实用户的实例由于敌手在第2轮无法产生正确的消息(S,C_A,m,w_A)从而拒绝接受;而在被动的会话中,所有的会话密钥是随机选择的,因此敌手通过方式5成功的概率是$\frac{1}{2}$.忽略方式3和方式4,我们有:

$\begin{align} & \Pr [Success]=\Pr [Success\wedge PwGuess]+\Pr [Success\wedge \overline{PwGuess}] \\ & \text{ }\le \Pr [PwGuess]+\Pr [Success|\overline{PwGuess}]\cdot (1-\Pr [PwGuess]) \\ & \text{ }=\frac{1}{2}+\frac{1}{2}\cdot \Pr [PwGuess] \\ & \text{ }\le \frac{1}{2}+\frac{1}{2}\cdot \frac{{{q}_{send}}}{|\mathcal{D}|}. \\ \end{align}$

综合上面所有的等式结果,定理1得证.

定理2. 假设A_kp是一个运行时间为t并且进行了q_execute次被动攻击的概率多项式敌手.假设DDH假设在循环群G_q中成立,那么敌手A_kp攻击本文的三方PAKE协议的密钥私密性的优势至多为

$Adv_{\mathcal{P},\mathcal{D}}^{ake-kp}(\mathcal{A})\le {{q}_{execute}}Adv_{{{G}_{q}}}^{DDH}(O(t)),$

其中,表示在多项式时间内破解DDH假设的优势.

证明:假设A_kp是一个运行时间为t并且进行了q_execute次被动攻击的概率多项式敌手.如果A_kp可以破坏协议的密钥私密性,那么我们可以通过敌手A_kp的能力来解决DDH问题.

给定DDH问题的一个实例(U,V,W),我们首先根据口令空间D的分布为所有用户选择口令并相应的选择所有的公共参数,并且将所有用户的口令告诉敌手A_kp.在攻击游戏模拟阶段,我们令模拟者随机猜测q_execute次被动攻击中的一次会话作为敌手A_kp的测试会话,对于其余的会话都正常模拟.显然,猜测正确测试会话的概率为1/q_execute.对于猜测的测试会话,我们令X₁=U,Y₁=V,并且随机令服务器选择z,计算$X_{1}^{*}=X_{1}^{z},Y_{1}^{*}=Y_{1}^{z}$.其余的模拟按照协议的描述执行.如果A_kp没有选择预先选定的会话作为测试会话,则跳出本次攻击游戏的模拟;否则,当敌手A_kp对测试会话进行TestPair询问时,我们返回K=W^z作为回答.显然:如果(U,V,W)是Diffie-Hellman三元组,那么返回的是真实的会话密钥;否则,返回的是一个与会话密钥等长的随机数.此时,敌手A_kp赢得攻击游戏的优势等同于解决DDH假设的优势.由于模拟者猜测正确测试会话的概率为1/q_execute,因此定理得证.

3 协议性能比较

在本节,我们对本文的协议和已有的标准模型下的三方口令认证密钥交换协议^[20-22]从效率和安全性两个方面进行比较.

在计算代价方面,我们主要考虑计算代价较高的模幂运算(用e表示)和公钥加解密运算,而忽略其余的运算(诸如哈希函数、对称加密和MAC等).我们采用标准模型下CCA安全的DHIES公钥加密算法来对参与比较的协议中所使用的CCA安全的加密体制进行实例化^[24],从而将公钥加解密的计算代价转化为模幂运算的个数. DHIES算法加密时需要两个模幂运算,解密时需要一个模幂运算.由于形如g^xh^y的两个模幂运算的乘积可以通过一个模幂运算的代价求得,因此对于此类运算,我们只计为一个模幂运算.在通信代价方面,三方口令认证密钥交换协议多用于无线通信环境,而在无线环境下,协议的交互轮数远比通信带宽重要,因此我们主要考虑协议的执行轮数.由于文献^[22]采用了模块化的设计思路,通过安全的两方PAKE协议来构造三方PAKE协议,因此我们用目前标准模型下效率最高的Jiang等人的两方PAKE协议^[5]对该协议进行实例化.在安全性方面,由于参与比较的协议都提供了相同的安全属性,因此我们主要从服务器是否具有公钥证书和证明所基于的困难性假设来进行比较,其中,ODH代表DHIES算法的安全性所基于的Oracle Diffie-Hellman假设.

从表 1可以看出:我们的协议在计算代价方面低于NRK协议^[22],与YC协议^[21]的计算代价相当,而计算代价高于KJL协议^[20],但是我们的协议在通信轮数方面要明显低于NRK协议.虽然NRK协议可以通过标准模型下一轮的PAKE进行实例化从而降低轮数,但是目前,标准模型下最高效的一轮的PAKE中,每个参与者需要至少12个模幂运算^[25],这将会极大增加协议的计算代价.KJL协议虽然只需要两轮通信,并且计算效率高于我们的协议,但是该协议假设服务器拥有公钥证书,并不是完全基于口令认证的;并且,用户需要知道服务器的公钥,这将给用户的使用带来不便.

4 结束语

本文以基于ElGamal加密的平滑投射哈希函数为工具设计了一种安全高效的三方PAKE协议,并且在标准模型下,基于DDH假设证明了其安全性.我们的协议实现了用户和服务器之间的双向认证并且具有前向安全性.与同类的协议相比,新协议完全基于口令实现用户认证,并且具有较高的通信和计算效率.因此,我们的协议更适用于大规模端到端通信的应用环境.