理想格上基于验证元的三方口令认证密钥交换协议*

舒 琴, 王圣宝, 胡 斌, 韩立东

杭州师范大学 信息科学与工程学院, 杭州311121

1 引言

三方口令认证密钥交换(three-party password-based key exchange, 3PAKE) 协议使得两个用户能够在可信服务器的帮助下协商得到一个会话密钥. 根据客户端和服务器所持有的口令信息是否相同[1], 可将3PAKE 协议分为两大类: 对称协议和基于验证元的协议. 在对称3PAKE 协议中, 用户口令被以明文或哈希值的形式存储在服务器上, 一旦服务器信息遭到泄露, 敌手获得用户的口令后就可伪装成合法用户.这种攻击被称为服务器泄露攻击. 而在基于验证元的3PAKE 协议中, 用户根据口令生成一对公私钥, 并将公钥作为验证元发送给服务器, 服务器存储该验证元. 即使验证元泄露, 敌手也无法推导出口令, 从而无法伪装成合法用户. 2007 年, Kwon 等[2]提出首个基于验证元的3PAKE 协议, 它的安全性基于判定性Diffie-Hellman 问题. 之后, 又有多个基于验证元的3PAKE 协议被陆续提出[3–5].

在未来的量子时代, 传统基于数论难题的密码方案或协议都将变得不再安全. 因此, 能够抵抗量子攻击的所谓“后量子密码” 研究越来越受到重视. 这其中, 基于格(lattice) 上难题的3PAKE 协议的研究也逐步成为热点之一. 2013 年, 叶等[6]构造出首个格上3PAKE 协议. 此后, 多个格上3PAKE 协议被提出[7–11]. 然而,现有格上3PAKE 协议皆为对称协议,无法抵抗服务器泄露攻击. 而基于验证元的3PAKE协议可抵抗此类攻击.

为填补格上基于验证元的3PAKE 协议这一空白, 本文首先在通用可组合框架下, 基于Gentry 等[12]所提出的非对称口令认证密钥交换理想功能, 定义基于验证元的3PAKE 理想功能. 然后, 借鉴Gao等[13]基于SRP[14]协议所提出的理想格上基于验证元的两方口令认证密钥交换协议RLWE-SRP, 同时利用Abdalla 等[15]关于构造UC 安全协议的设计思想, 构造出一个理想格上基于验证元的3PAKE 协议, 我们称之为RLWE-3VSRP. 最后, 通用可组合(universal composable, UC)[16]框架下证新协议可以安全实现本文所定义的基于验证元的3PAKE 理想功能.

2 预备知识

2.1 理想格

格是线性空间 Rn上 n 个线性无关向量 v1,··· ,vn组成的点的集合, 表示为 L ={a1v1+···+anvn|ai为整数}, 其中v1,··· ,vn被称为格基. 理想格[17]则是具有特殊环结构的格. 理想I 是环R = Z[x]/f(x) 的一个商环, 其中f(x) 为首一整数多项式. n 阶整数群Zn上I 的集合便是理想格. 相较于格, 理想格可以使用一个向量表示一个n 维格, 大大降低了空间复杂度; 理想格的特殊代数结构可以进行快速运算, 大大降低了时间复杂度.

2.2 环上带误差学习问题

2010 年, Lyubashevsky 等[17]提出了基于理想格的环上带误差学习(ring learning with errors,RLWE) 问题并指出求解RLWE 问题的难度可以量子规约到求解近似最短向量问题.

定义1 (RLWE 分布) 设R 为Z 上阶数为n 的多项式环, Rq= R/qR 为以正整数q 为模的商环, χγ为R 上以γ 为标准差, 0 为分布中心, r 为半径的高斯离散分布. 设固定向量s 为秘密值, 在Rq×Rq上的RLWE 分布As,χγ通过均匀随机地选择向量a ∈Rq, e ∈χγ进行采样, 并得到采样结果(a,b=s·a+e(modq)).

定义2 (判定性RLWE 问题) 给定多项式个独立样本(ai,bi) ∈Rq× Rq, 任意概率多项式时间(probabilistic polynomial time, PPT) 算法A 能够区分样本取自RLWE 分布As,χγ还是均匀随机地取自Rq×Rq的优势可忽略.

2.3 误差调和机制

为解决带误差学习问题特有的误差问题, Ding 等[18]首次提出误差调和机制(称为Ding 式误差调和机制). 2014 年, Peikert[19]指出使用Ding 式误差调和机制的协议双方提取出的共同比特只是具有高熵,而非均匀分布, 需要一个随机提取器来获得均匀的值, 这会带来效率损失. 于是他提出了一个改进机制(称为Peikert 式误差调和机制), 使协议双方提取的共同比特是均匀分布的. 本文将采用Peikert 式误差调和机制, 具体描述如下:

对于奇数模数q, 可定义随机翻倍函数dbl(·): Zq→Z2q如¯v = dbl(v) :=2v −¯e, 其中¯e ∈Z, ¯e 模2 后均匀随机且与v 独立. 2w = ¯v+(2e+¯e)(mod2q)∈Z2q.

2.4 安全模型

本文的安全性在Canetti 等[16]提出的UC 框架下, 结合Canetti-Rabin[20]提出具有联合状态的UC 组合定理, 使用UC 混合模型证明.

定义6 (混合模型下的安全实现) 给定混合模型下的n 方协议π 以及理想功能F, 如果对于任意PPT 混合敌手H 都存在PPT 理想攻击者S, 使得对于任意环境Z, 在和混合敌手H 及协议π 交互后输出1 的概率分布与在和理想攻击者S 及理想功能F 交互后输出1 的概率分布是多项式不可区分的, 则称协议π 在混合模型下UC 安全地实现了理想功能F.

3 基于验证元的3PAKE 理想函数

本节基于Gentry 等[12]提出的非对称口令认证密钥交换理想功能FapwKE, 提出一个基于验证元的三方口令认证密钥交换理想功能F3VPAKE. F3VPAKE分为三个阶段: 用户认证阶段、中间秘密传输阶段和会话密钥生成阶段. 其中, 用户认证阶段利用FapwKE替代. 附录详细描述了FapwKE. F3VPAKE的理想功能过程如图1所示.

图1 F3VPAKE 的理想功能过程Figure 1 Process of ideal functionality F3VPAKE

F3VPAKE的用户认证阶段的消息处理与FapwKE中的消息处理类似. 在中间秘密传输阶段, 若Pi输入的中间秘密与他在用户认证阶段获得的中间秘密不同, 则会话结束. 在会话密钥生成阶段, 若两个用户输入的信息都存在相应的记录, 则生成相同的会话密钥. F3VPAKE的中间秘密传输阶段和会话密钥生成阶段如下所示. 其中, Send 查询表示F3VPAKE向客户端用户发送中间秘密, KeyGen 查询表示F3VPAKE为两个客户端生成相同的会话密钥.

F3VPAKE的中间秘密传输阶段和会话密钥生成阶段:

这两个阶段的参数如下. 安全参数: k; 参与者: P1,··· ,Pn; 敌手: S; 初始为空的列表: L : id,Pi,Pj,pw,status; 会话ID: ssid; 会话结束: completed.

• 中间秘密传输阶段:

4 理想格上基于验证元的三方PAKE 协议

4.1 方案描述

2017 年, Gao 等[13]提出了一个两方格基口令认证密钥交换协议——RLWE-SRP 协议. 相比较而言,本文提出的新协议具有如下三个优势:

(1) 本质上说, 两方协议只适用于用户与服务器之间的通信. 两个用户之间若需通信, 则需要服务器进行协调. 而三方协议直接面向用户与用户之间的通信, 总体效率更高;

(2) 采用Peikert 式误差调和机制, 相较于RLWE-SRP 使用的Ding 式误差调和机制, 具有更高的计算效率;

(3) 借鉴Abdalla 等[15]构造UC 安全协议的设计思想, 包括在协议开始前便唯一确定会话ID;以及在会话密钥生成阶段, 若验证失败, 验证一方会发出一条错误消息, 可保证两用户之间相互认证.

4.1.1 用户注册阶段

用户加入系统时, 需向可信服务器注册. 用户Ui选择口令PWi和盐值salti, 生成特有的两个伪随机数生成器(pseudorandom generator, PRNG) 种子seed1 = SHA3-256(salti//SHA3-256(Ui||PWi)) 和seed2 = SHA3-256(seed1). 通过PRNG 种子从高斯离散分布χγ中选取svi和evi, 从商群Rq中均匀随机地选择公共参数a, 计算出验证元vi=a·svi+evi.

用户将a, Ui, salti, vi通过安全信道发送给服务器S. S 收到Ui的注册信息后首先检索存储在数据库中的列表L 上是否已有该用户名的记录, 若未检索到, 将a, Ui, salti, vi添加到L 上; 若检索到, 则提示用户重新输入用户名. 发送完注册信息后, 用户将所有生成的变量从内存中擦除. 如果验证元泄露, 需重新执行用户注册阶段生成新的验证元.

4.1.2 相互认证及密钥交换阶段

用户之间每次会话会自动生成一个会话ID 即SSID, 会话ID 为ssid 的三方认证及协商会话密钥的过程如下, 其中具体的计算如图2 所示.

(1) Ux→S :Ux|Uy

当用户Ux想要与用户Uy通信时, 输入对方的用户名Uy, 服务器名S, 自己的口令PWx. Ux将通信请求Ux|Uy发送给S.

(2) S →Ux:saltx|Rsx; S →Uy:salty|Rsy

图2 RLWE-3VSRP 相互认证及密钥交换过程Figure 2 Mutual authentication and key exchange of RLWE-3VSRP

4.2 正确性验证

若Ux, Uy和S 诚实地运行协议, S 将显式地认证Ux和Uy, Ux和Uy将以显著的概率得到SKxy=SKyx. 协议中:

5 安全性证明

本节定义一系列游戏来证明定理1. 表1 中给出了用这些游戏证明不可区分性的简要过程, 其中游戏G2是考虑A 未执行查询直接猜测出SKxy意外获胜的情况; 游戏G3和G4分别考虑了在中间秘密传输阶段之前没有攻陷发生和客户端已经被攻陷两种情况; 游戏G5考虑了服务器在中间秘密传输阶段被半攻陷的情况. 混合模型下, 攻击者H 和协议的用户实例通过下述查询进行交互:

(1) TestAbort 查询: 验证客户端用户身份是否有效.

(2) StealPWfile 查询: 攻击者获取服务器中存储的口令数据.

(3) OfflineTestPwd 查询: 验证从服务器中获取的口令数据是否为想要的那个口令的数据.

(4) Send 查询: 向客户端用户发送中间秘密.

(5) KeyGen 查询: 为两个客户端生成相同的会话密钥.

表1 UC 框架下RLWE-3VSRP 不可区分性证明概览Table 1 Overview of indistinguishability proof of RLWE-3VSRP under UC framework

证明: 游戏G0: 该游戏是环境Z 与A 及RLWE-3VSRPE 协议的实例在随机预言模型以及非对称口令认证密钥交换模型下进行交互.

游戏G1: 理想攻击者S 模拟随机预言机和非对称口令认证密钥交换预言机.

(1) 在随机预言模型下, S 维持一个长度为qH的列表ΛH, 用于提供随机预言机H1和H2的查询应答. 对于一个Hash 查询Hn(q)(n = 0 或1 或2), 如果在ΛH中存在(n,q,r) 记录, 则返回r; 否则, 随机选取一个r ∈{0,1}lHn, lHn是Hn的长度, 若ΛH中已经存在类似(n,∗,r) 的记录, 则中止查询; 否则, 在ΛH中添加(n,q,r) 记录并返回.

(2) 在非对称口令认证密钥交换模型下, S 维持一个长度为qAV的列表ΛAV= (ssid,Pi,Pj,pw,w)来提供非对称口令认证密钥交换预言机的 TestAbort 查询应答. 对于一个 TestAbort 查询(TestAbort,ssid,Pi,Pj,pw,w′), 如果qAV中存在(ssid,Pi,Pj,pw,w) 记录, 且w′= w, 则令b = succ,表示服务器成功验证客户端身份; 否则, 令b=fail, 表示服务器验证客户端身份失败. 返回b.

引理1 游戏G0和游戏G1对于任意环境Z 都是概率多项式不可区分的.

证明: 根据哈希函数的抗碰撞性, 对于r ̸= r′, 得到Hn(r) = Hn(r′)(n = 1 或2) 的概率是可忽略的. 用户认证阶段基于RLWE-SRP 构造, RLWE-SRP 具有UC 安全, 故而A 成功区分b 是来自协议RLWE-3VSRPE 还是非对称口令认证密钥交换预言机的概率可忽略. 因此A 无法在概率多项式时间内区分游戏G0和游戏G1.

游戏G2: 此游戏与游戏G1基本相同, 不同之处在于如果现实世界敌手A 在未执行任何查询的情况下成功猜测出SKxy, 则理想攻击者S 中止模拟随机预言机和非对称口令认证密钥交换预言机.

引理2 游戏G1和游戏G2对于任意环境Z 都是概率多项式不可区分的.

证明: 此种情况发生的概率是可忽略的,故A 无法在概率多项式时间内区分游戏G1和游戏G2.

游戏G3: 假定S 有能力掌控协议前三轮的双方参与者, 可知道两参与者的口令, 而A 可通过口令数据窃取(包括StealPWfile 查询和OfflineTestPwd 查询) 来攻陷参与者. 在该游戏中, S 模拟在中间秘密传输阶段中没被攻陷的服务器. 如果在中间秘密传输阶段之前没有攻陷发生, 则在中间秘密传输阶段S 模拟两方参与者模拟协议的执行. 如果在中间秘密传输阶段最开始, 两方参与者仍然都没有被攻陷, 且所有的消息都是预言机产生的, 则S 执行SamePwd 查询, 验证两方口令是否相同. 如果两方口令相同, S 从Rq×Rq中随机选择一个中间秘密K, 并将K 发送给两方参与者; 否则, S 从Rq×Rq中随机选择一个中间秘密单独发给客户端, 服务器则只收到错误信息. 如果在中间秘密传输阶段之前某一方参与者已经被攻陷, S 将不执行任何操作.

引理3 游戏G2和游戏G3对于任意环境Z 都是概率多项式不可区分的.

证明: 当两方参与者的口令相同时, 此游戏与前面的游戏不可区分; 当两方参与者的口令不同时, 根据RLWE 判定问题, A 成功区分K 是取自RLWE 分布As,χγ还是Rq×Rq的概率可忽略, 故A 无法在概率多项式时间内区分游戏G2和游戏G3.

游戏G4: 在该游戏中, S 模拟在中间秘密传输阶段中没被攻陷的服务器. 如果在中间秘密传输阶段之前客户端已经被A 攻陷, S 恢复出服务器已使用过的口令, 并验证客户端发送的Mi是否正确. 如果Mi正确, S 询问关于服务器GoodPwd 的查询, 若口令正确, 服务器会获得和客户端同样的中间秘密, 否则,会获得一条错误信息. 如果Mi不正确, 服务器会获得一条错误信息.

当A 意外猜测到了K 时, A 可在客户端发送完Mi之后模仿客户端, 此时游戏中止.

引理4 游戏G3和游戏G4对于任意环境Z 都是概率多项式不可区分的.

证明: A 意外猜测到K 的概率可忽略, 故A 无法在概率多项式时间内区分游戏G3和游戏G4.

游戏G5: 在该游戏中, S 模拟在中间秘密传输阶段被半攻陷的服务器. 当A 半攻陷服务器后, S 发送X,Y,xs给A. A 根据信息计算出SKxy则游戏中止.

引理5 游戏G4和游戏G5对于任意环境Z 都是概率多项式不可区分的.

证明: 根据RLWE 问题, A 根据X,Y,xs能够计算出SKxy的概率可忽略, 故A 无法在概率多项式时间内区分游戏G4和游戏G5.

游戏G6: S 从协议开始模拟未被攻陷的客户端和服务器, 其中将游戏G3和游戏G4中使用的混合模型下的GoodPwd 查询和SamePwd 查询分别替换为理想模型下的TestPwd 查询和NewKey 查询, 如果游戏中止或终止都会告知A.

引理6 游戏G5和游戏G6对于任意环境Z 都是概率多项式不可区分的.

证明: 如果两方参与者拥有相同的ssid, 相对的角色(客户端1、服务器、客户端2) 并且有相同的(X,Y,ss) 对, 则称两客户端拥有匹配会话. 如果三方拥有匹配会话, 则他们会得到相同的会话密钥: 如果三方都未被攻陷, 则两客户端的会话密钥与游戏G3中相同; 如果客户端被攻陷, 则他们的会话密钥与游戏G4相同; 如果客户端未被攻陷, 服务器被半攻陷, 他们的会话密钥与游戏G5中相同. 如果三方未拥有匹配会话, 他们的(X,Y,ss) 对或K 必有不同, 三方拥有相同的(X,Y,ss) 对的概率以/q 为上界, 这个概率是可忽略的, 其中qAV为向非对称口令认证密钥交换预言机查询的次数. 故A 无法在概率多项式时间内区分游戏G5和游戏G6.

由于游戏 G7与理想功能 ˆF3VPAKE中的三方拥有完全一样的行为, 因此游戏 G7与理想功能对于任意环境Z 都是概率多项式不可区分的. 进一步综合引理1 至引理6 可知, 对于任意环境Z, 在和混合敌手H 及RLWE-3VSRP 协议的实例交互后输出1 的概率分布与在和理想攻击者S 及理想功能 ˆF3VPAKE交互后输出1 的概率分布是多项式不可区分的. 定理1 证毕.

6 协议比较

本节从安全性和计算与通信效率两方面对本章节所提出的新协议 RLWE-3VSRP 与相关格上3PAKE 协议进行比较, 相关协议包括Xu-3PAKE[7]、Choi-3PAKE[8]及Liu-3PAKE[11]. Ding 式REC 代表Ding 式误差调和机制; Peikert 式REC 代表Peikert 式误差调和机制. 协议模型为对称模型即用户口令以明文或哈希值的形式存储在服务器中; 非对称模型即基于验证元的模型.

如表2 所示, 在计算与通信效率方面, 这四个协议均基于RLWE 问题, 且通信轮数和环运算次数相差不大. 新协议在设计时使用Peikert 式误差处理, 相较于Ding 式误差处理具有更高的计算效率. 并且,新协议未使用额外的构造单元, 不会产生额外的计算开销. 在安全性方面, Xu-3PAKE、Choi-3PAKE 和Liu-3PAKE 都是对称PAKE 协议, 易遭受服务器泄露攻击. 新协议RLWE-3VSRP 采用非对称模型,能够抵抗服务器泄露攻击. 此外, Xu-3PAKE 和Liu-3PAKE 基于的Bellare-Pointcheval-Rogaway(简称BPR) 模型[21]及Choi-3PAKE 基于的Real-Or-Random (简称ROR) 模型[22], 都未考虑到协议的组合性和口令的相关性, 新协议基于的UC 模型则考虑了这两个特性. 总的来说, 新协议在保持现有格上3PAKE 协议的计算与通信效率的基础上, 具有更强的安全性, 尤其是基于验证元的设计, 能够抵抗服务器泄露攻击.

表2 理想格上3PAKE 协议的协议比较Table 2 Protocol comparison of 3PAKE protocols from ideal lattices

7 结束语

本文在通用可组合框架下, 首先定义了基于验证元的3PAKE 理想功能, 然后进一步基于RLWESRP 协议提出了一个理想格上基于验证元的3PAKE 协议, 接着证明了该协议可以安全地实现该理想功能. 最后, 我们将新协议与现有格上3PAKE 协议进行了比较, 结果表明新协议不仅具有更高的安全性, 尤其是可抵抗服务器泄露攻击, 而且达到了与相关协议相当的计算和通信效率.