Resource-Efficient Multi-Source Authentication Utilizing Split-Join One-Way Key Chain
Seonho Choi1, Kun Sun2 and Hyeonsang Eom3, 1Bowie State University, Bowie, MD, USA, 2George Mason University, Fairfax, VA, USA, 3Seoul National University, Seoul, Korea
In wireless ad hoc networks, most of the authentication protocols assume a single source of trust. However, in the presence of multiple trust sources (called source group in this chapter), it becomes difficult to design resource- (or energy-) efficient authentication protocols, especially for multicast/broadcast services, utilizing multiple trust sources at the same time. Some traditional authentication approaches may be extended and used for this purpose. However, the communication overhead, for example, may increase significantly in proportion to the number of trust sources.
In this chapter, we propose a new scheme named as Multi-Source Authentication with Split-Join One-Way Key Chain (SOKC). In this new technique, the communication overhead is small and constant, and the memory requirement at the verifier node is also minimal. The source group node needs to store n keys, where n represents the key chain length, which may be a reasonable requirement considering that the trust sources usually have more resources compared to other regular node(s) in the network (e.g., base stations in wireless sensor networks).
Keywords
authentication; security; multicast; protocol; wireless ad hoc networks
Information in this chapter
• Emerging Issues in Multi-source Authentication for Multicast and Broadcast
• Towards the resource-efficient Multi-source Multicast Authentication protocol
Introduction
In wireless ad hoc networks, most of the authentication protocols assume a single source of trust. For example, in a wireless sensor network (WSN), it is typically assumed there is one trustworthy base station and it is the only source of the trust. However, in the presence of multiple trust sources (called source group in this chapter), it becomes difficult to design resource- (or energy-) efficient authentication protocols utilizing multiple trust sources at the same time. Some traditional authentication approaches may be extended and used for this purpose. However, the communication overhead, for example, may increase significantly proportional to the number of trust sources. In this chapter, we propose a new scheme named Multi-Source Authentication utilizing Split-Join One-Way Key Chain (SOKC). In this new technique, the communication overhead is small and constant, and the memory requirement at the verifier node is also small. The source node needs to store n keys, where n represents the key chain length, which may be a reasonable requirement considering that the trust sources usually have more resources compared to other regular node(s) in the network (e.g., as in sensor network).
Our technique utilizes a delayed key disclosure mechanism as in TESLA and uTESLA approaches [1,2], and also extends the one-way key chain technique to achieve the goals of minimal communication overhead and minimal storage requirements at the verifier nodes.
Our SOKC scheme may be applied to both unicast and multicast/broadcast authentication services. But the application of our scheme would be simpler for unicast cases, and for most of the cases, broadcast authentication services are more important, since conveying the information from the trustworthy source to other nodes may be more critical compared to the communication between non-trustworthy nodes. For example, several routing protocols were proposed based on periodic broadcasting (e.g., flooding) of routing (or beacon) messages. These include TinyOS beaconing [3], directed diffusion and its multi-path variants [4], etc. Also, several location discovery schemes have been proposed that utilize broadcasting capabilities to estimate node locations [1]. Even though more advanced broadcast techniques may be utilized in the network, simple flooding may be preferred or required due to the simplicity or instability of network connections. Our proposed approach may be applied in both cases. Hence, we will focus on developing and applying the SOKC scheme for the multicast/broadcast services.
This SOKC scheme may be applied for various authentication problems. However, to show its applicability, we chose two authentication problems. For example, in wireless ad hoc networks, some attacks exploit the fact that it is hard to authenticate the actual path (or number of hops) data packets traversed—especially the attacks against the broadcast services. Sinkhole and wormhole attacks belong to this attack category [3]. With the multi-source authentication capabilities, each node would be able to detect and cope with such attacks. A new path authentication technique may be developed by utilizing our multi-source SOKC scheme. For example, the source group keys may be duplicated and randomly distributed across the network, so that the verifier nodes may be able check whether a packet has really passed through a certain number of source group nodes along the routing path from the claimed origination point.
The SOKC scheme may also be applied to WSNs with multiple base stations. It is typically assumed that a WSN has only one base station. However, there may exist several drawbacks. Degraded reliability may be a problem due to a single point of failure. The latency may be an issue if the number of hops in the delivery paths become large, which may cause the reduced lifetime of the sensor nodes and, thus, the entire sensor network. The deployment of multiple base stations were proposed to overcome these limitations [5–7]. However, in the presence of multiple base stations, it would be more difficult to provide robust authentication services since it would be required to tolerate compromise of multiple base stations as well as sensor nodes. If we assume that the base stations can communicate with each other directly using a separate channel, then our SOKC-based approach may be used in providing multi-source broadcast authentication services. It is also assumed that all the base stations need to participate in authenticating the broadcast messages to provide increased security levels. If we consider the importance of the broadcast messages in WSNs, this would be a valid assumption.
Related works
Several security mechanisms for authentication and secure routing protocols in a wireless ad hoc network are based on public key cryptography [8,9]. However, until now, the public key cryptography has still been too expensive for the resource-constrained mobile nodes. Secure routing protocols based on symmetric key cryptography have been proposed (e.g., [10,11]). SEAD [10] is a distance vector routing protocol based on DSDV. The basic idea is to use one-way hash chains to authenticate the metrics and the sequence number of a routing table. The destination node can authenticate the source node; however, it cannot authenticate the intermediate nodes along the path from the source node to the destination node. Ariadne [11] uses a per-hop hashing technique and source routing techniques to prevent route misbehaviors. However, it requires a precise time synchronization among all the nodes, which is usually difficult to achieve in the mobile networks. Moreover, the communication overhead may increase significantly when including all the identifiers and corresponding MACs for all the nodes along the path.
Authenticating broadcast (or multicast) traffic in wireless ad hoc networks is also a difficult problem, since the traditional approaches like digital signatures may not be adequate due to the heavy resource requirements. TESLA and μTESLA approaches [2,12] were proposed as viable solutions to the authentication problem in such networks. μTESLA utilizes the delayed key disclosure and one-way key chain techniques. First, the packet is broadcast with a calculated keyed Message Authentication Codes attached along with the original data portion, and only after sufficient time is elapsed for all the nodes in the network to receive it will the corresponding key be disclosed to the network nodes for authentication of the previously sent data and MAC. TESLA and μTESLA requires loose time synchronization among the network nodes.
Researchers have proposed several mechanisms to prevent the false data injection attacks. Przydatek, Song, and Perrig propose SIA [13], a secure information aggregation scheme for sensor networks that addresses the issue of false data injection using statistical techniques and interactive proofs, ensuring that the aggregated result reported by the aggregation node is a good approximation to the true value, even if a small number of sensor nodes and the aggregation node may have been compromised. SIA focuses on the accuracy of query results reported from the base station, whereas our scheme focuses on the authenticity of the reports from sensor nodes and provides a means to filter out any injected false data as early as possible. Both schemes can be combined to make the network more robust to false data injection attacks.
SEF [14] is a statistical en-route filtering mechanism to detect and drop false reports during the forwarding process. Authenticating event reports requires that nodes share certain security information; however, attackers can obtain such information by compromising a single node. To prevent any single compromised node from breaking down the entire system, SEF carefully limits the amount of security information assigned to each node and relies on the collective decisions of multiple sensors for false report detection. First, SEF divides a global key pool into multiple partitions and carefully assigns a certain number of keys from one partition to an individual node. Given that any single node knows only a limited amount of the system secret, compromising one or a small number of nodes cannot disable the overall network from detecting bogus reports. Second, by assuming that the same event can be detected by multiple sensors, in SEF each of the detecting sensors generates a keyed message authentication code (MAC) and multiple MACs are attached to the event report. As the report is forwarded, each node along the way verifies the correctness of the MACs probabilistically and drops those with invalid MACs. Finally, the sink verifies the correctness of each MAC and eliminates remaining false reports that elude en-route filtering. Compared to the statistical solution provided by SEF, our solution can provide a more resource-efficient path authentication, but it cannot handle the broadcast authentication.
Zhu et al. [15] present an interleaved hop-by-hop authentication scheme for addressing the false data injection attack launched by the compromised nodes. The scheme guarantees that the base station will detect any injected false data packets when no more than a certain number t nodes are compromised. To defend against false data injection attacks, at least t + 1 sensor nodes have to agree upon a report before it is sent to the base station. t is a security threshold based on the security requirements of the application under consideration and the network node density. Further, it provides an upper bound for the number of hops that a false data packet could be forwarded before it is detected and dropped, given that there are up to t colluding compromised nodes. In other words, it also attempts to filter out false data packets injected into the network by compromised nodes before they reach the base station, thus saving the energy for relaying them. Zhu et al. [15] offers the most similar work to our proposed scheme, but their approach cannot handle the broadcast authentication. Our solution approach utilizes a new SOKC technique, along with the delayed key disclosure, to achieve a much smaller communication overhead.
Methodology
Assumptions
We refer to the minimum number of hops necessary for a packet to reach from any node located at one extreme edge of the network to another node located at the opposite extreme, as the diameter of the ad hoc network. Packets may be lost or corrupted in transmission on the network. A node receiving a corrupted packet can detect the error and discard the packet. Nodes within the ad hoc network may move at any time without notice, and may even move continuously, but we assume that the speed with which nodes move is moderate with respect to the packet transmission latency and wireless transmission range of the particular underlying network hardware in use. We assume that nodes may be able to enable a promiscuous receive mode on their wireless network interface hardware, causing the hardware to deliver every received packet to the network driver software without filtering based on the link-layer destination address. Even though this feature is not required, by utilizing this feature, the performance of our scheme may be enhanced, especially when the mobility level is high in the network.
The local clocks of the nodes are assumed to be (at least) loosely synchronized, with a maximum time synchronization error Δ. Various time synchronization techniques were proposed for wireless ad hoc networks, and any of them may be utilized to achieve this requirement. Similar assumptions were made in the broadcast authentication schemes such as TESLA, µTESLA, etc. [2,12].
Also, the time line is assumed to be divided into block periods, as in TESLA and µTESLA approaches [2,12]. In each block period, one packet may be sent out for broadcasting by any valid broadcast originator (which may be determined by the application). A delayed key disclosure mechanism is adapted and incorporated in our scheme. Each broadcast packet contains the message, the authentication-related information, and the key information that is disclosed for the previously sent out message. The key disclosure delay is denoted as d block periods. These can be seen in Figure 17.1.
Figure 17.1 A µTESLA technique [2,12] is shown with a key disclosure delay of d=3 block periods. Note that keys are disclosed later, while the message and MAC portions are disclosed in the corresponding block.
We assume that there is one source and one or more recipients that are involved in each session (one or more data packets are delivered in each session). That is, our authentication approach may be used for both unicast and multicast/broadcast communications. However, we will focus on developing protocols for broadcast services, as mentioned before. The packets are transmitted along a multi-hop delivery path to the receiver(s). The delivery path is determined by a routing protocol used in the network. Many routing protocols were proposed for wireless ad hoc networks, and any of them with reasonable route change rates (due to mobility) may be utilized in the network.
Finally, it is assumed that the number of different source group keys in one source group (which is denoted as m) is an odd number.
Overview of the protocol
The protocol carries out the following three processes to provide the multi-source authentication. In this scheme it is assumed that the number of source group keys, m, is an odd number.
1. Offline SOKC generation (Figure 17.2): SOKC is generated offline by utilizing the source seed (Z0), source keys (ai), one-way hash operation, and the bitwise EXOR operation. Source nodes with a secret source key ai will be equipped with a chain of keys that are obtained from the intermediate keys, Yj (1≤j≤n−1), by applying the EXOR operation with ai. The keys generated in this process are denoted as 
.
The intermediate keys that are generated in this process are named as Yj and Zj, which will be explained in more detail in a later section.
2. Semi-encrypted key pre-distribution (Figure 17.3): When the original sender node (this may or may not be one of the source group nodes) has some message to send, it will first send a packet that has the following field:
• random nonce Rj of k bits. This would be used to prevent the disclosure of the next key (Yj) in the SOKC that is needed for the next round of validation.
Figure 17.2 SOKC generation: The entire key chain is generated offline and only the keys in the solid rectangles are stored in the nodes. The keys, 
, are stored in the i-th source node(s). Yn is bootstrapped in each verifier node. The intermediate keys and even the secret source keys, ai, are not stored in any node in the network.
Figure 17.3 Semi-encrypted key pre-distribution and a delayed key disclosure along with the verifications at verifier nodes.
Once this field is filled with a random number generated by the original source and the packet is sent out, the first source group node from ai (this may be the same as the original sender node) will apply EXOR operation with this random number to its next key in the SOKCi
its Message and forward the packet to the next node in the delivery path. The next source group nodes with different source keys will carry out the same process: get the value from this field and apply the EXOR operation to it. But this process is done only once for each source key aj, 1≤j≤m. In other words, if there are multiple source group nodes with the same source key in the delivery path, only the first one will carry out this process. When the packet finishes traversing all the source group nodes with m different source keys, then the verifier nodes in the remaining path will have the following value in the packet field:
Mj stands for the message in the j-th packet. This value will be stored in the verifier nodes for later authentication purposes. Verifiers may store the other field values, such as the actual message (Mj), depending upon the scheme.
3. Delayed key disclosure with verification (Figure 17.3): After the key disclosure delay (d block periods), the original sender of Rj will start the key disclosure process by including the following fields in the packet:
• Disclose the actual random nonce used d block period before (Rj)—the original sender will initialize this field to all 0s.
• Key disclosure field for accommodating the SOKCj keys from the m source group nodes (they will be EXORed and this field requires only k bits).
Each group source node will apply the EXOR operation between the next key in SOKCi and the value from the key disclosure field mentioned above, and store back the result into the key disclosure field again. After the packet traverses all of the m source group nodes with different source keys, the packet will contain the following value in its key disclosure field:
Once the packet reaches a verifier node, and if the packet is claimed to have traversed m different source group nodes, then the verifier node will carry out a sequence of steps. First, it will extract the intermediate key, Zj, from the key disclosure field, and check whether this intermediate key is really from the authentic SOKC by applying the one-way hash operation and comparing the result to the already stored Yj+1. If they don’t match, then the key disclosure packet is discarded, and the already stored message Mj will not be authenticated. If they match, then the verifier extracts the intermediate key, Yj, by multiplying 
to Zj, and stores it as Yj as a newly disclosed authentic SOKC key to be used in the next round of authentication.
Then the verifier will check the following condition to compare to the already stored Φj:
If the equality holds, then the previously (in TESLA) stored Rj and Mj are validated.
Basic scheme
Notations
The following are defined for our authentication process:
• Source group: A group of nodes equipped with SOKCs generated from m different source keys, ai where 1 ≤ i ≤m , are distributed among Nsrc number of source nodes (m ≤Nsrc). It is assumed that m is an odd number in this scheme. The source nodes may or may not be located in close proximity, and some source nodes may have the same source key if m<Nsrc. The source key size is denoted as k bits.
• Verifier group: Nvrf nodes (e.g., multicast group members or all the nodes in the broadcast case) are equipped with verification information for authenticating a packet’s traversing of at least m source nodes with different ai in the routing path. That is, a verifier node has the ability to verify that the packet passed through all the source group nodes with m different source keys.
Information kept in the source group node and the verifier group node is as follows:
SOKC Generation with m source keys, ai, 1≤i≤m (Figure 17.2)
The process of SOKC generation is assumed to be carried out offline before the network launch time. The possible issues that may arise in developing online SOKC generation is addressed in the proposed research section later. For the offline case, the detailed algorithm is shown in Figure 17.2 and the detailed steps are as follows:
1. Apply a cryptographic hash function to Z0 to generate Y1, which is also k-bit long.
3. Calculate a key QUOTE 
in the chain by applying the EXOR operation with a secret source key ai, 
.
.5. Apply a cryptographic hash function to Z1 to generate Y2. That is, Y2=H(Z1).
in the chain, 
.
.
is obtained.The one-way key chain at the source is now obtained as 
. The keys in this SOKCi are bootstrapped in the source group nodes. These keys are used in reverse order starting from 
. The last key, Yn, in the entire SOKC is assumed to be bootstrapped at each verifier node.
Packet format
The j-th packet, 1≤j<n, has the following packet format consisting of five fields:
disclosure; k bits
) disclosure; k bits
SRC index bits are used for showing which source group nodes the packet has been traversed. For example, if its i-th bit is set to 1, then it means that the packet is claiming that it has already traversed a node with the source key ai, and if its i-th bit is 0, then it means that the packet has not traversed any such node. If another source node with the same ai receives the packet whose i-th SRC index bit is set to 1, then it will forward the packet without modifying any of the fields, even though it can repeat the process without any adverse effect; but it will waste resource if it does.
The other three fields following the SRC index bits field will be used in the semi-encrypted key pre-distribution and the delayed key disclosure with verification processes. Note that the nonce disclosure and SOKC key disclosure fields will disclose the values that were previously used in the (j-d)-th block period.
After the key disclosure delay (i.e., d block periods), another packet needs to be sent by the original sender; it would contain the following fields:
) disclosure; k bitsSemi-encrypted key pre-distribution at the source node with a source key ai (1≤i≤m)
Again, the purpose of the semi-encrypted key pre-distribution is to let source group nodes reveal their SOKC keys in a semi-encrypted form by applying the EXOR operation to the random nonce (Rj) sent out by the original sender of the packet. Let’s assume that a j-th packet is sent out by the original sender. The process is shown in Figure 17.3 and the detailed steps are described as follows:
1. Original sender generates a random nonce (Rj) and insert it into the semi-encrypted key pre-distribution field in the packet before sending it.
2. Each source group node from a source key, ai, in the delivery path will carry out the following:
a. If the SRC index bit (whose index value is i) is equal to 1, then go to step 3.
b. Extract the value in the semi-encrypted key pre-distribution field (let it be denoted as x).
c. Extract Mj from the packet.
d. Calculate 
and store this as a new value in the semi-encrypted key pre-distribution field of the packet.
e. Set the SRC index bit (whose index value is i) as 1.
3. Each verifier node will perform the following step:
a. If all of the m bits are set to 1 in the SRC index bits field, then the node will extract the value of the semi-encrypted key pre-distribution field, and store it as Φj to be used at the future verification time (after d block periods).
Delayed key disclosure and verification after the key disclosure delay
Because the actual SOKC keys are disclosed after the delay (d block periods), the verifications of the keys and messages that were included in the j-th packet may be carried out when the nodes receive/process a packet in the (j+d)-th block period. So, we disclose the j-th keys from the SOKCs in the (j+d)-th packet, and the verifications will be carried out by the verifier nodes upon the receipt of the (j+d)-th packet. This process is depicted in Figure 17.3, and the detailed steps are described as follows:
1. Original sender discloses the nonce (Rj) by including in the (j+d)-th packet’s nonce disclosure field.
2. Each source group node from a source key, ai, in the delivery path will carry out the following:
a. If the SRC index bit (whose index value is i) is equal to 1, then go to step 3.
b. Extract the value from the SOKC key disclosure field (let it be denoted as y).
c. Calculate 
and store this as a new value into the SOKC key disclosure field of the packet.
d. Set the SRC index bit (whose index value is i) as 1.
3. Each verifier node will perform the following steps:
a. If all of the m bits are set to 1 in the SRC index bits field, then the node will perform the following steps:
i. Extract the value of the SOKC key disclosure field (let it be denoted as z).
a) If not, then the key validation for SOKC fails, discards the packet and exit from the algorithm.
b) If the equality holds, then store 
as a valid Yj for future SOKC validation.
A. Calculate 
and compare this to Φj that were extracted and stored in the previously received j-th packet.
i. If they are the same, then the multi-source authentication succeeds for Mj.
ii. If they don’t match, then the multi-source authentication fails for Mj.
Resource requirements
The resource requirements at a source group node from ai are:
The resource requirements at a verifier node are:
• k bits: for storing the SOKC validation key Yn
• d×k bits: for storing Φj in, at most, d consecutive block periods
Hence, the total memory requirement at a verifier node is (d+3)×k bits.
The communication overhead required at each packet (purely needed for our scheme) consists of the following:
Conclusion
We present a new resource-efficient multi-source authentication scheme with Split-Join One-Way Key Chain (SOKC). In this new technique, the communication overhead is small and constant, and the memory requirement at the verifier node is also minimal. This technique may be effectively used for wireless ad hoc networks when there exist multiple trust sources to be utilized at the same time. For example, wireless sensor networks with multiple base stations may utilize this technique to provide enhanced security by incorporating multiple trust sources.
Acknowledgments
This work was supported by the US Army Research Office (ARO) grant W911NF-12-1-0060.
References
1. Park S, Bhatia A, Youn J-H. Hop-count based location discovery in ad hoc sensor networks. In: Proceeding (424) Wireless Networks and Emerging Technologies; 2004.
2. Perrig A, Canetti R, Song D, Tygar D. Efficient and secure source authentication for multicast. In: Proceedings of Network and Distributed System Security Symposium; 2001.
3. Karlof C, Wagner D. Secure routing in wireless sensor networks: Attacks and countermeasures. In: Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications; 2003 May.
4. di Pietro R, Mancini LV, Law YW, Etalle S, Havinga PA. Directed diffusion-based secure multicast scheme for wireless sensor networks. First International Workshop on Wireless Security and Privacy (WiSPr’03).
5. Deng J, Han R, Mishra S. Enhancing base station security in wireless sensor networks. Technical Report CU-CS-951-03. University of Colorado; 2003 Apr.
6. Gandham S, Dawande M, Prakash R, Venkatesan S. Energy efficient schemes for wireless sensor networks with multiple mobile base stations. IEEE Globecom ’03 2004;377–381.
7. Ramamurthy Y, Xue B. A key management protocol for wireless sensor networks with multiple base stations. ICC’08: Proceedings of the IEEE International Conference on Communications. Beijing, China; 2008. p. 1625–9.
8. Hubaux J, Buttyan L, Capkun S. The quest for security in mobile ad hoc networks. In: Proceedings of the ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC 2001); 2001.
9. Zhou L, Haas Z. Securing ad hoc networks. IEEE Network Magazine. 1999;13.
10. Hu Y-C, Johnson DB, Perrig A. SEAD: Secure efficient distance vector routing for mobile wireless ad hoc networks WMCSA 2002. Proceedings of the fourth IEEE Workshop on Mobile Computing Systems and Applications 2002 Jun:3–13.
11. Hu Y-C, Perrig A, Johnson D. Ariadne: a secure on-demand routing protocol for ad hoc networks. Wireless Networks Journal. 2005;11:1.
12. Liu D, Ning P. Multi-level u-TESLA: A broadcast authentication system for distributed sensor networks. Submitted for journal publication. Also available as Technical Report, TR-2003-08; North Carolina State University, Department of Computer Science; 2003 Mar.
13. Przydatek B, Song D, Perrig A. SIA: Secure information aggregation in sensor networks. In: Proc of ACM sensys; 2003.
14. Ye F, Luo H, Lu S. Statistical en-route filtering of injected false data in sensor networks. IEEE J Sel Areas Commun. 2005;23:4.
15. Zhu S, Setial S, Jajodia S. An interleaved hop-by-hop authentication scheme for filtering of injected false data in sensor networks.