臺灣博碩士論文加值系統

無線感測網路（Wireless Sensor Networks, WSNs）是由有限的計算和通訊能力之感測節點（sensor nodes）所組成，感測節點的功能可收集所需的資料，透過連結的網路將訊息傳遞至工作站等，再加以分析感測資料。這樣的網路型態最早使用於軍事用途，將感測節點散佈至敵方的環境，收集所需的情報；而近年來無線感測網路也漸漸應用於生活中。由於無線感測網路的應用層面越來越廣泛，相對的安全議題也越來越受重視。要使無線感測網路兩節點之間能安全地溝通，成對金鑰的建立是必須的安全機制。由於感測節點的資源能力有限，傳統的安全機制如公開金鑰加密系統與集中式金鑰分配機制並不適合用於無線感測網路，因此近年來許多針對無線感測網路的安全機制被提出。在本篇論文，我們提出了一個金鑰預先分配機制，使鄰近的兩節點之間可以建立成對金鑰，並有效地更新被捕獲的金鑰以撤銷被捕獲之節點。與之前其他學者所提出的方法比較，我們的機制具有較高的連結率，不論在同一群組或來自鄰近群組的兩節點都可直接建立成對金鑰；並能更有效地抵抗節點被捕獲與預防被捕獲節點的共謀攻擊。

Wireless sensor networks (WSNs) are composed of sensor nodes which have limited computations and communication capabilities. Sensor nodes can collect information needed, and transmit data to the base station through Internet. Then the base station analyzes the sensing information. The first application of wireless sensor networks is for military purpose, that is, sensor nodes are deployed in hostile environment and collect information needed. The applications of wireless sensor networks are currently extended popularly so that the security issues are more and more important. Pairwise key establishment is a necessary security service in wireless sensor networks for secure communication between any two nodes. Due to the limited resources of the sensor nodes, traditional security protocols such as public key cryptography and centralized key distribution are not suitable for wireless sensor networks. Recently, many security protocols of wireless sensor networks have been proposed. In this paper, we presents a novel key predistribution scheme for establishing pairwise key between nodes and efficiently rekeying the compromised keys to revoke the compromised nodes. Compared with the previous schemes, our scheme has a high probability to establish the pairwise keys whatever the nodes are placed in the same group or in the neighboring groups. A powerful procedure for the tolerance of node capture, and an efficient strategy to prevent the compromised nodes from colluding attacks are also discussed in this thesis.

中文摘要 i
ABSTRACT ii
目錄 iv
圖表目錄 viii
表格目錄 x
第一章　緒論 1
1.1　無線感測網路之安全議題 1
1.2　無線感測網路金鑰管理機制概觀 2
1.2.1　金鑰管理 2
1.2.2　金鑰管理應用於無線感測網路的限制 3
1.3　主要貢獻 4
1.4　論文架構 4
第二章　相關研究 5
2.1　目前金鑰管理機制之發展 5
2.2　靜態金鑰管理機制 6
2.2.1　單一全網路金鑰（Single Network-Wide Key） 6
2.2.2　非對稱式密碼系統（Public key cryptographic system） 7
2.2.3　完全成對金鑰共享（Fully Pairwise-Shared Keys） 9
2.2.4　基本隨機金鑰預先分配機制（Basic Random Key Predistribution Scheme） 11
2.2.5　隨機成對金鑰預先分配機制（Random-Pairwise keys Scheme） 13
2.2.6　基於多項式池之金鑰預先分配機制（Polynomial Pool-Based Key Predistribution） 14
2.2.7　基於群組之金鑰預先分配機制（Group-Based Key Pre-Distribution） 15
2.3　動態金鑰管理機制 17
2.3.1　EBS: Exclusion Basis Systems 17
2.3.2　SHELL 19
第三章　系統架構與部署模式 27
第四章　具位置相關並可抵抗共謀攻擊之無線感測網路成對金鑰預先分配機制 29
4.1　背景 29
4.1.1　基於多項式之金鑰預先分配機制[2] 29
4.1.2　EBS系統[9] 30
4.2　方法概述 30
4.3　金鑰預先分配 33
4.4　EBS系統的建立與管理金鑰的分配 34
4.5　成對金鑰的建立 36
4.6　金鑰更新 38
4.7　範例說明 41
4.7.1　金鑰預先分配 42
4.7.2　EBS系統的建立與管理金鑰的分配 44
4.7.3　成對金鑰的建立 44
4.7.4　金鑰更新 46
第五章　共謀攻擊的預防 49
5.1　實驗結果與討論 53
5.2　實驗範例 57
第六章　效率與安全性分析 60
6.1　區域連結率（Local Connectivity） 60
6.2　效率分析 61
6.2.1　金鑰儲存（storage overhead） 61
6.2.2　通訊效率（communication overhead） 62
6.2.3　計算效率（computation overhead） 63
6.3　安全性分析 64
6.4　與先前方法之比較 66
第七章　總結與未來研究方向 71
參考文獻 73

[1] T. Bass, “Intrusion Detection Systems and Multisensor Data Fusion,” Communications of the ACM, vol. 43, no. 4, April 2000, pp. 99–105.

[2] C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro, and M. Yung, “Perfectly-Secure Key Distribution for Dynamic Conferences,” in Advances in Cryptology – CRYPTO ’92, LNCS 740, 1993, pp. 471–486.

[3] H. Chan, V. D. Gligor, A. Perrig, and G. Muralidharan, “On the Distribution and Revocation of Cryptographic Keys in Sensor Networks,” IEEE Transactions on Dependable and Secure Computing, vol. 2, no. 3, July-September 2005, pp. 233–247.

[4] H. Chan, A. Perrig, and D. Song, “Random Key Predistribution Schemes for Sensor Networks,” in Proc. IEEE Symp. Security and Privacy, May 2003, pp. 197–213.

[5] H. Chan, A. Perrig, and D. Song, “Key Distribution Techniques for Sensor Networks,” Wireless sensor networks, 2004, pp. 277–303.

[6] W. Du, J. Deng, Y. S. Han and P. K. Varshney, “A Pairwise Key Predistribution Scheme for Wireless Sensor Networks,” in Proceedings of 10th ACM Conference on Computer and Communications Security (CCS’03), October 2003, pp. 42–51.

[7] W. Du, J. Deng, Y. S. Han, and P. K. Varshney, “A Key Management Scheme for Wireless Sensor Networks Using Deployment Knowledge,” IEEE Transactions on Dependable and Secure Computing, vol. 3, no. 1, January-March 2006, pp. 62–77.

[8] L. Eschenauer and V. Gligor, “A Key-Management Scheme for Distributed Sensor Networks,” in Proc. Ninth ACM Conf. Computer and Comm. Security, November 2002, pp. 41–47.

[9] M. Eltoweissy, H. Heydari, L. Morales, and H. Sadborough, “Combinatorial Optimization of Key Management in Group Communications,” J. Network and Systems Management, vol. 12, no. 1, Mar. 2004, pp. 33–50.

[10] D. Eastlake and P. Jones, “US Secure Hash Algorithm 1 (SHA-1),” RFC 3174, IETF, September 2001.

[11] M. Eltoweissy, M. Moharrum, R. Mukkamala, “Dynamic Key Management in Sensor Networks,” IEEE Communications Magazine, vol. 44, no. 4, April 2006, pp. 122–130.


[12] P. Erdos and A. Rényi, “On the Evolution of Random Graphs,” Publ. Math. Inst. Hungar. Acad. Sci. 5, 1960, pp. 17–61.

[13] D. Huang, M. Mehta, D. Medhi, and L. Harn, “Location-Aware Key Management Scheme for Wireless Sensor Networks,” in Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, pp. 29–42.

[14] K. Ilgun, R. A. Kemmerer, and P. A. Porras, “State Transition Analysis: A Rule-Based Intrusion Detection Approach,” IEEE Transactions on Software Engineering, vol. 21, no. 3, 1995, pp. 181–199.

[15] S. Kumar and E. H. Spafford, “A Software Architecture to Support Misuse Intrusion Detection,” in Proceedings of the 18th National Information Security Conference, 1995, pp. 194–204.

[16] A. Leon-Garcia, Probability and Random Processes for Electrical Engineering, second ed. Reading, Mass.: Addison-Wesley, 1994.

[17] D. Liu and P. Ning, “Establishing Pairwise Keys in Distributed Sensor Networks,” in Proceedings of 10th ACM Conference on Computer and Communications Security (CCS’03), October 2003, pp. 52–61.

[18] D. Liu and P. Ning, “Location-Based Pairwise Key Establishments for Static Sensor Networks,” in 2003 ACM Workshop on Security in Ad Hoc and Sensor Networks (SASN '03), October 2003, pp. 72–82.

[19] D. Liu, P. Ning, and W. Du, “Group-Based Key Pre-Distribution in Wireless Sensor Networks,” in Proceedings of 2005 ACM Workshop on Wireless Security (WiSe 2005), September 2005, pp. 11–20.

[20] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, “Efficient and Secure Source Authentication for Multicast,” Network and Distributed System Security Symposium, NDSS’01, February 2001, pp. 35–46.

[21] T. Park and K. G. Shin, “LiSP: A Lightweight Security Protocol for Wireless Sensor Networks,” ACM Transactions on Embedded Computing Systems (TECS), vol. 3 no. 3, August 2004, pp. 634–660.

[22] A. Perrig, R. Szewczyk, V. Wen, D. Culler, and J. D. Tygar, “SPINS: Security Protocols for Sensor Networks,” in ACM Wireless Networks Journal (WINE), vol. 8, no. 5, September 2002, pp. 521–534.

[23] R. Rivest, “The MD5 Message-Digest Algorithm,” RFC1321, MIT Laboratory for Computer Science and RSA Data Security, Inc., April 1992.

[24] Z. Yu and Y. Guan. “A Key Pre-distribution Scheme Using Deployment Knowledge for Wireless Sensor Networks,” in Proceedings of ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), April 2005, pp. 261–268.

[25] M. F. Younis, K. Ghumman, and M. Eltoweissy, “Location-Aware Combinatorial Key Management Scheme for Clustered Sensor Networks,” IEEE Transations on Parallel and Distributed Systems, vol. 17, no. 8, August 2006, pp. 865–882.


[26] Y. Zhang and W. Lee, “Intrusion Detection in Wireless Ad-Hoc Networks,” in Proceedings of the 6th IEEE/ACM International Conference on Mobile Computing and Networking (MobiCom’00), 2000, pp. 275–283.

[27] R. Zhang, D. Qlan, C. Ba, W. Wu, and X. Guo, “Multi-Agent Based Intrusion Detection Architecture,” in Proceedings of IEEE International Conference on Computer Networks and Mobile Computing, 2001, pp. 494–504.