Secure Route Formation Using Secure Key Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

To enhance security in distributed networks, such as ad hoc networks, it is important to evaluate the trustworthiness of participating entities since trust is the major driving force for collaboration especially in route formation from source to destination. Wireless broadcast is an effective approach to find route information among number of nodes. To provide secure access to routing table in wireless route formation, symmetric key-based encryption is used to ensure that only nodes who own the valid keys can decrypt the route information. Regarding various broadcasts, an efficient key management to distribute and change keys is in great demand for access control in route establishment. In this paper, we propose an efficient key management scheme (namely SCRFKM to handle key distribution with regarding to complex route formation possibilities and node activities. SCRFKM is designed to have the following advantages. First, it supports all route request activities in MANETs. Second, in SCRFKM, a node only needs to hold one set of keys for all requested route formation operations, instead of separate sets of keys for each request. Third, SCRFKM identifies the minimum set of keys that must be changed to ensure routing security and minimize the rekey cost. Our simulations show that SCRFKM can save about 25% of communication overhead in the broadcast channel and about 30%of decryption cost for each node, compared with logical key hierarchy based approaches.

Keywords: -Wireless broadcast, key management, access control, key hierarchy, key distribution, secure group communication, SCRFKM (Secure Route Formation Key Management)

1. Introduction

The rapid advent of wireless technology helped in the increasing popularity of mobile devices and there is a tremendous increase in interest of wireless routing mechanisms in both industrial and academic communities in recent years. Among various approaches, broadcasting allows a very efficient usage of the scarce wireless bandwidth, because it allows simultaneous access by an arbitrary number of mobile nodes [1]. Wireless data broadcast services have been available as commercial products for many years. A wireless data broadcast system can thus be assumed to consist of three components as depicted in Figure 1 (1) the broadcast server; (2) the mobile devices; and (3) the communication mechanism. The server broadcasts route formation requests on air. A mobile node that receives the broadcast information filters the nodes request according to node's queries and privileges. The specialty of the broadcast system is that (a) the routing server determines the schedule to broadcast all route requests on air and (b) the mobile nodes listen to the broadcast channel but only retrieve data (filter data out) based on nodes' queries. The communication mechanism includes wireless broadcast channels and (optional) uplink channels. Broadcast channel is the main mechanism for data dissemination. Route request data is broadcasted at regular intervals of time so that nodes can recover lost or missed route requests. The uplink channels, which have limited bandwidth, are reserved for occasional uses to dynamically route change requests.

Figure 1: Broadcasting mechanism for route formation form

In broadcast services, the basic data unit is data item, such as a Route Request Packet. Data items are grouped into requests and a node specifies which request he would like to transmit or receive. Typical request could be Route Request, Route Reply, Route Error, etc. For simplicity, we assume that each request covers a set of data items, and routes are exclusively formed successfully. A node may request for one or more routes. The set of requests is called the node's subscription. Nodes can subscribe via Internet or uplink channels to specify the routes that they are interested in route formation. Earlier studies on wireless route request broadcast services have mainly focused on performance issues such as reducing routing information access latency and conserving battery power of mobile nodes. Unfortunately, the critical security requirements of this type of broadcast routing service have not yet been addressed, i.e. broadcast service providers need to ensure backward and forward secrecy [2], [3] with respect to membership dynamics. In the wireless broadcast environment, any node can monitor the broadcast channel and record the broadcast data of route formation. If the routing information data is not encrypted, the content is open to the public and anyone can access the routing information data and thus may lead to adversaries' modification of routing information. In addition, a node may only subscribe to a few routes. If routing information data in other routing tables are not encrypted, the node can obtain data beyond the subscription privilege. Hence, access control should be enforced via encrypting routing data in a proper way so that only subscribing nodes can access the broadcast routing information data, and subscribing nodes can only access the data to which they subscribe.

Symmetric-key-based encryption is a natural choice for ensuring secure data dissemination and access in routing information to be accessed. The broadcast routing data can be encrypted so that only those nodes who own valid keys can decrypt them. Thus, the encryption keys can be used as an effective means for access control in wireless route information broadcast. For example, each node has one unique key to encrypt the route information. The key is issued to the node that is authorized to receive and decrypt the data items. If a node subscribes to multiple route requests, it needs an encryption key for each request. Since a node only has keys for his route request, he cannot decrypt broadcast data and rekey messages designated to other nodes. At the same time, a routing data item can be decrypted by an arbitrary number of nodes who subscribe to it. This allows many nodes to receive the data at the same time and addresses the scalability problem, or request lost or missed keys

Two categories of key management schemes in the literature may be applied in broadcast services: (1) logic key hierarchy (LKH) based techniques [2]-[9] proposed for multicast services; and (2) broadcast encryption techniques [10]-[16] in current broadcast services. They normally require nodes to possess decryption boxes to receive the subscribed route information, and the broadcast services can only provide to nodes a few routes, each of which includes a fixed set of routing information. Nodes cannot select individual route within a set of routes. If a node wants to change his route, the node needs to request another decryption box that can decrypt the subscribed route information. This straightforward approach used in LKH is inefficient for nodes subscribing to many routes. If nodes could use the same set of keys for multiple routes, there would be fewer requirements for nodes to handle keys. Furthermore, when a node changes its route request, we argue that it is unnecessary to change keys for the routes to which the node is still using, as long as security can be ensured. In this way, rekey cost can be reduced and fewer nodes will be affected. Therefore, we propose a new key management scheme, namely Secure Route formation Key Management (SCRFKM), based on two important observations: (1) nodes who subscribe to multiple routes can be captured by a shared key tree, and (2) old keys can be reused to save rekey cost without compromising security. SCRFKM has two components: shared key tree and shared key management.

2. Related Work

A. Logical Key Hierarchy

Secure key management for wireless broadcast is closely related to secure group key management in networking [4]. Logical key hierarchy (LKH) is proposed in [2], [5] that uses a key tree (depicted in Figure 2) for each group of nodes who subscribe the same route. The root (top node) of the tree is the data encryption key (DEK) of the route. Each leaf (bottom node) in the tree represents an individual key (IDK) of a node that is only shared between the system and the node. Other keys in the tree, namely key distribution keys (KDKs), are used to encrypt new DEKs and KDKs. A node only knows the keys along the path from the leaf of the node to the root of the key tree.

Figure 2: Logical Key Hierarchy

When a node joins or leaves the group, the server needs to change and broadcast the corresponding new keys, and this operation is called rekey, and the broadcast message of new keys is called rekey message. In our system, data and rekey messages are broadcast in the same broadcast channel to the nodes.

B. Broadcast Encryption

There are some other key management schemes in the literature for multicast and broadcast services for routing establishment.[10] used arbitrarily revealed key sequences to do scalable multicast key management without any overhead on joins/leaves.[11] proposed two schemes that insert an index head into packets for decryption. However, both of them require pre-planned subscription, which contradicts the fact that in pervasive computing and air data access, a node may change subscriptions at any moment. In addition [11] only supports a limited combination of programs.[13] proposed a scheme to yield maximal resilience against arbitrary coalitions of non-privileged nodes. Zero-message scheme [14], [15] does not require the broadcast server to disseminate any message in order to generate a common key. Naor et al. [16] proposed a stateless scheme to facilitate group members to obtain updated session keys even if they miss some previous key distribution messages. Although this scheme is more efficient than LKH in rekey operations, it mainly handles revocation when a node stops subscription. It does not efficiently support joins, which are crucial in our system. Finally, [24], [27] proposed self-healing approaches for group members to recover the session keys by combining information from previous key distribution information. Compared with LKH-based approaches, key management schemes in broadcast route information encryption are less flexible regarding possible subscriptions. Conforming to the current practice described in RFC2627 [2], we select binary trees to present our scheme. Note that our scheme does not require binary trees and can be applied in trees of other degrees.

3 Shared Key Structure

a. Rekey Operations

In this study, we consider node activities of joining/leaving/shifting among trees, instead of joining/quitting/changing among route formation. Consider the example in Figure 3, where a node us shifts from tr4 to tr6.

Figure 3 Shared Key Tree

When us was in tr4, us subscribed g1 and g2. After he shifts to tr6, he subscribes g1, g2 and g3. Hence, the shift in fact means the node adds g3 into his current subscription. To issue new keys upon a node event, the main task is to identify the keys that need to be changed. We use two types of paths in the key forest to represent the to-be-changed keys. When a node leaves a tree, we say, a leave path is formed, which consists of keys that the node will no longer use. When a node joins a tree, we say, an enroll path is formed, which consists of keys that the node will use in the future. Similarly, when a node shifts from one tree to another, a leave path and an enroll path are formed. In SCRFKM, a complete path starts from the leaf node and ends at the multiple DEKs of the subscribed routes that share the tree. For example, in Figure 4, when us shifts from tr4 to tr6, the leave path consists of knL and kr4, and the enroll path consists of knJ, kr6, kg1, kg2 and kg3. Note that in this example, kg1 and kg2 are the keys that node already has and still needs in the future. Hence, kg1 and kg2 are not in the leave path, although us leaves tr4. To broadcast new keys, the server should first compose rekey packets.

Algorithm of SCRFKM in Broadcast Server

1: if a join or shift event happens then

2: according to Theorem of Critical Key, find all critical keys in the tree the node wants to join or shift to;

3: select the best enroll path that has the minimum

number of critical keys;

4: change all critical keys in the best enroll path, and broadcast corresponding rekey messages;

5: end if

6: if a leave or shift event happens then

7: change all keys in the leave path, and broadcast

corresponding rekey messages;

8: end if

Figure 4: Key Forest

b. Security Analysis

To ensure multicast or broadcast security, group key management should satisfy four security properties [2], [3]: non group confidentiality, collusion freedom, future confidentiality (forward secrecy), and past confidentiality (backward secrecy).

In the following, we discuss how SCRFKM satisfies these properties.

Non-group confidentiality: passive adversaries should not have access to any group key. Because keys are encrypted when being broadcast, passive adversaries can not decrypt any key without knowing decryption key.

Collusion freedom: by sharing group keys, multiple present nodes can not derive any group key that they are not holding. When multiple nodes collude, they may try to share their keys to derived unknown group keys. The sharing can be represented by a sub graph of the paths belonging to the colluding nodes. However, in SCRFKM, a node does not know any key not on this path. Hence, colluding nodes do not know any key outside the sub graph that represents the collusion.

Future confidentiality (forward secrecy): a leaving node should not have access to any group key after leaving his present group. According to Algorithm, SCRFKM changes all keys in the leave path, because the leaving node holds these keys. Hence, the leaving node will not have the new keys after the node leaves his group.

Past confidentiality (backward secrecy): a joining node added at time t should not have access to any keys used to encrypt data before t. According to Algorithm, SCRFKM changes all critical keys in the enroll path when a node joins. It has been basically proved that the joining node can only derive past group keys from critical keys. Hence, changing critical keys and reusing non-critical keys prevent the joining node from obtaining past group keys.

4. Performance Evaluation.

Simulation: The analysis gives estimates on major performance metrics. We notice that some factors could bring more insightful results. For example, nodes may not be evenly distributed in trees due to the fact that some programs may be more popular than other programs. Also, nodes may be more or less likely to stay in current subscriptions than to frequently change their subscriptions. Hence, in the following, we use simulation to examine the impacts of these node behaviors.

In the simulation, we compare SCRFKM with three other representative schemes: SKT, eLKH, LKH, as listed in Table I, to illustrate how shared key and critical key improve the performance of key management in wireless broadcast services. SKT is the approach in [28] where only shared key tree is applied. eLKH is an approach where only critical key is applied to enhance LKH. Neither shared key tree nor critical key is adopted in LKH. If shared key tree is adopted, key management is based on the key forest as illustrated in Figure 4; otherwise, a key tree is created for each program and a node is assigned to all trees corresponding to the programs he subscribes. If critical key is used, a key in an enroll path is changed if and only if it is a critical key; otherwise, all keys in the enroll path need to be changed (as in the other old schemes). Table I lists four schemes representing different solutions which may or may not adopt these two ideas. The names of the schemes are self-explanatory. If key tree reuse is adopted, key management is based on the key forest as illustrated in Figure 4; otherwise, a key tree is created for each program and a node is assigned to all trees corresponding to the programs he subscribes. If critical key is used, a key in an enroll path is changed if and only if it is a critical key; otherwise, all keys in the enroll path need to be changed (as in other schemes). Note that the well-known LKH is used as a base line (i.e. neither shared key nor critical key is adopted).

TABLE I Key Management Schemes


Shared Key

Critical Key













Settings: We assume that the server provides 50 programs. In our experiments, the key forest consists of 300 trees when shared key tree is adopted. Each tree represents a different option of subscriptions. We also assume that there are 10000 nodes (on average) subscribing to the services. The root graph in key forest was automatically generated according to subscriptions. Each program had a different depth in root graph depending on the number of subscriptions that include the program. In the worst case where a program is included in all subscriptions, the depth for this program in root graph is 9. Most programs had a depth of 8 or less, because the probability that a program is selected by more than 256 subscriptions is low. At the same time, the tree depth is around 5, since 10000 nodes are randomly distributed to 300 trees. In each experiment, we compare two equivalent key graphs for shared key schemes and non-shared key schemes. We first generate a random key forest and assign nodes to leaf nodes of the key forest. Then, for non-shared key schemes (LKH and eLKH), we assign nodes to different key trees according to their subscriptions in shared key schemes. Any node event in shared key schemes was also mapped into the equivalent event in non-shared key schemes. All three node events (i.e. join, shift and leave) are modeled as independent Poisson processes. We let so the total number of nodes remains constant (i.e. around 10000). We vary and separately in order to observe their impacts on the rekey performance. The result of our performance comparison is obtained by averaging the rekey cost over 3000 random node events. Here, a node event is referred to an event in schemes that adopt shared key tree. Such an event is mapped into several node events in schemes that do not adopt shared key tree. For example, a node joins a tree of multiple programs in SCRFKM is mapped as a sequence of events in LKH (each is corresponding to the node joining a tree of these programs).

5. Conclusion & Future Scope

In this work, we investigated the issues of key management in support of secure wireless broadcast services for route formation. We proposed SCRFKM as a scalable, efficient and secure key management approach in the broadcast system. We used the key forest to exploit the overlapping nature between nodes and programs in broadcast services. SCRFKM let multiple programs share a single tree so that the nodes subscribing these programs can hold fewer keys. In addition, we proposed a novel shared key management approach to further reduce rekey cost by identifying the minimum set of keys that must be changed to ensure broadcast security. This approach is also applicable to other LKH-based approaches to reduce the rekey cost as in SCRFKM. Our simulation showed that SCRFKM can save about 25% of communication overhead in the broadcast channel and about 30% of decryption cost for each node, compared with the traditional LKH approach. Further deep investigations have to be explored in case of Rekey Operations