基于口令的认证密钥协商协议的安全分析与改进

舒剑，许春香

(1. 电子科技大学 计算机科学与工程学院，四川 成都 611731；2. 江西财经大学 电子商务系，江西 南昌 330013)

1 引言

认证密钥协商协议是让用户在开放网络通过交互，建立一个共享的会话密钥，从而实现开放网络中的安全通信。较早的认证密钥协商协议是通信双方借助持有的高熵秘密（如数字签名的私钥)生成会话密钥，然后使用会话密钥进行加密或认证。但是这些高熵秘密不便于保存和记忆，有时还需要可信第三方的参与。让用户共享一个低熵的口令而生成高熵的会话密钥在实际环境中有广泛的应用，但这方面的研究相对较少。由于口令具有长度短的特性，攻击者可能在离线状态下进行穷举字典攻击。

Bellovin和 Merritt[1]首先提出能抵抗字典攻击的基于口令的两方密钥协商协议，随后许多相关工作[2～9]对如何利用口令生成会话密钥进行了研究。文献[1～9]都是在随机预言模型下证明协议的安全性。随机预言模型自从1993年被Bellare和Rogaway[10]提出以来，在密码学的可证安全领域得到广泛的应用。然而，随机预言模型下的安全并不代表真实世界的安全，因为它依赖现实世界无法实现的随机预言假设。另一方面，不需要随机预言假设的证明（即在标准模型下的证明）就能够清楚地说明，除非其所基于的底层数学难题被破解，否则一个可证安全的方案不可能被攻破。因此，在标准模型下设计基于口令的认证协议更具有实际意义。

基于 Cramer-Shoup[11]提出的 CCA2(chosen ciphertext attack-2)安全的公钥加密体制，Katz,Ostovsky和 Yung[12]首先提出了一种标准模型下可证安全的基于口令认证密钥协商协议。Gennaro和Lindell[13]给出了KOY协议的抽象框架。他们的协议计算复杂度很高，并且协议只能实现单向认证。为降低计算复杂度和实现双向认证，Jiang和Gong[14]提出了一种改进的标准模型下基于口令认证密钥协商协议。

通过引入伪随机函数集和通信双方均使用ElGamal加密方案，殷胤等[15]提出了高效的基于口令认证密钥协商协议，该协议极大降低了计算复杂度。但是，协议对发起方(客户)要进行 2次认证，并且要求服务器方拥有私钥，因而该协议不适合只共享相同口令的双方进行密钥协商。另外，由于通信双方均使用ElGamal加密方案并且协议设计不合理，笔者发现该协议不能抵抗反射攻击或变型的反射攻击。

本文提出一种新的基于口令认证密钥协商协议。协议的发起方和响应方均使用ElGamal加密方案。与文献[15]协议相比，计算机复杂度相当并且不需要响应方拥有私钥。新协议实现了双向认证，并在标准模型下基于 DDH假设给出了安全性证明。

2 背景知识

2.1 DDH(decisional Diffie-Hellman)假设

2.2 伪随机函数集

2.3 形式化安全模型

本节简要回顾 Bellare等在文献[5]中定义的基于口令密钥协商协议的形式化安全模型。模型包括一个协议参与者集合U，每个参与者被模拟为一组预言机。参与者拥有一个共同的口令，预言机 ∏n

I,J指参与者I与J的第n个实例。模型中还包括一个主动攻击者(用A表示)，它被定义为一个概率多项式时间图灵机。模型将攻击者的能力抽象为对若干个预言机的查询，并且这些查询可以是无序和自适应的。

定义1会话标识符(SID)：预言机 ∏n发送和I,J接收的所有消息的串联。

定义2搭档预言机(PID)：若2个预言机在同意(accept)状态时有相同的会话标识符 SID, 则称 2个预言机互为搭档。

Execute查询：这种查询模拟被动攻击。攻击者A通过查询 execute( ∏n,∏s)获得搭档预言机I,J J,I∏n和 ∏s执行过程中的所有交互信息。

I,J J,I

Send查询：这种查询模拟主动攻击。攻击者A向预言机 ∏n发送伪造消息，若预言机收到的消息I,J为空(null)，表示攻击者让预言机发起一个新的会话。查询返回消息为接收到假冒消息后，预言机按照协议规则的回复。

Reveal 查询：这种查询模拟预言机 ∏n的会话I,J密钥泄漏，返回值为 s ki。如果预言机还不是“已接受”(accepted)，则返回一个符号⊥表示终止。执行了reveal查询的实例状态是打开的(opened)。

Corrupt 查询：这种查询模拟前向安全性。要求被询问的预言机返回它拥有的长期私钥(口令)。回答过corrupt查询的预言机的状态称为“已腐化”(corrupted)。

Test 查询：这种查询描述协议的语义安全性。它只能运行一次，并且只能对一个“新鲜”的预言机进行。当攻击者 A进行 Test 查询时，协议随机选择一个比特 b ∈ { 0,1},如果 b = 0 ，则返回 s ki，否则，返回一个随机数r，攻击者根据返回值以及利用其他查询获得的信息，猜测b的值为 b '。

如果在Test查询中，攻击者成功猜对b的值，则称攻击者成功。定义攻击者 A的成功概率为pr[]S。

定义 A dvgpa,Gke为所有攻击者 A可能取到的Advpake(A)的最大值，则称协议是安全的，如果g,G。其中：sq表示Send 查询的次数；N表示所有口令的总数；ε是一个可忽略函数；O(qs/N )保证每次Send查询，攻击者A最多排除常数个可能的口令。

定义 3新鲜预言机：预言机 ∏n在同意状态I,J下是未打开的，其搭档预言机也未打开，并且其搭档预言机没有被腐化，则预言机 ∏nI,J是新鲜的。

3 殷胤等人的协议及其攻击

本节对殷胤等[15]提出的高效的基于口令认证密钥协商协议进行分析。协议描述如图1所示。其中 p ,q是大素数且满足Gq是乘法群Z*的阶为q的子群；g,h是 G 的2个生成元；u是Pq服务器拥有的私钥；F是一个伪随机函数集；f是从口令空间到 ZP的映射；pw是客户和服务器共享的口令。

图1 标准模型下可证安全的EKE协议

协议双方均使用 ElGamal加密机制。由于ElGamal加密机制具有抵抗 CPA(chosen plaintext attack)特性，被动攻击无法获得任何有效信息。

在上面的攻击中，攻击者发动有效攻击时消息C必须为 h = gu。即使对协议作一定的修改，使客户对消息C进行验证，如果C = h ，则终止协议。攻击者仍可以利用消息的自规约特性，伪装成服务器实施有效攻击。攻击过程如下。

4 新的基于口令认证密钥协商协议

本节提出一种新的标准模型下基于口令认证密钥协商协议，协议描述如图2所示。 p ,q是大素数且满足 q | ( p - 1 )； Gq是乘法群 ZP*的阶为q的子群； g,h是 Gq的2个生成元；F是一个伪随机函数集；pw是客户和服务器共享的口令。

图2 标准模型下可证安全的基于口令认证密钥协商协议

协议发起方和响应方均采用 ElGamal加密机制。新协议与文献[15]协议相比，计算复杂度相当并且不需要对协议的发起方进行2次认证。由于协议响应方不需要保存私钥，该协议也适用于共享相同口令的2个客户进行密钥协商。

实验Γ5：下面开始考虑Send查询。当攻击者进行Send( s erver|D |E |T)查询时，仿真器按如下方式验证：仿真器验证(因为仿真器知道u的值)。如果验证通过，则判定攻击者成功，否则终止协议。攻击者除非猜对了口令的值，才能通过验证。

实验Γ6：Γ6与Γ5的区别是当攻击者进行Send(*, null)查询时，用随机数r替代消息B。

为了使攻击者的视角保持一致性，需要处理其他的预言机查询。Send( c lient|A|B)和 Send(c lient|a kc)查询保持不变。由于此时消息 A |B不存在让协议正常执行的x，Send( s erver|D |E|T)查询修改如下。

1) 如果查询消息是预言机产生的，仿真器不进行验证，用 Send( c lient|A|B)查询中的σ计算然后输出akc并计算。当B为随机数时，如果消息 A |B是 gpw的ElGamal加密(极小概率)，2个匹配预言机计算的σ值是相等的。仿真器的仿真实验是完美的。

2) 如果查询消息是攻击者产生的，仿真器按实验Γ5给出响应。如果攻击者有一定的优势获得会话密钥，则可以利用混合证明技巧，直接归约为解决DDH问题。

实验Γ7：当攻击者进行Send(client|A|B)查询时，如果 B = Augpw(仿真器知道u)，则判定攻击者成功，并终止协议。

5 协议的安全性证明

证明方法是把协议执行看作仿真器与攻击者之间的游戏。仿真器选择 2个大素数 p ,q且满足，然后选择和一个伪随机函数F并计算 h = gu。随后公布公钥参数 p ,q,g,h,F并像实际协议一样给通信实体分配口令。

定理1Γ是图2描述的协议；N表示所有可能的口令；F是的伪随机函数集； p ,q是大素数且满足是乘法群 ZP*的阶为q的子群；g ,h是 Gq的生成元；qe,qs,qr分别表示攻击者进行 Execute查询、Send查询、Reveal查询的次数。则，

实验0Γ：这是实际协议攻击实验。事件0S表示攻击者成功猜出Test查询中预言机所使用的比特b，则可以得到：

实验1Γ：在实验1Γ中，当攻击者进行Execute查询时，用随机数r替代消息B。基于DDH假设，运用混合证明(hybrid arguments)技巧，可得：

实验Γ2：Γ2与Γ1的区别在于攻击者进行Execute查询时, a kc,r替换为不同的随机数。

注意，在Γ1中，消息A|B不再是gpw的ElGamal加密。不失一般性，消息可为服务器计算由于λ的随机性和独立性，σ2在 Gq中也是随机均匀的。利用伪随机函数集定义，运用混合证明技巧，可得：

实验3Γ：在实验3Γ中，攻击者进行Execute查询时，用随机数r替代sk。

与实验2Γ中的分析类似，得出σ是随机均匀的。如果攻击者不进行Reveal查询，则在3Γ和2Γ中获得的信息是相同的。在2Γ中，攻击者得到sk就等价于对伪随机函数集nF进行了一次查询；而在3Γ中，攻击者得到r就等价于对均匀分布函数集nH进行了一次查询。根据伪随机函数集的定义，没有算法可以有效区分伪随机函数集和均匀分布函数集，所以，

实验4Γ：4Γ与3Γ的区别是，当攻击者进行Execute查询时，C替换为随机数，即T替换为随机数。运用混合证明技巧，可得：

由于攻击者之前通过Execute查询和Send查询得到的消息 A |B不是 gpw的 ElGamal加密(B是随机数)。攻击者成功是因为猜对了口令的值，可得：

实验Γ8：Γ8与Γ7的区别是，当攻击者进行Send(c lient|A|B)查询时，σ替换为随机数r。

在Γ8中，说明攻击者没有在Send(client|A|B)查询时成功(否则攻击者已经在Γ7中成功，协议已终止)。这时，消息 A |B不是 gpw的ElGamal加密。与实验Γ2的分析类似，σ是随机均匀分布的。则，

实验Γ9：Γ9与Γ8的区别在于攻击者进行Send查询时， a kc,r替换为不同的随机数。

由于消息 A |B不是 gpw的ElGamal加密，σ是随机均匀分布的。利用伪随机函数的定义，运用混合证明技巧，可得：

实验10Γ∶ 攻击者进行Send查询时, sk替换为随机数。

与实验9Γ中的分析类似，得出σ是随机均匀的。如果攻击者不进行Reveal查询，则在10Γ和9Γ中获得的信息是相同的。所以，

实验Γ11∶ Γ11与Γ10的区别在于攻击者进行Send( c lient|A|B)查询时，消息T替换为随机数。基于DDH假设，运用混合证明技巧，可得：

在11Γ中，由于攻击者无法获得关于pw的任何信息(与pw相关的信息 ,BT替换为随机数后，攻击者感觉不到任何变化)，从而无法获得σ的任何信息，说明在Test查询中，攻击者无法区分sk和随机数。

综合以上实验中的结果, 可以得出定理1。

定理1表明，攻击者成功的概率依赖于它每次进行Send查询时对口令的猜测，而与Execute查询和 Reveal查询无关。如果攻击者某个时刻通过Corrupt查询获得了长期私钥(双方共享的口令)，它通过以前被动窃听的会话信息得到许多三元对( gx, hx,D)，攻击者无法计算 Dx，其困难等价于CDH问题。攻击者无法获得σ的任何信息，说明协议具备完美前向安全。

6 协议的性能分析

本节给出新协议与其他标准模型下的协议比较（见表1），新协议能抵御主动攻击，且计算复杂度较小(新协议直接计算 gpw, 而不是 gf(pw), 由于pw较短，可以忽略以pw为指数的运算)。在通信效率方面，3种协议都要进行3轮通信而实现显式双向认证，并且新协议与其他2种协议占用的带宽相同。

表1 新协议与其他协议的比较

7 结束语

本文基于ElGamal加密机制和伪随机函数集，在标准模型下设计了可证安全的基于口令密钥协商协议。与其他标准模型下基于口令的认证协议相比，新协议的通信效率与其他协议相当，并具有较小的计算复杂度。新协议实现了显式双向认证，并基于DDH假设，给出了协议的“紧规约”证明，从而真正证明了协议的安全性。

[1] BELLOVIN S, MERRITT M．Encrypted key exchange∶ password-based protocol secure against dictionary attacks[A]. Proceedings of the 1992 Conference IEEE Computer Society Symp on Research in Security and Privacy[C]. Oakland∶ IEEE Computer Society, 1992. 72-84.

[2] BELLOVIN S, MERRITT M．Augmented encrypted key exchange∶ a password-based protocol secure against dictionary attacks and password file compromise[A]. Proceedings of the 1st ACM Conference on Computer and Communication Security[C]. New York, 1993.244-250.

[3] JABLON D P. Extended password key exchange protocols immune to dictionary attacks[A]. Proceedings of the WETICE’97 Workshop on Enterprise Security[C]. Cambridge∶ IEEE Computer Society, 1997. 248-255.

[4] WU T D. The secure remote password protocol[A]. Proceedings of the Network and Distributed System Security Symp NDSS 1998[C]. San Diego, Internet Society, 1998.232-245.

[5] BELLARE M, POINTCHEVAL D, ROGAWAY P．Authenticated key exchange secure against dictionary attacks[A]. Proceedings of the Advance Eurocrypt 2000[C]. Berlin∶ Springer-Verlag, 2000.139-155.

[6] ABDALLA M, CHEVASSUT O, POINTCHEVAL D. One-time verifier-based encrypted key exchange[A]. Proceedings of Public Key Cryptography-PKC 2005[C]. Berlin∶ Springer-Verlag, 2005.47-64.

[7] ABDALLA M, POINTCHEVAL D. Simple password-based encrypted key exchange protocols[A]. Proceedings of CT-RSA 2005[C]. Berlin∶Springer-Verlag, 2005.191-208.

[8] FENG D G, XU J. A new client-to-client password-authenticated key agreement protocol[A]. Proceedings of IWCC 2009[C]. Berlin∶Springer-Verlag, 2009.63-76.

[9] HUANG H F. A simple three-party password-based key exchange protocol[J]. Int J Commun Syst, 2009, 22(4)∶ 857-862.

[10] BELLARE M, ROGAWAY P. Random oracles are practical∶ a paradigm for designing efficient protocols[A]. Proceedings of the First ACM Conference on Computer and Communication Security[C]. New York, 1993.62-73.

[11] CRAMER R, SHOUP V. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[A]. Proceedings of the Advance in Cryptology-CRYPTO 1998[C]. Berlin∶ Springer-Verlag, 1998. 13-25.

[12] KATZ J, OSTROVSKY R, YUNG M. Efficient password- authentication key exchange using human-memorable passwords[A]. Proceedings of the Advances in Cryptology-EUROCRYPT 2001[C]. Berlin∶Springer-Verlag, 2001.475-494.

[13] GENNARO R, LINDELL Y. A framework for password-based authenticated key exchange[A]. Proceedings of the Advances in Cryptology-EUROCRYPT 2003[C]. Berlin∶ Springer-Verlag, 2003.524-543.

[14] JIANG S Q, GONG G. Password based key exchange with mutual authentication[A]. Proceedings of Cryptography-SAC 2004[C]. Berlin∶Springer-Verlag, 2004.267-279.

[15] 殷胤, 李宝. 标准模型下可证安全的加密密钥协商协议[J]. 软件学报, 2007, 18(2)∶ 422-429.YIN Y, LI B. Provable secure encrypted key exchange protocol under standard model[J]. Journal of Software, 2007, 18(2)∶ 422-429.