This document contains new research results in the field of security and privacy in
wireless ad hoc and sensor networks. Wireless ad hoc networks are self-organizing
wireless networks of end-user devices, where all networking services are provided by
the devices themselves without the help of any fixed infrastructure. Such networks will
never replace the existing infrastructure based Internet, but they can provide a new form
of wireless access, which has some advantages over traditional wireless access solutions.
Wireless sensor networks represent a special application area of ad hoc networking, where
the devices are tiny sensors that also have computing and wireless communication
capabilities. The sensors collect measurement data from the environment, and send their data
over multiple wireless hops to a set of few sink nodes, or base stations, for further
processing. From the networking point of view, sensor networks are often considered to be
self-organizing ad hoc networks.
While these new types of wireless networks have potentially useful applications, they
also represent an interesting challenge in terms of security. The most important challenges
include the lack of physical protection and the scarcity of resources. In many applications,
such networks are deployed in an environment where the devices simply cannot be protected by
physical means. In addition, providing tamper resistance for devices is expensive, and therefore,
it is not a viable option in applications where devices must be deployed in large quantities
(e.g., sensors) and hence unit cost must be kept very low. For this reason, we must assume that
devices can be compromised, and we must design our security mechanisms in such a way that they do not
fail in the presence of such compromised devices. For the same reason of economic viability, devices
in wireless ad hoc and sensor networks are usually constrained in terms of CPU power, memory,
communication range and speed, and available energy. Hence, our security mechanisms should be designed
with these resource limitations in mind.
The new security mechanisms that we propose in this document satisfy the above requirements:
they can tolerate compromised nodes and they also respect the resource constraints of the
environment. We grouped our results into 5 thesis groups as follows:
In the first thesis group (Section 1), we study the
problem of securing routing protocols in wireless ad hoc networks.
First, we present new attacks on existing routing protocols. Then,
we propose a mathematical framework in which security of routing
can be precisely defined, and routing protocols for
wireless ad hoc networks can be proved to be secure in a rigorous
manner. Our framework is tailored for on-demand source routing
protocols, but the general principles are applicable to other
types of protocols too. We also propose a new on-demand source
routing protocol, called endairA, and we demonstrate the usage of
our framework by proving that it is secure in our model.
In the second thesis group (Section 2), we study
another aspect of routing in wireless ad hoc networks, namely, the
function of packet forwarding. As mentioned before, wireless ad hoc networks are often assumed
to be fully self-organizing, where the nodes have to forward packets
for each other in order to enable multi-hop communication. This requires
the nodes to cooperate, but nodes may behave selfishly and jeopardize the
operation of the network. Here, we study if cooperation can emerge
spontaneously in static wireless ad hoc networks, without any explicit
incentive mechanism. We propose a model based on game theory to investigate
equilibrium conditions of packet forwarding strategies. We give the conditions
under which cooperation can exist sponatneously, and we perform simulations
to estimate the probability that the conditions for a cooperative equilibrium
hold. We conclude that in static ad hoc networks -- where the relationships
between the nodes are likely to be stable -- cooperation is unlikely to
emerge spontaneously and it needs to be encouraged.
In the third thesis group (Section 3), we address the
problem of wormhole attacks in wireless networks. A wormhole is a fast
out-of-band connection between two distant physical locations, which is
established by the attacker for the purpose of tunneling traffic between
those two locations. Wormholes can mislead neighbor discovery protocols, and
they can have serious negative effects on routing in ad hoc networks.
To address this problem, we propose three new wormhole detection mechanisms.
Two of our mechanisms use a centralized approach applicable in wireless sensor
networks, and they are both based on statistical hypothesis testing.
Both mechanisms assume that the sensors send their neighbor list to the
base station, and it is the base station that runs the wormhole detection
algorithm on the network graph that is reconstructed from the received neighborhood
information. Our third wormhole detection mechanism follows
a decentralized approach applicable in any ad hoc network, where pairs of nodes can detect locally if they are
connected via a wormhole by using our proposed authenticated distance bounding
protocol.
In the fourth thesis group (Section 4), we address the problem of pollution attacks in coding based
distributed storage systems proposed for wireless sensor networks.
In a pollution attack, the adversary maliciously alters some of the
stored encoded packets, which results in the incorrect decoding of a
large part of the original data upon retrieval. We propose
algorithms to detect and recover from such attacks and we study the
performance of the proposed algorithms in terms of communication and computing
overhead, and in terms of success rate. In contrast to
existing approaches to solve this problem, our approach is not based
on adding cryptographic checksums or signatures to the encoded
packets; rather, we take advantage of the inherent redundancy in
such distributed storage systems.
Finally, in the fifth thesis group (Section 5), we study the problem of efficient privacy
preserving authentication in resource constrained environments, such as sensor
networks or RFID systems. More specifically, we improve an approach that was proposed
earlier by others. This approach uses key-trees, and its basic problem is that
the level of privacy provided by the system to its members decreases
considerably if some members are compromised. We analyze this problem, and
show that careful design of the key-tree can help to minimize this loss of privacy.
First, we introduce a benchmark metric for measuring the resistance of the system
to a single compromised member. This metric is based on the well-known
concept of anonymity sets. Then, we show how the parameters of the
key-tree should be chosen in order to maximize the system's
resistance to single member compromise under some constraints on
the authentication delay. In the general case, when any member can
be compromised, we give a lower bound on the level of privacy
provided by the system. We also present some simulation results
that show that this lower bound is sharp.