王行甫,吳立濤,苗付友

(中國科學技術大學 計算機科學與技術學院,合肥 230027)

1 引 言

隨著無線通信技術和傳感器技術的快速發(fā)展,無線傳感器網絡(Wireless Sensor Networks,WSNs)在軍事和民用方面得到了廣泛的應用.WSNs是由大量的具有無線通信能力的、低功耗、低成本傳感器節(jié)點組成的網絡,節(jié)點一般具有有限的計算能力,有限的存儲空間,有限的能量,被部署在人類無法長期生存或者人類生存成本過高的區(qū)域,用于監(jiān)控、檢測的用途,如軍事檢測、森林火災監(jiān)測[1]、地震監(jiān)控等領域.

由于傳感器節(jié)點部署范圍廣,通常處于無人值守的狀態(tài),在某些應用中傳感器監(jiān)控的數據比較敏感,導致傳感器的安全性需要極大的重視.且WSNs的特殊性使得其面臨很多安全問題,如1)傳感器通常使用無線通信的方式進行數據交換,而無線通信的方式很容易使得數據被惡意節(jié)點監(jiān)聽、捕獲.2)sink節(jié)點是用來匯聚傳感器數據的節(jié)點,由于傳感器節(jié)點能量有限,而節(jié)點一旦部署,就很難再更換能量源,因此移動sink節(jié)點的路由算法被眾多研究者所青睞.但是由于sink節(jié)點的不固定,導致惡意節(jié)點可以仿冒sink節(jié)點,對傳感器網絡進行攻擊.

為了解決以上兩個典型的安全問題,加密方案被引入WSNs設計中.在加密過程中,密鑰協商是一個非常重要的步驟,它關系著加密過程是否可靠,加密結果是否有效,如果密鑰發(fā)生泄露,那么加密就變成了無用功.根據文獻[2]所述在通用網絡中,密鑰協商一般有三種研究方案,分別是1)可信服務器方案,這種方案依賴于一個可相信的服務器,服務器起著中間協商的作用,兩個需要進行密鑰協商的節(jié)點分別與可信服務器進行通信,由服務器分發(fā)一個共享密鑰進行加密通信.文獻[3]設計的Kerberos方案采用了這樣的方案,但是在WSNs中,節(jié)點受到通信距離的限制,導致這種方案無法實現.2)公鑰密碼體系方案,這種方案依賴于非對稱加密算法,受限于節(jié)點的計算能力和在WSNs中可能不存在的公鑰基礎設施,這種方案在WSNs中也無法實現.3)密鑰預分配方案,這種方案在節(jié)點部署之前就將密鑰配置到節(jié)點中,從方案設計和實驗結果來看,是最適合于WSNs的,也是研究者研究的最多的一種方案.本文擬提出的密鑰分配方案也是基于此設計的.

本文的全文安排如下,在第2章節(jié)介紹在密鑰分配方案設計中的相關工作,并對方案的優(yōu)點和不足提出本文的觀點.在第3章節(jié)介紹本文提出的基于多項式的密鑰分配方案設計,并對其進行分析.在第4章節(jié)介紹本文提出的分配方案的實驗結果,并對實驗結果進行分析.第5章節(jié)是對本文工作的總結.

2 相關工作

在已有的密鑰預分配方案設計中,主要基于兩種設計方法,1)基于密鑰池的密鑰預分配方案;2)基于多項式的密鑰預分配方案.

2.1 基于密鑰池的密鑰預分配方案

密鑰池預分配方案是在節(jié)點部署前,由服務器生成大量的密鑰,節(jié)點被隨機分配部分密鑰,然后進行部署.在密鑰協商階段,兩個節(jié)點尋找是否具有公共密鑰,如果有,則使用公共密鑰作為兩個節(jié)點通信的密鑰,否則不能建立通信.文獻[4]提出的E-G方案是一種基于概率性的隨機密鑰分配方案,該方案首先在節(jié)點部署前隨機分配密鑰,這樣節(jié)點間以一定概率擁有相同密鑰,在協商階段查看是否有相同密鑰,如果存在,則將該密鑰作為通信加密的密鑰,否則尋找中間節(jié)點來幫助兩個節(jié)點建立通信.該方案雖然基于一定的隨機性分配密鑰,但是由于在密鑰協商階段只需要找到一個相同的密鑰即可建立連接,使得節(jié)點的抗捕獲性較弱.文獻[5]針對E-G方案的不足,提出了q-composite方案(q-composite key predistribution scheme),該方案需要任意兩個節(jié)點至少存在q個共享密鑰時,節(jié)點才會協商會話密鑰K=Hash(k1‖k2‖…‖kq).不難看出,E-G方案是q-composite方案在q=1時的特殊情況,增大q值可以提高節(jié)點的抗捕獲性,提升系統安全性,但是節(jié)點間難以尋找到足夠的密鑰,導致節(jié)點連通性降低.

2.2 基于多項式的密鑰預分配方案

多項式預分配方案通常是基于某種數學理論建立的,和密鑰池預分配方案相比,它具有網絡安全性高、通信和存儲負載小等優(yōu)點[6].比較經典的多項式密鑰預分配方案主要是Blom方案[7]和Blundo方案[8].Blom方案是基于對稱矩陣建立兩節(jié)點間的共享密鑰,在部署節(jié)點前在服務器生成一個基于有限域GF(q)的(λ+1)×N的公共信息矩陣G和(λ+1)×(λ+1)的秘密對稱矩陣D,然后由公式獲得一個Blom矩陣A,將矩陣A的一行和矩陣G的一列作為密鑰存儲在每個節(jié)點中.節(jié)點在密鑰協商過程中,分別將各自內存中的種子密鑰發(fā)送給對方,兩節(jié)點分別計算密鑰,由于矩陣是對稱的,兩節(jié)點計算得到的密鑰一定相同,此密鑰可以作為節(jié)點的會話密鑰.該方案存儲的密鑰信息較少,占用內存較少,同時因為傳感器建立會話的密鑰是不相關的,所以節(jié)點抗捕獲性較強,該方案不足的地方在于存在嚴重的門限λ問題.Blundo方案是基于Blom方案的設計,不過Blundo方案使用的是二元t次對稱多項式函數,在有限域GF(q)上生成一個二元t次對稱多項式,在節(jié)點部署前將多項式保存在節(jié)點中,在密鑰協商過程中,兩個節(jié)點交換彼此的身份ID來計算通信密鑰,由于多項式是對稱的,節(jié)點計算結果一定是相同的.Blundo方案每個節(jié)點僅需要存儲多項式函數的t+1個系數即可,占用內存少,計算代價低.該方案的不足之處在于存在“t-secure”問題[9].

3 多多項式密鑰分配方案

由于密鑰池分配方案的基本原理是節(jié)點各自保存密鑰池的一個子集,在密鑰協商的過程中,尋找兩個節(jié)點保存的子集密鑰的交集,如果交集為空,則這兩個節(jié)點沒有協商出一致的密鑰,無法建立連接,如果交集不為空,則使用交集中的密鑰作為兩個節(jié)點通信的加密密鑰,因而密鑰池分配方案無法確保網絡中的節(jié)點一定能建立連通[10].當被捕獲的節(jié)點達到一定數量的時候,將這些被捕獲節(jié)點的密鑰合并在一起,就可以得到一個很大的密鑰池子集,利用這個大子集可以與網絡中的其他大部分節(jié)點進行合法的通信,造成密鑰空間泄露.基于多項式的密鑰分配方案存在“t-secure”問題,一旦存在個t+1節(jié)點泄露,由于只有單一多項式,如果輸入一定,則輸出也是一定的.攻擊者可以利用一定的輸入獲得t+1個密鑰,進而構建一個至少含有t+1個方程的方程組,使得用于計算密鑰的多項式函數的所有系數被計算出來,導致密鑰完全泄露.本文擬提出的多多項式密鑰分配方案(Multi-PolynomialsKey Distribution Scheme,MPKDS)就是為了解決上述問題,節(jié)點在密鑰協商階段,利用各自獲得的參數,基于多項式的計算,獲得用于加密通信的密鑰,進行安全通信,實現100%的連通性.節(jié)點間通信密鑰獨立,即使某一密鑰被竊取也不存在密鑰空間被泄露的問題,因為使用多個多項式,攻擊者幾乎不可能構建正確的t+1方程組,解方程求得多項式系數,即不存在“t-secure”問題.

3.1 密鑰分配步驟

MPKDS采用的也是基于對稱二元t次多項式函數的方案,下面是密鑰分配方案具體步驟.

1)選擇二元t次對稱多項式作為密鑰生成函數,選擇二元對稱多項式的原因在于為了保證兩個節(jié)點各自控制一個參數,同時計算結果一致.在節(jié)點部署前,由服務器端在有限域GF(q)隨機生成n個二元t次對稱多項式函數,其表達式如下:

(1)

2)每個節(jié)點都分配n個完全相同的多項式,按照無線傳感器網絡構建規(guī)則,可以進行隨機部署.在網絡運行過程中,任意兩個節(jié)點想要建立會話,必須先要進行密鑰協商,得到一致的密鑰后,說明節(jié)點是可信的,認證成功.接下來的通信過程都要使用該密鑰進行加密,保證網絡通信的安全性.

3)密鑰協商階段,兩個節(jié)點首先在節(jié)點內各自生成一個隨機數,發(fā)送到對方節(jié)點中,這樣每個節(jié)點可以得到兩個隨機數,作為節(jié)點內存儲的n個多項式的參數,生成n個基于二元t次多項式的密鑰,

由于f(x,y)是二元對稱多項式函數，有

f(x,y)=f(y,x)

(2)

所以每個節(jié)點在得到兩個隨機數后,生成的密鑰是一致的.這些密鑰組成密鑰空間N.密鑰空間N中的密鑰作為發(fā)送數據時用于加密的密鑰,接下來的工作是如何和通信對方節(jié)點商量使用一致的密鑰.

4)密鑰空間N中的n個密鑰，對于每一個密鑰，都使用密鑰空間中的n個密鑰進行加密，得到另外一個密鑰空間M，密鑰空間M的大小記為|M|=n×n=n2，其中每n個空間M中的密鑰可以映射到空間N中的一個密鑰.

5)節(jié)點在通信的時候,首先隨機選擇密鑰空間N中任意一個密鑰對通信數據進行加密,假設這里使用的是密鑰a,在密鑰空間M中存在n個密鑰可以映射為密鑰a,從這n中任意選擇一個密鑰,假設這里使用的是密鑰b,添加到數據包包頭,作為對方節(jié)點計算密鑰a的參數,這樣,數據包的形式可以使用下面的表達式表示:

p={b+F(a,d)|a∈M,b∈N,f(b)→a}

(3)

在上述表達式中,函數F是加密函數,函數f是單向映射函數.表達式p的形式可以理解為,首先任意選擇密鑰空間M中的密鑰a對數據d進行加密,存在密鑰空間N,N中的任意密鑰可以映射為M中的密鑰,現選擇N中的密鑰b,密鑰b可以映射為M中的密鑰a,將密鑰b作為數據包前導數據發(fā)送到對方節(jié)點.對方節(jié)點在收到數據包后,首先從數據包中分離出b，將b映射到密鑰空間N中的密鑰a，使用a對數據包中的數據進行解密，得到正確的明文數據.

3.2 MPKDS分析

3.2.1 連通性分析

與密鑰池方案不同的是,基于多項式的方案所有節(jié)點在部署前都會被分配相同的多項式函數.在本方案中,所有節(jié)點會被分配由服務器生成的n個多項式,在密鑰商議階段使用隨機數作為多項式的參數,計算得到密鑰空間N,再對密鑰空間N進行加密得到密鑰空間M,所有的計算結果都是確定的,節(jié)點雖然是單獨計算,但是基于二元對稱多項式的特性,計算結果是確定一致的.在密鑰商議階段一定可以計算得到一致的密鑰作為會話密鑰,所以本方案的連通性是100%,網絡內任意兩個合法節(jié)點都可以建立通信.

3.2.2 安全性分析

當網絡中被捕獲的節(jié)點數量較少時,無論是基于密鑰池的分配方案,還是基于多項式的分配方案都可以很好的保證網絡的安全性.但是一旦捕獲數量多,密鑰池分配方案會面臨密鑰空間被泄露,導致網絡安全性被破壞.單一多項式的分配方案面臨很嚴重的“t-secure”問題,本文提出的多多項式分配方案,由于每次使用的都是密鑰空間N的隨機密鑰,密鑰之間相互獨立,隨著多項式個數n的增大,密鑰空間大小快速增長,保證了網絡空間的安全性.

基于多項式的分配方案,節(jié)點在每次通信時都要計算新的密鑰,而不是使用密鑰池方案中的固定密鑰.攻擊者如果想要破解網絡,只有計算出所有多項式的系數,得到完整的多項式函數方可.為了驗證方案的安全性,假設惡意節(jié)點可以任意獲取節(jié)點間通信的數據包,n個二元t次多項式共有系數個,如果要解得所有系數,需要構建個方程組,因為每次節(jié)點通信都是從n個密鑰中隨機選擇任意一個密鑰,為了獲取經過所有密鑰加密的數據包,使用概率統計的方法,惡意節(jié)點需要獲取數據包個數的期望為Pc

(4)

多多項式密鑰分配方案偽代碼

密鑰協商階段：

r1=generate_one_random_integer()

r2=receive_one_random_integer()

key_space_N=[]

for f in polynomials_pool:

key_space_N.append(f(rl,r2))

key_space_M={}

key_space_map={}

for key_n in key_space_N:

key_space_M[key_n]=[]

for key_m in key_space_N:

key_space_M[key_n].append(crypt(key_m,key_n)) # for crypt

key_space_map[key_m]=key_n # decrypt

發(fā)送數據階段：

key=random_get_key_from(key_space_N)

random_key=random_get_key_from(key_space_M[key])

package_data=crypt(key,data)

package=[random_key,package_data]

send(package)

接收數據階段：

package=get_package()

rand_key=get_random_key(package)

key=key_space_map[random_key]

crypt_data=get_data(package)

data=decrypt(key,crypt_data)

圖1表示了在n個二元t次多項式組成的密鑰空間中,獲取經過所有密鑰加密的數據包,至少需要得到的數據包的個數Pc與n和t的關系.從圖中可以看到,即使n和t緩慢增長,Pc的增長速度非常快,因此攻擊者想要獲取足夠多有效的數據包難度大大增大,有效提升了網絡的安全性.

假設惡意節(jié)點得到經過所有密鑰加密的數據包，為了解出所有多項式的系數，需要構建n×(t+1)個方程組.現在假設攻擊者得到了Pc個有效數據包，從其中選擇任意n×(t+1)個數用來構建方程組，由于節(jié)點隨機選擇密鑰的原因，這里Pc應該遠遠大于n×(t+1)，因為節(jié)點可能多次選擇了相同的密鑰進行加密a進行加密，但是不同的密鑰b作為數據包前導數據.根據排列組合的知識共有Pn種不同的方程組

(5)

因此構建正確的方程組,得到全部正確的多項式系數為的概率P為

(6)

圖1 捕獲有效數據包期望與t、n的關系Fig.1 Relationship between the expectation of valid captured packets and t and n

表1記錄的數據是隨著n和t的增長,Pn的變化情況,從表中可以看到,Pn的快速增長使得構建正確方程組的概率幾乎為0,有效保證了該密鑰分配方案的安全性.

表1 Pn和t、n變化的關系表
Table 1 Relationship between Pnand the variations of t and n.

nt=2t=4t=6t=827．2e+23．6e+68．7e+106．4e+1532．6e+82．2e+172．3e+271．3e+3843．1e+141．8e+286e+432．1e+6053．9e+207．4e+394．4e+609．3e+8261．3e+274．7e+512．4e+787．1e+10675．8e+339．3e+637．9e+962．3e+13186e+405e+764．9e+1153e+15698．1e+476．8e+899．4e+1342．4e+182

4 實驗性能分析

無線傳感器網絡節(jié)點最重要的資源就是計算能力、存儲能力和能耗問題.由于影響能耗問題的因素諸多,密鑰分配方案不是根本原因,本文主要在計算能力和存儲能力兩個方面將MPKDS與Blundo方案進行對比分析.如今在嵌入式領域使用最廣泛的處理器即ARM公司設計的ARM內核CPU,本文基于ARM CortexM3架構的CPU指令集,系統時鐘120MHz,進行資源統計.通過統計程序運行時間作為占用計算資源的評價標準,在ARM架構下缺乏精確的內存占用統計工具,本文通過分析反匯編程序,統計占用的寄存器、內存空間作為占用存儲能力的評價標準.

表2 MPKDS與Blundo比較結果表(t=4)
Table 2 Comparison results between MPKDS and Blundo(t=4)

算法建立時間(ms)內存占用(Byte)Blundo123928MPKDS(n=1)128960MPKDS(n=2)1531412MPKDS(n=3)1841988MPKDS(n=4)2412428MPKDS(n=5)2982996MPKDS(n=6)3553508MPKDS(n=7)4134116

由表2分析知，MPKDS對節(jié)點占用資源總體上處于線性增長的趨勢.當n=1時，MPKDS方案就退化為Blundo方案；1

5 結束語

現有的密鑰分配方案中,基于密鑰池分配的方案存在占用內存過大、抗捕獲性不強、概率連通等不足,常規(guī)基于多項式的分配方案雖然占用內存小,但是存在嚴重的“t-secure”問題,本文針對上述不足,提出的基于多多項式的密鑰分配方案,保證網絡節(jié)點的100%連通性,避免了“t-secure”問題,增強網絡節(jié)點的抗捕獲性,網絡的安全性.實驗表明,MPKDS對節(jié)點計算能力要求不高,使用合適的多項式個數參數,可以在存儲資源有限的情況下極大的保證了網絡的安全性.

[1] Grammalidis N,Cetin E,Dimitropoulos K,et al.A multi-sensor network for the protection of cultural heritage[C].Signal Processing Conference,2011 19th European.IEEE,2011:889-893.

[2] Du Wen-liang,Deng Jing-han,Yunghsiang S,et al.A pairwise key predistribution scheme for wireless sensor networks[J].ACM Transactions on Information and System Security(TISSEC),2005,8(2):228-258.

[3] Clifford Neuman B,Theodore Ts′o.Kerberos:an authentication service for computer networks[J].IEEE Communications Magazine,1994,32(9):33-38.

[4] Laurent Eschenauer,Virgil D.Gligor.A key-management scheme for distributed aensor networks[C].Processding of the 9th ACM Conference on Computer and Communications Security,2002:41-47.

[5] Haowen Chan,Perrig A,song D.Random key predistribution schemes for sensor networks[C].Security and Privacy,Proceedings,2003 Symposium on.IEEE,2003:197-213.

[6] Saahira Banu Ahmed,Ananthi Shesasayee.To enhance security in wireless sensor networks with mobile sink[C].Current Trends in Engineering and Technology(ICCTET),2014 2nd International Conference on.IEEE,2014:547-550.

[7] Rolf Blom.An optimal class of symmetric key generation systems[C].Workshop on the Theory and Application of Cryptographic Techniques.Springer Berlin Heidelberg,1984:335-338.

[8] Blundo C,De Santis A,Herzberg A,et al.Perfectly-secure key distribution for dynamic conferences[C].Annual International Cryptology Conference.Springer Berlin Heidelberg,1992:471-486.

[9] Chen Yan,Wu Wen-kang,Liang Jun-bin.High safety scheme of key pre-distribution with a mobile sink in wireless sensor network[J].Journal of Guangxi Normal Universite:Natural Science Edition,2013,31(3):164-168.

[10] Liao Dong-ping.A key management research based on polynomial for WSN[D].Changsha:Central South University,2014.

附中文參考文獻：

[9] 陳 燕,吳文康,梁俊斌.Sink移動無線傳感網中高安全性密鑰預分配方案[J].廣西師范大學學報(自然科學版),2013,31(3):164-168.

[10] 廖東平.基于多項式的WSN密鑰管理方案研究[D].長沙:中南大學,2014.