基于理想格的用户匿名口令认证密钥协商协议

王彩芬, ,

(西北师范大学 计算机科学与工程学院,兰州 730070)

0 概述

随着量子计算机的发展,传统的困难问题在量子计算下存在多项式求解算法,其安全性受到越来越多的挑战,格密码依靠其独特的困难问题和归约结果成为密码学研究的热点,基于标准格的密码方案具有较长的密钥和较高的密文扩张率,且格的表示方式需要较大的空间,而理想格的表示方式简单,对内具有乘法封闭性、对外具有乘法吸收性,其可以克服标准格的相关缺点。因此,理想格在密码方案中被广泛使用,如公钥加密[1-3]、数字签名[4-6]、密钥协商协议[7-9]等。

认证密钥交换(Authenticated Key Exchange,AKE)允许通信方在不安全的信道中相互认证并协商出共享密钥,两方口令认证密钥交换(Two-party Password Authenticated Key Exchange,2PAKE)[10]协议中每2个用户共享一个低熵口令,导致该协商协议不适用于用户间的通信。为解决2PAKE的局限性,密码学者提出三方口令认证密钥交换(Three-party Password Authenticated Key Exchange,3PAKE)协议[11-12],并将其应用于大规模网络下的通信。文献[10]基于误差学习问题(Learing With Error,LWE),提出基于格的2PAKE协议,该方案存在密钥较长和效率较低等问题,无法应用在大规模的通信系统中。文献[7]针对一般格上密钥长度过大的问题提出基于理想格的环上误差学习(Ring Learning With Error,RLWE)问题,并证明其分布是伪随机的。文献[8]提出基于理想格的近似平滑投射Hash函数(ASPH)。文献[13]基于格的口令认证密钥交换协议,在相关加密算法的研究中提出基于理想格的2PAKE协议,该协议消息传输量较大,且不满足用户的匿名性。文献[10]提出基于理想格的认证密钥交换方案,其协议不使用任何加密原语,该方案的安全性基于RLWE困难问题,不适用于大规模网络中的通信。文献[11]基于ASPH提出基于格的3PAKE协议,该协议不满足用户的匿名性。文献[12]提出一种新型基于RLWE问题的认证密钥交换方案,该方案基于RLWE问题提出两方密钥协商协议。文献[14]提出基于验证元的3PAKE协议,该协议通信量较多,效率较低。

针对上述协议的局限性,本文提出基于理想格的用户匿名3PAKE协议,在文献[15]安全模型的基础上构建3PAKE协议的安全模型,并在标准模型下证明该协议的安全性。

1 相关定义

定义1理想格

定义2离散高斯分布[16]

定义3RLWE问题

根据RLWE问题,有以下相关引理:

定义4Cha和Mod2函数[9]

根据Cha和Mod2函数定义,有以下引理:

定义53PAKE协议的安全模型

在文献[15]安全模型的基础上构建3PAKE协议的安全模型。协议中使用的符号及说明如表1所示。

表1 基于理想格的3PAKE协议符号说明

从以下方面描述安全模型的定义:

安全游戏:定义挑战者XH和概率多项式时间敌手A的安全参数k,挑战者代表诚实用户运行协议P。

用户和口令:假设一个固定的用户集合Y分为2个非空集合:客户X和服务器Σ,假设非空字典D的长度为L。在开始游戏前,非空字典D随机均匀分配给每个客户C∈X一个口令pwC,并给敌手A分配口令。∀S∈Σ,有pwS=(f(pwC))C,f是被P指定的有效、可计算的单向函数。XH生成P的公共参数,并发送给A,模型假设敌手知道恶意客户口令集合,游戏开始。

Corrupt(Y)询问:如果U∈Y,返回(f(pwC))C;否则,返回pwU给A。

结束游戏:最后,A输出b′作为b的猜测。如果b′=b,则攻击者攻击成功。

2 基于理想格的密钥协商协议

针对文献[9-13]中存在的一些安全性问题,本文提出了基于理想格的用户匿名3PAKE协议。

2.1 协议内容

2.1.1 初始化阶段

如图1所示,当用户B和C进行安全通信时,用户分别输入临时身份TIDB、TIDC,两者在服务器的协助下进行相互认证,并协商一个共享的会话密钥。其中,协议基于RLWE困难问题,Rq=Zq/(xn+1),σ=Mod2(kS,ω)=Mod2(kB,ω)=Mod2(kC,ω)。

图1 基于理想格的3PAKE协议示意图

当用户加入系统时,需要向服务器S注册。以用户B为例,该注册过程具体如下:

1)B→S:(B,HpwB)

用户B随机选取身份B和口令pwB,并任意选取随机数a,B计算HpwB=h(pwB‖a),并将注册请求(B,HpwB)发送给服务器S。

2)S→B:(TIDB,H(·))

当S收到用户B的注册请求消息(B,HpwB)后,计算TIDB=B⊕HpwB,并将TIDB、H(·)发送给用户B。

2.1.2 相互认证与密钥协商阶段

用户的相互认证与密钥协商具体过程如下:

1)B→S:M1=〈TIDB,m1〉

用户B输入TIDB、pwB,随机选取sB,eB←χβ计算α1=asB+2eB,γ1=H1(pwB),m1=α1+γ1,B将M1发送给S。

2)C→S:M2=〈TIDC,m2〉

用户C输入TIDC,pwC,随机选取sC,eC←χβ计算α2=asC+2eC,γ2=H1(pwC),m2=α2+γ3,C将M2发送给S。

3)S→B,C:M3=〈m3〉

4)skB=H3(B,S,C,m,μ,σ,γ)

5)skC=H3(B,S,C,m,μ,σ,γ)

2.2 方案的正确性

q是一个大素数,若q>16β2n3/2,诚实用户运行方案,用户获得的会话密钥不匹配的概率可忽略。由引理3得,如果kC和kS非常接近,即|kC-kS|

3 安全性证明

认证协议能否得到广泛应用,不仅要其设计合理,还要具备正确性和安全性,本文给出基于理想格的用户匿名3PAKE协议的安全性证明。

定理1设n是安全参数,Dn是口令空间,若RLWE问题是困难的,则方案在标准模型下是安全的。因此,存在可忽略函数negl(n),对运行时间为t的敌手A,执行Execute、Send、Test询问的次数最多为qe、qs、qt,有AdvDn,Gx(A)≤qs/|Dn|+negl(n)成立。

游戏G0是H和真实协议的交互,H向模拟器S询问,并收到回答。

|Adv(H,G1)-Adv(H,G0)|≤negl(n)

(1)

|Adv(H,G2)-Adv(H,G1)|≤negl(n)

(2)

|Adv(H,G3)-Adv(H,G2)|≤negl(n)

(3)

|Adv(H,G4)-Adv(H,G3)|≤negl(n)

(4)

|Adv(H,G5)-Adv(H,G4)|≤negl(n)

(5)

游戏G6和G5基本相同,下述情况除外:如果客户E收到Send(E,i,m3‖skS)询问,检查〈m3‖skS〉是否由匹配生成,如果不是,对m3进行解密,求解γ1,如果pwE1=pwE,则H攻击成功,但游戏G6不减少H成功的概率。

m3=H2(μ1,μ2,ω,γ1,γ2),因为哈希函数的单向性,所以攻击者很难求解出真实的γ1=H1(pwE),即使求出正确的γ1,也很难得到真实的口令pwE。因此,式(6)成立。

|Adv(H,G6)|≤|Adv(H,G5)|

(6)

游戏G7和G6基本相同,下述情况除外:如果客户E收到Send(E,i,m3‖skS)询问,且〈m3‖skS〉由匹配生成,此时,客户和S使用共同的γ1,因为γ1对H不可见,所以H成功攻击协议的概率不变。因此,式(7)成立。

|Adv(H,G7)|=|Adv(H,G6)|

(7)

|Adv(H,G8)-Adv(H,G7)|≤negl(n)

(8)

|Adv(H,G9)|≤|Adv(H,G8)|

(9)

|Adv(H,G10)-Adv(H,G9)|≤negl(n)

(10)

|Adv(H,G11)-Adv(H,G10)|≤negl(n)

(11)

若攻击者猜测口令失败,则只可通过猜测随机比特b攻击协议,如果用随机值代替会话密钥,则H成功的概率为1/2。如游戏G6和G9,H每次通过猜测随机比特b获得正确口令的概率最多是1/|Dn|,因此,H最后成功攻破协议的优势最多为qs/|Dn|。综上式(1)～式(11),有AdvDn,Gx(H)≤qs/|Dn|+negl(n)成立,敌手攻破协议的优势是可忽略的量,即定理1结论成立。

4 协议性能分析比较

从安全性和效率2个方面,对本文方案与文献[9-11,13-14]方案进行比较,结果如表2所示。从表2可以看出,在安全性方面,与传统的3PAKE协议相比,本文方案能够抵抗量子攻击,满足用户匿名性,用户和服务器的相互认证可抗不可测在线字典攻击,同时本文方案还具有较高的效率。文献[9]基于RLWE困难问题的2PAKE协议需要2轮通信,因此,其3PAKE协议至少需要4轮通信,且不满足用户匿名性;文献[10]基于LWE困难问题的2PAKE协议需要3轮通信,因此,其3PAKE协议至少需要6轮通信,且不满足用户和服务器的相互认证,不能抵抗字典攻击,且不能满足用户匿名性;文献[11]基于ASPH的3PAKE协议需要3轮通信,通信量较多且不满足用户的匿名性;文献[13]基于ASPH的2PAKE协议需要3轮通信,因此,其3PAKE协议至少需要6轮通信,通信量大且不满足用户匿名性,不能在大规模通信系统中使用;文献[14]基于ASPH的3PAKE协议,需要4轮即8条消息传输量,效率较低且不满足用户匿名性。由于基于理想格的密钥协商协议较少,因此与其他方案相比,本文协议减少了公钥长度,降低了计算复杂度和消息传输量,提高了运行速度。

表2 不同协议性能比较

5 结束语

基于标准格的密码方案存在运行效率较低等缺点,而理想格的表示方式简单,具有较少的密钥量、较短的密钥长度、较低的运行开销以及较高的运行效率等特点。因此,本文提出基于理想格的用户匿名3PAKE协议,实现用户和服务器的双向认证,并在标准模型下证明该协议的安全性。下一步将研究高效的基于理想格的多方密钥协议。

[1] 杨晓元,吴立强,张敏情,等.基于理想格的适应性选择密文安全公钥加密方案[EB/OL].[2017-04-20].http://www.docin.com/p-1273161598.html.

[2] 古春生.近似理想格上的全同态加密方案[J].软件学报,2015,26(10):2696-2719.

[3] 魏理豪,艾解清,刘生寒.理想格上高效的身份基加密方案[J].计算机工程,2016,42(7):134-138.

[4] 冯超逸,赵一鸣.基于理想格的可证明安全数字签名方案[J].计算机工程,2017,43(5):103-107.

[5] 杨丹婷,许春根,徐 磊,等.理想格上基于身份的签名方案[J].密码学报,2015,2(4):306-316.

[6] 孙意如,梁向前,商玉芳.理想格上基于身份的环签名方案[J].计算机应用,2016,36(7):1861-1865.

[7] LYUBASHEVSKY V,PEIKERT C,REGEV O.On ideal lattices and learning with errors over rings[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,2010:1-23.

[8] 叶 茂,胡学先,刘文芬.基于理想格的近似平滑投射Hash函数[J].信息工程大学学报,2013,14(1):13-21.

[9] ZHANG J,ZHANG Z,DING J,et al.Authenticated key exchange from ideal lattices[C]//Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,2015:719-751.

[10] KATZ J,VAIKUNTANATHAN V.Smooth projective hashing and password-based authenticated key exchange from lattices[C]//Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security:Advances in Cryptology.Berlin,Germany:Springer,2009:636-652.

[11] 叶 茂,胡学先,刘文芬.基于格的三方口令认证密钥交换协议[J].电子与信息学报,2013,35(6):1376-1381.

[12] 杨孝鹏,马文平,张成丽.一种新型基于环上带误差学习问题的认证密钥交换方案[J].电子与信息学报,2015,37(8):1984-1988.

[13] 叶 茂.基于格的口令认证密钥交换协议和相关加密算法研究[D].郑州:解放军信息工程大学,2013.

[14] 杨晓燕,侯孟波,魏晓超.基于验证元的三方口令认证密钥交换协议[J].计算机研究与发展,2016,53(10):2230-2238.

[15] MACKENZIE P.The PAK suite:protocols for password-authenticated key exchange[EB/OL].[2017-05-05].https://www.researchgate.net/publication/2544702_The_PAK_suite_Protocols_for_Password-Authenticated_Key_Exchange.

[16] 詹海峰.基于格的高斯抽样和密钥交换[D].西安:西安电子科技大学,2014.