Identity Authentication and Key Agreement Schemesfor Ad Hoc Networks

Mohammad A AL-Fayoumiand Sattar J Aboud

Department of Computer Information Science

The Middle EastUniversity for Graduate Studies, Faculty of IT

Amman - Jordan

Abstract:Identityauthenticationandkey agreement schemes play significant role in ad hoc networks. In this paper, a new identity authentication schemerelies on the threshold group signature is introduced. Compared with the current schemes it is secure, efficient and adaptable to a multi-hop feature of ad hoc networks. In addition, a new key agreement schemebased on the threshold cryptography using the Lagrange interpolation theorem is suggested, its efficiency and security are examined, and is claimed to be more efficient than the existing schemes.

Key words: Ad hoc networks, key agreement, identity authentication, threshold group signature, multi-hop, shares key, identity certificate.

INTRODUCTION

An ad hoc network is often defined as an infrastructures network, denoting a network without the usual routing infrastructure like fixed routers and routing back-bourn(Yao and Zeng,2004,Mauve et al., 2001, Stjmenovic,and Lin, 2001).Mobile ad hoc networking offers convenient infrastructureless communication over the shared wireless channel (Jayakumar and Chellappan,2005). A group of networking devices communicates among one another using wireless radios and operates by following a peer-to-peer network model. The nature of such a network makes them vulnerable to security attacks. Examples of attacks include passive eavesdropping over the wireless channel, denial of service attacks by malicious users and attacks from compromised entities or stolen devices. Unlike wired networks where an opponent must gain physical access to the wired link or sneak through security holes at firewalls and routers, wireless attacks may come from anywhere along all directions(Luo et al.,2002). The infrastructureless ad hoc network will not have a clear line of defense, and eachuser must be prepared for encounters with an opponent. Therefore,a centralized or hierarchical network security solution(Aresenault and Turner, 2000) does not work well in mobile ad hoc networks.

Security is a crucial matter for ad hoc networks, especiallyfor security sensitive uses for example battleground. Ad hoc networks are usual dynamic peernetworks. The specificsecurity requirementsof dynamic peer networks such as key management are yet consideredas openresearchchallenges(Bettstetterand Friedrich,2003).Newly, a number of key agreement protocols regardingdynamic peer networks aresuggested. For examplethe key agreement protocolsthatare obtainedby extendedthe knownDiffie-Hellman key exchange scheme to groups ofnusers is described in(Ateniese et al., 1998). Two key agreement protocols relied on the threshold schemeemployingLagrange interpolation theorem,are introduced in(Desmedt,1994, Pieprzyk and Li, 2000). Anotherkey agreement protocol relied on the octopus schemeis presented in (Lang et al.,2003).

Identity authentication is another significant area of researchfor the security of ad hocnetworks. The valid certificate authority can efficiently stop the impersonationattacks.The centrally disciplinedtrust communications managedby a one certificate service is a specific point of failure. So we shouldemploy a distributed authority certificate in which the trust is managed by manyauthorities. The concept of distributing a certificate authorityall around the network ispresented in (Zhou and Hass, 1999,Luo et al.,2002). Theschemethat provided a method to authenticate the partitionedof ad hocnetworksis introducedin (Kaliaperumal,2003). Also an identificationprotocol issuggested in (Khalili et al.,2003)that allow efficient and flexible key distribution whilst respectingthe restrictions of ad hoc networks.

The objectives of this paper are:

  1. Introduce a new identity authentication protocol relies on the threshold group signatures.
  2. Develop a new key agreement protocol based on the threshold encryption using the Lagrange interpolation theorem.
  3. Compare these proposed schemes with the current schemes from security and efficiently point view
  4. To make these schemes more adaptable with the multi-hop characteristics of ad-hoc networks.
  5. To guaranteed the privacy of the basic group key and identify certificate by the intractability of computing discrete logarithm.

For an ad hoc network, there are many special properties we should follow, such that architecture, dynamic, distributed, multi-hop, etc. The great benefit of the suggested protocols is toachieve secure communication while following these properties.

THEPROPOSEDKEY AGREEMENTSCHEME

For ad hoc network, it is necessaryto distribute essential keys between numbers ofusers. However,the ad hoc network is a dynamic peer-to-peernetwork,and the key infrastructureshouldthereforebesuppliedin a distributedtechnique. Thesuggestedprotocolis to establish the key servicein ad hocnetworks. An efficient key agreement protocol is introducedusing the multi-hop propertyof the ad hoc networks.

To start with,assume that there are just several users in the network; these users require common group session keys to communicate mutually. So each user equally contributes to establish the group key. In addition everyuserhas a regularprivate password w. This password is just used at the establishment of the group session key. Also, assume that is the large prime and is the generator ofwith order, supposeis a large prime number and is a finite field. Everyuser in the ad hoc network selectsrandomly a prime number. But when there are users in the network, finds and sends the outcomesto. The shares key of this network can be calculated corresponding to Lagrange interpolation theorem. Where the number of users in the network and can be computedby how many 'hi' messages are received from other users. So each user gets a series of users and computes his share In fact the polynomial presents the lastformula contributed by all of users and. So, all users can work out the group key after they received all shares transmitted by other users. Then everyfollowinguserfor receives and multipliestheresultto the power to find. Thentogether withissentto. Thelastuser receives and multiplies theresultto the power to compute In addition, alsoreceives, Thus findsthe. On behalf the entiregroup, transmits the group session key to in the network. So everyuserknows the group session key .This situationis moreliketo the actuality of ad hoc networks since one important propertyof ad hoc networks is multi-hop. Figure 1 shows the process of the proposed key agreement protocol.

Figure 1: The Proposed Key Agreement Protocol

2.1. Security Analysis

For the security examination we gain from the modular design of proposed system using well known cryptography schemes. Although all attacks of the schemes are verified to be prevented. The security analysis is obliviously constructions as we stay away from interaction among the schemes as can as possible. We now plan the proofs that the new schemes own several security characteristics, If not providing a specific suggestion, we suppose that all users do not conspire with every other.

Theorem 1: This suggested schemegives great punctual security.

Proof 1: For the adversary unknowing the password, he can not find any helpful dataduring the messages sent among the users, since everymessage is encrypted by the password w. Even if the opponent sharedthe password w, he mostly can calculate instead of the shares key. The intermit messages are not useful to find the shares key. Whenthe last usertransmits the group key to eachuser, he encrypts the message with and contemporarily. It is obvious that is hard to solverelied on the difficulty to compute the Diffie-Hellman problem in prime order subgroups except forthe two usersand.

Theorem 2: The suggested schemesustains the share independence between the groups.

Proof 2: Corresponding to the suggested scheme, everyusertransmits to the next user. Even if can be found with, the share is yetnot unperceivableto other usersrelied on the difficulty of solving the discrete logarithm problem.

In this scheme, justabout rounds are required for establishing the shares key, the traffic between the networks is significantly decreasing. But it is obvious that the proposedscheme has the less communication than the other existing schemes, it grows the complexity cost for everyone.

THE PROPOSEDIDENTITYAUTHENTICATION PROTOCOL

In the pervious section, we only concentrate on the establishment of the shares key and we donot focusonthe identity authentication. But whena single user is compromisedand exposedby the authenticusers, there must be a methodto insulatethe user. Thus a new identity authentication protocol is suggested to facethis difficulty. It gives a distributed way to publish the authority certificate to eachuser.

For a considerablead hocnetwork, it is more suitable when the newuserjustrequiresfew of the usersthose are near to him to publish the authority certificate. Thus we suggestedthreshold groupsignature scheme to achieve thiswork, such that is the threshold value and is the number ofusers in the network. The firstpart of theprotocolcan be organizedas follows:

Each userselects a polynomial with order mostly, such thatcoefficientsare selectedrandomly for whereis the threshold value discussed bythe allusers. However,is a large compositemodulus where such thatand are large prime numbers. Eachuserhas its unique series integer number. Then, determinesthe shares key mod such that, and communicates to the user.Thus eachusergets a series of users and calculates his share such that and the polynomialmod denotesthe last formulaecontributedby the entireusers.Though,morethan users can find outthe share key, we do not permit them to rebuild the key since we do not require eachuserknowsthe shares key. Instead, one user is selected for the trusting user and the user canask for other users to detectthe share key. Then we require the keysissued by this trusting user. Assume that u1 is the trusting user and gathers the sub-secretsform other users. Then the user canfind out the shares key corresponding to the Language interpolation theorem.

Gullious-Quisquater(Guillou and Quisquater, 1990) suggestedadigital signature algorithmrelied on the difficulty of integer factoring. We enhancedthisalgorithmand suggested a novel group signature scheme to suitthe authentication of ad hocnetworks. Again we useasa composite integer modulus, is a arbitrary integer prime numberless than, is agenerator of with order and is a arbitrary integer numberof,is the multiplicative group of, is a one way hash function.Theusersecret key is and is the public key such as,where mod n. The keys and function are madepublic and the other keys are private.

Weperceivethat just useru1 can gather the sub privates and findthe shares key. However,u1requiresannouncingthe public groupkey, and is the group key discussed by all users. Onceu1transmittedall of the keys, hedeletes secretkey,ifaprivate key is recoveredby opponents later, u1playsas atypicaluser.Assume a new userjointsthe network for the first time;thisusermustask for an authority certificate from the userspresented in the network. The steps are as follows:

A new usertransmits his demand to thenextusers. But if more than t usersrespond and are eager implement outthe authenticationprocess,terminatetransmitting. Then chooses users as his authentication users and chooses the firstuser and lastuser. The medialusers are not decisivesotheir series can be arbitrary. Giventhat theusersgenerate the set A. So builds the session key as well as in advance. Thentransmitthe message m, the series numbers of set A andthe integerto. Then selectsa randomd1 and calculate,such that s1 is a share keyhold by.After that calculates and transmits to. The picks anarbitrary number then finds . Nexttransmitsto thesubsequent user. Similarity, the last user to link with the authenticationprocess, obtainsthe result (r1,, m) transmittedby.Thus plays anessentialrolein the creation of certificate authority. Also chooses an integer numberand finds mod n,then he computes, and, mod n, isa private shared key byand.Lastly transmitto.Thencalculates, and getsthe last authoritycertificate. To verify the signature,checkif. If true, then accepts the group signature as hisauthority certificate.But if not, reject the group signatureand asks foranotherauthority certificate. Figure 2 shows the identity authentication protocol.

Figure 2: The Proposed Identity Authentication Protocol

3.1.Security Evaluation

We now plan the proofs that the new scheme owns several security characteristics. If not provided a specific suggestion, we suppose that all users do not conspire with every other.

Theorem 3: Theproposed authentication protocolgivesthe share keyindependence.

Proof 3: The firstusertransmits to the seconduser, such thatis the private shared key by and. The cannot recovertheactual share keykeptby. Similarity, the next users also cannot decipherthe otherusers’ shares key.

Theorem 4:No onein this proposed scheme perceivesthe authority certificate of.

Proof 4: The formsthe last group signaturesuch that has the possibility to obtain the identity certificate of. However does not perceive the privateshared key by and.Sodoes notget the identity certificate of. While perceives the private, but hecan not perceive the randominteger number and cannot calculate the hash function.So cannot recover from the authority certificate even if issent byto.

Theorem 5: If the formula retains,the identity certificate istrue.

Proof 5: From the explanation above, we identifythat:

, and. So ifretains, it is proof that the identity certificate is true.

CONCLUSION

Thesuggested key agreement scheme is appropriate to create a groupsession key. In general the first users of the ad hoc network are considerstrustfulandhonest. So employing thesuggested key agreement protocol can rapidly establish the session key,since the messagecan be transmitted with outencryption.However, after the ad hoc network has run for a while, the suggested key agreement protocol can provide great security and meet the need to efficiently build the session key.It needsjust2(n-1) rounds highlydecreases the traffic in thenetwork.

In the proposed protocol, the fixedpassword wgreatly reduces the time complexityrequired (Ateniese et al., 1998). Comparedwith the protocol suggestedin (Ateniese et al., 1998), we do not require refreshing the group session key each time whena newuserconnectsthe network, since the group session key created bythe proposed protocol is just employed for group communication. The group session key can be transmitto another usersencryptedbythe fixed password w straight. Forvaluable discussion among two usersafter the authority certificate is checked out, the two users will assigna new session key byDiffie-Hellmanscheme. In addition, we developeda zero knowledge scheme to reusethe authority certificate. All these protocolsenhance the efficiency of the suggested protocols.Concerning the authenticationscheme, the discrete logarithm algorithmis employed in the proposedprotocolwhereas threshold RSA scheme is employed by (Luo et al.,2002). Since,it is well knownthat threshold RSA schemerequires additional timecomplexitycompared withthe discrete logarithm problem(Hezberg et al., 1995). Consequently theproposedidentity authentication protocolis more efficient compared with the scheme in (Luo et al.,2002).

REFERENCES

Aresenault, A. and Turner, S., 2000, Internet X.509 public key infrastructure, draft-ietf-pkix-roadmap-06.txt

Ateniese, G., Steiner, M., and Fsudik,G., 1998, Authenticated Group Key Agreement and Friends, Proceedings of the 5th ACM conference on Computer and Communications Security, ACM, pp. 17-26

Ateniese, G., Steiner, M., and Fsudik,G., 1998, Key agreement protocol in ad hoc networks, Communication Technology Proceedings, ICCT, International Conference on, IEEE, April 9-11, Volume 1, pp. 296-301.

Bettstetter, C. and Friedrich,B., 2003, Time and Message Complexities of the generalized distributed mobility adaptive clustering (GDMAC) algorithm in wireless multihop network, Proceeding of IEEE Vehicular Technology Conference, Jeju, Korea, pp. 22-25.

Desmedt,Y. 1994, Threshold cryptography, European Transactions on Tele-communications, 5(4), pp. 449-457.

Guillou L., and Quisquater,L., 1990, A paradoxical identity based signature scheme resulting from zero knowledge, Advances in Cryptology Proceedings, LNCS, Springer Verlag, pp. 216 - 231.

Hezberg,H., Jarecki,D., KrawzykH., and Young,M.,1995, Proactive secret sharing or: how to cope with perpetual leakage, Crypto ’95, Lecture Notes in Computer Science,Springer-Verlag.

Jayakumar,C. and Chellappan, C.,2005, A ware energy efficient routing protocol for wireless ad-hoc network, Asian Journal of Information Technology, Volume 4, No. 6, pp. 578-582.

Kaliaperumal,S.,2003, Securing authentication and Privacy in ad hoc partitioned networks, Applications and the Internet Workshops, Proceedings of Symposium, IEEE, 27-31, pp. 354-357.

Khalili,A., Katz J., and Arbaugh,W., 2003, Toward secure key distribution in truly ad hoc networks, Applications, Symposium, IEEE, 27-31, pp. 342-346.

Luo,H., Zerfos,P., Kong, J., Lu S., and Zhong,L. 2002, Self securing ad hoc wireless networks, 7thIEEE Symposium on Computers and Communications (ISCC'02), Italy, pp. 567-574.

Mauve, M., Widmer, J., and Hartenstein, H., 2001, A Survey on Position-Based Routing in Mobile Ad-Hoc Networks, IEEE Network, Volume 15, No. 6, pp. 30-39.

Pieprzyk, J., and Li,C., 2000, Multiparty Key Agreement Protocols, IEE Proceeding, Computers and Digital Techniques, Volume 147, issue 4, pp. 229-236.

Stjmenovic,I., and Lin,X., 2001, Power Aware Localized Routing in Wireless Networks, IEEE Transaction on Parallel and Distributed System, Vol. 12, No. 11, pp. 1122-1133.

Yao, J. and Zeng,G., 2004,Key Agreement and Identity Authentication Protocols for Ad Hoc Network, Proceeding of IEEE ITCC International Conference on Information Technology, 5-7, Las Vegas, Nevada, USA, pp. 720-724.

Zhou,L.,and Hass,Z.,1999, Securing ad hoc networks, IEEE Networks, 13(6), pp. 24-30