. 64
( 87 .)


the request. The source node discards replays that do not match with pending query iden-
tifiers and checks the integrity using the MAC generated by the destination.
The basic version of SRP is subject to route cache poisoning attacks: routing informa-
tion gathered by nodes that operate in promiscuous mode in order to improve the efficien-
cy of the DSR protocol could be invalid because they were fabricated by malicious nodes.
The authors propose two alternative designs of SRP that uses an Intermediate Node Reply
Token (INRT). INRT allows intermediate nodes that belong to the same group that share a
common key (KG) to validate RREQ and provide valid RREP messages.
SRP suffers also from the lack of a validation of route maintenance messages: route er-
rors packets are not verified. However, in order to minimize the effects of fabricated error
messages, SRP source-routes error packets along the prefix of the route reported as bro-
ken; as a consequence, the source node can verify that the provided route error feedback
refers to the actual route and is not generated by a node that is not even part of the route. A
malicious node can harm only the route it belongs to.
Assuming that the neighbor discovery mechanism maintains information on the bind-
ing of the medium-access control and the IP addresses of nodes, SRP has proven to be es-
sentially immune to IP spoofing [1].
SRP is, however, not immune to the wormhole attack: two colluding malicious nodes
can misroute the routing packets on a private network connection and alter the network
topology that a benign node can collect. ARIADNE. Hu, Perrig, and Johnson developed Ariadne, an on-demand se-
cure ad hoc routing protocol based on DSR that withstands node compromise and relies
only on highly efficient symmetric cryptography. Ariadne guarantees that the target node
of a route discovery process can authenticate the initiator, that the initiator can authenti-
cate each intermediate node on the path to the destination present in the RREP message,
and that no intermediate node can remove a previous node in the node list in the RREQ or
RREP messages.
As for the SRP protocol, Ariadne needs some mechanism to bootstrap authentic keys
required by the protocol. In particular, each node needs a shared secret key (KS,D is the
shared key between a source S and a destination D) with each node it communicates with
at a higher layer, an authentic TESLA [3, 4] key for each node in the network, and an au-
thentic “Route Discovery Chain” element for each node for which this node will forward
RREQ messages.
Ariadne provides point-to-point authentication of a routing message using a message
authentication code (MAC) and a shared key between the two parties. However, for au-
thentication of a broadcast packet such as RREQ, Ariadne uses the TESLA broadcast au-
thentication protocol. Ariadne copes with attacks performed by malicious nodes that mod-
ify and fabricate routing information, with attacks using impersonation, and, in an
advanced version, with the wormhole attack. Selfish nodes are not taken into account.
In Ariadne, the basic RREQ mechanism is enriched with eight fields used to provide
authentication and integrity to the routing protocol:

<ROUTE REQUEST, initiator, target, id, time interval, hash chain, node list, MAC list>

The initiator and target are set to the address of the initiator and target nodes, respectively.
As in DSR, the initiator sets the ID to an identifier that it has not recently used in initiat-
ing a route discovery. The time interval is the TESLA time interval at the pessimistic ex-

pected arrival time of the request at the target, accounting for clock skew. The initiator of
the request then initializes the hash chain to MACKS,D (initiator, target, ID, time interval)
and the node list and MAC list to empty lists.
When any node A receives a RREQ for which it is not the target, the node checks its lo-
cal table of <initiator, id> values from recent requests it has received, to determine if it has
already seen a request from this same route discovery. If it has, the node discards the
packet, as in DSR. The node also checks whether the time interval in the request is valid:
that time interval must not be too far in the future, and the key corresponding to it must
not have been disclosed yet. If the time interval is not valid, the node discards the packet.
Otherwise, the node modifies the request by appending its own address (A) to the node list
in the request, replacing the hash chain field with H [A, hash chain], and appending a
MAC of the entire REQUEST to the MAC list. The node uses the TESLA key KAi to com-
pute the MAC, where i is the index for the time interval specified in the request. Finally,
the node rebroadcasts the modified RREQ, as in DSR.
When the target node receives the RREQ, it checks the validity of the request by deter-
mining that the keys from the time interval specified have not been disclosed yet, and that
the hash chain field is equal to

H[ ,H[ , H [. . . , H [ , MACKSD (initiator, target, id, time interval) ] . . . ] ] ]
n n“1 1

where i is the node address at position i of the node list in the request, and where n is the
number of nodes in the node list. If the target node determines that the request is valid, it
returns a RREP to the initiator, containing eight fields:

<ROUTE REPLY, target, initiator, time interval, node list, MAC list, target MAC, key list>

The target, initiator, time interval, node list, and MAC list fields are set to the corre-
sponding values from the RREQ, the target MAC is set to a MAC computed on the pre-
ceding fields in the reply with the key KDS , and the key list is initialized to the empty
list. The RREP is then returned to the initiator of the request along the source route ob-
tained by reversing the sequence of hops in the node list of the request.
A node forwarding a RREP waits until it is able to disclose its key from the time inter-
val specified, then it appends its key from that time interval to the key list field in the re-
ply and forwards the packet according to the source route indicated in the packet. Waiting
delays the return of the RREP but does not consume extra computational power.
When the initiator receives a RREP, it verifies that each key in the key list is valid, that
the target MAC is valid, and that each MAC in the MAC list is valid. If all of these tests
succeed, the node accepts the RREP; otherwise, it discards it.
In order to prevent the injection of invalid route errors into the network fabricated by
any node other than the one on the sending end of the link specified in the error message,
each node that encounters a broken link adds TESLA authentication information to the
route error message, such that all nodes on the return path can authenticate the error.
However, TESLA authentication is delayed, so all the nodes on the return path buffer the
error but do not consider it until it is authenticated. Later, the node that encountered the
broken link discloses the key and sends it over the return path, which enables nodes on
that path to authenticate the buffered error messages.
Ariadne is also protected from a flood of RREQ packets that could lead to a cache poi-
soning attack. Benign nodes can filter out forged or excessive RREQ packets using route

discovery chains, a mechanism for authenticating route discovery, allowing each node to
rate-limit discoveries initiated by any other node. The authors present two different ap-
proaches that can be found in [2].
ARIADNE is immune to the wormhole attack only in its advanced version: using the
TIK (TESLA with Instant Key disclosure) protocol that allows for very precise time syn-
chronization between the nodes of the network, it is possible to detect anomalies in rout-
ing traffic flows in the network. ARAN. The ARAN secure routing protocol proposed by Dahill, Levine, Roy-
er, and Shields [5] is conceived of as an on-demand routing protocol that detects and pro-
tects against malicious actions carried out by third parties and peers in the ad hoc environ-
ment. ARAN introduces authentication, message integrity, and nonrepudiation as part of
a minimal security policy for the ad hoc environment and consists of a preliminary certifi-
cation process, a mandatory end-to-end authentication stage, and an optional second stage
that provides secure shortest paths.
ARAN requires the use of a trusted certificate server (T): before entering the ad hoc
network, each node has to request a certificate signed by T. The certificate contains the IP
address of the node, its public key, a timestamp of when the certificate was created, and a
time at which the certificate expires, along with the signature by T. All nodes are supposed
to maintain fresh certificates with the trusted server and must know T™s public key.
The goal of the first stage of the ARAN protocol is for the source to verify that the in-
tended destination was reached. In this stage, the source trusts the destination to choose
the return path. A source node, A, initiates the route discovery process to reach the desti-
nation X by broadcasting to its neighbors a route discovery packet called RDP:

[RDP; IPX ; certA ; NA ; t]KA“

The RDP includes a packet type identifier (“RDP”), the IP address of the destination
(IPX), A™s certificate (certA), a nonce NA, and the current time t, all signed with A™s private
key. Each time A performs route discovery, it monotonically increases the nonce.
Each node records the neighbor from which it received the message. It then forwards
the message to each of its neighbors, signing the contents of the message. This signature
prevents spoofing attacks that may alter the route or form loops. Let A™s neighbor be B. It
will broadcast the following message:

[[RDP; IPX ; certA ; NA ; t]KA“ ]KB“; certB

Nodes do not forward messages for which they have already seen the (NA ; IPA) tuple.
The IP address of A is contained in the certificate, and the monotonically increasing
nonce facilitates easy storage of recently received nonces.
Upon receiving the broadcast, B™s neighbor C validates the signature with the given
certificate. C then rebroadcasts the RDP to its neighbors, first removing B™s signature:

[[RDP; IPX ; certA ; NA ; t]KA“ ]KC“ ; certC

Eventually, the message is received by the destination, X, which replies to the first
RDP that it receives for a source and a given nonce. There is no guarantee that the first
RDP received traveled along the shortest path from the source. The destination unicasts a

Reply (REP) packet back along the reverse path to the source. Let the first node that re-
ceives the RDP sent by X be node D. X will send to D the following message:

[REP; IPA ; certX ; NA ; t]KX“

The REP includes a packet-type identifier (“REP”), the IP address of A, the certificate
belonging to X, and the nonce and associated timestamp sent by A. Nodes that receive the
REP forward the packet back to the predecessor from which they received the original
RDP. All REPs are signed by the sender. Let D™s next hop to the source be node C. D will
send to C the following message:

[[REP; IPA ; certX ; NA ; t]KX“ ]KD“ ; certD

C validates D™s signature, removes the signature, and then signs the contents of the
message before unicasting the following RDP message to B:

[[REP; IPA ; certX ; NA ; t]KX“ ]KC“ ; certC

A node checks the signature of the previous hop as the REP is returned to the source.
This avoids attacks in which malicious nodes instantiate routes by impersonation and re-
play of X™s message. When the source receives the REP, it verifies that the correct nonce
was returned by the destination as well as the destination™s signature. Only the destination
can answer an RDP packet. Other nodes that already have paths to the destination cannot
reply for the destination. Although other protocols allow this networking optimization,
ARAN removes several possible exploits and cuts down on the reply traffic received by
the source by disabling this option.
The second stage of the ARAN protocol guarantees in a secure way that the path re-
ceived by a source initiating a route discovery process is the shortest. Similarly to the first
stage of the protocol, the source broadcasts a Shortest Path Confirmation (SPC) message
to its neighbors. The SPC message is different from the RDP message only in two addi-
tional fields that provide the destination X certificate and the encryption of the entire mes-
sage with X™s public key (which is a costly operation). The onion-like signing of messages
combined with the encryption of the data prevents nodes in the middle from changing the
path length because doing so would break the integrity of the SPC of the packet.
Also, the route maintenance phase of the ARAN protocol is secured by digitally sign-
ing the route error packets. However, it is extremely difficult to detect when error mes-
sages are fabricated for links that are truly active and not broken. Nevertheless, because
messages are signed, malicious nodes cannot generate error messages for other nodes.
The nonrepudiation provided by the signed error message allows a node to be verified as
the source of each error message that it sends.
As with any secure system based on cryptographic certificates, the key revocation is-
sue has to be addressed in order to make sure that expired or revoked certificates do not
allow the holder to access the network. In ARAN, when a certificate needs to be revoked,
the trusted certificate server T sends a broadcast message to the ad hoc group that an-
nounces the revocation. Any node receiving this message rebroadcasts it to its neighbors.
Revocation notices need to be stored until the revoked certificate would have expired nor-
mally. Any neighbor of the node with the revoked certificate needs to reform routing as
necessary to avoid transmission through the now untrusted node. This method is not fail-

safe. In some cases, the untrusted node that is having its certificate revoked may be the
sole connection between two parts of the ad hoc network. In this case, the untrusted node
may not forward the notice of revocation for its certificate, resulting in a partition of the
network, as nodes that have received the revocation notice will no longer forward mes-
sages through the untrusted node, whereas all other nodes depend on it to reach the rest of
the network. This only lasts as long as the untrusted node™s certificate would have other-
wise been valid, or until the untrusted node is no longer the sole connection between the
two partitions. At the time that the revoked certificate should have expired, the untrusted
node is unable to renew the certificate, and routing across that node ceases. Additionally,
to detect this situation and to hasten the propagation of revocation notices, when a node
meets a new neighbor, it can exchange a summary of its revocation notices with that
neighbor; if these summaries do not match, the actual signed notices can be forwarded
and rebroadcast to restart propagation of the notice.
The ARAN protocol protects against exploits using modification, fabrication, and im-
personation, but the use of asymmetric cryptography makes it a very costly protocol to
use in terms of CPU and energy usage. Furthermore, ARAN is not immune to the worm-
hole attack SEAD. Hu, Perrig, and Johnson developed a proactive secure routing proto-
col called SEAD [7], based on the Destination-Sequenced Distance Vector protocol
(DSDV). In a proactive (or periodic) routing protocol, nodes periodically exchange rout-
ing information with other nodes in attempt to have each node always know a current
route to all destinations. SEAD was inspired by the DSDV-SQ version of the DSDV proto-
col. The DSDV-SQ version of the DSDV protocol has been shown to outperform other
DSDV versions in previous ad hoc networks simulations [8, 9].
SEAD deals with attackers that modify routing information broadcast during the up-
date phase of the DSDV-SQ protocol; in particular, routing can be disrupted if the attack-
er modifies the sequence number and the metric field of a routing table update message.
Replay attacks are also taken into account.
In order to secure the DSDV-SQ routing protocol, SEAD makes use of efficient one-
way hash chains rather than relying on expensive asymmetric cryptography operations.
However, like the other secure protocols presented in this chapter, SEAD assumes some
mechanism for a node to distribute an authentic element of the hash chain that can be used
to authenticate all the other elements of the chain. As a traditional approach, the authors
suggest to ensure the key distribution by relying on a trusted entity that signs public key
certificates for each node; each node can then use its public key to sign a hash chain ele-
ment and distribute it.
The basic idea of SEAD is to authenticate the sequence number and metric of a routing
table update message using hash chains elements. In addition, the receiver of SEAD rout-
ing information also authenticates the sender, ensuring that the routing information origi-
nates form the correct node.
To create a one-way hash chain, a node chooses a random initial value x {0,1} ,
where is the length in bits of the output of the hash function, and computes the list of
values h0, h1, h2, h3, . . . , hn, where h0 = x, and hi = H(hi“1) for 0 < i n, for some n. As an
example, given an authenticated hi value, a node can authenticate hi“3 by computing
H(H(H(hi“3))) and verifying that the resulting value equals hi.
Each node uses a specific authentic (i.e., signed) element from its hash chain in each
routing update that it sends about itself (metric 0). Based on this initial element, the one-

way hash chain provides authentication for the lower bound on the metric in other routing
updates for that node. The use of a hash value corresponding to the sequence number and
metric in a routing update entry prevents any node from advertising a route to some desti-
nation claiming a higher sequence number than that destination™s own current sequence
number. Likewise, a node cannot advertise a route better than those for which it has re-
ceived an advertisement, since the metric in an existing route cannot be decreased due to
the one-way nature of the hash chain.
When a node receives a routing update, it checks the authenticity of the information for
each entry in the update using the destination address, the sequence number, and the met-
ric of the received entry, together with the latest prior authentic hash value received from
that destination™s hash chain. Hashing the received elements the correct number of times


. 64
( 87 .)