基于口令的認(rèn)證密鑰協(xié)商協(xié)議的安全分析與改進(jìn)

舒劍，許春香

(1. 電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731；2. 江西財(cái)經(jīng)大學(xué) 電子商務(wù)系，江西 南昌 330013)

1 引言

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

Bellovin和 Merritt[1]首先提出能抵抗字典攻擊的基于口令的兩方密鑰協(xié)商協(xié)議，隨后許多相關(guān)工作[2～9]對(duì)如何利用口令生成會(huì)話密鑰進(jìn)行了研究。文獻(xiàn)[1～9]都是在隨機(jī)預(yù)言模型下證明協(xié)議的安全性。隨機(jī)預(yù)言模型自從1993年被Bellare和Rogaway[10]提出以來(lái)，在密碼學(xué)的可證安全領(lǐng)域得到廣泛的應(yīng)用。然而，隨機(jī)預(yù)言模型下的安全并不代表真實(shí)世界的安全，因?yàn)樗蕾嚞F(xiàn)實(shí)世界無(wú)法實(shí)現(xiàn)的隨機(jī)預(yù)言假設(shè)。另一方面，不需要隨機(jī)預(yù)言假設(shè)的證明（即在標(biāo)準(zhǔn)模型下的證明）就能夠清楚地說(shuō)明，除非其所基于的底層數(shù)學(xué)難題被破解，否則一個(gè)可證安全的方案不可能被攻破。因此，在標(biāo)準(zhǔn)模型下設(shè)計(jì)基于口令的認(rèn)證協(xié)議更具有實(shí)際意義。

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

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

本文提出一種新的基于口令認(rèn)證密鑰協(xié)商協(xié)議。協(xié)議的發(fā)起方和響應(yīng)方均使用ElGamal加密方案。與文獻(xiàn)[15]協(xié)議相比，計(jì)算機(jī)復(fù)雜度相當(dāng)并且不需要響應(yīng)方擁有私鑰。新協(xié)議實(shí)現(xiàn)了雙向認(rèn)證，并在標(biāo)準(zhǔn)模型下基于 DDH假設(shè)給出了安全性證明。

2 背景知識(shí)

2.1 DDH(decisional Diffie-Hellman)假設(shè)

2.2 偽隨機(jī)函數(shù)集

2.3 形式化安全模型

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

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

定義1會(huì)話標(biāo)識(shí)符(SID)：預(yù)言機(jī) ∏n發(fā)送和I,J接收的所有消息的串聯(lián)。

定義2搭檔預(yù)言機(jī)(PID)：若2個(gè)預(yù)言機(jī)在同意(accept)狀態(tài)時(shí)有相同的會(huì)話標(biāo)識(shí)符 SID, 則稱 2個(gè)預(yù)言機(jī)互為搭檔。

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

I,J J,I

Send查詢：這種查詢模擬主動(dòng)攻擊。攻擊者A向預(yù)言機(jī) ∏n發(fā)送偽造消息，若預(yù)言機(jī)收到的消息I,J為空(null)，表示攻擊者讓預(yù)言機(jī)發(fā)起一個(gè)新的會(huì)話。查詢返回消息為接收到假冒消息后，預(yù)言機(jī)按照協(xié)議規(guī)則的回復(fù)。

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

Corrupt 查詢：這種查詢模擬前向安全性。要求被詢問(wèn)的預(yù)言機(jī)返回它擁有的長(zhǎng)期私鑰(口令)?；卮疬^(guò)corrupt查詢的預(yù)言機(jī)的狀態(tài)稱為“已腐化”(corrupted)。

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

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

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

定義 3新鮮預(yù)言機(jī)：預(yù)言機(jī) ∏n在同意狀態(tài)I,J下是未打開的，其搭檔預(yù)言機(jī)也未打開，并且其搭檔預(yù)言機(jī)沒(méi)有被腐化，則預(yù)言機(jī) ∏nI,J是新鮮的。

3 殷胤等人的協(xié)議及其攻擊

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

圖1 標(biāo)準(zhǔn)模型下可證安全的EKE協(xié)議

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

在上面的攻擊中，攻擊者發(fā)動(dòng)有效攻擊時(shí)消息C必須為 h = gu。即使對(duì)協(xié)議作一定的修改，使客戶對(duì)消息C進(jìn)行驗(yàn)證，如果C = h ，則終止協(xié)議。攻擊者仍可以利用消息的自規(guī)約特性，偽裝成服務(wù)器實(shí)施有效攻擊。攻擊過(guò)程如下。

4 新的基于口令認(rèn)證密鑰協(xié)商協(xié)議

本節(jié)提出一種新的標(biāo)準(zhǔn)模型下基于口令認(rèn)證密鑰協(xié)商協(xié)議，協(xié)議描述如圖2所示。 p ,q是大素?cái)?shù)且滿足 q | ( p - 1 )； Gq是乘法群 ZP*的階為q的子群； g,h是 Gq的2個(gè)生成元；F是一個(gè)偽隨機(jī)函數(shù)集；pw是客戶和服務(wù)器共享的口令。

圖2 標(biāo)準(zhǔn)模型下可證安全的基于口令認(rèn)證密鑰協(xié)商協(xié)議

協(xié)議發(fā)起方和響應(yīng)方均采用 ElGamal加密機(jī)制。新協(xié)議與文獻(xiàn)[15]協(xié)議相比，計(jì)算復(fù)雜度相當(dāng)并且不需要對(duì)協(xié)議的發(fā)起方進(jìn)行2次認(rèn)證。由于協(xié)議響應(yīng)方不需要保存私鑰，該協(xié)議也適用于共享相同口令的2個(gè)客戶進(jìn)行密鑰協(xié)商。

實(shí)驗(yàn)Γ5：下面開始考慮Send查詢。當(dāng)攻擊者進(jìn)行Send( s erver|D |E |T)查詢時(shí)，仿真器按如下方式驗(yàn)證：仿真器驗(yàn)證(因?yàn)榉抡嫫髦纔的值)。如果驗(yàn)證通過(guò)，則判定攻擊者成功，否則終止協(xié)議。攻擊者除非猜對(duì)了口令的值，才能通過(guò)驗(yàn)證。

實(shí)驗(yàn)Γ6：Γ6與Γ5的區(qū)別是當(dāng)攻擊者進(jìn)行Send(*, null)查詢時(shí)，用隨機(jī)數(shù)r替代消息B。

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

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

2) 如果查詢消息是攻擊者產(chǎn)生的，仿真器按實(shí)驗(yàn)Γ5給出響應(yīng)。如果攻擊者有一定的優(yōu)勢(shì)獲得會(huì)話密鑰，則可以利用混合證明技巧，直接歸約為解決DDH問(wèn)題。

實(shí)驗(yàn)Γ7：當(dāng)攻擊者進(jìn)行Send(client|A|B)查詢時(shí)，如果 B = Augpw(仿真器知道u)，則判定攻擊者成功，并終止協(xié)議。

5 協(xié)議的安全性證明

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

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

實(shí)驗(yàn)0Γ：這是實(shí)際協(xié)議攻擊實(shí)驗(yàn)。事件0S表示攻擊者成功猜出Test查詢中預(yù)言機(jī)所使用的比特b，則可以得到：

實(shí)驗(yàn)1Γ：在實(shí)驗(yàn)1Γ中，當(dāng)攻擊者進(jìn)行Execute查詢時(shí)，用隨機(jī)數(shù)r替代消息B。基于DDH假設(shè)，運(yùn)用混合證明(hybrid arguments)技巧，可得：

實(shí)驗(yàn)Γ2：Γ2與Γ1的區(qū)別在于攻擊者進(jìn)行Execute查詢時(shí), a kc,r替換為不同的隨機(jī)數(shù)。

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

實(shí)驗(yàn)3Γ：在實(shí)驗(yàn)3Γ中，攻擊者進(jìn)行Execute查詢時(shí)，用隨機(jī)數(shù)r替代sk。

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

實(shí)驗(yàn)4Γ：4Γ與3Γ的區(qū)別是，當(dāng)攻擊者進(jìn)行Execute查詢時(shí)，C替換為隨機(jī)數(shù)，即T替換為隨機(jī)數(shù)。運(yùn)用混合證明技巧，可得：

由于攻擊者之前通過(guò)Execute查詢和Send查詢得到的消息 A |B不是 gpw的 ElGamal加密(B是隨機(jī)數(shù))。攻擊者成功是因?yàn)椴聦?duì)了口令的值，可得：

實(shí)驗(yàn)Γ8：Γ8與Γ7的區(qū)別是，當(dāng)攻擊者進(jìn)行Send(c lient|A|B)查詢時(shí)，σ替換為隨機(jī)數(shù)r。

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

實(shí)驗(yàn)Γ9：Γ9與Γ8的區(qū)別在于攻擊者進(jìn)行Send查詢時(shí)， a kc,r替換為不同的隨機(jī)數(shù)。

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

實(shí)驗(yàn)10?！?攻擊者進(jìn)行Send查詢時(shí), sk替換為隨機(jī)數(shù)。

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

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

在11Γ中，由于攻擊者無(wú)法獲得關(guān)于pw的任何信息(與pw相關(guān)的信息 ,BT替換為隨機(jī)數(shù)后，攻擊者感覺(jué)不到任何變化)，從而無(wú)法獲得σ的任何信息，說(shuō)明在Test查詢中，攻擊者無(wú)法區(qū)分sk和隨機(jī)數(shù)。

綜合以上實(shí)驗(yàn)中的結(jié)果, 可以得出定理1。

定理1表明，攻擊者成功的概率依賴于它每次進(jìn)行Send查詢時(shí)對(duì)口令的猜測(cè)，而與Execute查詢和 Reveal查詢無(wú)關(guān)。如果攻擊者某個(gè)時(shí)刻通過(guò)Corrupt查詢獲得了長(zhǎng)期私鑰(雙方共享的口令)，它通過(guò)以前被動(dòng)竊聽(tīng)的會(huì)話信息得到許多三元對(duì)( gx, hx,D)，攻擊者無(wú)法計(jì)算 Dx，其困難等價(jià)于CDH問(wèn)題。攻擊者無(wú)法獲得σ的任何信息，說(shuō)明協(xié)議具備完美前向安全。

6 協(xié)議的性能分析

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

表1 新協(xié)議與其他協(xié)議的比較

7 結(jié)束語(yǔ)

本文基于ElGamal加密機(jī)制和偽隨機(jī)函數(shù)集，在標(biāo)準(zhǔn)模型下設(shè)計(jì)了可證安全的基于口令密鑰協(xié)商協(xié)議。與其他標(biāo)準(zhǔn)模型下基于口令的認(rèn)證協(xié)議相比，新協(xié)議的通信效率與其他協(xié)議相當(dāng)，并具有較小的計(jì)算復(fù)雜度。新協(xié)議實(shí)現(xiàn)了顯式雙向認(rèn)證，并基于DDH假設(shè)，給出了協(xié)議的“緊規(guī)約”證明，從而真正證明了協(xié)議的安全性。

[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] 殷胤, 李寶. 標(biāo)準(zhǔn)模型下可證安全的加密密鑰協(xié)商協(xié)議[J]. 軟件學(xué)報(bào), 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.