基于RLWE的雙因子三方認證密鑰交換協(xié)議*

申艷梅，李亞平，王 巖，王 輝，黃鸝娟

(河南理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院,河南 焦作 454003)

1 引言

密鑰交換KE(Key Exchange)協(xié)議是通信方在開放的信道上產(chǎn)生共享會話密鑰來建立安全的通信信道。認證密鑰交換AKE(Authenticated Key Exchange)協(xié)議使得通信雙方在有主動敵手的信道上建立安全的共享會話密鑰，同時實現(xiàn)彼此身份的相互認證，在之后的對稱密碼中用于保證數(shù)據(jù)的完整性和真實性。

在后量子時代，隨著量子計算機的快速發(fā)展，現(xiàn)有的AKE協(xié)議在很大程度上是基于傳統(tǒng)的數(shù)學(xué)問題設(shè)計的，這些問題在使用量子計算機進行攻擊時是不安全的。而基于格理論構(gòu)造的新型密碼體制因具有較好的漸進效率、運算簡單、可并行性、抗量子攻擊和存在最壞情況下的隨機實例等優(yōu)點，成為密碼學(xué)中最有前途的后量子選擇之一。

2005年，Regev[1]提出了格上的困難性問題誤差學(xué)習(xí)LWE(Learning With Error)，并設(shè)計了基于LWE的公鑰密碼體制，使得構(gòu)造密碼系統(tǒng)時更加安全、方便。2010年，Lyubashevsky[2]提出基于環(huán)上誤差學(xué)習(xí)RLWE(Ring Learning With Error)問題的代數(shù)結(jié)構(gòu)，并將其多項式時間量子算法的困難性規(guī)約為理想格上最壞情形下的困難問題。基于RLWE問題構(gòu)造的密碼體制因其密鑰及密文尺寸短、運行效率高等優(yōu)勢，成為學(xué)術(shù)界設(shè)計后量子密鑰交換協(xié)議的研究熱點。而目前已有的基于RLWE的后量子密鑰交換協(xié)議[3 - 8]大多是無認證的Diffie-Hellman式密鑰交換協(xié)議，只能提供被動安全，滿足用戶服務(wù)器的認證結(jié)構(gòu)。但是，實際網(wǎng)絡(luò)中廣泛運用的密鑰交換協(xié)議存在主動攻擊，且需要滿足端到端的大規(guī)模通信，因此在后量子時代設(shè)計更高效、更安全的用戶-服務(wù)器-用戶結(jié)構(gòu)的三方口令認證密鑰交換協(xié)議PAKE(Password Authenticated Key Exchange)迫在眉睫。

2005年，Abdalla等[9]在兩方PAKE的基礎(chǔ)上，基于經(jīng)典困難問題構(gòu)造了三方PAKE協(xié)議的通用結(jié)構(gòu)，之后更多的此類協(xié)議[10 - 13]被設(shè)計出來，然而都不能抵抗量子攻擊。2009年，Katz等[14]首次提出了基于LWE假設(shè)的公鑰密碼體制，設(shè)計了格上的兩方PAKE協(xié)議。2013年，葉茂等[15]在文獻[14]的兩方PAKE框架下，設(shè)計了基于LWE的三方PAKE協(xié)議，減少了通信輪數(shù)，提高了通信效率，實現(xiàn)用戶之間的顯式雙向認證，適用于大規(guī)模通信。2018年，于金霞等[16]基于LWE的困難性問題設(shè)計了格上的三方PAKE協(xié)議，可抵抗消息的重放攻擊。基于LWE的協(xié)議安全性更加穩(wěn)定、可靠，但由于存在大矩陣使得協(xié)議的計算時間和通信量增大。

2015年，Zhang等[17]排除數(shù)字簽名，直接基于RLWE的困難性和誤差問題的安全性，提出了一種客戶-服務(wù)器模式的認證密鑰交換協(xié)議，提供了幾個具體的可供選擇的參數(shù)，并證明了協(xié)議的安全性。2017年，Ding等[18]基于RLWE的假設(shè)，利用底層環(huán)的可加結(jié)構(gòu)，設(shè)計了基于格的PAKE協(xié)議，實現(xiàn)了相互認證。2018年，王彩芬等[19]為了同時實現(xiàn)用戶和服務(wù)器的雙向認證，設(shè)計了2個基于RLWE的匿名三方PAKE協(xié)議，實現(xiàn)了通信方的顯式認證，具有更高的效率和更短的密鑰長度，經(jīng)研究發(fā)現(xiàn)該協(xié)議存在會話密鑰不一致性問題。

本文基于格上RLWE的困難性問題，利用口令和生物特征信息，通過丁式錯誤協(xié)調(diào)機制提出了一種新的三方PAKE協(xié)議。主要貢獻：(1)使用生物特征和口令實現(xiàn)服務(wù)器對客戶的顯式認證，減少協(xié)議的通信輪數(shù)，降低通信量，并增強了協(xié)議的安全性。(2)設(shè)計了三方AKE協(xié)議，避免客戶-服務(wù)器模式的局限性，同時協(xié)議可抵抗字典攻擊。本文協(xié)議的安全性可規(guī)約為RLWE的困難性，是一種安全性增強、效率更高的后量子PAKE協(xié)議，且適用于端到端的大規(guī)模通信系統(tǒng)。

2 基礎(chǔ)知識

2.1 環(huán)上誤差學(xué)習(xí)

定義1(離散高斯分布) 對任何正整數(shù)α∈R和向量c∈Rm，設(shè)ρα,c(Zm)=∑x∈Zmρα,c(x)，本文定義離散高斯分布為DZm,α,c(x)=ρα,c(x)/ρα,c(Zm)，這里x∈Zm。

定義2(RLWE分布) 設(shè)s∈Rq為秘密，χ是Rq上的錯誤概率分布，a∈Zq是隨機均勻選取的，錯誤e←χ從錯誤概率分布χ中采樣得到，則RLWE分布為(a,as+emodq)∈Rq×Rq。

定義3(Cha函數(shù)) 設(shè)奇數(shù)q>2，定義Zq={-(q-1)/2,…,(q-1)/2}，取該區(qū)間的中間一半定義為E={-|q/4|,…,q/4}，則信號函數(shù)Cha可定義為：

則對于任意的v∈Zq，v+Cha(v)·(q-1)/2 modq∈E。

定義4(模函數(shù)Mod2)Zq×{0,1}→{0,1},設(shè)b=Cha(v)，有Mod2(v,σ)=(v+σ·(q-1)/2) modqmod 2。

引理3對于奇數(shù)q，以及v∈Zq,e∈Zq，當(dāng)|e|

2.2 安全模型

通過對已有的安全模型的學(xué)習(xí)，本文構(gòu)造了如下安全模型：

(2)長期密鑰：每個用戶都有一個從隨機口令字典D中選取的口令pwi作為長期密鑰，服務(wù)器與用戶共享口令。

(3)預(yù)言機詢問：攻擊者A可以詢問任意多次的預(yù)言機查詢，預(yù)言機查詢的描述如下所示：

④PasswordReveal(U,pw)詢問：通過該詢問攻擊者A將獲得用戶和服務(wù)器共享的口令pw。

⑤BiometricReveal(U,B)詢問：通過該詢問攻擊者A將獲得用戶的生物特征信息BX,其中，X∈{A,B}。

⑥Hash(mes)詢問：通過該詢問攻擊者A可獲得哈希值。隨機預(yù)言機返回散列表中存在的結(jié)果，否則返回隨機數(shù)r給攻擊者A，并存儲(mes,r)在散列表中。

3 基于RLWE的雙因子認證密鑰交換協(xié)議

3.1 用戶注冊階段

本節(jié)將要使用到的符號說明如表1所示。

Table 1 Symbol description表1 符號說明

協(xié)議執(zhí)行之前，用戶需要在服務(wù)器上注冊，通過安全信道發(fā)送自己的身份信息IDA、IDB、口令pwA、pwB和從生物特征提取器獲得的生物信息BA、BB給服務(wù)器。當(dāng)服務(wù)器收到信息后，利用模糊提取技術(shù)，通過隨機字符串生成算法Gen(BA)→(RA,PA),Gen(BB)→(RB,PB)，產(chǎn)生隨機字符串RA、RB和公開的輔助隨機字符串PA、PB，計算WA=H(RA‖pwA),WB=H(RB‖pwB)，發(fā)送PA、PB給用戶，并將(IDA,IDB，PA,PB，WA,WB，pwA,pwB)存儲在數(shù)據(jù)庫中。

3.2 相互認證及密鑰生成

Figure 1 RLWE-based three-party authentication key exchange protocol圖1 基于RLWE的三方認證密鑰交換協(xié)議

協(xié)議執(zhí)行過程：

(1)用戶A隨機采樣sA,eA←χβ,計算α=asA+eA。錄入生物信息得RA=Rep(BA,PA),計算WA=H1(RA‖pwA)，ΑuthA=H(pwA)⊕WA，并發(fā)送信息[IDA,α,ΑuthA]給用戶B。

(2)用戶B收到來自用戶A的信息后，隨機采樣sB,eB←χβ,計算β=asB+eB。錄入生物信息得RB=Rep(BB,PB),計算WB=H1(RB‖pwB),ΑuthB=H(pwB)⊕WB，并發(fā)送信息[IDA,α,ΑuthA,IDB,β,ΑuthB]給可信服務(wù)器。

(3)服務(wù)器收到來自用戶B的消息[IDA,α,ΑuthA,IDB,β,ΑuthB]后，先驗證身份信息ΑuthA、ΑuthB，驗證不通過，則終止通信。否則采樣s′A,e′A;s′B,e′B←χβ，計算α′=as′A+2e′A，β′=as′B+2e′B，k′A=αs′A,k′B=βs′B,，ω′A=Cha(k′A),ω′B=Cha(k′B)，E′A=Mod2(k′A,ω′A),E′B=Mod2(k′B,ω′B),YA=α′+H2(IDA,S,pwA,wA);YB=β′+H2(IDB,S,pwB,wB),Δ=E′A⊕E′B,最后發(fā)送消息[YA,YB,ω′A,ω′B,Δ]給用戶B。

下面將描述一系列的協(xié)議來計算攻擊者的優(yōu)勢：

協(xié)議P0：最初的協(xié)議P。

協(xié)議P1：該協(xié)議類似協(xié)議P，若誠實用戶通過通信竊聽獲取身份認證信息ΑuthA、ΑuthB，執(zhí)行協(xié)議生成會話密鑰，則攻擊者成功的優(yōu)勢可忽略。

證明攻擊者通過監(jiān)聽通信線路竊取ΑuthA、ΑuthB想要模擬用戶執(zhí)行協(xié)議獲取會話密鑰，此時攻擊者可以通過身份驗證，但服務(wù)器端通過生物特征和口令的哈希值傳遞環(huán)元素YA=α′+H2(IDA,S,pwA,wA);YB=β′+H2(IDB,S,pwB,wB)給用戶，如果執(zhí)行Send、Execute和隨機預(yù)言機詢問的概率為(nro+nse+nex)/qn，且nse+nex是確定的，則隨機獲取YA和YB值的概率為((nse+nex)+(nro+nse+nex))/qn。在攻擊者不知道口令和用戶生物特征的情況下，不能恢復(fù)環(huán)元素和模函數(shù)Mod2(kA,ωA)、ModB(kB,ωB),故不能獲得會話密鑰，攻擊失敗。

□

協(xié)議P2：該協(xié)議除了不使用隨機預(yù)言機來詢問Send、Execute，其他都和協(xié)議P1類似，而對于任何隨機預(yù)言機的詢問，使得攻擊者A與Send、Execute詢問返回一致的結(jié)果。

□

協(xié)議P3：該協(xié)議對客戶端的口令進行正確的猜測攻擊，通過詢問獲得正確的H(pw)，執(zhí)行協(xié)議，若獲得正確的會話密鑰便終止協(xié)議，攻擊者攻擊成功。顯然攻擊者不能獲得用戶的生物特征信息，則無法通過身份驗證，攻擊成功的概率可以忽略。

證明攻擊者通過對H(pw)的詢問得到口令哈希值，當(dāng)進行Αuth=H(pw)⊕WC詢問認證用戶身份時，則可以區(qū)分協(xié)議P3和P2，則攻擊者獲取成功的概率是可忽略的，其中WC是用戶的生物特征信息和口令的哈希值。

□

協(xié)議P4：該協(xié)議獲取用戶的生物特征信息，通過詢問獲得正確的WC=H1(RC‖pw)并執(zhí)行協(xié)議，RC是用戶的生物特征信息經(jīng)過模糊提取器后產(chǎn)生的比特值。若獲得正確的會話密鑰便終止協(xié)議，攻擊者攻擊成功。顯然攻擊者不能獲得用戶的口令，則無法通過身份驗證，攻擊成功的概率可以忽略。

證明攻擊者通過詢問得到WC=H1(RC‖pw)，當(dāng)通過Αuth=H(pw)⊕WC認證用戶身份時，因無法獲取用戶的口令散列值，無法通過認證，則可以區(qū)分協(xié)議P1和P2，則攻擊者獲取成功的概率是可忽略的。

□

證明攻擊者執(zhí)行協(xié)議成功的概率為：

定理1得證。

□

因此,本文所提的三方認證協(xié)議是安全的。

4 協(xié)議性能分析比較

本文通過分析協(xié)議的安全性和效率，在相互認證、通信輪數(shù)、通信量、計算復(fù)雜度、類型、困難假設(shè)、運算方法幾個方面，與文獻[4,5,16-19]相比較，其分析結(jié)果如表2所示。

由表2可知，文獻[4]選取維度n=1024的參數(shù),其協(xié)議發(fā)起方通信量為4 096 B，響應(yīng)方通信量為4 224 B，和本文協(xié)議相比總的通信量幾乎不變。文獻[5]發(fā)起方通信量為1 824 B，響應(yīng)方通信量為2 048 B，和本文的協(xié)議相比總的通信量更加理想。但是，文獻[4，5]是經(jīng)典Diffie-Hellman式密鑰交換協(xié)議，任何人都可以參加協(xié)議的運行，不能抵抗中間人攻擊，無法實現(xiàn)相互認證，只提供被動的安全性。而本文協(xié)議在不改變通信輪數(shù)的前提下，提供主動安全性并且可抵抗中間人攻擊，提供通信方的顯式相互認證，且實現(xiàn)了客戶-服務(wù)器-客戶模式的大規(guī)模通信。文獻[16]是基于LWE困難問題的三方口令認證密鑰交換協(xié)議，協(xié)議更加穩(wěn)定，因LWE的大矩陣運算使得協(xié)議計算復(fù)雜度高，通信量大，相比而言本文協(xié)議通信量和計算開銷小，且安全屬性更高。文獻[17]在BR模型下可證明安全，是理想格上基于RLWE的認證密鑰交換協(xié)議，該協(xié)議既不使用簽名方式也不使用密鑰封裝方式，卻實現(xiàn)了通信方的相互認證。但是，協(xié)議的通信量和計算復(fù)雜度略高于本文協(xié)議，且不適用于客戶-服務(wù)器-客戶模式的大規(guī)模通信。文獻[18]是具有三輪通信消息基于口令的AKE協(xié)議，相比而言，本文提出的三方口令認證密鑰交換協(xié)議在實現(xiàn)通信方相互認證的同時，降低了通信量，可抵抗口令丟失用戶假冒攻擊。文獻[19]是基于RLWE的三方口令A(yù)KE協(xié)議，盡管適用于大規(guī)模通信且可相互認證，其通信輪數(shù)為3輪，比本文協(xié)議多1輪，通信量幾乎不變，但本文協(xié)議是基于口令和生物特征的雙因子認證密鑰交換協(xié)議，安全屬性更全面，可抵抗口令丟失用戶假冒攻擊。

5 結(jié)束語

針對基于RLWE的Diffie-Hellman式密鑰交換協(xié)議存在的無認證性、不能抵抗中間人攻擊，本文結(jié)合生物特征和口令設(shè)計認證密鑰交換協(xié)議，不僅實現(xiàn)了認證性，還增強了協(xié)議的安全屬性。因兩方協(xié)議不適用于大規(guī)模通信，從通信量和計算復(fù)雜度考慮，提出了一個格上基于RLWE的雙因子三方認證密鑰交換協(xié)議，并證明了其安全性。該協(xié)議結(jié)合丁式錯誤協(xié)調(diào)機制，經(jīng)過2輪通信消息，使得通信雙方通過可信服務(wù)器提取隨機均勻比特的會話密鑰。協(xié)議將用戶口令和生物特征信息作為長期會話密鑰，避免單一口令存在的離線字典攻擊和抵抗口令丟失引起的用戶假冒攻擊，加強服務(wù)器對客戶的顯式身份認證，可防止開放信道上的主動攻擊。分析表明該協(xié)議增強了安全屬性，減少了通信輪數(shù)，降低了通信量，在后量子密鑰交換協(xié)議中具有一定的優(yōu)勢。

Table 2 Protocol performance comparison表2 協(xié)議性能比較