改進的三方口令驗證元認證密鑰交換協議?

張啟慧,胡學先,劉文芬,魏江宏

1(中國人民解放軍戰略支援部隊信息工程大學,河南 鄭州 450001)

2(桂林電子科技大學 計算機與信息安全學院,廣西 桂林 541004)

當今,以移動互聯網、云計算、大數據為代表的信息技術日新月異,使人們的日常生活不斷網絡化,資產不斷數字化,構造安全的身份認證和密鑰交換(AKE)協議逐漸成為保障用戶數字化資產安全的關鍵.在所有的認證方式中,口令認證由于簡單易用、方便部署,成為目前應用最為普遍的一種[1].

早在1992 年,Bellovin 等人[2]就開創性地提出第一個真正意義上能夠抵抗離線字典攻擊的兩方口令認證密鑰交換(PAKE)協議,其中,用戶和服務器利用共享的低熵口令進行認證并生成高熵的會話密鑰.PAKE 協議僅僅要求用戶記住一個較短的口令,避免了傳統的基于對稱密鑰的AKE 協議對存儲初始對稱密鑰的專用硬件的需求,也無需網絡中配有復雜的公鑰基礎設施,非常方便實際使用.隨后,為進一步提高兩方PAKE 協議的安全性和效率,密碼學家針對兩方PAKE 協議的設計與分析進行了深入的探索,基于可證明安全理論構建了適用于PAKE的安全模型[3-6],分別設計了在隨機預言模型下安全的兩方PAKE 協議[3,4,7,8]和在標準模型下安全的兩方PAKE 協議[9-14].國際標準化組織(ISO)等機構還頒布了ISO/IEC 11770-4、IEEE Std 1363.2 等系列相關安全標準,進一步推動了PAKE 協議的廣泛應用.

兩方PAKE 協議比較適合“用戶-服務器”架構下的兩方通信,卻不適合用在大規模用戶相互通信的場合.此時,任何兩個需要相互通信的用戶都需要預先共享一個口令,從而導致每個用戶需要記住多個口令才能支持安全通信.為了降低這一情形下用戶記憶和管理口令的負擔,三方PAKE 協議隨即被提出,其中每個用戶僅僅需要和服務器共享一個口令,就可以在服務器的協助下與他人進行安全的密鑰交換.由于這類協議在大規模通信中較為實用,密碼學家基于不同假設構造了一系列實用的三方PAKE 協議[15,16],并在安全模型下嚴格地證明了協議的安全性[17-21].

盡管兩方、三方PAKE 協議已經得到深入而廣泛的研究,密碼學家提出了諸多安全、高效的構造方案,滿足了不同場合的安全應用,然而,多數已有口令協議關注的是服務器利用明文存儲用戶口令的情形,沒有考慮服務器口令文件泄露所造成的巨大威脅.而現實中關于服務器端存儲的口令文件被泄露的案例卻是層出不窮[22],亟待在PAKE 協議設計中增加減弱服務器文件泄露造成危害的措施.針對服務器文件泄露問題,常見的解決方案有驗證元[23-25]、泄露檢測[26]、慢哈希[27]、口令硬化[28]等技術.作為防止服務器文件泄露所造成攻擊的技術的典型代表,驗證元技術是指服務器端使用口令的變換值而非口令本身進行認證,使得攻擊者在獲得服務器口令文件后至少需要進行離線字典攻擊才能獲得原始的口令,有效地減弱了服務器口令文件泄露所造成的危害.

針對基于驗證元的三方PAKE 協議,楊等人[29]提出了首個標準模型下的協議構造.他們利用帶標簽的公鑰加密體制、平滑投射哈希函數等組件構造了一個基于驗證元的三方PAKE 協議,并在標準模型下分析了所提出協議的安全性.本文中,我們分析指出該協議并未達到所聲稱的安全性,難以抵抗離線字典攻擊.其次,在分析已有協議缺陷的基礎上,通過借鑒標準模型下PAKE 協議設計的新技術,我們利用改進的平滑投射哈希函數構造了一個新的基于驗證元的三方PAKE 協議,并在廣泛接受的安全模型中對其進行了嚴格的安全性證明.最后,還將所提出的基于驗證元的三方PAKE 協議與已有協議進行了安全性和效率比較,結果表明,新提出的協議在提供了更高安全性的同時具有可接受的計算和通信效率.

1 相關密碼學組件和假設

1.1 公鑰加密體制

一個公鑰加密體制含有3 個算法PKE=(KG,Enc,Dec),其中,密鑰生成算法KG在輸入安全參數k時,輸出公私鑰對(pk,sk)←KG(1k),加密算法Enc在輸入公鑰pk、明文m以及隨機數r時,輸出對應的密文c←Enc(pk,m;r),解密算法Dec在輸入私鑰sk、合法密文c時,輸出對應的明文m←Dec(sk,c),如果輸入的密文不合法,解密算法輸出⊥.

如果公鑰加密算法能夠抵御選擇密文攻擊(CCA),則稱它是CCA 安全的.在CCA 攻擊中,攻擊者A 除了能夠獲得加密公鑰pk外,還具有訪問解密預言Odec(c)=Dec(sk,c)的能力.攻擊者A 自適應地選擇兩個明文m0和m1,模擬者選擇隨機的比特b∈{0,1}并計算挑戰密文c*=Enc(pk,m).如果攻擊者在不向解密預言詢問c*的條件下,輸出猜測b′,則定義攻擊者的優勢以及相應的優勢函數分別為

其中,最大值函數跑遍所有計算時間至多為t,詢問解密預言的次數至多為qdec的CCA 攻擊者.在上述定義中,如果不提供給攻擊者訪問解密預言的能力,而僅僅讓其獲得公鑰pk,則相應的攻擊是選擇明文攻擊(CPA),此時安全的加密算法被稱為CPA 安全的.

在PAKE 協議設計中,我們需要用到公鑰加密體制的一種變體,稱為帶標簽(label)的公鑰加密體制,其定義類似于傳統的公鑰加密體制,不過,要求加密算法和解密算法能夠接受將標簽l作為一個額外的公開輸入(形如c←Enc(pk,m;l;r)),且僅當解密算法輸入和加密算法完全一樣的標簽時才能解密得到正確的明文.關于帶標簽的公鑰加密體制的CCA 安全性,其定義與傳統公鑰加密算法類似,不同之處在于,攻擊者詢問解密預言時要同時提供密文和標簽,攻擊者在選擇挑戰明文m0、m1時也需要同時提供一個挑戰標簽l*.

1.2 平滑投射哈希函數

平滑投射哈希函數最初是由密碼學家Cramer 和Shoup[30]提出的,隨后被Katz 等人[31]和Benhamouda 等人[13]加以改進用于通信高效的PAKE 協議構造.粗略地說,它是一種雙密鑰的哈希函數,給定集合X以及語言L?X,對任意的詞語c∈L,其相應的哈希值可以用兩種方式計算:利用哈希密鑰hk和c,或利用投射密鑰hp和相應于c∈L的證據w.具體而言,一個平滑投射哈希函數SPHF=(HashKG,ProjKG,Hash,ProjH)由4 個算法組成,其中密鑰生成算法HashKG在輸入安全參數k時輸出哈希密鑰hk←HashKG(1k),投射密鑰生成算法ProjKG在輸入哈希密鑰hk、語言L以及相應的元素c∈X時輸出相應的投射密鑰hp←ProjKG(hk,L,c),哈希函數Hash在輸入哈希密鑰hk、語言L以及任意元素c∈X時輸出哈希值h←Hash(hk,L,c),投射哈希函數ProjH在輸入投射密鑰hp、語言L、詞語c∈L以及相應證據w時輸出哈希值h←ProjH(hp,L,c,w).

平滑投射哈希函數應該滿足正確性和平滑性兩個特性.正確性是指,對任意合法的詞語c∈L以及相應證據w,Hash(hk,L,c)=ProjH(hp,L,c,w)成立;平滑性是指,對任意的不屬于給定語言的元素c?L,即使在已知hp的條件下,Hash(hk,L,c)也和完全隨機選取的輸出是統計不可區分的.當安全參數為k時,記εSPHF(k)為這兩個分布的統計距離的一個可忽略的上界.

1.3 口令哈希機制

Benhamouda 等人[25]形式化地給出了口令哈希機制的嚴格定義,用來描述基于驗證元的口令協議中驗證元的生成方式.一個口令哈希機制PHS 通常由5 個算法組成,其中參數生成算法PSetup在輸入安全參數k以及口令比特位數n時輸出公開參數param←PSetup(1k,1n),預鹽值生成算法PPHSalt在輸入參數param時輸出隨機的預鹽值sP←PPHSalt(param),預哈希值生成算法PPreHash在輸入參數param、預鹽值sP和口令π時輸出預哈希值P←PPreHash(param,s P,π),預鹽值sP和預哈希值P主要是客戶端使用;鹽值生成算法PSalt在輸入參數param時輸出隨機的鹽值sH←PSalt(param),驗證元生成算法PHash在輸入參數param、鹽值sH和口令π時輸出哈希值H←PHash(param,s H,π),鹽值sH和哈希值H被服務器端用作驗證元.

為了保證服務器口令文件泄露后讓攻擊者盡可能難地獲得用戶的口令,需要保證加鹽操作后攻擊者只有對每個驗證元進行獨立的離線字典攻擊才能獲得相應的口令,為此,Benhamouda 等人[25]給出了緊單向性(tight one-wayness)的定義.為了讓口令哈希機制能夠適配PAKE 協議設計中的平滑投射哈希等操作,文獻[25]還給出了一個基于代數運算的口令哈希機制.

1.4 DDH假設

設q是素數,G是q階乘法循環群,g∈G是其中的一個生成元.判定型Diffie-Hellman(DDH)假設是指,對所有概率多項式時間的攻擊者A,其成功區分{(g x,g y,gxy):x,y∈Zq}和{(g x,g y,g z):x,y,z∈Zq}上的均勻分布的優勢都是可忽略的.定義相應的優勢函數為,則DDH 假設成立意味著是安全參數的可忽略函數.

2 安全模型

本節介紹用于分析三方PAKE 協議的安全模型,該模型首先由Abdalla 等人提出[5],隨后,文獻[29,32]對其進行了改進.此外,在定義攻擊者優勢時,考慮到真實口令分布并不服從均勻分布,而是服從嚴重偏態的Zipf 分布[33],我們采用了類似于文獻[34]的方式對其進行了改進.

協議參與方.三方PAKE 協議的參與方包含兩個集合:所有用戶組成的集合U以及可信服務器組成的集合S.其中,用戶集合U又分為誠實用戶集合C和惡意用戶集合E,惡意用戶集合形式化了意圖攻擊其他用戶的惡意用戶.不失一般性,常常假設服務器集合僅包含一個元素S={S}.

長期密鑰.用戶集合U中的每一個用戶U∈U都擁有一個口令πU,服務器擁有口令列表pwS=〈pwS[U]〉U∈U,其中,pwS[U]={sU,HU}由口令πU相對應的鹽值sU和口令哈希值HU組成.

協議運行模型.假設每個用戶或服務器都可能同時運行多個會話,記Ui表示用戶U的第i個會話,Sj表示服務器S的第j個會話.概率多項式時間(PPT)攻擊者A 完全控制通信網絡,可以隨意竊聽、修改、偽造、延遲、刪除消息.形式化地講,攻擊者具有詢問下述預言的能力.

●SendClient(Ui,m):模型化攻擊者對用戶會話的主動攻擊.攻擊者將消息m發送給用戶會話Ui,然后輸出會話Ui在收到消息m后的響應消息.

●SendServer(Sj,m):模型化攻擊者對服務器會話的主動攻擊.攻擊者將消息m發送給服務器會話Sj,然后輸出會話Sj在收到消息m后的響應消息.

●Reveal(Ui):模型化會話密鑰泄露或丟失.攻擊者發給該詢問,即可獲得會話Ui的所擁有的會話密鑰.

●Corrupt(U):模型化敵手腐化用戶攻擊.攻擊者發出該詢問,即可獲得用戶U的口令以及用戶U中所有會話的內部狀態.

●Corrupt(S):模型化敵手腐化服務器攻擊.攻擊者發出該詢問,即可獲得服務器S中存儲的口令列表pwS=〈pwS[U]〉U∈U=〈{sU,HU}〉U∈U.

●Test(Ui):用以刻畫會話密鑰的安全性.如果用戶會話Ui已經生成會話密鑰,則拋擲一枚均勻的硬幣b∈{0,1}.若b=1,輸出會話Ui的真實會話密鑰;若b=0,輸出與會話密鑰等長度的隨機比特串.

對每個用戶會話Ui,記為會話標識,為其意定通信會話.如果一個會話順利完成且已生成會話密鑰,則稱其為已經接受(accepted).

匹配會話.稱兩個會話是匹配的,如果:(1)都已接受;(2)有相同的會話標識sid;(3)互為意定通信方;(4)除會話外沒有其他會話的意定通信方為.

新鮮會話.稱一個會話Ui是新鮮的,如果:(1)Ui已接受;(2)攻擊者未對Ui或其匹配會話發起Reveal詢問;(3)在會話Ui接受之前,攻擊者未對用戶U以及服務器發起過Corrupt詢問.

語義安全.在協議運行過程中,PPT 攻擊者A 能以任意順序發出Execute、SendClient、SendServer、Reveal和Corrupt詢問,但只能針對某個新鮮的用戶會話發出一次Test詢問.最終,A 輸出一個比特b′作為Test中的隨機比特b的猜測,若b′=b,則認為攻擊者攻擊成功,并記該事件為Succ.假設所攻擊的協議為P,相應口令字典為D,我們定義攻擊者A 的優勢為=2Pr[Succ]-1.若對所有發起主動攻擊的次數至多為qsend的PPT 攻擊者A,其優勢只比大一個可忽略量,則稱協議P是語義安全的,其中,C′和s′是相應于字典D的Zipf 參數[33].例如,當利用天涯論壇泄露的口令集作為口令分布的模型時,可以得到C′=0.062239 和s′=0.155478[34].

會話密鑰私密性.為了防止誠實但好奇的(Honest-but-Curious)服務器獲知最終的會話密鑰,需特別考慮一個知道所有用戶口令的攻擊者A,并假設A 能夠詢問Execute、SendClient、Reveal和Corrupt預言以及下述TestPair預言.

最終,A輸出一個比特b′作為TestPair 中的隨機比特b的猜測,若b′=b,則認為攻擊者攻擊成功,并記為Succkp.相應地定義攻擊者A的優勢為=2Pr[Succkp]-1.若對所有的PPT 攻擊者A,其優勢是安全參數的可忽略函數,則稱協議P相對于誠實但好奇的服務器能夠保證會話密鑰的私密性.

3 一個基于驗證元的3PAKE 協議的安全缺陷

本節我們首先回顧楊等人[29]提出的基于驗證元的三方PAKE 協議(簡記為Yang-V3PAKE 協議)的詳細步驟,然后提出了針對Yang-V3PAKE 協議的離線字典攻擊.

3.1 楊等人提出的協議

Yang-V3PAKE 協議采用了文獻[24]中給出的口令哈希機制的具體構造,其中,參數生成算法PSetup輸出為(p,G,g,h),G是階為素數p的循環群,g、h是其中兩個獨立生成元.預哈希值生成算法PPreHash的輸出為,哈希算法PHash的輸出為H=(H1,H2)=.

假設用戶A和用戶B想要在服務器S的協助下進行安全的密鑰交換,其中,A和B分別擁有口令πA和πB,服務器S擁有相應驗證元,則Yang-V3PAKE 協議的具體步驟如下.

(1)服務器S選擇兩個隨機數s A,sB∈RZp,分別計算,然后發送消息給用戶A,發送消息給用戶B;

(2)用戶A收到消息后,運行平滑投射哈希密鑰生成算法HashKG,生成哈希密鑰hk=(η1,η2,θ,μ,γ),計算ωA=hμ,,并利用ωAS計算MAC 認證值σAS=(A||B||S||),然后選擇隨機數rA∈RZp計算并向服務器發送消息;類似地,用戶B收到消息(,H1B)后,選擇隨機哈希密鑰和隨機數rB∈RZp,計算ω B,,TB,ωBS,σBS,e′,并向服務器發送消息.

(3)服務器S接收到消息后,首先計算,然后驗證σ AS,σBS的有效性.當驗證都通過時,服務器計算,生成MAC 值λAS=(A||B||S||eAS),λBS=(A||B||S||eBS),接著向用戶A和B分別發送消息(e AS,e BS,λAS)和(eBS,e AS,λBS).

(4)用戶A收到消息(e AS,e BS,λAS)后,首先驗證MAC 值λAS是否有效.驗證通過后,計算,l=(A,B,hp),,ξ=H k(l,u,eAS),然后,用戶A給用戶B發送消息hp=(hp1,hp2),CAS=(u1,u2,e AS,v);類似地,用戶B收到消息(e BS,e AS,λBS)且λBS驗證通過后,相應的計算并發送消息hp′=給用戶A.

(5)用戶A和B收到對方發送的消息后,分別計算,根據平滑投射哈希函數的性質可以保證skA=skB.

文獻[29]聲稱,Yang-V3PAKE 協議能夠提供會話密鑰的語義安全性、前向安全性、針對服務器的密鑰私密性,還能夠抵抗不可測在線字典攻擊和服務器泄露攻擊.根據安全模型的定義,協議滿足語義安全性是指攻擊者成功的優勢至多為O(qs/2β)+negl(k),其中,qs為攻擊者進行在線字典攻擊的次數,這意味著攻擊者不能針對協議實施離線字典攻擊.

3.2 對Yang-V3PAKE協議的攻擊和分析

本小節首先給出對Yang-V3PAKE 協議的離線字典攻擊.我們注意到,文獻[29]中假設攻擊者A 完全控制著通信信道,可以竊聽、插入、修改消息,或是創建、重發、轉發消息.其次,Yang-V3PAKE 協議中服務器發送了第1 輪消息,用戶在收到消息后就利用口令對其進行運算計算得到第2 輪的回復消息,且該回復消息中包含一個可用于驗證的MAC 值.

假設用戶A和用戶B想要在服務器S的協助下進行安全的密鑰交換,用戶A和B的真實口令分別為πA和πB.攻擊者A 按照如下方式對用戶A的口令進行離線字典攻擊.

(1)攻擊者A 選擇隨機數r1和r2,計算,然后攻擊者A 冒充服務器S向用戶A發送消息,H1A.

(2)用戶A收到消息后,將利用其真實口令πA進行下述運算.首先,運行平滑投射哈希密鑰生成算法HashKG生成哈希密鑰hk=(η1,η2,θ,μ,ν),然后利用口令πA計算ωA=hμ,,并利用ωAS計算MAC 認證值σAS=,然后選擇隨機數rA∈RZp計算并向服務器S發送消息.

(3)攻擊者A 攔截得到上述消息,逐個地窮舉所有可能的口令,然后利用這個猜測的口令計算,并檢驗=σAS是否成立,如果等式成立,則輸出當作用戶A的口令.

4 改進的基于驗證元的3PAKE 協議

鑒于Yang-V3PAKE 協議是首個在標準模型下設計的基于驗證元的三方PAKE 協議,但是該協議并沒有滿足三方PAKE 的安全需求,本節中我們提出一個新的改進的基于驗證元的三方PAKE 協議,并在標準模型下對所構造的協議進行嚴格的安全性證明.

4.1 協議描述

本節給出我們改進的基于驗證元的3PAKE 協議的詳細設計,記為I-V3PAKE 協議,該協議用到了文獻[11,21]中的PAKE 的設計技術以及文獻[25]中針對驗證元的驗證技術.

I-V3PAKE 協議用到了CPA 安全的ElGamal 公鑰加密體制PKE′=(KG′,Enc′,Dec′)和一個CCA 安全的帶標簽的公鑰加密體制PKE=(KG,Enc,Dec).記ElGamal 公鑰加密體制PKE′所對應的公鑰為pk′=(g,h),明文m所對應的ElGamal 密文為c←Enc′(pk′,m;r)=(u=g r,e=h r?m),記公鑰加密體制PKE 所對應的公鑰為pk.盡管協議設計使用了公鑰加密體制,但是并沒有依賴公鑰基礎設施(PKI),只需如同文獻[11]一樣,將這兩種加密算法的公鑰pk′和pk當作協議運行環境設置中的公共參考串(CRS).

協議采用了如下代數口令哈希機制PHS,其中,sP=⊥,P=gF(π),s=sH∈R{0,1}k,H=sF(π),F(?)是從口令空間到指數集Zq上的變換.定義語言

假設用戶A和用戶B想要在服務器S的協助下進行安全的密鑰交換,其中,A和B分別擁有口令πA和πB,服務器S擁有相應驗證元(s A,HA=)和(s B,HB=),則I-V3PAKE 協議的具體步驟如下.

(1)用戶A選擇隨機數rA∈Zp,計算口令的預哈希值PA=對應的ElGamal 密文cAS=(uA=,eA=?PA),然后發送消息〈A,B,cAS〉給服務器S;類似地,用戶B選擇隨機數rB∈Zp,計算口令的預哈希值PB=對應的ElGamal 密文,然后發送消息〈B,A,cBS〉給服務器S.

(2)服務器S收到消息后,先為用戶A選擇隨機數hkA=(x A,y A,zA),計算,設置lA=A||B||S||cAS||hp1A||hp2A,MA=s A||HA,并用tkA作為加密的隨機數計算cSA=Enc(pk,M A;l A;tkA),并發送消息〈s A,hp1A,hp2A,cSA〉給用戶A;類似地,為用戶B選擇隨機數hkB=(x B,yB,zB),計算hp1B=,tk B||mk B=Hash(hk B,L B,cB)=,設置lB=B||A||S||cBS||hp1B||hp2B,MB=s B||HB,并用tkB作為加密的隨機數計算cSB=Enc(pk,M B;l B;tkB),同時發送消息〈s B,hp1B,hp2B,cSB〉給用戶B.

(3)用戶A收到〈hp1A,hp2A,cSA〉后,首先計算tk A||mk A=ProjH((hp1A,hp2A),L A,c A,(rA,πA))=,然后利用tkA作為隨機數重新計算=Enc(pk,M A;l A;tkA),并驗證與其接收到的cSA是否相等.如果驗證不相等,則立即結束會話;如果驗證通過,則用戶A選擇隨機數x∈Zp,計算X=gx,σAS=MAC(mk A,A||B||S||X),然后向服務器S發送消息〈X,σAS〉;類似地,用戶B收到消息〈hp1B,hp2B,cSB〉后,計算tk B||mkB并驗證cSB,驗證通過后選擇隨機數y∈Zp,計算Y=gy,σBS=MAC(mk B,B||A||S||Y),然后向服務器S發送消息〈Y,σBS〉.

(4)服務器S收到消息后,首先用密鑰mkA和mkB驗證MAC 值σAS和σBS是否正確,驗證通過后計算σSA=MAC(mk A,A||B||S||X||Y),σSB=MAC(mk B,B||A||S||Y||X),然后向用戶A發送消息〈Y,σSA〉,向用戶B發送消息〈X,σSB〉.

(5)用戶A和B在收到來自服務器的消息后,分別利用密鑰mkA和mkB驗證MAC 值σSA和σSB是否正確,驗證失敗,則結束會話.然后,用戶A計算會話密鑰為skAB=Yx,用戶B計算會話密鑰為skBA=Xy.

在用戶和服務都誠實運行協議的情況下,對與用戶A相關的語言LA=而言,下式成立:

可知用戶A和服務器S將計算得到相同的tk A||mkA,保證了cSA、σAS、σSA的正確性;類似地,用戶B和服務器S將計算得到相同的tk B||mkB,保證了cSB、σBS、σSB的正確性.因此,協議中驗證都將通過,最終A和B將生成相同的會話密鑰skAB=Yx=gxy=Xy=skBA.

注1.在I-V3PAKE 協議中,我們利用具有良好代數性質的口令哈希機制和特別構造的平滑投射哈希函數實現了對口令和驗證元的驗證.一方面,用戶在利用投射密鑰計算哈希值ProjH(hp,Ls,H,c,(r,π))=時需要用到F(π),驗證了用戶確實擁有F(π)和π;另一方面,語言Ls,H={(u,e):?r,?π,u=g r,e=h r gF(π),H=sF(π)}的定義方式保證了e=h r g F(π)中的g F(π)部分相對于g的指數與H相對于s的指數是相等的,即證實了服務器確實擁有與用戶相匹配的驗證元.

注2.I-V3PAKE 協議能夠抵御針對Yang-V3PAKE 協議[29]的離線字典攻擊.具體地,如果攻擊者仿照第3.2節中提到的攻擊方法將I-V3PAKE 協議的第1 輪消息替換成偽造的消息,則只要攻擊者未猜對用戶U∈{A,B}的口令,將由于ElGamal 密文(u,e)?Ls,H使得服務器計算得到的tk U||mkU對攻擊者來說是完全隨機的,從而攻擊者無法通過驗證cSU來判別其猜測口令的正確性.

4.2 協議比較

本節給出I-V3PAKE 協議與其他典型的三方PAKE 協議在功能、安全性、效率方面的比較,具體結果見表1.在表1 中,“驗證元”“標準模型”“抗離線字典攻擊”“C2S 認證”“Key Privacy”分別表示所考慮的三方PAKE 協議是否支持驗證元、是否在標準模型下可證明安全、是否提供抗離線字典攻擊、用戶到服務器的顯式認證以及會話密鑰針對服務器的私密性,“計算效率A/B/S”表示用戶A、B和服務器S分別所需的計算模指數運算的次數.如同文獻[32],我們采用標準模型下CCA 安全的DHIES 公鑰加密算法[35]來實例化協議中的公鑰加密算法PKE.另外,注意到形如gxhy的多指數運算可以通過快速算法在約等于單個指數的計算時間內完成[32],因而在計算效率中只算作一次指數運算.

從表1 中的結果可以看出,目前只有文獻[29]和我們的I-V3PAKE 協議是基于驗證元的,且是在標準模型下設計的,但是文獻[29]中的協議不能抵抗離線字典攻擊,因而安全性不能滿足實用要求.盡管文獻[32,36]中的協議也是在標準模型下可證明安全的,但是這兩個協議都不是基于驗證元的,因此不能抵御服務器泄露攻擊.另外,從通信和計算效率上看,我們的I-V3PAKE 協議在額外的通過驗證元方式保護口令的條件下,還具備與文獻[29,32,36]較為接近的通信和計算復雜度,甚至I-V3PAKE 協議的計算效率要更優于文獻[29].因此,I-V3PAKE 協議不僅提供了更強的安全性保障,同時具有可接受的計算和通信效率.

Table 1 Comparisons between I-V3PAKE protocol and other verifier-based 3PAKE protocols表1 I-V3PAKE 協議與其他典型三方PAKE 協議的比較

5 安全性證明

本節在前述安全模型中證明I-V3PAKE 協議的安全性,首先證明I-V3PAKE 協議滿足語義安全性,然后證明協議中誠實用戶所生成的會話密鑰相對于誠實而好奇的服務器具有私密性.

定理1.如果公鑰加密體制PKE=(KG,Enc,Dec)是CCA 安全的,ElGamal 公鑰加密體制PKE′=(KG′,Enc′,Dec′)是CPA 安全的,Ls,H是按照式(1)定義的與公鑰加密體制PKE′及口令哈希機制PHS 相關聯的語言,SPHF是相應于語言Ls,H的平滑投射哈希函數,MAC 是安全的消息認證碼,則I-V3PAKE 協議是語義安全的.

證明:假設A 是針對I-V3PAKE 協議語義安全性的攻擊者,其計算時間至多為t,訪問Send和Execute預言的次數至多為qsend,qexe.下面通過構造游戲序列G0,G1,...,G8來估計攻擊者的優勢,起始游戲是安全模型所定義的與真實協議交互的游戲.

游戲G0:這個游戲對應于安全模型中語義安全定義時的真實攻擊,記此時攻擊者的優勢為

游戲G1:從這個游戲開始,我們先逐步修改對Execute詢問的模擬方式.游戲G1中,在模擬Execute詢問時,首先將用戶端利用ProjH的計算全部替換成對應的Hash 計算.由于Execute中用戶和服務器都是誠實的,因而上述替換可行;又根據平滑投射哈希函數的正確性定義,可知在游戲G1中攻擊者具有和在游戲G0中相同的優勢,即Adv1(A)=Adv0(A).

游戲G2:在模擬Execute時,對任意用戶U∈{A,B},我們將用戶第1 條消息中的密文cUS=Enc′(pk′,PU;rU)=替換成cUS=Enc′(pk′,P0;rU)=(uU=,eU=?P0),其中,P0是一個虛擬口令π0(即不屬于口令字典中的一個值)所對應的預哈希.根據ElGamal 公鑰加密體制PKE′的CPA 安全性,可知P0和PU的密文是不可區分的,從而利用標準的混合(hybrid)證明技術將qexe個Execute預言中的密文逐個替換可知,攻擊者在游戲G2與在游戲G1中的優勢差是可忽略的,即

其中,式(4)考慮到了CPA 攻擊者在模擬協議運行時,只有在模擬Send和Execute類預言時才需要進行額外的計算,在模擬Reveal和Corrupt詢問時只需要返回對應狀態,從而其計算時間至多為t+O(qsend+qexe).

游戲G3:在模擬Execute詢問時,我們將tkU||mkU=Hash(hkU,LU,cU),U∈{A,B}替換成隨機選擇的等長比特串.由于游戲G2已將cUS替換成P0的密文,從而有cUS?L A,cUS?LB,根據平滑投射哈希函數的平滑性質,可知攻擊者在游戲G3與在游戲G2中的優勢差可忽略,即記εSPHF(k)為平滑投射哈希函數在輸入非語言元素時的輸出哈希值與均勻分布之間的統計距離的一個可忽略的上界,則有

游戲G4:在模擬Execute詢問時,我們將cSA=Enc(pk,M A;l A;tk A),cSB=Enc(pk,M B;l B;tkB)中的MA和MB替換成MA=s A||H0,A,MB=s B||H0,B,其中,H0,A=,H0,B=是對應于不屬于字典的一個虛擬口令π0?D.由于tkA和tkB在游戲G3中已被替換成完全隨機的比特串,因此根據加密體制PKE=(KG,Enc,Dec)的CCA 安全性,可知攻擊者在游戲G4與在游戲G3中的優勢差是可忽略的,因此,

需要說明的是,在游戲G4中并沒有詢問加密體制PKE 的解密預言,從而實際上只用到了PKE 體制的CPA安全性.但是,在下面的游戲G10中需要詢問解密預言,因此需要PKE 是CCA 安全的.

游戲G5:在模擬Execute詢問時,我們直接將最終的會話密鑰skAB=skBA替換成隨機值.利用DDH 自規約技術,我們證明攻擊者在實驗G4和G5中的優勢差至多為攻擊者區分DDH 三元組的優勢.給定DDH 三元組(X0,Y0,Z0),當用戶A需要生成消息X和σAS時,我們選擇隨機的a,x∈Zp,并計算X=,當用戶B需要生成消息Y和σBS時,選擇隨機的b,y∈Zp,并計算Y=,當雙方需要生成密鑰時,計算skAB=skBA=.可以看出,當三元組(X0,Y0,Z0)滿足Z0=DH(X0,Y0)時,上述游戲和游戲G4完全一樣;當Z0≠DH(X0,Y0)時,上述游戲和游戲G5是一樣的.在DDH 問題困難假設下,可知

至此,我們已將Execute模擬中的與口令相關的消息和會話密鑰替換成為隨機值,從而攻擊者不能從中獲得用戶口令的信息.下面將開始修改對敵手主動攻擊類詢問的模擬.為了表述簡單,下面用SendClient0(Ui)表示攻擊者激活用戶的初始消息,SendClient d(Ui,m),d∈{2,4}表示在第d輪通信中給用戶會話Ui發送消息m,SendServerd(S j,m),d∈{1,3}表示在第d輪通信中給服務器會話Sj發送消息m.在公開參數產生階段,我們還讓模擬者記錄對應于公鑰pk′和pk的私鑰sk′和sk.

游戲G6:本游戲修改針對用戶A的SendClient2(Ai,〈hp1A,hp2A,cSA〉)的回答方式,對用戶B按照類似的方式進行處理(下同).先檢查〈hp1A,hp2A,cSA〉是否來源于某個誠實模擬的1(j,*)SendServer S的回復,如果答案是否定,則直接解密cSA得到s′A和H′A并檢查與用戶A的口令πA是否匹配.若成立,則直接認為攻擊者A 攻擊成功并結束模擬.如果驗證不通過,則讓Ai拒絕該消息并結束該會話的模擬.容易看出,上述修改增加了攻擊者成功的途徑,因此有Adv5(A)≤Adv6(A).

游戲G7:本游戲繼續修改針對用戶A的詢問SendClient2(Ai,〈hp1A,hp2A,cSA〉)響應的模擬.若消息〈hp1A,hp2A,cSA〉確實來源于某個誠實模擬的SendServer1(Sj,*)的回復,則不再按照協議規范為Ai計算tk A||mkA,而是直接將Ai中的tk A||mkA設置成與Sj中一樣的值.此時,由于會話Ai和Sj都是誠實模擬的,故上述修改并不改變攻擊者的優勢,即Adv6(A)=Adv7(A).

游戲G8:本游戲修改針對用戶的激活消息0(i)SendClient A響應的模擬方式.類似于游戲G2,我們將其中的替換成虛擬口令所對應的P0的密文.由于加密體制PKE′是CPA 安全的,從而攻擊者在游戲G8與在游戲G7中的優勢差是可忽略的,即

游戲G9:本游戲修改服務器在收到消息SendServer1(S j,〈A,B,cAS〉)的響應方式.直接利用私鑰sk′對密文cAS進行解密,并驗證其中的PA與用戶口令πA是否匹配.如果匹配,則直接認為攻擊成功,停止模擬;如果不匹配,則按照完全隨機的方式選擇tk A||mkA.可以看出,第1 部分修改僅僅是增加了攻擊者成功的途徑,而第2 部分修改的合理性則由平滑投射哈希函數的隨機性保證,從而可得

游戲G10:本游戲繼續修改服務器在收到消息SendServer1(Sj,〈A,B,cAS〉)的響應方式.類似于游戲G4,我們將cSA=Enc(pk,M A;l A;tk A),cSB=Enc(pk,MB;l B;tkB)替換成消息MA=s A||H0,A,MB=s B||H0,B的密文,其中,H0,A==,H0,B=.由于tkA和tkB已被替換成完全隨機的比特串,因此根據加密體制PKE 的CCA 安全性(由于游戲G6需要解密能力),可知

游戲G11:本游戲修改針對SendClient d(Ai,m),d∈{2,4}的模擬.類似于游戲G5,利用DDH 自規約技術在給定三元組(X0,Y0,Z0)的情形下,修改用戶會話A和B生成X、Y、skAB、skBA的方式,即當用戶A需要計算X時,選擇隨機的a,x∈Zp并計算X=,當用戶B需要計算Y時,選擇隨機的b,y∈Zp并計算Y=,當雙方需要生成密鑰時,計算skAB=skBA=.此時,攻擊者區分真實的會話密鑰skAB=skBA和完全隨機值的優勢不超過攻擊者攻破DDH 假設的優勢,即

(1)攻擊者冒充用戶A(B類似)發送了消息〈A,B,cAS〉,且密文cAS確實是與口令πA相對應的密文;

(2)攻擊者冒充服務器向用戶A(B類似)發送了消息〈hp1A,hp2A,cSA〉,且其中的cSA確實是與口令πA相對應的驗證元(sA,HA)的密文;

(3)在MAC 安全的情況下,攻擊者成功地偽造了用戶A(B類似)所使用的MAC 認證值;

(4)攻擊者成功地猜對了Test詢問中所使用的比特b.

記計算時間至多為t的攻擊者針對協議所采用的MAC 機制的優勢函數為,由于MAC 密鑰在游戲G3和G9中已被替換成隨機值,則攻擊者通過情形(3)成功的概率至多是2(qsend+qexe)?(t+O(qsend+qexe)).若用PwdGuess表示事件“上述情形(1)或情形(2)發生”,注意到在上述游戲G11中攻擊者已經不能從會話消息獲取到口令的任何信息,從而攻擊者只能通過暴力窮舉或字典攻擊[22]猜測用戶所使用的正確口令.

當協議中所有用戶口令構成的集合服從Zipf 定律時,可知攻擊者成功的概率至多為Pr[PwdGuess]≤,其中,C′和s′是相應的Zipf 參數.另外,如果事件PwdGuess不出現,注意到協議會話密鑰都已經被替換成隨機值,可知攻擊者通過情形(4)成功的概率至多為1/2.因此可得A dv11(A)≤.綜合上式以及式(3)～式(11)可得,

定理2.若DDH 假設成立,則I-V3PAKE 協議相對于誠實而好奇的服務器可保證會話密鑰的私密性.具體地說,假設Akp是安全模型中針對會話密鑰私密性的攻擊者,其運行時間至多為t,發出的Execute和Send詢問次數至多為qexe,qsend,則有

證明:給定會話密鑰私密性攻擊者Akp,我們按照如下方式構造針對DDH 問題的攻擊者Addh.DDH 攻擊者Addh收到輸入的三元組(X0,Y0,Z0),首先為所有用戶選擇口令,為TestPair詢問選擇隨機比特b∈{0,1},誠實地模擬協議運行并基本按照規范回答攻擊者Akp發出的Execute和SendClient詢問,不同之處在于,在詢問響應中將最終X、Y、skAB、skBA相關的部分予以修改:按照類似于定理1 證明中游戲G5和G11利用隨機自規約方式將三元組(X0,Y0,Z0)嵌入到協議運行中.

最后,Addh觀察Akp的輸出比特b′,如果b′=b,則Addh輸出1,若b′≠b,則Addh輸出0.那么可以估計Addh成功的概率為

其中,Real(·)和Rand(·)分別表示輸入的三元組是真實的DDH 三元組和隨機的三元組.當(X0,Y0,Z0)是隨機三元組時,隨機自規約保證了最終會話密鑰是獨立隨機的;當(X0,Y0,Z0)是真實的DDH 三元組時,給攻擊者Akp提供的模擬環境與真實攻擊相同.最后,注意到Addh對每個Execute和SendClient詢問的模擬都只需要常數時間,即可得定理結論. □

6 結束語

本文對基于驗證元三方PAKE 協議進行了研究.首先,指出目前唯一的在標準模型下設計的基于驗證元的三方PAKE 協議存在安全缺陷,易于遭受離線字典攻擊.其次,基于ElGamal 公鑰加密體制、口令哈希機制以及支持驗證元的平滑投射哈希函數等密碼學組件,構造了一個新的基于驗證元的三方PAKE 協議,并在標準模型下證明了該協議滿足語義安全、會話密鑰私密性等安全屬性,與已有協議的比較表明新協議不僅提供了更高的安全性,而且具有可接受的計算和通信效率.