Internet-Draft Suho Park Expires: June 8, 2006 KT Md. Abdul Hamid Kyung Hee University Choong Seon Hong Kyung Hee University December, 2005 Routing Security in Sensor Network: HELLO Flood Attack and Defense Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on June 8, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract In this document, We consider Wireless Sensor Network (WSN) security and focus our attention to tolerate damage caused by an adversary who has compromised deployed sensor node to modify, block, or inject packets. We adopt a probabilistic secret sharing protocol where secrets shared between two sensor nodes are not exposed to any other nodes. Adapting to WSN characteristics, we incorporate these secrets with bidirectional verification and multipath routing to multiple base stations to defend against HELLO flood attacks. We then analytically show that our defense mechanisms against HELLO flood attack can tolerate damage caused by an intruder Hamid, et al. Expires June 8, 2006 [Page 1] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense Table of Contents 1. Introduction . . . . . . . . . . . . . . ........... . 2 2. Contribution of the Proposal . . . . . . . . . . . . . 3 3. Network Assumption and Threat Model . . . . . . . . ... 3 4. Key Sharing Protocol . . . . . . . . ................. 3 4.1 Secret instantiation by Tree Protocol . . . . .... ... 3 4.2 Computing the vulnerability of security. . . . . . . . 4 5. Counter Measure against Hello Flood Attacks (Bidirectional Verification). . . . . . ................ 5 5.1 Problem of Bidirectional verification... . . . . . . . 6 6. Multi-Path Multi-Base Station Data Fowarding. . ...... 6 7. Conclusion................................ . . . . . . 7 1. Introduction In a large-scale sensor network individual sensors are subject to security compromise. Where the nature of communication is broadcast and, hence, an attacker can overhear messages posted by any sensor node; security is an important issue here. Wireless Sensor Networks (WSNs) are comprised of many small and resource constrained sensor nodes that are deployed in an environment to gather sensed data and forward that data to interested legal users. Advances in micro-electro-mechanical systems (MEMS) technology allow sensors to be reprogrammable, self-localizing, and to support low-energy, wireless, multi-hop networking, while requiring only minimal pre-configuration. To support the reliability of coordinated control, management, and reporting functions, the sensor networks are self-organizing with both decentralized control and autonomous sensor behavior, resulting in a sophisticated processing capability [5]. sinkhole attacks, Sybil attacks, wormholes, HELLO flood attacks, acknowledgement spoofing are well known attacks that try to manipulate sensed data. HELLO flood attack is introduced in [3]. Many protocols require nodes to broadcast HELLO packets to announce themselves to their Hamid, et al. Expires June 8, 2006 [Page 2] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense neighbors, and a node receiving such a packet may assume that it is within (normal) radio range of the sender. This assumption may be false: a laptop-class attacker broadcasting routing or other information with large enough transmission power could convince every node in the network that the adversary is its neighbor. In this paper we consider routing security against HELLO flood attack. 2. Contribution of the Proposal The main contributions of our proposal are as follows: 1. We present probabilistic secret sharing protocol adopted from [1] where, a small increase in the number of secrets maintained by a user substantially reduces the probability of privacy compromise. And it is beneficial for the case where the sensor nodes do not have the capability to hold sufficient secret to ensure privacy. We show how these secrets can be used to route packets in a secured way. 2.Then we propose defense mechanisms against HELLO flood attack using the secrets that nodes share among themselves. 3. Network Assumption and Threat Model We consider a network composed of moderately large number of resource constrained sensor nodes. We further assume that the sensor nodes are deployed in high density, e.g. battlefield deployments. Each sensor node has a communication range such that if the distance between two sensors is more than this range, they can not communicate. We also assume that the communications channels are bidirectional, i.e. if a node y can receive a message from z, then it can also send a message to z. We assume that an adversary can pose the following threat: •An attacker can cause a HELLO flood attack by advertising a very high quality route to the base station. So, every node in the network could cause a large number of nodes to attempt to use this route thereby sending the legitimate packets beyond the actual destination. 4. Key Sharing Protocol In this section, we present the probabilistic protocol, the tree protocol, for assigning the initial secrets. We will describe the single tree protocol and then compute the multiple trees based key assignment. 4.1 Secret instantiation by Tree Protocol We present single tree and then multiple tree protocol. For each of these versions, we first identify the secret distribution protocol that determines the secrets that each user should get. Then, we present the secret selection protocol; when two users need to communicate, they use this protocol to determine a shared secret that they should use. Subsequently, we compute the probability of compromise. Hamid, et al. Expires June 8, 2006 [Page 3] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense K1 / \ / \ K2 K3 / \ / \ K4 K5 K6 K7 / \ / \ / \ / \ S1S2S3 S4 S5 S6S7 S8 Fig. 1. Single tree key assignment We organize the secrets in a tree (Fig. 1). Each non-leaf node is associated with a secret and each leaf is associated with a sensor node. Each sensor node is assigned an ID that identifies its location in the tree. Finally each sensor node is provided the secrets along the path towards the root. Thus, node s1 has the secrets, k1, k2 and k4. When two nodes, say, s1 and s2, want to exchange messages during their effective communication, they first exchange their identities. Then, they identify their least common ancestor and based on the secret distribution mechanism, the common secret associated with this ancestor will be available to both s1 and s2. So, the secret associated with the ancestor will be used for communication between s1 and s2. For example, two nodes s1 and s2 want to communicate then they will use secret key k4 whereas if s1 and s5 want to communicate then they will use secret key k1. 4.2 Computing the vulnerability of security Let x be an intruder that can observe the communication between any two arbitrary nodes y and z. We calculate what is the probability that x knows the shared secret that y and z use. During this analysis, let the degree of the secret-tree be d. Now, we consider different cases based on the shared secret that y and z use during communication. First, we consider the probability that y and z use the secret at the root (level 1). Such a situation arises if z is not a descendant of the level-2-ancestor of y. Thus, the probability of this case is d - 1/d. And, in this case, the probability that x is aware of the secret that y and z use is 1; all users in the secret-tree have the secret associated with the root. Next, we consider the probability that y and z use the secret at level 2 in the tree. Such a situation arises if z is a descendant of the level-2-ancestor of y and z is not a descendant of the level-3-ancestor of y. Thus, the probability of this case is 1/d X (d - 1)/d. Moreover, x is aware of the shared secret between y and z iff x is a descendant of the level-2-ancestor of y. Thus, the probability of this case is 1/d.Continuing thus, the probability of compromise, pc, that x is aware of the shared secret used by y and z is d/(d+1). Multiple Tree Protocol: Secret distribution is the same as single tree protocol with one exception where the position of all sensor nodes is not identical. Because, Clearly, if we use two trees where the position of all users is hamid, et al. Expires June 8, 2006 [Page 4] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense identical and if x knows the secret (used by y and z) in the first tree then, by definition, x will know the secret in the second tree. Hence, when we use multiple trees to reduce the probability of compromise the probability that x knows the secret in one secret-tree should be independent of the probability that l knows the secret in another tree. This can be achieved if there is no correlation between the locations of a sensor node across two trees. Given T secret-trees, each with degree d, the probability that x knows secrets from all the trees is (d/(d + 1))T. 5. Counter Measure against Hello Flood Attacks (Bidirectional Verification) Many protocols require nodes to broadcast HELLO packets to announce themselves to their neighbors, and a node receiving such a packet may assume that it is within (normal) radio range of the sender. This assumption may be false: a laptop-class attacker broadcasting routing or other information with large enough transmission power could convince every node in the network that the adversary is its neighbor. To launch this kind of attack, an adversary’s packet sending range must be bigger than a normal node’s sending range. If each sensor node constructs a set of reachable neighbor nodes, and is only willing to receive REQ messages from this set of neighbor nodes, then REQ messages from an adversary transmitted with larger power will be ignored. Thus, the damage from a HELLO flood attack can be restricted within a small range. To defend against attack, each request (REQ) message forwarded by a node is encrypted with a key. As we have shown from the tree protocol that any two sensor nodes share some common secrets, the new encryption key is generated on-the-fly (i.e. during communication). In this way, any node’s reachable neighbors can decrypt and verify the REQ message while the attacker will not know the key and will be prevented from launching the attack. We show that the new key combined with the echo-back mechanism can well protect this attack. We see that the message exchange won’t be blocked by an adversary when bidirectional verification is applied. Each node locally broadcasts an echo message to its neighbor with format: s1-->: ECHO||Enew-key (IDs1||nonce) Where, ECHO is the message type, ID is the ID of the sensor node s1, nonce is the random number. If a node, say, s2 receives this message, it sends echo reply with format: S2-->s1: ECHOBACK||Enew-key (IDs2||nonce). When node s1 receives this message, it records node s2 as its verified neighbor. If an attacker obtains the shared secrets after a node has received its new encrypted key, it can not know the new pairwise key. Computing the pairwise key is more robust and secure in multiple tree protocol as we have described earlier, where we have shown that the probability of compromise of a secret is very low. However, if an attacker obtains the new key, it can initiate echo-back many times by sending several echo messages. The attacker can generate false identities and can initiate Sybil attack, adding new nodes with false identities. To prevent such attacks, node should destroy its new key from memory after a certain time that is long enough to set up pairwise keys with all its neighbors. Again, during communication, it can calculate new key from the secrets they share. Hamid, et al. Expires June 8, 2006 [Page 5] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense 5.1 Problem of Bidirectional verification As we have stated that this defense against “HELLO flood?attack is to verify the bidirectionality of a link before taking meaningful action based on a message received over that link. But, this defense gets less effectiveness when an attacker has a highly sensitive receiver as well as a powerful transmitter. If an attacker compromises a node before the feedback message, it can block all its downstream nodes by simple dropping feed back messages. And thus, such an attacker can easily create a wormhole to every node within range of its transmitter/receiver. Since the links between these nodes and attacker are bidirectional, the above approach will unlikely be able to locally detect or prevent a “HELLO flood? We propose a different way of reliable exchange of messages among nodes and base stations. We show that when any particular node has different route to send data, this problem is solved. 6. Multi-Path Multi-Base Station Data Fowarding We describe how a sensor node can forward its sensed data to multiple routes i.e. multiple base stations in case where an attacker manages to compromise a sensor node. We assume that, there are a number of base stations in the network who have control over specific number of nodes and also, there are common means of communications among base stations. Each base station has all the secrets those are shared by all the sensor nodes according to the key assignment protocol described earlier.Given the shared secrets and the generated new key between two sensor nodes, the operation of setting up different routing paths is as follows: Step 1: As each sensor node shares some common keys according to the secret distribution protocol (i.e. Multiple Tree Protocol), every node uses the echo-back scheme to identify its neighbor nodes and sets up pairwise new key with its verified neighbor nodes. Then it uses its new key to exchange messages among them. Step 2: Each base station broadcasts its request (REQ) message to its neighbor nodes with the following format: REQ||IDs||Ekey(IDB||HCN) Here, REQ is the message type, IDs is the ID of the sending node s, IDB is the base station ID who generated this request message, Ekey is the key that is common between any node to which base station floods the message and HCN is the base station’s one-way hash chain number. Receiving node verifies that the REQ comes from the base station, then it forwards the REQ to its neighbor node, say, y, with the format: REQ||IDy||Enew-key(IDB||HCN) Step 3: When any ordinary node say, y, receives this REQ message, it checks the sender ID. If s is y’s verified neighbor, y decrypts and authenticates the sender with computed new key Enew-key. If the message sender is valid, it replaces the HCN with the new value and encrypts the hamid, et al. Expires June 8, 2006 [Page 6] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense REQ message with its Enew-key and broadcasts the newly encrypted message. For example, where four base stations with their communication range and sensor nodes with their communication range, if any message comes from a malicious node, the message won’t be forwarded to that node, instead, the sensing node will take a different route to send data. Any base station, when receives the sensed data, it can cooperate with other base stations to interpret the sensed data as base station is powerful enough to communicate among themselves. 7. Conclusion Our work described the defense against HELLO flood attack by introducing bidirectional verification and multi path routing using shared secret between sensor nodes. We have adopted a probabilistic key assignment among sensor nodes and during communication, each node can calculate a pairwise key using these common secrets and hence improving the network resilience against security threats. The key objective of our approach is to tolerate damage caused by an adversary who has captured deployed sensor nodes and is intent on injecting, modifying or blocking packets. REFERENCES [1] S. S. Kulkarni, M. G. Gouda, and A. Arora, Secret instantiation in ad-hoc networks, Special Issue of Elsevier Journal of Computer Communications on Dependable Wireless Sensor Networks, pp. 1-5, May 2005. [2] F. Ye, H. Luo, S. Lu, and L. Zhang, Statistical En-Route Filtering of Injected False Data in Sensor Networks, IEEE Journal on Selected Areas in Communications, vol. 23, no. 4, April 2005. [3] C. Karlof and D.Wagner, Secure routing in wireless sensor networks: Attacks and countermeasures,Elsevier AdHoc Networks Journal, Special Issue on Sensor Network Applications and Protocols, 1(2):293-315, September 2003. [4] R. Di Pietro, L. V. Mancini, and S. Jajodia, Providing secrecy in key management protocols for large wireless sensors networks, Journal of AdHoc Networks, 1(4), pp.455-468, 2003. [5] V. Wen, A. Perrig, and R. Szewczyk, SPINS: Security suite for sensor networks, in Proc. ACM MobiCom, pp. 189?99, 2001. [6] H. Luo, J. Kong, P. Zerfos, S. Lu, and L. Zhang, URSA: Ubiquitous and robust access control for mobile ad hoc networks,?Proc. IEEE/ACM Trans. Netw., vol. 12, no. 6, pp. 1049?063, Oct. 2004. [7] A. Arora, P. Dutta, S. Bapat, V. Kulathumani, H. Zhang, V. Naik, V. Mittal, H. Cao, M. Demirbas, M. Gouda, Y. Choi, and et al., A Line in the Sand: A Wireless Sensor Network for Target Detection, Classification, and Tracking, Computer Networks (Elsevier), Special Issue on Military Communications Systems and Technologies, 46(5):pp.605-634, December 2004. [8] J.R. Douceur, The Sybil attack, in: 1st International Workshop on Peer-to-Peer Systems (IPTPS _02), 2002. [9] Y. Hu, A. Perrig, and D. Johnson, Rushing attacks and defense in wireless ad hoc network routing protocols, Proceedings of the Second ACM Workshop on Wireless Security (WiSe03), San Diego, CA, USA, September 2003. [10] H. Chan, A. Perrig, D. Song, Random key predistribution schemes for sensor networks, IEEE Symposium on Security and Privacy, 2003. hamid, et al. Expires June 8, 2006 [Page 7] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense [11] W. Du, J. Deng, Y. Han, P. Varshney, pairwise key pre-distribution scheme for wireless sensor networks, ACM Conference on Computer and Communications Security (CCS), pp. 42-51, 2003. [12] Y. Zhang, W. Lee, Intrusion detection in wireless ad hoc networks, ?in: Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking, pp. 275-283, 2000. [13] S. Yi, P. Naldurg, R. Kravets, Security-aware ad hocrouting for wireless networks, Proceedings of the 2001 ACM International Symposium on Mobile Ad Hoc Networking and Computing, ACM Press, New York, [14] D. Braginsky, D. Estrin, Rumour routing algorithm for sensor networks, Proceedings of First ACM International Workshop on Wireless Sensor Networks and Applications, 2002. [15] A. Manjeshwar, D. Agrawal, TEEN: a routing protocol for enhanced efficiency in wireless sensor networks, Proceedings of 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, 2001. AUTHOR'S ADDRESS Questions about this document can also be directed to the author: Suho Park Next Generation Internet Division Future Technology Research Department KT Advanced Technology Laboratory 1 woomyun, secho, Seoul, Korea Tel : +82 526-5479 suhopark@kt.co.kr Md. Abdul Hamid Networking Lab Department of Computer Engineering Kyung Hee University 1 Seocheon, Giheung, Yongin, Gyeongi-Do, 449-701, Korea Email: hamid@networking.khu.ac.kr Choong Seon Hong Department of Computer Engineering Kyung Hee University 1 Seocheon, Giheung, Yongin, Gyeongi-Do, 449-701, Korea E-mail : cshong@khu.ac.kr Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. hamid, et al. Expires June 8, 2006 [Page 8] Internet-Draft Routing Security in Sensor Network: December 2005 HELLO Flood Attack and Defense The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Hamid, et al. Expires June 8, 2006 [Page 9]