Distributed and Secure Bootstrapping of Mobile Ad Hoc Networks: Framework and Constructions

ABSTRACT

Secure bootstrapping of mobile ad hoc networks (MANETs) is a challenging problem in scenarios in which network users (or nodes) do not share trust relationships prior to the network deployment. In recent years, a number of schemes have been proposed to solve this problem, assuming either no or limited trust between the nodes prior to their deployment. Despite numerous proposals, there is no common understanding of the proposed schemes and of the trade-offs that they provide. This has consequences for both researchers and practitioners, who do not have a clear idea how to compare the schemes and how to select a scheme for a given application. In this article, we present a framework that helps in understanding and comparing schemes for secure bootstrapping of MANETs. The framework is general because it is policy-neutral and can accommodate many existing bootstrapping schemes. The proposed framework can equally serve as a good basis for the development of new MANET bootstrapping schemes; we show how the development of the framework leads to two new (classes of) distributed bootstrapping schemes. Within the framework, we not only investigate and characterize the properties of the relevant bootstrapping schemes, but also give methods for practitioners to select the relevant system parameters in the Random Walk and the (Restricted) Random Waypoint mobility models.

REFERENCES

• 1: Aldous, D. J. and Fill, A. 2000. Markov chains on graphs. Manuscript under preparation.
• 2: Ross Anderson , Markus Kuhn, Tamper resistance: a cautionary note, Proceedings of the 2nd conference on Proceedings of the Second USENIX Workshop on Electronic Commerce, p.1-1, November 18-21, 1996, Oakland, California
• 3: Asokan, N. and Ginzboorg, P. 2000. Key management in ad hoc networks. Comput. Comm., 23, 1627--1637.
• 4: Balfanz, D., Smetters, D., Stewart, P., and Wong, H. 2002. Talking to strangers: Authentication in ad-hoc wireless networks. In Proceedings of the Network and Distributed Systems Security Symposium (NDSS'02). The Internet Society, San Diego, CA.
• 5: Stefano Basagni , Kris Herrin , Danilo Bruschi , Emilia Rosti, Secure pebblenets, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501438]
• 6: Bechler, M., Hof, H., Kraft, D., Pahlke, F., and Wolf, L. 2004. A cluster-based security architecture for ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04).
• 7: Bellare, M. and Rogaway, P. 1996. The exact security of digital signatures - how to sign with rsa and rabin. In Proceedings of the International Conference on the Theory and Application of Crytographic Techniques (EUROCRYPT'96). 399--416.
• 8: R Blom, An optimal class of symmetric key generation systems, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.335-338, December 1985, Paris, France
• 9: Carlo Blundo , Alfredo De Santis , Amir Herzberg , Shay Kutten , Ugo Vaccaro , Moti Yung, Perfectly-Secure Key Distribution for Dynamic Conferences, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.471-486, August 16-20, 1992
• 10: Stefan Brands , David Chaum, Distance-bounding protocols, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.344-359, January 1994, Lofthus, Norway
• 11: Čagalj, M. and Hubaux, J. P. 2004. Key agreement over a radio link. Tech. Rep. IC/2004/16, EPFL-DI-ICA. January.
• 12: Čagalj, M., Čapkun, S., and Hubaux, J.-P. 2006. Key agreement in peer-to-peer wireless networks. Proceedings of the IEEE, to appear.
• 13: Camp, T., Boleng, J., and Davies, V. 2002. A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing: Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2, 5, 483--502.
• 14: Camtepe, S. and Yener, B. 2004. Combinatorial design of key distribution mechanisms for wireless sensor networks. In Proceedings of the 9th European Symposium on Research Computer Security (ESORICS'04). Lecture Notes in Computer Science, vol. 3193. 293--308.
• 15: Srdjan Čapkun , Levente Buttyán , Jean-Pierre Hubaux, Self-Organized Public-Key Management for Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.1, p.52-64, January-March 2003 [doi>10.1109/TMC.2003.1195151]
• 16: Srdjan Čapkun , Jean-Pierre Hubaux , Levente Buttyán, Mobility helps security in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778422]
• 17: Chan, A. 2004. Distributed symmetric key management for mobile ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04).
• 18: Chan, H. and Perrig, A. 2005. Pike: Peer intermediaries for key establishment in sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05).
• 19: Haowen Chan , Adrian Perrig , Dawn Song, Random Key Predistribution Schemes for Sensor Networks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.197, May 11-14, 2003
• 20: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 21: Wenliang Du , Jing Deng , Yunghsiang S. Han , Pramod K. Varshney, A pairwise key pre-distribution scheme for wireless sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948118]
• 22: Ellis, R. Torus Hitting Times Project. http://www.math.tamu.edu/~rellis/comb/torus/torus.html.
• 23: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 24: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 25: Michael T. Goodrich , Michael Sirivianos , John Solis , Gene Tsudik , Ersin Uzun, Loud and Clear: Human-Verifiable Authentication Based on Audio, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.10, July 04-07, 2006 [doi>10.1109/ICDCS.2006.52]
• 26: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 27: Grossglauser, M. and Vetterli, M. 2003. Locating nodes with ease: Mobility diffusion of last encounters in ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03).
• 28: Hoepman, J. 2004. The ephemeral pairing problem. In Proceedings of Financial Cryptography (FC'04). Lecture Notes in Computer Science, vol. 3110. 212--226.
• 29: Yih-Chun Hu , Adrian Perrig , David B. Johnson, Ariadne: a secure on-demand routing protocol for ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570648]
• 30: Jean-Pierre Hubaux , Levente Buttyán , Srdan Capkun, The quest for security in mobile ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501437]
• 31: Providing Robust and Ubiquitous Security Support for Mobile Ad Hoc Networks, Proceedings of the Ninth International Conference on Network Protocols, p.251, November 11-14, 2001
• 32: Krawczyk, H. 2003. Sigma: The “sign-and-mac” approach to authenticated Diffie-Hellman and its use in the ike-protocols. In Proceedings of the Annual International Cryptology Conference (CRYPTO'03). Lecture Notes in Computer Science, vol. 2729. 400--425.
• 33: Lee, J. and Stinson, D. 2004. Deterministic key predistribution schemes for distributed sensor networks. In Proceedings of the 11th International Workshop Selected Areas in Cryptography (SAC'04). Lecture Notes in Computer Science, vol. 3357. 294--307.
• 34: Donggang Liu , Peng Ning, Establishing pairwise keys in distributed sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948119]
• 35: Jonathan M. McCune , Adrian Perrig , Michael K. Reiter, Seeing-Is-Believing: Using Camera Phones for Human-Verifiable Authentication, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.110-124, May 08-11, 2005 [doi>10.1109/SP.2005.19]
• 36: Maithili Narasimha , Gene Tsudik , Jeong Hyun Yi, On the Utility of Distributed Cryptography in P2P and MANETs: The Case of Membership Control, Proceedings of the 11th IEEE International Conference on Network Protocols, p.336, November 04-07, 2003
• 37: Roger M. Needham , Michael D. Schroeder, Using encryption for authentication in large networks of computers, Communications of the ACM, v.21 n.12, p.993-999, Dec. 1978 [doi>10.1145/359657.359659]
• 38: Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
• 39: Papadimitratos, P. and Haas, Z. J. 2002. Secure routing for mobile ad hoc networks. In Proceedings of the Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS'02).
• 40: Panagiotis Papadimitratos , Zygmunt J. Haas, Secure data transmission in mobile ad hoc networks, Proceedings of the 2nd ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941311.941318]
• 41: D. B. Johnsort, Routing in Ad Hoc Networks of Mobile Hosts, Proceedings of the 1994 First Workshop on Mobile Computing Systems and Applications, p.158-163, December 08-09, 1994 [doi>10.1109/WMCSA.1994.33]
• 42: Doyle, P. G. and Snell, J. L. 2001. Random walks and electric networks. Number 22. Carus Mathematical Monographs.
• 43: Shah, R. C., Roy, S., Jain, S., and Brunette, W. 2003. Data MULEs: Modeling a three-tier architecture for sparse sensor networks. In Proceedings of the IEEE Workshop on Sensor Network Protocols and Applications (SNPA'03).
• 44: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 45: Saxena, N. 2006. Public key cryptography sans certificates in ad hoc networks. In Proceedings of the 4th International Conference Applied Cryptography and Network Security (ACNS'06). Lecture Notes in Computer Science, vol. 3989. 375--389.
• 46: Nitesh Saxena , Gene Tsudik , Jeong Hyun Yi, Efficient Node Admission for Short-lived Mobile Ad Hoc Networks, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.269-278, November 06-09, 2005 [doi>10.1109/ICNP.2005.14]
• 47: Frank Stajano , Ross J. Anderson, The Resurrecting Duckling: Security Issues for Ad-hoc Wireless Networks, Proceedings of the 7th International Workshop on Security Protocols, p.172-194, April 19-21, 1999
• 48: TCG. Trusted computing group (tcg) specifications. https://www.trustedcomputinggroup.org/home.
• 49: Vaudenay, S. 2005. Secure communications over insecure channels based on short authenticated strings. In Advances in Cryptology---Crypto'05. Springer-Verlag, Berlin, 309--326. Lecture Notes in Computer Science No. 3621.
• 50: Wu, J. and Wei, R. 2005. Comments on “distributed symmetric key management for mobile ad hoc networks” from infocom 2004. Cryptology ePrint Archive, Report 2005/008. Available at http://eprint.iacr.org/.
• 51: Xu, G. and Iftode, L. 2004. Locality driven key management architecture for mobile ad hoc networks. In Proceedings of the IEEE Conference on Mobile Ad Hoc and Sensor Systems (MOBIHOC'04). 436--446.
• 52: Yi, S. and Kravets, R. 2003. Moca: Mobile certificate authority for wireless ad hoc networks. In The 2nd Annual PKI Research Workshop (PKI'03).
• 53: Yoon, J., Liu, M., and Noble, B. 2003. Random Waypoint Considered Harmful. In Proceedings of the IEEE Conference on Computer Communications (InfoCom'03). San Francisco.
• 54: Zhou, L. and Haas, Z. 1999. Securing ad hoc networks. IEEE Networks, 13, 6, 24--30.
• 55: Sencun Zhu , Shouhuai Xu , Sanjeev Setia , Sushil Jajodia, Establishing Pairwise Keys for Secure Communication in Ad Hoc Networks: A Probabilistic Approach, Proceedings of the 11th IEEE International Conference on Network Protocols, p.326, November 04-07, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Security

Keywords:
MANETs, secure communication, security bootstrapping