AIRCC PUBLISHING CORPORATION
Node Authentication Using BLS Signature in Distributed PKI Based MANETS
N Chaitanya Kumar, Abdul Basit, Priyadarshi Singh, V. Ch. Venkaiah, and
Y. V. Subba Rao
School of Computer and Information Sciences, University of Hyderabad,
Authenticating a node in mobile ad-hoc networks is a challenging task due to their dynamic and resource constraint infrastructure. For this purpose, MANETS adopt two kinds of approaches Public key cryptography and identity based cryptography. In Public Key Infrastructure (PKI), Certi cate Authority (CA) is responsible for key management. In order to adopt it to MANET, the job of the CA must be distributed. The master secret key is shared among the nodes of the MANET, to self-organize the network without a central authority.The key is shared based on Shamir secret sharing scheme with bi-variate polynomial to make the MANET fully self-managed by nodes.In this paper, we considered PKI based scenario and proposed a new scheme to authenticate a node using BLS signature which is light weight compared to the existing schemes thus making it suitable for MANET.
Mobile ad-hoc network, bi-variate polynomial, secret sharing technique, threshold cryptography, BLS signature.
MANET known as Mobile Ad-Hoc Network is a self-organized, dynamic and infra-structureless network. MANET consists of mobile nodes that roam freely, every node has its own range of signal communication, other nodes within the range can interact and exchange messages. New nodes join and some other nodes may leave or some nodes fail to connect as they move out of the MANET network range. The nodes in MANET are energy constrained, i.e., nodes are battery powered devices. There are many security threats to MANETS such as Denial of service, eavesdrop-ping, interception and routing attacks . Public Key Infrastructure (PKI) helps in securing communication using authentication and encryption through dig-ital certi cates and public key cryptography respectively.The distributed PKI ap-proach is adopted in this paper so as to make the MANET network completely de-centralized.
Generally in a PKI environment, a certi cate authority(CA) issues and manages the public key certi cates of participating entities, the CA uses a master secret key s to sign the certi cate. General PKI is not suitable for MANET as we cannot assign the sole power of CA to a single node because of its dynamic and chang-ing topology i.e., the node with CA functionality may break-down or move out of MANET range, which results in non-availability of CA. To achieve the distributed PKI environment for MANETS, we use a (t,n) threshold scheme, which helps in distributing CA power, i.e., we have to distribute the master secret key s to nodes of the MANET. In our proposal, we discuss how a threshold number of nodes sign a certi cate and the veri cation of the certi cate can be done by any node using BLS signature scheme.
1.1 Attacks on MANETS
In MANETS, there are two types of attacks- Passive and Active. Passive attacks capture valuable data in transit and active attacks cause huge damage to the net-work by disrupting the normal ow of the operations. Malicious nodes cause both active and passive attacks. A malicious node is the one, which does not authenticate itself to other honest nodes and misbehaves in the network. An honest node can also be compromised if it is under the control of the attacker. As the network comprises of layers of protocols, the attacks are speci c to a layer and the security should also be implemented in the corresponding layer. Since the mobile nodes share a wireless medium, the messages transmitted can eavesdrop or fake messages may be injected at physical layer. Because of one-hop connectivity maintained among neighbors, the attacker can launch tra c analysis and tra c monitoring attacks. In network layer, the attacker exploits the routing algorithms to create routing hops and network congestion. The attacker uses a compromised node to perform SYN ooding and denial of service(DOS) attacks at transport layer. The majority of attacks in the application layer are worm attacks, mobile viruses and repudiation attacks. Some attacks like denial of service and man-in-the-middle can be launched from several layers. This paper proposes node authentication using BLS signature, so that many of the attacks can be avoided.
1.2 Distributed PKI
Public key cryptography(PKC) provides many security services like con den-tiality, integrity, authentication, non-repudiation, encryption and digital signatures. Public key infrastructure(PKI) manages digital certi cates which are important in the deployment of public key cryptography. In PKI environment, Certi cate authority(CA) issues and maintains the certi cates of participating entities, the certi cate contains the public key and the ID of the entity, the CA signs the certi – cate using the master secret key s and this certi cate can be veri ed by the master public key P K. In MANETS we cannot adopt the same PKI, as the network is dynamic and infrastructure-less. So the role of the CA needs to be distributed to the nodes i.e., the master secret key s is to be shared among di erent nodes and the master secret key can only be generated if atleast the threshold number of shares of secret are pooled together.
1.3 Threshold Cryptography
As MANET is a decentralized network, the master secret key (s) of the PKI is distributed among the nodes using secret sharing schemes. One of the popular and most widely used secret sharing technique is the Shamir’s secret sharing tech-nique. In this scheme, dealer distributes a secret s among n users. Each user receives it’s share privately from the dealer. To reconstruct a secret, it uses (t,n) threshold access structure, where t out of n shares are required. Shamir’s se-cret sharing scheme can be adopted in MANETS. Even the role of the dealer can be played by the nodes of MANET itself. This is achieved by using a bi-variate polynomial. This is discussed in section 3:1.
1.4 Related work
One common issue faced by MANET when applying cryptography is, how to dis-tribute the role of CA or trusted authority, many proposals use secret sharing technique to distribute secret key s of CA or trusted authority to secure MANET. Zhou and Haas were the rst to propose distributed CA for MANETS. They used threshold cryptography to distribute the role of the Certi cation Authority (CA) in a PKI scenario among a set of selected servers. However, this proposal is not suitable for a purely ad-hoc environment as these selected nodes may not al-ways be available. Kong et al. adapted a similar idea to distribute trust among all the nodes. However, their speci c RSA threshold scheme has been proved in-secure. Shamir secret sharing technique is the most widely used secret sharing technique. We show that Shamir secret sharing technique along with the use of bi-variate polynomial helps to distribute the secret of CA among all nodes of MANET. In other works, bi-variate polynomials have already been used to dy-namically allow new nodes joining the network without the need of any external trusted party. This technique is the result of inspiration from the original work of. Anzai et al. and Herranz et al. constructed decentralized, exible, dynamic group key distribution schemes by using polynomials in two variables. The goal is to generate common group secret keys. Saxena et al. used similar technique to establish pairwise keys in a non-interactive way for a mobile ad-hoc scenario. Recently Daxing et al.  proposed aggregate signature algorithm for MANET using bilinear pairing and Hanaoka et al.  construct multi user setting signature with tight security based on BLS signature.
Our work is more related to the cryptographic techniques proposed for MANETs by Herranz et al. . They proposed a fully self managed MANET and the ways to authenticate communication among the nodes. Our paper proposes the node au-thentication in their set up using BLS signature proposed by Boneh et al.. Our proposal reduces the size of keys used as it uses the bilinear pairing. This scenario is much suitable for MANET because its nodes are mostly resource constraint devices and they can not a ord the heavy computational overhead required by larger keys.
2.1 Self-Organized PKI and Secret Sharing Technique
2.3 BLS Signature
This scheme was introduced by D. Boneh, B. Lynn, H. Schacham. It is based on Computational Diffie-Hellman assumption on certain elliptic curve. We discuss the Gap Die-Hellman Group where this signature scheme works.
3. Our proposal
This section is divided into four major phases namely Setup, Key Generation, Signature Generation Protocol and Signature Veri_cation Protocol.
In this phase every node ni receives partial share si of the MANET secret s. This is achieved using the following protocol.
Let n be the number of nodes in the MANET, t be the threshold and k be the founding number of nodes.The founding number of nodes are such t k n.
Every founding node chooses a bi-variate polynomial fi(x; z), symmetric in x; z and the max degree.
Every node ni computes fij(h(nj); z) for all other founding nodes and itself, 1 i k:
Now every node secretly sends computed fij(h(n); z) to corresponding node nj. Furthermore, node ni includes the value yi = fi(0) P in each of these messages.
Finally every node has values received from other founding nodes and also it’s own value fii(h(ni); z) with it.
Then every node ni computes fi(z) = f(h(ni); z) = j2kfji(h(ni); z).
Now every node ni has partial secret si = fi(0) and a secret equation f(h(ni); z).
The MANET secret function f(x; z) = i2nfi(x; z) and MANET secret key is s = f(0; 0) are safe and hidden.This secret information can only be reconstructed if and only if there are at-least t nodes having partial share of MANET secret. For a new node nw trying to join the network, it has to request at-least t nodes for the values fiw(h(ni); h(nw)). When t nodes accept the node nw request, then they send fiw(h(ni); h(nw)) to node nw. Now node nw has t values and these values are used in Lagrange’s interpolation to derive a secret polynomial corresponding to node nw, Lagrange’s interpolation is applied as follows:
3.2 Key Generation
After every node ni has received a partial secret si, now the nodes run RSA key generation protocol. The protocol is responsible for generating a public (pki) and private (ski) key pair. The private key (ski) is kept secret with the node ni and public key (pki) is made available to all other nodes. The public key pki is used to encrypt messages that are sent to node ni, and the node ni uses its private key ski to decrypt messages as well as to sign messages.
3.3 Signature Generation Protocol
Now every node ni has two secret keys namely partial secret key of MANET si and individual secret key ski, partial secret key is used to partially sign a certificate and any t out of n nodes are required to sign a certificate to generate fully signed/valid certificate. When a node ni wants to get a public key certificate, it asks its neighboring nodes to generate partial signature on the certicate linking ni||pki. If the node ni receives at-least (t-1) partial signs, then the node itself can generate a partial sign using it’s own partial share, now the node has t partially signed values, then it uses the following Lagrange’s interpolation to generate a fully signed certificate.
Now that every node obtains its certificate in the above described manner. Next we discuss the protocol to verify the certificate.
3.4 Signature Verification Protocol
In this paper, we proposed a new scheme of verifying a certi cate in decentralized PKI based MANETS. In our scheme the nodes of the MANET holds a secret share and every node chooses its own public and private keys. The public key is associated with the node identity in the certi cate. This certi cate management is done using BLS Signature. Our scheme uses a bivariate polynomial to reduce the communication overhead. The same technique can be used in performing other functionalities of MANET like implementing threshold operations in sub group nodes communication and share veri cation etc.
N Chaitanya Kumar received M.Tech from JNTU Hyderabad, and he did Bach-elor degree in computer science. Currently, he is pursuing his PhD in Computer Science from the University of Hyderabad. His research interests include Informa-tion security, Cryptography in MANET.
Abdul Basit received Master of computer application from Jamia Hamdard Uni-versity New Delhi. He did Bachelor of Science in Information technology from SMU Gangtok. Currently, he is pursuing his PhD in Computer Science from the Univer-sity of Hyderabad. His research interests include Information security, Cryptogra-phy, Cyber security, and Algorithms.
Priyadarshi Singh received M.Tech from IIT(ISM) Dhanbad. He did Bachelor degree in Information Technology. Currently, he is pursuing his PhD in Computer Science from the University of Hyderabad. His research interests include Cryptog-raphy, Public key infrastructure.
V .Ch. Venkaiah obtained his PhD in 1988 from the Indian Institute of Science (IISc), Bangalore in the area of scienti_c computing. He worked for several organisations including the Central Research Laboratory of Bharat Electronics, Tata Elxsi India Pvt. Ltd., Motorola India Electronics Limited, all in Bangalore. He then moved onto academics and served IIT, Delhi, IIIT, Hyderabad, and C R Rao Advanced Institute of Mathematics, Statistics, and Computer Science. He is currently serving the Hyderabad Central University. He is a vivid researcher. He designed algorithms for linear programming, subspace rotation and direction of arrival estimation, graph colouring, matrix symmetriser, integer factorisation, cryptography,knapsack problem, etc.
Subba Rao Y V obtained his PhD from the University of Hyderabad. Currently, he is an Assistant Professor in the School of Computer and Information Sciences, University of Hyderabad. His area of interests includes Cryptography, Theory of Computation, etc.