組播密鑰管理方案的新研究

(電子科技大學(xué) 計(jì)算機(jī)學(xué)院， 四川 成都 610054）

摘 要：通過研究提出了一種新的組播密鑰管理方案，這種方案不僅極大地降低了用于密鑰存儲(chǔ)的空間開銷和由于發(fā)送密鑰更新信息而造成的帶寬浪費(fèi)，同時(shí)還具有良好的可擴(kuò)展性。有成員加入（退出）組播組時(shí)，雖然組控制器(Group Controller)必須更改以后報(bào)文的加密密鑰，但是對(duì)于其他成員來說，他們用以前的密鑰同樣可以解密這些信息，最后給出了這樣一種設(shè)想的實(shí)現(xiàn)方式。

關(guān)鍵詞：安全組播； 密鑰管理； 線性同余； 中國(guó)剩余定理（孫子定理）

中圖法分類號(hào)：TP309．2文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-3695(2006)08-0142-02



New Research on Multicast Key Management Scheme

QIN Ke， ZHOU Ming tian， LIU Nai qi

(College of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu Sichuan 610054， China)

Abstract:After some deeply research on kinds of secure multicast key management schemes， a completely new way which not only improve the efficiency but also minimize users’ keys storage is proposed. This scheme has pretty good flexibility as well. The scheme works like this: No matter how many users logout or login， the Group Controller(GC) need not send any re keying messages， and although the GC changes the DEK(Data Encryption Key)， users can decrypt these messages with there pre vious private keys. This paper also presents a realization for the proposition.

Key words:Secure Multicast; Key Management; Linear Congruantial; Chinese Remainder Theorem



1引言

組播是一種應(yīng)用前景極其廣泛的技術(shù)。但是，由于組播技術(shù)的一系列特性，它的安全研究相比單播來說要復(fù)雜得多。到目前為止，組播研究中很多難點(diǎn)尚未攻克，而組播密鑰管理是攻克這些難點(diǎn)的基礎(chǔ)。在密鑰管理方面，專家和學(xué)者們提出了各式各樣的方案，但是這些方案大部分都集中在對(duì)密鑰更新方式的研究上，這些研究又包括兩個(gè)方面：①如何進(jìn)行密鑰更新信息的發(fā)送，如Secure Lock方案[1]；②在減少密鑰更新信息量和減少組播成員存儲(chǔ)密鑰所花費(fèi)的空間這兩個(gè)方面尋求一個(gè)好的折中點(diǎn)。這樣的研究思路已經(jīng)持續(xù)了十多年，IETF的MSEC WG(Working Group)提出：是否可以采用 npairwise的方式進(jìn)行密鑰管理？但是到現(xiàn)在為止，還沒有正式的文獻(xiàn)對(duì)這一建議進(jìn)行詳細(xì)描述。在此我們提出來一個(gè)組播密鑰管理方案，方案的思想接近于MSEC WG的建議。這個(gè)方案將密鑰更新信息量減小到最少（0）；將成員存儲(chǔ)密鑰的空間開銷減小到最小（組播成員只需要存儲(chǔ)自己的密鑰）。

為了將我們提出的組播密鑰管理方案同目前的方案進(jìn)行比較，本文主要描述和討論了LHKT（Logical Hierarchical Key Tree）這種得到廣泛認(rèn)可的方案，給出了新方案的思想形成過程，描述了該方案的一個(gè)實(shí)現(xiàn)方式。

2現(xiàn)有的密鑰管理方案

在有些資料上，Logical Hierarchical Key Tree Scheme也被稱為Hierarchical Key Tree Scheme。這種方案的密鑰更新信息量可以從 O(N)減小到O (logN)，其中N 是節(jié)點(diǎn)數(shù)目。

如圖1所示，方案規(guī)定，樹中每一個(gè)非葉子節(jié)點(diǎn)都擁有一個(gè)密鑰，而任意一個(gè)葉子節(jié)點(diǎn)都擁有從根節(jié)點(diǎn)到它本身的路徑上的所有節(jié)點(diǎn)的密鑰。這樣，如果有成員退出組播組（如節(jié)點(diǎn)6），那么必須更新從根節(jié)點(diǎn)到節(jié)點(diǎn)6的路徑上的一切密鑰，即15，14，11這三個(gè)節(jié)點(diǎn)的密鑰，以防止節(jié)點(diǎn)6繼續(xù)監(jiān)聽組播報(bào)文。

假設(shè)節(jié)點(diǎn)6退出，密鑰更新過程如下：組控制器（Group Controller，GC）首先用生成一條消息 α=E_K5(K′₁₁)來更新K₁₁，該消息只能由節(jié)點(diǎn)5解密；再生成兩條消息α 1=E_K′11(K′₁₄)，α₂=E _K′12(K′₁₄)來更新K₁₄。因?yàn)橄聦庸?jié)點(diǎn)擁有上層節(jié)點(diǎn)的所有密鑰，所以該消息可以由U₁₁，U₁₂及其子節(jié)點(diǎn)解密（節(jié)點(diǎn)6除外）。最后再生成兩條消息α₃=E_K′14(K′₁₅)，α₄=E_K13(K′₁₅)來更新K₁₅，該消息只能由U₁₃，U₁₄及其子節(jié)點(diǎn)解密，從而用五條消息更新了15，14，11這三個(gè)節(jié)點(diǎn)的密鑰。將節(jié)點(diǎn)6排除在組播成員之外。

成員的加入過程同退出過程類似。

該方案的最大優(yōu)點(diǎn)就是大大減少了更新密鑰的信息量，僅需發(fā)送 O (logN )次消息便可以使用新的會(huì)話密鑰 K′_s來同剩下的組播組成員進(jìn)行通信。雖然減小了更新密鑰的信息量，但是對(duì)于組接收者來說，必須花費(fèi)較大的空間來存儲(chǔ)從根節(jié)點(diǎn)到自身節(jié)點(diǎn)的路徑上的所有密鑰，特別是在組播樹深度比較大的時(shí)候，用于存儲(chǔ)密鑰的空間開銷非常龐大。這對(duì)于一些存儲(chǔ)空間十分有限的嵌入式系統(tǒng)來說，是很不利的；另一個(gè)缺點(diǎn)就是方案存在Single Point Failure。這是集中式管理的通病，一旦與GC距離很近的節(jié)點(diǎn)被攻擊，那么下層所有節(jié)點(diǎn)均無(wú)法與其他組成員進(jìn)行通信。

關(guān)于密鑰管理方案，國(guó)際上的研究成果很多，文獻(xiàn)[4，6～9]是比較常見的方式，很多方案都在LHKT上作改進(jìn)，有些方案能夠?qū)⒚荑€更新信息數(shù)量降至 O (logN/2) 甚至更少。

3新方案設(shè)想

本文提出了一種新的密鑰管理方案。思路如下：考慮到現(xiàn)有的各種方案都具有這樣一個(gè)特點(diǎn)，當(dāng)有成員加入（退出）時(shí)，GC必須進(jìn)行密鑰更新，雖然不同方案的密鑰更新信息量各不相同。為此我們大膽地猜想，是否可以設(shè)計(jì)出一種密鑰管理方案，使得成員加入（退出）時(shí)不需要進(jìn)行密鑰更新？這種方案能否實(shí)現(xiàn)取決于我們能否找到這樣一種密碼機(jī)制：GC擁有一個(gè)密鑰K_g，成員U₁，U₂，…，U_r分別擁有密鑰K₁，K₂，…，K_r，滿足K_g=f(K₁，K₂，…，K_r)，用K_g加密要發(fā)送的數(shù)據(jù)，而每個(gè)成員都根據(jù)自己的密鑰K_i來解密消息。當(dāng)成員U_i退出時(shí)，GC根據(jù)組內(nèi)其他成員的密鑰重新計(jì)算得到新的加密密鑰 K′_g=f(K₁，K₂，…，K_i-1，K_i+1，…，K_r)。以后發(fā)送消息就使用K′_g進(jìn)行加密，而其他成員用現(xiàn)有的密鑰同樣可以解出用K′_g加密的信息。同時(shí)，由于計(jì)算K′_g時(shí)是排除了退出的成員U_i，所以U_i不能繼續(xù)參與組播。

密碼學(xué)上存在著類似的但是有根本區(qū)別的密碼機(jī)制：Colin Boyd對(duì)公開密鑰密碼進(jìn)行推廣[11]得到了多密鑰公開密鑰密碼體制。在這種機(jī)制中，用密鑰的某個(gè)子集來加密消息，用其他密鑰來解密消息。這種方案同本文提出的方案的根本的區(qū)別在于：①本文提出的密碼體制，加密密鑰只有一個(gè)；而多密鑰密碼體制的加密密鑰是密鑰集的任意子集。②本文提出的密碼體制的最大特點(diǎn)是解密密鑰隨時(shí)變動(dòng)，而加密密鑰不變；這一點(diǎn)是多密鑰密碼體制不具備的。



4方案的實(shí)現(xiàn)

4．1數(shù)學(xué)原理

假設(shè)在一個(gè)組播組中有 r 個(gè)成員，并且每個(gè)成員擁有一個(gè)方程：

4．2方案評(píng)價(jià)及應(yīng)用

應(yīng)用此方案可以很好地解決現(xiàn)有的安全組播密鑰管理問題中的兩個(gè)矛盾的方面：同時(shí)減少了需要成員保存的密鑰數(shù)量和密鑰更新信息發(fā)送量。對(duì)一個(gè)合法成員來說，只需要存儲(chǔ)兩個(gè)參數(shù) a_n+i，n_n+i，而這兩個(gè)參數(shù)足以保證該成員在任意時(shí)刻解密任何消息。同時(shí)，對(duì)于GC來說，一旦檢測(cè)到有成員加入（退出），那么GC就在現(xiàn)有的方程組中添加（刪除）該成員對(duì)應(yīng)的方程組，重新計(jì)算新的方程組的根 x′ ，得到新的密鑰，以此密鑰加密得到 C′=x′M 。雖然加密密鑰改變了，但根據(jù)以上論述，合法成員依然可以用他們現(xiàn)在掌握的密鑰來解密這個(gè)消息。

由于我們的方案也采用的是集中式管理，所以不可避免地繼承了集中式管理的缺陷——存在單點(diǎn)失效問題。為了避免這個(gè)問題，我們采用這樣一種組播結(jié)構(gòu)，如圖2所示。

在成員變動(dòng)很少的Backbone上采用MKS這種最簡(jiǎn)單直接的管理方案，在接收端節(jié)點(diǎn)變動(dòng)頻繁的Last hop采用本文提出的密鑰管理方案。這樣，既減輕了GC的負(fù)擔(dān)，又消除了單點(diǎn)失效問題。如果在Backbone上某個(gè)節(jié)點(diǎn)失效，影響的也只是一個(gè)小組，不會(huì)擴(kuò)散到整個(gè)組播組。

由以上論述可見，方案本身的優(yōu)勢(shì)是非常明顯的：

（1）GC不需要發(fā)送密鑰更新信息；

（2）接收方的空間開銷極小；

（3）可擴(kuò)展性良好；

（4）能夠抵御同謀攻擊。

而這四點(diǎn)正好是密鑰管理方案所極力追求的。

5結(jié)束語(yǔ)

通過對(duì)現(xiàn)有方案的研究，我們提出的這種密鑰管理方案不僅比較巧妙地減小了密鑰更新信息量，也使得組播分發(fā)樹的各個(gè)節(jié)點(diǎn)不需要花費(fèi)太多的密鑰存儲(chǔ)空間，并且擴(kuò)展性良好。為了解決當(dāng)組播組成員太多而帶來的GC負(fù)擔(dān)

大大加重的問題，我們采用了分級(jí)處理的思想：在Backbone上采用MKS方案，在Last hop采用本文提出的方案。這種組播結(jié)構(gòu)大大提高了組播的性能。

致謝： 向通信學(xué)院周亮教授表達(dá)誠(chéng)摯的謝意，感謝周亮教授傳授了許多密碼學(xué)的知識(shí)。

參考文獻(xiàn)：

[1] Guang Huei Chiou， Wen Tsuen Chen. Secure Broadcasting Using the Secure Lock[J]. IEEE Transactions on Software Engineering， 1989，8(8):929-933.

[2] Fan Du， Lionel M Ni， Abdol Hossein Esfahanian.Toward Solving Multicast Key Management Problem[EB/OL]. http://ieeexplore.ieee.org/Xplore/dynhome.jsp， 2005/2005.

[3] D Wallner， E Harder， R Agee. National Security Agency[EB/OL]. http://www.ietf.org/rfc.html， 1999 06/2005.

[4] Claudiu Duma， Nahid Shahmehri， Patrick Lambrix. A Hybrid Key Tree Scheme for Multicast to Balance Security and Efficiency Requirements[C]. Proceedings of the 12th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises，2003.1080-1086.

[5] Mingyan Li， R Poovendran， C Berenstein. Design of Secure Multicast Key Management Schemes with Communication Budget Constraint[J]. IEEE Communications Letters， 2002，6(3):108-111.

[6] A Ballardie. Scalable Multicast Key Distribution[EB/OL]. http://www.ietf.org/rfc.html， 1996/2005.

[7] A Ballardie. Core Based Trees Multicast Routing Architecture[EB/OL]. http://www.ietf.org/rfc.html， 1997/2005.

[8] David A McGrew， Alan T Sherman. Key Management for Dynamic Group: One Way Functions[EB/OL]. http://ieeexplore.ieee.org/Xplore/dynhome.jsp， 2005.

[9] Suvo Mittra. Iolus: A Framework for Scalable Secure Multicast[C]. Proceedings of the ACM SIGCOMM， 1997.268-272.

[10] 劉璟.大型動(dòng)態(tài)組播系統(tǒng)網(wǎng)絡(luò)安全服務(wù)的若干問題研究[D].成都：電子科技大學(xué)，2003.

[11] C Boyd. Some Applications of Multiple Key Ciphers Advances[EB/OL]. http://ieeexplore.ieee.org/Xplore/dynhome.jsp， 2005.

[12] 徐明偉，董曉虎，徐恪. 組播密鑰管理的研究進(jìn)展[J]. 軟件學(xué)報(bào)， 2004，15(1):141-150.

[13] 許勇，陳愷. 安全多播中基于成員行為的LKH方法[J]. 軟件學(xué)報(bào)， 2005，16(4):601-608.

作者簡(jiǎn)介：秦科(1980 )，男，四川綿竹人，博士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)安全/信息系統(tǒng)安全；周明天(1939 )，男，廣西容縣人，教授，博導(dǎo)，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、信息系統(tǒng)安全、分布式對(duì)象技術(shù)等；劉乃琦(1950 )，男，四川成都人，教授，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、信息系統(tǒng)安全。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。