不同PKG環(huán)境下可證安全的基于身份AKA協(xié)議

夏 松 權(quán)建校 韓文報

①(解放軍信息工程大學(xué)信息工程學(xué)院 鄭州 450002)②(江南計算技術(shù)研究所 無錫 214083)③(解放軍電子工程學(xué)院 合肥 230037)

1 引言

Shamir[1]于1984年提出了基于身份密碼系統(tǒng)(Identity-Based Cryptograph, IBC)的概念。在IBC中，用戶的唯一身份標(biāo)識被用作用戶公鑰，有一個稱作PKG(Private Key Generator)的可信中心負(fù)責(zé)給每個用戶分發(fā)與其身份對應(yīng)的私鑰。自2001年Boneh和Franklin[2]使用雙線性對技術(shù)提出了第一個安全且實用的基于身份加密機制(Identity- Based Encryption, IBE)以來，大量使用雙線性對的基于身份密碼機制被提出。當(dāng)前，絕大部分基于身份認(rèn)證密鑰協(xié)商(Authenticated Key Agreement, AKA)協(xié)議都要求參與協(xié)議的用戶是在同一個PKG環(huán)境下。在實際中，一個部門或區(qū)域下的用戶由同一個PKG為其分發(fā)私鑰，而不同部門或區(qū)域間的用戶也會有安全通信的需求，這就要求在不同PKG環(huán)境下的用戶也能夠協(xié)商達成一個共享的會話密鑰。Chen和Kulda[3]在2003年第一次提出了在不同PKG環(huán)境下的用戶之間實現(xiàn)AKA協(xié)議的思想。2005年McCullagh和Barreto[4]提出一個可以在不同PKG環(huán)境下的用戶之間實現(xiàn)的AKA協(xié)議 (簡記為MB協(xié)議)，但隨后被指出無法抵抗KCI(Key Compromise Impersonate)攻擊。

在以往的協(xié)議安全性證明中，為了在模擬游戲中實現(xiàn)敵手的判定性詢問，設(shè)計的協(xié)議多是基于gapDH(Diffie-Hellman)困難性問題，然而gap DH困難性假設(shè)是一個比較強的假設(shè)。在2008年的歐密會上，Cash，Kiltz和Shoup[5]提出了twin DH問題，它能夠在容許對問題進行判定性詢問的情況下保持問題的困難性，而這個性質(zhì)并不是一般的DH問題所具備的。其中實現(xiàn)對twin DH問題進行判定性詢問的核心方法是“trapdoor test”技術(shù)，它能夠在不知道相關(guān)離散對數(shù)的情況下實現(xiàn)對twin DH問題的判定性詢問。近期黃海和曹珍富[6]結(jié)合twin DH問題提出了一個新的基于身份AKA協(xié)議，而且利用“trapdoor test”技術(shù)實現(xiàn)了在eCK(extended Canetti-Krawczyk)模型[7?9]下的嚴(yán)格安全性證明。受這些已有結(jié)論的啟發(fā)，結(jié)合twin DH問題本文提出了一個新的在不同PKG環(huán)境下的用戶之間實現(xiàn)的AKA協(xié)議，并且利用trapdoor test技術(shù)在模擬游戲中實現(xiàn)判定性詢問，在目前最強的eCK模型中將新協(xié)議的安全性規(guī)約到標(biāo)準(zhǔn)的CDH(Computational DH)和BDH(Bilinear DH) 假設(shè)。

本文第2節(jié)介紹背景知識；第3節(jié)描述新協(xié)議；第4節(jié)在eCK模型下對新協(xié)議進行安全性證明；第5節(jié)進行性能評估；最后總結(jié)全文。

2 預(yù)備知識

2.1 相關(guān)密碼組件及關(guān)鍵技術(shù)

雙線性映射 如果G是階為q的加法循環(huán)群，GT為同階的乘法循環(huán)群，P是G的任一生成元，雙線性映射: G×G→GT滿足以下性質(zhì)：

(3)可計算性：對?Q, R∈G，存在一個有效的多項式時間算法來計算(Q, R)。

困難性假設(shè) CDH假設(shè)：對未知的x, y∈Zq，給定X=xP和Y=yP，計算Z=xyP是困難的；BDH假設(shè)：對未知的x, y, z∈Zq，給定X=xP，Y=yP和W=wP，計算Z=e(P, P)wxy是困難的。

定理1(“trapdoor test”技術(shù)[5,6]) 設(shè)e: G×G→GT是一個雙線性對，其中G，GT是階為大素數(shù)q的循環(huán)群，P是G的一個生成元。假設(shè)W1，r，s是相互獨立的隨機變量，其中W1∈G，r，s是Zq上均勻分布的，定義W2=sP?rW1。假設(shè)X，Y是取值于G的隨機變量，Z1，Z2是取值于GT的隨機變量，并且Z1，Z2都是W1，W2的函數(shù)，則有：

(1)W2在G上是均勻分布的；

(2)W1，W2相互獨立；

(3)如果W1=w1P, W2=w2P ，那么

式(1)不成立時，式(2)成立的概率至多是1/q，且式

(2)成立時則式(1)一定成立。

2.2 安全模型

本節(jié)簡要描述適用于基于身份AKA協(xié)議的擴展后的eCK模型，具體介紹參見文獻[7-9]。

協(xié)議參與者 協(xié)議的每一個參與者被視為一個概率多項式時間的圖靈機，每個參與者有一個身份IDi，并且每個參與者可以并行地執(zhí)行多個會話實例。記參與者IDi與參與者IDj的第s個實例為。

通過一個在模擬者S和攻擊者M之間的游戲來定義AKA協(xié)議的安全性，攻擊者M是一個概率多項式時間的圖靈機，并且控制整個通信網(wǎng)絡(luò)。通過給予敵手oracle詢問來模擬敵手的攻擊能力：

Long-term key reveal(IDi)：M得到協(xié)議參與者IDi的長期密鑰；

PKG Long-term key reveal(PKGi)：M得到PKGi的主密鑰；

Establish Party(IDi)：M可以代表IDi通過對應(yīng)的PKG注冊一個合法用戶，M得到IDi的長期密鑰并且完全控制IDi；

最后，M輸出一個對b的判斷(記為b')。若b'＝b，那么稱M贏得了此游戲。記Σ為一個AKA協(xié)議，定義M攻破AKA協(xié)議Σ的優(yōu)勢為=，其中k為安全參數(shù)。

(a)Long-term Key Reveal(IDi) 和 Ephemeral-term Key Reveal()；

(b)Long-term Key Reveal(IDi) 和 Ephemeral-term Key Reveal()。

(a)Long-term Key Reveal(IDi) 和 Ephemeral-term Key Reveal()；

(b)Long-term Key Reveal(IDi)。

定義3 如果協(xié)議Σ滿足以下條件，稱協(xié)議Σ是安全的AKA協(xié)議：

3 不同PKG環(huán)境下的基于身份AKA協(xié)議

本節(jié)給出一種新的在不同PKG環(huán)境下的基于身份AKA協(xié)議，新協(xié)議由系統(tǒng)建立、私鑰生成和密鑰協(xié)商3個階段組成。

系統(tǒng)建立：G是階為大素數(shù)q的加法循環(huán)群，GT為同階的乘法循環(huán)群，P為G的一個生成元，G*為G中的非用戶身份元素集，k為系統(tǒng)的安全參數(shù)，λ為臨時密鑰的長度，e?: G×G→GT為雙線性映射。Hash函數(shù)H1, H2:{0,1}*→G*，H3:{0,1}λ×G0→，H:{0,1}*→{0,1}k。隨機選取u，v∈Zq，令U=uP，V=vP。 設(shè)置u，v分別為 PKG1，PKG2的主密鑰，U，V分別為 PKG1， PKG2的公鑰。分別以C1，C2表示PKG1，PKG2的用戶集。

私鑰生成：對用戶A∈C1，對應(yīng)的IDA∈{0,1}*，PKG1計算 QA1=H1(IDA)，QA2=H2(IDA) 及相應(yīng)的私鑰dA1=uQA1，dA2=uQA2給A。對用戶B∈C2，對應(yīng)的IDB∈{0,1}*，PKG2計算 QB1=H1(IDB)，QB2=H2(IDB)及相應(yīng)的私鑰dB1=vQB1，dB2=vQB2給B。分別記Apri=dA1，Bpri=dB1。

密鑰協(xié)商：用戶A和B分別隨機選取一個臨時密鑰，分別記為x，y∈R{0,1}λ，然后分別計算x=H3(, Apri)，y=H3(, Bpri)及相應(yīng)的臨時公鑰X=xP，Y=yP，隨即分別銷毀x，y。然后，A和B相互交換協(xié)議數(shù)據(jù)X和Y，記sid=(X, Y,A, B)。消息傳遞完成后，A和B分別執(zhí)行如下步驟：

4 安全性證明

本節(jié)在第2.2節(jié)定義的安全模型下證明新協(xié)議的安全性。

定理2 若Hash函數(shù)被模型化為隨機預(yù)言機，且CDH假設(shè)及BDH假設(shè)成立，則新協(xié)議是一個安全的AKA協(xié)議。

證明 假設(shè)k是系統(tǒng)的安全參數(shù)，攻擊者M激活至多n(k)個誠實用戶，每個用戶至多激活s(k)個并行會話。假設(shè)M在第2.2節(jié)的模型中能以不可忽略的優(yōu)勢得到測試會話的會話密鑰，由于H是隨機預(yù)言機，因此在M進行test詢問后，只有下面兩種情況區(qū)分會話密鑰和隨機數(shù)。

情況1 偽造攻擊：在攻擊的某一時刻，M向H詢問了(Z1, Z2, Z3,X, Y, A, B)，因H是隨機預(yù)言機，所以此時M自己計算了Z1, Z2, Z3。

情況2 密鑰復(fù)制攻擊：M強迫一個非匹配會話與測試會話具有相同的會話密鑰。這樣M可以通過簡單的請求這個非匹配會話，來得到測試會話密鑰。

對于情況2，因為H為隨機預(yù)言機，所以不同的會話中H的輸入不可能相同，也就不會得到相同的會話密鑰。因此M通過密鑰復(fù)制攻擊成功的概率可忽略不計。下面主要分析情況1，根據(jù)新鮮會話的定義，從兩種情況來考慮：情況1.1不存在測試會話的匹配會話；情況1.2存在測試會話的匹配會話。

4.1 不存在測試會話的匹配會話

情況1.1可分為下面兩種情況：

情況1.1.1：在某一時刻，M得到A的長期密鑰。不失一般性，我們假設(shè)A∈C1。

如果存在M以不可忽略的優(yōu)勢ε(k)贏得游戲，那么我們可以利用M構(gòu)造一個算法攻擊BDH假設(shè)。即給模擬者S一個BDH實例：V=vP, Z=zP,W=wP，要求S利用M計算BDH(V, Z, W)=e(P, P)vzw。S隨機選擇U(U∈G)作為PKG1的公鑰，令V作為PKG2的公鑰。S至少以1/n(k)2的概率猜測測試會話是在A和B(B∈C2)之間進行，又以至少1/s(k)的概率猜測M會選擇A的會話s作為測試會話。S隨機選取s, r∈Zq，設(shè)置B的公鑰為QB1=W1=W ，QB2=W2=sP?rW ，為其它n(k)?1個用戶(包括A)隨機分配公/私鑰對。如果擁有M激活用戶的長期密鑰，S根據(jù)協(xié)議流程執(zhí)行。因S不知道B的長期密鑰，所以當(dāng)M向S發(fā)出關(guān)于B的詢問請求時，S的模擬行為如下：

H1(IDi)：S記錄一個最初記錄為空的列表，記錄的格式為((IDi,li1,Qi1)，

(1)若IDi在列表中，S回答相應(yīng)的Qi1；

H2(IDi)：S記錄一個最初記錄為空的列表，記錄的格式為((IDi,li1,Qi1)，

(1)若IDi在列表中，S回答相應(yīng)的Qi2；

(2)若IDi不在列表中，如果IDi=B，S隨機選擇r, s∈Zq，令QB1=W1=W,QB2=W2=sP ?rW，添加(B,null,QB2)到，同時添加(B,null,Q)到；否則，S隨機選擇l,l∈Z，計算

B1i1i2qQi1=li1P, Qi2=li2P ，添加(IDi,li2,Qi2)到，并且添加(IDi,li1,Qi1)到。

Establish Party(IDi)：S代替M注冊一個用戶IDi，即S向H1, H2詢問IDi。若IDi∈C1，返回dIDi1=li1U, dIDi2=li2U 給敵手，否則IDi∈C2，返回dIDi1=li1V, dIDi2=li2V 給敵手。

Long-term Key Reveal(IDi)：如果IDi=B，S退出游戲(事件E1)；否則返回相應(yīng)的私鑰。

(1)如果IDi=A并且是測試會話，那么S返回Z給M；

除臭規(guī)?？傦L(fēng)量Q為13 000 m3/h，共計2套處理系統(tǒng)，其中，一期設(shè)計風(fēng)量9 000 m3/h，二期設(shè)計風(fēng)量4 000 m3/h，除臭工藝采用生物土壤濾池除臭技術(shù)。首先將O池中的惡臭氣體密封加蓋，防止惡臭氣體外溢，采用不銹鋼收集風(fēng)管進行收集，通過引風(fēng)機將惡臭氣體引至生物土壤濾池進行處理，處理后的氣體無組織達標(biāo)排放。

(2)如果IDi=B，設(shè)IDj=C, m=X ，S隨機選擇y∈Zq，把Y=yP返還給M，S在Hlist中查找

若式(3)成立，則由定理1有

S查看

如果(X, Y, C, B)在列表Hlist中，S計算詢問中的方法相同，S根據(jù)定理1驗證是否正確生成，并通過計算來驗證是否正確生成。若經(jīng)驗證都是正確生成的，那么S返回列表Llist中的對應(yīng)值SK并添加到列表listH中。否則，S隨機隨機選擇作為返回值，并添加到列表listH中。

否則，S隨機隨機選擇{0,1}kh∈作為返回值，并添加到列表listH中。

在這種攻擊類型中，若S未退出游戲，則M以不可忽略的概率攻擊成功并向H詢問過關(guān)于測試會話的7元組，其中。為了解決BDH難題，S隨機選擇Hlist中的一個記錄IDi,IDj,h)，對于進行如下計算：

這樣S成功解決了BDH難題，與BDH假設(shè)矛盾。

令E5代表M贏得游戲，即有。若S猜中測試會話s，且情況1.1.1發(fā)生，則事件E1～E4都不發(fā)生，故p(k)/(s(k) n(k)2)，其中p(k)是情況1.1.1發(fā)生的概11率。令E7代表S獲得正確的和，則有Pr[E7]≥1/t(k)，其中t(k)為攻擊者詢問H的次數(shù)。那么S成功解決BDH問題的優(yōu)勢為

情況1.1.2：M始終沒有得到A的長期密鑰。

如果存在M以不可忽略的優(yōu)勢ε(k)贏得游戲，那么我們可以利用M構(gòu)造一個算法攻擊BDH假設(shè)。給模擬者S一個BDH實例：U=uP, Z=zP,W=wP，要求S利用M計算BDH(U, Z, W)=e(P, P)uzw。S取U作為PKG1的公鑰，隨機選擇V (V∈G)作為PKG2的公鑰。S至少以1/n(k)2的概率猜測測試會話是在A (A∈C1)和B(B∈C2)之間進行，又以至少1/s(k)的概率猜測M會選擇A的會話s?作為測試會話。S隨機選取s, r∈Zq，設(shè)置A的公鑰為QA1=W1=W ，QA2=W2=sP?rW ，隨機選取QB1，QB2作為B的公鑰，為其它n(k)?2個用戶隨機分配公/私鑰對。下面描述S區(qū)別于情況1.1.1的模擬行為：

H1(IDi) ：如果IDi=A，S隨機選擇r, s∈Zq，令QA1=W1=W,QA2=W2=sP?rW ，添加(A,null,QA1)到，相應(yīng)添加(A,null,QA2)到；如果IDi=B，S隨機選擇QB1，QB2作為B的公鑰，添加(B,null,QB1)到，同時添加(B,null,QB2)到。

H2(IDi)：模擬同H1(IDi)。

在這種攻擊類型中，若S未退出游戲，則M以不可忽略的概率攻擊成功并向H詢問過關(guān)于測試會話的7元組，其中為了解決BDH難題，S隨機選擇Hlist中的一個記錄(,,,X, Y,IDi,IDj,h)，對于,進行如下計算：其中Y是由M選擇的，X是S選擇的，因此S知道x。S隨機的選擇，然后計算：

這樣S成功解決了BDH難題，與BDH假設(shè)矛盾。

類似于情況1.1.1中的分析，可得S成功解決BDH問題的優(yōu)勢為?t(k)]，其中p2(k)是情況1.1.2發(fā)生的概率，t(k)為攻擊者詢問H的次數(shù)。

4.2 存在測試會話的匹配會話

根據(jù)新鮮會話的定義，情況1.2可分為下面4種情況：

情況1.2.1：攻擊者得到A，B的長期密鑰。

如果存在攻擊者M以不可忽略的優(yōu)勢ε(k)贏得游戲，那么我們可以利用M構(gòu)造一個算法攻擊CDH假設(shè)。給模擬者S一個CDH實例：X=xP,Y=yP(X, Y∈G)，要求S利用M計算CDH(X, Y)=xyP 。S至少以2/s(k)2的概率選中兩個會話，其中一個為測試會話，另一個為對應(yīng)的匹配會話。設(shè)置測試會話發(fā)起者A的臨時密鑰為X，響應(yīng)者B的臨時密鑰為Y。如果M攻擊成功，那么攻擊者肯定向H詢問過關(guān)于測試會話的7元組所以S輸出CDH(X, Y)=。這樣S就解決了CDH難題。這里S成功解決CDH問題的優(yōu)勢為，其中p3(k)是情況1.2.1發(fā)生的概率，t(k)為攻擊者詢問H的次數(shù)。

情況1.2.2：攻擊者得到A，B的臨時密鑰。

情況1.2.3：攻擊者得到A的長期密鑰，B的臨時密鑰。

情況1.2.4：攻擊者得到A的臨時密鑰，B的長期密鑰。

對情況1.2.3和情況1.2.4這兩種情況，S的模擬行為與情況1.1.1的情況類似，這里不再贅述。

綜合上述分析，如果存在攻擊者M以不可忽略的優(yōu)勢ε(k)贏得游戲，在情況1.1.1，情況1.1.2，情況1.2.3和情況1.2.4這4種情況中，模擬者S解決BDH難題的優(yōu)勢為其中p4(k)，p5(k)分別為情況1.2.3，情況1.2.4發(fā)生的概率。在情況1.2.1中，S解決CDH難題的優(yōu)勢為

因此，若攻擊者M在上述任一情況下能以不可忽略的優(yōu)勢對協(xié)議攻擊成功，那么我們就可以利用M以不可忽略的優(yōu)勢來解決BDH或CDH難題。這與協(xié)議所基于的安全假設(shè)相矛盾。所以新協(xié)議滿足定義3中的條件(2)。若協(xié)議參與雙方的對話是匹配的，這意味著他們正確地收到了對方發(fā)來的協(xié)議消息，那么他們能夠計算得到相同的會話密鑰，且該密鑰均勻分布于會話密鑰空間，因此定義3中的條件(1)也是滿足的。所以新協(xié)議是一個安全的AKA協(xié)議。

5 性能評估

Chow和Choo利用挑戰(zhàn)-響應(yīng)簽名技術(shù)提出一種新的基于身份AKA協(xié)議[10]，用CC-1協(xié)議和CC-2協(xié)議分別表示文獻[10]中的第1個和第2個協(xié)議?？紤]到MB協(xié)議[4]，CC-1協(xié)議[10]和CC-2協(xié)議[10]的高效性能，文獻[6]中的協(xié)議在安全方面的優(yōu)勢，本節(jié)將新協(xié)議與這4個協(xié)議進行安全性能、使用效率和適用范圍方面的比較，見表1。由于各協(xié)議都滿足基本的安全屬性，在此僅考慮完善前向安全(p-FS)，PKG前向安全(PKG-FS)，抗密鑰泄露偽裝攻擊(KCI)和抗臨時密鑰泄露攻擊(EKCI)?！啊獭北硎緷M足屬性，“×”表示不滿足屬性。在比較使用效率時，用P表示雙線性對運算，E表示G中的指數(shù)運算，T表示GT中的指數(shù)運算，統(tǒng)計內(nèi)容為協(xié)議成功運行一次的單方運算消耗。在比較協(xié)議適用范圍時，“√”表示該協(xié)議能被應(yīng)用在不同PKG環(huán)境中，“×”表示不能。

6 結(jié)束語

本文針對不同PKG環(huán)境提出了一種全新的基于身份AKA協(xié)議。利用Cash等人在2008年歐密會上提出的trapdoor test技術(shù)在eCK模型下給出了嚴(yán)格的形式化安全證明。通過比較可見，新協(xié)議同時具有安全性和適用性上的優(yōu)勢。如何進一步提高協(xié)議的執(zhí)行效率是我們下一步要研究的工作。

表1 基于身份AKA協(xié)議的性能比較

[1] Shamir A. Identity based cryptosystems and signature schemes[C]. CRYPTO’84, Santa Barbara, California, USA,August 19-22, 1984, LNCS 0196: 47-53.

[2] Boneh D and Franklin M. Identity based encryption from the Weil pairing [C]. CRYPTO’01, Santa Barbara, California,USA, August 19-23, 2001, LNCS 2139: 213-229.

[3] Chen L and Kudla C. Identity based authenticated key agreement protocols from pairing[C]. 16th IEEE Security Foundations Workshop, Los Alamitos, CA, USA, June 30-July 2, 2003: 219-233.

[4] McCullagh N and Barreto P S L M. A new two-party identity-based authenticated key agreement[C]. CT-RSA 2005, San Francisco, CA, USA, February 14-18, 2005, LNCS 3376: 262-274.

[5] Cash D, Kiltz E, and Shoup V. The twin diffie-hellman problem and applications[C]. EUROCRYPT2008, Istanbul,Turkey, April 13-17, 2008, LNCS 4965: 127-145.

[6] Huang Hai and Cao Zhen-fu. An ID-based authenticated key exchange protocol based on bilinear Diffie-Hellman problem[C]. ASIACCS 2009, Sydney, Australia, March 10-12,2009: 363-368.

[7] Canetti R and Krawczyk H. Analysis of key-exchange protocols and their use for building secure channels[C].EUROCRYPT 2001, Innsbruck, Austria, May 6-10, 2001,LNCS 2045: 453-474.

[8] LaMacchia B, Lauter K, and Mityagin A. Stronger security of authenticated key exchange[C]. ProvSec 2007, Wollongong,Australia, October 31 - November 2, 2007, LNCS 4784: 1-16.

[9] Ustaoglu B. Obtaining a secure and effcient key agreement protocol from (H)MQV and NAXOS[J]. Designs, Codes and Cryptography, 2008, 46(3): 329-342.

[10] Chow S S M and Choo K R. Strongly-secure identity-based key agreement and anonymous extension. Information Security, Volume 4779/2007, Springer Berlin Heidelberg,203-220, 2007. Cryptology ePrint Archive, Report 2007/018.Full version of this paper (2007).