24-12-2009, 03:03 PM
[attachment=714]
A
Seminar Report
On
Secure Positioning of Wireless Devices
in partial fulfillment for the degree of
Bachelor of Engineering
In
Electronics & Communication
of
University of Rajasthan
Submitted to: Submitted by:
Mr. Hiren joshi Deepak Shankhla
Head ECE dept. Final year
M.L.V.T.E.C, Bhilwara Electronics & Comm. Engg.
Under the guidance of:
Mr.Shaym Sunder Verma
(Lect.Information tech.Dept.)
M.L.V.Textile & Engineering College, Bhilwara
Preface
Seminar is an exposure of students for their personality development. This is the best time for the
students to improve their skills. It is possible when one has curiosity in his heart to know about
upcoming technologies. It trained us to be aware,co-operative and creative, which will surely help us
in future. It has also enhanced our reasoning power and sense of expressing our thoughts in better
and effective way as well as it has sharpened our minds. Without it the course would not have any
true sense.
This report contains complete introduction to secure positioning of wireless, which help those who
are primer in this field and want to know about the basics of distance detected. It delivers the
information about what the are procedure of detection of wireless devices , architecture of sensor
network.
Acknowledgement
This technical seminar gives exposure and increases knowledge about new technology. Knowledge
is incomplete without discussions or guidance.
I acknowledge here out debt to those who contributed significantly to one or more steps. We take
full responsibility for any remaining sins of commission.
I wish to spell the feeling of our great attitude and sincere thanks to Mr. Hiren Joshi, Head
of ECE and S.S. Verma, Head of IT. Department, M.L.V.T.& Engg.College, Bhilwara under their
supervision and proper guidance the present work is submitted. Their untiring assistance and contributions,
to our academic persuasions and to bring this elaborated work in the present comprehensive
form, exceeds the limits of ordinary editorial work.
It is my pleasant duty to present my deep sense of gratitude and sincere thanks to my family,
friends, and classmates for their moral support and good wishes that have always helped me in
avoiding hurdles.
Abstract
So far, the problem of positioning in wireless networks has been mainly studied in a non-adversarial
setting. In this work, we analyze the resistance of positioning techniques to position and distance
spoofing attacks. We propose a mechanism for secure positioning of wireless devices, that we call
Verifiable Multilateration. We then show how this mechanism can be used to secure positioning in
sensor networks.
Being able to securely determine a position of a node enables:
Location-based access control
Location-based charging
Detection of displacement of valuables
Monitoring and enforcement of policies (e.g., traffic monitoring)
Secure location-based and encounter-based routing (ad hoc networks)
Secure data harvesting (sensor networks)
Contents
1 Introduction 7
1.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Attacks Against position and Distance Estimation Techniques 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Global Positioning System(GPS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Ultrasound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Radio(RF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Verifiable Multilateration 11
3.0.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.0.2 properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 (SPINE) Secure positioning in Sensor Networks 14
4.1 Threat analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.1 Node physical dispacement and removal . . . . . . . . . . . . . . . . . . . . . 14
4.2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Security analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5 Application 18
5.1 Wireless Sensor Networks and Applications: . . . . . . . . . . . . . . 18
6 Conclusion & Future Scope 19
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5
List of Figures
3.1 Example of Verifiable Multilateration . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1 Attacks on sensor network positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 An Example of a distance attack by extenal nodes . . . . . . . . . . . . . . . . . . . . 17
4.3 Example of a distance enlargement attack by a compromised node . . . . . . . . . . . 17
6
Chapter 1
Introduction
Sensor networks are a promising approach for a variety of applications, such as monitoring safety
and security of buildings and spaces, measuring traffic flows, and tracking environmental pollutants.
Sensor networks will play an essential role in the upcoming age of pervasive computing, as our
personal mobile devices will interact with sensor networks in our environment.Many sensor networks
have mission-critical tasks, so it is clear that security needs to be taken into account at design time.
Security will be important for most applications for the following reasons. Most sensor networks
actively monitor their surroundings, and it is often easy to deduce information other than the data
monitored.
Such unwanted information leakage often results in privacy breaches of the people in the environment.
Moreover, the wireless communication employed by sensor networks facilitates eavesdropping
and packet injection by an adversary. The combination of these factors demands security for sensor
networks to ensure operation safety, secrecy of sensitive data, and privacy for people in sensor environments.
Security in sensor networks is complicated by the constrained capabilities of sensor node hardware
and the properties of the deployment: Since sensor nodes usually have severely constrained
computation, memory, and energy resources, asymmetric cryptography is often too expensive for
many applications. Thus, a promising approach is to use more efficient symmetric cryptographic
alternatives. In contrast to asymmetric cryptography (e.g., the RSA signature algorithm or the
Diffie-Hellman key agreement protocol), symmetric cryptography (e.g., the AES block cipher or the
HMAC-SHA-1 message authentication code) is three to four orders of symmetric cryptography is not
as versatile as public key cryptographic techniques, which complicates the design of secure applications.
Sensor nodes are susceptible to physical capture, but because of their targeted low cost, tamperresistant
hardware is unlikely to prevail. Therefore, when designing a secure sensor network we must
assume that nodes may be compromised by an attacker. Compromised nodes may exhibit arbitrary
behavior and may collude with other compromised nodes.
Sensor nodes use wireless communication, which is particularly easy to eavesdrop on. Similarly,
an attacker can easily inject malicious messages into the wireless network. Security also needs to
scale to large-scale deployments. Most current standard security protocols were designed for twoparty
settings and do not scale to a large number of participants. We expect future sensor networks
7
with thousands of sensor nodes, so it is clear that scalability is a prerequisite for any viable approach.
In this article we discuss security from a networking perspective and consider mechanisms to achieve
secure communication. We will first discuss the threat and trust model for sensor networks. We will
then discuss security requirements and propose specific countermeasures against attacks. Finally, we
describe
1.1 Problem statement
We address thwe problem of rubust computation ofthe location of sensors in WSN ,in the presence
of malicious adversaries .we will refer to this problem as Secore Localzation .
The problem of verifying the location claim of a sensor reports its ranges ,in our location verification
we only verify that an out ofrange sensor apear to bein range is of no use to the attacker and hence
,it is not addressed
Chapter 2
Attacks Against position and Distance
Estimation Techniques
2.1 Introduction
We now review positioning and distance estimation techniques and analyze their vulnerabilities.
We first shortly present our attacker model. We call an attacker external if the attacker cannot
authenticate itself as an honest network node to other network nodes or to a central authority.
We call a node compromised if it is controlled by an attacker and it can authenticate itself to the
authority and to other network nodes [11]. We assume that when a node is compromised, its secret
keys and other secrets that it shares with other nodes are known to the attacker.
2.2 Global Positioning System(GPS)
The Global Positioning System is today the most widespread outdoor positioning system for mobile
devices. The system is based on a set of satellites that provide a three dimensional positioning
with accuracy of around 3 m. GPS also provides devices with an accurate time reference. GPS,
however, has several limitations: it cannot be used for indoor positioning nor for positioning in dense
urban regions: in those cases, because of the interferences and obstacles, satellite signals cannot
reach the GPS devices. Furthermore, the civilian GPS was never designed for secure positioning.
Civilian GPS devices can be spoofed by GPS satellite simulators, which produce fake satellite radio
signals that are stronger than the real signals coming from satellites. Most current GPS receivers
are totally fooled, accepting these stronger signals while ignoring the weaker, authentic signals.
GPS satellite simulators are legitimately used to test new GPS products and Some simple software
changes to most GPS receivers would permit them to detect relatively unsophisticated spoofing
attacks . Nevertheless, more sophisticated spoofing attacks would still be hard to detect. Military
GPS are protected from position spoofing by codes which cannot be reproduced by the attackers.
An asymmetric security mechanism for navigation signals that can be used to secure civilian GPS.
This mechanism is, however, vulnerable to some sophisticated attacks involving jamming and fast
wormholes. Even if a mobile node is able to obtain its correct position from the GPS satellites, the
authority or another mobile node have no way to verify the correctness of nodes position, unless the
mobile node is equipped with a trusted software or hardware module.
9
2.3 Ultrasound
Ultrasound-based systems operate by measuring ToF of the sound signal measured between two
nodes. An interesting feature of these systems is that, if used with RF signals, they do not require
any time synchronization between the sender and the receiver. The limitations of the US-based systems
are that, due to outdoor interferences, US systems can be mainly used indoors, and that the US
signals can be animal-unfriendly.US-based systems are vulnerable to distance reduction and distance
enlargement attacks by external attackers and compromised nodes. To reduce the measured distance
between two honest nodes, two external nodes can use a fast radio link to transmit the signals faster
between the honest nodes.
Furthermore, by jamming and replaying the signals at a later time, external attacker can enlarge the
measured distances between honest nodes. If conventional US ToF technique is used, a compromised
node can also reduce or enlarge themeasured distance by laying about the signal sending/reception
times or by simply delaying its response to honest nodes.
Recently, Sastry, Shankar and Wagner [8] have proposed a US-based distance bounding technique
which resists to distance reduction attacks from compromised nodes; it does not, however, resist to
attacks from external attackers. This does not mean that this technique is useless for secure applications;
it can still be used for verifying location claims in systems in which attackers have no physical
access to the localization region. In [14] Waters and Felten presented a similar technique.
2.4 Radio(RF)
In techniques based on the Received Signal Strength (RSS), the distance is computed based on the
transmitted and received signal strengths. To cheat on the measured distance, a compromised node
therefore only needs to report a false power level to an honest node. External attackers can also
modify the measured distance between two honest nodes by jamming the nodes mutual communication
and by replaying the messages with higher or lower power strengths.
RF time-of-flight-based systems exhibit the best security properties. In these systems, nodes measure
their mutual distance based on the time of propagation of the signal between them. Because RF
signals travel at the speed of light, an external attackers can, by jamming and replaying the signals,
only increase, but not decrease the measured time-of-flight between the nodes. A compromised node
can further cheat on the distance by laying about the signal transmission and reception times.
An RF distance bounding technique exhibits better security properties than conventional RF ToF
distance estimation; it allows the nodes to upper bound their distances to other nodes, meaning that
it prevents a compromised node from reducing the measured distance. with RF ToF distancebounding
protocols, external attackers and compromised nodes can only increase, but not decrease the
measured distances to honest nodes.
Chapter 3
Verifiable Multilateration
we described security problems related to various positioning and distance estimation techniques and
in e showed how the devices can upper-bound their mutual distances. We now propose a technique
for position verification that we call Verifiable Multilateration (VM). This technique enables a secure
computation and verification of the positions of mobile devices in the presence of attackers. By
secure position computation we mean that base stations compute a correct position of a node in the
presence of attacker; by secure position verification we mean that the base stations verify a position
reported by the node.
Multilateration is a technique for determining the position of a (mobile) device from a set of reference
points whose positions are known, based on the distances measured between the reference points
and the device. The position of the device in two (three) dimensions can be computed if the device
measured its distance to three (four) reference points. Distance estimation techniques are vulnerable
to attacks from external attackers and from compromised nodes, which can maliciously modify the
measured distances. Multilateration is equally vulnerable to the same set of attacks because it relies
on distance estimations.
3.0.1 Algorithm
Verifiable Multilateration relies on distance bounding. It consists of distance bound measurements
from at least three reference points (verifiers) to the considered device (the claimant) and of subsequent
computations performed by an authority. For simplicity, we show the algorithm for two
dimensional positioning; at the end of this subsection, we briefly explain how a similar algorithm can
be applied to the three dimensional case.
The intuition behind verifiable multilateration algorithm is the following. Because of the distance
bounding property, the claimant can only pretend that it is more distant from the verifier than it
really is. If it increases the measured distance to one of the verifiers, to keep the position consistent,
the claimant needs to prove that at least one of the measured distances to other verifiers is shorter
than it actually is, which it cannot because of the distance bounding. This property holds only if
the position of the claimant is determined within the triangle formed by the verifiers. This can be
explained with a simple example: if an object is located within the triangle, and it moves to a different
position within the triangle, it will certainly reduce its distance to at least one of the triangle
vertices. The same properties hold if an external attacker enlarges distances between verifiers and
11
an honest claimant. This basic intuition behind verifiable multilateration is illustrated in Figure 2a.
The verifiable multilateration algorithm is executed by the verifiers and by the authority as follows.
Verifiable multilateration
T = ;; set of verification triangles around u
V = v1, ..., vn; set of verifiers in the power range of u
1 For all vi 2 V, perform distance bounding from vi to u and obtain dbi
2 With all vi 2 V, compute the estimate (x0u, y0u) of the position by MMSE
3 I f for all vi 2 V, |dbip(xix0u)2 + (yiy0u )2| then
f or all (vi, vj , vk) 2 V3, if (x0u, y0u) 2 (vi, vj , vk)
then T = T [ (vi, vj , vk)
i f |T| > 0 then position is accepted and xu = x0u, yu = y0u
else the position is rejected
else the position is rejected
In step 1 of the algorithm, the verifiers v1, ..., vn which are in the power range of the claimant u
perform distance bounding to the claimant u and obtain distance bounds db1, ..., dbn. These distance
bounds as well as the positions of the verifiers (which are precisely known) are then reported to the
authority.
Figure 3.1: Example of Verifiable Multilateration
In step 2, the authority computes an estimate (xâ„¢, yâ„¢) of the claimants position; this position is
computed by using distance bounds from all verifiers in us neighborhood, typically by the MMSE of
the following system of equations:
Let fi(x0u, y0u ) = dbi -p(xix0u)2 + (yiy0u)2
The position of u is obtained by minimizing
F(x0u, y0u) = Pvi2T fi
2(x0u, y0u)
over all estimates of u
In step 3 of the algorithm, the authority runs the following two tests: (i) - test: for all vi, does
the distance between (x0u, y0u) and vi differ from the measured distance bound dbi by less than the
expected distance measurement error and (ii) point in the triangle test: does (x0u, y0u) fall within at
least one physical triangle formed by a triplet of verifiers. Note also that we call the triangle formed
by the verifiers the verification triangle. If both the and the point in the triangle tests are positive,
the authority accepts the estimated position (x0u, y0u ) of the claimant as correct; else, the position is
rejected.
The expected error is a system parameter and depends on the number of verifiers and on the distance
estimation techniques used. This error becomes smaller as more verifiers are used to compute
(x0u, y0u). In most cases, can be approximated as 3, where is the expected standard deviation
of the computed position. The following well known test is run to detect if the claimants estimated
position (x0u, y0u ) falls within the verification triangle (vi, vj , vk)
Point in the triangle test
fij(u) = (y0u - yi)(xj - xi)(x0u - xi)(yjyi)
fki(u) = (y0u yk)(xixk)(x0uxk)(yiyk)
fjk(u) = (y0u yj)(xkxj)(x0uxj)(ykyj)
if fij(u) fjk(u) > 0andfjk(u) fki(u) > 0
then u is in (vi, vj , vk)
The logic behind this test is the following. Three functions fij(u), fik(u), fjk(u) are defined, one for
each edge of the triangle. fij(u) is zero for all points u on the line vi, vj , and non-zero for all other
points. In fact, looking from vj at vi, fij(u) is negative for all points (x, y) on the left side of the
edge vi, vj , and positive for all points (x,y) on the right side of the edge. The same applies for the
other two edges and functions. By combining the output from the three functions we can compute
if a point falls in or out of the triangle (vi, vj , vk).
3.0.2 properties
In this subsection, we summarize the most important properties of the Verifiable Multilateration
mechanism. These are the following: 1) A node located at position p within the triangle/pyramid
formed by the verifiers cannot prove to be at another position p0 6= p within the same triangle/
pyramid. 2) A node located outside the triangle/pyramid formed by the verifiers cannot prove
to be at any position p within the triangle/pyramid. 3) An external attacker performing a distance
enlargement attack cannot trick the verifiers into believing that a claimant located at a location p
in the triangle/pyramid is located at some other position p0 6= p in the triangle/ pyramid.
Chapter 4
(SPINE) Secure positioning in Sensor
Networks
One of the main challenges in sensor networks [18], [19], [20], [21] is sensor positioning. Knowing
the positions of sensors is important for relating the measured data with the physical location. Researchers
have recently proposed a number of positioning algorithms for sensor and ad hoc networks
(see Section VI). The majority of the proposed algorithms rely on insecure local distance measurements
and on cooperation between the nodes that are not necessarily trustworthy. In this section,
we present SPINE, a system for secure positioning of a network of sensors, that is based on Verifiable
Multilateration. We first shortly describe attacks on sensor network positioning systems.
4.1 Threat analysis
We characterize attackers according to the number of external and compromised nodes that they
control. By Attacker-x-y we denote attacker that controls x compromised and y external nodes.
4.1.1 Node physical dispacement and removal
most obvious threats to sensor networks is the physical displacement of nodes. An attacker can
physically displace nodes from their original positions to other positions in the network, or can
temporarily or permanently remove the nodes from the network while this remains undetected to
the nodes or to the network authority. These attacks are especially harmful in sensor networks, in
which the nodes are, given their size and purpose, in most cases easily accessible to the attacker. It
would be naive to believe that this problem can be solved only by a simple exchange of authenticated
beacons between the nodes, or by conventional positioning techniques. If the network is not properly
protected, an external attacker can create the impression to the displaced node and to its neighbors
that the node did not move. A simple approach for the attacker is to replace the network node with a
fake one, and to create a communication link to the new position of the honest node. Typically, this
attack can be performed by Attacker-0-2. By enabling communication between two honest nodes,
the attacker easily creates the impression to the nodes that their positions remained unchanged. This
attack, that we call the node displacement attack .
14
4.2 System model
Figure 4.1: Attacks on sensor network positioning
Our system consists of a set of sensor nodes and a set of reference nodes (landmarks) with known
locations. Nodes and verifiers communicate using radio transmissions. If two nodes reside within the
power range of each other, they are considered neighbors. We assume that the radio link between
neighbors is bidirectional. Nodes measure local information, which is then collected by the central
authority. Communication between nodes may involve multiple wireless hops; we do not make any
specific assumptions about the routing protocol used to transfer packets from their source to their
destination. We assume that the sensor nodes have distance-measuring capabilities, but are not
equipped with GPS receivers. We assume, notably, that the nodes are able to measure the distances
to their neighbors or to the landmarks by using ime-of-arrival or round-trip time measurements with
radio signals. We also assume that the nodes are able to bound their processing delays to a few
nanoseconds.
We assume that the network is operated by an authority. This authority can be on-line, meaning
that the authority operates on-line servers (by single hop or multi-hop communication), or off-line,
meaning that the services of the authority cannot be reached via the network. In any case, the
authority controls the network membership and assigns a unique identity to each node. We further
assume that each node is able generally to accomplish any task required to secure its communications.
We do not assume, however, that the nodes are able to generate or verify public-key signatures. We
assume that all network nodes can establish pairwise secret keys. This can be achieved by manually
pre-loading all keys into the nodes in a network setup phase, by probabilistic key pre-distribution
schemes or through an on-line key distribution center .
4.3 Security analysis
The resistance of SPINE relies on the resistance of BDV to attacks; it depends on the ability of
the attacker to modify the verified distances, but also depends on the positioning algorithm used to
compute node positions with verified distances. Here, we primarily analyze the resistance of BDV to
attacks. We then discuss security implications of using BDV with several positioning algorithms.
The resistance of BDV to attacks depends on the number and on the mutual dependance of triangles
that are formed around the distance. To spoof a distance verified by a single triangle, it
is sufficient that an external attacker enlarges two distances (the distance duv, and one additional
distance between the nodes forming a triangle). This is illustrated on Figure 8, where distances duv
and d1 are enlarged. By enlarging these two distances, all the distances in the verifi- cation triangle
remain mutually consistent. This attack can be performed by an external attacker.
If only a single node in a triangle is compromised, this node can enlarge distances to the claimant
and to other nodes forming the verification triangle. Node v is compromised, and enlarges distances
to u, v2 and to v3 such that all the distances in the verification triangle remain mutually consistent.
Similarly to the attack on Figure 8, if an attacker controls one compromised and one external node,
it can enlarge the measured distance even if the compromised node is not adjacent to the distance.
This essentially means that a single-triangle BDV resists only to attacks that enlarge only a single
distance. If k verification triangles can be formed around a distance, the resistance of BDV to attacks
can be expressed in terms of k. If the triangles are node-disjoint, then BDV resists to up to
2k distance enlargements. This is intuitive, as the distance is verified by k disjoint triangles, and
an attacker needs to spoof the verification process in each of the triangles to successful cheat on the
measured distance.
If the triangles are node-joint and edge-disjoint, then BDV also resists to up to 2k distance enlargements
by external attackers, but it does not resist attacks by a single compromised node adjacent to
the spoofed distance. Essentially, if all triangles have a common (compromised) node, the distance
adjacent to that node can be successfully spoofed. We note here, however, that the triangles formed
around a distance are almost never node-joint, given that some are formed with u and its neighbors
around v, others are formed with v and its neighbors around u, whereas the third set of triangles
is formed by the neighbors of u and v around the two nodes. If the triangles are edge-joint, then
BDV resists to up to k+1 distance enlargements by external attackers. If the nodes are positioned
favorably for the attacker, the attacker can enlarge the joint edge and enlarge one additional edge
from every triangle. We note here that this attack will not always be possible.
Figure 4.2: An Example of a distance attack by extenal nodes
Figure 4.3: Example of a distance enlargement attack by a compromised node
Chapter 5
Application
Our proposal is to see wireless sensor networks rather as a tool than a solution to a specfic problem.
Looking at the history of science and at scientfic discoveries tools have always played the key role.
5.1 Wireless Sensor Networks and Applications:
With the invention of the microscope new scientific discoveries have been enabled. Similarly wireless
sensor networks may enable new observations that were not possible before. However for this to
happen, cooperation with other disciplines is inevitable. In the domain of tangible and physical user
interfaces wireless sensor networks are an enabling technology. In this area the use of sensors in
devices, clothing, and everyday objects provides new ways for creating interactive systems. The user
experience created by such novel interfaces is hardly predictable and therefore trying them out is
essential. In both areas it is important to have a quick and easy way of building prototypes that
allow doing experiments to acquire real data. This was one main motivation to develop the DIY
SmartIts platform. It is designed to allow easy extensibility and tailoring for a specific application
domain.
18
Chapter 6
Conclusion & Future Scope
6.1 Conclusion
In this work, we have analyzed positioning and distance estimation techniques in adversarial settings.
We have shown that most proposed positioning techniques are vulnerable to position spoofing
attacks from external attackers and compromised nodes. We have further shown that positioning
and distance estimation techniques based on radio signal propagation exhibit the best properties for
position verification. We have proposed a novel mechanism for position verification, called Verifiable
Multilateration (VM). Verifiable Multilateration enables secure computation and verification of node
positions in the presence of attackers. We have further proposed SPINE, a system for secure positioning
in a network of sensors, based on Verifiable Multilateration. We have shown that this system
resists against distance modification attacks from a large number of attacker nodes. Our future
work includes a detailed analysis and possible implementation of distance bounding and position
verification techniques. Furthermore, we intend to investigate the applicability of our basic distance
verification scheme to a number of existing positioning algorithms.
19
A
Seminar Report
On
Secure Positioning of Wireless Devices
in partial fulfillment for the degree of
Bachelor of Engineering
In
Electronics & Communication
of
University of Rajasthan
Submitted to: Submitted by:
Mr. Hiren joshi Deepak Shankhla
Head ECE dept. Final year
M.L.V.T.E.C, Bhilwara Electronics & Comm. Engg.
Under the guidance of:
Mr.Shaym Sunder Verma
(Lect.Information tech.Dept.)
M.L.V.Textile & Engineering College, Bhilwara
Preface
Seminar is an exposure of students for their personality development. This is the best time for the
students to improve their skills. It is possible when one has curiosity in his heart to know about
upcoming technologies. It trained us to be aware,co-operative and creative, which will surely help us
in future. It has also enhanced our reasoning power and sense of expressing our thoughts in better
and effective way as well as it has sharpened our minds. Without it the course would not have any
true sense.
This report contains complete introduction to secure positioning of wireless, which help those who
are primer in this field and want to know about the basics of distance detected. It delivers the
information about what the are procedure of detection of wireless devices , architecture of sensor
network.
Acknowledgement
This technical seminar gives exposure and increases knowledge about new technology. Knowledge
is incomplete without discussions or guidance.
I acknowledge here out debt to those who contributed significantly to one or more steps. We take
full responsibility for any remaining sins of commission.
I wish to spell the feeling of our great attitude and sincere thanks to Mr. Hiren Joshi, Head
of ECE and S.S. Verma, Head of IT. Department, M.L.V.T.& Engg.College, Bhilwara under their
supervision and proper guidance the present work is submitted. Their untiring assistance and contributions,
to our academic persuasions and to bring this elaborated work in the present comprehensive
form, exceeds the limits of ordinary editorial work.
It is my pleasant duty to present my deep sense of gratitude and sincere thanks to my family,
friends, and classmates for their moral support and good wishes that have always helped me in
avoiding hurdles.
Abstract
So far, the problem of positioning in wireless networks has been mainly studied in a non-adversarial
setting. In this work, we analyze the resistance of positioning techniques to position and distance
spoofing attacks. We propose a mechanism for secure positioning of wireless devices, that we call
Verifiable Multilateration. We then show how this mechanism can be used to secure positioning in
sensor networks.
Being able to securely determine a position of a node enables:
Location-based access control
Location-based charging
Detection of displacement of valuables
Monitoring and enforcement of policies (e.g., traffic monitoring)
Secure location-based and encounter-based routing (ad hoc networks)
Secure data harvesting (sensor networks)
Contents
1 Introduction 7
1.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Attacks Against position and Distance Estimation Techniques 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Global Positioning System(GPS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Ultrasound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Radio(RF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Verifiable Multilateration 11
3.0.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.0.2 properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 (SPINE) Secure positioning in Sensor Networks 14
4.1 Threat analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.1 Node physical dispacement and removal . . . . . . . . . . . . . . . . . . . . . 14
4.2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Security analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5 Application 18
5.1 Wireless Sensor Networks and Applications: . . . . . . . . . . . . . . 18
6 Conclusion & Future Scope 19
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5
List of Figures
3.1 Example of Verifiable Multilateration . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1 Attacks on sensor network positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 An Example of a distance attack by extenal nodes . . . . . . . . . . . . . . . . . . . . 17
4.3 Example of a distance enlargement attack by a compromised node . . . . . . . . . . . 17
6
Chapter 1
Introduction
Sensor networks are a promising approach for a variety of applications, such as monitoring safety
and security of buildings and spaces, measuring traffic flows, and tracking environmental pollutants.
Sensor networks will play an essential role in the upcoming age of pervasive computing, as our
personal mobile devices will interact with sensor networks in our environment.Many sensor networks
have mission-critical tasks, so it is clear that security needs to be taken into account at design time.
Security will be important for most applications for the following reasons. Most sensor networks
actively monitor their surroundings, and it is often easy to deduce information other than the data
monitored.
Such unwanted information leakage often results in privacy breaches of the people in the environment.
Moreover, the wireless communication employed by sensor networks facilitates eavesdropping
and packet injection by an adversary. The combination of these factors demands security for sensor
networks to ensure operation safety, secrecy of sensitive data, and privacy for people in sensor environments.
Security in sensor networks is complicated by the constrained capabilities of sensor node hardware
and the properties of the deployment: Since sensor nodes usually have severely constrained
computation, memory, and energy resources, asymmetric cryptography is often too expensive for
many applications. Thus, a promising approach is to use more efficient symmetric cryptographic
alternatives. In contrast to asymmetric cryptography (e.g., the RSA signature algorithm or the
Diffie-Hellman key agreement protocol), symmetric cryptography (e.g., the AES block cipher or the
HMAC-SHA-1 message authentication code) is three to four orders of symmetric cryptography is not
as versatile as public key cryptographic techniques, which complicates the design of secure applications.
Sensor nodes are susceptible to physical capture, but because of their targeted low cost, tamperresistant
hardware is unlikely to prevail. Therefore, when designing a secure sensor network we must
assume that nodes may be compromised by an attacker. Compromised nodes may exhibit arbitrary
behavior and may collude with other compromised nodes.
Sensor nodes use wireless communication, which is particularly easy to eavesdrop on. Similarly,
an attacker can easily inject malicious messages into the wireless network. Security also needs to
scale to large-scale deployments. Most current standard security protocols were designed for twoparty
settings and do not scale to a large number of participants. We expect future sensor networks
7
with thousands of sensor nodes, so it is clear that scalability is a prerequisite for any viable approach.
In this article we discuss security from a networking perspective and consider mechanisms to achieve
secure communication. We will first discuss the threat and trust model for sensor networks. We will
then discuss security requirements and propose specific countermeasures against attacks. Finally, we
describe
1.1 Problem statement
We address thwe problem of rubust computation ofthe location of sensors in WSN ,in the presence
of malicious adversaries .we will refer to this problem as Secore Localzation .
The problem of verifying the location claim of a sensor reports its ranges ,in our location verification
we only verify that an out ofrange sensor apear to bein range is of no use to the attacker and hence
,it is not addressed
Chapter 2
Attacks Against position and Distance
Estimation Techniques
2.1 Introduction
We now review positioning and distance estimation techniques and analyze their vulnerabilities.
We first shortly present our attacker model. We call an attacker external if the attacker cannot
authenticate itself as an honest network node to other network nodes or to a central authority.
We call a node compromised if it is controlled by an attacker and it can authenticate itself to the
authority and to other network nodes [11]. We assume that when a node is compromised, its secret
keys and other secrets that it shares with other nodes are known to the attacker.
2.2 Global Positioning System(GPS)
The Global Positioning System is today the most widespread outdoor positioning system for mobile
devices. The system is based on a set of satellites that provide a three dimensional positioning
with accuracy of around 3 m. GPS also provides devices with an accurate time reference. GPS,
however, has several limitations: it cannot be used for indoor positioning nor for positioning in dense
urban regions: in those cases, because of the interferences and obstacles, satellite signals cannot
reach the GPS devices. Furthermore, the civilian GPS was never designed for secure positioning.
Civilian GPS devices can be spoofed by GPS satellite simulators, which produce fake satellite radio
signals that are stronger than the real signals coming from satellites. Most current GPS receivers
are totally fooled, accepting these stronger signals while ignoring the weaker, authentic signals.
GPS satellite simulators are legitimately used to test new GPS products and Some simple software
changes to most GPS receivers would permit them to detect relatively unsophisticated spoofing
attacks . Nevertheless, more sophisticated spoofing attacks would still be hard to detect. Military
GPS are protected from position spoofing by codes which cannot be reproduced by the attackers.
An asymmetric security mechanism for navigation signals that can be used to secure civilian GPS.
This mechanism is, however, vulnerable to some sophisticated attacks involving jamming and fast
wormholes. Even if a mobile node is able to obtain its correct position from the GPS satellites, the
authority or another mobile node have no way to verify the correctness of nodes position, unless the
mobile node is equipped with a trusted software or hardware module.
9
2.3 Ultrasound
Ultrasound-based systems operate by measuring ToF of the sound signal measured between two
nodes. An interesting feature of these systems is that, if used with RF signals, they do not require
any time synchronization between the sender and the receiver. The limitations of the US-based systems
are that, due to outdoor interferences, US systems can be mainly used indoors, and that the US
signals can be animal-unfriendly.US-based systems are vulnerable to distance reduction and distance
enlargement attacks by external attackers and compromised nodes. To reduce the measured distance
between two honest nodes, two external nodes can use a fast radio link to transmit the signals faster
between the honest nodes.
Furthermore, by jamming and replaying the signals at a later time, external attacker can enlarge the
measured distances between honest nodes. If conventional US ToF technique is used, a compromised
node can also reduce or enlarge themeasured distance by laying about the signal sending/reception
times or by simply delaying its response to honest nodes.
Recently, Sastry, Shankar and Wagner [8] have proposed a US-based distance bounding technique
which resists to distance reduction attacks from compromised nodes; it does not, however, resist to
attacks from external attackers. This does not mean that this technique is useless for secure applications;
it can still be used for verifying location claims in systems in which attackers have no physical
access to the localization region. In [14] Waters and Felten presented a similar technique.
2.4 Radio(RF)
In techniques based on the Received Signal Strength (RSS), the distance is computed based on the
transmitted and received signal strengths. To cheat on the measured distance, a compromised node
therefore only needs to report a false power level to an honest node. External attackers can also
modify the measured distance between two honest nodes by jamming the nodes mutual communication
and by replaying the messages with higher or lower power strengths.
RF time-of-flight-based systems exhibit the best security properties. In these systems, nodes measure
their mutual distance based on the time of propagation of the signal between them. Because RF
signals travel at the speed of light, an external attackers can, by jamming and replaying the signals,
only increase, but not decrease the measured time-of-flight between the nodes. A compromised node
can further cheat on the distance by laying about the signal transmission and reception times.
An RF distance bounding technique exhibits better security properties than conventional RF ToF
distance estimation; it allows the nodes to upper bound their distances to other nodes, meaning that
it prevents a compromised node from reducing the measured distance. with RF ToF distancebounding
protocols, external attackers and compromised nodes can only increase, but not decrease the
measured distances to honest nodes.
Chapter 3
Verifiable Multilateration
we described security problems related to various positioning and distance estimation techniques and
in e showed how the devices can upper-bound their mutual distances. We now propose a technique
for position verification that we call Verifiable Multilateration (VM). This technique enables a secure
computation and verification of the positions of mobile devices in the presence of attackers. By
secure position computation we mean that base stations compute a correct position of a node in the
presence of attacker; by secure position verification we mean that the base stations verify a position
reported by the node.
Multilateration is a technique for determining the position of a (mobile) device from a set of reference
points whose positions are known, based on the distances measured between the reference points
and the device. The position of the device in two (three) dimensions can be computed if the device
measured its distance to three (four) reference points. Distance estimation techniques are vulnerable
to attacks from external attackers and from compromised nodes, which can maliciously modify the
measured distances. Multilateration is equally vulnerable to the same set of attacks because it relies
on distance estimations.
3.0.1 Algorithm
Verifiable Multilateration relies on distance bounding. It consists of distance bound measurements
from at least three reference points (verifiers) to the considered device (the claimant) and of subsequent
computations performed by an authority. For simplicity, we show the algorithm for two
dimensional positioning; at the end of this subsection, we briefly explain how a similar algorithm can
be applied to the three dimensional case.
The intuition behind verifiable multilateration algorithm is the following. Because of the distance
bounding property, the claimant can only pretend that it is more distant from the verifier than it
really is. If it increases the measured distance to one of the verifiers, to keep the position consistent,
the claimant needs to prove that at least one of the measured distances to other verifiers is shorter
than it actually is, which it cannot because of the distance bounding. This property holds only if
the position of the claimant is determined within the triangle formed by the verifiers. This can be
explained with a simple example: if an object is located within the triangle, and it moves to a different
position within the triangle, it will certainly reduce its distance to at least one of the triangle
vertices. The same properties hold if an external attacker enlarges distances between verifiers and
11
an honest claimant. This basic intuition behind verifiable multilateration is illustrated in Figure 2a.
The verifiable multilateration algorithm is executed by the verifiers and by the authority as follows.
Verifiable multilateration
T = ;; set of verification triangles around u
V = v1, ..., vn; set of verifiers in the power range of u
1 For all vi 2 V, perform distance bounding from vi to u and obtain dbi
2 With all vi 2 V, compute the estimate (x0u, y0u) of the position by MMSE
3 I f for all vi 2 V, |dbip(xix0u)2 + (yiy0u )2| then
f or all (vi, vj , vk) 2 V3, if (x0u, y0u) 2 (vi, vj , vk)
then T = T [ (vi, vj , vk)
i f |T| > 0 then position is accepted and xu = x0u, yu = y0u
else the position is rejected
else the position is rejected
In step 1 of the algorithm, the verifiers v1, ..., vn which are in the power range of the claimant u
perform distance bounding to the claimant u and obtain distance bounds db1, ..., dbn. These distance
bounds as well as the positions of the verifiers (which are precisely known) are then reported to the
authority.
Figure 3.1: Example of Verifiable Multilateration
In step 2, the authority computes an estimate (xâ„¢, yâ„¢) of the claimants position; this position is
computed by using distance bounds from all verifiers in us neighborhood, typically by the MMSE of
the following system of equations:
Let fi(x0u, y0u ) = dbi -p(xix0u)2 + (yiy0u)2
The position of u is obtained by minimizing
F(x0u, y0u) = Pvi2T fi
2(x0u, y0u)
over all estimates of u
In step 3 of the algorithm, the authority runs the following two tests: (i) - test: for all vi, does
the distance between (x0u, y0u) and vi differ from the measured distance bound dbi by less than the
expected distance measurement error and (ii) point in the triangle test: does (x0u, y0u) fall within at
least one physical triangle formed by a triplet of verifiers. Note also that we call the triangle formed
by the verifiers the verification triangle. If both the and the point in the triangle tests are positive,
the authority accepts the estimated position (x0u, y0u ) of the claimant as correct; else, the position is
rejected.
The expected error is a system parameter and depends on the number of verifiers and on the distance
estimation techniques used. This error becomes smaller as more verifiers are used to compute
(x0u, y0u). In most cases, can be approximated as 3, where is the expected standard deviation
of the computed position. The following well known test is run to detect if the claimants estimated
position (x0u, y0u ) falls within the verification triangle (vi, vj , vk)
Point in the triangle test
fij(u) = (y0u - yi)(xj - xi)(x0u - xi)(yjyi)
fki(u) = (y0u yk)(xixk)(x0uxk)(yiyk)
fjk(u) = (y0u yj)(xkxj)(x0uxj)(ykyj)
if fij(u) fjk(u) > 0andfjk(u) fki(u) > 0
then u is in (vi, vj , vk)
The logic behind this test is the following. Three functions fij(u), fik(u), fjk(u) are defined, one for
each edge of the triangle. fij(u) is zero for all points u on the line vi, vj , and non-zero for all other
points. In fact, looking from vj at vi, fij(u) is negative for all points (x, y) on the left side of the
edge vi, vj , and positive for all points (x,y) on the right side of the edge. The same applies for the
other two edges and functions. By combining the output from the three functions we can compute
if a point falls in or out of the triangle (vi, vj , vk).
3.0.2 properties
In this subsection, we summarize the most important properties of the Verifiable Multilateration
mechanism. These are the following: 1) A node located at position p within the triangle/pyramid
formed by the verifiers cannot prove to be at another position p0 6= p within the same triangle/
pyramid. 2) A node located outside the triangle/pyramid formed by the verifiers cannot prove
to be at any position p within the triangle/pyramid. 3) An external attacker performing a distance
enlargement attack cannot trick the verifiers into believing that a claimant located at a location p
in the triangle/pyramid is located at some other position p0 6= p in the triangle/ pyramid.
Chapter 4
(SPINE) Secure positioning in Sensor
Networks
One of the main challenges in sensor networks [18], [19], [20], [21] is sensor positioning. Knowing
the positions of sensors is important for relating the measured data with the physical location. Researchers
have recently proposed a number of positioning algorithms for sensor and ad hoc networks
(see Section VI). The majority of the proposed algorithms rely on insecure local distance measurements
and on cooperation between the nodes that are not necessarily trustworthy. In this section,
we present SPINE, a system for secure positioning of a network of sensors, that is based on Verifiable
Multilateration. We first shortly describe attacks on sensor network positioning systems.
4.1 Threat analysis
We characterize attackers according to the number of external and compromised nodes that they
control. By Attacker-x-y we denote attacker that controls x compromised and y external nodes.
4.1.1 Node physical dispacement and removal
most obvious threats to sensor networks is the physical displacement of nodes. An attacker can
physically displace nodes from their original positions to other positions in the network, or can
temporarily or permanently remove the nodes from the network while this remains undetected to
the nodes or to the network authority. These attacks are especially harmful in sensor networks, in
which the nodes are, given their size and purpose, in most cases easily accessible to the attacker. It
would be naive to believe that this problem can be solved only by a simple exchange of authenticated
beacons between the nodes, or by conventional positioning techniques. If the network is not properly
protected, an external attacker can create the impression to the displaced node and to its neighbors
that the node did not move. A simple approach for the attacker is to replace the network node with a
fake one, and to create a communication link to the new position of the honest node. Typically, this
attack can be performed by Attacker-0-2. By enabling communication between two honest nodes,
the attacker easily creates the impression to the nodes that their positions remained unchanged. This
attack, that we call the node displacement attack .
14
4.2 System model
Figure 4.1: Attacks on sensor network positioning
Our system consists of a set of sensor nodes and a set of reference nodes (landmarks) with known
locations. Nodes and verifiers communicate using radio transmissions. If two nodes reside within the
power range of each other, they are considered neighbors. We assume that the radio link between
neighbors is bidirectional. Nodes measure local information, which is then collected by the central
authority. Communication between nodes may involve multiple wireless hops; we do not make any
specific assumptions about the routing protocol used to transfer packets from their source to their
destination. We assume that the sensor nodes have distance-measuring capabilities, but are not
equipped with GPS receivers. We assume, notably, that the nodes are able to measure the distances
to their neighbors or to the landmarks by using ime-of-arrival or round-trip time measurements with
radio signals. We also assume that the nodes are able to bound their processing delays to a few
nanoseconds.
We assume that the network is operated by an authority. This authority can be on-line, meaning
that the authority operates on-line servers (by single hop or multi-hop communication), or off-line,
meaning that the services of the authority cannot be reached via the network. In any case, the
authority controls the network membership and assigns a unique identity to each node. We further
assume that each node is able generally to accomplish any task required to secure its communications.
We do not assume, however, that the nodes are able to generate or verify public-key signatures. We
assume that all network nodes can establish pairwise secret keys. This can be achieved by manually
pre-loading all keys into the nodes in a network setup phase, by probabilistic key pre-distribution
schemes or through an on-line key distribution center .
4.3 Security analysis
The resistance of SPINE relies on the resistance of BDV to attacks; it depends on the ability of
the attacker to modify the verified distances, but also depends on the positioning algorithm used to
compute node positions with verified distances. Here, we primarily analyze the resistance of BDV to
attacks. We then discuss security implications of using BDV with several positioning algorithms.
The resistance of BDV to attacks depends on the number and on the mutual dependance of triangles
that are formed around the distance. To spoof a distance verified by a single triangle, it
is sufficient that an external attacker enlarges two distances (the distance duv, and one additional
distance between the nodes forming a triangle). This is illustrated on Figure 8, where distances duv
and d1 are enlarged. By enlarging these two distances, all the distances in the verifi- cation triangle
remain mutually consistent. This attack can be performed by an external attacker.
If only a single node in a triangle is compromised, this node can enlarge distances to the claimant
and to other nodes forming the verification triangle. Node v is compromised, and enlarges distances
to u, v2 and to v3 such that all the distances in the verification triangle remain mutually consistent.
Similarly to the attack on Figure 8, if an attacker controls one compromised and one external node,
it can enlarge the measured distance even if the compromised node is not adjacent to the distance.
This essentially means that a single-triangle BDV resists only to attacks that enlarge only a single
distance. If k verification triangles can be formed around a distance, the resistance of BDV to attacks
can be expressed in terms of k. If the triangles are node-disjoint, then BDV resists to up to
2k distance enlargements. This is intuitive, as the distance is verified by k disjoint triangles, and
an attacker needs to spoof the verification process in each of the triangles to successful cheat on the
measured distance.
If the triangles are node-joint and edge-disjoint, then BDV also resists to up to 2k distance enlargements
by external attackers, but it does not resist attacks by a single compromised node adjacent to
the spoofed distance. Essentially, if all triangles have a common (compromised) node, the distance
adjacent to that node can be successfully spoofed. We note here, however, that the triangles formed
around a distance are almost never node-joint, given that some are formed with u and its neighbors
around v, others are formed with v and its neighbors around u, whereas the third set of triangles
is formed by the neighbors of u and v around the two nodes. If the triangles are edge-joint, then
BDV resists to up to k+1 distance enlargements by external attackers. If the nodes are positioned
favorably for the attacker, the attacker can enlarge the joint edge and enlarge one additional edge
from every triangle. We note here that this attack will not always be possible.
Figure 4.2: An Example of a distance attack by extenal nodes
Figure 4.3: Example of a distance enlargement attack by a compromised node
Chapter 5
Application
Our proposal is to see wireless sensor networks rather as a tool than a solution to a specfic problem.
Looking at the history of science and at scientfic discoveries tools have always played the key role.
5.1 Wireless Sensor Networks and Applications:
With the invention of the microscope new scientific discoveries have been enabled. Similarly wireless
sensor networks may enable new observations that were not possible before. However for this to
happen, cooperation with other disciplines is inevitable. In the domain of tangible and physical user
interfaces wireless sensor networks are an enabling technology. In this area the use of sensors in
devices, clothing, and everyday objects provides new ways for creating interactive systems. The user
experience created by such novel interfaces is hardly predictable and therefore trying them out is
essential. In both areas it is important to have a quick and easy way of building prototypes that
allow doing experiments to acquire real data. This was one main motivation to develop the DIY
SmartIts platform. It is designed to allow easy extensibility and tailoring for a specific application
domain.
18
Chapter 6
Conclusion & Future Scope
6.1 Conclusion
In this work, we have analyzed positioning and distance estimation techniques in adversarial settings.
We have shown that most proposed positioning techniques are vulnerable to position spoofing
attacks from external attackers and compromised nodes. We have further shown that positioning
and distance estimation techniques based on radio signal propagation exhibit the best properties for
position verification. We have proposed a novel mechanism for position verification, called Verifiable
Multilateration (VM). Verifiable Multilateration enables secure computation and verification of node
positions in the presence of attackers. We have further proposed SPINE, a system for secure positioning
in a network of sensors, based on Verifiable Multilateration. We have shown that this system
resists against distance modification attacks from a large number of attacker nodes. Our future
work includes a detailed analysis and possible implementation of distance bounding and position
verification techniques. Furthermore, we intend to investigate the applicability of our basic distance
verification scheme to a number of existing positioning algorithms.
19