Secure routing for structured peer-to-peer overlay networks

ABSTRACT

Structured peer-to-peer overlay networks provide a substrate for the construction of large-scale, decentralized applications, including distributed storage, group communication, and content distribution. These overlays are highly resilient; they can route messages correctly even when a large fraction of the nodes crash or the network partitions. But current overlays are not secure; even a small fraction of malicious nodes can prevent correct message delivery throughout the overlay. This problem is particularly serious in open peer-to-peer systems, where many diverse, autonomous parties without preexisting trust relationships wish to pool their resources. This paper studies attacks aimed at preventing correct message delivery in structured peer-to-peer overlays and presents defenses to these attacks. We describe and evaluate techniques that allow nodes to join the overlay, to maintain routing state, and to forward messages securely in the presence of malicious nodes.

REFERENCES

• 1: M. Bellare and P. Rogaway. The exact security of digital signatures- How to sign with RSA and Rabin. In Advances in Cryptology - EUROCRYPT 96, Lecture Notes in Computer Science, Vol. 1070. Springer-Verlag, 1996.
• 2: Steve Bellovin. Security aspects of Napster and Gnutella. In 2001 Usenix Annual Technical Conference, Boston, Massachusetts, June 2001. Invited talk.
• 3: Miguel Castro, Peter Druschel, Y. Charlie Hu, and Antony Rowstron. Exploiting network proximity in peer-to-peer overlay networks. Technical Report MSR-TR-2002-82, Microsoft Research, May 2002.
• 4: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 5: Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 8: Drew Dean and Adam Stubblefield. Using client puzzles to protect TLS. In 10th Usenix Security Symposium, pages 1--8, Washington, D.C., August 2001.
• 9: Roger Dingledine, Michael J. Freedman, and David Molnar. Accountability measures for peer-to-peer systems. In Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O'Reilly and Associates, November 2000.
• 10: 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
• 11: M. P. Herlihy , J. M. Wing, Axioms for concurrent objects, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.13-26, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41627]
• 12: Amir Herzberg , Markus Jakobsson , Stanislław Jarecki , Hugo Krawczyk , Moti Yung, Proactive public key and signature systems, Proceedings of the 4th ACM conference on Computer and communications security, p.100-110, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266442]
• 13: Ari Juels and John Brainard. Client puzzles: A cryptographic defense against connection depletion attacks. In Internet Society Symposium on Network and Distributed System Security (NDSS '99), pages 151--165, San Diego, California, February 1999.
• 14: Nancy A. Lynch , Dahlia Malkhi , David Ratajczak, Atomic Data Access in Distributed Hash Tables, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.295-305, March 07-08, 2002
• 15: Ralph C. Merkle, Secure communications over insecure channels, Communications of the ACM, v.21 n.4, p.294-299, April 1978 [doi>10.1145/359460.359473]
• 16: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 17: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 18: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 19: Emil Sit , Robert Morris, Security Considerations for Peer-to-Peer Distributed Hash Tables, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.261-269, March 07-08, 2002
• 20: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 21: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001