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
<draft-suhopark-hello-wsn-00>
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
adversarys packet sending range must be bigger than a normal nodes 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 nodes 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 wont 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 stations 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 ys 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 wont 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]