Securing Mobile Ad Hoc Networks Using Enhanced Identity-Based Cryptography

ETRI Journal.
2015.
May,
37(3):
512-522

- Received : February 15, 2014
- Accepted : December 11, 2014
- Published : May 01, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

Recent developments in identity-based cryptography (IBC) have provided new solutions to problems related to the security of mobile ad hoc networks (MANETs). Although many proposals to solve problems related to the security of MANETs are suggested by the research community, there is no one solution that fits all. The interdependency cycle between secure routing and security services makes the use of IBC in MANETs very challenging. In this paper, two novel methods are proposed to eliminate the need for this cycle. One of these methods utilizes a key pool to secure routes for the distribution of cryptographic materials, while the other adopts a pairing-based key agreement method. Furthermore, our proposed methods utilize threshold cryptography for shared secret and private key generation to eliminate the “single point of failure” and distribute cryptographic services among network nodes. These characteristics guarantee high levels of availability and scalability for the proposed methods. To illustrate the effectiveness and capabilities of the proposed methods, they are simulated and compared against the performance of existing methods.
Steps of proposed method.
p
and
q
denote two large primes and
y
^{2}
=
x
^{3}
+
ax
+
b
over the finite field
G
_{1}
be a
q
-order subgroup of the additive group of points over the elliptic curve and
G
_{2}
be a
q
-order subgroup of the multiplicative group of the finite field
G
_{1}
and
G
_{2}
. The proposed IBC system deploys the following bilinear mapping
e
:
G
_{1}
×
G
_{1}
→
G
_{2}
. This mapping has the following properties
[17]
:
A bilinear map that satisfies the three aforementioned constraints is called an
admissible
bilinear map. According to the fact that
G
_{1}
is a cyclic group, it can be deduced that
P
,
Q
∈
G
_{1}
, equation
A. Key Pool–Based Method
The key pool–based method utilizes a variant of the KM scheme proposed by L. Eschenauer and V.D. Gligor
[23]
. This method consists of the following two stages: key pre-distribution and shared key discovery. The key pre-distribution stage is comprised of several offline phases, as follows:
The shared key discovery phase begins after deployment of the nodes. Each node broadcasts its key identifiers without any form of encryption. The nodes that are in radio range of each other discover the shared keys by comparison. However, it is possible that nodes discover shared keys privately by hiding their key sharing pattern. For example, each node broadcasts
a
and
E_{Ki}
(
α
), where
α
is a random challenge and
K_{i}
for
i
= 1,2, ... ,
k
represents all of the keys in the key ring of the node. The decryption of
E_{Ki}
(
α
) using the right key unveils
α
and establishes a shared key with the transmitter
[23]
.
B. Pairing-Based Method
The second method to establish a secure channel for transmission of IBC parameters utilizes pairing-based key agreement techniques. Similar to
[21]
, the proposed method uses pairing-based techniques to set up secure links between all network nodes. The algorithm of the proposed pairing-based method is as follows:
It is easy to show that
(1) $$\begin{array}{cc}{k}_{ij}^{0}\hfill & =\widehat{e}\left({s}_{i}^{0}.{P}_{j}^{\text{pub}0},P\right)=\widehat{e}\left({s}_{i}^{0}.{s}_{j}^{0}P,P\right)\hfill \\ \hfill & =\widehat{e}\left({s}_{j}^{0}.{s}_{i}^{0}P,P\right)=\widehat{e}\left({s}_{i}^{0}.{P}_{i}^{\text{pub}0},P\right)={k}_{ji}^{0}.\hfill \end{array}$$
Therefore, in this method, nodes share a common key without any additional communication.
n
initial nodes. Similar to
[11]
, the proposed method utilizes a variant of Shamir’s secret-sharing method
[16]
that does not need a trusted authority. The proposed method uses the following algorithm:
Similar to Shamir’s secret-sharing method
[22]
, any
k
set of shareholders can reconstruct the secret using
l_{i}
(
z
) are Lagrange coefficients that can be calculated using
(2) $${l}_{i}(z)={\displaystyle \prod}_{j=1,j\ne i}^{k}\frac{z-j}{i-j}.$$
Two master private keys are
C_{i}
, whether it is a PKG or not, is very important. Similar to
[17]
, the proposed method consists of a number of continuous, non-overlapping key update phases that are denoted by
p_{m}
for 1 ≤
m
<
M
, where
M
is the maximum index of a phase. Each phase
p_{m}
is associated with a binary string, called a phase identifier and denoted by salt
_{m}
. In the initialization phase, a random seed, salt
_{1}
, is preloaded to every node. After deployment, each node can determine phase identifiers using salt
_{m}
= salt
_{m−1}
+ 1(1 <
m
<
M
). In the proposed method, each public/private key pair is both node-specific and phase-specific. The key pair of node
C_{i}
in phase
p_{m}
is denoted by
(3) $$\{\begin{array}{l}{\mathcal{K}}_{{C}_{i},{p}_{m}}=\left({\mathcal{K}}_{{C}_{i}},{\mathcal{K}}_{{p}_{m}}\right)=\left({H}_{1}\left({\text{ID}}_{{C}_{i}}\parallel {\text{MAC}}_{{C}_{i}}\right),{H}_{1}\left({\text{salt}}_{m}\right)\right),\\ {\mathcal{K}}_{{C}_{i},{p}_{m}}^{-1}=\left({\mathcal{K}}_{{C}_{i}}^{-1},{\mathcal{K}}_{{p}_{m}}^{-1}\right)=\left(\text{SK}\times {H}_{1}\left({\text{ID}}_{{C}_{i}}\parallel {\text{MAC}}_{{C}_{i}}\right),\overline{\text{SK}}\times {H}_{1}\left({\text{salt}}_{m}\right)\right).\end{array}$$
Note that (3) is used only for public key calculation. A private key cannot be calculated using this equation because (3) uses SK and
k
PKGs and requests a private key share. After receiving the request, the PKG node
C_{j}
calculates the private key share of
C_{i}
using
C_{i}
over the secure channels that are provided by the shared key generation phase. In this equation,
f
_{extract}
denotes the process of private key share generation in PKG;
S_{j}
and
C_{j}
; and 𝒦
_{Ci}
and 𝒦
_{pm}
are, respectively, node-specific and phase-specific public keys of
C_{i}
. Using (4), node
C_{i}
can calculate the private key after receiving
k
shares as follows:
(4) $$\{\begin{array}{l}{\mathcal{K}}_{{C}_{i}}^{-1}={\displaystyle \prod _{j=1}^{k}{S}_{j}{\mathcal{K}}_{{C}_{i}}},\\ {\mathcal{K}}_{{p}_{m}}^{-1}={\displaystyle \prod _{j=1}^{k}{\overline{S}}_{j}{\mathcal{K}}_{{p}_{m}}},\end{array}$$
where
p_{m}
and
C_{i}
.
k
). Therefore, a MANET should be capable of setting up a new PKG. To become a PKG, a network node must satisfy the following conditions
[13]
:
If a node meets the above-mentioned constraints, then it is believed to be a trusted and capable node. The procedure of generating a new PKG is as follows:
(5) $$\{\begin{array}{c}{\text{ss}}_{iy}={S}_{i}{l}_{i}(I{D}_{y})\text{\hspace{0.17em}\hspace{0.17em}mod\hspace{0.17em}\hspace{0.17em}}q,\\ {\overline{\text{ss}}}_{iy}={\overline{S}}_{i}{l}_{i}(I{D}_{y})\text{\hspace{0.17em}\hspace{0.17em}mod\hspace{0.17em}\hspace{0.17em}}q.\end{array}$$
It is recommended to take an extra round of communications and shuffle the shares before they are sent to the requesting node so as to protect the secrecy of the coalition nodes’ secret shares
[13]
. After shuffling ss
_{iy}
and
_{iy}
and
k
valid shares from PKGs, it can then calculate its share of the master private key using (6) below.
(6) $$\begin{array}{l}{S}_{y}={\displaystyle \sum _{i=1}^{k}{\text{ss}}_{iy}^{\text{'}}}\text{mod}q,\\ {\overline{S}}_{y}={\displaystyle \sum _{i=1}^{k}{\overline{\text{ss}}}_{iy}^{\text{'}}}\text{mod}q.\end{array}$$
n
− 1 links that are connected to captured nodes are compromised. However, in the key pool technique only
k
<<
n
keys that belong to a key ring are compromised. In this case, an adversary can set up a successful attack with
k
/PO probability, in which PO is the number of keys in the key pool
[23]
. Due to wireless network constraints, the deployment of a fully connected network is infeasible. In fact, it is unnecessary to set up a fully connected network in the key discovery phase. It is enough to build a network with multi-hop links between every node; that is, a connected network is sufficient for the operation of our proposed method. Assume
p
_{ck}
is the probability that there is a shared key between two network nodes,
n
is the number of network nodes, and
d_{n}
=
p
_{ck}
× (
n
− 1) is the expected degree of a node (that is, the average number of edges that connect a node to its neighbors). To build a connected network, the following questions should be answered
[23]
:
The first question can be answered using graph theory. The random graph
G
(
n
,
p
_{ck}
) is a graph comprising
n
nodes, where there is a link (shared key) between each pair of nodes that has an associated probability
p
_{ck}
. When
p
_{ck}
equals zero, the graph has no edges, whereas, when
p
_{ck}
equals one, the graph is fully connected. The question is, what value of
p
_{ck}
gives an almost-fully-connected graph
G
? Erdos and others
[24]
showed that for monotone properties of a graph, there is a value for
p
_{ck}
for which any monotone property moves from nonexistent to certainly true. The function that defines
p
_{ck}
is called the threshold function of the property. For an arbitrary probability of graph connectivity
P_{c}
, the threshold function of
p
_{ck}
is defined by
(7) $${P}_{c}=\underset{n\to \infty}{\mathrm{lim}}\text{Pr}[G(n,{p}_{\text{ck}})\text{\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}connected}]={e}^{-{e}^{-c}},$$
where
(8) $${p}_{ck}=\frac{\text{ln}(n)}{n}+\frac{c}{n}$$
and
c
is a real constant. Therefore, for an arbitrary
n
, the values of
p
_{ck}
and
d_{n}
=
p
_{ck}
× (
n
− 1) can be determined such that the resultant graph is connected with probability
P_{c}
.
(9) $${d}_{n}=\left[\frac{n-1}{n}\right]\left[\mathrm{ln}(n)-\mathrm{ln}\left(-\mathrm{ln}({P}_{c})\right)\right].$$
According to (9), it is clear that
d
=
O
(log
n
).
Figure 2
depicts the expected degree of a node,
d_{n}
, as a function of network size
n
, for different values of
P_{c}
.
Figure 2
shows that the required number of neighbors for a graph, which is related to a high
P_{c}
value, is a finite value, and this can be achieved by using a finite number of keys.
Expected degree of nodes vs. number of network nodes for different graph connection probabilities.
For the second question, we note that the constraints of MANETs may cause the number of neighbors to be reduced to
n'
≪
n
. For a given
d_{n}
, the required probability of an existing link between each pair of network nodes is
k
, share at least one common key equals
p'
_{ck}
and the key pool size PO can be expressed as a function of
k
. To relate
p'
_{ck}
to PO and
k
, we use (10) from
[23]
.
(10) $${{p}^{\prime}}_{\text{ck}}\text{\hspace{0.05em}}=\text{\hspace{0.17em}}1\text{\hspace{0.05em}}-\text{\hspace{0.17em}}\mathrm{Pr}\left[\text{two\hspace{0.17em}\hspace{0.17em}nodes\hspace{0.17em}\hspace{0.17em}do\hspace{0.17em}\hspace{0.17em}not\hspace{0.17em}\hspace{0.17em}share\hspace{0.17em}\hspace{0.17em}any\hspace{0.17em}\hspace{0.17em}common\hspace{0.17em}\hspace{0.17em}key}\right].$$
To calculate the probability that two nodes do not share a common key, note that every key in a key ring is extracted from a key pool of size PO without replacement. Therefore, the number of possible key rings is
P
−
k
) keys. Then, the probability that two nodes at least share one common key is
(11) $${p}^{\ufe32}{}_{\text{ck}}=1-\frac{{\left((P-k)!\right)}^{2}}{(P-2k)!P!}.$$
The PO is a very large value, so the Stirling approximation can be used for
n
! as follows:
(12) $$n!\approx \sqrt{2\text{\pi}}{n}^{n+\frac{1}{2}}{\text{e}}^{-n}.$$
So, (11) can be approximated as follows:
(13) $${p}^{\ufe32}{}_{\text{ck}}=1-\frac{{\left(1-\frac{k}{P}\right)}^{2\left(P-k+\frac{1}{2}\right)}}{{\left(1-\frac{2k}{P}\right)}^{\left(P-2k+\frac{1}{2}\right)}}.$$
Figure 3
illustrates the values that (13) gives for different values of PO. This figure shows that for different values of key pool size, by storing a few keys in each node, there is a high probability that there is a shared key between each pair of network nodes.
Probability of existence of at least one shared key between every pair vs. key ring size.
Next, the resilience of the key pool technique is examined against node capture attacks. For this purpose, we need to answer the following question: given two uncompromised nodes, one from network A and one from network B, what is the probability that an intruder can decrypt any form of communication between the two nodes by means of only the information that is acquired through the captured nodes?
Let xx be the number of captured nodes. Each node contains
k
keys; thus, the probability that a specific key is not compromised is
Compromised link ratio vs. number of captured nodes.
The resilience of the key pool technique can be investigated from the point of view of an intruder; that is, how many network nodes should be captured, on average, so that the intruder can eavesdrop all network links with probability pp? To answer this question, 1 −
Number of captured nodes required for an intruder to eavesdrop on any link with a given probability.
After discussing both the applied prospects and the security prospects of the key pool technique, the efficiency of it should be investigated. This technique is simulated in a real network scenario to examine its efficiency. Networks with 10, 20, 30, 40, and 50 nodes are selected. For each scenario, the parameters of the key pool technique are chosen in such a way that a given network is always almost certainly connected. Furthermore, each scenario is simulated for a fully connected network to show an upper bound of this technique.
Table 1
illustrates the simulation parameters. The average time that is required for transmission of key identifiers and node ID is measured. The OPNET Modeler 14.5 is used for the simulations. The key load is simulated in Application layer and as an Application Demand. Network nodes are simulated in a wireless LAN workstation. These nodes utilize an antenna with 0.8 mW transmission power and −95 dB gain. The MAC and physical-layer protocols are 802.11b with 2 Mbps bitrate and direct sequence mode, respectively. The simulated nodes are mobile with 5 m/s velocity and 10 s pause time. They move on random patterns.
Figure 6
illustrates the required time for the key discovery phase. Note that in this simulation only key identifiers, node IDs, and routing information are sent. This figure shows that the required time is within a reasonable bound, and due to the fact that these operations would take place just once, it will not drastically affect the network performance. Using
k
keys in each node increases not only system reliability but also system cost. So, there exists a tradeoff between system reliability and communicational cost. However, an almost-certainly-connected network is enough in the case of our proposed method, but a network with high communicational capabilities may afford communicational cost. To investigate the effects of communicational capabilities on the required time for the key discovery phase, simulations are repeated for different bitrates.
Figures 7
and
8
illustrate the required time for different network sizes.

Required time to discover shared key vs. different network sizes.
Required time to discover shared key for different bitrates with key ring size k .
Required time to discover shared key for different bitrates with key ring size k' .
Required time to generate master key in distributed fashion.
Required time to generate master key for different bitrates.
To compare the key pool and pairing-based techniques, the required time for setting up a secure link is illustrated in
Fig. 11
. The figure shows that the pairing-based method and key pool with key ring size of
k
require almost equal amounts of time. However, the pairing-based method does not require key pre-distribution and storage and nodes can create a shared key on demand. Albeit, the pairing-based method seems to be an easy choice, but it is computationally more aggressive due to the bilinear mapping that it uses. However, the key pool technique needs fewer computations. Of course, pairing algorithms improve gradually; for example, recently an FPGA-based method was proposed
[17]
, but it is not applicable to less capable nodes, and the key pool technique is a good alternative.
Comparing required time to discover shared key using key pool method with time needed to agree on a key using pairing-based method.
The DLP is hard in
G
_{1}
; thus, it is infeasible to extract master private keys using a finite number of public/private key pairs. In other words, an intruder cannot determine the private key of an uncompromised node using the public/private keys of compromised nodes. Therefore, the proposed method is resilient against node capture.
A. Confidentiality
The confidentiality of key shares is guaranteed through two different techniques — key pool method and pairing-based method.
Key pool method
. In this method, initial network nodes exchange key identifiers through public channels. In this stage, nodes may use puzzles (for an example, see
[23]
) to ensure that only privileged nodes (nodes that already have possession of a key) can understand a key pattern. For example, each node broadcasts
α
and
E_{Ki}
(
α
), where
α
is a random challenge and
K_{i}
for
i
=1, 2, ... ,
k
represents all of the keys in the key ring of the node. Decryption of
E_{Ki}
(
α
) using the right key unveils
α
and establishes a shared key with the transmitter
[23]
. After the shared-key discovery phase, nodes share pair-wise common secrets; thus, they can use these secrets to encrypt the outgoing messages. According to assumption 1, the messages that are encrypted by these keys (for example, master key sub-shares or private key shares) are confidential. When the IBC system is deployed using secure links, all of the following transmissions between nodes that have got their private key are encrypted by the IBC system.
Assumption 2 guarantees the confidentiality of transmitted data, since it guarantees the security of the deployed IBC system.
Pairing-based method
. In this method, initial network nodes broadcast their own temporary public keys without any encryption. Two nodes that know the public key of each other can establish a secure channel and agree on a common key without any further communication. According to assumption 2, an intruder cannot decrypt the encrypted data even if it knows the public keys of both nodes. Furthermore, assumption 1 guarantees the confidentiality of messages that are encrypted using an agreed key. These secure links are used for the transmission of master key sub-shares and private key shares. After deployment of the IBC system, confidentiality of communication is guaranteed, as explained in the key pool method.
B. Integrity
When the IBC system is deployed, transmitted messages are encrypted and signed using the public key of the recipient and the private key of the sender, respectively. Any malicious modifications to a transmitted message can be detected by a recipient using the digital signature of the transmitter. Therefore, the integrity of information is guaranteed. Though, before the deployment of the IBC system, there is no signature system and therefore integrity of information is not guaranteed.
C. Authentication
The messages that are sent using the IBC system are authenticated because they are signed by a digital signature that only the owner of a specific private key (sender) can generate. An intruder cannot extract the private key of a node using its public key (assumption 2); thus, it cannot generate a valid signature for a forged message. Therefore, the authentication of messages is guaranteed. Of course, the proposed methods are not authenticated before the deployment of the IBC system, since there is no signature scheme.
D. Data Freshness
The
freshness
of signed messages can be guaranteed by using a time stamp; hence, out-of-order or replayed messages can be detected. However, the freshness of unsigned messages is not guaranteed; actually, this fact can be neglected, since these messages are used at the network formation stage.
E. Non-repudiation
The owner of a specific private key only can generate a valid signature. So, existence of a valid digital sign on any message declares the source of the message. Therefore, a node cannot deny its sign; hence, the proposed system is non-repudiation. However, non-repudiation only applies to messages that are sent after deployment of the IBC system; before this, there is no signature mechanism to create a non-repudiation system.

Corresponding Author k.adlimehr@tabrizu.ac.ir
Kamal Adli Mehr is currently a PhD candidate at the University of Tabriz, East Azerbaijan, Iran. He received his BS degree in electrical engineering (communication systems) and his MS degree in communication systems from the University of Tabriz, in 2011 and 2013, respectively. His current research interests include network security, secure communication, cryptography, and wireless communication systems.
niya@tabrizu.ac.ir
Javad Musevi Niya received his BS degree in electrical engineering from the University of Tehran, Iran and his MS and PhD degrees in communication systems from Sharif University of Technology, Tehran and the University of Tabriz, East Azerbaijan, Iran, in 1988, 1991, and 2006, respectively. Since September 2006, he has been with WiLab, the Faculty of Electrical and Computer Engineering, University of Tabriz. His current research interests include wireless communication systems, multimedia networks, and signal processing for communication systems.
Zhang Y.
2006
“Securing Mobile Ad Hoc Networks with Certificateless Public Keys,”
IEEE Trans. Dependable Secure Comput.
3
(4)
386 -
399
** DOI : 10.1109/TDSC.2006.58**

Identity-based cryptography
;
threshold cryptography
;
pairing-based cryptography
;
key pool
;
security-routing interdependency

I. Introduction

Security of mobile ad hoc networks (MANETs) remains a major concern in both academia and industry. Despite years of research, there is no mature solution to the problem of security of MANETs that is widely accepted, and the growing availability of small, personalized mobile devices with peer-to-peer communication capability through wireless channels makes this problem even more important.
Proven security mechanisms that are widely used in wired networks are not always applicable to MANETs. Detectable intrusions in wired networks have caused big security challenges in MANETs.
W. Li and A. Joshi
[1]
completely characterized MANETs and discussed their pros and cons. Of the characteristics described in
[1]
, the following make it particularly difficult to achieve security requirements: there is no network infrastructure or online administration available; dynamic network topology and node membership mechanism; possibility of an insider attack; constrained computational and communicational resources; and vulnerabilities of wireless channels. Due to the aforementioned characteristics, new security methods that are proposed for use with MANETs are required to guarantee availability, authentication, confidentiality, integrity, and so on
[1]
–
[2]
.
Early security proposals in MANETs were designed to combat specific kinds of security attacks. These early proposals often recommended solutions that were designed to target several security attacks (including the specific kind of security attach being addressed at the time) at once. Such solutions would work well against designated attacks but would still be vulnerable to collapse under combined or unanticipated attacks.
Later security proposals incorporated cryptography into their general design framework to achieve a general sense of security. There are two main categories of cryptography techniques used in MANETs — symmetric key and asymmetric key.
Identity-based cryptography (IBC) is a subclass of public key cryptography. IBC was designed to eliminate the need for a certification authority (CA) and public key certificates (PKCs)
[3]
. IBC was first proposed by A. Shamir
[4]
in 1984. In IBC, for a given user, both the user’s public key and the user’s private key are based on the identity of the user. In an IBC scheme, a user’s public key is an easily calculated function of their identity (for example, the user’s IP address, phone number, or e-mail address), while a user’s private key can only be calculated by a trusted authority — that is, a private key generator (PKG). In comparison with a traditional public key infrastructure (PKI), an IBC is not required to store and transmit large volumes of public keys and certificates; thus, it is a far more attractive option to be used in MANETs.
In this paper, two novel methods are proposed to eliminate the interdependency cycle between secure routing and security services. One of these methods utilizes a key pool to construct secure routes for the distribution of cryptographic materials, while the other one is based on pairing-based key agreement. Furthermore, the proposed methods utilize threshold cryptography for shared secret and private key generation to eliminate the single point of failure and distribute cryptographic services among network nodes. These characteristics guarantee high levels of availability and scalability for the proposed methods.
The rest of this paper is organized as follows. Section II provides some related work. Section III gives the detailed procedure of the proposed methods. The simulation results and discussions are presented in Section IV. Finally, Section V concludes the paper.
II. Related Work

Designing efficient key management (KM) mechanisms is of paramount importance to those aiming to provide security services in MANETs, because security services that employ cryptographic techniques rely on such mechanisms. KM is the process that specifies how to distribute cryptographic keys to network nodes and update (if required), revoke, and so on such keys
[5]
. There is a rich literature on KM methods. Investigations by the authors in
[6]
, within those publications that were available to them, have led to the classification of the current KM protocols into the following subsets: partially distributed certificate authority, fully distributed certificate authority, identity-based KM, certificate chaining-based KM, cluster-based KM, predeployment-based KM, mobility-based KM, and parallel KM. Each of these categories has its own pros and cons, but as mentioned in
[7]
, the spectacular characteristics of IBC make it an ideal choice for utilization in MANETs. Some of these characteristics are mentioned in the following. First, IBC does not utilize certificates; hence, there is no need for certificate distribution and verification, which saves on communication and computation overheads (especially in large-scale MANETs). Second, IBC offers non-interactive key agreement. Finally, the public keys provided by IBC are self-proving and can carry much useful information.
KM in IBC consists of key generation and distribution methods and, ideally, key protection and revocation. There is rich literature about KM using IBC
[8]
–
[19]
. Most of the schemes within these literatures are derived from and are variants of
[20]
and are thoroughly investigated in
[3]
. These schemes suffer from some common drawbacks. For example, suppose a node in a network can communicate with a PKG to obtain its private key; then, a major problem is the secure transmission of the private key from the PKG to the requesting node.
In the aforementioned proposals, there are no shared secrets between PKGs and nodes (that is, common symmetric keys), nor do nodes have public/private key pairs. Therefore, it is not exactly determined how a node should obtain its private key from a PKG in the presence of an intruder. This problem can only be solved by means of a secure channel or pre-distributed common keying material, neither of which is ideal in ad hoc networks
[6]
. Furthermore, the aforementioned proposals have a common problem — security-routing interdependency
[9]
. In these approaches, KM relies on secure routing to establish secret keys, while behind such secure routing is the assumption that secret keys are pre-deployed to set up a routing table.
Recently, S. Zhao and others
[21]
proposed a KM and secure routing (KM-SR) integrated framework that utilizes system parameters of IBC to derive node-specific broadcast keys. In this proposal, public channels are used to distribute system parameters to authenticated nodes. The integrated node-specific broadcast keys are generated, and secure routing is set up by means of system parameters. The authors of
[21]
claim that because the authenticated distribution of system parameters and routing setup are all carried out through public channels and generation of integrated node-specific broadcast keys does not require any extra communication between nodes, there is no KM-SR interdependency cycle. However, despite the fact that the proposed method in
[21]
utilizes the novel idea of a KM-SR integrated framework, it cannot satisfy the required conditions of an appropriate KM system for MANETs. The major problem of this method is its deployment of a centralized PKG. Although, this avoids the problems that are caused by threshold cryptography, the fact still remains that the centralized PKG can be a single point of failure and an ideal target for intruders. Furthermore, the deployment of a centralized PKG reduces the scalability of the system; thus, the use of this method in large-scale networks is infeasible. This method also lacks any sort of revocation or key update mechanism. The proposed method in
[21]
is an ideal choice for trusted and authenticated networks that have a trusted authority to act as a PKG; however, this cannot take away the fact that it fails to meet the security requirements of MANETs.
III. Proposed Methods

The proposed methods in this paper consist of the following five stages: initialization, shared secret generation, distributed master-key generation, private-key generation, and generation of a new master key for new-comer nodes and existing nodes that want to become a new PKG (
Fig. 1
). These methods utilize a key pool and pairing-based key generation techniques to eliminate the KM-SR interdependency cycle. To distribute a PKG task among network nodes, A. Shamir’s
[22]
secret-sharing technique, with some slight modifications to it, is used.
PPT Slide

Lager Image

- 1. Initialization Phase

Let
E/ F p

an elliptic curve of the form
F p

. Let
F p 2 *

. It is assumed that the discrete logarithm problem (DLP) is hard over both
- ■Bilinear. Thee:G1×G1→G2mapping isbilinearif for allP,Q∈G1, anda,b∈Zequatione^(aP,bQ) = e^(P,Q)abholds.
- ■Non-degenerate. The mapping does not transform all the possible values ofG1×G1to the identity. Note that becauseG1andG2are prime groups, non-degeneracy implies that ifPis a generator ofG1, thene^(P,P)is a generator ofG2.
- ■Computable. For all possible values ofP,Q∈G1, there is an efficient algorithm to computee^(P, Q).

e ^

is bilinear and that
e ^

is symmetric; that is, for all
e ^ (P,Q)= e ^ (Q,P)

holds. Examples of such bilinear maps are the modified Weil pairing and the Tate pairing, for which the bilinear Diffie–Hellman problem (BDHP) is believed to be hard
[17]
. The algorithm 𝒢 that is used to generate pairing parameters acts as follows:
- For security parameterk∈Z+as its input, 𝒢 generates a prime number (q);G1andG2(of orderq); and an admissible bilinear mape^:G1×G1→G2according to the above constraints.
- Generate the hash functionH1: {0, 1}*→G1.
- ChoosePas the generator ofG1.
- Public system parameters 〈P,q,e,H1,G1,G2〉 are available from the beginning for all.

- 2. Shared Key Generation

To operate properly in MANETs, IBC relies on a shared-key generation phase. In this phase, network nodes that have never met develop a shared key, and based on this shared key, further secure communications become feasible. For this phase, we developed two fundamentally different methods to achieve this goal. One of these methods is based on a key pool and uses several large pools of keys that are implemented in network nodes, whereas the other method generates a shared key based on public system parameters.
- ■ Offline authorityAgenerates a large pool ofKkeys and their corresponding key identifiers.
- ■ For each node,Arandomly selectskkeys without replacement and preloads them along with their respective key identifiers. These keys then form a key ring.

- ■ Each nodeCichooses a random valuesi0∈Zqand then calculatesPipub0=si0P.
- ■ ThenCibroadcastsPipub0to its neighbors.
- ■ NodeCican encrypt its data usingkij0=e^(si0.Pjpub0,P). It can then send the encrypted data toCj.
- ■ NodeCjcan decrypt the encrypted data bykji0=ê(sj0.Pipub0,P).

k ij 0 = k ji 0

. This can be proved by manipulating the properties of the admissible bilinear mapping.
- 3. Distributed Master-Key Generation

The proposed master-key generation mechanism does not rely on a trusted third party to securely generate a master key, divide a master key into shares, and distribute the shares among PKGs. A master key is calculated in a distributed fashion through the collaboration of
- ■ NodeCichooses two secrets,xiandx¯i, and polynomialsfi(z) andf¯i(z)of orderk− 1 overZqin such a way thatfi(0) =xiandf¯i(0)=x¯i.
- ■ NodeCicalculates the sub-share of nodeCjusingssij=fi(j) andss¯ij=f¯i(j)forj= 1,2, ... ,nand sends them toCjthrough the secure channels that are established in the shared-key generation phase.
- ■ After reception ofn− 1 sub-shares,Cjcan calculate its own share of the master private key usingSj=∑i=1nssij=∑i=1nfi(j)andS¯j=∑i=1nss¯ij=∑i=1nf¯i(j); that is, the master-private-key share of nodeCjis a combination of all received sub-shares from the initialnnodes.

∑ i=1 k S i l i ( z )mod q

and
∑ i=1 k S ¯ i l i ( z )mod q

, in which
SK= ∑ i=1 n x i = ∑ i=1 n f i ( 0 )

and
SK ¯ = ∑ i=1 n x ¯ i = ∑ i=1 n f ¯ i ( 0 )

; although, they are not reconstructed in any single node.
- 4. Private-Key Generation

The mechanism that is used for identity-based public/private-key generation for each node
〈 K C i , p m , K C i , p m −1 〉

. Each of
K C i , p m

and
K C i , p m −1

is comprised of both a node-specific element and a phase-specific element. Furthermore, similar to
[11]
and unlike common IBC systems, a node-specific public key, and subsequently a private key, is a function of a node ID and MAC address so as to bind the identity of the node to its MAC address, which is assumed not to change during the lifetime of a network. The public/private key pair is calculated by
SK ¯

; these are parameters that should not be reconstructed in any single node. Instead, to calculate a private key in a distributed fashion, the requesting node communicates with
k ji, p m −1 = f extract ( S j , S ¯ j ,( ID C i ∥ MAC C i ), salt m )=( S j K C i , S ¯ j K p m )

and sends it to
S ¯ j

are master private key shares of
〈 K p m , K p m −1 〉

are public/private key elements corresponding to phase
〈 K C i , K C i −1 〉

are public/private key elements corresponding to node
- 5. Generating New Master Key Share

Nodes in an ad hoc network may leave the network or enter it randomly; subsequently, this may mean that the number of PKGs in the network at any one time is less than a certain threshold value (
- ■ The lifetime of the node must be more than a constant valueT, whereTis an adequate period of time.
- ■ The node must be well behaved throughout its lifetime; that is, it must not be found to be on a black list.
- ■ The node must have enough capabilities, such as computational, communicational, and energy, to act as a PKG.

- The nodeCyrequestskPKGs to become a new PKG. The requesting node signs and encrypts the request with its own private keyKCy,pm−1and the public key of PKG 𝒦Ci,pm, respectively. Then it sends it to the corresponding PKG.
- When theith PKG receives the request, it investigates the conditions of the requesting node. IfCymeets the required constraints to be a PKG, then theith PKG calculates ssiyandss¯iy, using (5) below, and sends them toCy.

ss ¯ iy

, the ss'
ss ¯ ' iy

shares are obtained. Now, they are signed and encrypted, using the private keys of PKGs and the public key of the requesting node, respectively, and then sent to the requesting node.
Once the requesting node receives
IV. Simulation Results and Discussion

In this section, our proposed methods are investigated and simulated in real network conditions.
- 1. Key Pool

The key pool technique is more robust than both those techniques that utilize a single key for all communications and those that use pair-wise private keys, because under node capture attacks, in the former case, all of the links between nodes are compromised, while in the latter case, all of the
- ■ What is the expected value ofdnrequired to set up a connected network ofnnodes?
- ■ According todnand wireless network constraints, what is the appropriate key ring sizekand key pool size PO for a network ofnnodes?

PPT Slide

Lager Image

p ′ ck = d n ( n ′ −1) ≫ p ck

. So, the probability that two network nodes, with a key ring size of
P! k!(P−k)!

. After the formation of the first key ring, the number of possible key rings that do not share a common key with the first key ring is
(P−k)! k!(P−k)!

; that is, the number of key rings that are formed from the remaining (
PPT Slide

Lager Image

( 1− k P ) xx

. Therefore, the probability that a link is compromised is 1 −
( 1− k P ) xx

. In fact, this equation shows the additional information that an intruder obtains by capturing xx nodes.
Figure 4
shows this parameter as a function of xx for different key ring size to key pool size ratios. Note that in this figure, the horizontal axis shows the total number of captured nodes, while the vertical axis shows the ratio of compromised links in the network.
PPT Slide

Lager Image

( 1− k P ) xx

is used. It can be written as
xx =ln(1−pp) / ln( 1− k P )

by slight modifications.
Figure 5
depicts the average number of captured nodes required for an intruder to eavesdrop on any link as a function of pp, for different key ring size to key pool size ratios.
PPT Slide

Lager Image

Parameters of simulated networks.

Scenario | Number of network nodes ( | Probability of network connectivity (_{c} | Key pool size (PO) | Key ring size ( | Required number of neighbors ( | Required key ring size ( |
---|---|---|---|---|---|---|

1 | 10 | 0.99 | 1,000 | 34 | 9 | 95 |

2 | 20 | 0.999999 | 2,000 | 60 | 19 | 136 |

3 | 30 | 0.999999 | 5,000 | 65 | 29 | 218 |

4 | 40 | 0.999999 | 10,000 | 76 | 39 | 310 |

5 | 50 | 0.999999 | 20,000 | 94 | 49 | 377 |

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- 2. Master Key Generation

The required time for master key generation in a distributed fashion has a significant impact on overall system performance, because a master key is significant to other cryptographic operations. The initial network nodes generate a master private key by sending master key subshares to shareholders.
Figure 9
illustrates the required time for distributed master key generation as a function of network size. In this figure, the plot of required time for the TIDS method
[11]
is depicted for the sake of comparison; the “required time” results of the simulations of the TIDS method are given for a 2 Mbps bitrate. Note that the additional cost of the proposed method is due to its additional security, since it generates two master keys; one for node-specific keys and another for phase-specific keys. This method greatly simplifies the key update and key revocation procedure.
PPT Slide

Lager Image

- 3. Pairing-Based Key Agreement

The second proposed technique to set up secure links between network nodes for transmission of master key and private key shares is pairing-based key agreement. In this method, it is necessary that each node broadcasts its self-generated temporary public key. Again, the prominent factor is required time. To measure the required time, different network sizes are simulated.
Figure 10
illustrates the required time for pairing-based key agreement as a function of network size for different bitrates.
PPT Slide

Lager Image

PPT Slide

Lager Image

- 4. Security of Proposed Methods

The proposed security method utilizes a symmetric key method; for example, AES, to encrypt confidential data of IBC methods. The security requirements of a MANET depend on its cryptography system. In this section, the security features of the proposed method are investigated. The following assumptions are made for this purpose:
- ■ The deployed symmetric key (for example, AES) is robust enough against intruders that do not have the encryption key.
- ■ The BDHP over (G1,G2,e^) is hard enough; that is, by knowingP,aP,bp,cP∈G1, in whicha,b,c∈Zq*, there is no efficient algorithm to calculatee^(P,P)abc∈G2.

- 5. Future Work

Although the proposed methods offer data confidentiality before the deployment of an IBC system, they lack authentication, integrity, and so on. Therefore, they are still vulnerable to some form of attacks. It is recommended to investigate possible techniques to solve this problem. Certificate chaining methods
[6]
seem to be a good option for this purpose. Investigating the performance of the proposed methods in real nodes is also of great interest. As the next step, implementing a secure routing method based on the proposed methods is suggested.
Comparison of existing and proposed methods.

Pulse | KM-SR | Integrity | Availability | Scalability |
---|---|---|---|---|

Proposed method in | Yes | — | Good | Average |

Proposed method in | Yes | No | Good | Good |

Proposed method in | Yes | No | Good | Good |

Proposed method in | Yes | No | Good | Good |

Proposed method in | Yes | Yes | Good | Good |

Proposed method in | No | No | Bad | Bad |

Proposed key pool-based method | No | No | Good | Good |

Proposed pairing-based method | No | No | Good | Good |

V. Conclusion

Security of MANETs is still a great challenge for researchers. Recently, security proposals that utilize IBC offered promising insights in how to tackle certain security problems. Despite these efforts, these proposals are not designed for truly ad hoc environments. Most commonly, they usually suffer from a security-routing interdependency cycle. In this paper, two novel methods were proposed to eliminate the interdependency cycle between secure routing and security services. One of these methods utilizes a key pool to construct secure routes for the distribution of cryptographic materials, while the other is based on pairing-based key agreement. Furthermore, the proposed methods utilize threshold cryptography for shared secret and private-key generation to eliminate the single point of failure and distribute the cryptographic services among network nodes. These characteristics guarantee high levels of availability and scalability for the proposed methods. To illustrate the effectiveness and capabilities of the proposed methods, they were simulated and compared with existing methods. Our simulation results showed that the proposed methods are well-suited for ad hoc environments. Also, these methods offer an acceptable degree of security for a MANET environment.
BIO

Li W.
,
Joshi A.
2008
Security Issues in Mobile Ad Hoc Networks - A Survey
Department of Computer Science and Electrical Engineering, University of Maryland
Baltimore County
1 -
23

Djenouri D.
,
Khelladi L.
,
Badache N.
2006
“A Survey of Security Issues in Mobile Ad Hoc and Sensor Networks,”
IEEE Commun. Surveys Tutorials
7
(4)
2 -
28

Zhao S.
2012
“A Survey of Applications of Identity-Based Cryptography in Mobile Ad-Hoc Networks,”
IEEE Commun. Surveys Tutorials
14
(2)
380 -
400
** DOI : 10.1109/SURV.2011.020211.00045**

Shamir A.
1985
“Identity-Based Cryptosystems and Signature Schemes,”
Springer Berlin Heidelberg
Advances in Cryptology
Berlin, Germany
47 -
53

Fan X.
2010
“Efficient Cryptographic Algorithms and Protocols for Mobile Ad Hoc Networks,” Ph.D. dissertation
University of Waterloo
Ontario, Canada

Merwe J.V.D.
,
Dawoud D.
,
McDonald S.
2007
“A Survey on Peer-to-Peer Key Management for Mobile Ad Hoc Networks,”
ACM Comput. Surveys
39
(1)
1 -
23
** DOI : 10.1145/1216370.1216371**

Zhang Y.
2006
“Securing Mobile Ad Hoc Networks with Certificateless Public Keys,”
IEEE Trans. Dependable Secure Comput.
3
(4)
386 -
399
** DOI : 10.1109/TDSC.2006.58**

Khalili A.
,
Katz J.
,
Arbaugh W.A.
“Toward Secure Key Distribution in Truly Ad-Hoc Networks,”
Proc. Symp. Appl. Internet Workshops
Orlando, FL, USA
Jan. 27–31, 2003
342 -
346

Bobba R.B.
“Bootstrapping Security Associations for Routing in Mobile Ad-Hoc Networks,”
IEEE Global Telecommun. Conf.
San Francisco, CA, USA
Dec. 1–5, 2003
3
1511 -
1515

Deng H.
,
Mukherjee A.
,
Agrawal D.P.
“Threshold and Identity-Based Key Management and Authentication for Wireless Ad Hoc Networks,”
Proc. IEEE Int. Conf. Inf. Technol.: Coding Comput.
Las Vegas, NV, USA
Apr. 5–7, 2004
1
107 -
111

Deng H.
,
Agrawal D.P.
2004
“TIDS: Threshold and Identity-Based Security Scheme for Wireless Ad Hoc Networks,”
Ad Hoc Netw.
2
(3)
291 -
307
** DOI : 10.1016/j.adhoc.2004.03.005**

Zhang Y.
“Identity-Based Threshold Key Management for Ad Hoc Networks,”
Pacific-Asia Workshop Comput. Intell. Ind. Appl.
Wuhan, China
Dec. 19–20, 2008
2
797 -
801

Xia P.
“Identity-Based Fully Distributed Certificate Authority in an OLSR MANET,”
Int. Conf. Wireless Commun., Netw. Mobile Comput.
Dalian, China
Oct. 12–14, 2008
1 -
4

Li G.
,
Han W.
“A New Scheme for Key Management in Ad Hoc Networks,”
Netw.-Int. Conf. Netw.
Reunion Island, France
Apr. 17–21, 2005
242 -
249

Zhang Y.
“AC-PKI: Anonymous and Certificateless Public-Key Infrastructure for Mobile Ad Hoc Networks,”
IEEE Int. Conf. Commun.
Seoul, Rep. of Korea
May 16–20, 2005
5
3515 -
3519

Ren Y.
“Identity-Based Key Issuing Protocol for Ad Hoc Networks,”
IEEE Int. Conf. Comput. Intell. Security
Harbin, China
Dec. 15–19, 2007
917 -
921

Lee B.
2004
“Secure Key Issuing in ID-Based Cryptography,”
Australian Computer Society Inc.
Proc. Workshop Australasian Inf. Security, Data Mining Web Intell., Softw. Int.
Australia
32
69 -
74

Saxena N.
2006
“Public Key Cryptography Sans Certificates in Ad Hoc Networks,”
Springer Berlin Heidelberg
Appl. Cryptography Netw. Security
Berlin, Germany
375 -
389

Boneh D.
,
Franklin M.
2001
“Identity-Based Encryption from the Weil Pairing,”
Springer Berlin Heidelberg
Adv. Cryptology
Berlin, Germany
213 -
229

Zhao S.
,
Kent R.
,
Aggarwal A.
2013
“A Key Management and Secure Routing Integrated Framework for Mobile Ad-Hoc Networks,”
Ad Hoc Netw.
11
(3)
1046 -
1061
** DOI : 10.1016/j.adhoc.2012.11.005**

Shamir A.
1979
“How to Share a Secret,”
Commun. ACM
22
(11)
612 -
613
** DOI : 10.1145/359168.359176**

Eschenauer L.
,
Gligor V.D.
2002
“A Key-Management Scheme for Distributed Sensor Networks,”
ACM
Proc. ACM Conf. Comput. Commun. Security
USA
41 -
47

Spencer J.
2001
“The Strange Logic of Random Graphs,”
Springer-Verlag Berlin Heidelberg
Berlin, Germany

Citing 'Securing Mobile Ad Hoc Networks Using Enhanced Identity-Based Cryptography
'

@article{ HJTODO_2015_v37n3_512}
,title={Securing Mobile Ad Hoc Networks Using Enhanced Identity-Based Cryptography}
,volume={3}
, url={http://dx.doi.org/10.4218/etrij.15.0114.0195}, DOI={10.4218/etrij.15.0114.0195}
, number= {3}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Mehr, Kamal Adli
and
Niya, Javad Musevi}
, year={2015}
, month={May}