移動(dòng)自組網(wǎng)的組密鑰鏈更新算法

陳 蹊 ， 趙躍龍

（華南理工大學(xué) 計(jì) 算機(jī)科學(xué)與工程學(xué)院，廣東 廣 州510006）

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

移動(dòng)通信設(shè)備以及無(wú)線網(wǎng)絡(luò)的高速發(fā)展為移動(dòng)網(wǎng)絡(luò)的應(yīng)用提供了發(fā)展平臺(tái)，例如：野外活動(dòng)、救災(zāi)工作、軍事行動(dòng)等。而移動(dòng)自組網(wǎng)更是成為快速建立通信網(wǎng)絡(luò)的有效途徑。移動(dòng)自組網(wǎng)絡(luò) （Mobile Ad hoc Network，MANET）是一種不依賴于任何固定基礎(chǔ)設(shè)施的新型無(wú)線網(wǎng)絡(luò)。與需要中心控制的設(shè)備，如基站或訪問(wèn)服務(wù)點(diǎn)的蜂窩移動(dòng)通信網(wǎng)絡(luò)和無(wú)線局域網(wǎng)相比，移動(dòng)自組網(wǎng)絡(luò)具有自組性、多跳性、無(wú)基礎(chǔ)設(shè)施要求、易鋪設(shè)等特點(diǎn)。同時(shí)移動(dòng)自組網(wǎng)也具有不穩(wěn)定、不可靠、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化頻繁、連接短暫等缺點(diǎn)[2-5]。

1 傳統(tǒng)組密鑰算法

組密鑰管理為網(wǎng)絡(luò)中的組成員生成、分發(fā)和更新組密鑰。組密鑰是所有組成員都知道的密鑰，被用來(lái)進(jìn)行加密/解密或者認(rèn)證，以滿足保密、組成員認(rèn)證等需求。因此，組密鑰管理可以看成是一種組成員會(huì)話權(quán)限控制技術(shù)。通過(guò)對(duì)組密鑰的管理，能夠有效地完成對(duì)組成員會(huì)話權(quán)限的動(dòng)態(tài)授權(quán)與回收。組密鑰管理至少需要具有前向安全、后向安全和抵抗合謀破解的能力。

根據(jù)拓?fù)浣Y(jié)構(gòu)的不同，可以把組密鑰管理方案分為3大類：集中式、分布式和分層分組式[2]。集中式組密鑰管理主要是由一個(gè)組管理器（group controller，GC）執(zhí)行密鑰的生成分發(fā)和更新。這種架構(gòu)能夠很好地管理組成員的密鑰，實(shí)現(xiàn)諸如節(jié)點(diǎn)身份認(rèn)證、密鑰生成、實(shí)時(shí)監(jiān)控等功能。但是集中式的管理方式對(duì)GC的依賴性太強(qiáng)，容易出現(xiàn)單點(diǎn)失效的問(wèn)題。分布式組密鑰管理中，參與組播的成員的關(guān)系是對(duì)等的，他們共同參與組密鑰的生成和管理?？朔思惺絾吸c(diǎn)失效的問(wèn)題，是動(dòng)態(tài)組播密鑰管理的較好方案。而分層分組式組密鑰管理則是前兩者的結(jié)合，其架構(gòu)是將各節(jié)點(diǎn)分成多組，組內(nèi)進(jìn)行分布式密鑰管理，而組與組之間則采用集中式密鑰管理。

移動(dòng)自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)具有多變性，一個(gè)節(jié)點(diǎn)的加入和退出都要引起組密鑰的更新。本設(shè)計(jì)在分布式組密鑰管理的基礎(chǔ)上進(jìn)行改進(jìn)。運(yùn)用密鑰鏈以及左向性共享密鑰與右向性共享密鑰的設(shè)計(jì)減少密鑰的更新次數(shù)，但這樣需要一定的存儲(chǔ)開銷。

2 DKCGR組密鑰算法設(shè)計(jì)

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

2.1 密鑰鏈生成

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

圖1 8節(jié)點(diǎn)密鑰鏈結(jié)構(gòu)

2.2 左/右向性密鑰生成

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

圖2左/右向性密鑰

2.3 初始組密鑰生成

密鑰鏈建立好后，將key12組密鑰K。這里并不采用DH的傳統(tǒng)算法，即將所有Keyij都作模指運(yùn)算生成最終的組密鑰。因?yàn)檫@樣將消耗極大的計(jì)算時(shí)間，隨著節(jié)點(diǎn)數(shù)的增多，擴(kuò)展性便會(huì)降低。雖然采用Key12作為組密鑰有可能會(huì)被破解，但在一定時(shí)間段內(nèi)破解的可能性不大，因?yàn)橐平釪H算法需要很長(zhǎng)的一段時(shí)間；而考慮到移動(dòng)自組網(wǎng)的動(dòng)態(tài)性，每次節(jié)點(diǎn)的退出和加入都會(huì)引起組密鑰的更新，所以，在還未破解原密碼前，新密碼就已產(chǎn)生了，從而大大加強(qiáng)了組播的安全性。

2.4 節(jié)點(diǎn)的加入與退出

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

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

圖3 8節(jié)點(diǎn)密鑰鏈結(jié)構(gòu)

根據(jù)以上方案可知，若退出節(jié)點(diǎn)的ID號(hào)為偶數(shù)，那么在步驟3和5時(shí)，組密鑰被組播到所有的奇數(shù)節(jié)點(diǎn)。各奇數(shù)節(jié)點(diǎn)再通過(guò)共享密鑰把組密鑰通過(guò)單播的方式傳到相鄰的偶數(shù)節(jié)點(diǎn)。這樣就實(shí)現(xiàn)了所有組密鑰的更新，因而保證了向前保密性。

3 方案實(shí)現(xiàn)

1）密鑰鏈的生成n表示節(jié)點(diǎn)的個(gè)數(shù)；DH（i，j）為一次模指運(yùn)算，計(jì)算出一個(gè)共享密鑰；K為組密鑰。

4 系統(tǒng)分析

在分析組播密鑰管理方案中，主要要考慮的是：組密鑰管理的安全性，密鑰變更時(shí)的計(jì)算復(fù)雜度和通信量，節(jié)點(diǎn)的負(fù)載以及存儲(chǔ)開銷等。以下將對(duì)本設(shè)計(jì)的相關(guān)方面作具體的分析。

4.1 安全性分析

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

2）向后保密性確保新加入的組成員無(wú)法破解它加入前的組播報(bào)文[2]。根據(jù)上文所述的節(jié)點(diǎn)加入方案，當(dāng)節(jié)點(diǎn)加入時(shí)，該節(jié)點(diǎn)便與ID1共同生成一個(gè)新的組密鑰K′。但是新節(jié)點(diǎn)并不具備原來(lái)的組密鑰K，用K加密K′后組播給其他節(jié)點(diǎn)便可。

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

4.2 系統(tǒng)資源開銷分析

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

本設(shè)計(jì)與經(jīng)典的LKH算法相比，在計(jì)算次數(shù)上是一個(gè)常數(shù)，而LKH的計(jì)算次數(shù)會(huì)因?yàn)楣?jié)點(diǎn)的增多而增加。在存儲(chǔ)開銷上，LKH比DKGR需要的少。在通信量方面，LKH用的是樹形結(jié)構(gòu)，為組播節(jié)省了一些通信量。DKGR由于要進(jìn)行n/2次單播，所以通信量稍大，但是本文會(huì)在后面提出改進(jìn)的方法。

4.3 算法改進(jìn)

目前流行的組密鑰管理方法主要采用樹形結(jié)構(gòu)，也就是LKH密鑰數(shù)結(jié)構(gòu)。本設(shè)計(jì)受LKH結(jié)構(gòu)的啟發(fā)采用森林結(jié)構(gòu)。具體結(jié)構(gòu)是：將每4個(gè)節(jié)點(diǎn)分為一組作為一個(gè)根節(jié)點(diǎn)的葉子節(jié)點(diǎn)。每一子組有一個(gè)子組密鑰，如圖4所示。

圖4 樹形圖密鑰結(jié)構(gòu)

當(dāng)需要組密鑰更新時(shí)，由產(chǎn)生新的組密鑰的節(jié)點(diǎn)用Key14將新組密鑰K′加密后組播給本組的成員。假設(shè)圖中ID1節(jié)點(diǎn)組播K′后，由ID4用共享密鑰把K′傳給ID5。ID5再用Key58組播給子組成員。采用這種結(jié)構(gòu)有2個(gè)好處：1）能夠進(jìn)一步減少同謀破解的概率，因?yàn)?個(gè)成員必須要在一個(gè)子組盡可能破解所有密鑰；2）減少單播的次數(shù)，用2次組播代替n/4次組播代替n/2次，減少了通信量。

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

本文提出的DKGR算法是在密鑰鏈[8]和左右向性密鑰[9]的基礎(chǔ)上進(jìn)行了融合和改進(jìn)，吸取了兩者的優(yōu)勢(shì)，通過(guò)增加少量的存儲(chǔ)成本減少通信量。本算法與傳統(tǒng)的密鑰鏈算法相比，增加少量的存儲(chǔ)開銷，從而減少網(wǎng)絡(luò)通信量。在分布式自組網(wǎng)的環(huán)境下，針對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的頻繁改動(dòng)，在快速更新組密鑰的前提下，減少整個(gè)網(wǎng)絡(luò)的通信量，提高整個(gè)網(wǎng)絡(luò)的健壯性。因此，該算法在小型移動(dòng)自組網(wǎng)中的組密鑰管理是行之有效的。

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

[2]徐恪，徐明偉，董曉虎.組播密鑰管理的研究進(jìn)展[J].軟件學(xué)報(bào)，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].計(jì)算機(jī)應(yīng)用研究，2006（08）：142-154.

[8]林林，李學(xué)明，陳勇.無(wú)線網(wǎng)絡(luò)中動(dòng)態(tài)組密鑰管理方案[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（5）：133-136.

[9]唐揚(yáng)，蘭巨龍.一種新的組密鑰管理算法[J].計(jì)算機(jī)科學(xué)，2008，135（111）：89-93.