移動自組網的組密鑰鏈更新算法

陳 蹊 ， 趙躍龍

（華南理工大學 計 算機科學與工程學院，廣東 廣 州510006）

網絡數據的傳輸分為單播、廣播、組播3種方式。單播傳輸方式在發送者和每一個接收者之間實現點對點的網絡連接。如果一位發送者同時向多位接收者傳輸相同的數據，即使在相同的鏈路上也必須相應復制多份相同的數據包，每一個接收者接收一個數據包的副本。而廣播傳輸是指在IP子網內廣播數據包，所在子網內的主機都要收到一份數據包，不論這些主機是否愿意接收該數據包。近年來，隨著網絡和視頻/音頻技術的迅速發展，高帶寬的應用和多媒體業務越來越多，諸如遠程教學、視頻會議、視頻點播、網絡游戲等新興的網絡應用。組播就是順應這種需求產生的。組播通信是指在發送者和多個接收者之間實現點對多點的網絡連接，是“一對一組”的通訊模式，它通過使用特定的IP組播地址，把同一數據包從一臺主機傳送到由若干臺主機組成的組播組的每一個成員。組播傳輸不僅節省網絡資源，還可有效控制子網中接收組播信息的用戶[1]。

移動通信設備以及無線網絡的高速發展為移動網絡的應用提供了發展平臺，例如：野外活動、救災工作、軍事行動等。而移動自組網更是成為快速建立通信網絡的有效途徑。移動自組網絡 （Mobile Ad hoc Network，MANET）是一種不依賴于任何固定基礎設施的新型無線網絡。與需要中心控制的設備，如基站或訪問服務點的蜂窩移動通信網絡和無線局域網相比，移動自組網絡具有自組性、多跳性、無基礎設施要求、易鋪設等特點。同時移動自組網也具有不穩定、不可靠、網絡拓撲結構變化頻繁、連接短暫等缺點[2-5]。

1 傳統組密鑰算法

組密鑰管理為網絡中的組成員生成、分發和更新組密鑰。組密鑰是所有組成員都知道的密鑰，被用來進行加密/解密或者認證，以滿足保密、組成員認證等需求。因此，組密鑰管理可以看成是一種組成員會話權限控制技術。通過對組密鑰的管理，能夠有效地完成對組成員會話權限的動態授權與回收。組密鑰管理至少需要具有前向安全、后向安全和抵抗合謀破解的能力。

根據拓撲結構的不同，可以把組密鑰管理方案分為3大類：集中式、分布式和分層分組式[2]。集中式組密鑰管理主要是由一個組管理器（group controller，GC）執行密鑰的生成分發和更新。這種架構能夠很好地管理組成員的密鑰，實現諸如節點身份認證、密鑰生成、實時監控等功能。但是集中式的管理方式對GC的依賴性太強，容易出現單點失效的問題。分布式組密鑰管理中，參與組播的成員的關系是對等的，他們共同參與組密鑰的生成和管理。克服了集中式單點失效的問題，是動態組播密鑰管理的較好方案。而分層分組式組密鑰管理則是前兩者的結合，其架構是將各節點分成多組，組內進行分布式密鑰管理，而組與組之間則采用集中式密鑰管理。

移動自組網的拓撲結構具有多變性，一個節點的加入和退出都要引起組密鑰的更新。本設計在分布式組密鑰管理的基礎上進行改進。運用密鑰鏈以及左向性共享密鑰與右向性共享密鑰的設計減少密鑰的更新次數，但這樣需要一定的存儲開銷。

2 DKCGR組密鑰算法設計

分布式密鑰鏈更新算法（Distributed Key-chain Group Rekeying，DKCGR）的符號定義如下：n表示節點數；ID表示節點的唯一標識；keyij表示節點i和節點j之間的共享密鑰，用DH算法生成[6]；Li和Ri分別表示左向性密鑰和右向性密鑰；K表示組密鑰；{m}K是用密鑰K加密消息m；

2.1 密鑰鏈生成

基于移動自組網中的節點是分布式拓撲結構，節點彼此之間是對等關系，這里將這些節點按邏輯方式排列成一排并進行編號，即ID號。排列方式可按照地理分布排列[7]。由于移動節點不僅存在信號強弱問題，還存在功率、電量等不穩定因素。因此，組成員越集中，網絡的信號將越強。在此，可以假設按照各節點在場景中心附近的移動概率來排列。相鄰成員采用DH密鑰協商，每2個成員之間共享1個密鑰，從而可以通過成員之間的共享密鑰作為傳遞信息的通道，該通道稱為密鑰鏈。密鑰鏈的具體生成算法如下：節點IDi分別與左鄰IDi－1右鄰IDi+1用DH算法計算出key（i－1）i和keyi（i+1）（1＜i＜n）。而處于邊界的節點，即ID1和IDn也進行一次DH算法生成Key1n，如此便生成一個循環的密鑰鏈。因為密鑰鏈的生成由各個節點共同完成，所以相當于是并行計算密鑰鏈，故整條鏈的生成時間只用了一次DH算法的時間。圖1所示是8個節點完成密鑰鏈后的結構。

圖1 8節點密鑰鏈結構

2.2 左/右向性密鑰生成

在一個組播組中，根據節點的個數n生成n個左向性共享密鑰和n個右向性共享密鑰，但并不是每個節點都保存這兩組密鑰。節點IDi保存的左向性密鑰有Lj（j=i+2k，i＜j＜n，k=1，2，3…），同時保存Rj（j=i－2k，1＜j＜i，k=1，2，3…）。當j+2＞8或j－2＜1時，不生成密鑰。以8個節點為例，如圖2所示。

圖2左/右向性密鑰

2.3 初始組密鑰生成

密鑰鏈建立好后，將key12組密鑰K。這里并不采用DH的傳統算法，即將所有Keyij都作模指運算生成最終的組密鑰。因為這樣將消耗極大的計算時間，隨著節點數的增多，擴展性便會降低。雖然采用Key12作為組密鑰有可能會被破解，但在一定時間段內破解的可能性不大，因為要破解DH算法需要很長的一段時間；而考慮到移動自組網的動態性，每次節點的退出和加入都會引起組密鑰的更新，所以，在還未破解原密碼前，新密碼就已產生了，從而大大加強了組播的安全性。

2.4 節點的加入與退出

新節點的加入比較簡單。具體過程如下：假設新節點為IDm（m=n+1），則IDm與IDn生成共享密鑰Keynm，再與ID1生成Key1m，并按照左右向性密鑰算法給IDm生成左右向性密碼；同時，Key1m便成為新的組播密碼K′，ID1用K加密K′即{K′}K并組播給其他組員，從而保證了組密鑰的向后保密性。

當有節點退出組播組時，假設在有8個成員的組播組，ID4號成員退出時如圖3所示，將按以下步驟進行：1）把ID3和ID5用一次DH算法計算出它們的共享密鑰Key35；同時廢除Key34與Key45；2）將Key35作為新的組密鑰K′；3）ID3節點執行的操作：{K′}L5，并進行組播；4）ID5節點執行的操作：{K′}R3，并進行組播；5）得到組密鑰的節點，再通過與鄰居的共享密鑰，把K′傳給鄰居節點，從而完成組密鑰更新。

圖3 8節點密鑰鏈結構

根據以上方案可知，若退出節點的ID號為偶數，那么在步驟3和5時，組密鑰被組播到所有的奇數節點。各奇數節點再通過共享密鑰把組密鑰通過單播的方式傳到相鄰的偶數節點。這樣就實現了所有組密鑰的更新，因而保證了向前保密性。

3 方案實現

1）密鑰鏈的生成n表示節點的個數；DH（i，j）為一次模指運算，計算出一個共享密鑰；K為組密鑰。

4 系統分析

在分析組播密鑰管理方案中，主要要考慮的是：組密鑰管理的安全性，密鑰變更時的計算復雜度和通信量，節點的負載以及存儲開銷等。以下將對本設計的相關方面作具體的分析。

4.1 安全性分析

1）向前保密性確保組成員在退出組后，除非重新加入，否則無法再參與組播，包括獲知組播報文的內容和發送加密報文[2]。如圖3所示，當一個節點退出組后，首先斷絕其與左右鄰建立的共享密鑰，這樣左右鄰都無法將新的組密鑰傳給退出的節點。接下來ID3用L5加密新的組密鑰K′，ID5用R3加密K′。而ID4不具有這兩個密鑰，所以也就無法破解出新的組密鑰。

2）向后保密性確保新加入的組成員無法破解它加入前的組播報文[2]。根據上文所述的節點加入方案，當節點加入時，該節點便與ID1共同生成一個新的組密鑰K′。但是新節點并不具備原來的組密鑰K，用K加密K′后組播給其他節點便可。

3）防御同謀破解避免（或減少發生的概率）多個組員聯合起來破解系統[2]。在本設計中，能夠進行同謀破解的關鍵在于左/右向性密碼。一個組播組的左向性密鑰和右向性密鑰之和為2n個。一個節點保存有左右向性密碼（n/2）－1個。以8節點為例，每個節點共保存有3個左或者右向性密碼。見圖2，要完全破解兩組向性密鑰，最理想的狀態為ID1，ID2，ID7，ID8都是同謀才能破解組密鑰，這已達到組成員的一半，而能夠在這4個位置上的概率還不足0．6%，還不包括身份認證程序的失敗率（身份認證在本設計中暫時不討論）。

4.2 系統資源開銷分析

首先考慮節點加入時，更新密鑰所需的計算量。當IDm節點加入時，ID1與IDm需要用DH算法計算出組密鑰K′，再用K加密K′。總共2次計算。而更新密鑰所要進行的操作就是組播K′。當節點退出時，不僅要生成新的組密鑰K′，還要對其分別用左右向性共享密鑰加密。之后，再通過2次組播和1次與相鄰節點的單播通信。本設計的特點是盡可能的減少了計算次數與通信消息數，同時將計算的負載和通信的負載都分布到各個節點上去，但也增加了密鑰數的存儲空間。在本方案中，每個節點都要存儲n/2+2個密鑰，其中包括組密鑰，n/2－1個左右向性密鑰，2個鄰居密鑰。但隨著移動設備技術的發展，這些存儲開銷是可以接受的。

本設計與經典的LKH算法相比，在計算次數上是一個常數，而LKH的計算次數會因為節點的增多而增加。在存儲開銷上，LKH比DKGR需要的少。在通信量方面，LKH用的是樹形結構，為組播節省了一些通信量。DKGR由于要進行n/2次單播，所以通信量稍大，但是本文會在后面提出改進的方法。

4.3 算法改進

目前流行的組密鑰管理方法主要采用樹形結構，也就是LKH密鑰數結構。本設計受LKH結構的啟發采用森林結構。具體結構是：將每4個節點分為一組作為一個根節點的葉子節點。每一子組有一個子組密鑰，如圖4所示。

圖4 樹形圖密鑰結構

當需要組密鑰更新時，由產生新的組密鑰的節點用Key14將新組密鑰K′加密后組播給本組的成員。假設圖中ID1節點組播K′后，由ID4用共享密鑰把K′傳給ID5。ID5再用Key58組播給子組成員。采用這種結構有2個好處：1）能夠進一步減少同謀破解的概率，因為4個成員必須要在一個子組盡可能破解所有密鑰；2）減少單播的次數，用2次組播代替n/4次組播代替n/2次，減少了通信量。

5 結束語

本文提出的DKGR算法是在密鑰鏈[8]和左右向性密鑰[9]的基礎上進行了融合和改進，吸取了兩者的優勢，通過增加少量的存儲成本減少通信量。本算法與傳統的密鑰鏈算法相比，增加少量的存儲開銷，從而減少網絡通信量。在分布式自組網的環境下，針對網絡拓撲結構的頻繁改動，在快速更新組密鑰的前提下，減少整個網絡的通信量，提高整個網絡的健壯性。因此，該算法在小型移動自組網中的組密鑰管理是行之有效的。

[1]屈勁，葛建華，蔣銘.安全組播密鑰批更新算法研究[J].電子學報，2003，31（7）：1046-1048.

[2]徐恪，徐明偉，董曉虎.組播密鑰管理的研究進展[J].軟件學報，2004，15（1）：141-150.

[3]Zhou L D，Hass Z J.Securing in ad-hoc networks[J].IEEE Networks，1999，13（6）：24-30.

[4]Wong C K，Gouda M，Lam S.Secure group communications using key graphs[J].IEEE/ACM Transactions on Networking（TON），2000，8（1）：16-30.

[5]Basagni S，Herrin K，Bruschi D，et al.Secure pebblenets[M].In:Proc.of the 2001 ACM Int'l Symp.on Mobile Ad Hoc Networking and Computing，New York:ACM Press，2001.

[6]Diffe W，Hellman M E.New directions in cryptography[J].IEEE Trans.Inform.Theory，1976，IT222:6442654.

[7]秦科，周明天，劉乃琦.組播密鑰管理方案的新研究[J].計算機應用研究，2006（08）：142-154.

[8]林林，李學明，陳勇.無線網絡中動態組密鑰管理方案[J].計算機工程與應用，2007，43（5）：133-136.

[9]唐揚，蘭巨龍.一種新的組密鑰管理算法[J].計算機科學，2008，135（111）：89-93.