改进的三方口令验证元认证密钥交换协议∗

张启慧,胡学先,刘文芬,魏江宏

1(中国人民解放军战略支援部队信息工程大学,河南 郑州 450001)

2(桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004)

当今,以移动互联网、云计算、大数据为代表的信息技术日新月异,使人们的日常生活不断网络化,资产不断数字化,构造安全的身份认证和密钥交换(AKE)协议逐渐成为保障用户数字化资产安全的关键.在所有的认证方式中,口令认证由于简单易用、方便部署,成为目前应用最为普遍的一种[1].

早在1992 年,Bellovin 等人[2]就开创性地提出第一个真正意义上能够抵抗离线字典攻击的两方口令认证密钥交换(PAKE)协议,其中,用户和服务器利用共享的低熵口令进行认证并生成高熵的会话密钥.PAKE 协议仅仅要求用户记住一个较短的口令,避免了传统的基于对称密钥的AKE 协议对存储初始对称密钥的专用硬件的需求,也无需网络中配有复杂的公钥基础设施,非常方便实际使用.随后,为进一步提高两方PAKE 协议的安全性和效率,密码学家针对两方PAKE 协议的设计与分析进行了深入的探索,基于可证明安全理论构建了适用于PAKE的安全模型[3-6],分别设计了在随机预言模型下安全的两方PAKE 协议[3,4,7,8]和在标准模型下安全的两方PAKE 协议[9-14].国际标准化组织(ISO)等机构还颁布了ISO/IEC 11770-4、IEEE Std 1363.2 等系列相关安全标准,进一步推动了PAKE 协议的广泛应用.

两方PAKE 协议比较适合“用户-服务器”架构下的两方通信,却不适合用在大规模用户相互通信的场合.此时,任何两个需要相互通信的用户都需要预先共享一个口令,从而导致每个用户需要记住多个口令才能支持安全通信.为了降低这一情形下用户记忆和管理口令的负担,三方PAKE 协议随即被提出,其中每个用户仅仅需要和服务器共享一个口令,就可以在服务器的协助下与他人进行安全的密钥交换.由于这类协议在大规模通信中较为实用,密码学家基于不同假设构造了一系列实用的三方PAKE 协议[15,16],并在安全模型下严格地证明了协议的安全性[17-21].

尽管两方、三方PAKE 协议已经得到深入而广泛的研究,密码学家提出了诸多安全、高效的构造方案,满足了不同场合的安全应用,然而,多数已有口令协议关注的是服务器利用明文存储用户口令的情形,没有考虑服务器口令文件泄露所造成的巨大威胁.而现实中关于服务器端存储的口令文件被泄露的案例却是层出不穷[22],亟待在PAKE 协议设计中增加减弱服务器文件泄露造成危害的措施.针对服务器文件泄露问题,常见的解决方案有验证元[23-25]、泄露检测[26]、慢哈希[27]、口令硬化[28]等技术.作为防止服务器文件泄露所造成攻击的技术的典型代表,验证元技术是指服务器端使用口令的变换值而非口令本身进行认证,使得攻击者在获得服务器口令文件后至少需要进行离线字典攻击才能获得原始的口令,有效地减弱了服务器口令文件泄露所造成的危害.

针对基于验证元的三方PAKE 协议,杨等人[29]提出了首个标准模型下的协议构造.他们利用带标签的公钥加密体制、平滑投射哈希函数等组件构造了一个基于验证元的三方PAKE 协议,并在标准模型下分析了所提出协议的安全性.本文中,我们分析指出该协议并未达到所声称的安全性,难以抵抗离线字典攻击.其次,在分析已有协议缺陷的基础上,通过借鉴标准模型下PAKE 协议设计的新技术,我们利用改进的平滑投射哈希函数构造了一个新的基于验证元的三方PAKE 协议,并在广泛接受的安全模型中对其进行了严格的安全性证明.最后,还将所提出的基于验证元的三方PAKE 协议与已有协议进行了安全性和效率比较,结果表明,新提出的协议在提供了更高安全性的同时具有可接受的计算和通信效率.

1 相关密码学组件和假设

1.1 公钥加密体制

一个公钥加密体制含有3 个算法PKE=(KG,Enc,Dec),其中,密钥生成算法KG在输入安全参数k时,输出公私钥对(pk,sk)←KG(1k),加密算法Enc在输入公钥pk、明文m以及随机数r时,输出对应的密文c←Enc(pk,m;r),解密算法Dec在输入私钥sk、合法密文c时,输出对应的明文m←Dec(sk,c),如果输入的密文不合法,解密算法输出⊥.

如果公钥加密算法能够抵御选择密文攻击(CCA),则称它是CCA 安全的.在CCA 攻击中,攻击者A 除了能够获得加密公钥pk外,还具有访问解密预言Odec(c)=Dec(sk,c)的能力.攻击者A 自适应地选择两个明文m0和m1,模拟者选择随机的比特b∈{0,1}并计算挑战密文c*=Enc(pk,m).如果攻击者在不向解密预言询问c*的条件下,输出猜测b′,则定义攻击者的优势以及相应的优势函数分别为

其中,最大值函数跑遍所有计算时间至多为t,询问解密预言的次数至多为qdec的CCA 攻击者.在上述定义中,如果不提供给攻击者访问解密预言的能力,而仅仅让其获得公钥pk,则相应的攻击是选择明文攻击(CPA),此时安全的加密算法被称为CPA 安全的.

在PAKE 协议设计中,我们需要用到公钥加密体制的一种变体,称为带标签(label)的公钥加密体制,其定义类似于传统的公钥加密体制,不过,要求加密算法和解密算法能够接受将标签l作为一个额外的公开输入(形如c←Enc(pk,m;l;r)),且仅当解密算法输入和加密算法完全一样的标签时才能解密得到正确的明文.关于带标签的公钥加密体制的CCA 安全性,其定义与传统公钥加密算法类似,不同之处在于,攻击者询问解密预言时要同时提供密文和标签,攻击者在选择挑战明文m0、m1时也需要同时提供一个挑战标签l*.

1.2 平滑投射哈希函数

平滑投射哈希函数最初是由密码学家Cramer 和Shoup[30]提出的,随后被Katz 等人[31]和Benhamouda 等人[13]加以改进用于通信高效的PAKE 协议构造.粗略地说,它是一种双密钥的哈希函数,给定集合X以及语言L⊂X,对任意的词语c∈L,其相应的哈希值可以用两种方式计算:利用哈希密钥hk和c,或利用投射密钥hp和相应于c∈L的证据w.具体而言,一个平滑投射哈希函数SPHF=(HashKG,ProjKG,Hash,ProjH)由4 个算法组成,其中密钥生成算法HashKG在输入安全参数k时输出哈希密钥hk←HashKG(1k),投射密钥生成算法ProjKG在输入哈希密钥hk、语言L以及相应的元素c∈X时输出相应的投射密钥hp←ProjKG(hk,L,c),哈希函数Hash在输入哈希密钥hk、语言L以及任意元素c∈X时输出哈希值h←Hash(hk,L,c),投射哈希函数ProjH在输入投射密钥hp、语言L、词语c∈L以及相应证据w时输出哈希值h←ProjH(hp,L,c,w).

平滑投射哈希函数应该满足正确性和平滑性两个特性.正确性是指,对任意合法的词语c∈L以及相应证据w,Hash(hk,L,c)=ProjH(hp,L,c,w)成立;平滑性是指,对任意的不属于给定语言的元素c∉L,即使在已知hp的条件下,Hash(hk,L,c)也和完全随机选取的输出是统计不可区分的.当安全参数为k时,记εSPHF(k)为这两个分布的统计距离的一个可忽略的上界.

1.3 口令哈希机制

Benhamouda 等人[25]形式化地给出了口令哈希机制的严格定义,用来描述基于验证元的口令协议中验证元的生成方式.一个口令哈希机制PHS 通常由5 个算法组成,其中参数生成算法PSetup在输入安全参数k以及口令比特位数n时输出公开参数param←PSetup(1k,1n),预盐值生成算法PPHSalt在输入参数param时输出随机的预盐值sP←PPHSalt(param),预哈希值生成算法PPreHash在输入参数param、预盐值sP和口令π时输出预哈希值P←PPreHash(param,s P,π),预盐值sP和预哈希值P主要是客户端使用;盐值生成算法PSalt在输入参数param时输出随机的盐值sH←PSalt(param),验证元生成算法PHash在输入参数param、盐值sH和口令π时输出哈希值H←PHash(param,s H,π),盐值sH和哈希值H被服务器端用作验证元.

为了保证服务器口令文件泄露后让攻击者尽可能难地获得用户的口令,需要保证加盐操作后攻击者只有对每个验证元进行独立的离线字典攻击才能获得相应的口令,为此,Benhamouda 等人[25]给出了紧单向性(tight one-wayness)的定义.为了让口令哈希机制能够适配PAKE 协议设计中的平滑投射哈希等操作,文献[25]还给出了一个基于代数运算的口令哈希机制.

1.4 DDH假设

设q是素数,G是q阶乘法循环群,g∈G是其中的一个生成元.判定型Diffie-Hellman(DDH)假设是指,对所有概率多项式时间的攻击者A,其成功区分{(g x,g y,gxy):x,y∈Zq}和{(g x,g y,g z):x,y,z∈Zq}上的均匀分布的优势都是可忽略的.定义相应的优势函数为,则DDH 假设成立意味着是安全参数的可忽略函数.

2 安全模型

本节介绍用于分析三方PAKE 协议的安全模型,该模型首先由Abdalla 等人提出[5],随后,文献[29,32]对其进行了改进.此外,在定义攻击者优势时,考虑到真实口令分布并不服从均匀分布,而是服从严重偏态的Zipf 分布[33],我们采用了类似于文献[34]的方式对其进行了改进.

协议参与方.三方PAKE 协议的参与方包含两个集合:所有用户组成的集合U以及可信服务器组成的集合S.其中,用户集合U又分为诚实用户集合C和恶意用户集合E,恶意用户集合形式化了意图攻击其他用户的恶意用户.不失一般性,常常假设服务器集合仅包含一个元素S={S}.

长期密钥.用户集合U中的每一个用户U∈U都拥有一个口令πU,服务器拥有口令列表pwS=〈pwS[U]〉U∈U,其中,pwS[U]={sU,HU}由口令πU相对应的盐值sU和口令哈希值HU组成.

协议运行模型.假设每个用户或服务器都可能同时运行多个会话,记Ui表示用户U的第i个会话,Sj表示服务器S的第j个会话.概率多项式时间(PPT)攻击者A 完全控制通信网络,可以随意窃听、修改、伪造、延迟、删除消息.形式化地讲,攻击者具有询问下述预言的能力.

●SendClient(Ui,m):模型化攻击者对用户会话的主动攻击.攻击者将消息m发送给用户会话Ui,然后输出会话Ui在收到消息m后的响应消息.

●SendServer(Sj,m):模型化攻击者对服务器会话的主动攻击.攻击者将消息m发送给服务器会话Sj,然后输出会话Sj在收到消息m后的响应消息.

●Reveal(Ui):模型化会话密钥泄露或丢失.攻击者发给该询问,即可获得会话Ui的所拥有的会话密钥.

●Corrupt(U):模型化敌手腐化用户攻击.攻击者发出该询问,即可获得用户U的口令以及用户U中所有会话的内部状态.

●Corrupt(S):模型化敌手腐化服务器攻击.攻击者发出该询问,即可获得服务器S中存储的口令列表pwS=〈pwS[U]〉U∈U=〈{sU,HU}〉U∈U.

●Test(Ui):用以刻画会话密钥的安全性.如果用户会话Ui已经生成会话密钥,则抛掷一枚均匀的硬币b∈{0,1}.若b=1,输出会话Ui的真实会话密钥;若b=0,输出与会话密钥等长度的随机比特串.

对每个用户会话Ui,记为会话标识,为其意定通信会话.如果一个会话顺利完成且已生成会话密钥,则称其为已经接受(accepted).

匹配会话.称两个会话是匹配的,如果:(1)都已接受;(2)有相同的会话标识sid;(3)互为意定通信方;(4)除会话外没有其他会话的意定通信方为.

新鲜会话.称一个会话Ui是新鲜的,如果:(1)Ui已接受;(2)攻击者未对Ui或其匹配会话发起Reveal询问;(3)在会话Ui接受之前,攻击者未对用户U以及服务器发起过Corrupt询问.

语义安全.在协议运行过程中,PPT 攻击者A 能以任意顺序发出Execute、SendClient、SendServer、Reveal和Corrupt询问,但只能针对某个新鲜的用户会话发出一次Test询问.最终,A 输出一个比特b′作为Test中的随机比特b的猜测,若b′=b,则认为攻击者攻击成功,并记该事件为Succ.假设所攻击的协议为P,相应口令字典为D,我们定义攻击者A 的优势为=2Pr[Succ]-1.若对所有发起主动攻击的次数至多为qsend的PPT 攻击者A,其优势只比大一个可忽略量,则称协议P是语义安全的,其中,C′和s′是相应于字典D的Zipf 参数[33].例如,当利用天涯论坛泄露的口令集作为口令分布的模型时,可以得到C′=0.062239 和s′=0.155478[34].

会话密钥私密性.为了防止诚实但好奇的(Honest-but-Curious)服务器获知最终的会话密钥,需特别考虑一个知道所有用户口令的攻击者A,并假设A 能够询问Execute、SendClient、Reveal和Corrupt预言以及下述TestPair预言.

最终,A输出一个比特b′作为TestPair 中的随机比特b的猜测,若b′=b,则认为攻击者攻击成功,并记为Succkp.相应地定义攻击者A的优势为=2Pr[Succkp]-1.若对所有的PPT 攻击者A,其优势是安全参数的可忽略函数,则称协议P相对于诚实但好奇的服务器能够保证会话密钥的私密性.

3 一个基于验证元的3PAKE 协议的安全缺陷

本节我们首先回顾杨等人[29]提出的基于验证元的三方PAKE 协议(简记为Yang-V3PAKE 协议)的详细步骤,然后提出了针对Yang-V3PAKE 协议的离线字典攻击.

3.1 杨等人提出的协议

Yang-V3PAKE 协议采用了文献[24]中给出的口令哈希机制的具体构造,其中,参数生成算法PSetup输出为(p,G,g,h),G是阶为素数p的循环群,g、h是其中两个独立生成元.预哈希值生成算法PPreHash的输出为,哈希算法PHash的输出为H=(H1,H2)=.

假设用户A和用户B想要在服务器S的协助下进行安全的密钥交换,其中,A和B分别拥有口令πA和πB,服务器S拥有相应验证元,则Yang-V3PAKE 协议的具体步骤如下.

(1)服务器S选择两个随机数s A,sB∈RZp,分别计算,然后发送消息给用户A,发送消息给用户B;

(2)用户A收到消息后,运行平滑投射哈希密钥生成算法HashKG,生成哈希密钥hk=(η1,η2,θ,μ,γ),计算ωA=hμ,,并利用ωAS计算MAC 认证值σAS=(A||B||S||),然后选择随机数rA∈RZp计算并向服务器发送消息;类似地,用户B收到消息(,H1B)后,选择随机哈希密钥和随机数rB∈RZp,计算ω B,,TB,ωBS,σBS,e′,并向服务器发送消息.

(3)服务器S接收到消息后,首先计算,然后验证σ AS,σBS的有效性.当验证都通过时,服务器计算,生成MAC 值λAS=(A||B||S||eAS),λBS=(A||B||S||eBS),接着向用户A和B分别发送消息(e AS,e BS,λAS)和(eBS,e AS,λBS).

(4)用户A收到消息(e AS,e BS,λAS)后,首先验证MAC 值λAS是否有效.验证通过后,计算,l=(A,B,hp),,ξ=H k(l,u,eAS),然后,用户A给用户B发送消息hp=(hp1,hp2),CAS=(u1,u2,e AS,v);类似地,用户B收到消息(e BS,e AS,λBS)且λBS验证通过后,相应的计算并发送消息hp′=给用户A.

(5)用户A和B收到对方发送的消息后,分别计算,根据平滑投射哈希函数的性质可以保证skA=skB.

文献[29]声称,Yang-V3PAKE 协议能够提供会话密钥的语义安全性、前向安全性、针对服务器的密钥私密性,还能够抵抗不可测在线字典攻击和服务器泄露攻击.根据安全模型的定义,协议满足语义安全性是指攻击者成功的优势至多为O(qs/2β)+negl(k),其中,qs为攻击者进行在线字典攻击的次数,这意味着攻击者不能针对协议实施离线字典攻击.

3.2 对Yang-V3PAKE协议的攻击和分析

本小节首先给出对Yang-V3PAKE 协议的离线字典攻击.我们注意到,文献[29]中假设攻击者A 完全控制着通信信道,可以窃听、插入、修改消息,或是创建、重发、转发消息.其次,Yang-V3PAKE 协议中服务器发送了第1 轮消息,用户在收到消息后就利用口令对其进行运算计算得到第2 轮的回复消息,且该回复消息中包含一个可用于验证的MAC 值.

假设用户A和用户B想要在服务器S的协助下进行安全的密钥交换,用户A和B的真实口令分别为πA和πB.攻击者A 按照如下方式对用户A的口令进行离线字典攻击.

(1)攻击者A 选择随机数r1和r2,计算,然后攻击者A 冒充服务器S向用户A发送消息,H1A.

(2)用户A收到消息后,将利用其真实口令πA进行下述运算.首先,运行平滑投射哈希密钥生成算法HashKG生成哈希密钥hk=(η1,η2,θ,μ,ν),然后利用口令πA计算ωA=hμ,,并利用ωAS计算MAC 认证值σAS=,然后选择随机数rA∈RZp计算并向服务器S发送消息.

(3)攻击者A 拦截得到上述消息,逐个地穷举所有可能的口令,然后利用这个猜测的口令计算,并检验=σAS是否成立,如果等式成立,则输出当作用户A的口令.

4 改进的基于验证元的3PAKE 协议

鉴于Yang-V3PAKE 协议是首个在标准模型下设计的基于验证元的三方PAKE 协议,但是该协议并没有满足三方PAKE 的安全需求,本节中我们提出一个新的改进的基于验证元的三方PAKE 协议,并在标准模型下对所构造的协议进行严格的安全性证明.

4.1 协议描述

本节给出我们改进的基于验证元的3PAKE 协议的详细设计,记为I-V3PAKE 协议,该协议用到了文献[11,21]中的PAKE 的设计技术以及文献[25]中针对验证元的验证技术.

I-V3PAKE 协议用到了CPA 安全的ElGamal 公钥加密体制PKE′=(KG′,Enc′,Dec′)和一个CCA 安全的带标签的公钥加密体制PKE=(KG,Enc,Dec).记ElGamal 公钥加密体制PKE′所对应的公钥为pk′=(g,h),明文m所对应的ElGamal 密文为c←Enc′(pk′,m;r)=(u=g r,e=h r⋅m),记公钥加密体制PKE 所对应的公钥为pk.尽管协议设计使用了公钥加密体制,但是并没有依赖公钥基础设施(PKI),只需如同文献[11]一样,将这两种加密算法的公钥pk′和pk当作协议运行环境设置中的公共参考串(CRS).

协议采用了如下代数口令哈希机制PHS,其中,sP=⊥,P=gF(π),s=sH∈R{0,1}k,H=sF(π),F(⋅)是从口令空间到指数集Zq上的变换.定义语言

假设用户A和用户B想要在服务器S的协助下进行安全的密钥交换,其中,A和B分别拥有口令πA和πB,服务器S拥有相应验证元(s A,HA=)和(s B,HB=),则I-V3PAKE 协议的具体步骤如下.

(1)用户A选择随机数rA∈Zp,计算口令的预哈希值PA=对应的ElGamal 密文cAS=(uA=,eA=⋅PA),然后发送消息〈A,B,cAS〉给服务器S;类似地,用户B选择随机数rB∈Zp,计算口令的预哈希值PB=对应的ElGamal 密文,然后发送消息〈B,A,cBS〉给服务器S.

(2)服务器S收到消息后,先为用户A选择随机数hkA=(x A,y A,zA),计算,设置lA=A||B||S||cAS||hp1A||hp2A,MA=s A||HA,并用tkA作为加密的随机数计算cSA=Enc(pk,M A;l A;tkA),并发送消息〈s A,hp1A,hp2A,cSA〉给用户A;类似地,为用户B选择随机数hkB=(x B,yB,zB),计算hp1B=,tk B||mk B=Hash(hk B,L B,cB)=,设置lB=B||A||S||cBS||hp1B||hp2B,MB=s B||HB,并用tkB作为加密的随机数计算cSB=Enc(pk,M B;l B;tkB),同时发送消息〈s B,hp1B,hp2B,cSB〉给用户B.

(3)用户A收到〈hp1A,hp2A,cSA〉后,首先计算tk A||mk A=ProjH((hp1A,hp2A),L A,c A,(rA,πA))=,然后利用tkA作为随机数重新计算=Enc(pk,M A;l A;tkA),并验证与其接收到的cSA是否相等.如果验证不相等,则立即结束会话;如果验证通过,则用户A选择随机数x∈Zp,计算X=gx,σAS=MAC(mk A,A||B||S||X),然后向服务器S发送消息〈X,σAS〉;类似地,用户B收到消息〈hp1B,hp2B,cSB〉后,计算tk B||mkB并验证cSB,验证通过后选择随机数y∈Zp,计算Y=gy,σBS=MAC(mk B,B||A||S||Y),然后向服务器S发送消息〈Y,σBS〉.

(4)服务器S收到消息后,首先用密钥mkA和mkB验证MAC 值σAS和σBS是否正确,验证通过后计算σSA=MAC(mk A,A||B||S||X||Y),σSB=MAC(mk B,B||A||S||Y||X),然后向用户A发送消息〈Y,σSA〉,向用户B发送消息〈X,σSB〉.

(5)用户A和B在收到来自服务器的消息后,分别利用密钥mkA和mkB验证MAC 值σSA和σSB是否正确,验证失败,则结束会话.然后,用户A计算会话密钥为skAB=Yx,用户B计算会话密钥为skBA=Xy.

在用户和服务都诚实运行协议的情况下,对与用户A相关的语言LA=而言,下式成立:

可知用户A和服务器S将计算得到相同的tk A||mkA,保证了cSA、σAS、σSA的正确性;类似地,用户B和服务器S将计算得到相同的tk B||mkB,保证了cSB、σBS、σSB的正确性.因此,协议中验证都将通过,最终A和B将生成相同的会话密钥skAB=Yx=gxy=Xy=skBA.

注1.在I-V3PAKE 协议中,我们利用具有良好代数性质的口令哈希机制和特别构造的平滑投射哈希函数实现了对口令和验证元的验证.一方面,用户在利用投射密钥计算哈希值ProjH(hp,Ls,H,c,(r,π))=时需要用到F(π),验证了用户确实拥有F(π)和π;另一方面,语言Ls,H={(u,e):∃r,∃π,u=g r,e=h r gF(π),H=sF(π)}的定义方式保证了e=h r g F(π)中的g F(π)部分相对于g的指数与H相对于s的指数是相等的,即证实了服务器确实拥有与用户相匹配的验证元.

注2.I-V3PAKE 协议能够抵御针对Yang-V3PAKE 协议[29]的离线字典攻击.具体地,如果攻击者仿照第3.2节中提到的攻击方法将I-V3PAKE 协议的第1 轮消息替换成伪造的消息,则只要攻击者未猜对用户U∈{A,B}的口令,将由于ElGamal 密文(u,e)∉Ls,H使得服务器计算得到的tk U||mkU对攻击者来说是完全随机的,从而攻击者无法通过验证cSU来判别其猜测口令的正确性.

4.2 协议比较

本节给出I-V3PAKE 协议与其他典型的三方PAKE 协议在功能、安全性、效率方面的比较,具体结果见表1.在表1 中,“验证元”“标准模型”“抗离线字典攻击”“C2S 认证”“Key Privacy”分别表示所考虑的三方PAKE 协议是否支持验证元、是否在标准模型下可证明安全、是否提供抗离线字典攻击、用户到服务器的显式认证以及会话密钥针对服务器的私密性,“计算效率A/B/S”表示用户A、B和服务器S分别所需的计算模指数运算的次数.如同文献[32],我们采用标准模型下CCA 安全的DHIES 公钥加密算法[35]来实例化协议中的公钥加密算法PKE.另外,注意到形如gxhy的多指数运算可以通过快速算法在约等于单个指数的计算时间内完成[32],因而在计算效率中只算作一次指数运算.

从表1 中的结果可以看出,目前只有文献[29]和我们的I-V3PAKE 协议是基于验证元的,且是在标准模型下设计的,但是文献[29]中的协议不能抵抗离线字典攻击,因而安全性不能满足实用要求.尽管文献[32,36]中的协议也是在标准模型下可证明安全的,但是这两个协议都不是基于验证元的,因此不能抵御服务器泄露攻击.另外,从通信和计算效率上看,我们的I-V3PAKE 协议在额外的通过验证元方式保护口令的条件下,还具备与文献[29,32,36]较为接近的通信和计算复杂度,甚至I-V3PAKE 协议的计算效率要更优于文献[29].因此,I-V3PAKE 协议不仅提供了更强的安全性保障,同时具有可接受的计算和通信效率.

Table 1 Comparisons between I-V3PAKE protocol and other verifier-based 3PAKE protocols表1 I-V3PAKE 协议与其他典型三方PAKE 协议的比较

5 安全性证明

本节在前述安全模型中证明I-V3PAKE 协议的安全性,首先证明I-V3PAKE 协议满足语义安全性,然后证明协议中诚实用户所生成的会话密钥相对于诚实而好奇的服务器具有私密性.

定理1.如果公钥加密体制PKE=(KG,Enc,Dec)是CCA 安全的,ElGamal 公钥加密体制PKE′=(KG′,Enc′,Dec′)是CPA 安全的,Ls,H是按照式(1)定义的与公钥加密体制PKE′及口令哈希机制PHS 相关联的语言,SPHF是相应于语言Ls,H的平滑投射哈希函数,MAC 是安全的消息认证码,则I-V3PAKE 协议是语义安全的.

证明:假设A 是针对I-V3PAKE 协议语义安全性的攻击者,其计算时间至多为t,访问Send和Execute预言的次数至多为qsend,qexe.下面通过构造游戏序列G0,G1,...,G8来估计攻击者的优势,起始游戏是安全模型所定义的与真实协议交互的游戏.

游戏G0:这个游戏对应于安全模型中语义安全定义时的真实攻击,记此时攻击者的优势为

游戏G1:从这个游戏开始,我们先逐步修改对Execute询问的模拟方式.游戏G1中,在模拟Execute询问时,首先将用户端利用ProjH的计算全部替换成对应的Hash 计算.由于Execute中用户和服务器都是诚实的,因而上述替换可行;又根据平滑投射哈希函数的正确性定义,可知在游戏G1中攻击者具有和在游戏G0中相同的优势,即Adv1(A)=Adv0(A).

游戏G2:在模拟Execute时,对任意用户U∈{A,B},我们将用户第1 条消息中的密文cUS=Enc′(pk′,PU;rU)=替换成cUS=Enc′(pk′,P0;rU)=(uU=,eU=⋅P0),其中,P0是一个虚拟口令π0(即不属于口令字典中的一个值)所对应的预哈希.根据ElGamal 公钥加密体制PKE′的CPA 安全性,可知P0和PU的密文是不可区分的,从而利用标准的混合(hybrid)证明技术将qexe个Execute预言中的密文逐个替换可知,攻击者在游戏G2与在游戏G1中的优势差是可忽略的,即

其中,式(4)考虑到了CPA 攻击者在模拟协议运行时,只有在模拟Send和Execute类预言时才需要进行额外的计算,在模拟Reveal和Corrupt询问时只需要返回对应状态,从而其计算时间至多为t+O(qsend+qexe).

游戏G3:在模拟Execute询问时,我们将tkU||mkU=Hash(hkU,LU,cU),U∈{A,B}替换成随机选择的等长比特串.由于游戏G2已将cUS替换成P0的密文,从而有cUS∉L A,cUS∉LB,根据平滑投射哈希函数的平滑性质,可知攻击者在游戏G3与在游戏G2中的优势差可忽略,即记εSPHF(k)为平滑投射哈希函数在输入非语言元素时的输出哈希值与均匀分布之间的统计距离的一个可忽略的上界,则有

游戏G4:在模拟Execute询问时,我们将cSA=Enc(pk,M A;l A;tk A),cSB=Enc(pk,M B;l B;tkB)中的MA和MB替换成MA=s A||H0,A,MB=s B||H0,B,其中,H0,A=,H0,B=是对应于不属于字典的一个虚拟口令π0∉D.由于tkA和tkB在游戏G3中已被替换成完全随机的比特串,因此根据加密体制PKE=(KG,Enc,Dec)的CCA 安全性,可知攻击者在游戏G4与在游戏G3中的优势差是可忽略的,因此,

需要说明的是,在游戏G4中并没有询问加密体制PKE 的解密预言,从而实际上只用到了PKE 体制的CPA安全性.但是,在下面的游戏G10中需要询问解密预言,因此需要PKE 是CCA 安全的.

游戏G5:在模拟Execute询问时,我们直接将最终的会话密钥skAB=skBA替换成随机值.利用DDH 自规约技术,我们证明攻击者在实验G4和G5中的优势差至多为攻击者区分DDH 三元组的优势.给定DDH 三元组(X0,Y0,Z0),当用户A需要生成消息X和σAS时,我们选择随机的a,x∈Zp,并计算X=,当用户B需要生成消息Y和σBS时,选择随机的b,y∈Zp,并计算Y=,当双方需要生成密钥时,计算skAB=skBA=.可以看出,当三元组(X0,Y0,Z0)满足Z0=DH(X0,Y0)时,上述游戏和游戏G4完全一样;当Z0≠DH(X0,Y0)时,上述游戏和游戏G5是一样的.在DDH 问题困难假设下,可知

至此,我们已将Execute模拟中的与口令相关的消息和会话密钥替换成为随机值,从而攻击者不能从中获得用户口令的信息.下面将开始修改对敌手主动攻击类询问的模拟.为了表述简单,下面用SendClient0(Ui)表示攻击者激活用户的初始消息,SendClient d(Ui,m),d∈{2,4}表示在第d轮通信中给用户会话Ui发送消息m,SendServerd(S j,m),d∈{1,3}表示在第d轮通信中给服务器会话Sj发送消息m.在公开参数产生阶段,我们还让模拟者记录对应于公钥pk′和pk的私钥sk′和sk.

游戏G6:本游戏修改针对用户A的SendClient2(Ai,〈hp1A,hp2A,cSA〉)的回答方式,对用户B按照类似的方式进行处理(下同).先检查〈hp1A,hp2A,cSA〉是否来源于某个诚实模拟的1(j,*)SendServer S的回复,如果答案是否定,则直接解密cSA得到s′A和H′A并检查与用户A的口令πA是否匹配.若成立,则直接认为攻击者A 攻击成功并结束模拟.如果验证不通过,则让Ai拒绝该消息并结束该会话的模拟.容易看出,上述修改增加了攻击者成功的途径,因此有Adv5(A)≤Adv6(A).

游戏G7:本游戏继续修改针对用户A的询问SendClient2(Ai,〈hp1A,hp2A,cSA〉)响应的模拟.若消息〈hp1A,hp2A,cSA〉确实来源于某个诚实模拟的SendServer1(Sj,*)的回复,则不再按照协议规范为Ai计算tk A||mkA,而是直接将Ai中的tk A||mkA设置成与Sj中一样的值.此时,由于会话Ai和Sj都是诚实模拟的,故上述修改并不改变攻击者的优势,即Adv6(A)=Adv7(A).

游戏G8:本游戏修改针对用户的激活消息0(i)SendClient A响应的模拟方式.类似于游戏G2,我们将其中的替换成虚拟口令所对应的P0的密文.由于加密体制PKE′是CPA 安全的,从而攻击者在游戏G8与在游戏G7中的优势差是可忽略的,即

游戏G9:本游戏修改服务器在收到消息SendServer1(S j,〈A,B,cAS〉)的响应方式.直接利用私钥sk′对密文cAS进行解密,并验证其中的PA与用户口令πA是否匹配.如果匹配,则直接认为攻击成功,停止模拟;如果不匹配,则按照完全随机的方式选择tk A||mkA.可以看出,第1 部分修改仅仅是增加了攻击者成功的途径,而第2 部分修改的合理性则由平滑投射哈希函数的随机性保证,从而可得

游戏G10:本游戏继续修改服务器在收到消息SendServer1(Sj,〈A,B,cAS〉)的响应方式.类似于游戏G4,我们将cSA=Enc(pk,M A;l A;tk A),cSB=Enc(pk,MB;l B;tkB)替换成消息MA=s A||H0,A,MB=s B||H0,B的密文,其中,H0,A==,H0,B=.由于tkA和tkB已被替换成完全随机的比特串,因此根据加密体制PKE 的CCA 安全性(由于游戏G6需要解密能力),可知

游戏G11:本游戏修改针对SendClient d(Ai,m),d∈{2,4}的模拟.类似于游戏G5,利用DDH 自规约技术在给定三元组(X0,Y0,Z0)的情形下,修改用户会话A和B生成X、Y、skAB、skBA的方式,即当用户A需要计算X时,选择随机的a,x∈Zp并计算X=,当用户B需要计算Y时,选择随机的b,y∈Zp并计算Y=,当双方需要生成密钥时,计算skAB=skBA=.此时,攻击者区分真实的会话密钥skAB=skBA和完全随机值的优势不超过攻击者攻破DDH 假设的优势,即

(1)攻击者冒充用户A(B类似)发送了消息〈A,B,cAS〉,且密文cAS确实是与口令πA相对应的密文;

(2)攻击者冒充服务器向用户A(B类似)发送了消息〈hp1A,hp2A,cSA〉,且其中的cSA确实是与口令πA相对应的验证元(sA,HA)的密文;

(3)在MAC 安全的情况下,攻击者成功地伪造了用户A(B类似)所使用的MAC 认证值;

(4)攻击者成功地猜对了Test询问中所使用的比特b.

记计算时间至多为t的攻击者针对协议所采用的MAC 机制的优势函数为,由于MAC 密钥在游戏G3和G9中已被替换成随机值,则攻击者通过情形(3)成功的概率至多是2(qsend+qexe)⋅(t+O(qsend+qexe)).若用PwdGuess表示事件“上述情形(1)或情形(2)发生”,注意到在上述游戏G11中攻击者已经不能从会话消息获取到口令的任何信息,从而攻击者只能通过暴力穷举或字典攻击[22]猜测用户所使用的正确口令.

当协议中所有用户口令构成的集合服从Zipf 定律时,可知攻击者成功的概率至多为Pr[PwdGuess]≤,其中,C′和s′是相应的Zipf 参数.另外,如果事件PwdGuess不出现,注意到协议会话密钥都已经被替换成随机值,可知攻击者通过情形(4)成功的概率至多为1/2.因此可得A dv11(A)≤.综合上式以及式(3)～式(11)可得,

定理2.若DDH 假设成立,则I-V3PAKE 协议相对于诚实而好奇的服务器可保证会话密钥的私密性.具体地说,假设Akp是安全模型中针对会话密钥私密性的攻击者,其运行时间至多为t,发出的Execute和Send询问次数至多为qexe,qsend,则有

证明:给定会话密钥私密性攻击者Akp,我们按照如下方式构造针对DDH 问题的攻击者Addh.DDH 攻击者Addh收到输入的三元组(X0,Y0,Z0),首先为所有用户选择口令,为TestPair询问选择随机比特b∈{0,1},诚实地模拟协议运行并基本按照规范回答攻击者Akp发出的Execute和SendClient询问,不同之处在于,在询问响应中将最终X、Y、skAB、skBA相关的部分予以修改:按照类似于定理1 证明中游戏G5和G11利用随机自规约方式将三元组(X0,Y0,Z0)嵌入到协议运行中.

最后,Addh观察Akp的输出比特b′,如果b′=b,则Addh输出1,若b′≠b,则Addh输出0.那么可以估计Addh成功的概率为

其中,Real(·)和Rand(·)分别表示输入的三元组是真实的DDH 三元组和随机的三元组.当(X0,Y0,Z0)是随机三元组时,随机自规约保证了最终会话密钥是独立随机的;当(X0,Y0,Z0)是真实的DDH 三元组时,给攻击者Akp提供的模拟环境与真实攻击相同.最后,注意到Addh对每个Execute和SendClient询问的模拟都只需要常数时间,即可得定理结论. □

6 结束语

本文对基于验证元三方PAKE 协议进行了研究.首先,指出目前唯一的在标准模型下设计的基于验证元的三方PAKE 协议存在安全缺陷,易于遭受离线字典攻击.其次,基于ElGamal 公钥加密体制、口令哈希机制以及支持验证元的平滑投射哈希函数等密码学组件,构造了一个新的基于验证元的三方PAKE 协议,并在标准模型下证明了该协议满足语义安全、会话密钥私密性等安全属性,与已有协议的比较表明新协议不仅提供了更高的安全性,而且具有可接受的计算和通信效率.