無線傳感器網絡中抗捕獲的密鑰管理協議
2008-12-31 00:00:00朱政堅譚慶平朱培棟
計算機應用研究 2008年10期
收稿日期：2007-12-05；
修回日期：2008-03-05
基金項目：國家“863”計劃資助項目（2006AA01Z213）
作者簡介：朱政堅(1975-)，男，湖南長沙人，博士研究生，主要研究方向為無線傳感器網絡的安全路由(waterzzj@163.com);
譚慶平 (1965-)，男，教授，主要研究方向為分布式軟件工程agent形式化方法等;
朱培棟(1971-)，男，副教授，主要研究方向為域間路由、無線網絡等.
（國防科學技術大學 計算機學院 長沙 410073）
摘要：
傳感器節點往往被部署在可被捕獲的敵對區域，其中的密鑰及安全算法可被敵人知曉，所以如何進行密鑰管理成為了研究焦點。提出了一種抗捕獲的密鑰管理協議SELF。SELF要求各節點每經過一個規定的時間間隔，就更新一次節點的身份密鑰和節點間的鄰居密鑰，并將原密鑰作廢。這樣即使敵人捕獲了傳感器節點，也只能得到一些過期的密鑰，因此SELF可以有效地防止敵人利用被捕獲傳感器節點中所保存的密鑰來冒充合法節點。
關鍵詞：無線傳感器網絡； 密碼學； 密鑰管理
中圖分類號：TP311
文獻標志碼：A
文章編號：1001-3695(2008)10-3088-04
Anti-capture key management protocol in WSN
ZHU Zheng-jian TAN Qing-ping ZHU Pei-dong
(School of Computer National University of Defense Technology Changsha 410073 China)
Abstract:
Because sensor nodes are often deposed in hostile areas the keys and security algorithms can be understood by the enemies. So the key management has became the focus of research. This paper presented SELF an anti-capture key management protocol. SELF required each node update the identity key of the node and the neighbor key between nodes and invalidate the old keys at given intervals. In this way even if the enemy captured the sensor nodes they could only get some old keys. SELF could prevent the enemy from pretending to be a legal node by making use of the keys of captured sensor nodes.
Key words：WSN; cryptograph; key management
無線傳感器網絡因其巨大的應用前景而受到學術界和工業界越來越廣泛的重視。目前已有的許多應用涉及到了軍事、檢測等數據敏感領域[1]。這些應用中的數據采樣、傳輸，甚至節點的物理分布，都不能讓敵人或無關人員知曉。安全性是這些應用得以實施的重要保障。但無線傳感器網絡本身所具有的一些限制使得安全問題的解決成為一個巨大的挑戰。密鑰管理作為安全機制的核心部分，吸引了眾多專家學者的目光。
WSN中節點之間的位置關系無法在部署前確定，并且網絡拓撲不穩定，使得傳統的密鑰管理技術無法有效地運用于WSN。同時由于無線傳感器節點往往被部署在節點物理安全無法保證的敵對區域，研究人員在設計密鑰管理協議時，一般要考慮節點被捕獲后，節點本身所帶密鑰泄露帶來的危害。
1相關工作
由于對稱密鑰算法在計算復雜度和能量消耗方面的優勢，目前絕大部分密鑰管理技術的研究都是基于對稱密鑰機制的。下面將對當前流行的密鑰管理技術進行分類介紹。
1)預共享密鑰模型和非預共享密鑰模型
預共享密鑰模型是指節點間的共享密鑰在節點布置前就已經確定。預共享密鑰模型有兩種主要模式：
a)每對節點間都共享一個主密鑰。這種模式的優點是共享密鑰的建立不依賴于基站、計算復雜度低、節點密鑰共享成功率為100%、一個節點的被俘不會影響其他節點；缺點是網絡擴展性不好、節點存儲壓力巨大、不適合大型網絡。
b)每個普通節點都與基站共享一個主密鑰。這種模式的優點是節點存儲壓力小、計算復雜度低、節點密鑰共享成功率高、易于擴展；缺點是對基站依賴性太高、基站容易成為瓶頸、網絡效率低。
非預共享密鑰模型是指節點間的共享密鑰在節點布置后通過協商機制確定。非預共享密鑰模型符合WSN中節點相對位置一般無法在布置前預知的特點，因此更適合WSN。后面介紹的密鑰管理技術都屬于非預共享密鑰模型。
2)概率性和確定性
如果密鑰共享成功與否是以一個可計算的概率提出的，則這種密鑰管理技術屬于概率性密鑰管理技術。
Eschenauer等人[2]首先提出了基本的隨機密鑰預分布協議。它的基本思想是，建立一個較大的容量為s的密鑰池，每個節點都擁有m個密鑰池中的密鑰。只要任何兩個節點擁有1個相同的密鑰，兩個節點就可以建立安全信道。他們證明了在已知網絡規模和鄰居節點個數期望值的條件下，s、m與網絡連通概率p之間存在可計算關系。它的優點表現在大大降低了每個節點的密鑰存儲壓力，適合大規模WSN的密鑰管理；缺點是存在孤立點問題，需要數據交換的節點間密鑰共享不一定成功。
后來在此基礎上進一步變化出q-composite隨機密鑰預分布協議等[3，4]多個版本。
確定性密鑰管理技術是指忽略信道出錯等物理因素，兩個需要交換數據的節點之間在理論上一定可以生成一個共享密鑰。
LEAP[5]是一種典型的確定性密鑰管理技術。LEAP協議認為單一的安全需求無法滿足WSN中所有類型的通信，因此它使用了多種密鑰機制。LEAP在每個節點上維護四個密鑰：與基站單獨共享的身份密鑰（預分布）、與網內所有節點共享的組密鑰（預分布）、與鄰居節點共享的鄰居密鑰以及與簇頭共享的簇頭密鑰。后兩個密鑰是在節點布置后，通過協商機制，利用預分布的主密鑰在欲共享密鑰的節點間建立的。
LEAP協議與隨機密鑰預分布協議相比，節點的計算量和存儲空間需求都增大了，但它可以保證需要交換數據的節點之間一定有共享密鑰。LEAP適合于安全需求高的WSN應用。
3)同構和異構
以上介紹的密鑰管理協議都假設基站外的所有節點性能是一樣的，因此它們適用的對象是同構型WSN。而Traynor等人[6]針對異構WSN，在隨機密鑰預分布協議中引入超節點，通過在超節點中存放更多的密鑰池中的密鑰，進一步減少了普通節點上需要存放的密鑰個數，并提高了網絡安全性。
以上這些密鑰管理協議關注的主要問題是如何在節點未被捕獲的情況下，確保消息的可用性、秘密性、完整性、可認證性和新鮮性。當節點被捕獲時，這些協議一般都認為敵人可獲得被捕獲節點上的一切與安全相關的信息，包括安全算法和密鑰。敵人可以制造一個“合法”的惡意節點，而網絡無法通過認證機制來識別節點的合法性。這些協議基本上都無法解決節點被捕獲后密鑰泄露的問題。
筆者認為，之所以出現“合法”的惡意節點無法被識別的情況，主要是由于正常節點間通信所使用的密鑰在節點生存期間一直保持不變所造成的。SELF協議通過不斷更新通信密鑰，可以有效地解決節點被俘后密鑰泄露的問題。
2SELF協議
2.1基本假設和思想
SELF對問題所處應用背景作出如下假設：
a)網絡屬于異構型的，其中有部分節點具有與基站時間同步的功能[7]，這類節點被稱為控制節點。安全信息不會從控制節點泄露。
這個假設是基于兩點考慮：第一，控制節點的數目在網絡全體節點中僅占極少部分，敵人隨機捕獲一定數目的節點，其中包含它們的概率小；第二，可在這兩類節點中裝入節點抗捕獲裝置，使得其中的安全機制信息在節點被捕獲前自動銷毀。由于這類節點在全網中所占比重小，其造價的提高不會使得整個應用的造價大幅度提高。文獻[6]也曾給出同樣假設。
b)網絡按簇的結構組織，每個簇內至少包含一個控制節點。
c)當敵人捕獲合法節點后，敵人無法在維持合法節點正常工作的同時對節點進行分析破解。
d)從敵人捕獲合法節點到復制出“合法”惡意節點的時間長度為TF。控制節點在簇內完成一次密鑰更新的時間長度為TC。TC遠遠小于TF。
e)所有節點在網絡自組織階段是安全的。新節點自身在節點加入階段是安全的。
SELF的基本思想是：每隔時間TG，網絡中的控制節點發布一次簇內密鑰更新廣播，網內的普通節點將根據收到的密鑰更新廣播的內容來實時更新自己的身份密鑰、鄰居密鑰和簇內身份密鑰。更新不成功的節點將被認為是被俘節點。根據假設c)和d)，敵人即便捕獲合法節點，也無法維持下一個時間段被俘節點所包含密鑰的有效性。
2.2協議描述
SELF分為四個階段：節點預設置、網絡自組織、密鑰更新和新節點加入。
在描述SELF的過程中，將引入以下符號：A、B分別表示節點；KDA表示節點A的身份密鑰；KNAB表示節點A、B之間的鄰居密鑰；KCDA表示A的簇內身份密鑰。
2.2.1節點預設置階段
SELF中有三類節點，分別是sink、控制節點和普通節點。Sink負責對網內收集來的數據進行匯總和處理；控制節點負責協調簇內節點的密鑰更新；普通節點負責事件的監控、數據采集和消息的傳遞。
SELF在節點預設置階段為各類節點分配建立安全通信所用的密鑰，主要過程如下：
a)選擇三個合適的單向散列函數J(x)、S(x)和G(x)。J(x)和S(x)用于新節點的加入，G(x)用于節點密鑰的更新。
b)假設N是需要進行節點加入操作的次數，KSN和KJN作為基站確定的初始節點加入密鑰，對于任意的密鑰KSi+1和KJi+1，運用KJi=J(KJi+1)和KSi=S(KSi+1)得到其子密鑰。運行N次該密鑰生成過程，得到兩個大小為N+1的密鑰池：J(0)(KJN)，J(1)(KJN)，J(2)(KJN)，…，J(N)(KJN)，從左到右依次對應KJN到KJ0；S(0)(KSN)，S(1)(KSN)，S(2)(KSN)，…，S(N)(KSN)，從左到右依次對應KSN到KS0。
c)假設M是需要進行密鑰更新操作的次數，KGM作為控制節點確定的初始廣播密鑰，對于任意的密鑰KGi+1，運用KGi=G(KGi+1)得到其子密鑰。運行M次該密鑰生成過程，得到大小為M+1的密鑰池：G(0)(KGM)，G(1)(KGM)，G(2)(KGM)，…，G(M)(KGM)，從左到右依次對應KGM到KG0。
d)為每個節點分配惟一的節點號i和與基站惟一共享的身份密鑰KDi。
e)將J(x)、G(x)、KG0和KJ0載入每個節點。
f)將KS0和S(x)存放在控制節點。
g)將KG0到KGN存放在控制節點，用于控制節點進行簇內密鑰更新消息的廣播。
h)SELF設網絡自組織階段所用時間為TZ。在節點被部署到目標區域前，sink節點、控制節點和普通節點被設置為TZ時間后進入密鑰更新階段。
i)SELF根據預估的TF時間長度和TC時間長度來設置控制節點發布密鑰更新消息的時間間隔TG。TG的設置要求在第3章中給出。
2.2.2網絡自組織階段
在節點預設置階段結束后，控制節點和普通節點被均勻隨機地布置到目標監測區域。所有節點按照LEACH算法[8]組織成簇的結構。根據網絡形成的拓撲結構，任意相鄰節點A、B之間使用密鑰KJ0協商鄰居密鑰KNAB。
在網絡自組織階段結束后，相鄰節點A、B間的消息傳遞和認證都使用鄰居密鑰KNAB。密鑰KJ0以后僅用于對新加入的節點進行認證。
若一個簇內有兩個或兩個以上的控制節點存在，則通過協商機制確定一個控制節點作為活動控制節點，其余的控制節點作為備用控制節點。活動控制節點收集同簇的所有普通節點的ID，并向同簇的其他所有節點廣播自己的ID，并與簇內所有節點建立簇內身份密鑰KCDi。
2.2.3密鑰更新階段
進入密鑰更新階段后，活動控制節點每隔TG發出密鑰更新廣播，此消息僅在簇內傳播。
整個密鑰更新過程被分成M個長度為TG的時間段，按時間關系可表示成圖1。在每個時間段內，SELF完成一次全網的密鑰更新。
SELF在每個時刻ti（0 a)活動控制節點使用密鑰KG(i-1)對密鑰KGi進行加密，然后進行簇內廣播。 b)同簇內的普通節點在收到廣播消息后，對廣播包進行解密，得到KGi。 c)為了驗證廣播包的合法性，接收到廣播消息的普通節點判斷KG(i-1)是否等于G(KGi)。若等式成立則此廣播包是合法的，進行步驟d)；反之則為非法假冒包，直接丟棄。 d)普通節點A將自己與鄰居節點B之間的鄰居密鑰進行更新，KNAB=G(KNAB|KGi)。同時普通節點更新自己的身份密鑰和簇內身份密鑰，KDA=G(KDA|KGi)，KCDA=G(KCDA|KGi)。接著普通節點刪除KG(i-1)，保存KGi。 e)成功更新了密鑰的節點向簇內的活動控制節點發出確認信息。 f)所有控制節點將自己的鄰居密鑰、簇內身份密鑰和身份密鑰以同樣的方式進行更新。 g)對于沒有回復確認消息的節點，活動控制節點認為該節點失效或被俘，在簇內對這些節點進行通報作廢，并上報基站。 h)活動控制節點檢查自己的剩余電量。若剩余電量低于門限值，要備用活動節點接替其工作。 2.2.4新節點加入階段 在新節點加入階段，SELF必須提供新老節點之間、新節點之間合法性的認證。 根據應用的不同，SELF采用不同的M值表示需要進行節點加入操作的總次數。對于其中的第j次加入節點操作，SELF采用以下方法： a)SELF預設新節點加入網絡的時間。新節點的加入時刻可選擇在任一次密鑰更新完成后過a時間的時刻，a為時間常數。若新節點P的加入時間在時刻(ti+TC+a)，則除開在節點預設置階段載入的信息外，在新節點中另外載入以下安全信息： KDP=G(KDP|KGi)，KSj，S(x)，KJj，KXj。其中：KXj是第j次要加入的新節點之間的共享密鑰，用于新節點之間的身份確認。 b)新節點被部署到目標區域后，新節點P首先使用KXj與鄰居節點中的新節點之間進行鄰居密鑰的協商，協商完成后，馬上刪除KXj。 c)接著新節點P使用KJ(j-1)對自己的ID、節點類型和KJj進行加密，然后將得到的密文向鄰居節點廣播，鄰居節點中的其他新節點將忽略這個廣播消息。 d)鄰居節點中的老節點Q收到節點P的廣播消息后，驗證KJ(j-1)是否等于J(KJj)。若兩者相等，則認為節點P是合法的新加入節點，進行步驟e)；否則丟棄該廣播消息，停止與節點P的通信。 e)節點Q將自己的ID、所在簇號告訴新節點P。 f)在等待一段時間后，節點P收集到鄰居節點中所有老節點的ID和簇號，用SNB表示。節點P使用KS(j-1)對SNB和KSj進行加密得密文E，然后廣播到鄰居中的老節點，要求它們傳送E到各自對應的活動控制節點。 g)每個收到密文E的活動控制節點，首先對E進行解密，然后判斷KS(j-1)是否等于S(KSj)。若兩者不相等，則丟棄該消息；否則認為節點P是合法的新加入節點。活動控制節點利用自己掌握的簇內合法節點的信息和SNB來為新節點P及其本簇內的鄰居節點之間分配鄰居密鑰和新節點的簇內身份密鑰。接著活動控制節點使用老節點的簇內身份密鑰對分配給它的鄰居密鑰進行加密，再發送給它。同樣活動控制節點使用KSj對分配的鄰居密鑰和新節點P的簇內身份密鑰進行加密，再發送回新節點P。 h)新節點P收到多個來自活動控制節點的回復消息，從中選擇一個簇加入，并宣布退出其他簇。被退出的簇中的鄰居節點將刪除與新節點P之間共享的鄰居密鑰，并通知自己所在簇的活動控制節點刪除新節點P的簇內身份密鑰。 i)Sink節點在等待一段時間TW后，在全網內發布第i次新節點加入完成的廣播。全網所有節點刪除KJ(i-1)，保存KJi。控制節點刪除KS(i-1)，保存KSi。新節點刪除KSi。 3安全性分析 首先說明SELF中時間參數的設置要求。 a)網絡自組織階段所用時間TZ：max(網絡完成自組織的必要時間)＜TZ＜min(節點部署后，敵人捕獲節點所花時間+TF)。 b)從敵人捕獲了合法節點，到復制出“合法”的惡意節點的時間長度TF：TF=avg(經驗值)。 c)在簇內完成一次密鑰更新的時間長度為TC：TC=avg(經驗值)。 d)密鑰更新的時間間隔TG：TC< TG小于TF可以保證即便節點被俘，敵人也無法獲得下一時間段的密鑰。TG盡可能地接近TF可以盡可能地減少密鑰的更新次數，從而減小SELF所帶入的安全負載。 e)新節點加入時，sink節點的等待時間TW：TW=avg(經驗值)，(TC+a+TW)< 定義1如果節點無法知道網絡中與應用相關的消息內容，或向此網絡注入消息，則稱此節點無法加入此網絡。 定義2如果網絡中的節點A被捕獲，敵人利用A中的密鑰制造的A*無法加入此網絡，則稱節點A是抗捕獲的。 定義3如果網絡中的所有節點都是抗捕獲的，則稱此網絡是抗捕獲的。 定理1在滿足SELF協議假設的條件下，使用SELF協議的網絡是抗捕獲的。 證明首先筆者假設控制節點和sink節點是不可被捕獲的，只需要證明普通節點的抗捕獲性；其次假設普通節點在網絡自組織階段是安全的，所以問題進一步簡化為證明普通節點在密鑰更新階段和新節點加入階段是抗捕獲的。而新節點在新節點加入階段被假設為安全的，所以要證明的命題歸結為要證明老節點在密鑰更新階段和新節點加入階段是抗捕獲的。 如圖2、3所示，筆者將假設節點A在ti到t(i+1)之間被捕獲，轉而證明敵人無法利用節點A在tj到t(j+1)之間將偽造節點加入網絡（i+1≤j）。 圖2中的stb1代表從ti到tg的所有時刻組成的集合；stb2代表從tg到t(i+1)的所有時刻組成的集合。圖3中的stf1、stf2、stf3代表偽造節點可能加入網絡的時刻集合。問題進一步轉換為要證明：假設節點A在stb1或stb2中的任意一個時刻被捕獲，敵人都無法利用節點A造出偽造節點A*，使得A*可以在stf1、stf2、stf3中的某一個時刻加入網絡。 1）節點A在sb1中的任一時刻被捕獲 若節點A在sb1中的任何一個時刻被敵人捕獲，不妨設此時刻為tb1。此時節點A并未向所屬的活動控制節點發出確認消息。因此節點A即便收到了KGi，并成功地更新了自己的身份密鑰、鄰居密鑰和簇內身份密鑰，但活動控制節點仍將知道節點A被俘或失效。所以簇內的所有節點都將廢除自己與節點A共享的鄰居密鑰，對應的活動控制節點將廢除節點A的身份密鑰和簇內身份密鑰。 a)節點A*在stf1中的任一個時刻要求加入網絡。 節點A*向網絡中注入消息或了解網絡中消息內容的行為需要鄰居密鑰的支持，而原鄰居節點因為已經從活動控制節點的通知中知道節點A被俘，并刪除了與節點A共享的鄰居密鑰，所以A*無法與原鄰居節點建立聯系。而其他節點因為沒有與節點A*共享鄰居密鑰也不會與A*發生聯系。而且，A*也無法證明自己是合法的新節點，所以也不會被老節點當做新節點而建立聯系。 b)節點A*在stf2中的任一個時刻要求加入網絡。設此時剛好是第q次加入節點操作階段。 由于A*沒有新節點標志密鑰KXq，A*無法冒充新節點來加入其他新節點。 由于A*沒有密鑰KSq，它無法在活動控制節點前冒充新節點，無法獲得新的簇內身份密鑰以及與老節點之間新的鄰居密鑰。A*無法冒充新節點來加入其他老節點。 由于沒有合法的老鄰居密鑰，A*無法以老節點的身份來加入其他老節點。 c）節點A*在stf2中的任一個時刻要求加入網絡。 由于沒有合法的老鄰居密鑰，A*無法以老節點的身份來加入其他老節點。而且，A*也無法證明自己是合法的新節點，所以也不會被老節點當做新節點而建立聯系。 2）節點A在sb2中的任一時刻被捕獲 若節點A在sb2中的任何一個時刻被敵人捕獲，不妨設此時刻為tb2。由于敵人破解節點A到造出A*的時間長度最小為TF，而時刻tb2+TF必然在時刻t(i+1)+TC之后，活動控制節點必將在t(i+1)到(t(i+1)+TC)之間發現節點A被俘或失效。 根據相關時間參數的關系，節點A*不可能在t(i+1)到(t(i+1)+TC)之間發出加入請求。所以節點A*發出加入請求時，活動控制節點已發現節點A被俘。剩余的證明與節點A在sb1中的任一時刻被捕獲相同。 綜上所述，可知所有普通節點都是抗捕獲的，從而使用SELF協議的網絡都是抗捕獲的，定理1得證。 4結束語 由于節點可能被敵人捕獲，無線傳感器網絡中的密鑰管理問題有其特殊性。目前的其他密鑰管理協議大多局限于節點被捕獲后如何識別偽造數據，而不能識別被捕獲節點本身。而基于從節點被捕獲到敵人造出“合法”的惡意節點的時間較長這一事實，本文提出的SELF協議在密鑰定時更新的基礎上很好地解決了這個問題。盡管SELF協議的使用增加了節點的能耗，但它通過對偽造節點的識別，能夠很大地提高網絡的安全性，能夠使用安全需求高的應用。 參考文獻： [1]任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報，2003，14(7):1282-1291. [2]ESCHENAUER L GLIGOR V D. A key-management scheme for distributed sensor networks[C]//Proc of the 9th ACM Conference on Computer and Communications Security.[S.l.]: ACM Press 2002:41-47. [3]CHAN H PERRIG A SONG D. Random key predistribution schemes for sensor networks[C]//Proc of IEEE Symp Security and Privacy. 2003. [4]PIETRO R D MANCINI L V MEI A. Random key-assignment for secure wireless sensor networks[C]//Proc of the 1st ACM Workshop. Security of Ad hoc and Sensor Networks. New York: ACM Press 2003:62-71. [5]ZHU S SETIA S JAJODIA S. Leap: efficient security mechanisms for large-scale distributed sensor networks[C]//Proc of the 10th ACM Conference on Computer and Communications Security.[S.l.]: ACM Press 2003:62-72. [6]TRAYNOR P CHOI H CAO G et al. Establishing pair-wise keys in heterogeneous sensor networks[C]//Proc of IEEE INFOCOM. 2006. [7]ELSON J ESTRIN D. Time synchronization for wireless sensor networks[C]//Proc of International Parallel and Distributed Processing Symposium (IPDPS)，Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing. San Francisco:[s.n.] 2001. [8]HEINZELMAN W B CHANDRAKASAN A P BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[C]. 2002:660-670.
