CHAPTER 11
Wireless Network Security
With the rapid development of technology in wireless communication and microchips, wireless technology has been widely used in various application areas. The proliferation of wireless devices and wireless networks in the past decade shows the widespread use of wireless technology.
Wireless networks is a general term to refer to various types of networks that communicate without the need of wire lines. Wireless networks can be broadly categorized into two classes based on the structures of the networks: wireless ad hoc networks and cellular networks. The main difference between these two is whether a fixed infrastructure is present.
Three of the well-known cellular networks are the GSM network, the CDMA network, and the 802.11 wireless LAN. The GSM network and the CDMA network are the main network technologies that support modern mobile communication, with most of the mobile phones and mobile networks that are built based on these two wireless networking technologies and their variants. As cellular networks require fixed infrastructures to support the communication between mobile nodes, deployment of the fixed infrastructures is essential. Further, cellular networks require serious and careful topology design of the fixed infrastructures before deployment, because the network topologies of the fixed infrastructures are mostly static and will have a great impact on network performance and network coverage.
Wireless ad hoc networks do not require a fixed infrastructure; thus it is relatively easy to set up and deploy a wireless ad hoc network (see Figure 11.1). Without the fixed infrastructure, the topology of a wireless ad hoc network is dynamic and changes frequently. It is not realistic to assume a static or a specific topology for a wireless ad hoc network. On the other hand, wireless ad hoc networks need to be self-organizing; thus mobile nodes in a wireless ad hoc network can adapt to the change of topology and establish cooperation with other nodes at runtime.
Figure 11.1: Classification of wireless networks.
Besides the conventional wireless ad hoc networks, there are two special types that should be mentioned: wireless sensor networks and wireless mesh networks. Wireless sensor networks are wireless ad hoc networks, most of the network nodes of which are sensors that monitor a target scene. The wireless sensors are mostly deprived devices in terms of computation power, power supply, bandwidth, and other computation resources. Wireless mesh networks are wireless networks with either a full mesh topology or a partial mesh topology in which some or all nodes are directly connected to all other nodes. The redundancy in connectivity of wireless networks provides great reliability and excellent flexibility in network packet delivery.
1. Cellular Networks
Cellular networks require fixed infrastructures to work (see Figure 11.2). A cellular network comprises a fixed infrastructure and a number of mobile nodes. Mobile nodes connect to the fixed infrastructure through wireless links. They may move around from within the range of one base station to outside the range of the base station, and they can move into the ranges of other base stations. The fixed infrastructure is stationary, or mostly stationary, including base stations, links between base stations, and possibly other conventional network devices such as routers. The links between base stations can be either wired or wireless. The links should be more substantial than those links between base stations and mobile nodes in terms of reliability, transmission range, bandwidth, and so on.
Figure 11.2: Cellular networking.
The fixed infrastructure serves as the backbone of a cellular network, providing high speed and stable connection for the whole network, compared to the connectivity between a base station and a mobile node. In most cases, mobile nodes do not communicate with each other directly without going through a base station. A packet from a source mobile node to a destination mobile node is likely to be first transmitted to the base station to which the source mobile node is connected. The packet is then relayed within the fixed infrastructures until reaching the destination base station to which the destination mobile node is connected. The destination base station can then deliver the packet to the destination mobile node to complete the packet delivery.
Cellular Telephone Networks
Cellular telephone networks offer mobile communication for most of us. With a cellular telephone network, base stations are distributed over a region, with each base station covering a small area. Each part of the small area is called a cell. Cell phones within a cell connect to the base station of the cell for communication. When a cell phone moves from one cell to another, its connection will also be migrated from one base station to a new base station. The new base station is the base station of the cell into which the cell phone just moved.
Two of the technologies are the mainstream for cellular telephone networks: the global system for mobile communication (GSM) and code division multiple access (CDMA).
GSM is a wireless cellular network technology for mobile communication that has been widely deployed in most parts of the world. Each GSM mobile phone uses a pair of frequency channels, with one channel for sending data and another for receiving data. Time division multiplexing (TDM) is used to share frequency pairs by multiple mobiles.
CDMA is a technology developed by a company named Qualcomm and has been accepted as an international standard. CDMA assumes that multiple signals add linearly, instead of assuming that colliding frames are completely garbled and of no value. With coding theory and the new assumption, CDMA allows each mobile to transmit over the entire frequency spectrum at all times. The core algorithm of CDMA is how to extract data of interest from the mixed data.
802.11 Wireless LANs
Wireless LANs are specified by the IEEE 802.11 series standard [1], which describes various technologies and protocols for wireless LANs to achieve different targets, allowing the maximum bit rate from 2 Mbits per second to 248 Mbits per second.
Wireless LANs can work in either access point (AP) mode or ad hoc mode, as shown in Figure 11.3. When a wireless LAN is working in AP mode, all communication passes through a base station, called an access point. The access point then passes the communication data to the destination node, if it is connected to the access point, or forwards the communication data to a router for further routing and relaying. When working in ad hoc mode, wireless LANs work in the absence of base stations. Nodes directly communicate with other nodes within their transmission range, without depending on a base station.
One of the complications that 802.11 wireless LANs incur is medium access control in the data link layer. Medium access control in 802.11 wireless LANs can be either distributed or centralized control by a base station. The distributed medium access control relies on the Carrier Sense Multiple Access (CSMA) with Collision Avoidance (CSMA/CA) protocol. CSMA/CA allows network nodes to compete to transmit data when a channel is idle and uses the Ethernet binary exponential backoff algorithm to decide a waiting time before retransmission when a collision occurs. CSMA/CA can also operate based on MACAW (Multiple Access with Collision Avoidance for Wireless) using virtual channel sensing. Request packets and clear-to-send (CTS) packets are broadcast before data transmission by the sender and the receiver, respectively. All stations within the range of the sender or the receiver will keep silent in the course of data transmission to avoid interference on the transmission.
The centralized medium access control is implemented by having the base station broadcast a beacon frame periodically and poll nodes to check whether they have data to send. The base station serves as a central control over the allocation of the bandwidth. It allocates bandwidth according to the polling results. All nodes connected to the base station must behave in accordance with the allocation decision made by the base station. With the centralized medium access control, it is possible to provide quality-of-service guarantees because the base station can control on the allocation of bandwidth to a specific node to meet the quality requirements.
Figure 11.3: (a) A wireless network in AP mode; (b) a wireless network in ad hoc mode.
2. Wireless Ad Hoc Networks
Wireless ad hoc networks are distributed networks that work without fixed infrastructures and in which each network node is willing to forward network packets for other network nodes. The main characteristics of wireless ad hoc networks are as follows.
• Wireless ad hoc networks are distributed networks that do not require fixed infrastructures to work. Network nodes in a wireless ad hoc network can be randomly deployed to form the wireless ad hoc network.
• Network nodes will forward network packets for other network nodes. Network nodes in a wireless ad hoc network directly communicate with other nodes within their ranges. When these networks communicate with network nodes outside their ranges, network packets will be forwarded by the nearby network nodes and other nodes that are on the path from the source nodes to the destination nodes.
• Wireless ad hoc networks are self-organizing. Without fixed infrastructures and central administration, wireless ad hoc networks must be capable of establishing cooperation between nodes on their own. Network nodes must also be able to adapt to changes in the network, such as the network topology.
• Wireless ad hoc networks have dynamic network topologies. Network nodes of a wireless ad hoc network connect to other network nodes through wireless links. The network nodes are mostly mobile. The topology of a wireless ad hoc network can change from time to time, since network nodes move around from within the range to the outside, and new network nodes may join the network, just as existing network nodes may leave the network.
Wireless Sensor Networks
A wireless sensor network is an ad hoc network mainly comprising sensor nodes, which are normally used to monitor and observe a phenomenon or a scene. The sensor nodes are physically deployed within or close to the phenomenon or the scene. The collected data will be sent back to a base station from time to time through routes dynamically discovered and formed by sensor nodes.
Sensors in wireless sensor networks are normally small network nodes with very limited computation power, limited communication capacity, and limited power supply. Thus a sensor may perform only simple computation and can communicate with sensors and other nodes within a short range. The life spans of sensors are also limited by the power supply.
Wireless sensor networks can be self-organizing, since sensors can be randomly deployed in some inaccessible areas. The randomly deployed sensors can cooperate with other sensors within their range to implement the task of monitoring or observing the target scene or the target phenomenon and to communicate with the base station that collects data from all sensor nodes. The cooperation might involve finding a route to transmit data to a specific destination, relaying data from one neighbor to another neighbor when the two neighbors are not within reach of each other, and so on.
Mesh Networks
One of the emerging technologies of wireless network is wireless mesh networks (WMNs). Nodes in a WMN include mesh routers and mesh clients. Each node in a WMN works as a router as well as a host. When it’s a router, each node needs to perform routing and to forward packets for other nodes when necessary, such as when two nodes are not within direct reach of each other and when a route to a specific destination for packet delivery is required to be discovered.
Mesh routers may be equipped with multiple wireless interfaces, built on either the same or different wireless technologies, and are capable of bridging different networks. Mesh routers can also be classified as access mesh routers, backbone mesh routers, or gateway mesh routers. Access mesh routers provide mesh clients with access to mesh networks; backbone mesh routers form the backbone of a mesh network; and a gateway mesh router connects the backbone to an external network.
Each mesh client normally has only one network interface that provides network connectivity with other nodes. Mesh clients are not usually capable of bridging different networks, which is different from mesh routers.
Similar to other ad hoc networks, a wireless mesh network can be self-organizing. Thus nodes can establish and maintain connectivity with other nodes automatically, without human intervention. Wireless mesh networks can divided into backbone mesh networks and access mesh networks.
3. Security Protocols
Wired Equivalent Privacy (WEP) was defined by the IEEE 802.11 standard [2]. WEP is designed to protect linkage-level data for wireless transmission by providing confidentiality, access control, and data integrity, to provide secure communication between a mobile device and an access point in a 802.11 wireless LAN.
Wired Equivalent Privacy
Implemented based on shared key secrets and the RC4 stream cipher [3], WEP’s encryption of a frame includes two operations (see Figure 11. 4). It first produces a checksum of the data, and then it encrypts the plaintext and the checksum using RC4:
• Checksumming. Let c be an integrity checksum function. For a given message M, a checksum c(M) is calculated and then concatenated to the end of M, obtaining a plaintext P = <M, c(M)>. Note that the checksum c(M) does not depend on the shared key.
• Encryption. The shared key k is concatenated to the end of the initialization vector (IV) v, forming <v,k> . <v,k> is then used as the input to the RC4 algorithm to generate a keystream RC4(v,k). The plaintext P is exclusive-or’ed (XOR, denoted by ⊕) with the keystream to obtain the ciphertext: C = P ⊕ RC4(v,k).
Using the shared key k and the IV v, WEP can greatly simplify the complexity of key distribution because it needs only to distribute k and v but can achieve a relatively very long key sequence. IV changes from time to time, which will force the RC4 algorithm to produce a new key sequence, avoiding the situation where the same key sequence is used to encrypt a large amount of data, which potentially leads to several types of attacks [4, 5].
Figure 11.4: WEP encryption and decryption.
WEP combines the shared key k and the IV v as inputs to seed the RC4 function. 802.11B [6] specifies that the seed shall be 64 bits long, with 24 bits from the IV v and 40 bits from the shared key k. Bits 0 through 23 of the seed contain bits 0 through 23 of the IV v, and bits 24 through 63 of the seed contain bits 0 through 39 of the shared key k.
When a receiver receives the ciphertext C, it will XOR the ciphertext C with the corresponding keystream to produce the plaintext M′ as follows.
WPA and WPA2
Wi-Fi Protected Access (WPA) is specified by the IEEE 802.11i standard, which is aimed at providing stronger security compared to WEP and is expected to tackle most of the weakness found in WEP [7–9].
WPA
WPA has been designed to target both enterprise and consumers. Enterprise deployment of WPA is required to be used with IEEE 802.1x authentication, which is responsible for distributing different keys to each user. Personal deployment of WPA adopts a simpler mechanism, which allows all stations to use the same key. This mechanism is called the Pre-Shared Key (PSK) mode.
The WPA protocol works in a similar way to WEP. WPA mandates the use of the RC4 stream cipher with a 128-bit key and a 48-bit initialization vector (IV), compared with the 40-bit key and the 24-bit IV in WEP.
WPA also has a few other improvements over WEP, including the Temporal Key Integrity Protocol (TKIP) and the Message Integrity Code (MIC). With TKIP, WPA will dynamically change keys used by the system periodically. With the much larger IV and the dynamically changing key, the stream cipher RC4 is able to produce a much longer keystream. The longer keystream improved WPA’s protection against the well-known key recovery attacks on WEP, since finding two packets encrypted using the same key sequences is literally impossible due to the extremely long keystream.
With MIC, WPA uses an algorithm named Michael to produce an authentication code for each message, which is termed the message integrity code. The message integrity code also contains a frame counter to provide protection over replay attacks.
WPA uses the Extensible Authentication Protocol (EAP) framework [10] to conduct authentication. When a user (supplicant) tries to connect to a network, an authenticator will send a request to the user asking the user to authenticate herself using a specific type of authentication mechanism. The user will respond with corresponding authentication information. The authenticator relies on an authentication server to make the decision regarding the user’s authentication.
WPA2
WPA2 is not much different from WPA. Though TKIP is required in WPA, Advanced Encryption Standard (AES) is optional. This is aimed to provide backward compatibility for WPA over hardware designed for WEP, as TKIP can be implemented on the same hardware as those for WEP, but AES cannot be implemented on this hardware. TKIP and AES are both mandatory in WPA2 to provide a higher level of protection over wireless connections. AES is a block cipher, which can only be applied to a fixed length of data block. AES accepts key sizes of 128 bits, 196 bits, and 256 bits.
Besides the mandatory requirement of supporting AES, WPA2 also introduces supports for fast roaming of wireless clients migrating between wireless access points. First, WPA2 allows the caching of a Pair-wise Master Key (PMK), which is the key used for a session between an access point and a wireless client; thus a wireless client can reconnect a recently connected access point without having to reauthenticate. Second, WPA2 enables a wireless client to authenticate itself to a wireless access point that it is moving to while the wireless client maintains its connection to the existing access point. This reduces the time needed for roaming clients to move from one access point to another, and it is especially useful for timing-sensitive applications.
SPINS: Security Protocols for Sensor Networks
Sensor nodes in sensor networks are normally low-end devices with very limited resources, such as memory, computation power, battery, and network bandwidth.
Perrig et al. [11] proposed a family of security protocols named SPINS, which were specially designed for low-end devices with severely limited resources, such as sensor nodes in sensor networks. SPINS consists of two building blocks: Secure Network Encryption Protocol (SNEP) and the “micro” version of the Timed, Efficient, Streaming, Loss-tolerant Authentication Protocol (μTESLA). SNEP uses symmetry encryption to provide data confidentiality, two-party data authentication, and data freshness. μTESLA provides authentication over broadcast streams. SPINS assumes that each sensor node shares a master key with the base station. The master key serves as the base of trust and is used to derive all other keys.
SNEP
As illustrated in Figure 11. 5, SNEP uses a block cipher to provide data confidentiality and message authentication code (MAC) to provide authentication. SNEP assumes a shared counter C between the sender and the receiver and two keys, the encryption key Kencr and the authentication key Kmac·
Figure 11.5: Sensor Network Encryption Protocol (SNEP).
For an outgoing message D, SNEP processes it as follows:
• The message D is first encrypted using a block cipher in counter mode with the key Kencr and the counter C, forming the encrypted text E = {D}<Kencr,C>.
• A message authentication code is produced for the encrypted text E with the key Kmac and the counter C, forming the MAC M = MAC(Kmac,C|E) where MAC() is a one-way function and C|E stands for the concatenation of C and E.
• SNEP increments the counter C.
To send the message D to the recipient, SNEP actually sends out E and M. In other words, SNEP encrypts D to E using the shared key Kencr between the sender and the receiver to prevent unauthorized disclosure of the data, and it uses the shared key Kmac, known only to the sender and the receiver, to provide message authentication. Thus data confidentiality and message authentication can both be implemented.
The message D is encrypted with the counter C, which will be different in each message. The same message D will be encrypted differently even it is sent multiple times. Thus semantic security is implemented in SNEP. The MAC is also produced using the counter C; thus it enables SNEP to prevent replying to old messages.
μTESLA
μTESLA [12–14] was proposed to provide message authentication for multicast. TESLA does not use any asymmetry cryptography, which makes it lightweight in terms of computation and overhead of bandwidth.
μTESLA is a modified version of TESLA, aiming to provide message authentication for multicasting in sensor networks. The general idea of μTESLA is that the sender splits the sending time into intervals. Packets sent out in different intervals are authenticated with different keys. Keys to authenticate packets will be disclosed after a short delay, when the keys are no longer used to send out messages. Thus packets can be authenticated when the authentication keys have been disclosed. Packets will not be tampered with while they are in transit since the keys have not been disclosed yet. The disclosed authentication keys can be verified using previous known keys to prevent malicious nodes from forging authentication keys.
μTESLA has four phases: sender setup, sending authenticated packets, bootstrapping new receivers, and authenticating packets. In the sender setup phase, a sender generates a chain of keys, Ki (0 ≤ i ≤ n). The keychain is a one-way chain such that Ki can be derived from Kj if i ≤ j, such as a keychain Ki (i = 0, ... , n), Ki = F(Ki+1), where F is a one-way function. The sender also decides on the starting time T0, the interval duration Tint, and the disclosure delay d (unit is interval), as shown in Figure 11.6.
To send out authenticated packets, the sender attaches a MAC with each packet, where the MAC is produced using a key from the keychain and the data in the network packet. μTESLA has specific requirements on the use of keys for producing MACs. Keys are used in the same order as the key sequence of the keychain. Each of the keys is used in one interval only. For the interval Ti = T0 + i × Tint, the key Ki is used to produce the MACs for the messages sent out in the interval Ti. Keys are disclosed with a fixed delay d such that the key Ki used in interval Ti will be disclosed in the interval Ti+d. The sequence of key usage and the sequence of key disclosure are demonstrated in Figure 11.6.
To bootstrap a new receiver, the sender needs to synchronize the time with the receiver and needs to inform the new receiver of a key Kj that is used in a past interval Tj, the interval duration Tint, and the disclosure delay d. With a previous key Kj, the receiver will be able to verify any key Kp where j ≤ p using the one-way keychain’s property. After this, the new receiver will be able to receive and verify data in the same way as other receivers that join the communication prior to the new receiver.
To receive and authenticate messages, a receiver will check all incoming messages if they have been delayed for more than d. Messages with a delay greater than d will be discarded, since they are suspect as fake messages constructed after the key has been disclosed. The receiver will buffer the remaining messages for at least d intervals until the corresponding keys are disclosed. When a key Ki is disclosed at the moment Ti + d, the receiver will verify Ki using Ki-1 by checking if Ki-1 = F(Ki). Once the key Ki is verified, Ki will be used to authenticate those messages sent in the interval Ti.
Figure 11.6: Sequences of intervals, key usages, and key disclosure.
4. Secure Routing
Secure Efficient Ad hoc Distance (SEAD) [15] vector routing is designed based on Destination-Sequenced Distance Vector (DSDV) routing [16]. SEAD augments DSDV with authentication to provide security in the construction and exchange of routing information.
SEAD
Distance vector routing works as follows. Each router maintains a routing table. Each entry of the table contains a specific destination, a metric (the shortest distance to the destination), and the next hop on the shortest path from the current router to the destination. For a packet that needs to be sent to a certain destination, the router will look up the destination from the routing table to get the matching entry. Then the packet is sent to the next hop specified in the entry.
To allow routers to automatically discover new routes and maintain their routing tables, routers exchange routing information periodically. Each router advises its neighbors of its own routing information by broadcasting its routing table to all its neighbors. Each router will update its routing table according to the information it hears from its neighbors. If a new destination is found from the information advertised by a neighbor, a new entry is added to the routing table with the metric recalculated based on the advertised metric and the linking between the router and the neighbor. If an existing destination is found, the corresponding entry is updated only when a new path that is shorter than the original one has been found. In this case, the metric and the next hop for the specified destination are modified based on the advertised information.
Though distance vector routing is simple and effective, it suffers from possible routing loops, also known as the counting to infinity problem. DSDV [17] is one of the extensions to distance vector routing to tackle this issue. DSDV augments each routing update with a sequence number, which can be used to identify the sequence of routing updates, preventing routing updates being applied in an out-of-order manner. Newer routing updates are advised with sequence numbers greater than those of the previous routing updates. In each routing update, the sequence number will be incremented to the next even number. Only when a broken link has been detected will the router use the next odd sequence number as the sequence number for the new routing update that is to be advertised to all its neighbors. Each router maintains an even sequence number to identify the sequence of every routing update. Neighbors will only accept newer routing updates by discarding routing updates with sequence numbers less than the last sequence number heard from the router.
SEAD provides authentication on metrics’ lower bounds and senders’ identities by using the one-way hash chain. Let H be a hash function and x be a given value. A list of values is computed as follows:
h0, h1, h2, ..., hn
where h0 = x and hi+1 = H(hi) for 0 ≤ i ≤ n. Given any value hk that has been confirmed to be in the list, to authenticate if a given value d is on the list or not one can compute if d can be derived from hk by applying H a certain number of times, or if hk can be derived from d by applying H to d a certain number of times. If either d can be derived from hk or hk can be derived from d within a certain number of steps, it is said that d can be authenticated by hk.
SEAD assumes an upper bound m – 1 on the diameter of the ad hoc network, which means that the metric of a routing entry will be less than m. Let h0, h1, h2, ..., hn be a hash chain where n = m × k and k Є Z+.
For an update with the sequence number i and the metric value of j, the value, h(k−i)m+j is used to authenticate the routing update entry.
By using h(k−i)m+j to authenticate the routing update entry, a node is actually disclosing the value h(k−i)m+j and subsequently all hp where p ≥ (k – i)m + j, but not any value hq where q ≤ (k – i)m + j.
Using a hash value corresponding to the sequence number and metric in a routing update entry allows the authentication of the update and prevents any node from advertising a route to some destination, forging a greater sequence number or a smaller metric.
To authenticate the update, a node can use any given earlier authentic hash value hp from the same hash chain to authenticate the current update with sequence number i and metric j. The current update uses the hash value h(k−i)m+j and (k – i)m + j ≥ p, thus hp can be computed from h(k−i)m+j by applying H for (k – i)m + j – p times.
The disclosure of h(k−i)m+j does not disclose any value hq where q ≤ (k – i)m + j. Let a fake update be advised with a sequence number p and metric q, where p ≥ i and q ≤ j, or q ≤ j. The fake update will need to use the hash value h(k−p)m+q. If the sequence number p is greater than i or the metric q is less than j, (k – p)m + q < (k – i)m + j. This means that a hash value h(k−p)m+q that has not been disclosed is needed to authenticate the update. Since the value h(k−p)m+q has not been disclosed, the malicious node will not be able to have it to fake a routing update.
Ariadne
Ariadne [18] is a secure on-demand routing protocol for ad hoc networks. Ariadne is built on the Dynamic Source Routing protocol (DSR) [19].
Routing in Ariadne is divided into two stages: the route discovery stage and the route maintenance stage. In the route discovery stage, a source node in the ad hoc network tries to find a path to a specific destination node. The discovered path will be used by the source node as the path for all communication from the source node to the destination node until the discovered path becomes invalid. In the route maintenance stage, network nodes identify broken paths that have been found. A node sends a packet along a specified route to some destination. Each node on the route forwards the packet to the next node on the specified route and tries to confirm the delivery of the packet to the next node. If a node fails to receive an acknowledgment from the next node, it will signal the source node using a ROUTE ERROR packet that a broken link has been found. The source node and other nodes on the path can then be advised of the broken link.
The key security features Ariadne adds onto the route discovery and route maintenance are node authentication and data verification for the routing relation packets. Node authentication is the process of verifying the identifiers of nodes that are involved in Ariadne’s route discovery and route maintenance, to prevent forging routing packets. In route discovery, a node sends out a ROUTE REQUEST packet to perform a route discovery. When the ROUTE REQUEST packet reaches the destination node, the destination node verifies the originator identity before responding. Similarly, when the source node receives a ROUTE REPLY packet, which is a response to the ROUTE REQUEST packet, the source node will also authenticate the identity of the sender. The authentication of node identities can be of one of the three methods: TELSA, digital signatures, and Message Authentication Code (MAC).
Data verification is the process of verifying the integrity of the node list in route discovery for the prevention of adding and removing nodes from the node list in a ROUTE RQUEST. To build a full list of nodes for a route to a destination, each node will need to add itself into the node list in the ROUTE REQUEST when it forwards the ROUTE REQUEST to its neighbor. Data verification protects the node list by preventing unauthorized adding of nodes and unauthorized removal of nodes.
ARAN
Authenticated Routing for Ad hoc Networks (ARAN) [20] is a routing protocol for ad hoc networks with authentication enabled. It allows routing messages to be authenticated at each node between the source nodes and the destination nodes. The authentication that ARAN has implemented is based on cryptographic certificates.
ARAN requires a trusted certificate server, the public key of which is known to all valid nodes. Keys are assumed to have been established between the trusted certificate server and nodes. For each node to enter into a wireless ad hoc network, it needs to have a certificate issued by the trusted server. The certificate contains the IP address of the node, the public key of the node, a time stamp indicating the issue time of the certification, and the expiration time of the certificate. Because all nodes have the public key of the trusted server, a certificate can be verified by all nodes to check whether it is authentic. With an authentic certificate and the corresponding private key, the node that owns the certificate can authenticate itself using its private key.
To discover a route from a source node to the destination node, the source node sends out a route discovery packet (RDP) to all its neighbors. The RDP is signed by the source node’s private key and contains a nonce, a time stamp, and the source node’s certificate. The time stamp and the nonce work to prevent replay attacks and flooding of the RDP.
The RDP is then rebroadcast in the network until it reaches the destination. The RDP is rebroadcast with the signature and the certificate of the rebroadcaster. On receiving an RDP, each node will first verify the source’s signature and the previous node’s signature on the RDP.
On receiving an RDP, the destination sends back a reply packet (REP) along the reverse path to the source after validating the RDP. The REP contains the nonce specified in the RDP and the signature from the destination node.
The REP is unicast along the reverse path. Each node on the path will put its own certificate and its own signature on the RDP before forwarding it to the next node. Each node will also verify the signatures on the RDP. An REP is discarded if one or more invalid signatures are found on the REP.
When the source receives the REP, it will first verify the signatures and then the nonce in the REP. A valid REP indicates that a route has been discovered. The node list on a valid REP suggests an operational path from the source node to the destination node that is found.
As an on-demand protocol, nodes keep track of route status. If there has been no traffic for a route’s lifetime or a broken link has been detected, the route will be deactivated. Receiving data on an inactive route will force a node to signal an error state by using an error (ERR) message. The ERR message is signed by the node that produces it and will be forwarded to the source without modification. The ERR message contains a nonce and a time stamp to ensure that the ERR message is fresh.
SLSP
Secure Link State Routing Protocol (SLSP) [21] is a secure routing protocol for ad hoc network building based on link state protocols. SLSP assumes that each node has a public/private key pair and has the capability of signing and verifying digital signatures. Keys are bound with the Medium Access Code and the IP address, allowing neighbors within transmission range to uniquely verify nodes if public keys have been known prior to communication.
In SLSP, each node broadcasts its IP address and the MAC to its neighbor with its signature. Neighbors verify the signature and keep a record of the pairing IP address and the MAC. The Neighbor Lookup Protocol (NLP) of SLSP extracts and retains the MAC and IP address of each network frame received by a node. The extracted information is used to maintain the mapping of MACs and IP addresses.
Nodes using SLSP periodically send out link state updates (LSUs) to advise the state of their network links. LSU packets are limited to propagating within a zone of their origin node, which is specified by the maximum number of hops. To restrict the propagation of LSU packets, each LSU packet contains the zone radius and the hops traversed fields. Let the maximum hop be R; X, a random number; and H be a hash function. Zone–radius will be initialized to HR(X) and hops_traversed be initialized to H(X). Each LSU packet also contains a TTL field initialized as R – 1. If TTL < 0 or H(hops–traversed) = zone–radius, a node will not rebroadcast the LSU packet. Otherwise, the node will replace the hops–traversed field with H(hops–traversed) and decrease TTL by one. In this way, the hop count is authenticated. SLSP also uses signatures to protect LSU packets. Receiving nodes can verify the authenticity and the integrity of the received LSU packets, thus preventing forging or tampering with LSU packets.
5. Key Establishment
Because wireless communication is open and the signals are accessible by anyone within the vicinity, it is important for wireless networks to establish trust to guard the access to the networks. Key establishment builds relations between nodes using keys; thus security services, such as authentication, confidentiality, and integrity can be achieved for the communication between these nodes with the help of the established keys.
The dynamically changing topology of wireless networks, the lack of fixed infrastructure of wireless ad hoc and sensor networks, and the limited computation and energy resources of sensor networks have all added complication to the key establishment process in wireless networks.
Bootstrapping
Bootstrapping is the process by which nodes in a wireless network are made aware of the presence of others in the network. On bootstrapping, a node gets its identifying credentials that can be used in the network the node is trying to join. Upon completion of the bootstrapping, the wireless network should be ready to accept the node as a valid node to join the network.
To enter a network, a node needs to present its identifying credential to show its eligibility to access the network. This process is called preauthentication. Once the credentials are accepted, network security associations are established with other nodes.
These network security associations will serve as further proof of authorization in the network. Security associations can be of various forms, including symmetric keys, public key pairs, hash key chains, and so on. The security associations can be used to authenticate nodes. Security associations may expire after a certain period of time and can be revoked if necessary. For example, if a node is suspected of being compromised, its security association will be revoked to prevent the node accessing the network. The actual way of revocation depends on the form of the security associations.
Bootstrapping in Wireless ad hoc Networks
Wireless ad hoc networks bring new challenges to the bootstrapping process by their lack of a centralized security infrastructure. It is necessary to build a security infrastructure in the bootstrapping phase. The trust infrastructure should be able to accept nodes with valid credentials to enter the network but stop those nodes without valid credentials from joining the network and establish security association between nodes within the network.
To build such a trust infrastructure, we can use any one of the following three supports: prior knowledge, trusted third parties, or self-organizing capability. Prior knowledge is information that has been set on valid nodes in advance, such as predistributed secrets or preset shared keys. This information can be used to distinguish legitimate nodes from malicious ones. Only nodes with prior knowledge will be accepted to enter the network. For example, the predistributed secrets can be used to authenticate legitimate nodes, so the network can simply reject those nodes without the predistributed secrets so that they can’t enter the network.
Trusted third parties can also be used to support the establishment of the trust infrastructure. The trusted third party can be a Certificate Authority (CA), a base station of the wireless network, or any nodes that are designated to be trusted. If trusted third parties are used, all nodes must mutually agree to trust them and derive their trust on others from the trusted third parties. One of the issues with this method is that trusted third parties are required to be available for access by all nodes across the whole network, which is a very strong assumption for wireless networks as well as an impractical requirement.
It is desirable to have a self-organizing capability for building the trust infrastructure for wireless networks, taking into account the dynamically changing topology of wireless ad hoc networks. Implementing a self-organizing capability for building the trust infrastructure often requires an out-of-band authenticated communication channel or special hardware support, such as tamper-proof hardware tokens.
Bootstrapping in Wireless Sensor Networks
Bootstrapping nodes in wireless sensor networks is also challenging for the following reasons:
• Node capture. Sensor nodes are normally deployed in an area that is geographically close or inside the monitoring environment, which might not be a closed and confined area under guard. Thus sensor nodes are vulnerable to physical capture because it might be difficult to prevent physical access to the area.
• Node replication. Once a sensor node is compromised, it is possible for adversaries to replicate sensor nodes by using the secret acquired from the compromised node. In this case, adversaries can produce fake legitimate node that cannot be distinguished by the network.
• Scalability. A single-sensor network may comprise a large number of sensor nodes. The more nodes in a wireless sensor network, the more complicated it is for bootstrapping.
• Resource limitation. Sensor nodes normally have extremely limited computation power and memory as well as limited power supply and weak communication capability. This makes some of the deliberate algorithms and methods not applicable to wireless sensor networks. Only those algorithms that require a moderate amount of resources can be implemented in wireless sensor networks.
Bootstrapping a sensor node is achieved using an incremental communication output power level to discover neighbors nearby. The output power level is increased step by step from the minimum level to the maximum level, to send out a HELLO message. This will enable the sensor node to discover neighbors in the order of their distance from the sensor node, from the closest to the farthest away.
Key Management
Key management schemes can be classified according to the way keys are set up (see Figure 11.7). Either keys are managed based on the contribution from all participating nodes in the network or they are managed based on a central node in the network. Thus key management schemes can be divided into contributory key management schemes, in which all nodes work equally together to manage the keys, and distributed key management schemes, in which only one central node is responsible for key management [22].
Classification
The distributed key management scheme can be further divided into symmetric schemes and public key schemes. Symmetric key schemes are based on private key cryptography, whereby shared secrets are used to authenticate legitimate nodes and to provide secure communication between them. The underlying assumption is that the shared secrets are known only to legitimate nodes involved in the interaction. Thus proving the knowledge of the shared secrets is enough to authenticate legitimate nodes. Shared secrets are distributed via secure channels or out-of-band measures. Trust on a node is established if the node has knowledge of a shared secret.
Figure 11.7: Key management schemes.
Public key schemes are built on public key cryptography. Keys are constructed in pairs, with a private key and a public key in each pair. Private keys are kept secret by the owners. Public keys are distributed and used to authenticate nodes and to verify credentials. Keys are normally conveyed in certificates for distribution. Certificates are signed by trusted nodes for which the public keys have been known and validated. Trust on the certificates will be derived from the public keys that sign the certificates. Note that given gi (mod p) and gj (mod p), it is hard to compute gi * j (mod p) without the knowledge of i and j.
Contributory Schemes
Diffie–Hellman (D-H) [23] is a well-known algorithm for establishing shared secrets. The D-H algorithm’s strength depends on the discrete log problem: It is hard to calculate s if given the value gs (mod p), where p is a large prime number.
Diffie–Hellman Key Exchange
D-H was designed for establishing a shared secret between two parties, namely node A and node B. Each party agrees on a large prime number p and a generator g. A and B each choose a random value i and j, respectively. A and B are then exchanged with the public values gi (mod p) and gj (mod p). On the reception of gj (mod p) from B, A is then able to calculate the value gj × i (mod p). Similarly, B computes gi × j (mod p). Thus a shared secret, gi × j (mod p), has been set up between A and B.
ING
Ingemarsson, Tang, and Wong (ING) [24] extends the D-F key exchange to a group of n members, d1, ... , dn. All group members are organized in a ring, where each member has a left neighbor and a right neighbor. Node di has a right neighbor di−1 and a left neighbor di+1. Note that for node di, its right neighbor is di+1; for node di+1, its left neighbor is di. Same as the D-F algorithm, all members in an ING group assume a large prime number p and a generator g. Initially, node di will choose a random number ri. At the first round of key exchange, node di will compute gri (mod p) and send it to its left neighbor di+1. At the same time, node di also receives the public value gri-1 (mod p) from its right neighbor di-1. From the second round on, let q be the value that node di received in the previous round, node di will compute a new public value qdi (mod p). After n – 1 rounds, the node di would have received a public value, gk (mod p) where 
from its right neighbors. With the public value received at the n – 1th round, the node di can raise it to the power of ri to compute the value gl (mod p) where 
Hypercube and Octopus (H&O)
The Hypercube protocol [25] assumes that there are 2d nodes joining to establish a shared secret and all nodes are organized as a d-dimensional vector space GF(2)d Let b1, ..., bd be the basic of GF(2)d The hypercube protocol takes d rounds to complete:
• In the first round, every participant v ∈ 2 GF(2)d chooses a random number rv and conducts a D-H key exchange with another participant v + b1, with the random values rv and rv+b1, respectively.
• In the ith round, every participant v ∈ 2 GF(2)d performances a D-H key exchange with the participant v + bi, where both v and v + bi use the value generated in the previous round as the random number for D-H key exchange.
This algorithm can be explained using a complete binary tree to make it more comprehensible. All the nodes are put in a complete binary tree as leaves, with leaves at the 0–level and the root at the d-level. D-H key exchanges are performed from the leaves up to the root. The key exchange takes d rounds:
• In the first round, each leaf chooses a random number k and performs a D-H key exchange with its sibling leaf, which has a random number j, and the resulting value gk × j (mod p) is saved as the random value for the parent node of the above two leaves.
• In the ith round, each node at the i – 1 level performs a D-H key exchange with its sibling node using the random numbers m and n, respectively, that they received in the previous round. The resulting value gm × n (mod p) is saved as the random value for the parent node of the above two nodes.
After d rounds, the root of the complete binary tree contains the established shared secret s.
The hypercube protocol assumes that there are 2d network nodes. The octopus protocol removes the assumption and extends the hypercube protocol to work with an arbitrary number of nodes. Thus the octopus protocol can be used to establish a shared key for a node set containing an arbitrary number of nodes.
Distributed Schemes
A partially distributed threshold CA scheme [26] works with a normal PKI system where a CA exists. The private key of the CA is split and distributed over a set of n server nodes using a (k,n) secret-sharing scheme [27]. The (k,n) secret-sharing scheme allows any k or more server nodes within the n server nodes to work together to reveal the CA’s private key. Any set of nodes with fewer than k nodes will not be able to reveal the CA’s private key. With the threshold signature scheme [28], any k of the n nodes can cooperate to sign a certificate. Each of the k nodes produces a piece of the signature on the request of signing a given certificate. With all the k pieces of the signature, a valid signature, which is the same as the one produced using the CA’s private key, can be produced by combining the k pieces of the signature.
Partially Distributed Threshold CA Scheme
In this way, the partial distributed threshold CA scheme can avoid the bottleneck of the centralized CA of conventional PKI infrastructures. As long as there are at least k of the n nodes available, the network can always issue and sign new certificates. Attacks to any single node will not bring the whole CA down. Only when an attack manages to paralyze n – k or more nodes will the CA’s signing service not be available.
To further improve the security of the private key that is distributed over the n nodes, proactive security [29] can be imposed. Proactive security forces the private key shares to be refreshed periodically. Each refreshment will invalidate the previous share held by a node. Attacks on multiple nodes must complete within a refresh period to succeed. To be specific, only when an attack can compromise k or more nodes within a refresh period can the attack succeed.
While conventional PKI systems depend on directories to publish public key certificates, it is suggested that certificates should be disseminated to communication peers when establishing a communication channel with the partial distributed threshold CA scheme. This is due to the fact that the availability of centralized directories cannot be guaranteed in wireless networks. Therefore it is not realistic to assume the availability of a centralized directory.
Self-Organized Key Management (PGP-A)
A self-organized key management scheme (PGP-A) [30] has its basis in the Pretty Good Privacy (PGP) [31] scheme. PGP is built based on the “web of trust” model, in which all nodes have equal roles in playing a CA. Each node generates its own public/private key pair and signs other nodes’ public keys if it trusts the nodes. The signed certificates are kept by nodes in their own certificate repositories instead of being published by centralized directories in the X.509 PKI systems [32].
PGP-A treats trust as transitive, so trust can be derived from a trusted node’s trust on another node, that is, if node A trusts node B, and node B trusts node C, then A should also trust C if A knows the fact that node B trusts node C.
To verify a key of a node u, a node j will merge its certificate repository with those of j’s trusted nodes, and those of the nodes trusted by j’s trusted nodes, and so forth. In this way, node j can build up a web of trust in which node j is at the center of the web and j’s directly trusted nodes as node j’s neighbors. Node l is linked with node k if node k trusts node l. Node j can search the web of trust built as above to find a path from j to u. If such as path exists, let it be a sequence of nodes S: nodei where i = 1, ..., n, n be the length of the path, and node1 = j and noden = u. This means that nodei trust nodei+1 for all i = 1, ..., n 1. Therefore u can be trusted by j. The path S represents a verifiable chain of certificates. PGP-A does not guarantee that a node u that should be trusted by node j will always be trusted by node j, since there are chances that the node j fails to find a path from node j to node u in the web of trust. This might be due to the reason that node j has not acquired enough certificates from its trusted nodes to cover the path from node j to node u.
Self-healing Session Key Distribution
The preceding two key management schemes are public key management schemes. The one discussed here, a self-healing session key distribution [33], is a symmetric key management scheme. In such a scheme, keys can be distributed either by an online key distribution server or by key predistribution. A key predistribution scheme normally comprises the key predistribution phase, the shared-key discovery phase, and the path key establishment phase.
In the key predistribution phase, a key pool of a large number of keys is created. Every key can be identified by a unique key identifier. Each network node is given a set of keys from the key pool. The shared-key discovery phase begins when a node tries to communicate with the others. All nodes exchange their key identifiers to find out whether there are any keys shared with others. The shared keys can then be used to establish a secure channel for communication. If no shared key exists, a key path will need to be discovered. The key path is a sequence of nodes with which all adjacent nodes share a key. With the key path, a message can travel from the first node to the last node securely, by which a secure channel can be established between the first node and the last node.
The self-healing session key distribution (S-HEAL) [34] assumes the existence of a group manager and preshared secrets. Keys are distributed from the group manager to group members. Let h be a polynomial, where for a node i, node i knows about h(i). Let K be the group key to be distributed, K is covered by h in the distribution: f(x) = h(x) + K. The polynomial f(x) is the information that the group manager sends out to all its group members. For node j, node j will calculate K = f(j) h(j) to reveal the group key. Without the knowledge of h(j), node j will not be able to recover K.
To enable revocation in S-HEAL, the polynomial h(x) is replaced by a bivariate polynomial s(x,y). The group key is covered by the bivariate polynomial s(x,y) when it is distributed to group members, in the way that f(N,x) = s(N,x) + K. Node i must calculate s(N,i) to recover K. The revocation enabled S-HEAL tries to stop revoked nodes to calculate s(N,i), thus preventing them to recover K.
Let s of degree t; then t + 1 values are needed to compute s(x,i). Assuming that s(i,i) is predistributed to node i, node i will need another t values to recover s(N,i), namely s(r1,x), ..., s(rt,x). These values will be disseminating to group members together with the key update. If the group manager wants to revoke node i, the group manager can set one of the values s(r1,x), ..., s(rt,x) to s(i,x). In this case, node i obtains only t values instead of t + 1 values. Therefore, node i will not be able to compute s(x,i), thus it will not be able to recover K. This scheme can only revoke maximum t nodes at the same time.
References
[1] L. M. S. C. of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, technical report, IEEE Standard 802.11, 1999 ed., 1999.
[2] L. M. S. C. of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, technical report, IEEE Standard 802.11, 1999 ed., 1999.
[3] Rivest RL. The RC4 encryption algorithm, RSA Data Security, Inc., March 1992 technical report..
[4] Dawson E, Nielsen L. Automated cryptanalysis of XOR plaintext strings. Cryptologia 1996;20(2), April.
[5] Singh S. The code book: the evolution of secrecy from Mary, Queen of Scots, to quantum cryptography. Doubleday, 1999.
[6] L. M. S. C. of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, technical report, IEEE Standard 802.11, 1999 ed.; 1999.
[7] Arbaugh WA. An inductive chosen plaintext attack against WEP/WEP2, IEEE Document 802.11-01/230, May 2001.
[8] Walker JR. Unsafe at any key size; an analysis of the WEP encapsulation, IEEE Document 802.11-00/362, October 2000.
[9] Borisov N, Goldberg I, Wagner D. Intercepting Mobile Communications: The Insecurity of 802.11, MobiCom, 2001.
[10] Aboba B, Blunk L, Vollbrecht J, Carlson J, Levkowetz EH. Extensible Authentication Protocol (EAP), request for comment. Network Working Group; 2004.
[11] Perrig A, Szewczyk R, Wen V, Culler D, Tygar JD. SPINS: Security protocols for sensor networks, MobiCom ’01: Proceedings of the 7th annual international conference on Mobile computing and networking, 2001.
[12] Perrig A, Canetti R, Xiaodong Song D, Tygar JD. Efficient and secure source authentication for multicast, NDSS 01: Network and Distributed System Security Symposium, 2001.
[13] Perrig A, Tygar JD, Song D, Canetti R. Efficient authentication and signing of multicast streams over lossy channels, SP ’00: Proceedings of the 2000 IEEE Symposium on Security and Privacy; 2000.
[14] Perrig A, Canetti R, Tygar JD, Song D. RSA CryptoBytes. 2002:5.
[15] Hu Y-C, Johnson DB, Perrig A. SEAD. Secure efficient distance vector routing for mobile wireless ad hoc networks. WMCSA ’02: Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, Washington, DC: IEEE Computer Society; 2002. p. 3.
[16] Perkins CE, Bhagwat P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. SIGCOMM Comput. Commun Rev 1994;24(4):234–44.
[17] Perkins CE, Bhagwat P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. SIGCOMM Comput. Commun Rev 1994;24(4):234–44.
[18] Hu Y-C, Perrig A, Johnson D. Ariadne: a secure on-demand routing protocol for ad hoc networks. Wireless Networks Journal 2005;11(1).
[19] Johnson DB, Maltz DA. Dynamic source routing in ad hoc wireless networks. Mobile Computing. Kluwer Academic Publishers; 1996. p. 153–81.
[20] Sanzgiri K, Dahill B, Levine BN, Shields C, Belding-Royer EM. A secure routing protocol for ad hoc networks. 10th IEEE International Conference on Network Protocols (ICNP’02), 2002.
[21] Papadimitratos P, Haas ZJ. Secure link state routing for mobile ad hoc networks. saint-w, 00, 2003.
[22] Cayirci E, Rong C. Security in wireless ad hoc, sensor, and mesh networks. John Wiley & Sons; 2008.
[23] Diffie W, Hellman ME. New directions in cryptography. IEEE Transactions on Information Theory 1976;IT-22(6):644–54.
[24] Ingemarsson I, Tang D, Wong C. A conference key distribution system. IEEE Transactions on Information Theory 1982;28(5):714–20, September.
[25] Becker K, Wille U. Communication complexity of group key distribution. ACM conference on computer and communications security 1998.
[26] Zhou L, Haas ZJ. Securing ad hoc networks. IEEE Network 1999;13:24–30.
[27] Shamir A. How to share a secret. Comm. ACM 1979;22(11).
[28] Desmedt Y. Some recent research aspects of threshold cryptography. ISW 1997;158–73.
[29] Canetti R, Gennaro A, Herzberg D. Naor, Proactive security: Long-term protection against break-ins. CryptoBytes 1997;3(1), Spring.
[30] Capkun S, Buttyán L, Hubaux J-P. Self-organized public-key management for mobile ad hoc networks. IEEE Trans Mob Comput 2003;2(1):52–64.
[31] Zimmermann P. The Official PGP User’s Guide. The MIT Press; 1995.
[32] ITU-T. Recommendation X.509, ISO/IEC 9594-8. Information Technology: Open Systems Interconnection– The Directory: Public-key and Attribute Certificate Frameworks. 4th ed. 2000, ITU.
[33] Staddon J, Miner SK, Franklin MK, Balfanz D, Malkin M, Dean D. Self-healing key distribution with revocation. IEEE Symposium on Security and Privacy 2002.
[34] Staddon J, Miner SK, Franklin MK, Balfanz D, Malkin M, Dean D. Self-healing key distribution with revocation. IEEE Symposium on Security and Privacy 2002.