無線傳感網(wǎng)多多項式密鑰分配方案研究

王行甫,吳立濤,苗付友

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

2.1 基于密鑰池的密鑰預(yù)分配方案

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

2.2 基于多項式的密鑰預(yù)分配方案

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

3 多多項式密鑰分配方案

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

3.1 密鑰分配步驟

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

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

(1)

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

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

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

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

(2)

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

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

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

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

(3)

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

3.2 MPKDS分析

3.2.1 連通性分析

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

3.2.2 安全性分析

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

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

(4)

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

密鑰協(xié)商階段：

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ā)送數(shù)據(jù)階段：

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)

接收數(shù)據(jù)階段：

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次多項式組成的密鑰空間中,獲取經(jīng)過所有密鑰加密的數(shù)據(jù)包,至少需要得到的數(shù)據(jù)包的個數(shù)Pc與n和t的關(guān)系.從圖中可以看到,即使n和t緩慢增長,Pc的增長速度非?？?因此攻擊者想要獲取足夠多有效的數(shù)據(jù)包難度大大增大,有效提升了網(wǎng)絡(luò)的安全性.

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

(5)

因此構(gòu)建正確的方程組,得到全部正確的多項式系數(shù)為的概率P為

(6)

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

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

表1 Pn和t、n變化的關(guā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 實驗性能分析

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

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

算法建立時間(ms)內(nèi)存占用(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é)點占用資源總體上處于線性增長的趨勢.當(dāng)n=1時，MPKDS方案就退化為Blundo方案；1

5 結(jié)束語

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

[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移動無線傳感網(wǎng)中高安全性密鑰預(yù)分配方案[J].廣西師范大學(xué)學(xué)報(自然科學(xué)版),2013,31(3):164-168.

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