Small worlds in security systems: an analysis of the PGP certificate graph

ABSTRACT

We propose a new approach to securing self-organized mobile ad hoc networks. In this approach, security is achieved in a fully self-organized manner; by this we mean that the security system does not require any kind of certification authority or centralized server, even for the initialization phase. In our work, we were inspired by PGP [15] because its operation relies solely on the acquaintances between users. We show that the small-world phenomenon naturally emerges in the PGP system as a consequence of the self-organization of users. We show this by studying the PGP certificate graph properties and by quantifying its small-world characteristics. We argue that the certificate graphs of self-organized security systems will exhibit a similar small-world phenomenon, and we provide a way to model self-organized certificate graphs. The results of the PGP certificate graph analysis and graph modelling can be used to build new self-organized security systems and to test the performance of the existing proposals. In this work, we refer to such an example.

REFERENCES

• 1: K. Aberer, M. Punceva, M. Hauswirth, and R. Schmidt. Gridella, a P2P system based on the P-Grid approach, improves on Gnutella's search performance while reducing bandwidth requirements. IEEE Internet Computing, 2002.
• 2: Lada A. Adamic, The Small World Web, Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries, p.443-452, September 22-24, 1999
• 3: R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the World Wide Web. Nature, 401:130--131, 1999.
• 4: L. Blažević, L. Buttyán, S. Čapkun, S. Giordano, J.-P. Hubaux, and J.-Y. Le Boudec. Self-organization in mobile ad hoc networks: The approach of Terminodes. IEEE Communications Magazine, June 2001.
• 5: J. Jubin and J. Turnow. The DARPA packet radio project. Proceedings of the IEEE, 1987.
• 6: Rajesh Kasturirangan, Multiple Scales in Small-World Networks, Massachusetts Institute of Technology, Cambridge, MA, 1999
• 7: 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
• 8: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 9: S. Milgram. The small world problem. In Psychology Today, volume 61, 1967.
• 10: 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]
• 11: J.-P. Hubaux, T. Gross, J.-Y. Le Boudec, and M. Vetterli. Toward self-organized mobile ad hoc networks: The Terminodes Project. IEEE Communications Magazine, January 2001.
• 12: J. Travers and S. Milgram. An experimental study of the small world problem. In Sociometry, volume 32, 1969.
• 13: D. Watts. Small Worlds. Princeton University Press, 1999.
• 14: L. Zhou and Z. Haas. Securing ad hoc networks. IEEE Network, 13(6):24--30, November/December 1999.
• 15: Philip R. Zimmermann, The official PGP user's guide, MIT Press, Cambridge, MA, 1995

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

General Terms:
Design, Experimentation, Measurement, Performance, Security

Keywords:
PGP, public-key management, self-organization, small-world graphs