基于六邊形網格組部署的對稱密鑰預分配模型

龐浩杰 ，常 凱 ， 金 琰， 朱 亮

(1.河南省洛陽正骨醫院(河南省骨科醫院)， 鄭州 450016; 2.湖北中醫藥大學 信息工程學院，武漢 430065;3.鄭州輕工業大學 計算機與通訊工程學院，鄭州 450002)

0 引言

傳感器網絡有許多應用，如家庭安全監控、軍事偵察、環境監測和目標跟蹤等等[1-4]。典型的傳感器網絡通常由大量的微小感知設備構成，這些設備又稱為傳感器節點，它們的電池電量和數據處理能力有限，并且通常通過短距離無線電信號彼此通信；在許多應用中，傳感器節點通常隨機分布在特定區域，以感知和收集有用的信息。

傳感器網絡最基本的安全要求之一是保證傳感器節點間發送信息的保密性和完整性。尤其是傳感器網絡部署在“敵對”環境中時，密鑰的建立在認證和加密中起著很重要的作用。攻擊者可以通過對傳感器節點發起物理攻擊，或者對不同的通信協議采用邏輯攻擊來竊聽消息或使網絡失效[5-6]。因此，傳感器網絡需要加密和認證服務。由于資源的限制，實現有效的密鑰建立機制并不是一項簡單的任務。除了目前流行的橢圓曲線密碼體制外[7]，對稱密鑰算法[8]也是解決這一問題的可行途徑。

文獻[9]提出的隨機密鑰預分配模型離線生成一個大的密鑰池，每個傳感器從密鑰池中隨機選取一個密鑰子集。通信范圍內的任意兩個節點只有共享一個公用密鑰才能相互通信。根據密鑰池的大小和網絡中傳感器節點的數量，這種體制可以實現不同的連通性和恢復能力；文獻[10]提出將部署知識應用到基本的隨機成對密鑰中；文獻[11]通過應用部署知識提出了一種密鑰預分配模型。在這種模型中，把整個網絡分成組，每個組執行基本的隨機密鑰預分配。一個組的密鑰池與水平組密鑰池共享(個密鑰，與對角組密鑰池共享(個密鑰；從Blom解決方案[12]發展而來的密鑰矩陣方案還有文獻[13]的多空間密鑰預分配模型。

文獻[14]提出了采用多項式的隨機密鑰生成思想。它采用對稱多項式計算來獲得成對密鑰。這種方案對捕獲的節點具有t-串謀抵抗能力，即小于t+1個節點的攻擊不會泄露任何關于其他節點密鑰的信息；文獻[15]基于該思想和基本隨機密鑰預分配[9]，提出了隨機子集分配密鑰預分配模型。與生成大型密鑰池和創建密鑰環不同，該方案創建一個大型多項式池，并從池中為每個節點分配一個多項式子集。這樣，兩個節點只有共享至少一個公用多項式才能相互通信。結果表明，與文獻[9]模型相比，這種模型提高了恢復能力；文獻[16]提出了利用預部署知識的私有多項式預分配方案，文獻[17]提出了基于8-方形網格的多項式預分配方案；文獻[18] 針對Sheetal Kalra 方案容易在數據庫泄露和用戶智能卡丟失的情況下受到用戶的假冒攻擊、并且不能達成正確的共享密鑰的分析，基于口令的無線傳感器網絡認證方案，提出了一種改進的帶有智能卡的認證方案，解決了 Sheetal Kalra 方案中的安全性問題，提供了用戶、傳感器、網關節點之間的相互認證并達成正確的共享密鑰。此外，還給出了提出方案的安全性分析，以此證明提出的方案可以滿足無線傳感器網絡中的安全需求；文獻[19]針對移動異構無線傳感器網絡模型，提出了在一種安全高效的密鑰管理方法。方法采用橢圓曲線密碼學加密算法實現移動節點位置信息到基站的安全上傳，以及基于密鑰哈希的消息認證碼來實現消息源的身份認證。基站則對收集的移動節點位置信息進行統計分析來協助完成固定節點與移動節點間的身份認證及會話密鑰建立。實驗結果表明，所提出的方法在密鑰建立過程中節省了網絡資源，同時可有效防御攻擊者發起重放攻擊，節點復制攻擊和女巫攻擊等，增強了網絡的安全性；文獻[20]基于具有節點移動性的動態傳感器網絡安全通信，分析了一種證書無效密鑰管理(CL-EKM,certificate less-effective key management)協議，保護數據和通信需要適當的加密密鑰協議。針對具有節點移動性的動態傳感器網絡的安全通信，提出了一種證書無效密鑰管理(CL-EKM)協議。CL-EKM協議支持在節點離開或加入集群時進行高效的密鑰更新，并保證了向前和向后的密鑰保密。該協議還支持對被破壞的節點有效的密鑰撤銷，并將節點被破壞對其他通信鏈路安全的影響降到最低。對方案的安全性分析表明，該方案能夠有效地防御各種攻擊。

上述這些解決方案在采用預部署知識來提高性能和安全性方面仍有一些局限性。對此，本文提出了一種基于六邊形網格組部署的無線傳感器網絡對稱密鑰預分配模型。模型將多項式信息分配到一個六邊形網格組中的特定區域內有限數量的傳感器節點上，從而使得每個傳感器節點找到與其相鄰節點的共享密鑰空間；仿真實驗結果表明，提出的對稱密鑰預分配模型不僅具有良好的加密性能，而且相比于其他模型的密鑰方案有更好的內存開銷、運行時間和節點受損攻擊時的網絡恢復能力。

1 相關模型

1.1 基于Blom思想的密鑰預分配模型

基于Blom思想提出的密鑰預分配模型[9]能夠確保組中的任何一對成員都可以計算公用共享密鑰。用N表示網絡中傳感器節點數目，G為有限域上大小為(t+1)×N的生成矩陣，D為大小為(t+1)×(t+1)的秘密隨機矩陣，其中t為攻擊者攻擊的節點個數。從矩陣G和D，構造一個N×N的對稱矩陣K，它的元素是節點之間的成對密鑰，則矩陣K為：

K=(D·G)T·G

(1)

每個節點i存儲私有矩陣A=(D·G)T對應的第i行。如果節點i想要與節點j通信，則它計算其存儲的行向量與G的第j列的內積，得到公用密鑰Ki,j。文獻[13]的多空間密鑰預分配模型將Blom思想與文獻[9]的基本隨機密鑰預分配模型相結合應用于傳感器網絡。在這種方法中，他們將每個元組(D,G)生成的密鑰空間表示為密鑰集合。網絡中的每個節點隨機存儲來自于ω個預生成空間的τ個空間。基于概率，任意兩個節點可以共享一個公用空間，該空間可以計算出一個公用秘密密鑰。所有密鑰矩陣解決方案都具有閾值t-安全特性，即當攻擊者攻擊的節點不超過t個時，未被攻擊的節點之間的通信仍然是安全的。

1.2 基于Blundo思想的密鑰預分配模型

基于Blundo思想提出的多項式密鑰預分配模型[15]采用對稱多項式計算來獲得成對密鑰，方案使用n個變量的t次多項式來建立t-安全n-聯盟的密鑰分配。應用于兩個對象之間的成對密鑰，密鑰預分配服務器在一個有限域Fq上隨機生成一個二元t次多項式：

(2)

其中:q是一個足夠大的素數，可以容納一個密碼密鑰，函數f(x,y)是對稱的即f(x,y)=f(y,x)。每個節點有唯一的整數IDi，加載來自于多項式f(x,y)的信息f(i,y)。這樣，任意兩個節點i和j可以計算節點i的密鑰Ki,j=f(i,j)和節點j的密鑰Kj,i=f(j,i)。由于對稱特性，有：

Ki,j=Kj,i

(3)

故兩個節點有一個共用的成對密鑰。

每個節點必須存儲t+1個系數，每個系數有log2q比特(bits)。因此，該模型中每個節點的內存存儲需求為(t+1)log2q比特。由于存儲密鑰的內存開銷很大，這種方案不能直接應用于傳感器網絡，因為內存的大小按指數規律依賴于網絡的規模，因此對于資源受限的傳感器節點等設備來說是不可行的；對此，本文將通過采用預部署知識來解決這個問題，并表明相比其他基于多項式的、應用預期位置知識的方案更具優勢；此外，我們在計算成對密鑰中還加入了一些隨機數，這樣，對手就很難對未捕獲節點的額外安全連接造成破壞。

2 基于六邊形網格組部署的對稱密鑰預分配模型

在提出本文方案之前，我們將密鑰空間定義為采用Blundo模型生成的一個t次二元多項式f(x,y)的全部密鑰的集合，密鑰空間中的密鑰數量表示密鑰空間大小。假設如果一個節點攜帶f(x,y)生成的信息，則它將選擇一個密鑰空間。任意兩個選擇公用密鑰空間的節點總是計算它們的成對密鑰。

節點nA選擇密鑰空間fu,v(x,y)，如果它攜帶fu,v(nA⊕RvA,y)的系數，其中RvA是節點nA的隨機值，將在密鑰預分配階段進行描述。當兩個節點在相同的密鑰空間時，它們可以計算成對密鑰來建立安全通道。

本文方案允許傳感器節點在部署后找到與其相鄰的每個節點的公用密鑰空間。方案共分為3個階段：密鑰預分配階段、直接密鑰建立階段和間接密鑰建立階段。在部署前執行密鑰預分配階段，將憑證信息預加載到每個傳感器節點。之后，如果兩個傳感器節點至少共享一個共用密鑰空間，則可在它們之間建立一個直接密鑰，否則，它們可以在間接密鑰建立階段的基礎上商定一個間接密鑰。

首先，要解決傳感器網絡的部署模型。

2.1 基于六邊形網格組的傳感器節點部署

在本文模型中，把目標區域劃分為六邊形網格。六邊形網格提供了對圓的最佳近似，比在連續區域中可以重復使用的其他2種幾何圖形(三角形和矩形)所覆蓋的面積更大。與矩形的8個或三角形的12個相鄰單元格相比，六邊形有最少的相鄰單元格(6個)。傳感器節點在單元格上進行劃分并分組。這種模型適合于實際場景，當每組的傳感器節點一起部署時，預期的相鄰組更有可能彼此接近。

(4)

式中,(xi,yi)為組Gi中的節點ni的坐標，σ為分布的標準偏差。基于六邊形網格組的部署模型如圖1所示。

圖1 基于六邊形網格組的部署模型

在描述本文方案的原理之前，定義集群為3個相鄰組的集合，一個組有3種類型的集群：1-集群、2-集群和3-集群。對于任何一個組(i,j)，1-集群包含這個組(i,j)和組(i+1,j)以及(i+1,j+1)，2-集群包含這個組(i,j)和組(i,j-1)以及(i-1,j)，3-集群包含這個組(i,j)和組(i-1,j+1)以及(i,j+1)。

例如在圖1中，對于組(2,2)來說，組(3,2)和組(3,3)屬于1-集群(2,2)，組(2,1)和組(1,2)屬于2-集群(2,2)，組(2,3)和組(1,3)屬于3-集群(2,2)。

在一個單元格上，分布函數可能是不均勻的，但可以在部署點之間選擇合適的距離，使得總體分布接近均勻。

2.2 密鑰預分配階段

此階段的目標是將密鑰材料分配給每個節點。基于這些密鑰材料，相鄰節點在部署后可以對密鑰進行配對設置。

這個任務是通過離線服務器完成的。首先，服務器為每個集群生成一個多項式池F，它包含足夠多的t次對稱二元多項式。然后將每個多項式分配給每個集群中的所有傳感器節點。由于每個單元格屬于3個集群，所以每個節點要存儲3個t次二元多項式的知識。換句話說，每個節點要選擇3個密鑰空間。算法1所示為多項式預分配實現的偽代碼。

這一階段完成后，每個傳感器節點存儲一個節點ID、3個空間ID、一個隨機值和3個對應于3個密鑰空間的系數向量的值。這些密鑰材料將用于下一階段的成對鑰匙建立。

算法1:多項式預分配算法

Input: 網絡中的節點集合N, 集群集合Ψ, 多項式池F

Output: 加載密鑰材料給網絡中的每個傳感器節點

1.For每個組Gi,j

2.For1-集群(Gi,j)中的每個組Gu,v

3.If不在polynomial_sharing(Gu,v,Gi,j)中

4.生成一個f(x,y)

5.把f(x,y)分配給1-集群(Gi,j)

6.Endif

7.Endfor

8.For2-集群(Gi,j)中的每個組Gu,v

9.If不在polynomial_sharing(Gu,v,Gi,j)中

10.生成一個f(x,y)

11.把f(x,y)分配給2-集群(Gi,j)

12.Endif

13.Endfor

14.For3-集群(Gi,j)中的每個組Gu,v

15.If不在polynomial_sharing(Gu,v, Gi,j)中

16. 生成一個f(x,y)

17. 把f(x,y)分配給3-集群(Gi,j)

18.Endif

19.Endfor

20.Endfor

2.3 直接密鑰建立階段

在傳感器節點部署到目標區域后，每個傳感器節點必須找到與其相鄰節點的共享密鑰空間。假設節點nA具有3個空間IDfi,fj,fk，需要與其鄰居發現共享密鑰空間。它廣播一個1-跳發現消息—密鑰空間發現消息(KSDM,key-space discovery message)如下：

(nA,RvA,H(fi⊕RvA),H(fj⊕RvA),H(fk⊕RvA))

(5)

式中,H為哈希函數，⊕為異或運算。

當A的一個鄰居(設為B)接收到這個消息時，它會發現它可以與A共享3個、1個或不共享公用密鑰空間。類似地，節點A也接收到B的KSDM消息并發現公用密鑰空間。如果共享至少1個公用密鑰空間，則B和A之間的成對密鑰在B點計算如下：

KB,A=f(nB⊕(RvB,nA⊕RvA)

(6)

在獲得KB,A之后，節點B從它的內存中刪除RvA值。計算A點的成對密鑰的過程與此類似。由于二元多項式的對稱性，所以：

KA,B=KB,A

(7)

完成這一階段后，除了前一階段的密鑰空間信息和一個隨機值外，每個節點還存儲一個與其相鄰節點的成對密鑰列表。

2.4 間接密鑰建立階段

如果兩個相鄰節點之間沒有公用密鑰空間，則需要通過一個或多個中間節點建立一個路徑密鑰，實現過程如下。

在直接密鑰建立階段之后，每個節點A知道其安全鄰接節點的集合SA。源節點A希望與其鄰居B建立一個成對密鑰，但是B和A不共享任何密鑰空間。在這種情況下，A生成一個會話密鑰KS，并找到在SA中與節點B有相同的組ID或包含節點B的組的相鄰組ID的節點C，然后節點A向節點C發送一條包含通過密鑰KA,C加密的KS消息。然后，節點C通過密鑰KC,B保護的安全通道向B發送會話密鑰，則密鑰KS作為節點A和節點B之間的成對密鑰。

在以上3個階段完成之后，每個節點都存儲一個包含鄰居的IDs和對等的密鑰表。密鑰材料的存在使得傳感器網絡能夠增加新的節點供后面替換。

2.5 傳感器節點的添加和刪除

為了增加一個新的傳感器節點，密鑰建立服務器只需要將相關的多項式共享預先分配給新節點，類似于預分配階段。由于密鑰空間的大小是有限的，添加的傳感器越多，該單元中的安全性就越低；刪除方法很簡單。每個傳感器節點只需要存儲一個與自身共享至少一個二元變量多項式的被破壞傳感器的黑名單IDs。如果有超過t個被破壞節點共享同一個多項式，則擁有該多項式的非被破壞節點將刪除該多項式和所有相關的被破壞節點。

算法2為密鑰建立和分配實現的偽代碼。

算法2:密鑰建立和分配算法

1.ForN中每個傳感器節點nADo

2. 對nA的預加載數據生成并插入一個隨機值RvA;

3.Endfor

4.For(中每個集群CiDo

5.從F中獲取一個二元多項式fi(x,y);

6.ForCi中每個節點nADo

8. 插入nA的預加載數據{bj|j=0,...,t};

9. 將多項式的ID(也稱為了空間-ID)fi插入到nA;

10.Endfor

11.從F中刪除fi(x,y);

12.Endfor

3 算法仿真實驗結果及分析

仿真中采用的度量指標如下。

1)網絡連通性：包括局部連通性和全局連通性。局部連通性是指一個節點可以在其傳輸范圍內與相鄰節點連接的概率。全局連通性是最終密鑰圖G中形成最大獨立連通部分的傳感器節點數目與整個網絡的大小之比。

2)內存開銷和運行時間：內存開銷為模型中在節點上存儲密鑰材料的內存需求，運行時間為密鑰空間形成和分配，直至最終兩個節點獲得成對密鑰所消耗的時間。

3)對捕獲節點攻擊的恢復能力：對手通常發起節點捕獲攻擊，以竊聽網絡中的安全通道，或者利用捕獲節點泄露的密鑰材料進行節點復制攻擊。在此分析中，我們評價節點破壞攻擊對剩余網絡通信的影響，即對手能夠發現一個二元多項式的概率，這意味著它們可以泄露所有由這個多項式得到的加密安全連接。

3.1 系統配置

采用表1中的設置進行仿真和數值分析。在這種場景下，假設節點部署遵循二維高斯分布，其PDF函數如式(1)所示。

表1 仿真設置

3.2 網絡連通性

假設A(ni,nj)和B(ni,nj)為事件，節點ni為節點nj的鄰居，它們共享至少1個共用密鑰空間。局部連通性可以計算為：

Plocal=P(B(ni,nj)|A(ni,nj))=

(8)

節點ni∈Gi為節點nj(xj,yj)的鄰居的概率是在節點nj周圍半徑為R的圓上的PDFf(ni)的積分：

(9)

由于nj按式(1)分布在組Gj中，所以ni∈Gi為nj∈Gj的鄰居的概率為：

(10)

因此:

(11)

用S(Gi)表示Gi相鄰組的集合，則有：

(12)

由于傳感器節點是在給定的組中以相等的概率被選擇的，因此局部連通性可以計算為：

(13)

用d=k×σ表示兩個相鄰單元格的兩個部署點之間的距離(k為比例系數)，這個值會影響網絡的局部連通性和全局連通性。當k值較大時，則一個組中幾乎每個節點都位于自己的單元格區域內，而且相鄰節點都來自自己的組。在這種情況下，局部連通性非常高，但網絡完全被分割成單獨的部分，這意味著全局連通性非常低；當d值較小時，可能局部連通性較低，但全局連通性較高。因此，選擇合適的d值會影響網絡的連通性。由于無線傳感器網絡中密鑰建立的最終目標是形成盡可能高的全局連通性網絡，因此必須適當選擇相鄰部署點的距離d的值。

表2所示為通過改變k來得到不同的d值獲得的局部連通性和全局連通性。可以看到，當兩個相鄰單元格的兩個部署點之間的距離過小(k=0.4,0.6,0.8或1.0)時，在任意節點A，其周圍分布著許多非相鄰單元格的節點，這些節點不與節點A共享任何密鑰空間，因此降低了局部連通性和全局連通性；而當選擇合適的部署點距離值時，模型能夠獲得較高的局部和全局連通性，如當k=1.5時，全局連通性為0.999 0，即網絡中只有0.01%的節點是浪費的。

表2 仿真結果

3.3 內存開銷和運行時間

在無線傳感器網絡協議設計中，長壽命是關鍵目標。在本文模型中，我們最小化相鄰節點之間發現公用密鑰空間的廣播數據需求，1-跳廣播消息長度為：

節點ID的大小+ Rv的大小+3×H的大小(bits)

(14)

用于存儲從多項式得到的密鑰材料的內存大小為：

M=3×(t+1)log2q+節點ID的大小+Rv的大小(bits)

(15)

這個值連同共享一個多項式的節點數量影響成對密鑰建立之前節點受攻擊的恢復能力。這將在3.4中詳細討論。

將本文模型與文獻[13]～[15]的模型在不同網絡規模下的內存開銷即所需要的內存大小進行比較，結果如表3所示。從表3可見，不同模型隨著網絡規模的增大，內存開銷也增大，這是因為要完成更多節點間的密鑰空間計算、交換和配對，但是本文模型的內存開銷始終是最小的。這是由于本文模型在密鑰建立階段將全部節點進行集群分組，而且盡可能使傳感器節點均勻分布，減少了密鑰分配和建立階段計算空間的存儲開銷和信息交換。

表3 不同模型的內存開銷比較

將本文方案與文獻[13]～[15]的模型在不同網絡規模下的的運行時間進行比較，結果如表4所示。從表4可以看到，不同模型隨著網絡規模的增大，運行時間也是增加的，這是由于隨著節點數目的增大，不僅增加了節點部署和多項式分配的時間開銷，更重要的要花更多時間完成密鑰空間的計算和配對；但是本文模型在密鑰建立階段采用了密鑰材料的預加載和1-跳密鑰空間發現消息來實現相鄰節點的共享密鑰空間分配，所以仍然有最小的運行時間。

表4 不同模型的運行時間比較

運行時間/ms網絡規模本文模型文獻[13]模型文獻[14]模型文獻[15]模型 N=2 0001 295 2 0791 664 1 648N=4 0002 045 2 8232 456 2 418N=6 0002 879 3 6763 246 3 217N=8 000 3 759 4 6864 245 4 203N=10 0004 768 5 7665 379 5 318

3.4 對捕獲節點攻擊的恢復能力

由于傳感器網絡工作環境通常比較惡劣，傳感器節點很容易被捕獲并泄露信息。捕獲的傳感器節點數量依賴于多項式的次數，也就是存儲密鑰材料的內存。對捕獲節點攻擊的恢復能力定義為當x個節點被攻破時，泄漏一個多項式的概率，這相當于在未受損的傳感器節點之間泄漏直接密鑰。

文獻[14]表明，基于多項式的方案具有t-安全性：即除非公開了一個二元多項式的超過t個多項式共享，否則對手不會知道使用該多項式建立的非受損節點的成對密鑰。因此，本文模型的安全性依賴于共享同一多項式的傳感器節點的平均數量，即期望位于3個相鄰六邊形單元格中的傳感器節點的數量。

把期望位于一個單元格內的傳感器節點的平均數量表示為Nc，則共享一個多項式的傳感器節點的平均數量可計算為：

(16)

式中，?為傳感器節點密度。

如前所述，存儲密鑰材料的內存需求為M(bits)，因此二元多項式的次數為：

t=[M/3]-1

(17)

只要NG≤t，本文模型就能很好地抵抗節點捕獲。換句話說，受損的傳感器節點不會導致非受損傳感器節點之間共享的直接密鑰受損。

由于攻擊是隨機的，假設網絡中有一小部分傳感器節點pc被攻擊者破壞。在具有多項式共享的NG個傳感器節點中，正好有i個傳感器節點被攻擊的概率可以計算為：

(18)

因此，二元多項式被破壞的概率可計算為：

(19)

圖2所示為本文模型在不同部署點距離d節點受損攻擊時仿真得到的網絡恢復能力。可以看到，部署點距離越長即單元格越大，對節點受損攻擊的網絡恢復能力越脆弱。這是因為當單元格較大時，在一個單元格中有更多的傳感器節點共享一個密鑰空間，從而導致安全性降低。

圖2 不同部署點距離下節點受損攻擊時網絡的恢復能力

圖3所示為本文模型在不同內存大小M(bits)情形下節點受損攻擊時仿真得到的網絡恢復能力。可以看到，隨著內存的增大，網絡的恢復能力增強，這是因為多項式的次數更高，就越不容易被攻擊破壞。

圖3 不同內存大小情形下節點受損攻擊時網絡的恢復能力

圖4所示為不同模型的傳感器節點被攻擊時的網絡恢復能力比較。可見，與文獻[13]、[14]和[15]模型相比，本文模型在節點受損時的具有更好的安全性。這是由于本文模型存在密鑰預分配階段，而且離線服務器為每個集群生成一個包含足夠多的t次對稱二元多項式多池，然后將每個多項式分配給每個集群中的所有傳感器節點，以確保每個節點都要存儲3個t次二元多項式的共享知識，對手更難獲得融合多個節點的密鑰材料，從而提高了安全性。

圖4 傳感器節點被攻擊時不同模型的網絡恢復能力比較

4 結束語

本文提出了一種可實現的基于多項式的密鑰預分配模型，它利用了高斯分布的預部署知識。同時還表明了模型在網絡連通性、通信開銷和內存需求等方面具有的優勢。它還可以抵御非捕獲節點間受損附加密鑰的攻擊；未來的研究將集中在部署誤差率對網絡連通性的影響和分析多跳間接密鑰建立的可能性。