UC安全的動(dòng)態(tài)群組密鑰協(xié)商協(xié)議設(shè)計(jì)與分析*

楊春堯,陸正福,李 軍

(1.成都衛(wèi)士通信息產(chǎn)業(yè)股份有限公司,四川成都610041;2.云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,云南昆明6500091)

UC安全的動(dòng)態(tài)群組密鑰協(xié)商協(xié)議設(shè)計(jì)與分析*

楊春堯1,陸正福2,李 軍1

(1.成都衛(wèi)士通信息產(chǎn)業(yè)股份有限公司,四川成都610041;2.云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,云南昆明6500091)

針對(duì)以往群組密鑰協(xié)商限于孤立模型下討論的問題,基于m叉樹的判定Diffie-Hellman假設(shè),使用通用可組合安全(UC安全)理論設(shè)計(jì)了一個(gè)群組密鑰協(xié)商協(xié)議,并根據(jù)協(xié)議需要滿足的安全目標(biāo),形式化地建立了協(xié)議的安全模型,通過對(duì)協(xié)議安全模塊的設(shè)計(jì)和實(shí)現(xiàn),證明了該協(xié)議滿足UC安全性質(zhì)。和同類協(xié)議相比,降低了密鑰更新所需要的通信和計(jì)算開銷,同時(shí)支持群組成員的動(dòng)態(tài)加入和退出。

群組密鑰協(xié)商 UC安全 通信安全

0 引 言

群組密鑰協(xié)商(GKA,Group Key Agreement)協(xié)議在群組安全通信中具有重要的作用,因?yàn)樗鼌f(xié)商得到的密鑰具有臨時(shí)性,從而限制了密鑰泄露事件帶來的問題,常常被用于密鑰泄露可能性高、復(fù)雜的環(huán)境中保證安全通信。

目前應(yīng)用領(lǐng)域已經(jīng)提出了一些GKA協(xié)議[1-2],這些協(xié)議的安全性分析都是在孤立模型中進(jìn)行的,缺乏對(duì)并發(fā)環(huán)境下協(xié)議的安全性討論,使得協(xié)議在并發(fā)運(yùn)行時(shí)出現(xiàn)了許多設(shè)計(jì)時(shí)沒有考慮到的缺陷。例如著名的Atenises-Steiner-Tsudik協(xié)議在提出之后3年才被發(fā)現(xiàn)存在并行會(huì)話攻擊的漏洞[3]。究其原因,一方面固然是GKA協(xié)議的構(gòu)造比較復(fù)雜、所需要考慮的安全因素比較多,但一個(gè)更為重要的原因是缺乏精準(zhǔn)的安全模型和分析這些模型的理論工具。

為此,Canetti提出了通用可組合安全(UC安全,Universally Composable Security)理論[4]。根據(jù)UC安全理論,如果一個(gè)安全協(xié)議滿足UC安全框架下的某些安全性質(zhì),則該協(xié)議和其他任何協(xié)議并發(fā)運(yùn)行仍然能夠保持這些安全性質(zhì)。

文獻(xiàn)[5]根據(jù)UC安全理論構(gòu)造了一個(gè)GKA協(xié)議,該協(xié)議使用了簽名理想函數(shù)作為參與者的身份認(rèn)證接口,得到靜態(tài)模型下基于二叉樹的UC安全群組密鑰交換協(xié)議(LTDH協(xié)議),但參與者之間的密鑰關(guān)系采用的是線性二叉樹,隨著參與方人數(shù)增加,會(huì)使二叉樹嚴(yán)重失去平衡,增加了下游結(jié)點(diǎn)的計(jì)算負(fù)擔(dān),導(dǎo)致協(xié)議的可擴(kuò)展性較差。

文中在此基礎(chǔ)上,采用了基于m叉樹數(shù)據(jù)結(jié)構(gòu)[6]的GKA協(xié)議,通過改變參數(shù)m來平衡成員關(guān)系樹,較好地降低了關(guān)系樹的高度。同時(shí)文中在UC理想函數(shù)中增加了群組成員的動(dòng)態(tài)加入/退出的理想函數(shù),并設(shè)計(jì)了一個(gè)子協(xié)議安全實(shí)現(xiàn)了該理想函數(shù),最后通過UC安全組合定理,證明了文中所設(shè)計(jì)的群組密鑰交換協(xié)議(m-TGDH協(xié)議)具有UC安全性質(zhì),其計(jì)算和通信效率好于LTDH協(xié)議。

1 理論基礎(chǔ)

定義1(UC相似) 設(shè)φ,φ使兩個(gè)協(xié)議,k為復(fù)雜度參數(shù),用PPT表示所有概率多項(xiàng)式時(shí)間算法的集合,如果對(duì)任何攻擊者A∈PPT都存在理想攻擊者S∈PPT,使得對(duì)任何環(huán)境Z∈PPT和任何輸入u其輸出序列都是多項(xiàng)式時(shí)間不可區(qū)分的,即對(duì)任何判決器D∈PPT的優(yōu)勢(shì)函數(shù):

是關(guān)于k的一個(gè)速降函數(shù),則稱ψ與φ相似,記作ψ→UCφ。

定義2(協(xié)議獨(dú)立性) 若協(xié)議ψ1的任何實(shí)例既不顯式地、也不隱式地(例如,通過某則子程序或某個(gè)高層控制程序)訪問協(xié)議ψ2的任何運(yùn)行實(shí)例,同時(shí)ψ2對(duì)ψ1也有同樣的性質(zhì),則協(xié)議ψ1和ψ2稱為相互獨(dú)立。若協(xié)議ψ與自身的任何運(yùn)行實(shí)例之間從來不發(fā)生顯式訪問,也不發(fā)生隱式訪問,則稱協(xié)議ψ是自獨(dú)立(subroutine-respective)的。

引理1(UC組合定理) 協(xié)議π(φ)是基于子協(xié)議φ的復(fù)合協(xié)議,協(xié)議φ和協(xié)議ψ都是自獨(dú)立的,并且φ與ψ相互獨(dú)立,若ψ→UCφ,則π(ψ/ φ)→UCπ(φ),其中π(ψ/φ)表示子協(xié)議φ和ψ組合后的復(fù)合協(xié)議[4]。

2 GKA協(xié)議的理想函數(shù)

UC安全模型下的協(xié)議的安全目標(biāo)是由理想函數(shù)所刻畫的,因此首先要定義GKA協(xié)議理想函數(shù)FGKA。設(shè)k為復(fù)雜度參數(shù),P={M1,M2,…,Mn}為參與者集合,每個(gè)特定的FGKA實(shí)例都由一個(gè)唯一的sid標(biāo)識(shí),同時(shí),該實(shí)例中對(duì)外部事務(wù)的請(qǐng)求標(biāo)識(shí)為ssid。在通信過程中,假定群組成員的廣播通信滿足可靠性,則協(xié)議的理想函數(shù)描述如下。

1)初始化階段:啟動(dòng)環(huán)境Z,當(dāng)理想函數(shù)FGKA從參與者M(jìn)i收到消息(gkassion,sid,ssid,P,Mi)后,若該消息是第一次收到,則記錄該消息,并將其轉(zhuǎn)發(fā)給理想攻擊者S,如果此時(shí)FGKA已收到|P|-1條此類消息,就將消息(Ready,sid,ssid,P)存儲(chǔ)起來,同時(shí)轉(zhuǎn)發(fā)該消息給理想攻擊者S。

該階段中FGKA刻畫了理想攻擊者S具有控制通信信道的攻擊能力,因而可以截獲FGKA發(fā)送給參與者的消息。

2)成員關(guān)系更新階段:Mi向FGKA發(fā)送請(qǐng)求加入群組G的消息(Join,sid,Mi),FGKA把該消息轉(zhuǎn)發(fā)給理想攻擊者S,然后等待S響應(yīng),如果Mi獲得S響應(yīng),FGKA就把Mi加入到群組中。如果參與者M(jìn)i向FGKA發(fā)送請(qǐng)求退出群組G的消息(Remove,sid,Mi),則FGKA把該消息轉(zhuǎn)發(fā)給理想攻擊者S,但不等S響應(yīng),FGKA直接將Mi從群組中刪除。

3)密鑰生成階段:當(dāng)理想函數(shù)FGKA從理想攻擊者S收到消息(ok,sid,ssid,P)后,檢查是否存在消息(Ready,sid,ssid,P),若存在該消息,則進(jìn)行如下操作:

①若參與者集合P中任何一個(gè)參與者M(jìn)i都沒有被理想攻擊者完全控制,那么由FGKA生成群組會(huì)話密鑰K←{0,1}k,保存消息:(SessionKey,sid,ssid,P,K)。

②若有某個(gè)參與者完全被理想攻擊者控制,那么FGKA就等待S發(fā)送消息,接收到后保存為(SessionKey,sid,ssid,P,K)。

4)密鑰廣播階段:當(dāng)收到S發(fā)送的消息(Delivery,sid,ssid,Mi)時(shí),FGKA檢查是否存在消息(SessionKey,sid,ssid,P,K),同時(shí)檢查Mi是否屬于P的成員,如果兩個(gè)條件都滿足,由FGKA向Mi發(fā)送消息(SessionKey,sid,ssid,P,K),如果有一個(gè)不符合,則忽略該消息。

安全地實(shí)現(xiàn)理想函數(shù)是構(gòu)造UC安全的群組密鑰協(xié)商協(xié)議的關(guān)鍵。下面文中將構(gòu)造實(shí)現(xiàn)FGKA的安全協(xié)議m-TGDH。

3 理想函數(shù)FGKA的安全實(shí)現(xiàn)

3.1 m-TGDH協(xié)議的模塊化設(shè)計(jì)

對(duì)理想函數(shù)FGKA進(jìn)行模塊化設(shè)計(jì)可以簡(jiǎn)化協(xié)議的實(shí)現(xiàn),文中對(duì)安全協(xié)議m-TGDH的實(shí)現(xiàn)分為三個(gè)模塊(如圖1所示)。

圖1 GKA協(xié)議的UC組合模型Fig.1 UC Security model of GKA protocol

文中安全實(shí)現(xiàn)FGKA的思路是:首先構(gòu)造一個(gè)安全實(shí)現(xiàn)簽名理想函數(shù)Fsig的協(xié)議πsig;然后再構(gòu)造一個(gè)安全實(shí)現(xiàn)群組成員關(guān)系理想函數(shù)Fset的協(xié)議πset;最后通過UC安全組合定理,在混合模型(Fsig,Fset, Fagent)上構(gòu)造協(xié)議m-TGDH,證明協(xié)議在混合模型下安全實(shí)現(xiàn)了FGKA。

Fsig是文獻(xiàn)[7]中提出具有UC安全性質(zhì)的數(shù)字簽名方案,用于對(duì)參與者的身份認(rèn)證和抗消息偽造。

Fset理想函數(shù)是對(duì)群組成員加入和退出群組的一個(gè)抽象。

模塊Fagent是用于描述用于提供在線認(rèn)證功能但通信受限的理想函數(shù)。在文中的協(xié)議中,Mi能夠使用該理想函數(shù)向CA機(jī)構(gòu)提供Mi的公私鑰對(duì)的合法性證明。

3.2 安全實(shí)現(xiàn)理想函數(shù)FGKA的協(xié)議形式化描述3.2.1 協(xié)議πsig的形式化描述

引理2設(shè)Sig=(gen,sig,ver)是能夠抵抗選擇密文攻擊的簽名方案,則在真實(shí)環(huán)境下,該協(xié)議對(duì)于靜態(tài)攻擊者可以安全實(shí)現(xiàn)Fsig,當(dāng)且僅當(dāng)Sig能抵抗選擇密文攻擊[7]。

由于可以抵抗選擇密文攻擊的簽名方案容易得到(例如經(jīng)過Fiat-Shamir變換得到的簽名方案),所以由引理2可以構(gòu)造安全實(shí)現(xiàn)理想函數(shù)Fsig。

3.2.2 協(xié)議πset的形式化描述

根據(jù)理想函數(shù)Fset的語(yǔ)義接口,文中將安全實(shí)現(xiàn)Fset的協(xié)議分再為兩個(gè)子協(xié)議:成員加入子協(xié)議πset_J和成員離開子協(xié)議πset_R。

假設(shè)在t時(shí)刻,所有成員維護(hù)具有相同結(jié)構(gòu)的m叉樹。在這棵m叉樹中每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)一個(gè)組成員Mi,hi為成員Mi在m叉樹中的高度。在這棵m叉樹中,首先由該組的第一個(gè)成員建立并選擇具體的m叉樹,并產(chǎn)生群組密鑰。每個(gè)結(jié)點(diǎn)＜l,v＞有兩個(gè)密鑰:一個(gè)私有密鑰K＜l,v＞和一個(gè)輔助密鑰BK＜l,v＞,二者關(guān)系為:BK＜l,v＞=f(K＜l,v＞),其中f(k)≡gk(modp),g和p的取值來源于Diffie-Hellman協(xié)議。廣播BK＜l,v＞,葉子結(jié)點(diǎn)密鑰由Mi隨機(jī)產(chǎn)生。

(1)成員加入?yún)f(xié)議πset_J的形式化描述

假設(shè)動(dòng)態(tài)群組成員{M1,M2,…,MN},現(xiàn)MN+1請(qǐng)求加入群組,則協(xié)議的形式化描述如下:

1)MN+1向群組發(fā)送請(qǐng)求加入的消息(Jion,sid,P,Mi||ssid||Cert#MN+1)和其輔助密鑰給{M1,M2,…,MN}。

2){M1,M2,…,MN}使用證書Cert#MN+1對(duì)MN+1的身份進(jìn)行認(rèn)證,若所有成員認(rèn)證通過,則表示接受,負(fù)責(zé)表示拒絕。如果拒絕則停止該事務(wù),否則進(jìn)入下一步。

3)每個(gè)組成員調(diào)用以下算法更新m叉樹:

①如果任取樹的任意內(nèi)部節(jié)點(diǎn)(l,v),度為TD (l,v)=m,按照層級(jí)遍歷算法搜索深度最大且編號(hào)最小的的中間結(jié)點(diǎn)＜l,v＞,創(chuàng)建一個(gè)中間結(jié)點(diǎn)編號(hào)為＜l+1,mv＞,原來結(jié)點(diǎn)編號(hào)為＜l+1,mv＞的葉子結(jié)點(diǎn)變?yōu)椋糽+2,mv2＞,新加入的結(jié)點(diǎn)變?yōu)椋糽+2,mv2+1＞,否則轉(zhuǎn)下一步。

②按照層次遍歷算法搜索深度最大且編號(hào)最小且TD(l,v)＜m的中間結(jié)點(diǎn)＜l,v＞與深度最大且編號(hào)最小葉子結(jié)點(diǎn)＜l+1,mv+ni-1＞,新加入的群組成員MN+1編號(hào)為＜l+1,mv+ni＞。

(2)成員離開協(xié)議πset_R的形式化描述

假定群組中現(xiàn)在有N個(gè)成員P={M1,M2,…, MN},成員ML離開群組,則離開協(xié)議的形式化描述如下:

1)ML向群組中其它成員發(fā)送退出請(qǐng)求(Remove,sid,ssid,P,ML),Mi對(duì)ML進(jìn)行檢查:如果ML?P則終止該事務(wù),否則按照以下算法更新群組成員關(guān)系:

①離開結(jié)點(diǎn)M＜l.v＞的父結(jié)點(diǎn)為＜l-1,＞,按照層級(jí)遍歷的來遍歷m叉成員關(guān)系樹。遍歷編號(hào)最大的葉結(jié)點(diǎn)為發(fā)起者,否則次大的葉結(jié)點(diǎn)為發(fā)起者＜l′,v′＞。如果＜l,v+1＞為空,則＜l,v-1＞為發(fā)起者,如果＜l,v+1＞與＜l,v-1＞均為空,則＜l-1,m＞為發(fā)起者,否則停止。

②如果TD(＜l-2,v/m2＞)≥3,發(fā)起者＜l′,v′＞刪除離開結(jié)點(diǎn)M＜l.v＞,并且令＜l′,v′＞=＜l,v＞,否則離開結(jié)點(diǎn)的兄弟結(jié)點(diǎn)M′提升父結(jié)點(diǎn)使得M′=＜l-1,＞。

2)發(fā)起者改變其私有密鑰K與計(jì)算輔助密鑰BK≡gKmodp,并將成員關(guān)系和輔助密鑰廣播到{M1,M2,…,MN}-{ML}。

3)所有組成員刪除離開結(jié)點(diǎn)及其父結(jié)點(diǎn),永久刪除群組密鑰,更新發(fā)起者的輔助密鑰,并重新生成m叉成員關(guān)系樹。

定理1如果群組成員的證書可以有效證實(shí)其身份的真實(shí)性,則協(xié)議πset安全地實(shí)現(xiàn)了理想函數(shù)Fset。

該引理的結(jié)論是顯然的,因?yàn)閺睦硐牒瘮?shù)Fset和協(xié)議πset的描述可以看出,協(xié)議中安全更新成員的關(guān)系僅依賴于證書的存在。而每個(gè)成員的證書都可以通過密鑰注冊(cè)獲得,因而該協(xié)議容易實(shí)現(xiàn)。

3.2.3 混合模型(Fsig,Fset,Fagent)下基于m叉樹的m-GKA協(xié)議的形式化描述

當(dāng)所有組成員維護(hù)好一棵m叉樹后,開始協(xié)商通信所用的組密鑰K=f(K＜0,0＞),其中f(.)為單向雜湊函數(shù)。m-TGDH協(xié)議的形式化描述如下。

1)設(shè)最深中間結(jié)點(diǎn)編號(hào)為＜l,v＞,則群組成員葉子結(jié)點(diǎn)編號(hào)為＜l+1,mv＞…,＜l+1,mv+ni-1＞。l+1層葉子結(jié)點(diǎn)Mi(編號(hào)為＜l+1,mv＞)調(diào)用偽隨機(jī)函數(shù)Gen-Key(1k)產(chǎn)生結(jié)點(diǎn)密鑰K＜l+1,mv＞,并計(jì)算BK＜l+1,mv＞=gK＜l+1,mv＞modp,向理想函數(shù)Fsig發(fā)送消息(Sign,sid,0| BK＜l+1,mv＞|ssid),Fsig返回簽名值σi=SignSKMi(0| BK＜l+1,v＞|ssid)。Mi向Mi+1(其編號(hào)為＜l+1,mv+1＞)發(fā)送消息(Mi|0|BK＜l+1,mv＞|σi)。依此類推,編號(hào)為＜l+1,mv+j＞的成員Mi+j調(diào)用偽隨機(jī)函數(shù)GenKey(1k)產(chǎn)生私有密鑰K＜l+1,mv+j＞(j∈[0,ni-2]),并計(jì)算輔助

密鑰BK＜l+1,mv+j＞≡(BK＜l+1,mv+j-1＞)K＜l+1,mv+j-1＞modp,向理想函數(shù)Fsig發(fā)送消息(Sign,sid,0|BK＜l+1,mv+j＞|ssid),Fsig返回簽名σi+j=SignSKMi+j(0|BK＜l+1,mv+j＞|ssid),然后向Mi+j+1發(fā)送(Mi+j|0|BK＜l+1,mv+j＞|σj)。

2)成員Mni-1(結(jié)點(diǎn)編號(hào)為＜l+1,mv+ni-1＞)把消息(Mni-1|0|BK＜l+1,mv+ni-2＞|σni-2)廣播給編號(hào)為{＜l+1,mv+j＞|j∈[0,ni-1]}的所有結(jié)點(diǎn)。

3){＜l+1,mv+ni-1＞|j∈[0,ni-1]}中的結(jié)點(diǎn)成員＜l+1,mv+j＞向理想函數(shù)Fsig發(fā)送驗(yàn)證消息(Verify,sid,Mi+j,σj)。如果驗(yàn)證通過,則進(jìn)行下面的操作,否則終止該事務(wù)。上述每個(gè)成員計(jì)算:

并對(duì)該消息簽名后發(fā)送給Mni-1。

4)Mni-1調(diào)用偽隨機(jī)函數(shù)GenKey(1k)產(chǎn)生私有密鑰K＜l+1,mv+ni-1＞并計(jì)算集合:

S≡{)|?j∈[0,ni-1]},之后向理想函數(shù)Fsig發(fā)送需要簽名的消息(Sign,sid,1|S|ssid),得到理想函數(shù)Fsig的簽名值σS=SignSKMni-1(1|S|ssid),并將消息(Mni-1|1|S|σS)廣播給{＜l+1,mv+j＞|j∈[0,ni-1]}。

5)對(duì)于?j∈[0,ni-1],Mi+j可以計(jì)算:

和輔助密鑰BK＜l,v＞≡gk＜l,v＞modp。

6)K＜l,v＞和BK＜l,v＞為中間結(jié)點(diǎn)＜l-1,＞的子結(jié)點(diǎn)＜l,v＞的私有密鑰和輔助密鑰用于上層的子樹結(jié)點(diǎn)＜l-1,＞的和的計(jì)算,遞歸調(diào)用步驟1)～6)直到計(jì)算出K＜0,0＞為止。

7)當(dāng)組成員關(guān)系發(fā)生變化或者組密鑰更新時(shí)間Δt到時(shí),由與發(fā)生變化結(jié)點(diǎn)相鄰結(jié)點(diǎn)Mi充當(dāng)發(fā)起人,向理想函數(shù)Fset發(fā)送消息(Rekey,sid,ssid||Mi| |cert#Mi),所有組成員重新維護(hù)成員關(guān)系樹。

4 m-TGDH協(xié)議的性質(zhì)分析

4.1 協(xié)議的正確性證明

由于采用m叉樹得到的密鑰協(xié)商協(xié)議不同于GDH和基于2叉樹的TGDH,其正確性不是顯然的,下面采用數(shù)學(xué)歸納法對(duì)該協(xié)議進(jìn)行證明。

證明:對(duì)樹高H使用數(shù)學(xué)歸納法。當(dāng)H=1時(shí),協(xié)議就轉(zhuǎn)化為一般的群組密鑰協(xié)商(GDH)協(xié)議,并且群組至多有m個(gè)成員。當(dāng)H≥2且m=2時(shí),協(xié)議就變成TGDH協(xié)議;當(dāng)H≥2且m＞2時(shí),假定結(jié)點(diǎn)編號(hào)為:＜1,0＞,…,＜1,m-1＞則:

結(jié)點(diǎn)＜1,0＞產(chǎn)生隨機(jī)私有K＜1,0＞,并計(jì)算其輔助密鑰BK＜1,0＞≡gK＜1,1＞modp,并傳送輔助密鑰到結(jié)點(diǎn)＜1,1＞。

結(jié)點(diǎn)＜1,1＞產(chǎn)生隨機(jī)私有密鑰K＜1,1＞,并計(jì)算輔助密鑰:BK＜1,1＞≡(BK＜1,0＞)K＜1,1＞≡gK＜1,0＞K＜1,1＞modp,并傳送K＜1,1＞到結(jié)點(diǎn)＜1,2＞。依此類推,直到結(jié)點(diǎn)＜1, m-1＞計(jì)算出BK＜1,m-2＞,將其廣播到群組集合:S={＜1,0＞,＜1,1＞,…,＜1,m-2＞}。

對(duì)于?＜1,i＞∈S中的所有參與者計(jì)算(BK＜1,m-2＞)1/K＜1,i＞≡gK＜1,0＞K＜1,1＞…K＜1,m-2＞/K＜1,i＞modp,并發(fā)

送到結(jié)點(diǎn)＜1,m-1＞。結(jié)點(diǎn)＜1,m-1＞產(chǎn)生隨機(jī)密鑰K＜1,m-1＞,并對(duì)?＜1,i＞∈S傳送的密鑰計(jì)算: (BK＜1,m-2＞)K＜1,m-1＞*1/K＜1,i＞≡gK＜1,0＞K＜1,1＞…K＜1,m-1＞/K＜1,i＞modp并將該密鑰傳送到結(jié)點(diǎn)＜1,i＞。對(duì)于?＜1,i＞∈S計(jì)算:

位置為＜1,m-1＞的結(jié)點(diǎn)計(jì)算得到:

因而命題成立。

現(xiàn)假設(shè)當(dāng)高度H＜h時(shí),協(xié)議的計(jì)算是正確的,并且有每個(gè)葉子結(jié)點(diǎn)維護(hù)一棵m叉成員關(guān)系樹。由上面的討論可知,任意一個(gè)高度為H＜h的成員關(guān)系樹,其每個(gè)成員都能計(jì)算出其祖先結(jié)點(diǎn)的私有密鑰和輔助密鑰。

當(dāng)H=h時(shí),由協(xié)議的密鑰協(xié)商樹的過程可知,每個(gè)群組成員都維護(hù)一棵相同的m叉成員關(guān)系樹。在成員關(guān)系樹的第1層,結(jié)點(diǎn)編號(hào)為＜1,0＞,＜1,1＞,…,＜1,m-1＞。以這些結(jié)點(diǎn)為根結(jié)點(diǎn)的每棵m叉成員關(guān)系樹所具有層數(shù)至多為H=h-1,由遞歸假設(shè)可知,任意一個(gè)高度為H＜h的成員關(guān)系樹,其每個(gè)成員都能計(jì)算出其祖先結(jié)點(diǎn)的私有密鑰與輔助密鑰,所以每個(gè)組成員均能計(jì)算出:＜K＜1,0＞,BK＜1,0＞＞、＜K＜1,1＞,BK＜1,1＞＞和＜K＜1,m-1＞,BK＜1,m-1＞＞。

因?yàn)槊總€(gè)葉子結(jié)點(diǎn)均知道第1層的結(jié)點(diǎn)的私有密鑰的輔助密鑰,根據(jù)群組密鑰的計(jì)算過程,每個(gè)葉結(jié)點(diǎn)都能計(jì)算出:K＜0,0＞≡gK＜1,0＞K＜1,1＞...K＜1,m-1＞modp,因而協(xié)議是正確的。

4.2 m-TGDH協(xié)議的UC安全性證明

定理2如果通信受限的Fagent實(shí)例M能夠以證據(jù)不可區(qū)分方式證明私鑰的合法性,TDDH假設(shè)多項(xiàng)式等價(jià)于DDH假設(shè),,則協(xié)議m-TGDH能夠在混合模型中有(m-TGDH)→UCFGKA。

證明:在m-TGDH協(xié)議中,理想函數(shù)FGKA有三個(gè)模塊Fsig,Fset,Fagent,則根據(jù)三者的定義,易知這三個(gè)理想函數(shù)是自獨(dú)立的,并且兩兩之間相互獨(dú)立。

記FGKEFset為FGKE去掉Fset后的理想函數(shù),(m-TGDH)πset為去掉πset部分的協(xié)議,根據(jù)引理2,有(m-TGDH)πset→UCFGKEFset成立。由Fsig,Fset,Fagent三者的自獨(dú)立性和兩兩相互獨(dú)立性可知,FGKEFset和Fset之間、(m-TGDH)πset和πset之間也相互獨(dú)立,根據(jù)定理1,有πset→UCFset成立,由UC組合定理得到(m-TGDH)→UCFGKA。

4.3 m-TGDH協(xié)議的性能分析

該協(xié)議的性能主要從計(jì)算開銷、通信開銷和存儲(chǔ)開銷三個(gè)方面進(jìn)行分析。

通信開銷:由于m-TGDH顯著地降低了成員關(guān)系樹的高度,GKA協(xié)議的通信開銷主要依賴于成員關(guān)系樹高度,其通信復(fù)雜度為O(nlogmn)。

計(jì)算開銷:模冪運(yùn)算是衡量計(jì)算開銷的主要標(biāo)準(zhǔn)。在m-TGDH協(xié)議中,使用m叉樹降低了成員關(guān)系樹的高度,從而減少了中間結(jié)點(diǎn)的個(gè)數(shù),有效降低了計(jì)算復(fù)雜度。因?yàn)閘ogmn=logm2×lbn＜lbn,故該協(xié)議計(jì)算上的開銷要低于LTDH協(xié)議。

存儲(chǔ)開銷:與TDH協(xié)議相似,m-TGDH協(xié)議的存儲(chǔ)量也是O(n),但實(shí)際應(yīng)用中,由于中間結(jié)點(diǎn)減少,其存儲(chǔ)開銷可能要略好與LTDH。

5 結(jié) 語(yǔ)

文中利用UC安全框架對(duì)群組密鑰交換協(xié)議進(jìn)行了分析,進(jìn)而提出了一個(gè)動(dòng)態(tài)的群組密鑰交換理想函數(shù),并針對(duì)文獻(xiàn)[5]中的LTDH協(xié)議的不足之處,使用m叉樹設(shè)計(jì)了一個(gè)實(shí)現(xiàn)該理想函數(shù)的安全協(xié)議m -TGDH,并對(duì)協(xié)議的UC安全性作出了證明。經(jīng)過對(duì)協(xié)議的性能分析比較,文中所設(shè)計(jì)的m-TGDH協(xié)議的性能要好于LTDH協(xié)議。文中采用的數(shù)據(jù)結(jié)構(gòu)是m叉樹,當(dāng)成員加入、成員離開當(dāng)成員關(guān)系變化時(shí),所有組成員首先維護(hù)m叉樹而把密鑰更新放在群組密鑰的協(xié)商階段,其更新代價(jià)為O(logmn)。

[1]KIM Y,PERRIG A,TSUDIK G.Tree-based Group Key Agreement[C]//ACM Transaction on Information and System Security.New York:ACM Press,2004:60-96.

[2]陳廷威,高博.一種基于服務(wù)端的群組密鑰協(xié)商方案[J].通信技術(shù),2010,43(03):162-164.

CHEN Ting-wei,GAO Bo.A Key Agreement Scheme based on Servers Group[J].Communications Technology, 2010,43(03):162-164.

[3]PERERIA O,QUISQUATER J.Some Attacks on Authenticated Group Key Agreement Protocols[J].Journal of Computer Security,2003,11(04):555-580.

[4]CANETTI R.Universally Composable Security:A New Paradigm for Cryptographic Protocols[EB/OL].http:// eprint.iacr.org/2000/067.pdf

[5]賈洪勇,卿斯?jié)h,谷澤利,等.通用可組合的組密鑰交換協(xié)議[J].電子與信息學(xué)報(bào),2009,31(07):1571-1575.

JIA Hong-yong,QING Si-han,GU Li-ze,et al.Universally Composable Group Key Exchange Protocol[J]. Journal of Electronics&Information Technology,2009,31 (07):1571-1575.

[6]陸正福,何英.組密鑰管理中d叉樹數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)[J].計(jì)算機(jī)工程與科學(xué),2006,28(10):13-15.

LU Zheng-fu,HE Ying.Design of d-ary Tree Structure for Group key Mangement[J].Computer Engineering& Science.2006,28(10):13-15.

[7]CANETTI R.On Universally Composable Notions of Security for Signature,Certification and Authentication [M].New York:ACM Press,2003.

楊春堯(1986—),男,碩士研究生,主要研究方向?yàn)槊艽a編碼學(xué)、密碼協(xié)議;

YANG Chun-yao(1986-),male,graduate student,majoring in cryptography and cryptographic protocols.

陸正福(1965—),男,教授,主要研究方向?yàn)槊艽a編碼學(xué)、安全多方計(jì)算;

LU Zheng-fu(1965-),male,professor,mainly engaged in cryptography and SMC.

李 軍(1974—),男,工程師,主要研究方向?yàn)樾畔踩?/p>

LI Jun(1974-),male,engineer,mainly working at information security.

Design and Analysis of Dynamic Group Key Agreement Protocol with UC Security

YANG Chun-yao1,LU Zheng-fu2,LI Jun1
(1.Chengdu Westone Information Security Industry Co.,Ltd.,Chengdu Sichuan 610041,China; 2.School of Mathematics and Statistics,Yunnan University,Kunming Yunnan 650091,China)

Aiming at the fact that the concurrent group key agreement(GKA)protocol is discussed only within the isolate model,and based on m-ary tree decisional Diffie-Hellman within the framework of universally composable(UC)security,a group key agreement protocol is designed,and the ideal functionality model for GKA protocol formulated.The security modular design and implementation of GKA protocol indicates that this protocol could meet the requirement of UC security.Compared with the similar protocol of GKA,this new protocol has the advantages of less communication and computation overhead,while supports group members in their dynamic joining and exiting.

group key agreement;universally composable security;communication secrutiy

TP393

A

1002-0802(2014)01-0081-05

10.3969/j.issn.1002-0802.2014.01.016

國(guó)家自然科學(xué)基金資助項(xiàng)目(No.10861012)

Foundation Item：NSFC(No.10861012)