一種高效的動態(tài)組播密鑰管理方案

摘 要:為了高效地管理動態(tài)組播，近年來提出了一些動態(tài)組播管理方案。在分析基于兩層結(jié)構(gòu)的密鑰管理以及安全哈希函數(shù)理論的基礎上，提出了一種新的密鑰管理方案GC-RH以及相應的密鑰更新算法。實驗結(jié)果表明其在密鑰存儲量、加密計算量、網(wǎng)絡通信量等性能方面均優(yōu)于其他同類方案，比較適用于大型動態(tài)組播環(huán)境。

關(guān)鍵詞:組密鑰;組播;隨機數(shù);哈希函數(shù);密鑰管理

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1061-03

doi:10.3969/j.issn.1001-3695.2010.03.071

Efficient key management scheme for dynamic multicast groups

XU Jian-zhen， DONG Yong-xian， LIANG Ke-hui

(College of Computer， Nanjing University of Posts Telecommunications， Nanjing 210003， China)

Abstract:In order to manage the dynamic multicast efficiently，this paper proposed some management schemes for dynamic multicast group.And analyzed those schemes which based on bi-layered key management and security hash functions， and then presented a new management scheme which was called GC-RH(group center-random GC-random and hash) and related key-updating algorithm. Simulation results show that this scheme has strong points in the key storage， encryption， network traffic aspects over other ones，which fits those large-scale dynamic multicast environment.

Key words:group key; multicast; random number; hash function; key management

組播是下一代Internet應用的重要支撐技術(shù)，而組播的安全性是成功進行組通信所必須解決的重要課題之一。為了保障組播通信的安全性，需要使用所有組成員共享的傳輸加密密鑰[1](traffic encrypting key，TEK)來加密通信內(nèi)容，密鑰服務器和組成員采用密鑰加密密鑰[1](key encryption key，KEK)來加密TEK。當組播中有成員加入或退出時，密鑰服務器[1](key server，KS)更新組密鑰，并用密鑰加密密鑰加密后發(fā)送至合法組成員。在組播安全問題中組密鑰的安全管理是研究的熱點課題。目前，人們已提出多種密鑰管理方案。組密鑰管理的基本結(jié)構(gòu)主要有基于兩層結(jié)構(gòu)和多層結(jié)構(gòu)。其中典型的有IKAM[2]和Iolus[3]。由于多層結(jié)構(gòu)資源開銷較大且系統(tǒng)時延較長，其不適合成員關(guān)系頻繁變化的大型動態(tài)群組。本文主要討論基于兩層結(jié)構(gòu)的密鑰管理方案，提出了一種基于高效的動態(tài)組播密鑰管理方案，并給出其密鑰更新算法。

1 已有組播密鑰管理方案分析

1.1 IKAM方案

文獻[2]中介紹了一種基于兩層結(jié)構(gòu)的基本方案，模型如圖1所示。根據(jù)網(wǎng)絡拓撲結(jié)構(gòu)，將成員分為一個域和若干個子組區(qū)域。在域內(nèi)由DKD(domain key distributor)進行組密鑰的管理和向各個子組密鑰分發(fā)者AKD(area key distributor)分發(fā)密鑰;在子組區(qū)域內(nèi)由AKD進行區(qū)域內(nèi)的密鑰管理和分發(fā)。

1) DKD

a)k0:整個組播組共享的通信密鑰;

b)ka1～kam:AKD與DKD共享的密鑰。

2)AKD

a)k0:整個組播組共享的通信密鑰;

b)kgi:i∈ [1，m]，子組密鑰;

c)kai:i∈ [1，m]，AKD與DKD共享密鑰;

d)ki1～kin:i∈ [1，m]，成員與本區(qū)域AKD共享個人密鑰。

3)Member

a)k0:整個組播組共享的通信密鑰;

b)kgi:i∈ [1，m]，成員所在區(qū)域的子組密鑰;

c)kij:i∈[1，m] ，j∈[1，n]，第i個區(qū)域中第j個成員與AKDi共享的個人密鑰。

由此可知，DKD的密鑰存儲量是m+1，AKDs的密鑰存儲量是n+3，member端密鑰存儲量是3。

該方案的密鑰分發(fā)采用SKDC(simple key distribute center)算法，即點對點的方式。以單個成員退出為例，當區(qū)域1中的成員M1要退出時，首先子組kg1需要更新。由AKD1產(chǎn)生新的k′g1，并用區(qū)域1中各個成員的個人密鑰(k12，…，k1n)加密后一一發(fā)送給各個成員;各成員解密后得到k′g1;AKD1再用ka1(AKD1與DKD共享的密鑰)加密k′g1后單播給DKD;DKD產(chǎn)生新的組密鑰k′0，分別用ka1，ka2，…，kan加密后單播給各AKDi。每個AKDi轉(zhuǎn)發(fā)各報文，區(qū)域中成員分別用自己知道的子組密鑰k′gi解密得到k′0。所以，DKD的加密次數(shù)和網(wǎng)絡通信量均為m次;而各個 AKDi的加密次數(shù)和網(wǎng)絡通信量為n-1次。

這種方案較易實現(xiàn)，具有可靠的密鑰分配安全性。雖然DKD的存儲復雜度僅與子組樹有關(guān)，但AKD的存儲復雜度和通信復雜度均為O(n)，故不具有可擴展性，只適合小規(guī)模的組通信。

1.2 GC-LKH方案

文獻[4]中提出了GC-LKH密鑰管理方案，它結(jié)合LKH算法和IKAM方案的特點，在每個area中利用LKH[5]樹算法進行子組密鑰更新，組播組的全體成員共享一個組密鑰K0，用來加密和解密組播組中的通信數(shù)據(jù);將組播組分為m個子組進行管理，每個子組中的成員數(shù)為n。其中DKD分別與每個AKD共享一個個人密鑰，同時也擁有各個子組密鑰，所以DKD中保存的密鑰總數(shù)為2m+1。各個AKD中保存LKH樹中所有節(jié)點的密鑰，會話密鑰k0以及與DKD共享的密鑰kai，密鑰總數(shù)=2n-1+1+1=2n+1。

算法的基本思想是:當每個子組內(nèi)有成員變動時，AKD利用LKH樹算法進行子組密鑰更新，并將更新后的子組密鑰單播給DKD。DKD用于給AKD共享的個人密鑰解密出新的子組密鑰，同時產(chǎn)生一個新的組密鑰k′0，用各子組密鑰加密后組播給所有的AKD，并由AKD轉(zhuǎn)發(fā)給本子組內(nèi)的所有成員。

由此可知，當一個成員退出時DKD所付出的加密次數(shù)與網(wǎng)絡通信量為m+1，各個AKDi的加密次數(shù)與網(wǎng)絡通信量為logd n。

GC-LKH方案比IKAM在通信開銷上有所減低，但卻增加了AKD的密鑰存儲量。

2 GC-RH方案總體框架

由于IKAM的兩層密鑰管理方案將訪問控制和密鑰分配安排在子組內(nèi)完成，具有較好的擴展性。結(jié)合本文將要提出的密鑰更新算法，該算法在保持通信開銷的同時，在RH計算開銷方面優(yōu)于LKH 和OFT算法。綜合這兩種算法的優(yōu)點，本文設計了一種組播密鑰管理方案。其總體框架如圖2所示。

本方案的特點如下:

a)組播組的全體成員共享一個組密鑰K0，用來加密和解密組播中的通信數(shù)據(jù)。

b)將組播組分為m個子組進行管理，每個子組中的成員數(shù)為n，則組播組的總體成員數(shù)為N=m×n。

c)設DKD為組控制器，負責對各個子組控制器的管理及組密鑰的分配。DKD分別與每個子組控制器共享一個個人密鑰(ka1，ka2，…，kan)，所以DKD中保存的密鑰數(shù)=m+1 。

d)設Gi為第i組標志，AKD為子主控制器，負責子組內(nèi)各個成員的訪問控制和密鑰分配，各子組均有自己的子組密鑰kgi，與DKD共享密鑰，而且AKDi(i∈ [1，m])擁有與子組內(nèi)的每個成員共享的個人密鑰(ki1，ki2，…，kin)。所以AKD中保存的密鑰總數(shù)=n+2 。本文提出的RH密鑰更新算法具有較高的密鑰分配效率，在子組內(nèi)采用該算法作為密鑰更新算法。

3 RH組密鑰管理方案描述

本文將提出一種新的密鑰分配方案——RH(random and hash)密鑰分配方案，并將此方案應用到area中作為密鑰分配算法，其能夠抵抗任意數(shù)目用戶的共同攻擊，進行組密鑰更新需要更少的通信消息和計算開銷，可以減少對網(wǎng)絡帶寬資源的占用以及降低組控制中心GC和用戶的計算開銷。

本文的密鑰更新數(shù)學模型繼承了邏輯密鑰層次樹(LKH)的結(jié)構(gòu)，即基于集中式的邏輯密鑰樹這樣一個結(jié)構(gòu)模型。但是密鑰更新算法是通過舊密鑰值、隨機數(shù)以及安全單向哈希函數(shù)的結(jié)合使用來實現(xiàn)的。為了方便討論，假設邏輯密鑰樹是二叉平衡樹，如圖3所示。該密鑰樹由組控制中心GC存儲和管理。樹中的葉子節(jié)點和組成員一一對應并關(guān)聯(lián)。位于葉子節(jié)點的密鑰值是成員的個人密鑰，該成員和GC所共享。樹的根節(jié)點密鑰為組共享密鑰，用于保護組內(nèi)部通信，其余節(jié)點密鑰為輔助密鑰。每個合法成員僅知道與其相關(guān)聯(lián)的葉子節(jié)點到樹根節(jié)點路徑上的那些節(jié)點密鑰值，這些節(jié)點密鑰被稱做與該成員相關(guān)的節(jié)點密鑰集。每一次組成員變化時，與該成員關(guān)聯(lián)的某個葉子節(jié)點密鑰發(fā)生變化，從該葉子節(jié)點到根節(jié)點路徑上的所有節(jié)點密鑰值都要被更新。新的節(jié)點密鑰值的計算公式為

K′〈i， j〉=h(K〈i， j〉，R)(1)

其中:h(x，y)表示密碼學上安全的單向哈希函數(shù)，其輸入為x，y;R是一個秘密的隨機數(shù)，由組控制中心GC產(chǎn)生并安全分發(fā)給全組內(nèi)所有合法成員;〈i， j〉為節(jié)點編號;K〈i， j〉為當前(舊的)節(jié)點密鑰值;K′〈i， j〉為更新后(新的)節(jié)點密鑰值。

關(guān)于邏輯密鑰樹的初始化管理工作，可以參考Waller[6]的LKH算法初始化。用n表示初始化成員數(shù)目。首先，GC為組構(gòu)造一棵完全二叉樹，用T表示;d表示樹的度;H表示樹的高度。規(guī)定樹的根節(jié)點位于樹的第0 層，T中每一個節(jié)點用二元組〈h，s〉來表示，h表示該節(jié)點位于第h層，s表示該節(jié)點是第h層從左往右計數(shù)的第s個節(jié)點。其次，GC生成一個隨機種子r， r是對應于帶密鑰的散列函數(shù)Fr()[7]的入口索引。

這里，帶密鑰的散列函數(shù)Fr()被定義為根據(jù)r和輸入M產(chǎn)生位長為l的輸出:Fr(M)。GC保密r的值。樹T中的每個節(jié)點可以用一個整數(shù)惟一表示，例如〈h，s〉可以用大(dh-1)/(d-1)+s來惟一地標志。GC為樹中的每個節(jié)點分配一個對稱密鑰。節(jié)點〈h，s〉對應的密鑰用K〈h，s〉來表示，由GC按如下方法生成:

K〈h，s〉=Fr[(dh-1)/(d-1)+s];0≤h≤H，1≤s≤dh(2)

按LKH方案的規(guī)定，樹T中的每個葉子節(jié)點與組內(nèi)部的一個成員相關(guān)聯(lián)。而且組內(nèi)部的一個成員知道從代表自己的葉子節(jié)點〈h，s〉到樹的根節(jié)點〈0，1〉的路徑上所有節(jié)點密鑰值。例如，組成員m1知道的密鑰為K〈0，1〉，K〈1，1〉，K〈2，1〉，K〈3，1〉，如圖3所示。

3.1 新成員加入子組的協(xié)議方案

設一個新成員mn要求加入組。選擇樹中距離根節(jié)點最近的地方進行加入。為了防止新成員訪問其加入前的組通信內(nèi)容，必須更新從新成員到樹根節(jié)點的路徑上所有節(jié)點密鑰。加入過程如下:

a)新成員加入到距離根節(jié)點最近的地方。

b)GC調(diào)用隨機數(shù)發(fā)生器產(chǎn)生一個隨機數(shù)r1，并用過去的會話密鑰SEK加密，廣播給組內(nèi)成員，以隨機數(shù)r1和節(jié)點的當前密鑰值作為輸入，按式(3):

K′〈i， j〉=h(K〈i， j〉，r1)(3)

產(chǎn)生新的節(jié)點密鑰。

c)GC用新節(jié)點密鑰加密新成員到樹根節(jié)點路徑上所有新的節(jié)點(輔助)密鑰，并單播給新節(jié)點。

d)新成員用其個人密鑰解密c)中的消息，從而得到新成員節(jié)點到根節(jié)點的密鑰集。

e)其他組成員通過K′〈i， j〉=h(K〈i， j〉，r1)更新密鑰。

3.2 當前成員刪除協(xié)議

組控制中心GC產(chǎn)生隨機數(shù)r2并用舊的密鑰加密密鑰加密，發(fā)送給組中所有剩余成員。收到后，每個剩余成員按照式(3)更新與自己相關(guān)的節(jié)點密鑰。

3.3 RH與LKH、OFT[8]協(xié)議的性能比較

本文選二叉平衡樹作為邏輯密鑰樹，并以此為基礎對這三種協(xié)議在通信、存儲、組控制中心GC計算和組成員計算等方面的開銷進行詳細的比較，如表1~3所示。

表1 新成員加入時的通信和計算開銷

LKHOFTRH

CB/bit2H×LH×L1×L

CS/bitH×LH×LH×L

CC2HCE+HCRHCE+2HCF+CR+HCXORCE+HCF+CR

max(CM)HCECE+HCF+HCXORCE+HCF

表2 刪除一個組成員時的通信和計算開銷

LKHOFTRH

CB/bit2H×LH×LH×L

CC2HCE+HCRHCE+2HCF+CR+HCXORHCE+HCF+CR

max(CM)HCECE+HCF+HCXORCE+HCF

表3 三種協(xié)議中GC和成員的存儲開銷

LKHOFTRH

SC/bit(2n-1)L(2n-1)L(2n-1)L

SM/bit(H+1)L(H+1)L(H+1)L

其中:n表示組成員數(shù)目;d表示樹的度;H表示樹的深度;L表示密鑰或隨機數(shù)的比特長度;CE表示對稱加/解密運算;CF表示單向哈西函數(shù)運算; CR表示隨機數(shù)的產(chǎn)生運算;CXOR表示比特異或運算;CC表示組控制中心GC需要完成的計算開銷;CM表示組內(nèi)每個成員所需要的計算開銷;CS表示單播通信開銷;CB表示廣播通信開銷;SC表示組控制中GC的存儲開銷;SM表示組內(nèi)成員的存儲開銷。

通過與LKH、OFT協(xié)議比較可知，三種協(xié)議的存儲開銷相同，但RH協(xié)議在通信開銷和計算開銷方面具有更好的可伸縮性。在成員加入時，RH協(xié)議進行密鑰更新操作，所需的廣播通信開銷和組控制中心GC的計算開銷均為常數(shù)O(1)，而OFT和LKH協(xié)議中這兩種開銷均為對數(shù)級O(logd n);當成員被刪除時，RH協(xié)議的通信開銷和OFT協(xié)議持平，但其組控制中心GC和成員的計算開銷卻低于OFT和LKH協(xié)議。

4 仿真及結(jié)果分析

本文對本模型中的數(shù)據(jù)傳輸機制進行了仿真模擬，建立了一個軟件環(huán)境來模擬GC-RH，在一臺Linux主機上搭建了仿真平臺，隨機選擇組成員組成不同規(guī)模的組，并取m=4(組成員平均分成四組)，每個子組為二叉平衡樹，所有組成員都是隨機加入或退出。

圖4顯示了IKAM、GC-LKH和GC-RH協(xié)議更新開銷的比較。這三種協(xié)議方案的更新開銷與推導結(jié)果一致，其在成員變動時的更新開銷與組有關(guān)，隨著組規(guī)模的增大而增加。

圖5顯示了IKAM、GC-LKH和GC-RH協(xié)議通信開銷的比較。這三種協(xié)議方案的通信開銷與推導結(jié)果一致。這是因為GC-RH協(xié)議在組成員更新時，組控制中心提供密鑰更新所需的部分信息(隨機數(shù))，而密鑰更新的具體運算則由組成員自己通過哈希函數(shù)運算完成，所以密鑰更新時的通信開銷比GC-LKH、IKAM都要低。

圖6顯示了IKAM、GC-LKH和GC-RH協(xié)議密鑰存儲開銷的比較。GC-LKH和GC-RH的密鑰存儲開銷是相同的，并高于IKAM。因為這是由算法中的邏輯密鑰樹層次結(jié)構(gòu)所決定的。

5 結(jié)束語

本文結(jié)合兩層的密鑰管理結(jié)構(gòu)和隨機數(shù)以及安全哈希函數(shù)算法的特點，設計了一種新的組播密鑰管理方案。該方案在通信效率、可擴展性和計算開銷方面具有更好的伸縮性，并且能夠抵抗任意數(shù)目成員的共同攻擊。

下一步的工作將研究是否存在一個比邏輯密鑰層次樹結(jié)構(gòu)更優(yōu)的數(shù)學模型，該模型能使組密鑰更新操作在通信、計算、存儲開銷三方面取得一個更好的平衡效果。

參考文獻:

[1]WILLIAMSON B.Developing IP multicaticast networks[C]//Proc of ACM SIGCOMM.2002.

[2]HARDJONO T，CANB H J，MONGA I.Intra-domain group key management protocol-domain group key management protocol I[EB/OL].(2000-02).draft-ietf-ietf-ipsec-intragkm-02.tex.

[3]李徽，武傳坤.一種高效的long-lived self-healing密鑰分發(fā)機制[J].軟件學報，2009，20(2):462-468.

[4]韓秀玲，王行愚.大型動態(tài)多播群組的分布式密鑰管理方案[J].小型微型計算機系統(tǒng)，2004，25(12):2199-2202.

[5]SHERMAN A，McGREW D.Key establishment in large dynamic groups using one-way function trees[J].IEEE Trans on Software Engineering，2003，29(5):444- 458.

[6]WANG C K，GOUDA M，LAM S S.Secure group communications using key graphs[J].IEEE/ACM Trans on Networking，2000，8(1):16-30.

[7]BOYD C，MATHURIA A.Systematic design of key establishment protocols based on one-way function[C]//Proc of Computers and Digital Techniques.1997.

[8]MITTRA S I.A frame work for scable secure multicasting[J].ACM Computer Communication Review，1997，27(4):277-288.