一種安全的多層移動自組網密鑰管理方案

施榮華，袁倩

(中南大學 信息科學與工程學院，湖南 長沙，410083)

移動自組網 MANET(Mobile ad hoc networks)是由多個移動節點通過無線鏈路連接，具有時變拓撲結構的多跳、臨時性自治系統[1?2]，被廣泛應用于軍事戰場和交互式信息共享等。由于其應用的特殊性，移動自組網的安全性能越來越受到人們的關注。移動自組網又分單層和多層2種結構，其中，單層移動ad hoc網絡的網絡規模受限且維護路由的網絡開銷太大，使得網絡的效率較低和可擴展性較差[3?5]。與此相比，多層移動ad hoc網絡中包含具有不同功能的多種節點。可以根據節點的自身特點賦予不同的網絡角色。這使得多層結構除了具有較好的擴展性外，網絡的路由開銷也大大減少，從而具有較高的效率。此外，引入多層結構還便于實施網絡管理。針對動態網絡的密鑰管理，研究者們提出了很多方案及相關通信協議[6?9]，且這些方案中有許多應用分級結構[10]，基本的密鑰重分發算法和分級架構常把密鑰管理范圍分為較小的模塊，再分別進行管理。另外，公鑰密鑰體系[11]、多點傳送及基礎樹算法在相關方案中得到應用。Steiner等[12]提出了一個名為CLIQUES的方案，該方案采用了密鑰協商和一個順序傳遞密鑰信息的線性邏輯結構。在該方案中，每2個節點間必須有1個交換密鑰，這樣對每個節點的存儲量要求太高，且群密鑰的生成步驟太多，安全性較低；Tseng等[13]提出了一個名為SGCP的方案，有利于移動自組網中的安全通信。該方案中的通信以群結構為基礎并應用了無線架構，在這個架構中，每個節點的傳送能力都是1跳節點，負荷量最大即1跳鄰居節點數最多的節點被選為多點傳送中的路由器，這些被選出來的節點是以后構建的群的中心。群建好以后，路由器能自己生成群密鑰并能在數據傳送過程中對相關的加密數據進行解密操作。但由于在方案中所有節點加解密用的是統一的群密鑰，所以，一旦有節點加入或退出，架構必須重新生成群密鑰，以保證安全性，重分發密鑰次數較多，資源浪費較大。為此，本文作者提出1個利于群安全通信的多層移動自組網密鑰管理方案。該方案采用雙層架構將網絡劃分為2層。根據節點信息，各層又被分為不同的子群，每個子群都有1個群首來管理該子群中所有節點的信息，并生成與傳遞該子群的群密鑰，由此而簡化了群結構的管理，降低了對節點存儲量的要求，減少了密鑰重分發的次數。此外，方案中對 1個將要被傳送的數據包可先后用節點間的交換密鑰及群密鑰進行雙重加密，有效地解決了網絡通信中前向安全與后向安全的問題，提高了網絡通信的安全性。

1 分層密鑰管理方案

移動自組網中頻繁變動的拓撲結構會引起節點不斷移動，如何構造及維護一個群是一項復雜的問題。假設1個節點要傳送1個信息給1個2跳鄰居節點，這時，該節點便會收集它所有2跳節點的相關信息，然后，根據這些相關信息來設計傳送路徑及構造群結構。

1.1 密鑰管理

本方案構建了1個兩層架構。第1層(稱為L1子群)由所有節點構成；第2層(稱為 L2子群)則在形成L1子群后根據存儲在L1子群的所有剩余節點的信息劃分而成。方案在各子群中都會選出負荷量最大的節點作為該子群的群首[10]，以管理群信息以及生成和傳送群密鑰。第 1層中子群的群首記為 L1-head，第 2層中子群的群首記為L2-head。圖1所示為節點間群密鑰的傳輸過程。

下面分別討論L1-head和L2-head的生成過程。

L1-head的生成過程為：

(1) 每個節點向 2跳范圍內的鄰居節點傳送信息的同時，附帶傳送各自負荷量。

(2) 收集各個節點的負荷量，選出負荷量最大的節點為L1-head。

(3) 其余節點向L1-head發送所有相關信息，并到L1-head注冊。

L2-head的生成過程為：

(1) 所有節點把本地信息發送給L1-head。

(2) 收到所有的信息后，L1-head根據相關信息把除自身外的其他節點分成子群，標為L2子群。

(3) 每個L2子群中的節點再分別比較各自的負荷量，負荷量最大的被選為該 L2子群的群首，標為L2-head，負責與L1-head及其他的L2-head進行通信。

圖1 節點間群密鑰的傳輸Fig.1 Subgroup key transmission operation between nodes

當群關系建立好以后，所有的節點將注冊信息發送給L1-head。L1-head存儲好 L1子群中所有節點的信息后，采用RSA算法生成L1子群群密鑰L1GK，并將L1GK傳送給子群中的所有節點，節點可用它來加密所要傳遞的信息。

為了提高子群中信息傳輸的安全性，將除L1-head外的所有節點分成幾個L2子群，每個L2子群都含有1個群首L2-head，且子群中的節點由L2-head進行管理。每個L2子群都擁有它們各自的群密鑰(L2GK)。其中，L2GK由已知的L1GK經計算而得到。因此，只有L2-head及它下面管理的各普通節點知道本子群的L2GK。對于子群之間的通信，利用DH協議獲取安全性。首先利用子群中的通信節點來聯系鄰居子群，在此過程中通信節點先將信息傳送給L1-head以得到2個不同子群中的節點i和節點j之間的通信密鑰Kc，然后，Kc將被用來加解密需在不同子群中傳送的信息。當L2-head知道目的節點的位置后，便會利用DH協議生成 1個只屬于源節點和目的節點的交換私鑰KDH，KDH被用于對所要傳遞的信息進行最初加密。

圖2所示為數據包傳遞過程中的加密和解密操作過程。在圖2中，假設節點A要傳送1個數據包給節點 D，路徑及目的節點都已知。首先，A將利用 DH協議生成1個交換密鑰KDH，并用它先加密數據包；接著，利用L2GK1,1對數據包進行第2次加密，并把加密后的數據包傳送給L2-head即H1,1。H1,1將先用L2GK1,1對收到的數據進行解密，然后，用L1GK1對數據進行加密，最后，將它傳送給H1,2。H1,2收到數據包后，先用L1GK1對數據進行解密，再用L2GK1,2對數據進行加密，然后，數據包傳送給節點 B。節點B收到數據包后先用L2GK1,2對數據進行解密，再用交換密鑰Kc對數據進行加密，然后，傳送給節點C。經過一系列重復加密與解密操作后，數據包最終被傳到目的節點D。收到數據包后，節點D先用 L2GK1,2解密，然后，用KDH解密以獲得最初的信息。

1.2 群密鑰的維護

下面討論當移動自組網的網絡拓撲變化引起節點移動時群密鑰的維護過程。

圖2 數據傳輸中的加密與解密過程Fig.2 Encryption and decryption operation during data transmission

1.2.1 子群中新節點的加入過程

移動自組網中節點會頻繁地進行移動。假設每個新加入的節點都是安全節點。當1個新節點要加入某個子群時，群首只需要重新生成1個群密鑰，然后，分發給各節點。

1個新節點加入某個子群的具體過程為：

(1) 新節點發送加入的請求信息給子群中的鄰居節點。

(2) 相關鄰居節點收到請求信息后再把它轉發給群首L2-head。

(3) L2-head發送1個回復信息給新節點。

(4) 新節點收到回復信息并被允許加入子群。

(5) L2-head在更新子群信息的同時將重新生成L2子群群密鑰，并把新的群密鑰發送給子群中所有的節點。

1.2.2 子群中節點的離開過程

普通節點的離開過程較簡單，只需它所在的子群L2-head重新生成1個L2GK，而其他子群的節點密鑰都沒有改變。具體步驟如下：

(1) 普通節點的離開過程。

① 在普通節點離開子群以前，先發送1個離開信息給它所屬子群的L2-head。

② L2-head收到節點的離開信息后，發送1個回復信息給將要離開的節點，然后更新子群信息，同時重新生成1個群密鑰，再將新的群密鑰發送給子群中剩余的節點。

(2) 節點L2-head 的離開過程。

對于L2-head的離開，方案將從子群中剩余的普通節點中選出負荷量最大的節點作為新的群首L2-head。接著，子群中所有的其他節點會到新的L2-head進行注冊，并將自身的相關信息發送給新的L2-head。具體步驟如下：

① 在離開以前，L2-head分別向子群中的所有節點和所屬的L1-head發送1個離開信息。收到L2-head的信息后，普通節點和L1-head都會發送回復信息給L2-head。若L2-head在某段時期內沒有收到回復信息，則會向沒有反應的節點重新發送。

② L2子群中由L2-head管理的普通節點將會通過比較各自的負荷量來選出新的 L2-head，將負荷量最大的節點作為新的L2-head。

③ 新的L2-head將L2子群的更新信息發送給所屬管理的L1-head。

④ L1-head收到新的L2-head發送來的群更新信息后，生成1個新的群密鑰L1GK，并發送給它所管理的所有L2-head。

⑤ 每個L2-head從L1-head處收到新的L1群密鑰后，也會在本地生成1個新的群密鑰，并發送給本子群中的所有節點。

對于 L1-head的離開，方案先從該群所有的L2-head中選出負荷量最大的節點作為新的L1-head，然后，其余的L2-head到新的L1-head處注冊，并將相關信息發送給 L1-head。而被選為新的 L1-head的L2-head以前所管理的L2子群則按上述節點L2-head離開的情況重新進行組織。

(3) 節點L1-head 的離開過程。

① L1-head發送離開信息給它所管理的L2-head，收到信息后L2-head發送回復信息。若L1-head在某段時期內沒有收到某些L2-head的回復信息，則對這些節點進行重發。

② 收到L1-head的離開信息后，所有L2-head比較各自的負荷量，最大的那個被選出來作為該群的新L1-head。

③ 新的L1-head節點以前管理的L2子群中的普通節點，比較各自的負荷量，選出負荷量最大的節點作為該L2子群的新L2-head。

④ L1子群中所有的L2-head將各自管理的L2子群信息發送給新的L1-head，進行注冊。

⑤ 新L1-head在收到所有的L2-head信息后，生成1個新的L1群密鑰L1GK，然后，將它發送給該群中所有的L2-head。

⑥ 各L2-head在收到新的L1GK后，重新生成1個群密鑰，發送給群中的各普通節點。

上面討論的是節點正常離開的情形，在移動自組網中，節點移動頻繁，甚至會突然消失，這會使群維護困難且不能有效地傳送數據。下面討論發生特殊情況時方案采取的措施。

情況 1：離開節點沒有發送任何離開信息而突然消失。在本方案中，L1-head會在固定的時間內向群內的L2-head發送相關信息以取得聯系，L2-head也會向群內的普通節點發送相關信息取得聯系。若某個節點突然沒反應，則該子群便會進行重組織，生成新的群密鑰。

情況 2：節點在不同的子群間不斷移動。節點的頻繁移動會引起子群不斷地生成不必要的新的群密鑰，造成資源浪費。為了防止這種情況，當1個節點加入或者離開某個子群時，采取讓子群群首過一段時間再生成新的群密鑰的措施。

2 安全性與時間復雜度分析

現階段快速的計算能力及現存的各種各樣的攻擊方法都會威脅到節點的安全，從而影響整個網絡的安全。保證網絡通信的安全性是密鑰管理方案的必備性能。

2.1 安全分析

2.1.1 前向安全

方案提出新節點在加入群以前不會收到群中以前傳送的任何信息。在群的維護中，新節點加入后，L2-head將生成新的群密鑰并傳送給新節點，新節點能用它來加密或者解密以后要傳遞的信息，但不能用于解密在節點加入群以前傳送的數據。因此，該方案很好地保證了網絡通信的前向安全。

2.1.2 后向安全

當1個節點離開后，該方案保證它再不能收到與子群有關的任何信息。這里分 3種情況討論節點的離開。

(1) L2子群中普通節點的離開。節點離開后，L2-head重分發新的群密鑰，這樣，離開后的節點便不能對新的信息解密。

(2) L2-head的離開。L2子群不但選出了新的L2-head，而且L1-head也生成了新的L1群密鑰，最后，所有的L2-head在收到新的L1群密鑰后又為本子群生成新的 L2群密鑰，即所有的群密鑰都發生了變化，離開后的 L2-head根本無法獲取后來會傳送的信息。

(3) L1-head的離開。對于這種情況，方案從L1-head管理的L2-head中選出新的群首，然后，所有的密鑰都重新生成，與情況(2)一樣，離開后的節點無法再對網絡中傳送的信息解密。因此，該方案很好地保證了后向安全。

2.2 時間復雜度分析

設m表示1個L2子群的總成員數，k為架構中L2-head的總個數，p為1個L1子群中的所有節點數。假設每個L2子群擁有相同的成員數，那么p=km+1。

2.2.1 L1-head中的密鑰存儲量

在方案提出的2層架構中，L1-head先生成1個L1GK并存儲，當L2子群結構布置好并生成L2子群密鑰L2GK后，L2-head把L2GK發送給L1-head進行存儲。因此，L1-head中存儲的密鑰總數為k+1個，其時間復雜度為O(m)。然而，CLQUES利用DH協議來生成密鑰，每2個節點間必須有1個交換密鑰，然后，由這些密鑰聯合生成群密鑰，所以，其時間復雜度為O(p)。與其他2個方案比較，這個方案中節點所需的存儲量是最大的。在SGCP方案中，加解密都用同一個群密鑰，所以，它的L1-head中存儲的密鑰數是最小的，時間復雜度為O(1)。

2.2.2 L2-head中的密鑰存儲量

在CLQUES和SGCP方案中，L2-head中沒有存儲任何密鑰。而在本方案中，L2-head存儲了2個密鑰：一個是用于聯系 L1-head和其他的 L2-head的L1GK，另一個是該L2子群群密鑰L2GK，用于子群內部通信。在這部分，方案的時間復雜度為O(1)。

2.2.3 普通節點的密鑰存儲量

在HKMS和SGCP中，普通節點只存儲了1個群密鑰。而在CLQUES中，每2個節點都有交換密鑰便于通信。群密鑰由這些通信密鑰聯合生成，因此，存儲在普通節點中的密鑰明顯比前 2種方案的密鑰要多。

2.2.4 新節點加入

當1個新節點加入群時，HKMS只需生成1個新的L2子群群密鑰(L2GK)，即只有該子群的成員數會發生變化，對其他子群沒有任何影響，時間復雜度為O(m)。然而，在其他2種方案中，一旦有新節點要加入群，則必須生成1個新的群密鑰并將它發送給所有的節點，時間復雜度為O(p)。

表1 時間復雜度比較Table 1 Time complexity comparison

2.2.5 節點離開

對于節點的離開，HKMS分3種情況：第1種是普通節點的離開，方案需為剩下的節點生成1個新群密鑰并分發，時間復雜度為 O(m)；另外 2種情況是L1-head和L2-head的離開，無論哪種情況，網絡中的第1層和第2層所有的群密鑰都需更新，時間復雜度都為O(p)。在CLQUES和SGCP方案中，無論哪個節點離開，整個網絡都必須生成新的群密鑰并分發給剩下的節點，時間復雜度也都為O(p)。

2.2.6 群內部通信

在CLQUES和SGCP方案中，對傳輸的數據包只需進行1次加密和解密。而在HKMS中，當數據在不同的L2子群中進行傳輸時，需進行2次加解密操作，耗費的時間比前2種所耗費的時間都要多。

在CLQUES中群密鑰的生成需經歷的步驟較多，與其他2種方案相比，其安全性較低。

3 結論

(1) 提出了 1個安全的分層移動自組網密鑰管理方案。該方案采用了1個雙層架構，將網絡節點分為2層，根據節點信息，各層又被分為不同的子群，每個子群都由 1個群首來管理該子群中所有節點的信息，并負責生成與分發該子群的群密鑰，而簡化了群結構的管理。

(2) 該方案通過雙重加密傳送信息來保證安全。當1個節點要傳送數據給另一節點時，相互之間能生成交換密鑰，在傳送數據的過程中，先用交換密鑰加密數據，再用群密鑰加密，提高了數據傳輸的安全性。

(3) 所提出的方案可以有效地減少移動自組網的網絡拓撲頻繁變化所引起的群密鑰重分發數，節省資源。

(4) 本方案與Tseng方案及Steiner方案相比，有效地簡化了群管理，對節點的存儲要求較低，且能有效地保證網絡通信的安全性。

[1]Macker J P, Corson M S. Mobile ad hoc networking and the IETF[J]. ACM Sigmobile Mobile Computing and Communications Reviews 1998, 2(2): 9?14.

[2]Marwaha S, Chen K T, Srinivasan D. A novel routing protocol using mobile agents and reactive route discovery for ad hoc wireless networks[C]//Proceedings of the 10th IEEE International Conference on Networks. Singapore, 2002:311?316.

[3]Kim Y, Perrig A, Tsudik G. Group key agreement efficient in communication[J]. IEEE Transactions of Computers, 2004,53(7): 905?921.

[4]Mishra A, Nadkni K, Patcha A. Intrusion detection in wireless ad hoc networks[J]. IEEE Wireless Communications, 2004(2):48?60.

[5]LIAO Li-jun, Manulis M. Tree-based group key agreement framework for mobile ad hoc networks[J]. Future Generation Computer Systems, 2007, 23(6): 787?803.

[6]Steiner M, Tsudik G, Waidner M. Diffie-Hellman key distribution extended to group communication[C]//Proceedings of the Third ACM Conference on Computer and communications Security. New Delhi, India: ACM Press, 1996:31?37.

[7]Pieprzyk J, LI C H. Multiparty key agreement protocols[C]//IEE Proceedings Computers and Digital Techniques. America, 2000:229?236.

[8]CAO Jian-nong, WANG Guo-jun, Keith C C. A fault tolerant group communication protocol in large scale and highly dynamic mobile next-generation networks[J]. IEEE Transactions on Computers, 2007, 56(1): 80?94.

[9]WANG Guo-jun, CAO Jian-nong, Keith C C. A novel group communication protocol using the ring net hierarchy in mobile internet[J]. International Journal of Parallel, Emergent and Distributed Systems (Taylor & Francis), 2005, 20(4): 253?280.

[10]Dhurandher S K, Singh G V. Weight based adaptive clustering in wireless ad hoc networks[C]//Proceedings of the 2005 IEEE International Conference on Personal Wireless Communications.New Delhi, India: IEEE, 2005: 95?100.

[11]施榮華. 一種基于復合問題的公鑰密碼系統[J]. 計算機工程與科學, 1998, 20(1): 39?42.SHI Rong-hua. A public key cryptosystem based on complex problems[J]. Computer Engineering & Science, 1998, 20(1):39?42.

[12]Steiner M, Tsudik G, Waidner M. CLIQUES: A new approach to group key agreement[C]//Proceedings of the 18th IEEE International Conference on Distributed Computing System,Amsterdam, Netherlands, 1998: 380?387.

[13]Tseng Y M, Yang C C, Liao D R. A secure group communication protocol for ad hoc wireless networks[C]//Advances in Wireless Ad Hoc and Sensor Networks and Mobile Computing. Springer, 2007: 385?390.