基于邊密鑰的傳感器網絡動態密鑰協商方案

摘 要:由于傳感器自身資源受限，目前采用的主要安全技術是對稱密鑰與密鑰預分配策略。在當前基于對稱密鑰的動態密鑰協商方案中，節點預裝入密鑰材料，部署后與鄰居節點通過共享密鑰材料建立配對密鑰。為提高動態密鑰協商中密鑰材料的安全性，在一個典型的動態密鑰協商方案，即LBKP方案的研究基礎上，提出了一種新的基于邊密鑰的傳感器網絡動態密鑰協商方案。與LBKP方案相比，該方案有效地減少了內存開銷，提高了密鑰安全性。

關鍵詞:傳感器網絡; 動態密鑰; 網絡安全; 密鑰材料

中圖分類號:TP301 文獻標志碼:A

文章編號:1001-3695(2010)03-1029-03

doi:10.3969/j.issn.1001-3695.2010.03.061

Edge key-based dynamic keying scheme for wireless sensor network

GUO Jiang-hong1， LI Xing-hua2， WU Jian-qiang1

(1.Dept. of Computer Science， Jiaying University， Meizhou Guangdong 514015， China; 2.Key Laboratory of Computer Networks Information Security of Ministry of Education， Xidian University， Xi’an 710071，China)

Abstract:For constraint resources of sensor nodes， existing security approaches are symmetric key and key pre-distribution. In most of existing symmetric key based dynamic keying schemes， pairwise key is established by using the shared keying materials preloaded on sensors. For improving the security of keying materials， this paper proposed an edge key-based dynamic keying scheme (EK-DKS) for wireless sensor network based on the study of a typical dynamic keying scheme——LBKP(location based key pre-distribution)scheme. Compared with LBKP scheme， EK-DKS scheme reduced the storage overhead and improved the security effectively.

Key words:sensor network; dynamic keying; network security; keying material

隨著無線傳感器網絡器網絡 (wireless sensor network， WSN)的應用領域日益廣泛，相應的研究也在不斷深入。在無線傳感器網絡中，由于無線通信的廣播特性，節點間的安全通信問題顯得更為重要。以提供安全、可靠的保密通信為目標的密鑰管理是WSN安全研究最為重要、最為基本的內容，也是其他安全機制的基礎。同時，傳感器節點資源受限，如有限的數據處理能力。有限的存儲空間、有限的計算能力及通信范圍等特點，使得傳統網絡密鑰管理的許多成果不能直接應用WSN，如RSA等。目前普遍認為可行的方法是采用密鑰預分配方案(key pre-distribution scheme， KPS)。

國外關于WSNs密鑰協商、分配方案的代表性相關研究成果有Eschenauer等人[1]提出的一種概率密鑰共享方式以及Chan等人[2]對該方案的改進;Younis等人[3]在層次式WSN中提出基于位置信息的EBS動態密鑰管理方案; Liu等人[4]和Du等人[5]結合部署知識提出了基于地理信息的密鑰分配方案及多矩陣空間密鑰分配方案進行動態密鑰協商，有效地提高了網絡的密鑰連通率。國內對WSNs密鑰協商及密鑰建立、分配方案的成果有蘇忠等人[6]對當前傳感器網絡的密鑰管理進行了綜合論述;陳克非等人[7]研究了無線傳感器網絡中對密鑰管理的評估指標問題，對目前比較流行的基于 KDC和基于預先配置這兩種密鑰管理方案進行了分析;劉志宏等人[8]討論了隨機預分配密鑰中區域重疊因子對網絡連通性及安全性的影響;王佳昊等人[9]討論了隨機預分配密鑰在無線傳感器網絡跟蹤算法中的應用等。

在Liu的基于對稱密鑰的動態密鑰協商方案——LBKP方案(location-based key pre-distribution scheme，LBKP)[6]中，使用對稱多項式作為密鑰材料預裝入傳感器節點中，并在部署后利用鄰居間的共享多項式建立配對密鑰。同時，利用部署知識得到高的密鑰連通率，并利用密鑰材料的門限安全提供一定的密鑰安全性。本文在LBKP方案的基礎上提出了一種新的基于邊密鑰的傳感器網絡動態密鑰協商方案EK-DKS(edge key-based dynamic keying sheme)，提高了安全性。

1 簡介LBKP方案

Liu提出了使用基于地理信息的對稱二元多項式隨機密鑰預分配方案[6]，簡稱LBKP方案。該方案把部署目標區域劃分為若干個大小一致的正方形區域。部署前，部署服務器生成與區域數量相等的對稱t 階二元多項式，并為每一區域指定惟一的二元多項式。對于每一節點，根據其期望位置來確定其所處區域，部署服務器把與該區域相鄰的上、下、左、右四個區域以及節點所在的區域共五個二元多項式共享載入該節點。部署后，兩個節點若共享至少一 個二元多項式就可以直接密鑰協商。與E-G方案[4]和q-composite方案[7]相比，LBKP方案有效地提高了密鑰連通率與安全性。

在LBKP方案中，每個區域對應分組中的節點存儲五個多項式，以保證與任一鄰居分組中的節點均可建立安全通信。每個多項式被五個區域對應分組中的所有節點擁有，同時，每個節點存儲五個對稱多項式對應的秘密分量，如圖1所示。

2 EK-DKS簡介

2.1 基本思想

現有的大部分基于對稱密鑰的動態密鑰協商方案中，都使用對稱多項式或對稱矩陣作為密鑰材料來提供門限安全。在給定網絡規模下，密鑰材料的安全性取決于網絡中擁有該密鑰材料部分信息(如多項式的秘密分量)的節點數目。顯然，這部分節點占總節點數比例越大，則敵手隨機捕獲一個節點含有該密鑰材料部分信息的概率越大，即安全性越低。在LBKP方案中，主要通過減少節點密度等方式來減少網絡中擁有某密鑰材料部分信息(如多項式的秘密分量)的節點數目，提高密鑰材料的安全性。本文方案則在預分配階段通過不同的密鑰材料的生產及分配方式，從開始就減少擁有某多項式秘密分量的傳感器節點數目，來提高安全性。

LBKP方案中，為每個區域生產一個多項式，稱之為區域多項式，該多項式同時被本區域及上、下、左、右四個鄰居區域共享。對于每個節點，將存儲五個多項式分量;對于每個多項式，網絡中共有五個區域的節點擁有該多項式的秘密分量。若部署目標劃分為N個區域，則對每個多項式而言，含有該多項式秘密分量的節點數目占總節點數的比例為5∶N。

與LBKP方案不同的是，本文不是為每個區域生產一個多項式，而是為區域中的每條邊生成一個多項式，稱為邊密鑰或邊多項式，是本文方案中節點間進行動態密鑰協商使用的密鑰材料，所用本文方案叫做基于邊密鑰的無線傳感器網絡動態密鑰協商方案。顯然，每條邊連接兩個區域，即每個邊密鑰被兩個區域中的節點共享。這樣，對于任意節點，將存儲節點所在區域四條邊對應的四個邊多項式秘密分量;對于每個邊多項式，網絡中有兩個區域的節點擁有該多項式的秘密分量。同樣設部署目標劃分為N個區域，則對每個多項式而言，含有該多項式秘密分量的節點數目占總節點數的比例為2∶N。顯然，任一被俘節點含有某多項式秘密分量的概率小于LBKP方案中的5∶N，即為暴露某多項式，敵手需捕獲更多的節點，密鑰安全性得到了提高，如圖2所示。

2.2 EK-KDS方案簡介

EK-KDS方案建立在Liu等人基于地理信息的對稱二元多項式隨機密鑰預分配方案(LBKP)基礎上，分為三個階段，即密鑰預分配階段、共享密鑰發現階段和路徑密鑰發現階段。其中，再預分配階段采用不同的密鑰材料生成及分配方式，以減少網絡中擁有某個多項式對應秘密分量的節點數目，達到提高安全性的目的;共享密鑰發現階段及路徑密鑰發現階段與LBKP方案相同，都是利用節點間的共享多項式計算配對密鑰或通過多跳路徑建立密鑰。

2.2.1 密鑰預分配階段

密鑰預分配階段，部署服務器生成與區域邊數相等的有限域Fq上的對稱t 階二元雙變量對稱多項式f，為每個多項式建立相應索引，q為素數，且Fq要足夠大以容納所有多項式系數。網絡中全部節點按照區域數量進行分組，一個分組中所有節點的期望位置為同一區域，部署服務器為每個節點計算其所在區域的四條邊對應的對稱多項式秘密分量并裝入節點中。其中每個邊多項式僅被某區域及其某一個鄰居區域共享。t階多項式有t安全門限，即不超過t個擁有與某多項式對應的秘密多項式分量的節點被俘，多項式仍然安全。

2.2.2 共享密鑰發現

1)每個節點在其通信范圍內廣播節點ID與多項式索引。考慮到安全性因素，可對多項式索引進行加密。例如，節點A可以先廣播其ID，然后利用存儲的秘密多項式和鄰居節點ID對索引進行加密[5]，形成一個加密索引鏈表并發送給鄰居節點。那些知道節點A的ID且與A有共享多項式的鄰居節點可以正確解密加密索引鏈表中的一個或多個消息，進而得到節點A的多項式索引。

2)節點間通過多項式索引，發現共享多項式。

3)鄰居節點間通過共享多項式建立密鑰。

設兩個有共享雙變量二元對稱多項式f(x，y)的鄰居節點u、v的ID分為k、 j，被服務器事先計算并預裝入的秘密分量為f(k，y)、 f(j，y)。兩個節點以對方ID為輸入分別計算f(k，j)與f(j，k)。由于多項式的對稱性，有

f(k，j)=f(j，k)=ku，v(1)

節點u、v以ku，v作為它們之間的通信密鑰。

2.2.3 路徑密鑰發現

與LBKP方案相同，當兩個無共享多項式的鄰居節點通信時，可通過多跳路徑進行間接密鑰協商。例如節點u、v是鄰居節點，分別屬于C2，2與C3，1，無共享多項式，則可通過一定的路由算法尋找一個中間節點i， i與u、v分別有共享多項式， 即i屬于C3，2或C2，1，與節點u和v可進行直接密鑰協商得到會話密鑰Kui(k)、Kiv(k)，則u可選擇一隨機密鑰k作為u、v間的會話密鑰，將Kui(k)發送給節點i，i再生成Kiv(k)發送給v。

2.2.4 節點加入及去除

在傳感器網絡生存期內，可能需要加入新的節點以取代損壞或被俘的節點。為了加入一個新節點，部署服務器需為該節點預裝入上文中的五個秘密多項式。

出于安全性考慮，有時也需要從傳感器網絡中去除部分節點，如被俘節點等。假設有某些異常節點的檢測方法，可以判定節點是否被俘。為了去除被俘節點，那些與被俘節點有共享多項式的節點需要將被俘節點的ID存入本地黑名單，并刪除對應的密鑰。當黑名單中與某個共享多項式對應節點ID數目超過多項式次數t時，則去除對應的秘密多項式分量及黑名單中擁有該秘密多項式的被俘節點ID。

3 性能分析

本文主要從連通率、安全性、方案開銷(包括存儲開銷、通信開銷、計算開銷)等方面對EK-DKS進行性能分析。設網絡規模N為104個傳感器節點，目標區域面積為103×103m2，節點通信半徑為40 m，區域邊長為L，節點存儲容量m為200個密鑰，節點服從正態分布，標準方差為σ，部署半徑為3σ。

3.1 連通率分析

本文使用與LBKP方案相同的方法對連通率進行分析(限于篇幅，文中不再進行連通率的推導，具體過程可參見文獻[6])。設節點服從正態分布，鄰居部署點間的距離d=a×σ，σ=50為標準方差，即區域邊長L=d。圖3為給定部署半徑時，不同區域邊長下連通率分析(以σ為單位長度)。從圖中可看出，給定部署半徑為3σ時，當L較小時，某節點與少部分鄰居節點進行直接密鑰協商。由于密鑰分配方式不同，在EK-DKS中，某區域與其對角鄰居區域無共享多項式，在L較小時密鑰連通率劣于LBKP方案;隨著L的增加，某節點的鄰居節點中來自本區域及鄰居區域的節點所占比例隨之增加，網絡連通率也在不斷提高，EK-DKS方案仍然到達了很高的網絡連通率。

3.2 安全性分析

本文采用與LBKP方案相同的標準衡量節點被俘對非被俘節點間通信鏈路的影響，即用某個秘密多項式暴露的概率衡量非被俘節點間通信鏈路受損比例。

某秘密多項式被俘的概率pc為

pc=1-∑ti=1Cinpi(1-p)n-i(2)

其中:Pc為某秘密多項式被俘的概率;n為網絡中擁有該t次多項式秘密分量的節點數;p為任一被俘節點含有該多項式對應秘密分量的概率，對應LBKP方案，p=5/N，對應EK-DKS方案，p=2/N，N為網絡中劃分的區域總數。

兩種方案的安全性比較如圖4所示。其中區域邊長L=100，節點存儲容量m為200個密鑰，每個區域對應的節點分組中的節點數目為100個。對于LBKP方案中的任一多項式(多項式次數為39)，網絡中有500個節點擁有其對應的秘密分量;對于EK-DKS方案中的任一多項式(多項式次數為39)，網絡中最多有200個節點擁有其對應的秘密分量(其中預分配的對應與區域的秘密多項式僅為本區域對應節點分組中100個節點共享，對于預分配的與邊鄰接鄰居區域的共享秘密多項式，為2個區域中共200個節點共享)，是相同多項式次數下的安全性比較。

如前所述，在給定密鑰存儲空間及多項式安全門限，即多項式次數下，多項式的暴露概率取決于網絡中擁有該多項式對應秘密分量的節點數目占總節點數的比例。該比例越大，意味著敵手任意捕獲的節點中含有該多項式對應秘密分量的概率越大，即為暴露該多項式，敵手需付出的代價較小。顯然，在上設網絡環境下，當被俘節點超過1 200時，LBKP中的秘密多項式將暴露;在EK-DKS方案中，被俘節點超過2 800時，秘密多項式將暴露。在相同的多項式次數下及網絡規模下，本文方案中的安全性遠高于LBKP方案。

3.3 方案開銷分析

1)存儲開銷 節點的存儲開銷最主要的是存儲各秘密多項式系數所需的存儲空間。對于LBKP方案，每個節點要存儲預分配的5個t次秘密多項式分量，需占用5(t+1)log Fq的存儲空間;對于EK-DKS方案，每個節點要存儲預分配的4個t次秘密多項式分量，需占用4(t+1)log Fq的存儲空間。顯然，本文方案的存儲開銷較優。

2)通信開銷 對于兩種方案，建立配對密鑰的通信開銷主要來自于共享密鑰發現。鄰居節點間為發現共享密鑰，需廣播自己的ID及多項式索引(可加密形成多項式索引鏈表以提高安全性)，以及對鄰居節點廣播消息的確認，通信開銷為O(2)。

3)計算開銷 為了建立配對密鑰，兩種方案中節點均需對t次多項式進行計算，計算開銷為t次模乘及t次模加。計算開銷取決于多項式次數。

兩種方案都采用多項式作為建立密鑰的工具，在相同的多項式次數下，使用不同的密鑰分配方式不會影響節點間建立配對密鑰所用計算開銷及通信開銷。

4 結束語

傳感器網絡的密鑰分配一直是研究的熱點問題之一。本文在基于LBKP密鑰預分配方案及部署知識的基礎上，提出一種新的基于邊密鑰的傳感器網絡密鑰動態密鑰協商方案——EK-DKS方案。通過改變密鑰的生成及分配形式，在保證高的網絡連通率的基礎上，在預部署階段就有效地減少了網絡中擁有某秘密多項式秘密分量的節點數目占總節點的比例，在減小節點存儲開銷的基礎上，有效地提高了安全性。

參考文獻:

[1]ESCHENAUER L， GLIGOR V. A key management scheme for distributed sensor networks[C]//Proc of the 9th ACM Conference on Computer and Communications Security. New York: ACM Press， 2002:41-47.

[2]CHAN Hao-wen， PERRIG A， SONG D. Random key predistribution schemes for sensor networks[C]//Proc of IEEE Symp on Security and Privacy. Washington DC: IEEE Computer Society， 2003:197-213.

[3]YOUNIS M，GHUMMAN K， LTOWEISSY M. Location-aware combinatorial key management scheme for clustered sensor networks[J]. IEEE Trans on Parallel and Distribution System， 2006，17(8):865-882.

[4]LIU Dong-gang， NING Peng. Location-based pairwise key establishments for static sensor networks[C]//Proc of the 1st ACM Workshop on Security of Ad hoc and Sensor Networks. New York: ACM Press， 2003:72-82.

[5]DU Wen-liang， DENG Jing， HAN Y S，et al. A pairwise key pre-distribution scheme for wireless sensor networks[C]//Proc of the 10th ACM Conference on Computer and Communications Security. Washington DC: ACM Press， 2003:42-51.

[6]蘇忠，林闖，封富君，等.無線傳感器網絡密鑰管理的方案和協議[J]. 軟件學報，2007，18(5):1218-1231.

[7]陳克非，陳菲，宋志高. 無線傳感器網絡中對密鑰管理評估指標研究[J].計算機仿真，2005， 22 (5):137-140.

[8]劉志宏，馬建峰，黃啟萍.基于區域的傳感器網絡密鑰預分配方案[J].計算機學報， 2006， 29(9):1608-1616.

[9]王佳昊，王勝坤，秦志光，等.隨機預分配密鑰在WSN跟蹤算法中的應用[J] .四川大學學報，2005，27(11):113-119.