在感測網路中建立共享金鑰的研究

Pairwise Key Establishment in Sensor Networks

廖燕華(Yen-Hua Liao)

指導教授 ： 雷欽隆

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2011年)

https://doi.org/10.6342/NTU.2011.02484

摘要

由於感測點的資源有限，公開金鑰密碼系統和金鑰分配中心並不是那麼適合在感測網路中使用。反而是對稱式的密碼系統較適合使用於感測網路的環境。因此，共享金鑰的建立變成了維護感測網路安全的基本工作。然而以多項式為基底的金鑰分配方式卻只能夠提供機率性的認證服務。目前，許多的金鑰管理系統皆以它為基礎。在這篇論文中，我們首先介紹了一個新穎的以馴映射為基底的金鑰分配方法。這個方法可以提供決定性的認證服務。以這個方法為基礎，我們提出了一套金鑰分配的架構。
在這個架構中，我們分別發展出局部的對稱馴映射分配系統、以超立方為基底的金鑰分配系統、以格子為基底的金鑰分配、強化的以馴映射為基底的金鑰分配、以群為基底的金鑰分配、以及在行動感測網路中建立共享金鑰。
在局部的對稱馴映射分配系統中，我們利用感測點的相關位置的資訊來做金鑰的分配。分析的結果顯示，這個系統除了能夠提供決定性的認證服務之外，在相鄰的兩個感測點之間有極高的機率能夠建立一把直接金鑰、並且當感測點遭遇危害時能有極好的恢復能力。
以超立方為基底的金鑰分配系統有一些優點，包括任何兩個感測點之間皆能夠建立一把共享金鑰、當感測點遭遇危害時仍有恢復力、以及花費較少的儲存空間、計算量和傳輸量。然而它也只能夠提供機率性的認證服務。因此，我們先將前人的以超立方為基底的金鑰分配改善成一個能夠提供決定性認證服務的系統。然後，我們更進一步地提出了以格子(超立方的一種情況)為基底的金鑰分配系統的一個變形。除了保留了被改善的以超立方為基底的金鑰分配系統的優點之外，分析的結果還顯示，這個變形系統花費更少的計算量、並且在相鄰的兩個感測點之間有更高的機率能夠建立一把直接金鑰。
雖然，我們能夠利用感測點的相關位置的資訊來改善金鑰管理系統，然而，在某些應用中，感測點的相關位置的資訊未必能夠被取得。因此，我們另外利用了異質感測點來強化以馴映射為基底的金鑰分配方法。分析與模擬的結果皆顯示，這個強化版在初始化的時間花費、儲存量和傳輸量的花費、建立共享金鑰的機率、以及當感測點遭遇危害時的恢復能力上，都有更好的表現。我們更進一步將這個強化版延伸到一個以群為基底的金鑰分配系統。分析與實驗的結果顯示，除了保留了強化版的優點，這個以群為基底的系統還能有更有效率的金鑰分配過程、在建立共享金鑰時的電力消耗量更少、並且當感測點遭遇危害時能有完美的恢復能力。最後，我們將這個以群為基底的系統應用於行動感測網路中來建立行動感測點之間的共享金鑰。

關鍵字

感測網路 ； 馴變換 ； 金鑰管理 ； 金鑰分配 ； 共享金鑰 ； 網路安全 ； 認證

並列摘要

Due to resource constraints on sensor nodes, public key cryptography and key distribution center (KDC) are not desirable to use in sensor networks. Instead, symmetric cryptosystem using preloaded keys is suitable for this environment. In such a solution, pairwise key establishment is a fundamental task for securing sensor networks. However, the conventional polynomial-based key predistribution approach, on which many existing key management schemes in sensor networks were based, can only offer probabilistic authentication. In this dissertation, we first develop a novel tame-based key predistribution approach, where we exploit tame automorphisms to get symmetric and two-one bivariate maps for pairwise key establishment. This tame-based approach can provide deterministic authentication between two parties. We then present a general framework for key predistribution, in the basis of the tame-based approach.
Based on this framework, we propose several schemes of pairwise key establishment. They are the local symmetric-tame maps predistribution scheme, robust hypercube-based key predistribution scheme, robust grid-based key predistribution scheme, enhanced tame-based key predistribution scheme, cluster-based key predistribution scheme, and pairwise key establishment in mobile sensor networks. In the local symmetric-tame maps predistribution scheme, we utilize the location information of sensor nodes for key predistribution. The analysis demonstrates that, in addition to being able to provide deterministic authentication service, the scheme not only has significantly better performance, but can also achieve greater resilience on security than existing schemes.
The hypercube-based key predistribution scheme is superior to other methods in some features. These features include being able to establish a pairwise key between any two sensor nodes, having resilience against node compromises, and the low memory, computation and communication overhead. Nevertheless, it can only provide probabilistic authentication service for sensor networks. In this dissertation, we improve the hypercube-based scheme to provide deterministic authentication service. Then we further present a variance of the grid-based scheme (one case of the hypercube-based scheme). It turns out that in addition to keeping the advantages of the improved hypercube-based scheme, the analysis demonstrates that the variance of the grid-based scheme can have the lower computation overhead and higher probability of having a direct pairwise key between two neighboring sensor nodes (two sensor nodes within the transmission range).
Although we can utilize the location information to improve the performance of key management scheme in sensor networks, however, in some applications, the location information of sensor nodes may not be available. Therefore, in this dissertation, we additionally take advantage of heterogeneous sensor nodes to enhance the tame-based key predistribution scheme. The analysis and simulation demonstrate that the enhanced scheme has better performance in terms of the initialization time, memory overhead, communication overhead, probability to establish a pairwise key between two neighboring nodes, and resilience against node compromises. We further extend the enhanced scheme to a cluster-based key predistribution scheme. The analysis and experiment indicate that in addition to preserving the advantages of the enhanced scheme, the cluster-based scheme has more efficient key predistribution process, much less energy consumption for the pairwise key establishment, and perfect resilience against node compromises. Finally, we apply the cluster-based scheme in mobile sensor networks to support the pairwise key establishment between mobile sensor nodes.

並列關鍵字

Sensor networks ； Tame automorphism ； Key management ； Key predistribution ； Pairwise key ； Network security ； Authentication

參考文獻

[2] L. Ho, M. Moh, Z. Walker, T. Hamada, and C. F. Su, A prototype on RFID and sensor networks for elder healthcare: progress report, SIGCOMM’05 Workshops, Aug. 2005.

[3] T. H. Kim, S. I. Lee, Y. D. Lee, and W. K. Hong, Design and evaluation of in-vehicle sensor network for web based control, Proc. 13th IEEE Int’l Symp. and Workshop on Engineering of Computer Based Systems (ECBS’06), Mar. 2006.

[4] The cricket indoor location system an NMS project @ MIT CSAIL.htm.

[9] I. C. Lin, P. Y. Chang, and C. C. Chang, A key management scheme for sensor networks using bilinear pairings and gap Diffie-Hellman group, International Journal of Innovative Computing, Information and Control, vol. 6, no. 2, pp. 809-816, 2010.

[11] F. Delgosha and F. Fekri, Threshold key-establishment in distributed sensor networks using a multivariate scheme, Proc. INFOCOM, Apr. 2006.