Towards provable security for ad hoc routing protocols

ABSTRACT

We propose a formal framework for the security analysis of on-demand source routing protocols for wireless ad hoc networks. Our approach is based on the well-known simulation paradigm that has been proposed to prove the security of cryptographic protocols. Our main contribution is the application of the simulation-based approach in the context of ad hoc routing. This involves a precise definition of a real-world model, which describes the real operation of the protocol, and an ideal-world model, which captures what the protocol wants to achieve in terms of security. Both models take into account the peculiarities of wireless communications and ad hoc routing. Then, we give a formal definition of routing security in terms of indistinguishability of the two models from the point of view of honest parties. We demonstrate the usefulness of our approach by analyzing two "secure" ad hoc routing protocols, SRP and Ariadne. This analysis leads to the discovery of as yet unknown attacks against both protocols. Finally, we propose a new ad hoc routing protocol and prove it to be secure in our model.

REFERENCES

• 1: M. Backes and B. Pfitzmann. A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol. to appear in IEEE Journal on Selected Areas in Communication .
• 2: Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
• 3: Mihir Bellare , Phillip Rogaway, Entity Authentication and Key Distribution, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.232-249, August 22-26, 1993
• 4: Mihir Bellare , Phillip Rogaway, Provably secure session key distribution: the three party case, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.57-66, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225084]
• 5: Mihir Bellare , Ran Canetti , Hugo Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.419-428, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276854]
• 6: Michael Burrows , Martin Abadi , Roger Needham, A logic of authentication, ACM Transactions on Computer Systems (TOCS), v.8 n.1, p.18-36, Feb. 1990 [doi>10.1145/77648.77649]
• 7: Michael Burrows , Martín Abadi , Roger Needham, Rejoinder to Nessett, ACM SIGOPS Operating Systems Review, v.24 n.2, p.39-40, April 1990 [doi>10.1145/382258.382790]
• 8: L. Buttyán and I. Vajda. Towards provable security for ad hoc routing protocols. Techical Report No. 2004/159, http://eprint.iacr.org/, July 2004.
• 9: R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD dissertation, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, June 1995.
• 10: Joshua D. Guttman, Security Goals: Packet Trajectories and Strand Spaces, Revised versions of lectures given during the IFIP WG 1.7 International School on Foundations of Security Analysis and Design on Foundations of Security Analysis and Design: Tutorial Lectures, p.197-261, September 01, 2000
• 11: Z. Haas, M. Perlman, and P. Samar. The Interzone Routing Protocol (IERP) for ad hoc networks. Internet Draft, IETF MANET Working Group, June 2001.
• 12: 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]
• 13: Yih-Chun Hu , David B. Johnson , Adrian Perrig, SEAD: Secure Efficient Distance Vector Routing for Mobile Wireless Ad Hoc Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.3, June 20-21, 2002
• 14: Yih-Chun Hu , Adrian Perrig, A Survey of Secure Wireless Ad Hoc Routing, IEEE Security and Privacy, v.2 n.3, p.28-39, May 2004 [doi>10.1109/MSP.2004.1]
• 15: D. Johnson and D. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, edited by Tomasz Imielinski and Hank Korth, Chapter 5, pages 153--181. Kluwer Academic Publisher, 1996.
• 16: Wenbo Mao, Modern Cryptography: Theory and Practice, Prentice Hall Professional Technical Reference, 2003
• 17: J. Marshall. An Analysis of the Secure Routing Protocol for mobile ad hoc network route discovery: using intuitive reasoning and formal verification to identify flaws. MSc thesis, Department of Computer Science, Florida State University, April 2003.
• 18: S. Micali and P. Rogaway. Secure computation. In Proceedings of Crypto'91, 1991.
• 19: P. Papadimitratos and Z. Haas. Secure routing for mobile ad hoc networks. In Proceedings of SCS Communication Networks and Distributed Systems Modelling Simulation Conference (CNDS), 2002.
• 20: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 21: Birgit Pfitzmann , Michael Waidner, A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.184, May 14-16, 2001
• 22: Kimaya Sanzgiri , Bridget Dahill , Brian Neil Levine , Clay Shields , Elizabeth M. Belding-Royer, A Secure Routing Protocol for Ad Hoc Networks, Proceedings of the 10th IEEE International Conference on Network Protocols, p.78-89, November 12-15, 2002
• 23: V. Shoup. On formal models for secure key exchange (version 4), revision of IBM Research Report RZ 3120, November 1999.
• 24: Manel Guerrero Zapata , N. Asokan, Securing ad hoc routing protocols, Proceedings of the 3rd ACM workshop on Wireless security, p.1-10, September 28-28, 2002, Atlanta, GA, USA [doi>10.1145/570681.570682]
• 25: Shahan Yang , John S. Baras, Modeling vulnerabilities of ad hoc routing protocols, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986861]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Security

Keywords:
ad hoc networks, on-demand source routing, provable security, routing protocols, simulatability