A survey and taxonomy of distributed certificate authorities in mobile ad hoc networks

Having enough time, an attacker could compromise k shareholders and this allows him to reconstruct the secret. To defend against such attackers, proactive secret sharing scheme updates the shares periodically, without changing the associated private key of DCA. It can be performed more than refreshing the private key. So, an attacker must compromise k shareholders between the updates. Because shares before and after the refresh operation have no relation and if one share is leaked, it will become useless after the refresh. Determining the periods of private key and key shares' updates is very important and has direct impact on the security and performance of the DCA. Thus, if we choose too long values for these periods, the performance of DCA increases, but the security decreases. Also, if we choose short values for these periods, we may have performance problems. Many messages must be sent for these updates so the security increases and keys change sooner than an attacker can find them. As a result, update periods are functions of performance, security, and the situations of MANET.

Second, it reduces the communication overhead and increases the efficiency of certificate management, as certificates are always available to each node at a local repository, few hops away.

Chaddoud et al. [2] proposed a DCA for near-term digital radio (NTDR) cluster-based ad hoc networks. The DCA is distributed among the cluster heads (CHs) which become the shareholding DCA nodes. Thus, no single CH knows the DCA private key and when a new CH joins the backbone it needs to be issued with a share of the DCA's private key. In this scheme, when a node wants the DCA to sign a request, the node's CH receives the request and forwards it to the backbone. Any CH that receives the request uses his share of shared key to sign the request and produces a signature share. Once the node has received and verified k signature shares it can use them to construct the DCA's signature on request. This DCA supports the operations such as system setup or bootstrapping, applying a DCA private key, joining a new CH, evicting an existing CH, refreshing CH shares. In Bootstrapping operation, to construct the shared key and establish a (k,n) threshold sharing of a private key, all CHs must participate with the Distributed Key Generation algorithm as part of the construction of the NTDR backbone.

Rao and Xie [8] present another distributed certification authority scheme based on clustering scheme. They classify MANET nodes into clients, repositories, and server nodes. The client nodes are organized into clusters. In each cluster, some nodes are elected to be repository which stores the certificates of the nodes and servers within the cluster. The server nodes are elected in repository nodes. Because authentication is one of the key vulnerabilities of CA systems, they use a registration authority (RA). When a new node joins the network, it contacts a fixed RA. Then RA verifies credential of new node and contacts k server nodes. In addition, they issue certificate for new node and sent it to RA. Considering next step, RA gives this certificate to new node. Unfortunately, they have assumed that the RA does not belong to ad hoc network and it is part of a wired network. To design various components of ad hoc network, we should preserve the independence of MANET and do not depend on any other networks' components. Certificate revocation lists (CRLs) are the other issues that have been discussed in this approach. Revoking a certificate can be initiated either by few nodes belonging to the same cluster or by a node that wants to revoke its own certificate. Furthermore, they have considered the mobility of nodes among clusters of MANET, something that almost never discussed in other schemes. When a mobile node leaves the source cluster and enters the destination cluster, it contacts any repository at destination cluster. At the same time, the mobile node sends its own certificate to the repository of destination cluster. The certificates of the node in the source cluster can be removed, unless the mobility management protocol predicts that the node is temporarily moved to a new cluster.

Elhdhili et al. [9] propose a totally distributed cluster-based key management for ad hoc networks and use a (K,N) threshold scheme to distribute an RSA signing key to the set of CHs, Furthermore, they use proactive and verifiable secret sharing to protect the secret from various attacks. They also assume that the system contains three types of nodes. The first one is an administrator that will exist only when the initialization step can leave the network. The second nodes are a set of CHs and the third ones are regular nodes. In addition, the administrator and CHs have directories to save the certificates. Each CH is a central CA for its cluster members. It is initialized by the administrator or by a coalition of K, other CHs. For system bootstrapping, administrator plays the role of a certification authority for CHs and then he can leave. Its main role is to certify existing CHs, distribute his secret key over them according to the secret sharing scheme and give them his certificate. The CHs will be considered as a distributed certification authority for the new nodes. In Figure 3, we have specified the advantages of clustering in DCA systems and the functions that CH can do on behalf of other users.

Dong et al. [6] have designed another cluster-based PDCA for MANET and propose optimization for DCA's nodes operations. First, when a user needs PDCA services, he must locate enough PDCA server nodes. To solve this problem, they shift the responsibility of CA discovery from user nodes to the CHs. Thus, a CH must maintain the required information to locate the CA nodes in or out of its cluster. Therefore, each CH maintains a CA information table (CIT), which contains a list of the CA nodes in its local cluster, and probably the CA information in other clusters. When a user requests DCA services, he sends it to his CH to obtain the required CA information through which the CA servers can quickly be located. In this way, DCA information is managed only among the CHs, which reduces the response time and overhead of various DCA operations and enhance the availability and response time of the system. Second, to increase the security of DCA, each node's share must be updated regularly, so the efficient updating of this secret shares in all CA server nodes is very important and has direct impact on DCA's performance. In this approach, they have devised a distributed scheme called sequential share update, to reduce the update overhead. It can resolve the multiple initializations problem and achieves fast system-wide update with low system overhead. At the beginning of sequential update, a coalition of t servers, instead of all servers, update their shares by applying the traditional proactive share update scheme. The remaining nodes will implement the self-initialization protocol so they can refresh their secret share with the help of t servers who have already updated their shares. Finally, although they have devised good solutions to increase availability and performance of DCA, they did not propose anything about RA in their scheme and just assume when a user first joins the network, he has been authenticated.

Lee and Jeong [10] proposed a partially distributed certificate management system that can handle mobility of nodes. It minimizes routing loads and enhances expandability of network by allowing participating nodes to authenticate each other without being interrupted by joining the cluster. In their model, certificate creation time slightly rose as the number of bits increased. But, the pace of increase was much slower than that obtained from the use of existing certificate-based authentication protocol. In addition, the proposed model offered a steady delivery time in the certificate creation phase despite the increase in packet size. The efficiency and security can be therefore maintained in the network. It was also found that the efficiency of the network was not influenced by changes in the number of nodes (k) because partial certificates are consistently generated by coalition of existing member nodes without being interfered by nodes joining the cluster. Since the node requesting partially distributed certificates performs the whole process involving certificate creation, unnecessary system overhead can be eliminated.

Zouridaki et al. [11] designed an elliptic curve-based DCA system. Elliptic curve is used because of its shorter key length and lower computational overhead. Their scheme uses a three-tiered logical view of DCA architecture. At the lowest tier, individual nodes are organized into clusters. The next tier consists of one or more certificate repositories in each cluster that broadcast the certificates of new nodes and the top tier consists of DCA servers that periodically inform the cluster about issued or the updated CRL. In general, the inter-cluster communication depends on whether it needs to be authenticated or encrypted, but the communication inside a cluster is relatively fast. Because each node caches the most used certificates and updated CRLs of the nodes within the cluster and infrequently communicates with the repositories. In this scheme, the number of servers is defined by n = 2k + 1 and it tolerates k compromised server in a predefined period of time. In Table 4, we have compared the various properties of all cluster-based DCA schemes.

Even though flooding the messages in the network is the easiest way to transfer the certificate requests and other messages, it degrades the performance of MANET, so unicast protocols have been used in most of the DCA schemes to solve this problem. In MANETs, unicast routing protocols are classified into proactive, reactive, and hybrid protocols. With the large amount of control data that proactive routing protocols send, it seems that they can be used for implementing DCA in MANET. So, Dhillon et al. [5] propose an FDCA to be implemented with OLSR protocol. This approach uses existing OLSR control packets. It enables MANET to autonomously self-secure itself without any external administration and minimizes the signaling overhead. It is assumed that the network is initialized with at least k shareholders and a certificate-requesting node must discover them. Each MPR uses its TC message to announce which nodes in its MPR selector set claim to be shareholders. When a node receives TC messages, it uses them to build routing and shareholder tables. A node chooses a serving coalition of the k least costly shareholders in terms of hop count and sends a CREQ message to these nodes. Upon receiving this message, each node generates a certificate and returns it in a CREPLY message. The requesting node verifies the validity of the partial signature using verifiable secret sharing techniques. Upon receiving k valid replies, the requesting node adds them together and generates a proper signature. Unfortunately, the OLSR protocol does not support any security mechanism and attackers can alter control packets or send incorrect control packets. Also attacker may broadcast HELLO messages specifying neighbors that do not exist and becomes an MPR or he may send TC messages to be MPR and launch black hole attacks. To solve these problems, they use encryption and digital signatures to ensure the integrity and authenticity of the HELLO and TC messages.

Another OLSR-based scheme is proposed by Xia et al. [12]. They use identity-based encryption and alter the OLSR's HELLO and TC messages for sending the control data. However, there are two problems for implementing identity-based FDCA in MANET, the distributed generation of master keys and distribution of private keys. To solve these problems, they propose to distribute the master key share with threshold secret sharing and use of identity-based signcryption mechanism to provide a security channel for distributed private key generation.

In addition, because the identity-based encryption can reduce the communication overhead and resource consumption, the proposed approach is more suitable to the characteristics of the MANET.

Previous schemes were based on proactive routing, Yi and Kravets [7] present a PDCA scheme that uses reactive routing and call it MObile CA (MOCA). Any client who needs a certificate must contact at least k MOCAs. The contacted MOCAs generate a partial signature over the received data and client collects at least k partial signatures to construct the full signature. They also propose a protocol called MOCA certification protocol (MP), to provide an efficient way for communication between clients and MOCA nodes. If too few CREP packets are received, the client timeout and the certification request fail. So, setting the right value for this timer is very important. As a CREQ packet passes through a node, a reverse path to the sender is established. These reverse paths are coupled with timers and maintained long enough for a returning CREP packet to be able to travel back to the sender. The simplest method to reach MOCAs is the flooding of CREQ packets. To reduce the overhead of flooding, they introduce B-unicast, where the client can use multiple unicast to replace flooding of CREQs. It utilizes the existing information in the route cache and just uses flooding when there are not enough routes cached. If the network has low mobility, having just k cached routes may be sufficient. But, in highly mobile networks, sending exactly k unicast CREQs is dangerous since one CREQ loss results in the failure of certification request. Therefore, the node should send additional CREQs. Setting the right amount of these messages depends on the mobility of network. There are schemes that are based on MOCA and try to extend its functionality. For example, Sen et al. [13] designed a MOCA-based scheme and developed a reliable protocol with less communication overhead compared to the original MOCA. Their protocol uses the CREQ and CREP messages that can be piggybacked on the routing packets for reducing the communication overhead. The revocation of certificates is another issue that has been considered in this scheme. It is only possible when at least k CA nodes put their partial signatures on it. Each of the k CA nodes broadcasts the certificate to be revoked after putting its own signature. When the certificate to be revoked gathers k - 1 such partial signatures and reaches another CA node, it completes the signature, revokes the certificate, and broadcasts the revoked certificate to other CA nodes for updating their local CRLs. Network partitioning is one of the major problems that DCA scheme has to deal with it, in this scheme, it is handled by the transitive delegation of CA responsibilities. Thus, an ordinary node that has recently authenticated itself by communicating with k CA nodes will be temporarily deputed to act as a CA node until the partition problem gets over.

In Table 5, we have specified the important properties of routing-based DCA schemes so it gives us appropriate details about these schemes.

In MANETs, it is very important that DCA schemes be self-initialized and the system authority exists only at the beginning of the network startup. So, a number of schemes have been proposed that support this property, for example, Ge and Lam [14] present a self-initialized DCA or SDCA that combine the advantages of the DCA and certificate chain schemes. They claim that this scheme addresses the scalability of certificate chain and has low cost, high availability, and security. In this scheme, the participating nodes initialize CA with the self-initializing protocol (SIP). With this protocol, the fundamental parameters of the DCA, such as the total number of DCA members, threshold value, and list of DCA members, will be negotiated and agreed among a certain number of nodes. With these parameters, the DCA is then constructed collaboratively by the involving nodes and without a trusted dealer. Another scheme for self-initialized DCA in ad hoc network is introduced by Kang et al. [15]. Their scheme uses proxy and threshold signatures. In this scheme, chair nodes that can distribute partial proxy keys for proxy nodes are authenticated by the system authority. In addition, proxy nodes that can issue certificates for other nodes are authenticated and initialized by the system authority or the chair nodes.

The mobility of DCA nodes in MANET has direct impact on DCA operations. If we do not find k DCA node, the certificate cannot be created. In Figure 4, we have classified different kinds of mobility that DCA nodes can show.

Pereira et al. [16] propose a self-adaptable and intrusion tolerant CA, that is able to manage changes in the membership of the servers group and allows the CA to reconfigure itself for guaranteeing the availability and the inviolability of the certification service.

Another solution is to increase the number of shares per node. Joshi et al. [4] have used this approach and proposed a secure, redundant, and fully distributed key management scheme for MANET. As a result, the number of nodes required to recreate the CA key is reduced and the probability of creating the certificate for normal users increases. System decreases and an attacker may compromises the CA key. Therefore, to increase security, intrusion detection systems must be used for identifying and removing the misbehaving or compromising nodes and the q shares chosen at random.

Luo et al. [17] proposed a solution called DIstributed CerTification Authority with probabilisTic freshness (DICTATE). They tried to enhance the security of an ad hoc network under the responsibility of a mother certification authority (mCA). Since the nodes can frequently be isolated from the mCA there is still a need to access to a certification authority. The mCA preassigns a special role to several nodes called servers that constitute a distributed certification authority during the isolated period. This solution ensures that the DCA always processes a certificate update or query request in a finite amount of time and that an adversary cannot forge a certificate. Moreover, it guarantees that the DCA responds to a query request with the most recent version of the queried certificate in a certain probability; this probability can be made arbitrarily close to one, but at the expense of higher overhead.

Some of the presented schemes for DCA try to improve DCA's security and guard it against various attacks. For example, Zhou et al. [18] have designed a scheme called multiple-key cryptography-based DCA (MC-DCA) which is resilient to Sybil attacks. It achieves lower communication overhead and moderate latency compared with the threshold-based schemes. The Sybil attack is fatal to the threshold scheme. There is no efficient way to defeat it. In MANET, attackers can forge the IP and hardware addresses easily, so a malicious node impersonates many identities and it is difficult to bind a single identity with one node.

Also, Rajaram and Palaniswami [19] designed a high performance CA that supports certificate renewal, revocation, and resists to various outside attacks. Their scheme supports routing cum forwarding (RCF) of packet monitoring, certification revival, and certificate revocation. By monitoring RCF behavior, the malicious nodes are detected by monitoring the behavior hop-by-hop. Certificate revival uses a redundancy scheme in which a node is allocated more than one key share by incorporating redundancy into the network. This mechanism guarantees that genuine nodes can continue to stay in the network by revival of their certificates along a periodical time period. Certificate revocation provides the authority to isolate any malicious nodes or regain the nodes which turn up to its best state after any attack or failure.

In Figure 5, we have specified the security techniques that can be applied in DCA systems. It is obvious that none of these methods can provide security and we must apply all of them to provide a secure DCA scheme.

In general, when we distribute the task of one system to many subsystems, we may have availability and performance problems. So, some of the DCA schemes try to decrease these problems and use special infrastructures to provide better availability and performance. For example, Raghani et al. [20] have designed a DCA, in which networks nodes can obtain certificate from their one hop neighbors. With such distributed CA, when the number of neighbors of a node, also called node degree, reduces, there is a substantial increase in the certification service delays. Therefore, they have tried to solve this problem with a suite of network monitoring protocols. The proposed protocols dynamically adjust the threshold value by monitoring the average node degree of the network and thereby prevent an increase in certification service delay.

We have compared the properties of various proposed DCA schemes at Table 3. This comparison gives us good insight on the proposed schemes and determines the less researched areas that can be studied in future works.