Multicasting Key Distribution With Cluster Formation In Ad Hoc Network

A key management scheme for large-scale distributed sensor networks is based on symmetric key pre-distribution. The key pre-distribution is the only practical option for the networks whose physical topology is unknown prior to deployment or changes fast after deployment.

Overview

The key management scheme relies on probabilistic key sharing among the nodes in the network and takes help of a simple shared-key discovery protocol for key distribution, revocation and node re-keying. In the proposed scheme an offline trusted third party pre initializes each node of the network with a key ring. The key ring is consists of k keys chosen randomly from a large pull of keys named P. As the keys are chosen randomly, some pair of nodes may not share a common key
Key rings are constructed from randomly chosen keys from the large key pool P and distributed to every node. Suppose a pair of node (B,F) does not have a shared key exist among them. But, (B, C) and (C, F) node pairs have shared key among them. Nodes Band F can use the path exists between them (i.e., which have pair-wise key-sharing of nodes (B, C) and (C, F)) to exchange a key that establishes a direct link. So, the main motivation is, it does not require having full shared-key connectivity as offered by pair wise private key sharing between every two nodes in the network.

Basic operations
The following sub-sections describe the basic operations of this key management scheme.

Key Distribution
The major part of the scheme deals with key distribution, which consists of three parts namely key pre-distribution, shared-key discovery and path-key establishment.

The process of key pre-distribution is done offline with an aim to ensure each node with a moderate number of keys in its key ring so that any two nodes share a key with a chosen probability. Followings tasks are done in this step:

• Generate a large pool of P keys and corresponding key identifiers.

• Select k key randomly from P to form a key ring.

• Load the key ring to a node.

• Save the key identifier of a key ring and associated sensor identifier on a trusted controller.

• Load controller nodes with the keys they share with individual nodes.

In the shared-key discovery phase a node tries to find a neighbor within its communication range to whom it shares key. Two nodes can discover if they have a shared-key by broadcasting the list of key identifiers of the keys on their key rings. So, if corresponding nodes share a key, they will find a common key identifier and communication between those neighboring nodes will be secured. But, as the keys are chosen randomly, same key can be shared by more than a pair of nodes

After the completion of shared-key discovery phase, some pairs of nodes can be found that do not share a key but connected by a path consist of node pairs that share a key. In the path-key establishment phase a path-key is assigned to those selected pairs of nodes. Path keys are chosen from the unassigned keys left in the key rings.

Key Revocation
Key revocation is necessary when a node in the network is compromised. When a node is compromised, the associated controller node broadcasts a message containing signed key identifiers to request revoking the corresponding keys. After receiving the revocation message, each node verifies the signature of the key identifiers finds those key identifiers in its key ring and removes the corresponding keys. Removal of keys certainly will affect some of the links to disappear and those nodes will have to restart the shared-key discovery phase and likely path-key establishment phase.

Re-Keying
Re-keying is needed when a node wants to revoke its keys (i.e., self-revocation) or lifetime of a key expires. Re-keying does not require any network wide message broadcast from a controller node and hence simple. As like key revocation the affected nodes after expired keys are revoked, need to start the shared-key discovery phase and possibly path-key establishment phase

Analysis

This key management scheme is simple and considers the low computational power of the nodes. Based on the operational requirement, design parameters can be adopted. Like for a higher probability of finding a shared key between any two nodes, higher number of keys should be required in a key ring and so as the size of the key pool.
Looking to the fact that ad hoc networks are dynamic in nature, network topologies cannot be determined before deployment, low energy constraint devices etc; a key pre distribution scheme would be a better solution.

The scheme uses symmetric encryption which is fast and requires less computational operations. It ensures confidentiality. The proposed key pre-distribution scheme requires the availability of a trusted third party (i.e., large key pool) in the initialization phase to pre-load each node with a key ring and corresponding key identifies. So, it is evident that if the trusted third party is compromised, whole network will be in secured. This could be a limitation to apply this technique in many ad hoc network scenarios. In most of the ad hoc network scenario nodes do not know each other before deployment and get to know each other when they meet. Consider the scenarios like an emergency rescue, battlefield communication and conferencing. It is very likely that nodes in these cases do not have any prior knowledge to which it is going to meet. So, it is impractical to contact to same trusted third party for pre-distribution of keys. So, sharing the key pre-distribution task to all the nodes such that each node contributes in the key pre-distribution phase would be a viable solution.