An on-demand secure routing protocol resilient to byzantine failures.
An ad hoc wireless network is an autonomous self-organizing system ofmobile nodes connected by wireless links where nodes not in directrange can communicate via intermediate nodes. A common technique usedin routing protocols for ad hoc wireless networks is to establish therouting paths on-demand, as opposed to continually maintaining acomplete routing table. A significant concern in routing is theability to function in the presence of byzantine failures whichinclude nodes that drop, modify, or mis-route packets in an attempt todisrupt the routing service.We propose an on-demand routing protocol for ad hoc wireless networks that provides resilience to byzantine failures caused by individual or colluding nodes. Our adaptive probing technique detects a malicious link after log n faults have occurred, where n is the length of the path. These links are then avoided by multiplicatively increasing their weights and by using an on-demand route discovery protocol that finds a least weight path to the destination.
INTRODUCTION
Ad hoc wireless networks are self-organizing multi-hop
wireless networks where all the hosts (nodes) take part in
the process of forwarding packets. Ad hoc networks can
easily be deployed since they do not require any fixed in-
frastructure, such as base stations or routers. Therefore,
they are highly applicable to emergency deployments, natural
disasters, military battle fields, and search and rescue
missions.
A key component of ad hoc wireless networks is an efficient
routing protocol, since all of the nodes in the net-work
act as routers. Some of the challenges faced in ad
hoc wireless networks include high mobility and constrained
power resources. Consequently, ad hoc wireless routing protocols
must converge quickly and use battery power e#-
ciently. Traditional proactive routing protocols (link-state
[1] and distance vectors [1]), which use periodic updates or
beacons which trigger event based updates, are less suitable
for ad hoc wireless networks because they constantly
consume power throughout the network, regardless of the
presence of network activity, and are not designed to track
topology changes occurring at a high rate.
On-demand routing protocols [2, 3] are more appropriate
for wireless environments because they initiate a route discovery
process only when data packets need to be routed.
Discovered routes are then cached until they go unused for
a period of time, or break because the network topology
changes.
Many of the security threats to ad hoc wireless routing
protocols are similar to those of wired networks. For exam-
ple, a malicious node may advertise false routing informa-
tion, try to redirect routes, or perform a denial of service
attack by engaging a node in resource consuming activities
such as routing packets in a loop. Furthermore, due to their
cooperative nature and the broadcast medium, ad hoc wireless
networks are more vulnerable to attacks in practice [4].
Although one might assume that once authenticated, a
node should be trusted, there are many scenarios where this
is not appropriate. For example, when ad hoc networks are
used in a public Internet access system (airports or con-
ferences), users are authenticated by the Internet service
provider, but this authentication does not imply trust between
the individual users of the service. Also, mobile devices
are easier to compromise because of reduced physical
security, so complete trust should not be assumed.
Our contribution. We focus on providing routing survivability
under an adversarial model where any intermediate
node or group of nodes can perform byzantine attacks such
as creating routing loops, misrouting packets on non-optimal
paths, or selectively dropping packets (black hole). Only the
source and destination nodes are assumed to be trusted. We
propose an on-demand routing protocol for wireless ad hoc
networks that operates under this strong adversarial model.
It is provably impossible under certain circumstances, for
example when a majority of the nodes are malicious, to attribute
a byzantine fault occurring along a path to a specific
node, even using expensive and complex byzantine agree-
ment. Our protocol circumvents this obstacle by avoiding
the assignment of "guilt" to individual nodes. Instead it reduces
the possible fault location to two adjacent nodes along
a path, and attributes the fault to the link between them.
As long as a fault-free path exists between two nodes, they
can communicate reliably even if an overwhelming majority
of the network acts in a byzantine manner.
Our protocol consists of the following phases:
. Route discovery with fault avoidance. Using flooding
and a faulty link weight list, this phase finds a least
weight path from the source to the destination.
. Byzantine fault detection. This phase discovers faulty
links on the path from the source to the destination.
Our adaptive probing technique identifies a faulty link
after log n faults have occurred, where n is the length
of the path.
. Link weight management. This phase maintains a weight
list of links discovered by the fault detection algorithm.
A multiplicative increase scheme is used to penalize
links which are then rehabilitated over time. This list
is used by the route discovery phase to avoid faulty
paths.
The rest of the paper is organized as follows. Section 2
summarizes related work. We further define the problem
we are addressing and the model we consider in Section 3.
We then present our protocol in Section 4 and provide an
analysis in Section 5. We conclude and suggest directions
for future work in Section 6.
2. RELATED WORK
Secure routing protocols for ad hoc wireless networks is a
fairly new topic. Although routing in ad hoc wireless networks
has unique aspects, many of the security problems
faced in ad hoc routing protocols are similar to those faced
by wired networks. In this section, we review the work done
in securing routing protocols for both ad hoc wireless and
wired networks.
One of the problems addressed by researchers is providing
an e#ective public key infrastructure in an ad hoc wireless
environment which by nature is decentralized. Examples
of these works are as follows. Hubaux et al.[5] proposed
a completely decentralized public-key distribution system
similar to PGP [6]. Zhou and Haas [7] explored threshold
cryptography methods in a wireless environment. Brown et
al.[8] showed how PGP, enhanced by employing elliptic curve
cryptography, is a viable option for wireless constrained devices

A more general trust model where levels of security are defined
for paths carrying specific classes of tra#c is suggested
in [9]. The paper discusses very briefly some of the cryptographic
techniques that can be used to secure on-demand
routing protocols: shared key encryption associated with a
security level and digital signatures for data source authentication

As mentioned in [10], source authentication is more of a
concern in routing than confidentiality. Papadimitratos and
Haas showed in [11] how impersonation and replay attacks
can be prevented for on-demand routing by disabling route
caching and providing end-to-end authentication using an
HMAC [12] primitive which relies on the existence of security
associations between sources and destinations. Dahill
et al.[16] focus on providing hop-by-hop authentication for
the route discovery stage of two well-known on-demand pro-
tocols: AODV [2] and DSR [3], relying on digital signatures.
Other significant works include SEAD [13] and Ariadne [4]
that provide e#cient secure solutions for the DSDV [14] and
DSR [3] routing protocols, respectively. While SEAD uses
one-way hash chains to provide authentication, Ariadne uses
a variant of the Tesla [15] source authentication technique
to achieve similar security goals.
Marti et al.[18] address a problem similar to the one we
consider, survivability of the routing service when nodes selectively
drop packets. They take advantage of the wireless
cards promiscuous mode and have trusted nodes monitoring
their neighbors. Links with an unreliable history are
avoided in order to achieve robustness. Although the idea of
using the promiscuous mode is interesting, this solution does
not work well in multi-rate wireless networks because nodes
might not hear their neighbors forwarding communication
due to di#erent modulations. In addition, this method is
not robust against collaborating adversaries.
Also, relevant work has been done in the wired network
community. Many researchers focused on securing classes
of routing protocols such as link-state [10, 19, 20, 21] and
distance-vector [22]. Others addressed in detail the security
issues of well-known protocols such as OSPF [23] and
BGP [24]. The problem of source authentication for routing
protocols was explored using digital signatures [23] or
symmetric cryptography based methods: hash chains [10],
chains of one-time signatures [20] or HMAC [21]. Intrusion
detection is another topic that researchers focused on, for
generic link-state [25, 26] or OSPF [27].
Perlman [28] designed the Network-layer Protocol with
Byzantine Robustness (NPBR) which addresses denial of
service at the expense of flooding and digital signatures.
The problem of byzantine nodes that simply drop packets
(black holes) in wired networks is explored in [29, 30]. The
approach in [29] is to use a number of trusted nodes to probe
their neighbors, assuming a limited model and without discussing
how probing packets are disguised from the adver-
sary. A di#erent technique, flow conservation, is used in [30].
Based on the observation that for a correct node the number
of bytes entering a node should be equal to the number of
bytes exiting the node (within a threshold), the authors suggest
a scheme where nodes monitor the flow in the network.
This is done by requiring each node to have a copy of the
routing table of their neighbors and reporting the incoming
and outgoing data. Although interesting, the scheme does
not work when two or more adversarial nodes collude.
3. PROBLEM DEFINITION AND MODEL
In this section we discuss the network and security assumptions
we make in this paper and present a more precise
description of the problem we are addressing.
3.1 Network Model
This work relies on a few specific network assumptions.
Our protocol requires bi-directional communication on all
links in the network. This is also a requirement of most
wireless MAC protocols, including 802.11 [31] and MACAW
[32]. We focused on providing a secure routing protocol,
which addresses threats to the ISO/OSI network layer. We
do not specifically address attacks against lower layers. For
example, the physical layer can be disrupted by jamming,
and MAC protocols such as 802.11 can be disrupted by attacks
using the special RTS/CTS packets. Though MAC
protocols can detect packet corruption, we do not consider
this a substitute for cryptographic integrity checks [33].
3.2 Security Model and Considered Attacks
In this work we consider only the source and the destination
to be trusted. Nodes that can not be authenticated do
not participate in the protocol, and are not trusted. Any
intermediate node on the path between the source and destination
can be authenticated and can participate in the
protocol, but may exhibit byzantine behavior. The goal of
our protocol is to detect byzantine behavior and avoid it.
We define byzantine behavior as any action by an authenticated
node that results in disruption or degradation of the
routing service. We assume that an intermediate node can
exhibit such behavior either alone or in collusion with other
nodes. More generally, we use the term fault to refer to
any disruption that causes significant loss or delay in the
network. A fault can be caused by byzantine behavior, external
adversaries, lower layer influences, and certain types
of normal network behavior such as bursting tra#c.
An adversary or group of adversaries can intercept, mod-
ify, or fabricate packets, create routing loops, drop packets
selectively (often referred to as a black hole), artificially delay
packets, route packets along non-optimal paths, or make
a path look either longer or shorter than it is. All the above
attacks result in disruption or degradation of the routing
service. In addition, they can induce excess resource consumption
which is particularly problematic in wireless networks

There are strong attacks that our protocol can not pre-
vent. One of these strong attacks, referred to as a wormhole
[4], is where two attackers establish a path and tunnel packets
from one to another. For example, the attackers can
tunnel route request packets that can arrive faster than the
normal route request flood. This may result in non-optimal
adversarial controlled routing paths. Our protocol addresses
this attack by treating the wormhole as a single link which
will be avoided if it exhibits byzantine behavior, but does not
prevent the wormhole formation. Also, we do not address
traditional denial of service attacks which are characterized
by packet injection with the goal of resource consumption.
Whenever possible, our protocol uses e#cient cryptographic
primitives. This requires pairwise shared keys 1 which are
established on-demand. The public-key infrastructure used
We discourage group shared keys since this is an invitation
for impersonation in a cooperative environment.
Route
Discovery
Byzantine
Fault
Detection
Link
Weight
Management
Weight List Path Faulty Link

Figure

1: Secure Routing Protocol Phases
for authentication can be either completely distributed (as
described in [5]), or Certificate Authority (CA) based. In
the latter case, a distributed cluster of peer CAs sharing a
common certificate and revocation list can be deployed to
improve the CA's availability.
3.3 Problem Definition
The goal of this work is to provide a robust on-demand
ad hoc routing service which is resilient to byzantine behavior
and operates under the network and security models
described in Sections 3.1 and 3.2. We attempt to bound the
amount of damage an adversary or group of adversaries can
cause to the network.
4. SECURE ROUTING PROTOCOL
Our protocol establishes a reliability metric based on past
history and uses it to select the best path. The metric is
represented by a list of link weights where high weights correspond
to low reliability. Each node in the network maintains
its own list, referred to as a weight list, and dynamically
updates that list when it detects faults. Faulty links
are identified using a secure adaptive probing technique that
is embedded in the normal packet stream. These links are
avoided using a secure route discovery protocol that incorporates
the reliability metric.
More specifically, our routing protocol can be separated
into three successive phases, each phase using as input the
output from the previous (see Figure 1):
. Route discovery with fault avoidance. Using flooding,
cryptographic primitives, and the source's weight list
as input, this phase finds and outputs the full least
weight path from the source to the destination.
. Byzantine fault detection. The goal of this phase is
to discover faulty links on the path from the source
to the destination. This phase takes as input the full
path and outputs a faulty link. Our adaptive probing
technique identifies a faulty link after log n faults
occurred, where n is the length of the path. Cryptographic
primitives and sequence numbers are used to
protect the detection protocol from adversaries.
. Link weight management. This phase maintains a weight
list of links discovered by the fault detection algo-
rithm. A multiplicative increase scheme is used to
penalize links which are then rehabilitated over time.
The weight list is used by the route discovery phase to
avoid faulty paths.
4.1 Route Discovery with Fault Avoidance
Our route discovery protocol floods both the route request
and the response in order to ensure that if any fault free path
exists in the network, a path can be established. However,
there is no guarantee that the established path is free of
Procedure list:
creates a message of the concatenated item list, signed by the current node, and broadcasts it
broadcasts a message
verifies the signature and exits the procedure if the signature is not valid
Find( list, item returns an item in a list, or NULL if the item does not exist
InsertList( list, item inserts an item in a list
UpdateList( list, item ) - replaces the item in a list
returns the listed weight of the link between A and B, or one if the link is not listed
Code executed at node source when a new route to node destination is needed:
(1) CreateSignSend( REQUEST, destination, source, req sequence, weight list )
Code executed at node this node when a request message req is received:
(2) if( Find( requests list,
(4) if( this node = req.destination )
(5) CreateSignSend( RESPONSE, req.destination, req.source, req.req sequence, req.high weights list )
else
InsertList(requests list, req)
Code executed at node this node when a response message res is received:
(12) prev node = res.destination
total weight += LinkWeight( res.weight list, prev node, res.hops[i].node )
list, prev node, this node )
res )
else
(32) if( this node = source )
path list, res )
else
CreateSignSend( res, this node )
res )

Figure

2: Route Discovery Algorithm
adversarial nodes. The initial flood is required to guarantee
that the route request reaches the destination. The response
must also be flooded because if it was unicast, a single adversary
could prevent the path from being established. If an
adversary was able to prevent routes from being established,
the fault detection algorithm would be unable to detect and
avoid the faulty link since it requires a path as input in order
to operate.
A digital signature is used to authenticate the source.
This is required to prevent unauthorized nodes from initiating
resource consuming route requests. An unauthorized
route request would fail verification and be dropped by each
of the requesting node's immediate neighbors, preventing
the request from flooding through the network.
At the completion of the route discovery protocol, the
source is provided with the complete path to the destina-
tion. Many on-demand routing protocols use route caching
by intermediate nodes as an optimization; we do not consider
it in this work because of the security implications. We
intend to address route caching optimizations with strong
security semantics in a future work.
Our route discovery protocol uses link weights to avoid
faults. A weight list is provided by the link weight management
phase (Section 4.3). The route discovery protocol
chooses a route that is a minimum weight path between the
source and the destination. This path is found during a
flood by accumulating the cost hop by hop and forwarding
the flood only if the new cost is less than the previously
forwarded cost. The protocol uses digital signatures at each
hop to prevent an adversary from specifying an arbitrary
path. For example, it can stop an adversary from inventing
a short path in an attempt to draw packets into a black
hole. Since the cost associated with signing a message at
each hop is very high, the weights are accumulated as part
of the response flood instead of the request flood in order to
minimize the cost of route requests to unreachable destinations

If only the source verifies all of the weights and signa-
tures, then the protocol becomes vulnerable to attacks on
the response flood propagation. The adversaries could block
correct information from reaching the source by propagating
low cost fabricated responses. The source can ignore non-
authentic responses, however, since intermediate nodes only
re-send lower cost information, a valid response would never
reach the source. Therefore, each intermediate node must
verify the weights and the signatures carried by a response,
in order to guarantee that a path will be established.
An adversary can still influence the path selection by creating
what we refer to as virtual links. A virtual link is
formed when adversaries form wormholes, as described in
Section 3.2, or any other type of shortcuts in the network.
A virtual link can be created by deleting one or more hops
from the end of the route response. Our detection algorithm
(Section 4.2) can identify and avoid virtual links if they exhibit
byzantine behavior, but our route discovery algorithm
does not prevent their formation. We present a detailed
analysis of the e#ect of virtual links in Section 5.
As part of the route discovery protocol, each node maintains
a list of recent requests and responses that it has already
forwarded. The following five steps comprise the route
discovery protocol (see also Figure 2):
I. Request Initiation. The source creates and signs a request
that includes the destination, the source, a sequence
number, and a weight list (see Line 1, Figure 2). The source
then broadcasts this request to its neighbors. The source's
signature allows the destination and intermediate nodes to
authenticate the request and prevents an adversary from
creating a false route request.
II. Request Propagation. The request propagates to the
destination via flooding which is performed by the intermediate
nodes as follows. When receiving a request, the node
first checks its list of recently seen requests for a matching
request (one with the exact same destination, source, and
request identifiers). If there is no matching request in its list,
and the source's signature is valid, it stores the request in
its list and rebroadcasts the request (see Lines 2-10, Figure
2). If there is a matching request, the node does nothing.
III. Request Receipt / Response Initiation. Upon receiving
a new request from a source for the first time, the destination
verifies the authenticity of the request, creates and
signs a response that contains the source, the destination, a
response sequence number and the weight list from the request
packet. The destination then broadcasts this response
(see Lines 2-10, Figure 2).
IV. Response Propagation. When receiving a response,
the node computes the total weight of the path by summing
the weight of all the links on the specified path to this
node (Lines 12-18, Figure 2). If the total weight is less than
any previously forwarded matching response (same source,
destination and response identifiers), the node verifies the
signatures of the response header and every hop listed on
the packet so far 2 (Lines 28-31, Figure 2). If the entire
packet is verified, the node appends its identifier to the end
of the packet, signs the appended packet, and broadcasts
the modified response (Lines 35-36, Figure 2).
V. Response Receipt. When the source receives a response,
it performs the same computation and verification as the
intermediate nodes as described in the response propagation
step. If the path in the response is better than the best path
received so far, the source updates the route used to send
packets to that specific destination (see Line 33, Figure 2).
4.2 Byzantine Fault Detection
Our detection algorithm is based on using acknowledgments
(acks) of the data packets. If a valid ack is not received
within a timeout, it is assumed that the packet has
been lost. Note that this definition of loss includes both malicious
and non-malicious causes. A loss can be caused by
packet drop due to bu#er overflow, packet corruption due to
interference, a malicious attempt to modify the packet con-
tents, or any other event that prevents either the packet or
the ack from being received and verified within the timeout.
A network operating "normally" exhibits some amount of
loss. We define a threshold that sets a bound on what is
considered a tolerable loss rate. In a well behaved network
the loss rate should stay below the threshold. We define a
fault as a loss rate greater than or equal to the threshold.
To maximize the performance of multiple verifications we
use RSA keys with a low public exponent.
The value of the threshold also specifies the amount of loss
that an adversary can create without being detected. Hence,
the threshold should be chosen as low as possible, while still
greater than the normal loss rate. The threshold value is
determined by the source, and may be varied independently
for each route to accommodate di#erent situations, but this
work uses a fixed threshold.
While this threshold scheme may seem overly "simple",
we would like to emphasize that our protocol provides fault
avoidance and never disconnects nodes from the network.
Thus, the impact of false positives, due to normal events
such as bursting tra#c, is drastically reduced. This provides
a much more flexible solution than one where nodes
are declared faulty and excluded from the network. In ad-
dition, this avoidance property allows the threshold to be
set very low, where it may be periodically triggered by false
positives, without severely impacting network performance
or a#ecting network connectivity.
A substantial advantage of our protocol is that it limits
the overhead to a minimum under normal conditions. Only
the destination is required to send an ack when no faults
have occurred. If losses exceed the threshold, the protocol
attempts to locate the faulty link. This is achieved by requiring
a dynamic set of intermediate nodes, in addition to
the destination node, to send acks to the source.
Normal topology changes occur frequently in ad hoc wireless
networks. Although our detection protocol locates "faulty
links" that are caused by these changes, an optimized mechanism
for detecting them would decrease the overhead and
detection time. Any of the mechanisms described in the
route maintenance section of the DSR protocol [3], for instance
MAC layer notification, can be used as an optimized
topology change detector. When our protocol receives notification
from such a detector, it reacts by creating a route
error message that is propagated along the path back to the
source. The node that generates this message, signs it, in
order to provide integrity and authentication. Upon receipt
of an authenticated route error message, the source passes
the faulty link to the link weight management phase. Note
that an intermediate node exhibiting byzantine behavior can
always incriminate one of its links, so adding a mechanism
that allows it to explicitly declare one of its links faulty, does
not weaken the security model.
Fault Detection Overview. Our fault detection protocol
requires the destination to return an ack to the source, for
every successfully received data packet. The source keeps
track of the number of recent losses (acks not received over
a window of recent packets). If the number of recent losses
violates the acceptable threshold, the protocol registers a
fault between the source and the destination and starts a
binary search on the path, in order to identify the faulty
link. A simple example is illustrated in Figure 3.
The source controls the search by specifying a list of intermediate
nodes on data packets. Each node in the list, in
addition to the destination, must send an ack for the packet.
We refer to the set of nodes required to send acks as probed
nodes, or for short probes. Since the list of probed nodes
is specified on legitimate tra#c, an adversary is unable to
drop tra#c without also dropping the list of probed nodes
and eventually being detected.
The list of probes defines a set of non-overlapping intervals
that cover the whole path, where each interval covers the
Source Destination
Trusted End Point
Intermediate Router
Successful Probe
Failed Probe
Fault Location
Good Interval
Faulty Interval
Unknown Interval
Success
Failure 1
Failure 2
Failure 3
Failure 4

Figure

3: Byzantine Fault Detection
sub-path between the two consecutive probes that form its
endpoints. When a fault is detected on an interval, the
interval is divided in two by inserting a new probe. This
new probe is added to the list of probes appended to future
packets. The process of sub-division continues until a fault is
detected on an interval that corresponds to a single link. In
this case, the link is identified as being faulty and is passed
as input to the link weight management phase (see Figure
1). The path sub-division process is a binary search that
proceeds one step for each fault detected. This results in the
identification of a faulty link after log n faults are detected,
where n is the length of the path.
We use shared keys between the source and each probed
node as a basis for our cryptographic primitives in order to
avoid the prohibitively high cost of using public key cryptography
on an per packet basis. These pairwise shared keys
can be established on-demand via a key exchange protocol
such as Di#e-Hellman [34], authenticated using digital sig-
natures. The on-demand key exchange must be fully integrated
into the fault detection protocol in order to maintain
the security semantics. The integrated key exchange operates
similarly to the probe and ack specification discussed
below (see also Figure 4), but it is not described in detail in
this work.
Probe Specification. The mechanism for specifying the
probe list on a packet is essential for the correct operation of
the detection protocol. The probes are specified in the list
in the same order as they appear on the path. The list is
"onion" encrypted [17]. Each probe is specified by the identifier
of the node, an HMAC of the packet (not including the
list), and the encrypted remaining list (see Lines 3-6, Figure
4). Both the HMAC and the encrypted remaining list are
computed with the shared key between the source and that
node. An HMAC [12] using a one-way hash function such as
SHA1 [35] and a standard block cipher encryption algorithm
such as AES [36] can be used.
A node can detect if it is required to send acks by checking
the identifier at the beginning of the list (see Lines 8-12,

Figure

4). If it matches, then it verifies the HMAC of the
packet and replaces the list on the packet with the decrypted
version of the remaining list. This mechanism forces the
Procedure list:
returns the concatenation of a, b, etc.
Hmac( data, key ) - compute and return the hmac of data using key
data with key and return result
Report Loss and Return( node ) - reports that a loss was detected on the interval before node and exit the procedure
Code executed at source when sending a packet with the contents data to destination :
Code executed at this node when receiving a packet with the contents source, destination,
enc data, id, hmac, enc remainder :
node and
waiting for ack = true
Schedule ack timer()
Code executed at destination when receiving a packet with the contents source, destination, counter, enc data, hmac:
prev counter and
Code executed at probed node when receiving an ack with the contents source, ack node, counter, enc remainder:
waiting for ack )
encrypted ack = Encrypt( Cat( ack node, counter, enc remainder
probed node.id, counter, enc ack, Hmac( Cat( probed node.id, counter, enc ack ), source.key
waiting for ack = false
Unschedule ack timer()
Code executed at this node when ack timer expires:
waiting for ack = false
source, this node.id, counter, Hmac( Cat( this node.id, counter ), source.key
Code executed at source when ack timer expires:
waiting for ack = false
Report Loss and Return( probe list[0] )
Code executed at source when receiving an ack with the contents source, ack node, counter, enc remainder, hmac:
ack and ack node = probe list[0].id and
waiting for ack = false
Unschedule ack timer()
Report Loss and Return( probe list[i] )
ack node, counter, enc remainder,
(35) if( ack node #= probe list[i].id or hmac #= Hmac( Cat( ack node, counter, enc remainder ), ack node.key )
Report Loss and Return( probe list[i] )
Report Loss and Return( destination )
ack node, counter,
destination or hmac #= Hmac( Cat( ack node, counter
Report Loss and Return( destination )
return

Figure

4: Probe and Acknowledgement Specification
packet to traverse the probes in order, which verifies the
route taken. Additionally, it verifies the contents of the
packet at every probe point. The onion encryption prevents
the adversary from incriminating other links by removing
specific nodes from the probe list. Note that the adversary is
able to remove the entire probe list, but this will incriminate
one of its own links.

Acknowledgment

Specification. If the adversary can drop
individual acks, it can incriminate any arbitrary link along
the path. In order to prevent this, each probe does not send
its ack immediately, but waits for the ack from the next
probe and combines them into one ack. Each ack consists of
the identifier of the probe, the identifier of the data packet
that is being acknowledged, the ack received from the next
probe encrypted with the key shared by this probe and the
source, and an HMAC of the new combined ack (see Lines
15 and 18-19,

Figure

4).
If no ack is received within a timeout, the probe gives up
waiting, and creates and sends its ack (see Line 24, Figure
4). The timeouts are set up in such a way that if there is a
failure, all the acks before the failure point can be combined
without other timeouts occurring. This is accomplished by
setting the timeout for each probe to be the upper bound of
the round-trip from it to the destination.
Upon receipt of an ack, the source checks the acks from
each probe by successively verifying the HMACs and decrypting
the next ack (see Lines 27-54, Figure 4). The source
either verifies all the acks up through the destination, or discovers
a loss on the interval following the last ack.
Interval and Probe Management. Let # be the acceptable
threshold loss rate. By using the above probe and acknowledgment
specifications, it is simple to attribute losses
to individual intervals. A loss is attributed to an interval
between two probes when the source successfully received
and verified an ack from the closer probe, but does not from
the further probe. When the loss rate on an interval exceeds
# , the interval is divided in two.
Maintaining probes adds overhead to our protocol, so it is
desirable to retire probes when they are no longer needed.
The mechanism for deciding when to retire probes is based
on the loss rate # and the number of lost packets. The goal
is to amortize the cost of the lost packets over enough good
packets, so that the aggregate loss rate is bounded to # .
Each interval has an associated counter C that specifies
its lifetime. Initially, there is one interval with a counter
of zero (there are initially no losses between the source and
destination). When a fault is detected on an interval with a
counter C, a new probe is inserted which divides the interval.
Each of the two new intervals have their counters initialized
to is the number of losses that caused
the fault. The counters are decremented for every ack that
is successfully received, until they reach zero. When the
counters of both intervals on either side of a probe reach
zero, the probe is retired joining the two intervals.
In the worst case scenario, a dynamic adversary can cause
enough loss to trigger a fault, then switch to causing loss just
under # in order to wait out the additional probe, and then
repeat when the probe is removed. This results in a loss
rate bounded to 2# . If the adversary attempts to create a
higher loss rate, the algorithm will be able to identify the
faulty link.
4.3 Link Weight Management
An important aspect of our protocol is its ability to avoid
faulty links in the process of route discovery by the use of
link weights. The decision to identify a link as faulty is made
by the detection phase of the protocol. The management
scheme maintains the weight list using the history of faults
that have been detected. When a link is identified as faulty,
we use a multiplicative increase scheme to double its weight.
The technique we use for reseting a link weight is similar
to the one we use for retiring probes (see Section 4.2). The
weight of a link can be reset to half of the previous value
after the counter associated with that link returns to zero. If
- is the number of packets dropped while identifying a faulty
link, then the link's counter is increased by -/# where # is
the threshold loss rate. Each non-zero counter is reduced by
1/m for every successfully delivered packet, where m is the
number of links with non-zero counters. This bounds the
aggregate loss rate to 2# in the worst case.
5. ANALYSIS
Our protocol ensures that, even in a highly adversarial
controlled network, as long as there is one fault-free path,
it will be discovered after a bounded number of faults have
occurred. As defined in Section 4.2, a fault means a violation
of the threshold loss rate. We consider a network of n nodes
of which k exhibit adversarial behavior. The adversaries
cooperate and create the maximum number of virtual links
possible in order to slow the convergence of our algorithm.
We provide an analysis of the upper bound for the total
number of packets lost while finding the fault free path. This
bound is defined by the number of losses that result in an
increase of the costs of all adversarial controlled paths above
the cost of the
Let q - and q + be the total number of lost packets and
successfully transmitted packets, respectively. Ideally, q -
# 0, where # is the transmission success rate, slightly
higher than the original threshold. This means the number
of lost packets is a #-fraction of the number of transmitted
packets. While this is not quite true, it is true "up to an
additive constant", i.e. ignoring a bounded number # of
packets lost. Specifically, we prove that there exists an upper
bound # for the previous expression. We show that:
Assume that there are k adversarial nodes, k < n. We denote
by -
E the set of "virtual links" controlled by adversarial
nodes. The maximum size of -
E is kn.
Consider a faulty link e, convicted je times and rehabilitated
ae times. Then, its weight, we , is at most n,
means that the whole path is adversarial. By the algorithm,
we is given by the formula:
The number of convictions is at least q -
, so
je < 0. (3)
Also, the number of rehabilitations is at most q
-/# , so
ae
-/#
where - is the number of lost packets that exposes a link.
Thus
-/#
(je - ae) (5)
From Eq. 2 we have je log we . Therefore:
(je
log we (6)
By combining Eq. 5 and 6, we obtain
log we # - kn - log n (7)
and since is the number of lost packets
per window, Eq. 7 becomes
Therefore, the amount of disruption a dynamic adversary
can cause to the network is bounded. Note that kn represents
the number of links controlled by an adversary. If
there is no adversarial node Eq. 8 becomes the ideal case
6. CONCLUSIONS AND FUTURE WORK
We presented a secure on-demand routing protocol resilient
to byzantine failures. Our scheme detects malicious
links after log n faults occurred, where n is the length of the
routing path. These links are then avoided by the route discovery
protocol. Our protocol bounds logarithmically the
total amount of damage that can be caused by an attacker
or group of attackers.
An important aspect of our protocol is the algorithm used
to detect that a fault has occurred. However, it is di#cult to
design such a scheme that is resistant to a large number of
adversaries. The method suggested in this paper uses a fixed
threshold scheme. We intend to explore other methods, such
as adaptive threshold or probabilistic schemes which may
provide superior performance and flexibility.
In order to further enhance performance, we would like to
investigate ways of taking advantage of route caching without
breaching our security guarantees.
We also plan to evaluate the overhead of our protocol with
respect to existing protocols, in normal, non-faulty conditions
as well as in adversarial environments. Finally, we
are interested in investigating means of protecting routing
against traditional denial of service attacks.

Acknowledgments

We are grateful to Giuseppe Ateniese, Avi Rubin, Gene
Tsudik and Moti Yung for their comments. We would like to
thank Jonathan Stanton and Ciprian Tutu for helpful feed-back
and discussions. We also thank the anonymous referees
for their comments.
We would like to thank the Johns Hopkins University Information
Security Institute for providing the funding that
made this research possible.
7.



--R

Computer Networking

DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks
"Ariadne: A secure on-demand routing protocol for ad hoc networks,"
"The quest for security in mobile ad hoc networks,"

"Securing ad hoc networks,"
"PGP in constrained wireless devices,"
"Security-aware ad hoc routing for wireless networks,"
"Reducing the cost of security in link-state routing,"
"Secure routing for mobile ad hoc networks,"
The Keyed-Hash Message Authentication Code (HMAC)
"SEAD: Secure e#cient distance vector routing for mobile wireless ad hoc networks,"
"Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,"
"E#cient and secure source authentication for multicast,"
"A secure routing protocol for ad hoc networks,"
"Anonymous connections and onion routing,"
"Mitigating routing misbehavior in mobile ad hoc networks,"
"An e#cient message authentication scheme for link state routing,"
"E#cient protocols for signing routing messages,"
"E#cient and secure network routing algorithms."
"Securing distance-vector routing protocols,"
"Digital signature protection of the OSPF routing protocol,"
"E#cient security mechanisms for the border gateway routing protocol,"
"Intrusion detection for link-state routing protocols,"
"Statistical anomaly detection for link-state routing protocols,"
"JiNao: Design and implementation of a scalable intrusion detection system for the OSPF routing protocol,"
Network Layer Protocols with Byzantine Robustness.
"Protecting routing infrastructures from denial of service using cooperative intrusion detection,"
"Detecting disruptive routers: A distributed network monitoring approach,"
ANSI/IEEE Std 802.11

"When the CRC and TCP checksum disagree,"
"New directions in cryptography,"


--TR
Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers
The official PGP user''s guide
Protecting routing infrastructures from denial of service using cooperative intrusion detection
Mitigating routing misbehavior in mobile ad hoc networks
When the CRC and TCP checksum disagree
DSR
The quest for security in mobile ad hoc networks
Security-aware ad hoc routing for wireless networks
Computer Networking
Ariadne:
Digital signature protection of the OSPF routing protocol
Reducing The Cost Of Security In Link-State Routing
Securing Distance-Vector Routing Protocols
An efficient message authentication scheme for link state routing
Anonymous Connections and Onion Routing
A Secure Routing Protocol for Ad Hoc Networks TITLE2:

--CTR
Sylvie Laniepce , Jacques Demerjian , Amdjed Mokhtari, Cooperation monitoring issues in ad hoc networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
Taojun Wu , Yuan Xue , Yi Cui, Preserving Traffic Privacy in Wireless Mesh Networks, Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, p.459-461, June 26-29, 2006
Rajendra V. Boppana , Saman Desilva, Evaluation of a Stastical Technique to Mitigate Malicious Control Packets in Ad Hoc Networks, Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, p.559-563, June 26-29, 2006
Yih-Chun Hu , David B. Johnson, Securing quality-of-service route discovery in on-demand routing for ad hoc networks, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA
Mike Burmester , Tri Van Le , Alec Yasinsac, Adaptive gossip protocols: Managing security and redundancy in dense ad hoc networks, Ad Hoc Networks, v.5 n.3, p.313-323, April, 2007
Imad Aad , Jean-Pierre Hubaux , Edward W. Knightly, Denial of service resilience in ad hoc networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
A. A. Pirzada , C. McDonald, Trust Establishment In Pure Ad-hoc Networks, Wireless Personal Communications: An International Journal, v.37 n.1-2, p.139-168, April     2006
Jiejun Kong , Xiaoyang Hong , Yunjung Yi , Joon-Sang Park , Jun Liu , Mario Gerla, A secure ad-hoc routing approach using localized self-healing communities, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
Sasikanth Avancha , Jeffrey Undercoffer , Anupam Joshi , John Pinkston, Security for wireless sensor networks, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
Jiejun Kong , Xiaoyan Hong , Mario Gerla, Modeling Ad-hoc rushing attack in a negligibility-based security framework, Proceedings of the 5th ACM workshop on Wireless security, September 29-29, 2006, Los Angeles, California
Bogdan Carbunar , Ioanis Ioannidis , Cristina Nita-Rotaru, JANUS: towards robust and malicious resilient routing in hybrid wireless networks, Proceedings of the 2004 ACM workshop on Wireless security, October 01-01, 2004, Philadelphia, PA, USA
Bharat Bhargava , Xiaoxin Wu , Yi Lu , Weichao Wang, Integrating heterogeneous wireless technologies: a cellular aided mobile Ad Hoc network (CAMA), Mobile Networks and Applications, v.9 n.4, p.393-408, August 2004
Ignacy Gawedzki , Khaldoun Al Agha, How to avoid packet droppers with proactive routing protocols for ad hoc networks, International Journal of Network Management, v.18 n.2, p.195-208, March 2008
Sathishkumar Alampalayam , Anup Kumar, An Adaptive and Predictive Security Model for Mobile Ad hoc Networks, Wireless Personal Communications: An International Journal, v.29 n.3-4, p.263-281, June 2004
Panagiotis Papadimitratos , Zygmunt J. Haas, Secure data transmission in mobile ad hoc networks, Proceedings of the ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA
Xiaoxin Wu , Ninghui Li, Achieving privacy in mesh networks, Proceedings of the fourth ACM workshop on Security of ad hoc and sensor networks, October 30-30, 2006, Alexandria, Virginia, USA
Yih-Chun Hu , Adrian Perrig, A Survey of Secure Wireless Ad Hoc Routing, IEEE Security and Privacy, v.2 n.3, p.28-39, May 2004
I. G. Niemegeers , S. M. Heemstra De Groot, Research Issues in Ad-Hoc Distributed Personal Networking, Wireless Personal Communications: An International Journal, v.26 n.2-3, p.149-167,
on-demand routing;ad hoc wireless networks;security;byzantine failures