組播密鑰管理中一種新的密鑰更新策略

(1.北京科技大學 信息工程學院 計算機科學與技術系， 北京 100083; 2.涪陵師范學院 數學系， 重慶 408003)

摘 要：為節約存儲空間和整體處理時間，首先基于KOR提出一種新的密鑰更新策略和協議(KOR+)，并與KOR作了比較。其次，在密鑰樹是滿和平衡的條件下，對采用KOR+及UOR策略的密鑰服務器分別建立平均加密代價公式。最后，用解析方法導出它們的最優密鑰樹度數。

關鍵詞：組播安全； 組密鑰管理； 密鑰樹； 度數； 優化

中圖法分類號：TP393．08文獻標識碼：A

文章編號：1001-3695(2006)08-0102-02



A New Rekeying Policy for Multicast Key Management



YANG Jun1，2， ZHOU Xian wei1， QIN Bo ping1， XUE Nan1

(1.Dept. of Computer Science Technology， College of Information Engineering， Beijing University of Science Technology， Beijing 100083， China; 2. Dept. of Mathematics， Fuling Teachers College， Chongqing 408003， China)

Abstract:Based on KOR a new rekeying strategy and protocol(called KOR+) are first proposed and compared with KOR in this paper. Then two formulae of the average encryption costs of a key server utilizing KOR+ and UOR are established respectively provided that the key trees are full and balanced. Finally， optimal key tree degrees are deduced analytically for both of them.

Key words:Multicast Security; Group Key Management; Key Tree; Degree; Optimization



1引言

由于能使組通信取得可擴展的消息交換，具有高效利用網絡資源的潛在優勢，組播成為下一代Internet應用的一門支撐技術，但組播安全性是成功部署組通信應用所必須解決的一個重要課題[1，2]。為了對傳輸的組播數據進行訪問控制，高效地分發密碼密鑰到合法的組成員是組密鑰管理(Group Key Ma nagement，GKM)研究的一項挑戰，而可擴展的組密鑰更新(Group Rekeying)是GKM研究的中心問題。

已有研究表明[1～3]，不存在一個萬能的GKM方案滿足各種組通信應用的安全需求?，F有的GKM方案可主要分為三類，即集中式平坦型方案、分布式平坦型方案和層次方案（又細分為密鑰層次與節點層次兩個子類）。C.K.Wong等人[4]提出了LKH (Logical Key Hierarchy) 模型和方案及三種密鑰更新的策略和協議：面向成員（User Oriented Rekeying，UOR），面向密鑰（Key Oriented Rekeying，KOR）及面向組（Group Oriented Rekeying，GOR）。每個策略均有其與應用環境及需求有關的適用范圍。因兼備較好的擴展性（在維護密鑰樹平衡的條件下，密鑰更新的通信開銷和用戶端存儲開銷都僅隨組規模呈對數級增長，但密鑰服務器的存儲開銷卻隨組規模呈線性增長）和安全性（非組機密性、前向/后向機密性及抗串謀性），目前GKM研究的熱點[1～6]主要集中于以LKH為代表的密鑰樹模型。鑒于對大型（如10萬以上的組成員）動態組的密鑰更新操作，其通信、存儲和計算開銷仍然很高，本文的第一個目標就是在不影響安全性的前提下對KOR策略提出兩點改進(KOR+)，并設計相應的密鑰更新協議，以節約存儲空間和整體處理時間。另外，近來IETF(Internet Engineering Task Force)提倡在GSAKMP（Group Security Association Key Management Protocol）中使用任意度數的LKH樹[3]。C.K.Wong等人從大量的計算機模擬實驗得到：對采用GOR（或KOR）的密鑰服務器，其最優的平均處理時間在樹的度數為4左右取得。W.T.Zhu[5]解析地證明了：對采用KOR的密鑰服務器和滿的平衡樹，其最優的平均加密開銷在度數為4時取得。本文的第二個目標是解析地求出在KOR+和UOR策略中密鑰服務器的平均加密代價及其最優的密鑰樹度數。

2KOR₊協議

一棵密鑰樹是組密鑰(Group Key)作為根的有根樹。密鑰樹上的每個節點都代表一把密鑰加密密鑰(Key Encrypting Key，KEK)，其中樹的內部節點是邏輯的。每一成員擁有其葉節點（對應于個體密鑰）到根的所有密鑰，但不知道樹上其他節點密鑰。組密鑰更新是改變KEK并把新的密鑰分配到被授權組成員的過程。文獻[4]把密鑰樹的葉節點作為成員(這不合密鑰樹之意)，而文獻[1，3，5，6]把密鑰樹的葉節點定義為個體密鑰。前者的樹高比后者大1。本文遵從后者約定。

與文獻[4～6]一樣，本文假定：一次密鑰更新過程只處理一個成員加入或離開組播組；對于單播及(子組)組播存在可靠的消息傳送系統。新策略KOR+由三部分組成：①新成員所需的一切新密鑰均用其個體密鑰來加密，其余每個新密鑰均單獨加密；此款與KOR一致；②對于成員加入情形，服務器利用子組組播方式，根據組成員“需要則及早”的原則發送密鑰更新信息；此款與GOR類似；③服務器根據解密代價的大小，從大至小地依次發送密鑰更新消息的有效載荷。基于該策略，我們下面就成員加入(J)及離開(L)密鑰樹的情形分別建立相應的密鑰更新協議。

2．1 KOR+(J)協議

3平均加密代價及最優密鑰樹度數

密鑰服務器的加密代價是指被加密的密鑰的個數[4，5]。對于滿的平衡樹，由KOR和KOR₊協議，它們的加密代價均為 h+h=2h(加入)、(h-1)d+(d-1)=hd-1(離開)；它們的密鑰更新消息數均為h+1(加入)、h(d-1) (離開)。與KOR相比，KOR₊另有兩個優勢：①對于KOR+(J)協議，通過充分利用子組組播方式，服務器無需存儲用于不同密鑰更新消息中需要加密的新密鑰（如例1中的 {k_1-8}k_1-8），從而節約了存儲空間；②因為只有當新加入成員或與離開者同屬一子組的所有成員把最長的密鑰更新消息解密之后，下一階段的安全組通信才能恢復[6]，故按照KOR₊的兩個協議，通過優先發送解密操作最多的密鑰更新消息，可以縮短密鑰更新的整體處理時間。

另外，UOR的加密代價[4]為 h(h+3)/2(加入)、h(h+1)(d-1)/2 (離開)。在分析平均情形下的計算復雜性時，通常假定[4～6]成員請求加入或離開組是等概率的；對大型組播組，組的大小n=d_h 是一充分大的常量。因此，在KOR₊、UOR中服務器的平均每次（加入/離開）請求的加密代價分別為

s₁=(hd+2h-1)/2， s₂=h(hd+d+2)/4 

值得注意的是，文獻[4]中的斷言“在成員離開情形，KOR及GOR的加密代價都為 d(h-1) ” 是不成立的；應都為hd-1 。但我們仍有

定理1（KOR₊）:在滿和平衡的d叉密鑰樹中，服務器的平均加密代價s₊在d=4時取得最小值。

證明:類似于文獻[5]中KOR的情形。

下面我們再考察UOR的情形。

定理2（UOR）:在滿和平衡的 d叉密鑰樹中，服務器的平均加密代價s₂當n≥2 692時在d=7 取得最小值。

證明：令h=log_dn=N/lnd，其中N=lnn則s₂可改寫為

N(Nd+(d+2)lnd)/(4ln₂d)

綜合以上三個條件不等式結果，即完成了定理2的證明。

R.D.Pietro等人[6]在研究成員離開情形時發現，使密鑰更新完成時間（Rekeying Completion Time，RCT）最小的密鑰樹度數不是唯一的，而與通信帶寬和用戶端計算能力有關。鑒于從用戶端的角度看，UOR提供最佳的性能，而且對于通過調制解調器低速連接到網絡的大型組播組，KOR或UOR比GOR更為合適[4]，上述兩個定理具有一定的理論價值和實際意義。

4結論

（1）與KOR相比，KOR₂在保持密鑰更新消息數和加密代價相同的情況下，另有兩個優勢：①對成員加入情形，采用KOR₂協議的密鑰服務器通過利用子組組播可以節約存儲空間。②按照KOR₂協議，服務器通過優先發送解密操作最多的密鑰更新消息可以縮短密鑰更新過程的整體處理時間。

參考文獻：

[1]蔣國瑞，趙書良.基于MultiAgent和Ontology的技術性貿易壁壘預警預測系統設計［J］.計算機工程與應用，2004，40(27):192-195.

[2]蔣國瑞.TBT對我國走新型工業化道路的影響及其對策［J］.國際經貿探索，2004，20(2):59-62.

[3]胡舜耕，等.面向自動文摘的多Agent系統中的協調算法研究［J］.計算機研究與發展，2001，38(11):1302-1309.

[4]Sycara K P. MultiAgent Systems［J］.AI，1999，2(19)：79-92.

作者簡介：蔣國瑞(1954-)，男，河北蠡縣人，副院長，教授，博士后，研究方向為管理信息系統和決策支持系統、技術性貿易壁壘等；任榮平(1981-)，男，湖北宜昌人，碩士研究生，研究方向為信息管理與信息系統。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。