In this section the main characteristics of the public-key infrastructure models used in MANETs are described before introducing some new ideas that conform our proposal. We may find two main alternatives for the deployment of PKIs in MANETs in the bibliography: distributed certification authorities, and self-organized public-key management.
In the first case, the certification process is underpinned by distributed CAs, which use a threshold digital signature scheme and are in charge of issuing and renewing certificates of nodes [
11‐
13]. One of the first schemes following this approach was proposed in [
14], where a group of special nodes, acting as a coalition, are responsible for certification tasks. There the authors put forward that the CA's functions should be the responsibility of a set of special servers set included in the network. These servers will sign the public key of the nodes trough a
threshold signature scheme [
15]. Therefore, each time a node in the network
wishes to communicate with one of his peers
, he should contact with
servers in advance in order to obtain
's public key signed with the CA's secret key. One of the servers included in the previous coalition will be in charge of playing the combiner's role. This means that once he receives the shares from its peers in the coalition, he generates the signature of the requested public key. However, there are some general drawbacks associated to this alternative. First, the combiner figure and the servers acting as certification authorities produce system overload as all the communications requesting certification issuance and validation should be attended for them. Additionally, introducing special servers does not guarantee the elimination of vulnerabilities to DoS attacks. Another question to take into account is the need for additional storage requirements since the public keys of all the members of the network must be stored by the servers. When the network is sparse or during its first deployment stages finding
servers available in its transmission range may become a handicap.
Such a self-organized version of public-key management was chosen as base for this paper in order to guarantee identical roles for all MANET nodes. This approach involves the relocation of the responsibility for creating, storing, distributing, and revoking public keys among the members of the network.
3.1. Describing the Self-Organized Approach
The self-organized model in MANETs was initially described in [
20]. Its authors put forward the substitution of the centralized certification authority by a self-organized scenario where certification is carried out through chains of certificates which are issued by the nodes themselves. Such a scheme is based on the information stored by each node and the trust relationship among neighbour nodes.
In this work we decided to follow the self-organized key management model based on the web of trust approach. Several are the reasons that justify the choice of this option. First, this model demands less maintenance overhead. Secondly, it is well worth remarking that on the one hand the self-organized approach eases the use of a simple bootstrap mechanism, and on the other hand all the nodes perform equal roles.
In this model, public keys and certificates are represented as a directed graph
, known as certificate graph. Each vertex
in this graph defines a public key of a node, and each arc
denotes a certificate associated to
's public key, signed with
's private key. Each node
has a public key, a private key, and two certificate repositories, the updated and the nonupdated repositories, denoted, respectively,
and
. Initially the updated certificate repository contains the list of certificates on which each node trusts (out-bound list) and the list of certificates of all the nodes that trust on
(in-bound list). A sequence
of certificates where the vertices are all different is called a certificate chain from
to
.
The tasks that any member of the network has to develop in this public-key management scheme are:
(1)
Certificate Management:
(a)
Key generation: the node generates its keys by itself.
(b)
Certificate issuance: each node issues certificates that bind public keys of other nodes to their identities.
(c)
Certificate exchange: each node exchanges certificates with other nodes and builds its non-updated repository.
(d)
Updated certificate repository construction: the node builds its updated repository.
(2)
Public-Key Verification:
(a)
Finding a certificate chain.
(b)
Verifying the certificates in the chain.
Although the self-organized methodology for PKI deployment has been extensively analyzed [
21‐
23], there are still open questions that needs further research. One of this pending questions is how to encourage node's participation in the tasks related to certification issuance or certification exchange. Since many resources are limited in MANETs the cooperation issue is a major issue when dealing with many node tasks, and PKI management is one of the crucial ones.
In the following we describe how certificate management and public-key verification are carried out in the self-organized model.
Each node
generates by itself the pair formed by its public key and its secret key. Then a request for signing the generated public key is sent to
's neighbours. Since these nodes are in a one-hop distance from
, they can use any trusted mechanisms such as side channels in order to assure the binding established between the corresponding public key and the node's identity.
Apart from that, in order to ease certificate revocation, each certificate issued will be valid for a certain period of time. This parameter may be chosen depending on the mobility characteristics of the underlying MANET.
Since the certificates issued by a node are stored in its local repository, one of the tasks that a node may perform during idle periods is the renewal of certificates issued by it to those nodes that might still be considered as trusted. Otherwise, certificate renewal may be developed on demand. It means that when an expired certificate is included in the non-updated repository of a node, such a node should request a renewal for that certificate. When a certificate for a node
is issued by a node
the edge
is added to the certificate graph and each node
and
stores it in its in-bound and outbound list, respectively.
Note that the speed in the creation of the certificate graph and its density depend on the willingness of users for distributing certificates, and on nodes' mobility. In particular, the more mobility the nodes have, the more complete the repositories will be. The same happens with other aspects related to MANET cooperation.
As in any PKI-based system, certificate revocation should be also taken into account. When revocation is initiated due to key compromise or misbehaviour of the corresponding node, the certificate issuer sends a message to all nodes stating that such a certificate has been revoked. This can be accomplished because each node maintains a list containing the members of the network that have contacted it to request updates of the certificates it had issued. Hence, in fact it is not necessary to send the revocation message to all the members of the network. The last proposals related to revocation policies in MANETs defend the creation of schemes based in reputation systems [
24,
25]. When revocation is due to the fact that the expiration time has been reached, such a revocation can be deduced directly by all nodes since the expiration date is contained in the certificate. The work in [
26] describes a method to update expired certificates by using probabilistic multicast. The importance of this method is that nodes different from the actual issuer of the certificate can update it once it has expired.
Certificate exchange can be considered a low-cost procedure because it only involves one-hop distance nodes. It allows to share and to distribute the issued and stored certificates. A description of this procedure is as follows.
(1)
Every node
retransmits the hash values of the certificates stored in the repositories
and
to its neighbours. The recipient nodes answer with the hash values of the certificates contained in their repositories.
(2)
Every node compares the received value with the one it already has and requests to its neighbours only the certificates that are new.
(3)
If the local memory of a node is not large enough, the expired certificates are deleted from the non-updated repository, starting by the oldest ones.
(4)
In this way, after a short period of time the non-updated repository
contains almost all the certificate graph
. Afterwards, the only task to be carried out by the nodes is to exchange the new certificates.
In the original proposal two ways of building the updated certificate repository
of a node
were described.
(1)
Node
communicates with its neighbours in the certificate graph.
(2)
Node
applies over
an appropriate algorithm in order to generate
after checking the validity of every single certificate.
One of the crucial issues in the self-organized scheme that may influence the correct behaviour of the whole scheme is the selection of the certificates stored by each node in its repository. The method specified with this objective should satisfy two requirements at the same time: limitation in storing requirements, and performance of the updated repository in terms of ability to find chains for the largest possible number of nodes. This problem, known as certification chain discovery problem, has received particular attention in the bibliography related to MANETs [
21‐
23,
27].
Since the algorithm used in the construction of the updated repositories will influence the efficiency of the scheme, it should be carefully designed. The simplest algorithm for that construction is the so-called Maximum Degree Algorithm (MDA) [
20] (see Algorithm 1), where the criterion followed in the selection of certificates is mainly the degree of the vertices in the certificate graph.
Algorithm 1:
–
heuristic.
Output:
Initialization
(9)
while
do
(10)
while
do
(11)
if
then
(18)
while
and
do
(20)
if
then
(24)
if
then
(34)
if
then
There is another more sophisticated algorithm, called Shortcut Hunter Algorithm, in which certificates are chosen taking into account that when they are deleted, the length of the minimum path between the nodes connected through that certificate is increased in more than 2.
When using the MDA, every node
builds two subgraphs, the out-bound subgraph and the inbound subgraph, which when joined generate the updated certificate repository
. The outbound subgraph is formed by several disjoint paths with the same origin vertex
while in the in-bound subgraph
is the final vertex. In the description of the MDA algorithm, the starting node is
and
,
stands for the in-degree and the out-degree of node
, respectively. The number of paths to be found is represented by
.
A bound on the number of disjoint paths starting at
as well as a bound on the number of disjoint paths to be built with
as final node are given by
and
, respectively.
Another important input parameter is
, which represents the maximum number of vertices to be included in the subgraph generated when the in-bound and the out-bound subgraphs are combined. This parameter may be also controlled by defining as
the length of the chains generated when building the out-bound subgraph and
for the in-bound one.
In order to apply the greedy criterion,
and
, where
consists of a set of vertices, include the sorted vertices of
into descending order according to
and
, respectively.
Note that the process to build the in-bound subgraph is equivalent to it except for the fact that in this case the edges to be chosen are always incoming edges.
In the first stage of the MDA,
outgoing arcs from
are included. The final vertices of these arcs are then included in
. This set is implemented as a typical queue where the insertion (put) and the extraction (get)operations are used. Henceforth,
arcs are chosen in such a way that the formed paths are disjoint. This is accomplished by selecting their origin belonging to
and checking that neither the origin nor the final vertices were previously used in another path.