一种高效的匿名口令认证密钥交换协议

阮 鸥，王子豪，张明武

(湖北工业大学 计算机学院，武汉 430068)

互联互通时代，口令认证密钥交换 (PAKE) 协议是使用最广泛的安全技术手段，通信各方通过一个易于记忆的口令可以建立一个可靠安全的会话密钥，后期通过会话密钥对通信数据加密进而保证数据机密性. 由于口令非常方便用户使用而且也不需要特殊设备，所以PAKE协议应用广泛，成为网络空间安全研究的热点问题. 在Bellovin等人[1]首次提出PAKE协议后，有大量研究跟进，解决PAKE协议的效率问题及形式化证明[2-4]，提出多方情况[5-8]、组情况[9,10]的解决方案，设计抗泄露方案[11-13].

传统PAKE协议中，用户需要发送身份及口令信息到服务器，服务器据此确定用户身份进而协商会话密钥. 近年来，由于云计算等新应用的兴起，人们十分关心其在网络中的隐私性，期望各类应用及协议提供更高的安全服务——保护用户隐私[14-18]. 同样地，PAKE协议也需要提供隐私保护服务，例如云服务中，用户希望服务器不能确定其真实身份，而服务器希望能通过某种途径确定用户合法性. 为满足这种需求，Viet等学者[19]提出了匿名口令认证密钥交换协议 (APAKE) ，用户能通过口令与服务器建立共享会话密钥，却不会暴露其真实身份信息. 之后，Shin等学者[20]指出Viet等的方案不能抵抗离线口令攻击，进而提出了一种陷门APAKE协议；接着，Yang等学者[21]指出Shin等的陷门APAKE协议既不能抵抗离线口令攻击也不能抵抗冒充身份攻击，然后给出了一种解决这两个问题的新方案. 最近，Hu等学者[22]设计了标准安全模型下的APAKE协议. 然而，上述APAKE协议效率都比较差，特别是服务器端的计算开销很大. 本文基于椭圆曲线CDH假设提出了一种高效的APAKE协议，并给出了形式化的安全证明. 该协议既能抵抗身份冒充攻击及离线口令猜测攻击，也提供双向认证. 同时，协议效率得到很大提高，客户端及服务器端计算开销得到大幅降低.

1 安全模型

1.1 APAKE系统模型

APAKE协议典型系统模型如图1所示，用户U与服务器S通过交互协商一个共享的安全会话密钥k，而敌手A不能获知k的任何信息，同时服务器S无法获知用户U的具体身份信息.

系统模型符号：

协议参与方. 协议参与方包括一组用户G={U1,…,Un}及可信服务器集合S. 我们假设G是固定的；可信服务器仅有一个，它是诚实而好奇的，即S严格按照协议规程执行，但会收集分析信息以期获取额外信息.

敌手A.A控制网络信息通道，并能访问任意谕言机.

会话. 用户与服务器的一次APAKE协议执行实例.

图1 APAKE系统模型Fig.1 The system model of APAKE

1.2 敌手能力模型

我们通过定义以下访问来量化敌手能力：

·Send(Pi，m). 通过此请求访问，敌手A完成一次主动攻击，它发送消息m给会话i中参与方Pi(可能是用户也可能是服务器) ，Pi根据协议规程计算下一条信息并返回给A. 敌手A可以通过Send(S，“start”)初始化启动一次会话流程.

·Reveal(Ui). 收到此访问请求后，Ui发送会话i的会话密钥给敌手A.

·Execute(Ui，S). 这个访问用于建模离线口令猜测攻击. 通过此访问，敌手将得到Ui与S一次诚实会话的执行脚本.

·HO(m) . 这是一个哈希谕言机访问，如果m未被访问过，HO产生一个随机数r返回给A，并将(m，r)记入哈希表；否则在哈希表寻找(m，r′)然后返回r′给A.

·Test(Ui) . 此访问测试敌手A是否获取会话密钥. 收到此访问后，Ui随机选取一个比特b，如果b= 0返回实际会话密钥给A，否则返回随机密钥给A. 注意：整个执行过程中，此访问最多只能执行一次.

1.3 安全定义

定义1.1 [新鲜性] 当会话密钥ski已产生但Reveal(Ui)未被访问时，我们称Ui是新鲜的.

定义1.2 [APAKE安全] 当满足如下3个属性时，我们称APAKE协议是安全的：

· 正确性： 会话结束后，用户与服务器产出相同的会话密钥sk.

·PAKE安全性： 考察下面的游戏执行过程，敌手A任意访问谕言机Send(Pi，m)，Execute(Ui，S)，HO(m)，Reveal(Ui)，最后Test访问新鲜的Ui，Ui随机选取一个比特b，如果b= 0返回实际会话密钥给A，否则返回随机密钥给A. 敌手A输出猜测的比特b′并终止执行. 敌手A成功攻击上述游戏的优势定义为：

若对于任意多项式时间内的敌手A，下式均成立，则称协议具有PAKE安全性，

其中ε(·)是可忽略函数，N是口令字典容量大小，qs是Send访问的次数.

注：对于PAKE协议，在线口令猜测攻击是无法避免的，其成功的概率为qs/N. 但我们可以采用一些有效机制来限制在线口令猜测攻击，比如口令输入尝试失败一定次数后自动终止协议执行.

·用户匿名性：用户匿名性指外部敌手或者可信服务器都不能区分某次会话的具体用户，在这里，可信服务器是一个诚实而好奇的服务器，它会严格按协议规程产生协议信息，但会试图分析协议执行脚本去确定用户实际身份.

Pi表示用户Ui与可信服务器会话的执行脚本. 对于任何两个合法用户Ui和Uj，如果Pi和Pj计算不可区分，则称协议P满足用户匿名性.

2 一种高效的APAKE协议

新协议基于椭圆曲线CDH假设设计，其中用到的符号总结于表1.

表1 符号表Tab.1 The symbol Table

Step4 用户Ui计算kU=a·ηS，验证σS=H(S‖TU‖kU)是否成立，成立则计算会话密钥skUS=H(U1,…，Un‖S‖kU) . 同时，服务器S计算会话密钥skSU=H(U1,…,Un‖S‖kS).

2.1 APAKE协议

新协议如图2所示包含4步.

图2 APAKE协议Fig.2 The APAKE protocol

2.2 安全性证明

我们将基于随机谕言机模型来证明新协议安全性，包括正确性、PAKE安全性及匿名性三个部分.

(1) 正确性.

协议结束后，用户Ui和服务器S协商后的会议密钥分别为：skUS=H(U1,…,Un‖S‖kU)及skSU=H(U1,…,Un‖S‖kS). 由于：

kS=b·η′=b(ηU-TS)=b(ηU-r·US)=

b(ηU-r·ri·hi·Q)=b(ηU-ri·Si)=

b(ηU-TU)=b·a·Q=a·b·Q=a·ηS=kU,

所以，skUS=skSU.

(2)PAKE安全性.

定理1 新协议中，假设A为安全游戏中的多项式时间敌手，它执行了qs次Send访问，qe次Execute访问及qh次HO访问，则有：

其中εCDH为破解CDH假设的概率.

构造CDH敌手ACDH，它破解CDH假设的概率为εCDH.ACDH以(r1·Q，r2·Q))为输入，选择用户口令集pwj(1≤j≤n).ACDH把A作为其子程序访问，对A的谕言机访问做如下回答：

> 若A的访问为Send(S，(US,ηU,σU))，ACDH计算TS=r·US,η′=ηU-TS,ηS=r2·Q，验证σU=H(TS‖US)是否成立，成立则选择随机数σS，发送{ηS,σS} 给A.

> 若A的访问为Send(U，ηS,σS)，ACDH输出随机会话密钥skSU.

> 若A的访问为Reveal或Test，此时它企图获取由(r1·Q，r2·Q)构造的会话密钥，ACDH终止执行并输出“⊥”；当A停止执行后，ACDH访问哈希表，寻找是否存在形如HO(U1,…，Un‖S‖*)结构的HO访问，如果存在，ACDH随机选择一个并输出“*”；否则ACDH终止执行并输出“⊥”.

由于单向哈希函数H被看作随机谕言机，如果A知道会话密钥sk，则A必然访问了哈希表记录的HO(U1,…，Un‖S‖r1·r2·Q). 这种情况，ACDH破解了CDH 假设.

设λ为ACDH从哈希表正确选择HO(U1,…，Un‖S‖r1·r2·Q)的概率，则有：λ≥1/qh.

设φ为ACDH正确猜测到A成功破解APAKE协议安全性的时刻，则有：φ≥1/qs.

根据上述分析，ACDH成功破解CDH假设的概率εCDH为：

所以有：

破解口令情况下攻破新APAKE协议安全性的事件可分为两种情况：在线口令猜测攻击及离线口令猜测攻击.

Case 1：在线口令猜测攻击

Case 2：离线口令猜测攻击

根据分析1)及2)，有：

(3) 匿名性.

对于任何两个合法用户Ui和Uj，其执行脚本分别为：

Pi={(Sk(1≤k≤n)),(UiS,ηUi,σUi),(ηSi,σSi)},

Pj={(Sk(1≤k≤n)),(UjS,ηUj,σUj),(ηSj,σSj)},

其中，

a)Pi:UiS=ri·H1(i‖pwi)Q,TUi=ri·Si,ηUi=aiQ+TUi,σUi=H(TUi‖UiS),ηSi=bi·Q,σSi=H(S‖riSi‖aibiQ)，ri，ai，bi为随机数；

b)Pj:UiS=rj·H1(j‖pwj)Q,TUj=rj·Sj,ηUj=ajQ+TUj,σUj=H(TUj‖UjS),ηSj=bj·Q,σSj=H(S‖rjSj‖ajbjQ)，rj，aj，bj为随机数；

因为ri,ai,bi及rj,aj,bj为随机数, 所以Pi与Pj计算不可区分. 既新协议满足用户匿名性.

3 协议分析

安全性及效率分析结果见表2，其中Exp代表模幂运算，n代表客户端用户数量. 根据表2可知，协议[19]不能抵抗身份冒充攻击及离线口令猜测攻击，且效率较低；协议[21]不提供双向认证，并且其安全性基于复杂的SCDH及DIADH假设；协议[22]计算复杂度高，效率较差. 我们新提出的协议具有如下优势：(1) 能抵抗身份冒充攻击及离线口令猜测攻击，(2) 提供双向认证，(3) 新协议效率得到很大提高，客户端及服务器端计算开销都有很大降低.

表2 APAKE协议安全性及效率比较Tab. 2 The comparison of security and efficiency of network protocol

4 结语

网络新应用如云环境中用户特别关注其隐私安全性，基于此问题，提出了一种高效的APAKE协议，并在随机谕言机模型下给出了形式化的安全证明. 通过与现有方案对比分析表明，新协议既能抵抗身份冒充攻击及离线口令猜测攻击，又提供双向认证; 协议效率得到很大提高. APAKE协议作为一种保护用户隐私的认证密钥交换协议，其在网络新应用中的研究刚刚开始，下一步工作包括除了在满足安全性及隐私性基础上进一步提高协议效率外，还可以基于标准安全模型构造高效的APAKE协议.

参 考 文 献

[1] Bellovin S M，Merritt M，Bellovin S M. Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks[C]// IEEE. IEEE Symposium on Security and Privacy. Washington: USA,IEEE, 1992:72 - 84.

[2] Ran C, Dachman-Soled D, Vaikuntanathan V, et al. Efficient Password Authenticated key Exchange via Oblivious Transfer[C]// Marc F. PKC2012. Berlin:German, Springer, 2012:449-466.

[3] Goyal V. Positive Results for Concurrently Secure Computation in the Plain Model[C]// Tim R. FOCS 2012. New Jersey:USA, IEEE, 2012:41-50.

[4] Ruan O，Kumar N，He D，et al. Efficient Provably Secure Password-based Explicit Authenticated Key Agreement[J]. Pervasive & Mobile Computing, 2015, 24(12):50-60.

[5] Yi X，Rao F Y，Tari Z，et al. ID2S Password-Authenticated Key Exchange Protocols[J]. IEEE Transactions on Computers，2016，65(12):3687-3701.

[6] Islam S H. Design and Analysis of a Three Party Password-based Authenticated Key Exchange Protocol using Extended Chaotic Maps[J]. Information Sciences，2015，312(C):104-130.

[7] Amin R，Biswas G P. Cryptanalysis and Design of a Three-Party Authenticated Key Exchange Protocol Using Smart Card [J]. Arabian Journal for Science & Engineering，2015，40(11):3135-3149.

[8] Lu C F. Multi-party Password-Authenticated Key Exchange Scheme with Privacy Preservation for Mobile Environment[J]. Ksii Transactions on Internet & Information Systems，2015，9(12): 5135-5149.

[9] Nam J，Paik J，Kim J，et al. Server-aided Password-authenticated Key Exchange: from 3-party to Group[C]// Smith M J. International Conference on Human Interface and the Management of Information 2011. Orlando:USA, Springer，2011: 339-348.

[10] Guo C，Zhang Z J，Zhu L H，et al. Scalable Protocol for Cross-domain Group Password-based Authenticated Key Exchange [J]. Frontiers of Computer Science，2014，9(1): 157 -169.

[11] Chen R，Mu Y，Yang G，et al. Strongly Leakage-Resilient Authenticated Key Exchange [J]. Des Codes Cryptography, 2017, 85(1): 145-173.

[12] Ruan O, Chen J, Zhang M W, Provably Leakage-Resilient Password-Based Authenticated Key Exchange in the Standard Model[J]. IEEE Access, 2017, 5(1): 26832-26841.

[13] Ruan O, Wang QP, Wang ZH, Provably leakage-resilient three-party password-based authenticated key exchange[J]. Journal of Ambient Intelligence and Humanized Computing, 2017, DOI: 10.1007/s12652-017-0628-8 .

[14] He D B，Zeadally S，Kumar N，et al. Anonymous authentication for wireless body area networks with provable security[J]. IEEE Systems Journal，2017，11(4): 2590-2601.

[15] Wang D，He D，Wang P，et al. Anonymous Two-factor Authentication in Distributed Systems: Certain Goals are Beyond Attainment [J]. IEEE Transactions on Dependable and Secure Computing，2015，12(4): 428-442.

[16] Xia Z，Wang X，Zhang L，et al. A privacy-Preserving and Copydeterrence Content-based Image Retrieval Scheme in Cloud Computing [J]. IEEE Transactions on Information Forensics and Security，2016，11(11): 2594-2608.

[17] Xia Z，Wang X，Sun X，et al. A Secure and Dynamic Multi-keyword Ranked Search Scheme over Encrypted Cloud Data [J]. IEEE Transactions on Parallel and Distributed Systems，2016，27(2): 340-352.

[18] Fu Z，Ren K，Shu J，et al. Enabling Personalized Search over Encrypted Outsourced Data with Efficiency Improvement [J]. IEEE Transactions on Parallel and Distributed Systems，2016，27(9): 2546-2559.

[19] Viet DQ，Yamamura A，Tanaka H. Anonymous Password-Based Authenticated Key Exchange[C]// Subhamoy M. INDOCRYPT 2005. Bangalore: Springer, 2005: 244-257.

[20] Shin S，Kobara K，Imai H. A Secure Threshold Anonymous Password-authenticated Key Exchange Protocol[C]// Atsuko M. IWSEC 2007. Nara: Springer, 2007: 444-458.

[21] Yang J，Zhang Z. A New Anonymous Password-based Authenticated Key Exchange Protocol[C]// Dipanwita R C. INDOCRYPT 2008. Kharagpur: Springer，2008: 200-212.

[22] Hu X，Zhang J，Zhang Z，et al. Anonymous Password Authenticated Key Exchange Protocol in the Standard Model [J]. Wireless Personal Communications，2017 (4): 1-24.