基于口令的高效語義安全的密鑰交換

王立斌, 潘嘉昕, 馬昌社

(華南師范大學(xué)計(jì)算機(jī)學(xué)院,廣東廣州 510631)

基于口令的高效語義安全的密鑰交換

王立斌, 潘嘉昕, 馬昌社

(華南師范大學(xué)計(jì)算機(jī)學(xué)院,廣東廣州 510631)

僅借助Hash函數(shù)和異或運(yùn)算，構(gòu)造了一種高效、可證明安全的基于口令的密鑰交換協(xié)議．在隨機(jī)預(yù)言模型下，該協(xié)議的安全性可緊致歸約到計(jì)算Diffie-Hellman難題上，從而證明該協(xié)議是語義安全的，并能對(duì)抗離線字典攻擊．最后，與同類協(xié)議相比，該協(xié)議顯示出更高的執(zhí)行效率與通信效率．

基于口令的密鑰交換； 語義安全； 可證明安全； 隨機(jī)預(yù)言模型； Diffie-Hellman假設(shè)

在開放的網(wǎng)絡(luò)中，2個(gè)實(shí)體可利用密鑰交換協(xié)議協(xié)商1個(gè)共享密鑰，用以確保通信安全．基于口令的協(xié)議，能讓用戶擺脫對(duì)中心認(rèn)證服務(wù)器的依賴，用戶只需記憶1個(gè)口令即可確保協(xié)議的安全性．

為密鑰交換協(xié)議加入口令機(jī)制并不是一件容易的事情．由于口令的熵值較低以及口令空間較小等原因，攻擊者能離線枚舉口令空間以猜測(cè)口令偽裝合法用戶，稱之為離線字典攻擊．不少基于口令的協(xié)議都遭受離線字典攻擊的威脅[1-4]，所以如何加入口令機(jī)制確保協(xié)議的安全性，如何證明協(xié)議的安全性都是學(xué)者研究的熱點(diǎn)．

傳統(tǒng)的EKE協(xié)議是一個(gè)經(jīng)典的解決方案，它利用分組密碼算法加密關(guān)鍵的協(xié)議報(bào)文[5-10]．2008年，H?LBL等人[1]利用Hash函數(shù)和異或運(yùn)算對(duì)關(guān)鍵的報(bào)文進(jìn)行了保密，該方法的優(yōu)點(diǎn)在于對(duì)設(shè)備的計(jì)算能力要求低，能在智能卡等計(jì)算能力較低的設(shè)備上運(yùn)行．不久以后，CHEN等人[4]和MUNILLA等人[2]分別發(fā)現(xiàn)H?LBL等人所設(shè)計(jì)的協(xié)議具有不可抵抗離線字典攻擊的弱點(diǎn)，CHEN等人給出了一個(gè)安全的改進(jìn)方案．

針對(duì)H?LBL等人的協(xié)議中存在的安全問題以及CHEN等人改進(jìn)方案的不足，本文完成了以下2項(xiàng)工作：第一，借鑒EKE協(xié)議的設(shè)計(jì)思想設(shè)計(jì)出新的協(xié)議，克服原有協(xié)議的安全缺陷，提高了協(xié)議的執(zhí)行效率．第二，對(duì)協(xié)議的安全性進(jìn)行嚴(yán)格的證明．通過比較顯示，所提出的協(xié)議(POPKE協(xié)議)執(zhí)行效率、通信效率高于同類協(xié)議，具有語義安全性和對(duì)抗離線字典攻擊的能力．語義安全是密鑰交換協(xié)議的重要安全屬性，指攻擊者不能獲取任何有關(guān)會(huì)話密鑰的信息．POPKE協(xié)議的語義安全性在隨機(jī)預(yù)言模型下得以證明，這是同類工作中唯一一個(gè)得到形式化證明的協(xié)議．本文所采用的形式化證明方法是可證明安全的方法．它是目前廣為接受的協(xié)議安全性的形式化分析方法，其核心是歸約：將攻擊者成功攻破協(xié)議的安全性，歸約到某個(gè)計(jì)算難題之上；由于該計(jì)算難題目前不存在有效算法，所以成功攻破協(xié)議的安全性是不可行的．本文將協(xié)議的安全性緊致歸約到計(jì)算Diffie-Hellman難題上，從而證明協(xié)議是語義安全，并能對(duì)抗離線字典攻擊．

本文組織如下：第1章定義基于口令的密鑰交換協(xié)議的攻擊模型，明確攻擊者的能力與安全性定義；第2章描述了所設(shè)計(jì)的POPKE協(xié)議；第3章在隨機(jī)預(yù)言模型[11]下證明協(xié)議是語義安全的，并具有抵抗離線字典攻擊的能力；第4章將POPKE協(xié)議與其它同類型協(xié)議進(jìn)行對(duì)比，指出其具有更優(yōu)的執(zhí)行效率，并且是同類協(xié)議中唯一一個(gè)經(jīng)形式化證明的協(xié)議，最后總結(jié)全文．

1 安全模型與定義

本章定義了基于口令的密鑰交換協(xié)議的安全模型，以及一些必要的概念．該安全模型通過定義攻擊者能進(jìn)行的查詢來描述其能力，對(duì)BPR模型[6]作了簡(jiǎn)化．

1.1協(xié)議模型

協(xié)議P有2個(gè)參與者，客戶端C和服務(wù)器S．參與者的某次協(xié)議執(zhí)行稱為實(shí)例(或Oracle)，分別用Ci和Si表示客戶端實(shí)例和服務(wù)器實(shí)例，I表示任一種實(shí)例．客戶端和服務(wù)器共享著從某個(gè)字典中均勻選取的口令pw，字典D的大小為N．

攻擊者A只能通過以下定義的Oracle查詢與協(xié)議參與者交互，同時(shí)這些Oracle查詢模擬了攻擊者的真實(shí)能力：

?Send(I,m)：向?qū)嵗齀發(fā)送報(bào)文m，并根據(jù)協(xié)議P的定義返回相應(yīng)的報(bào)文．Send(Ci,Start)查詢初始化了協(xié)議的執(zhí)行．Send查詢模擬了攻擊者向協(xié)議參與者發(fā)送報(bào)文的能力；

?Reveal(I)：如果I及其伙伴(詳見下一節(jié)的定義)沒有被詢問Test，且I已獲得當(dāng)前會(huì)話的密鑰Sk，則返回Sk給A；否則返回?zé)o效記號(hào)⊥．

?Test(I)：如果I沒有獲得當(dāng)前會(huì)話的密鑰Sk，則返回⊥；否則進(jìn)行一次秘密拋幣b，如果b=1，將Sk返回，如果b=0，返回與Sk等長的隨機(jī)數(shù)．該查詢描述攻擊者是否有能力區(qū)分會(huì)話密鑰與隨機(jī)數(shù)．

在BPR模型中，攻擊者被動(dòng)攻擊的能力用Execute查詢描述，主動(dòng)攻擊的能力用Send查詢描述[6]．然而Execute查詢能用Send查詢模擬[12]，所以本文省略了Execute查詢的描述．

1.2伙伴關(guān)系與新鮮性

本文通過會(huì)話標(biāo)識(shí)符(sid)定義伙伴關(guān)系，會(huì)話標(biāo)識(shí)符可理解為Ci(或Sj)接收與發(fā)送的報(bào)文序列．假設(shè)Ci和Sj是一對(duì)實(shí)例，當(dāng)如下條件同時(shí)成立時(shí)，稱Ci和Sj互為伙伴：(1)2個(gè)實(shí)例都成功完成協(xié)議執(zhí)行并共享會(huì)話標(biāo)識(shí)符sid；(2)Ci的伙伴標(biāo)識(shí)符是S，Sj的伙伴標(biāo)識(shí)符是C．

當(dāng)如下條件同時(shí)成立時(shí)，則稱實(shí)例I是新鮮的：(1)I成功完成協(xié)議執(zhí)行；(2)I及其伙伴都沒有被詢問Reveal．

1.3語義安全

語義安全的密鑰交換(也稱AKE安全)，指攻擊者不能夠得到關(guān)于會(huì)話密鑰的任何信息．

在協(xié)議P的執(zhí)行過程中，攻擊者A能進(jìn)行若干次Send、Reveal查詢，只能對(duì)新鮮的實(shí)例詢問一次Test．最終A要猜測(cè)Test查詢中的拋幣b，假設(shè)b′是A的猜測(cè)值．如果A能以不可忽略的優(yōu)勢(shì)猜中b(即b′=b)，則A攻破了協(xié)議的語義安全．

更一般地，定義攻擊者的AKE優(yōu)勢(shì)為：

1.4計(jì)算Diffie-Hellman假設(shè)(CDH假設(shè))

假設(shè)G=g是一個(gè)素階循環(huán)群，q是G的階，g是G的生成元．CDH假設(shè)認(rèn)為：給定gx和gy(x,y從[0,q-1]中隨機(jī)選取)難以計(jì)算出gxy．記概率圖靈機(jī)Δ是一個(gè)以多項(xiàng)式t為運(yùn)行時(shí)間的CDH問題求解器，它能以不小于ε的優(yōu)勢(shì)求解CDH問題．定義解決CDH問題的優(yōu)勢(shì)為：

2 POPKE協(xié)議

本章描述了POPKE協(xié)議．

POPKE協(xié)議需要一個(gè)使CDH問題難解的q階循環(huán)群G=g，q是一個(gè)n比特的素?cái)?shù)，g是G的生成元．協(xié)議中的冪運(yùn)算在G上進(jìn)行．Hi表示從{0,1}*映射到{0,1}li的Hash函數(shù)．POPKE協(xié)議描述如下：

(1)客戶端C從{0,1}l中選取隨機(jī)數(shù)NC，從[1,q-1]中選擇隨機(jī)冪次x；計(jì)算X=gx和X*=X?H0(C,pw,NC)；向S發(fā)送{C,NC,X*}．

(2)服務(wù)器S接收了{(lán)C,NC,X*}之后，從{0,1}l中選擇隨機(jī)數(shù)NS，從[0,q-1]中選擇隨機(jī)冪次y；恢復(fù)出X(=X*?H0(C,pw,NC))，計(jì)算KS=Xy；計(jì)算Y=gy和Y*=Y?H0(S,pw,NS)；向C發(fā)送{S,NS,Y*}．

(3)客戶端C收到報(bào)文后，恢復(fù)出Y，并計(jì)算共享密鑰KC=Yx．

至此，C和S都獲取了共享的會(huì)話密鑰SkC和SkS(因?yàn)镵C=KS=gxy)．圖1簡(jiǎn)述了協(xié)議的執(zhí)行過程．

圖1 POPKE協(xié)議

3 協(xié)議安全性分析與證明

本章在隨機(jī)預(yù)言模型下，證明如果CDH問題是難解的，則POPKE協(xié)議是語義安全的．以下定理說明了這一點(diǎn)：

定理1 假設(shè)D是一個(gè)大小為N的字典；G是一個(gè)q階循環(huán)群；A是一個(gè)針對(duì)POPKE協(xié)議語義安全的攻擊者，其運(yùn)行時(shí)間不超過多項(xiàng)式t．A至多詢問qS次Send查詢和qh次Hash查詢，攻擊者的優(yōu)勢(shì)為：

證明思路本證明使用了基于Game的規(guī)約方法，將協(xié)議的安全性緊致地歸約到CDH難題上，該方法在密碼體制的安全性證明中被廣泛接受[5,10]．假設(shè)A是某個(gè)針對(duì)POPKE協(xié)議語義安全的攻擊者，利用A構(gòu)造CDH問題的求解器，如果A能以不可忽略的優(yōu)勢(shì)攻破POPKE協(xié)議的語義安全性，則求解器就能以不可忽略的優(yōu)勢(shì)解決CDH問題，從而導(dǎo)致與CDH假設(shè)相矛盾．證明的過程中，定義了一系列的Game模擬協(xié)議的執(zhí)行，以原始的攻擊Game開始，在最終的Game里攻擊者的優(yōu)勢(shì)為0，同時(shí)利用Shoup引理[13]確定Game之間可區(qū)分的概率上界．

證明對(duì)以下每個(gè)GameGi，定義如下事件：

Succi：攻擊者A成功猜測(cè)Test查詢中的b，即b′=b；

AskPadi：攻擊者A成功猜測(cè)用戶口令pw，并詢問了H0(U,pw,N)；

AskHi：攻擊者A成功猜測(cè)用戶口令pw，并詢問了H1(U1,U2,X*,Y*,K,pw)．

Game定義如下：

Game G0：這是在隨機(jī)預(yù)言模型下的原始攻擊Game，由定義，可得

(1)

Game G1：G1利用圖2展示的方式模擬Hash查詢(H2、H3將在G4中使用)，并按圖3和圖4模擬Send、Reveal、Test查詢．可見，經(jīng)過模擬后的G1與G0是不可區(qū)分的，即：

Pr[Succ1]=Pr[Succ0].

(2)

圖2 Hash函數(shù)的模擬

圖3 Send查詢的模擬

圖4 Reveal、Test查詢的模擬

(3)

Game G3：G3的模擬防止攻擊者猜測(cè)口令，并偽裝客戶端(或服務(wù)器)向?qū)Ψ桨l(fā)送報(bào)文．為此，按如下方式修改Send查詢的模擬：

?進(jìn)行Send(I1,(I2,N,W*))查詢時(shí)，先在ΛA中查詢表項(xiàng)(0,(U2,pw,N),r)，其中U2為實(shí)例I2對(duì)應(yīng)的用戶．如果存在該表項(xiàng)并且pw是I1和I2共享的口令，則AskPad3事件為真并停止模擬．

(4)

Game G4：G4利用2個(gè)私有的隨機(jī)預(yù)言H2和H3分別取代原來的公有預(yù)言H0和H1，使得X*,Y*,sk與pw,KC,KS完全獨(dú)立．為此按如下方式修改Send查詢的模擬：

?Send(Ci,Start)查詢按如下方式模擬：

返回(C,NC,X*)

?Send(Si,(C,NC,X*))查詢按如下方式模擬：

Y←gy,Y*←Y?H2(S,NS),

SkS←H3(C,S,X*,Y*),

返回(S,NS,Y*)

?Send(Ci,(S,NS,Y*))查詢按如下方式模擬：

SkC←H3(C,S,X*,Y*).

G4和G3是不可區(qū)分的，除非AskH4發(fā)生．

(5)

(6)

引理1 在G4中，Succ4和AskPad4的概率上界為：

Pr[Succ4]=1/2, Pr[AskPad4]≤qS/(2N).

(7)

證明本Game里，由于H2和H3都是攻擊者無法獲取的私有隨機(jī)預(yù)言，所以從攻擊者的角度看，會(huì)話密鑰是隨機(jī)分布的，與其它數(shù)據(jù)無關(guān)．故

Pr[Succ4]=1/2．

令FG表示被攻擊者A偽造并發(fā)送的數(shù)據(jù)集合，由于G2已經(jīng)避免了W*之間的碰撞(W*為X*或Y*)，且這些數(shù)據(jù)是隨機(jī)的，與pw無關(guān)，

其中U為C或S，N是隨機(jī)數(shù)；ΛA保存著攻擊者A所進(jìn)行的Hash查詢請(qǐng)求； #FG表示FG集合的元素個(gè)數(shù)．

如果在同一個(gè)會(huì)話中，A既偽裝客戶端，又偽裝服務(wù)器是沒有意義的，所以#FG不超過qS/2，引理1得證．

引理2 AskH4和AskH5的概率上界為：

Pr[AskH5]=Pr[AskH4],

(8)

(9)

其中t′≤t+2·qS·+3·．

證明G5和G4是不可區(qū)分的，故Pr[AskH5]=Pr[AskH4]．

AskH5事件為真，意味著A成功地猜測(cè)pw，并查詢隨機(jī)預(yù)言H1(C,S,X*,Y*,K,pw)，其中K=CDH(X,Y)=CDH(Φ,Ψ)×Φy×Ψx×gxy．因此只需查詢?chǔ)獺和進(jìn)行簡(jiǎn)單的運(yùn)算即可有效地求解CDH問題．故

綜合：由式(2)～(5)，可得

由式(6)～(9)，可得

Pr[AskPad3]≤Pr[AskPad4]+Pr[AskH4]≤

所以，

根據(jù)AKE優(yōu)勢(shì)的定義：

4 相關(guān)協(xié)議的對(duì)比

PARK等人[14]的協(xié)議和CHEN等人[4]的協(xié)議都是與本文所設(shè)計(jì)的POPKE相類似的協(xié)議，在協(xié)議的執(zhí)行過程中都采用了Hash函數(shù)和異或運(yùn)算確保協(xié)議的安全性．在比較協(xié)議的執(zhí)行效率時(shí)，只關(guān)注協(xié)議的通信輪次，用戶所進(jìn)行的Hash運(yùn)算次數(shù)，以及所進(jìn)行的異或運(yùn)算次數(shù)．3個(gè)協(xié)議之間的效率對(duì)比見表1.

表1 POPKE與同類協(xié)議的效率對(duì)比

由表1可見，POPKE所需的Hash計(jì)算、異或運(yùn)算以及通信輪次都比同類協(xié)議少，具有更高的執(zhí)行效率．更重要的是POPKE是其中唯一一個(gè)被形式化證明的協(xié)議，其可信度較高．

5 結(jié)論

基于口令的密鑰交換協(xié)議是密碼學(xué)界研究的熱點(diǎn)．如何設(shè)計(jì)安全的協(xié)議，如何分析協(xié)議的安全性，都是目前學(xué)者廣泛討論的問題．利用Hash函數(shù)和異或運(yùn)算構(gòu)造協(xié)議，是一種新的協(xié)議構(gòu)造方法．其優(yōu)點(diǎn)在于對(duì)計(jì)算設(shè)備的要求低，能在智能卡等計(jì)算能力較低的設(shè)備上進(jìn)行．但該方法還不夠成熟，某些構(gòu)造出來的協(xié)議易遭受離線字典攻擊．

本文克服了原有協(xié)議的安全缺陷，僅借助Hash函數(shù)和異或運(yùn)算構(gòu)造了一個(gè)簡(jiǎn)易、高效的密鑰交換協(xié)議:POPKE協(xié)議．在隨機(jī)預(yù)言模型下，該協(xié)議的安全性能緊致歸約到CDH問題上，從而證明POPKE協(xié)議具有語義安全和對(duì)抗離線字典攻擊的能力．與同類協(xié)議相比，POPKE協(xié)議需要更少的Hash運(yùn)算和更少的異或運(yùn)算，具有更高的執(zhí)行效率，更重要的是POPKE的安全性經(jīng)過了嚴(yán)格的形式化證明．

本文所提出帶認(rèn)證密鑰交換協(xié)議是一個(gè)兩輪的隱式認(rèn)證協(xié)議，不具備雙向認(rèn)證與密鑰確認(rèn)功能．然而，通過常規(guī)性構(gòu)造方法，增加一輪認(rèn)證報(bào)文的交換，就可立即獲得這兩種功能．隱式認(rèn)證協(xié)議已經(jīng)得到廣泛的認(rèn)同[5,10],并寫入了多個(gè)重要的國際標(biāo)準(zhǔn)中．從安全性分析的角度看，隱式認(rèn)證協(xié)議的安全性證明更加簡(jiǎn)潔；從應(yīng)用的角度看，雙向認(rèn)證與密鑰確認(rèn)往往可以在應(yīng)用層中實(shí)現(xiàn)，使用隱式認(rèn)證協(xié)議可簡(jiǎn)化底層協(xié)議的設(shè)計(jì)，提高系統(tǒng)效率．我們將帶密鑰確認(rèn)的三輪POPKE協(xié)議的安全性分析留做下一階段的工作，但重點(diǎn)不再是本文提及的語義安全與抗字典攻擊，而是本文沒有證明的前向安全、密鑰泄露冒充、無感知密鑰分享攻擊等.值得一提的是，即使加入第三輪認(rèn)證報(bào)文，相比PARK等人[14]的協(xié)議和CHEN等人[4]的協(xié)議，POPKE依然具有更好的執(zhí)行效率與通信效率．

[1] H?LBL M, WELZER T, BRUMEN B. Improvement of the Peyravian-Jeffries’s user authentication protocol and password change protocol[J]. Computer Communications, 2008, 31(10):1945-1951.

[2] MUNILLA J, PEINADO A. Security flaw of H?lbl et al.’s protocol[J]. Computer Communications, 2009, 32(3):736-739.

[3] MUNILLA J, PEINADO A. Off-line password-guessing attack to Peyravian-Jeffries’s remote user authentication protocol[J]. Computer Communications, 2006, 30(1):52-54.

[4] CHEN Y, SUN H, HUANG C, et al. Comments on two password based protocols[EB/OL]. (2008-09-24)[2009-10-08]. http://eprint.iacr.org/2008/400.pdf.

[5] ABDALLA M, POINTCHEVAL D. Simple password-based encrypted key exchange protocols[C]∥Proceedings of the Cryptographers’ Track at RSA Conference ’05 (CT-RSA ’05). Berlin: Springer-Verlag, 2005: 191-208.

[6] BELLARE M, POINTCHEVAL D, ROGAWAY P. Authenticated key exchange secure against dictionary attacks[C]∥Proceedings of Eurocrypt 2000. Berlin: Springer-Verlag, 2000: 139-155.

[7] BELLARE M, ROGAWAY P. The AuthA protocol for password-based authenticated key exchange[R]. California: University of California,2000.

[8] BELLOVIN S M, MERRITT M. Encrypted key exchange: Password protocols secure against dictionary attacks[C]∥Proceedings of IEEE Symposium on Security and Privacy. Los Alamitos, USA: IEEE Computer Society Press, 1992: 72-84.

[9] BOYKO V, MACKENZIE P, PATEL S. Provably secure password-authenticated key exchange using Diffie-Hellman[C]∥Proceedings of Eurocrypt 2000. Berlin: Springer-Verlag, 2000: 156-171.

[10] BRESSON E, CHEVASSUT O, POINTCHEVAL D. Security proofs for an efficient password-based key exchange[C]∥ Proceedings of the 10th ACM Conference on Computer and Communications Security (ACM CCS 2003). New York: ACM Press, 2003: 241-250.

[11] BELLARE M, ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocols[C]∥ Proceedings First Annual Conference on Computer and Communications Security (ACM CCS 1993). New York: ACM Press, 1993: 62-73.

[12] ABDALLA M, BRESSON E, CHEVASSUT O, et al. Password-based group key exchange in a constant number of rounds[C]∥Proceedings of the 9th International Workshop on Practice and Theory in Public Key Cryptography (PKC 2006). Berlin: Springer-Verlag, 2006: 427-442.

[13] SHOUP V. Sequences of games: A tool for taming complexity in security proofs[EB/OL]. (2006-01-18)[2009-10-08]. http://eprint.iacr.org/2004/332.

[14] PARK J H, YIM S J, CHANG J H. A secure remote user authentication scheme[C]∥Proceedings of the 3rd International Conference on Convergence and Hybrid Information Technology. Los Alamitos, USA: IEEE Computer Society, 2008: 369-373.

Keywords： password-based key exchange; semantic security; provable security; random oracle model; Diffie-Hellman assumption

【責(zé)任編輯 莊曉瓊】

EFFICIENTANDSEMANTICALLYSECUREPASSWORD-BASEDKEYEXCHANGEPROTOCOL

WANG Libin, PAN Jiaxin, MA Changshe

(School of Computer, South China Normal University, Guangzhou 510631, China)

An efficient and provably secure password-based key exchange protocol is proposed, using only hash function and XOR operator. The security of the protocol can be tightly reduced to the hardness of the computational Diffie-Hellman problem in random oracle model. Thus, the protocol is proved to be semantically secure against off-line dictionary attacks. Finally, compared with the related works, the protocol is more efficient with respect to computation and communication.

2009-11-09

國家自然科學(xué)基金資助項(xiàng)目(60703094)

王立斌(1972—)，男，廣東龍門人，博士，華南師范大學(xué)副教授，碩士生導(dǎo)師，主要研究方向：密碼學(xué)與網(wǎng)絡(luò)安全,Email:lbwang@scnu.edu.cn.

1000-5463(2010)02-0040-05

TP309

A