無線感測網路是由一群低成本的微型感測器所組成的無線通訊網路，它們可能散佈在某特定區域進行感測資料收集的任務。為了避免一些敏感的機密資料遭到敵人的竊取，於是在無線感測網路中有關安全的議題愈來愈受到重視，並且隨著科技的日新月異，原本不太適用於無線感測網路的公開鑰匙密碼學也會逐漸地廣泛地被應用無線感測網路。本論文提出了一種基於One-way Hash Chain的分散式投票節點撤銷機制，它是在散佈網路節點之前先由基地台預先分發憑證給各個節點，之後各個節點就可以基於這個憑證做認證管理或是當發現有節點被入侵時可以進行節點撤銷的運作。

在效能評估上，跟目前現有的節點撤銷機制比較，由於我們使用的是基於公開鑰匙密碼學的分散式投票節點撤銷機制，所以相對來說我們的計算成本是比較高的，但是我們使用了One-way Hash Function和XOR運算來降低投廢除票所需的能源消耗，所以新機制的能源消耗對於硬體能有限的微型感測器是能夠負荷的，並且本機制的安全性分析方面顯示出此機制對於被已入侵節點主動攻擊有較良好的抵禦能力，還有因為節點撤銷算是一個稀有發生的事情，它的安全性考量卻對整個網路來說非常重要，所以既然它是一個稀有發生的事情我們可以假設我們能夠提供更多計算頻寬資源來負擔，兩相比較之下此機制比較高的計算成本是我們可以接受的。

Wireless sensor network is composed of a large number of low-cost sensor nodes that are small in size and communicate untethered in short distances. The security issue in distributed sensor networks (DSNs) has been drawing considerable research attention in recent years. With the advance of technology, Public Key Cryptography (PKC) will sooner or later be widely used in wireless sensor networks. This thesis presents a based on One-way Hash Chain distributed voting way node revocation scheme which Base Station will sign the certificates to every node before deployment, and a certificate allows a node to prove that it is authorized to access some service such as data authenticate or node revocation.

Evaluation results show that when we compared with the other node revocation scheme because of what we used is based on PKC distributed voting way node revocation scheme, so calculation cost is comparatively higher. We exploit One-way Hash Function and XOR operation to reduce the energy consumption when casting a revocation vote. After that the energy consumption of new scheme is able to accept by hardware-constrained sensor node. The security analysis of this scheme shows that it has better ability to resistance the active adversaries. Node revocation is a rare happened event, but the security of it considers to be very important in the whole network. Since it is a rare happened event we can suppose that when it happens we can offer more calculation resources. According to previous discussions we can accept the higher calculation cost from our new scheme.

目錄

中文摘要.................................................Ⅰ
英文摘要	................................................Ⅲ
目錄.....................................................Ⅴ
圖表目錄...............................................VIII

第一章 緒論...............................................1
第二章 相關研究背景.......................................4
2.1 EG Scheme.............................................4
2.2 CPS Scheme 2003.......................................5
2.2.1 The Original Scheme.................................5
2.2.2 The Enhanced Scheme.................................8
2.3 利用門檻秘密分享之節點撤銷機制[5]....................10
2.3.1 門檻秘密分享之介紹.................................11
2.3.2 節點撤銷機制之架構.................................11
2.4 CPS Scheme 2005......................................13
2.4.1 節點初始化.........................................14
2.4.2 投票廢除節點程序...................................17
2.4.3 分散式撤銷之基本特性...............................18
2.5 Attacker & Communications Model......................19
第三章 PKC in Wireless Sensor Networks...................21
3.1 Authenticating Public Keys in Sensor Networks........21
3.1.1 解決公鑰認證.......................................22
3.1.2 解決通訊額外負擔...................................23
3.2 PKC in Wireless Sensor Networks......................25
3.2.1 ECC in Sensor Networks.............................26
3.2.2 RSA in Sensor Networks.............................31
3.2.3 Comparing ECC with RSA.............................32
3.3 應用PKC的可行性評估..................................33
3.4 新機制採用憑證撤銷清單之由來.........................35
3.4.1 在Ad Hoc網路中使用CRL之介紹[13]....................36
3.4.2 在感測網路中使用CRL之構想..........................38
第四章 新節點撤銷機制之架構..............................40
4.1 新機制運作方式.......................................40
4.1.1 憑證產生方式.......................................43
4.1.2 憑證查核方式.......................................44
4.2 節點撤銷步驟.........................................45
4.3 新分散式投票憑證撤銷機制.............................48
第五章 效能評估..........................................51
5.1 非對稱式加密與對稱式加密之比較.......................51
5.2 新機制之時間和空間複雜度.............................54
5.3 分散式投票須符合條件之分析...........................54
5.4 新機制與CPS05[7]特性之比較...........................56
5.5 新機制與3.5節方法之比較..............................57
5.5.1 安全方面...........................................57
5.5.2 效率方面...........................................58
5.5.3 延展性方面.........................................59
5.6 能源評估.............................................60
5.7 利用門檻秘密分享節點撤銷機制[5]、CPS05[7]與新機制之綜合比較.....................................................63
第六章 結論..............................................65
參考文獻.................................................69


圖表目錄

圖 2.1：[3]其空間複雜度示意圖.............................7
圖 2.2：ㄧ個Merkle tree的範例.............................9
圖 2.3：[3]加入Merkle tree後，其空間複雜度示意圖.........10
圖 2.4：Block Cipher演算法示意圖.........................14
圖 2.5：預先儲存在節點內的資訊示意圖[7]..................16
圖 3.1：利用Merkle tree認證公鑰示意圖....................23
圖 3.2：一個Merkle forest的示意圖........................25
圖 3.3：內含憑證產生過程示意圖[9]........................27
圖 3.4：混合式鑰匙建立協定示意圖[9]......................30
圖 4.1：整體機制流程圖...................................42
圖 4.2：憑證運作示意圖...................................45
圖 4.3：新機制運作實例...................................50

表 3.1：ECC和RSA在兩個平台的相關比較表[11]...............33
表 3.2：MICA2上運作PKC相關能源消耗表[12].................34
表 5.1：節點端能源消耗表示表.............................62
表 5.2：[5]、[7]與新機制綜合比較表.......................63
表 6.1：評估模式表.......................................68

[1] I. F. Akyildiz, Su Weilian, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, Vol. 40, Aug. 2002, pp. 102-114

[2] L. Eschenauer and V. D. Gligor, “A key-Management Scheme for Distributed Sensor Networks,” Proc. of 9th ACM Conference on Computer and Communication Security, Nov. 2002, pp. 41-47.

[3] H. Chan, A. Perrig, and D. Song, “Random Key Predistribution Schemes for Sensor Networks,” Proc. of IEEE Symposium on Research in Security and Privacy, May 2003, pp. 197-213.

[4] R. Merkle, “Protocols for public key cryptosystems,” Proc. of 1980 IEEE Symposium on Security and Privacy, Apr. 1980, pp. 122-134.

[5] 趙惇豪,”無線感測網路中金鑰分發及節點撤銷機制,” 淡江大學電機工程學系積體電路與計算機系統組碩士班碩士論文,Jun. 2005, Ch.5, pp. 43-45.

[6] A. Shamir, “How to Share a Secret,” Communications of the ACM, Vol. 22, No. 11, Nov. 1979, pp. 612-613.

[7] 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, July-Sept. 2005, pp. 233-247.

[8] W. Du, R. Wang, and P. Ning, “An Efficient Scheme for Authenticating Public Keys in Sensor Networks,” Proc. of the 6th ACM international symposium on Mobile ad hoc networking and computing, 2005, pp. 58-67.

[9] Q. Huang, J. Cukier, H. Kobayashi, B. Liu and J. Zhang, “Fast Authenticated Key Establishment Protocols for Self-Organizing Sensor Networks,” Proc. of the 2nd ACM international conference on Wireless sensor networks and applications, Sept. 2003, pp. 141-150.

[10] R. Watro, D. Kong, S. Cuti, C. Gardiner, C. Lynn, and P. Kruus, “TinyPK Securing Sensor Networks with Public Key Technology,” Proc. of the 2nd ACM workshop on Security of ad hoc and sensor networks, Oct. 2004, pp. 59-64.

[11] N. Gura, A. Patel, A. Wander, H. Eberle, and S. C. Shantz, “Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs,” Aug. 2004.

[12] D. J. Malan, M. Welsh, and M. D. Smith, “A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography,” In The 1st IEEE International Conference on Sensor and Ad Hoc Communications and Networks, Oct. 2004, pp. 71-80.

[13] T. Kaya, G. Lin, G. Noubir, and A. Yilmaz, “Secure Multicast Groups on Ad Hoc Networks,” Proc. of the 1st ACM workshop on Security of ad hoc and sensor networks, 2003, pp. 94-102.

[14] J. Li, Y. Zhu, H. Pan, and S. Liu, “A Distributed Certificate Revocation Scheme Based on One-way Hash Chain for Wireless Ad Hoc Networks,” Proc. of 2nd IEEE International Conference on Mobile Technology, Applications and Systems, Nov. 2005.