理想格上基于驗證元的三方口令認證密鑰交換協(xié)議*

舒 琴, 王圣寶, 胡 斌, 韓立東

杭州師范大學 信息科學與工程學院, 杭州311121

1 引言

三方口令認證密鑰交換(three-party password-based key exchange, 3PAKE) 協(xié)議使得兩個用戶能夠在可信服務器的幫助下協(xié)商得到一個會話密鑰. 根據客戶端和服務器所持有的口令信息是否相同[1], 可將3PAKE 協(xié)議分為兩大類: 對稱協(xié)議和基于驗證元的協(xié)議. 在對稱3PAKE 協(xié)議中, 用戶口令被以明文或哈希值的形式存儲在服務器上, 一旦服務器信息遭到泄露, 敵手獲得用戶的口令后就可偽裝成合法用戶.這種攻擊被稱為服務器泄露攻擊. 而在基于驗證元的3PAKE 協(xié)議中, 用戶根據口令生成一對公私鑰, 并將公鑰作為驗證元發(fā)送給服務器, 服務器存儲該驗證元. 即使驗證元泄露, 敵手也無法推導出口令, 從而無法偽裝成合法用戶. 2007 年, Kwon 等[2]提出首個基于驗證元的3PAKE 協(xié)議, 它的安全性基于判定性Diffie-Hellman 問題. 之后, 又有多個基于驗證元的3PAKE 協(xié)議被陸續(xù)提出[3–5].

在未來的量子時代, 傳統(tǒng)基于數(shù)論難題的密碼方案或協(xié)議都將變得不再安全. 因此, 能夠抵抗量子攻擊的所謂“后量子密碼” 研究越來越受到重視. 這其中, 基于格(lattice) 上難題的3PAKE 協(xié)議的研究也逐步成為熱點之一. 2013 年, 葉等[6]構造出首個格上3PAKE 協(xié)議. 此后, 多個格上3PAKE 協(xié)議被提出[7–11]. 然而,現(xiàn)有格上3PAKE 協(xié)議皆為對稱協(xié)議,無法抵抗服務器泄露攻擊. 而基于驗證元的3PAKE協(xié)議可抵抗此類攻擊.

為填補格上基于驗證元的3PAKE 協(xié)議這一空白, 本文首先在通用可組合框架下, 基于Gentry 等[12]所提出的非對稱口令認證密鑰交換理想功能, 定義基于驗證元的3PAKE 理想功能. 然后, 借鑒Gao等[13]基于SRP[14]協(xié)議所提出的理想格上基于驗證元的兩方口令認證密鑰交換協(xié)議RLWE-SRP, 同時利用Abdalla 等[15]關于構造UC 安全協(xié)議的設計思想, 構造出一個理想格上基于驗證元的3PAKE 協(xié)議, 我們稱之為RLWE-3VSRP. 最后, 通用可組合(universal composable, UC)[16]框架下證新協(xié)議可以安全實現(xiàn)本文所定義的基于驗證元的3PAKE 理想功能.

2 預備知識

2.1 理想格

格是線性空間 Rn上 n 個線性無關向量 v1,··· ,vn組成的點的集合, 表示為 L ={a1v1+···+anvn|ai為整數(shù)}, 其中v1,··· ,vn被稱為格基. 理想格[17]則是具有特殊環(huán)結構的格. 理想I 是環(huán)R = Z[x]/f(x) 的一個商環(huán), 其中f(x) 為首一整數(shù)多項式. n 階整數(shù)群Zn上I 的集合便是理想格. 相較于格, 理想格可以使用一個向量表示一個n 維格, 大大降低了空間復雜度; 理想格的特殊代數(shù)結構可以進行快速運算, 大大降低了時間復雜度.

2.2 環(huán)上帶誤差學習問題

2010 年, Lyubashevsky 等[17]提出了基于理想格的環(huán)上帶誤差學習(ring learning with errors,RLWE) 問題并指出求解RLWE 問題的難度可以量子規(guī)約到求解近似最短向量問題.

定義1 (RLWE 分布) 設R 為Z 上階數(shù)為n 的多項式環(huán), Rq= R/qR 為以正整數(shù)q 為模的商環(huán), χγ為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 能夠區(qū)分樣本取自RLWE 分布As,χγ還是均勻隨機地取自Rq×Rq的優(yōu)勢可忽略.

2.3 誤差調和機制

為解決帶誤差學習問題特有的誤差問題, Ding 等[18]首次提出誤差調和機制(稱為Ding 式誤差調和機制). 2014 年, Peikert[19]指出使用Ding 式誤差調和機制的協(xié)議雙方提取出的共同比特只是具有高熵,而非均勻分布, 需要一個隨機提取器來獲得均勻的值, 這會帶來效率損失. 于是他提出了一個改進機制(稱為Peikert 式誤差調和機制), 使協(xié)議雙方提取的共同比特是均勻分布的. 本文將采用Peikert 式誤差調和機制, 具體描述如下:

對于奇數(shù)模數(shù)q, 可定義隨機翻倍函數(shù)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]提出具有聯(lián)合狀態(tài)的UC 組合定理, 使用UC 混合模型證明.

定義6 (混合模型下的安全實現(xiàn)) 給定混合模型下的n 方協(xié)議π 以及理想功能F, 如果對于任意PPT 混合敵手H 都存在PPT 理想攻擊者S, 使得對于任意環(huán)境Z, 在和混合敵手H 及協(xié)議π 交互后輸出1 的概率分布與在和理想攻擊者S 及理想功能F 交互后輸出1 的概率分布是多項式不可區(qū)分的, 則稱協(xié)議π 在混合模型下UC 安全地實現(xiàn)了理想功能F.

3 基于驗證元的3PAKE 理想函數(shù)

本節(jié)基于Gentry 等[12]提出的非對稱口令認證密鑰交換理想功能FapwKE, 提出一個基于驗證元的三方口令認證密鑰交換理想功能F3VPAKE. F3VPAKE分為三個階段: 用戶認證階段、中間秘密傳輸階段和會話密鑰生成階段. 其中, 用戶認證階段利用FapwKE替代. 附錄詳細描述了FapwKE. F3VPAKE的理想功能過程如圖1所示.

圖1 F3VPAKE 的理想功能過程Figure 1 Process of ideal functionality F3VPAKE

F3VPAKE的用戶認證階段的消息處理與FapwKE中的消息處理類似. 在中間秘密傳輸階段, 若Pi輸入的中間秘密與他在用戶認證階段獲得的中間秘密不同, 則會話結束. 在會話密鑰生成階段, 若兩個用戶輸入的信息都存在相應的記錄, 則生成相同的會話密鑰. F3VPAKE的中間秘密傳輸階段和會話密鑰生成階段如下所示. 其中, Send 查詢表示F3VPAKE向客戶端用戶發(fā)送中間秘密, KeyGen 查詢表示F3VPAKE為兩個客戶端生成相同的會話密鑰.

F3VPAKE的中間秘密傳輸階段和會話密鑰生成階段:

這兩個階段的參數(shù)如下. 安全參數(shù): k; 參與者: P1,··· ,Pn; 敵手: S; 初始為空的列表: L : id,Pi,Pj,pw,status; 會話ID: ssid; 會話結束: completed.

? 中間秘密傳輸階段:

4 理想格上基于驗證元的三方PAKE 協(xié)議

4.1 方案描述

2017 年, Gao 等[13]提出了一個兩方格基口令認證密鑰交換協(xié)議——RLWE-SRP 協(xié)議. 相比較而言,本文提出的新協(xié)議具有如下三個優(yōu)勢:

(1) 本質上說, 兩方協(xié)議只適用于用戶與服務器之間的通信. 兩個用戶之間若需通信, 則需要服務器進行協(xié)調. 而三方協(xié)議直接面向用戶與用戶之間的通信, 總體效率更高;

(2) 采用Peikert 式誤差調和機制, 相較于RLWE-SRP 使用的Ding 式誤差調和機制, 具有更高的計算效率;

(3) 借鑒Abdalla 等[15]構造UC 安全協(xié)議的設計思想, 包括在協(xié)議開始前便唯一確定會話ID;以及在會話密鑰生成階段, 若驗證失敗, 驗證一方會發(fā)出一條錯誤消息, 可保證兩用戶之間相互認證.

4.1.1 用戶注冊階段

用戶加入系統(tǒng)時, 需向可信服務器注冊. 用戶Ui選擇口令PWi和鹽值salti, 生成特有的兩個偽隨機數(shù)生成器(pseudorandom generator, PRNG) 種子seed1 = SHA3-256(salti//SHA3-256(Ui||PWi)) 和seed2 = SHA3-256(seed1). 通過PRNG 種子從高斯離散分布χγ中選取svi和evi, 從商群Rq中均勻隨機地選擇公共參數(shù)a, 計算出驗證元vi=a·svi+evi.

用戶將a, Ui, salti, vi通過安全信道發(fā)送給服務器S. S 收到Ui的注冊信息后首先檢索存儲在數(shù)據庫中的列表L 上是否已有該用戶名的記錄, 若未檢索到, 將a, Ui, salti, vi添加到L 上; 若檢索到, 則提示用戶重新輸入用戶名. 發(fā)送完注冊信息后, 用戶將所有生成的變量從內存中擦除. 如果驗證元泄露, 需重新執(zhí)行用戶注冊階段生成新的驗證元.

4.1.2 相互認證及密鑰交換階段

用戶之間每次會話會自動生成一個會話ID 即SSID, 會話ID 為ssid 的三方認證及協(xié)商會話密鑰的過程如下, 其中具體的計算如圖2 所示.

(1) Ux→S :Ux|Uy

當用戶Ux想要與用戶Uy通信時, 輸入對方的用戶名Uy, 服務器名S, 自己的口令PWx. Ux將通信請求Ux|Uy發(fā)送給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 誠實地運行協(xié)議, S 將顯式地認證Ux和Uy, Ux和Uy將以顯著的概率得到SKxy=SKyx. 協(xié)議中:

5 安全性證明

本節(jié)定義一系列游戲來證明定理1. 表1 中給出了用這些游戲證明不可區(qū)分性的簡要過程, 其中游戲G2是考慮A 未執(zhí)行查詢直接猜測出SKxy意外獲勝的情況; 游戲G3和G4分別考慮了在中間秘密傳輸階段之前沒有攻陷發(fā)生和客戶端已經被攻陷兩種情況; 游戲G5考慮了服務器在中間秘密傳輸階段被半攻陷的情況. 混合模型下, 攻擊者H 和協(xié)議的用戶實例通過下述查詢進行交互:

(1) TestAbort 查詢: 驗證客戶端用戶身份是否有效.

(2) StealPWfile 查詢: 攻擊者獲取服務器中存儲的口令數(shù)據.

(3) OfflineTestPwd 查詢: 驗證從服務器中獲取的口令數(shù)據是否為想要的那個口令的數(shù)據.

(4) Send 查詢: 向客戶端用戶發(fā)送中間秘密.

(5) KeyGen 查詢: 為兩個客戶端生成相同的會話密鑰.

表1 UC 框架下RLWE-3VSRP 不可區(qū)分性證明概覽Table 1 Overview of indistinguishability proof of RLWE-3VSRP under UC framework

證明: 游戲G0: 該游戲是環(huán)境Z 與A 及RLWE-3VSRPE 協(xié)議的實例在隨機預言模型以及非對稱口令認證密鑰交換模型下進行交互.

游戲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對于任意環(huán)境Z 都是概率多項式不可區(qū)分的.

證明: 根據哈希函數(shù)的抗碰撞性, 對于r ?= r′, 得到Hn(r) = Hn(r′)(n = 1 或2) 的概率是可忽略的. 用戶認證階段基于RLWE-SRP 構造, RLWE-SRP 具有UC 安全, 故而A 成功區(qū)分b 是來自協(xié)議RLWE-3VSRPE 還是非對稱口令認證密鑰交換預言機的概率可忽略. 因此A 無法在概率多項式時間內區(qū)分游戲G0和游戲G1.

游戲G2: 此游戲與游戲G1基本相同, 不同之處在于如果現(xiàn)實世界敵手A 在未執(zhí)行任何查詢的情況下成功猜測出SKxy, 則理想攻擊者S 中止模擬隨機預言機和非對稱口令認證密鑰交換預言機.

引理2 游戲G1和游戲G2對于任意環(huán)境Z 都是概率多項式不可區(qū)分的.

證明: 此種情況發(fā)生的概率是可忽略的,故A 無法在概率多項式時間內區(qū)分游戲G1和游戲G2.

游戲G3: 假定S 有能力掌控協(xié)議前三輪的雙方參與者, 可知道兩參與者的口令, 而A 可通過口令數(shù)據竊取(包括StealPWfile 查詢和OfflineTestPwd 查詢) 來攻陷參與者. 在該游戲中, S 模擬在中間秘密傳輸階段中沒被攻陷的服務器. 如果在中間秘密傳輸階段之前沒有攻陷發(fā)生, 則在中間秘密傳輸階段S 模擬兩方參與者模擬協(xié)議的執(zhí)行. 如果在中間秘密傳輸階段最開始, 兩方參與者仍然都沒有被攻陷, 且所有的消息都是預言機產生的, 則S 執(zhí)行SamePwd 查詢, 驗證兩方口令是否相同. 如果兩方口令相同, S 從Rq×Rq中隨機選擇一個中間秘密K, 并將K 發(fā)送給兩方參與者; 否則, S 從Rq×Rq中隨機選擇一個中間秘密單獨發(fā)給客戶端, 服務器則只收到錯誤信息. 如果在中間秘密傳輸階段之前某一方參與者已經被攻陷, S 將不執(zhí)行任何操作.

引理3 游戲G2和游戲G3對于任意環(huán)境Z 都是概率多項式不可區(qū)分的.

證明: 當兩方參與者的口令相同時, 此游戲與前面的游戲不可區(qū)分; 當兩方參與者的口令不同時, 根據RLWE 判定問題, A 成功區(qū)分K 是取自RLWE 分布As,χγ還是Rq×Rq的概率可忽略, 故A 無法在概率多項式時間內區(qū)分游戲G2和游戲G3.

游戲G4: 在該游戲中, S 模擬在中間秘密傳輸階段中沒被攻陷的服務器. 如果在中間秘密傳輸階段之前客戶端已經被A 攻陷, S 恢復出服務器已使用過的口令, 并驗證客戶端發(fā)送的Mi是否正確. 如果Mi正確, S 詢問關于服務器GoodPwd 的查詢, 若口令正確, 服務器會獲得和客戶端同樣的中間秘密, 否則,會獲得一條錯誤信息. 如果Mi不正確, 服務器會獲得一條錯誤信息.

當A 意外猜測到了K 時, A 可在客戶端發(fā)送完Mi之后模仿客戶端, 此時游戲中止.

引理4 游戲G3和游戲G4對于任意環(huán)境Z 都是概率多項式不可區(qū)分的.

證明: A 意外猜測到K 的概率可忽略, 故A 無法在概率多項式時間內區(qū)分游戲G3和游戲G4.

游戲G5: 在該游戲中, S 模擬在中間秘密傳輸階段被半攻陷的服務器. 當A 半攻陷服務器后, S 發(fā)送X,Y,xs給A. A 根據信息計算出SKxy則游戲中止.

引理5 游戲G4和游戲G5對于任意環(huán)境Z 都是概率多項式不可區(qū)分的.

證明: 根據RLWE 問題, A 根據X,Y,xs能夠計算出SKxy的概率可忽略, 故A 無法在概率多項式時間內區(qū)分游戲G4和游戲G5.

游戲G6: S 從協(xié)議開始模擬未被攻陷的客戶端和服務器, 其中將游戲G3和游戲G4中使用的混合模型下的GoodPwd 查詢和SamePwd 查詢分別替換為理想模型下的TestPwd 查詢和NewKey 查詢, 如果游戲中止或終止都會告知A.

引理6 游戲G5和游戲G6對于任意環(huán)境Z 都是概率多項式不可區(qū)分的.

證明: 如果兩方參與者擁有相同的ssid, 相對的角色(客戶端1、服務器、客戶端2) 并且有相同的(X,Y,ss) 對, 則稱兩客戶端擁有匹配會話. 如果三方擁有匹配會話, 則他們會得到相同的會話密鑰: 如果三方都未被攻陷, 則兩客戶端的會話密鑰與游戲G3中相同; 如果客戶端被攻陷, 則他們的會話密鑰與游戲G4相同; 如果客戶端未被攻陷, 服務器被半攻陷, 他們的會話密鑰與游戲G5中相同. 如果三方未擁有匹配會話, 他們的(X,Y,ss) 對或K 必有不同, 三方擁有相同的(X,Y,ss) 對的概率以/q 為上界, 這個概率是可忽略的, 其中qAV為向非對稱口令認證密鑰交換預言機查詢的次數(shù). 故A 無法在概率多項式時間內區(qū)分游戲G5和游戲G6.

由于游戲 G7與理想功能 ?F3VPAKE中的三方擁有完全一樣的行為, 因此游戲 G7與理想功能對于任意環(huán)境Z 都是概率多項式不可區(qū)分的. 進一步綜合引理1 至引理6 可知, 對于任意環(huán)境Z, 在和混合敵手H 及RLWE-3VSRP 協(xié)議的實例交互后輸出1 的概率分布與在和理想攻擊者S 及理想功能 ?F3VPAKE交互后輸出1 的概率分布是多項式不可區(qū)分的. 定理1 證畢.

6 協(xié)議比較

本節(jié)從安全性和計算與通信效率兩方面對本章節(jié)所提出的新協(xié)議 RLWE-3VSRP 與相關格上3PAKE 協(xié)議進行比較, 相關協(xié)議包括Xu-3PAKE[7]、Choi-3PAKE[8]及Liu-3PAKE[11]. Ding 式REC 代表Ding 式誤差調和機制; Peikert 式REC 代表Peikert 式誤差調和機制. 協(xié)議模型為對稱模型即用戶口令以明文或哈希值的形式存儲在服務器中; 非對稱模型即基于驗證元的模型.

如表2 所示, 在計算與通信效率方面, 這四個協(xié)議均基于RLWE 問題, 且通信輪數(shù)和環(huán)運算次數(shù)相差不大. 新協(xié)議在設計時使用Peikert 式誤差處理, 相較于Ding 式誤差處理具有更高的計算效率. 并且,新協(xié)議未使用額外的構造單元, 不會產生額外的計算開銷. 在安全性方面, Xu-3PAKE、Choi-3PAKE 和Liu-3PAKE 都是對稱PAKE 協(xié)議, 易遭受服務器泄露攻擊. 新協(xié)議RLWE-3VSRP 采用非對稱模型,能夠抵抗服務器泄露攻擊. 此外, Xu-3PAKE 和Liu-3PAKE 基于的Bellare-Pointcheval-Rogaway(簡稱BPR) 模型[21]及Choi-3PAKE 基于的Real-Or-Random (簡稱ROR) 模型[22], 都未考慮到協(xié)議的組合性和口令的相關性, 新協(xié)議基于的UC 模型則考慮了這兩個特性. 總的來說, 新協(xié)議在保持現(xiàn)有格上3PAKE 協(xié)議的計算與通信效率的基礎上, 具有更強的安全性, 尤其是基于驗證元的設計, 能夠抵抗服務器泄露攻擊.

表2 理想格上3PAKE 協(xié)議的協(xié)議比較Table 2 Protocol comparison of 3PAKE protocols from ideal lattices

7 結束語

本文在通用可組合框架下, 首先定義了基于驗證元的3PAKE 理想功能, 然后進一步基于RLWESRP 協(xié)議提出了一個理想格上基于驗證元的3PAKE 協(xié)議, 接著證明了該協(xié)議可以安全地實現(xiàn)該理想功能. 最后, 我們將新協(xié)議與現(xiàn)有格上3PAKE 協(xié)議進行了比較, 結果表明新協(xié)議不僅具有更高的安全性, 尤其是可抵抗服務器泄露攻擊, 而且達到了與相關協(xié)議相當?shù)挠嬎愫屯ㄐ判?