基于口令的認證密鑰協商協議的安全分析與改進

舒劍，許春香

(1. 電子科技大學 計算機科學與工程學院，四川 成都 611731；2. 江西財經大學 電子商務系，江西 南昌 330013)

1 引言

認證密鑰協商協議是讓用戶在開放網絡通過交互，建立一個共享的會話密鑰，從而實現開放網絡中的安全通信。較早的認證密鑰協商協議是通信雙方借助持有的高熵秘密（如數字簽名的私鑰)生成會話密鑰，然后使用會話密鑰進行加密或認證。但是這些高熵秘密不便于保存和記憶，有時還需要可信第三方的參與。讓用戶共享一個低熵的口令而生成高熵的會話密鑰在實際環境中有廣泛的應用，但這方面的研究相對較少。由于口令具有長度短的特性，攻擊者可能在離線狀態下進行窮舉字典攻擊。

Bellovin和 Merritt[1]首先提出能抵抗字典攻擊的基于口令的兩方密鑰協商協議，隨后許多相關工作[2～9]對如何利用口令生成會話密鑰進行了研究。文獻[1～9]都是在隨機預言模型下證明協議的安全性。隨機預言模型自從1993年被Bellare和Rogaway[10]提出以來，在密碼學的可證安全領域得到廣泛的應用。然而，隨機預言模型下的安全并不代表真實世界的安全，因為它依賴現實世界無法實現的隨機預言假設。另一方面，不需要隨機預言假設的證明（即在標準模型下的證明）就能夠清楚地說明，除非其所基于的底層數學難題被破解，否則一個可證安全的方案不可能被攻破。因此，在標準模型下設計基于口令的認證協議更具有實際意義。

基于 Cramer-Shoup[11]提出的 CCA2(chosen ciphertext attack-2)安全的公鑰加密體制，Katz,Ostovsky和 Yung[12]首先提出了一種標準模型下可證安全的基于口令認證密鑰協商協議。Gennaro和Lindell[13]給出了KOY協議的抽象框架。他們的協議計算復雜度很高，并且協議只能實現單向認證。為降低計算復雜度和實現雙向認證，Jiang和Gong[14]提出了一種改進的標準模型下基于口令認證密鑰協商協議。

通過引入偽隨機函數集和通信雙方均使用ElGamal加密方案，殷胤等[15]提出了高效的基于口令認證密鑰協商協議，該協議極大降低了計算復雜度。但是，協議對發起方(客戶)要進行 2次認證，并且要求服務器方擁有私鑰，因而該協議不適合只共享相同口令的雙方進行密鑰協商。另外，由于通信雙方均使用ElGamal加密方案并且協議設計不合理，筆者發現該協議不能抵抗反射攻擊或變型的反射攻擊。

本文提出一種新的基于口令認證密鑰協商協議。協議的發起方和響應方均使用ElGamal加密方案。與文獻[15]協議相比，計算機復雜度相當并且不需要響應方擁有私鑰。新協議實現了雙向認證，并在標準模型下基于 DDH假設給出了安全性證明。

2 背景知識

2.1 DDH(decisional Diffie-Hellman)假設

2.2 偽隨機函數集

2.3 形式化安全模型

本節簡要回顧 Bellare等在文獻[5]中定義的基于口令密鑰協商協議的形式化安全模型。模型包括一個協議參與者集合U，每個參與者被模擬為一組預言機。參與者擁有一個共同的口令，預言機 ∏n

I,J指參與者I與J的第n個實例。模型中還包括一個主動攻擊者(用A表示)，它被定義為一個概率多項式時間圖靈機。模型將攻擊者的能力抽象為對若干個預言機的查詢，并且這些查詢可以是無序和自適應的。

定義1會話標識符(SID)：預言機 ∏n發送和I,J接收的所有消息的串聯。

定義2搭檔預言機(PID)：若2個預言機在同意(accept)狀態時有相同的會話標識符 SID, 則稱 2個預言機互為搭檔。

Execute查詢：這種查詢模擬被動攻擊。攻擊者A通過查詢 execute( ∏n,∏s)獲得搭檔預言機I,J J,I∏n和 ∏s執行過程中的所有交互信息。

I,J J,I

Send查詢：這種查詢模擬主動攻擊。攻擊者A向預言機 ∏n發送偽造消息，若預言機收到的消息I,J為空(null)，表示攻擊者讓預言機發起一個新的會話。查詢返回消息為接收到假冒消息后，預言機按照協議規則的回復。

Reveal 查詢：這種查詢模擬預言機 ∏n的會話I,J密鑰泄漏，返回值為 s ki。如果預言機還不是“已接受”(accepted)，則返回一個符號⊥表示終止。執行了reveal查詢的實例狀態是打開的(opened)。

Corrupt 查詢：這種查詢模擬前向安全性。要求被詢問的預言機返回它擁有的長期私鑰(口令)。回答過corrupt查詢的預言機的狀態稱為“已腐化”(corrupted)。

Test 查詢：這種查詢描述協議的語義安全性。它只能運行一次，并且只能對一個“新鮮”的預言機進行。當攻擊者 A進行 Test 查詢時，協議隨機選擇一個比特 b ∈ { 0,1},如果 b = 0 ，則返回 s ki，否則，返回一個隨機數r，攻擊者根據返回值以及利用其他查詢獲得的信息，猜測b的值為 b '。

如果在Test查詢中，攻擊者成功猜對b的值，則稱攻擊者成功。定義攻擊者 A的成功概率為pr[]S。

定義 A dvgpa,Gke為所有攻擊者 A可能取到的Advpake(A)的最大值，則稱協議是安全的，如果g,G。其中：sq表示Send 查詢的次數；N表示所有口令的總數；ε是一個可忽略函數；O(qs/N )保證每次Send查詢，攻擊者A最多排除常數個可能的口令。

定義 3新鮮預言機：預言機 ∏n在同意狀態I,J下是未打開的，其搭檔預言機也未打開，并且其搭檔預言機沒有被腐化，則預言機 ∏nI,J是新鮮的。

3 殷胤等人的協議及其攻擊

本節對殷胤等[15]提出的高效的基于口令認證密鑰協商協議進行分析。協議描述如圖1所示。其中 p ,q是大素數且滿足Gq是乘法群Z*的階為q的子群；g,h是 G 的2個生成元；u是Pq服務器擁有的私鑰；F是一個偽隨機函數集；f是從口令空間到 ZP的映射；pw是客戶和服務器共享的口令。

圖1 標準模型下可證安全的EKE協議

協議雙方均使用 ElGamal加密機制。由于ElGamal加密機制具有抵抗 CPA(chosen plaintext attack)特性，被動攻擊無法獲得任何有效信息。

在上面的攻擊中，攻擊者發動有效攻擊時消息C必須為 h = gu。即使對協議作一定的修改，使客戶對消息C進行驗證，如果C = h ，則終止協議。攻擊者仍可以利用消息的自規約特性，偽裝成服務器實施有效攻擊。攻擊過程如下。

4 新的基于口令認證密鑰協商協議

本節提出一種新的標準模型下基于口令認證密鑰協商協議，協議描述如圖2所示。 p ,q是大素數且滿足 q | ( p - 1 )； Gq是乘法群 ZP*的階為q的子群； g,h是 Gq的2個生成元；F是一個偽隨機函數集；pw是客戶和服務器共享的口令。

圖2 標準模型下可證安全的基于口令認證密鑰協商協議

協議發起方和響應方均采用 ElGamal加密機制。新協議與文獻[15]協議相比，計算復雜度相當并且不需要對協議的發起方進行2次認證。由于協議響應方不需要保存私鑰，該協議也適用于共享相同口令的2個客戶進行密鑰協商。

實驗Γ5：下面開始考慮Send查詢。當攻擊者進行Send( s erver|D |E |T)查詢時，仿真器按如下方式驗證：仿真器驗證(因為仿真器知道u的值)。如果驗證通過，則判定攻擊者成功，否則終止協議。攻擊者除非猜對了口令的值，才能通過驗證。

實驗Γ6：Γ6與Γ5的區別是當攻擊者進行Send(*, null)查詢時，用隨機數r替代消息B。

為了使攻擊者的視角保持一致性，需要處理其他的預言機查詢。Send( c lient|A|B)和 Send(c lient|a kc)查詢保持不變。由于此時消息 A |B不存在讓協議正常執行的x，Send( s erver|D |E|T)查詢修改如下。

1) 如果查詢消息是預言機產生的，仿真器不進行驗證，用 Send( c lient|A|B)查詢中的σ計算然后輸出akc并計算。當B為隨機數時，如果消息 A |B是 gpw的ElGamal加密(極小概率)，2個匹配預言機計算的σ值是相等的。仿真器的仿真實驗是完美的。

2) 如果查詢消息是攻擊者產生的，仿真器按實驗Γ5給出響應。如果攻擊者有一定的優勢獲得會話密鑰，則可以利用混合證明技巧，直接歸約為解決DDH問題。

實驗Γ7：當攻擊者進行Send(client|A|B)查詢時，如果 B = Augpw(仿真器知道u)，則判定攻擊者成功，并終止協議。

5 協議的安全性證明

證明方法是把協議執行看作仿真器與攻擊者之間的游戲。仿真器選擇 2個大素數 p ,q且滿足，然后選擇和一個偽隨機函數F并計算 h = gu。隨后公布公鑰參數 p ,q,g,h,F并像實際協議一樣給通信實體分配口令。

定理1Γ是圖2描述的協議；N表示所有可能的口令；F是的偽隨機函數集； p ,q是大素數且滿足是乘法群 ZP*的階為q的子群；g ,h是 Gq的生成元；qe,qs,qr分別表示攻擊者進行 Execute查詢、Send查詢、Reveal查詢的次數。則，

實驗0Γ：這是實際協議攻擊實驗。事件0S表示攻擊者成功猜出Test查詢中預言機所使用的比特b，則可以得到：

實驗1Γ：在實驗1Γ中，當攻擊者進行Execute查詢時，用隨機數r替代消息B。基于DDH假設，運用混合證明(hybrid arguments)技巧，可得：

實驗Γ2：Γ2與Γ1的區別在于攻擊者進行Execute查詢時, a kc,r替換為不同的隨機數。

注意，在Γ1中，消息A|B不再是gpw的ElGamal加密。不失一般性，消息可為服務器計算由于λ的隨機性和獨立性，σ2在 Gq中也是隨機均勻的。利用偽隨機函數集定義，運用混合證明技巧，可得：

實驗3Γ：在實驗3Γ中，攻擊者進行Execute查詢時，用隨機數r替代sk。

與實驗2Γ中的分析類似，得出σ是隨機均勻的。如果攻擊者不進行Reveal查詢，則在3Γ和2Γ中獲得的信息是相同的。在2Γ中，攻擊者得到sk就等價于對偽隨機函數集nF進行了一次查詢；而在3Γ中，攻擊者得到r就等價于對均勻分布函數集nH進行了一次查詢。根據偽隨機函數集的定義，沒有算法可以有效區分偽隨機函數集和均勻分布函數集，所以，

實驗4Γ：4Γ與3Γ的區別是，當攻擊者進行Execute查詢時，C替換為隨機數，即T替換為隨機數。運用混合證明技巧，可得：

由于攻擊者之前通過Execute查詢和Send查詢得到的消息 A |B不是 gpw的 ElGamal加密(B是隨機數)。攻擊者成功是因為猜對了口令的值，可得：

實驗Γ8：Γ8與Γ7的區別是，當攻擊者進行Send(c lient|A|B)查詢時，σ替換為隨機數r。

在Γ8中，說明攻擊者沒有在Send(client|A|B)查詢時成功(否則攻擊者已經在Γ7中成功，協議已終止)。這時，消息 A |B不是 gpw的ElGamal加密。與實驗Γ2的分析類似，σ是隨機均勻分布的。則，

實驗Γ9：Γ9與Γ8的區別在于攻擊者進行Send查詢時， a kc,r替換為不同的隨機數。

由于消息 A |B不是 gpw的ElGamal加密，σ是隨機均勻分布的。利用偽隨機函數的定義，運用混合證明技巧，可得：

實驗10Γ∶ 攻擊者進行Send查詢時, sk替換為隨機數。

與實驗9Γ中的分析類似，得出σ是隨機均勻的。如果攻擊者不進行Reveal查詢，則在10Γ和9Γ中獲得的信息是相同的。所以，

實驗Γ11∶ Γ11與Γ10的區別在于攻擊者進行Send( c lient|A|B)查詢時，消息T替換為隨機數。基于DDH假設，運用混合證明技巧，可得：

在11Γ中，由于攻擊者無法獲得關于pw的任何信息(與pw相關的信息 ,BT替換為隨機數后，攻擊者感覺不到任何變化)，從而無法獲得σ的任何信息，說明在Test查詢中，攻擊者無法區分sk和隨機數。

綜合以上實驗中的結果, 可以得出定理1。

定理1表明，攻擊者成功的概率依賴于它每次進行Send查詢時對口令的猜測，而與Execute查詢和 Reveal查詢無關。如果攻擊者某個時刻通過Corrupt查詢獲得了長期私鑰(雙方共享的口令)，它通過以前被動竊聽的會話信息得到許多三元對( gx, hx,D)，攻擊者無法計算 Dx，其困難等價于CDH問題。攻擊者無法獲得σ的任何信息，說明協議具備完美前向安全。

6 協議的性能分析

本節給出新協議與其他標準模型下的協議比較（見表1），新協議能抵御主動攻擊，且計算復雜度較小(新協議直接計算 gpw, 而不是 gf(pw), 由于pw較短，可以忽略以pw為指數的運算)。在通信效率方面，3種協議都要進行3輪通信而實現顯式雙向認證，并且新協議與其他2種協議占用的帶寬相同。

表1 新協議與其他協議的比較

7 結束語

本文基于ElGamal加密機制和偽隨機函數集，在標準模型下設計了可證安全的基于口令密鑰協商協議。與其他標準模型下基于口令的認證協議相比，新協議的通信效率與其他協議相當，并具有較小的計算復雜度。新協議實現了顯式雙向認證，并基于DDH假設，給出了協議的“緊規約”證明，從而真正證明了協議的安全性。

[1] BELLOVIN S, MERRITT M．Encrypted key exchange∶ password-based protocol secure against dictionary attacks[A]. Proceedings of the 1992 Conference IEEE Computer Society Symp on Research in Security and Privacy[C]. Oakland∶ IEEE Computer Society, 1992. 72-84.

[2] BELLOVIN S, MERRITT M．Augmented encrypted key exchange∶ a password-based protocol secure against dictionary attacks and password file compromise[A]. Proceedings of the 1st ACM Conference on Computer and Communication Security[C]. New York, 1993.244-250.

[3] JABLON D P. Extended password key exchange protocols immune to dictionary attacks[A]. Proceedings of the WETICE’97 Workshop on Enterprise Security[C]. Cambridge∶ IEEE Computer Society, 1997. 248-255.

[4] WU T D. The secure remote password protocol[A]. Proceedings of the Network and Distributed System Security Symp NDSS 1998[C]. San Diego, Internet Society, 1998.232-245.

[5] BELLARE M, POINTCHEVAL D, ROGAWAY P．Authenticated key exchange secure against dictionary attacks[A]. Proceedings of the Advance Eurocrypt 2000[C]. Berlin∶ Springer-Verlag, 2000.139-155.

[6] ABDALLA M, CHEVASSUT O, POINTCHEVAL D. One-time verifier-based encrypted key exchange[A]. Proceedings of Public Key Cryptography-PKC 2005[C]. Berlin∶ Springer-Verlag, 2005.47-64.

[7] ABDALLA M, POINTCHEVAL D. Simple password-based encrypted key exchange protocols[A]. Proceedings of CT-RSA 2005[C]. Berlin∶Springer-Verlag, 2005.191-208.

[8] FENG D G, XU J. A new client-to-client password-authenticated key agreement protocol[A]. Proceedings of IWCC 2009[C]. Berlin∶Springer-Verlag, 2009.63-76.

[9] HUANG H F. A simple three-party password-based key exchange protocol[J]. Int J Commun Syst, 2009, 22(4)∶ 857-862.

[10] BELLARE M, ROGAWAY P. Random oracles are practical∶ a paradigm for designing efficient protocols[A]. Proceedings of the First ACM Conference on Computer and Communication Security[C]. New York, 1993.62-73.

[11] CRAMER R, SHOUP V. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[A]. Proceedings of the Advance in Cryptology-CRYPTO 1998[C]. Berlin∶ Springer-Verlag, 1998. 13-25.

[12] KATZ J, OSTROVSKY R, YUNG M. Efficient password- authentication key exchange using human-memorable passwords[A]. Proceedings of the Advances in Cryptology-EUROCRYPT 2001[C]. Berlin∶Springer-Verlag, 2001.475-494.

[13] GENNARO R, LINDELL Y. A framework for password-based authenticated key exchange[A]. Proceedings of the Advances in Cryptology-EUROCRYPT 2003[C]. Berlin∶ Springer-Verlag, 2003.524-543.

[14] JIANG S Q, GONG G. Password based key exchange with mutual authentication[A]. Proceedings of Cryptography-SAC 2004[C]. Berlin∶Springer-Verlag, 2004.267-279.

[15] 殷胤, 李寶. 標準模型下可證安全的加密密鑰協商協議[J]. 軟件學報, 2007, 18(2)∶ 422-429.YIN Y, LI B. Provable secure encrypted key exchange protocol under standard model[J]. Journal of Software, 2007, 18(2)∶ 422-429.