Information leaks in structured peer-to-peer anonymous communication systems

ABSTRACT

We analyze information leaks in the lookup mechanisms of structured peer-to-peer anonymous communication systems and how these leaks can be used to compromise anonymity. We show that the techniques that are used to combat active attacks on the lookup mechanism dramatically increase information leaks and increase the efficacy of passive attacks. Thus there is a trade-off between robustness to active and passive attacks.

We study this trade-off in two P2P anonymous systems, Salsa and AP3. In both cases, we find that, by combining both passive and active attacks, anonymity can be compromised much more effectively than previously thought, rendering these systems insecure for most proposed uses. Our results hold even if security parameters are changed or other improvements to the systems are considered. Our study therefore motivates the search for new approaches to P2P anonymous communication.

REFERENCES

• 1: Adam Back , Ulf Möller , Anton Stiglic, Traffic Analysis Attacks and Trade-Offs in Anonymity Providing Systems, Proceedings of the 4th International Workshop on Information Hiding, p.245-257, April 25-27, 2001
• 2: Kevin Bauer , Damon McCoy , Dirk Grunwald , Tadayoshi Kohno , Douglas Sicker, Low-resource routing attacks against tor, Proceedings of the 2007 ACM workshop on Privacy in electronic society, October 29-29, 2007, Alexandria, Virginia, USA [doi>10.1145/1314333.1314336]
• 3: S. M. Bellovin and D. A. Wagner, editors. IEEE Symposium on Security and Privacy, May 2003.
• 4: Oliver Berthold , Hannes Federrath , Marit Köhntopp, Project “anonymity and unobservability in the Internet”, Proceedings of the tenth conference on Computers, freedom and privacy: challenging the assumptions, p.57-65, April 04-07, 2000, Toronto, Ontario, Canada [doi>10.1145/332186.332211]
• 5: Nikita Borissov , Eric A. Brewer, Anonymous routing in structured peer-to-peer overlays, University of California at Berkeley, Berkeley, CA, 2005
• 6: Nikita Borisov , George Danezis , Prateek Mittal , Parisa Tabriz, Denial of service or denial of security?, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315258]
• 7: Miguel Castro , Peter Druschel , Ayalvadi Ganesh , Antony Rowstron , Dan S. Wallach, Secure routing for structured peer-to-peer overlay networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060317]
• 8: G. Ciaccio. Improving sender anonymity in a structured overlay with imprecise routing. In Danezis and Golle {13}, pages 190--207.
• 9: David Daly , Daniel D. Deavours , Jay M. Doyle , Patrick G. Webster , William H. Sanders, Möbius: An Extensible Tool for Performance and Dependability Modeling, Proceedings of the 11th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools, p.332-336, March 27-31, 2000
• 10: G. Danezis. Statistical disclosure attacks: Traffic confirmation in open environments. In Gritzalis, Vimercati, Samarati, and Katsikas, editors, Proceedings of Security and Privacy in the Age of Uncertainty, (SEC2003), pages 421--426, Athens, May 2003. IFIP TC11, Kluwer.
• 11: George Danezis , Richard Clayton, Route Fingerprinting in Anonymous Communications, Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing, p.69-72, September 06-June 08, 2006 [doi>10.1109/P2P.2006.33]
• 12: George Danezis , Roger Dingledine , Nick Mathewson, Mixminion: Design of a Type III Anonymous Remailer Protocol, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.2, May 11-14, 2003
• 13: G. Danezis and P. Golle, editors. Sixth Workshop on Privacy Enhancing Technologies, volume 4258 of Lecture Notes in Computer Science, Cambridge, UK, June 2006. Springer.
• 14: George Danezis , Paul Syverson, Bridging and Fingerprinting: Epistemic Attacks on Route Selection, Proceedings of the 8th international symposium on Privacy Enhancing Technologies, p.151-166, July 23-25, 2008, Leuven, Belgium [doi>10.1007/978-3-540-70630-4_10]
• 15: C. Diaz, S. Seys, J. Claessens, and B. Preneel. Towards measuring anonymity. In Dingledine and Syverson {17}, pages 184--188.
• 16: Roger Dingledine , Nick Mathewson , Paul Syverson, Tor: the second-generation onion router, Proceedings of the 13th conference on USENIX Security Symposium, p.21-21, August 09-13, 2004, San Diego, CA
• 17: R. Dingledine and P. Syverson, editors. Privacy Enhancing Technologies Workshop, volume 2482 of Lecture Notes in Computer Science. Springer, April 2002.
• 18: 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
• 19: Revised Papers from the First International Workshop on Peer-to-Peer Systems, March 2002
• 20: H. Federrath, editor. International Workshop on Design Issues in Anonymity and Unobservability, volume 2009 of Lecture Notes in Computer Science. Springer, July 2000.
• 21: Michael J. Freedman , Robert Morris, Tarzan: a peer-to-peer anonymizing network layer, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586137]
• 22: D. Goodin. Tor at heart of embassy passwords leak. The Register, September 10 2007.
• 23: Nicholas Hopper , Eugene Y. Vasserman , Eric Chan-Tin, How much anonymity does network latency leak?, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315257]
• 24: M. F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal distributed hash table. In F. Kaashoek and I. Stoica, editors, International Workshop on Peer-to-Peer Systems (IPTPS), volume 2735 of Lecture Notes in Computer Science, pages 98--107. Springer, Feb. 2003.
• 25: A. Kapadia and N. Triandopoulos. Halo: High-assurance locate for distributed hash tables. In C. Cowan and G. Vigna, editors, Network and Distributed System Security Symposium, pages 61--79, Feb. 2008.
• 26: Dogan Kedogan , Dakshi Agrawal , Stefan Penz, Limits of Anonymity in Open Environments, Revised Papers from the 5th International Workshop on Information Hiding, p.53-69, October 07-09, 2002
• 27: N. Mathewson and R. Dingledine. Practical traffic analysis: Extending and resisting statistical disclosure. In D. Martin and A. Serjantov, editors, Workshop on Privacy Enhancing Technologies, volume 3424 of Lecture Notes in Computer Science, pages 17--24. Springer, May 2004.
• 28: Alan Mislove , Gaurav Oberoi , Ansley Post , Charles Reis , Peter Druschel , Dan S. Wallach, AP3: cooperative, decentralized anonymous communication, Proceedings of the 11th workshop on ACM SIGOPS European workshop, p.30-es, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133578]
• 29: U. Moller, L. Cottrell, P. Palfrader, and L. Sassaman. Mixmaster Protocol - Version 2. IETF Internet Draft, July 2003.
• 30: Steven J. Murdoch, Hot or not: revealing hidden services by their clock skew, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180410]
• 31: Steven J. Murdoch , George Danezis, Low-Cost Traffic Analysis of Tor, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.183-195, May 08-11, 2005 [doi>10.1109/SP.2005.12]
• 32: S. J. Murdoch and P. Zielinski. Sampled traffic analysis by Internet-exchange-level adversaries. In N. Borisov and P. Golle, editors, Privacy Enhancing Technologies Symposium, volume 4776 of Lecture Notes in Computer Science, pages 167--183. Springer, June 2007.
• 33: A. Nambiar and M. Wright. The Salsa simulator. http://ranger.uta.edu/~mwright/code/salsa-sims.zip.
• 34: Arjun Nambiar , Matthew Wright, Salsa: a structured approach to large-scale anonymity, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180409]
• 35: Linda Daily Paulson, News Briefs, Computer, v.39 n.4, p.17-19, April 2006 [doi>10.1109/MC.2006.136]
• 36: Jean-François Raymond, Traffic analysis: protocols, attacks, design issues, and open problems, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.10-29, January 2001, Berkeley, California, United States
• 37: Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
• 38: Marc Rennhard , Bernhard Plattner, Introducing MorphMix: peer-to-peer based anonymous Internet usage with collusion detection, Proceedings of the 2002 ACM workshop on Privacy in the Electronic Society, p.91-102, November 21-21, 2002, Washington, DC [doi>10.1145/644527.644537]
• 39: 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
• 40: A. Serjantov and G. Danezis. Towards an information theoretic metric for anonymity. In Dingledine and Syverson {17}.
• 41: Micah Sherr , Boon Thau Loo , Matt Blaze, Towards application-aware anonymous routing, Proceedings of the 2nd USENIX workshop on Hot topics in security, p.1-5, August 07, 2007, Boston, MA
• 42: 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
• 43: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 44: Paul Syverson , Gene Tsudik , Michael Reed , Carl Landwehr, Towards an analysis of onion routing security, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.96-114, January 2001, Berkeley, California, United States
• 45: P. Tabriz and N. Borisov. Breaking the collusion detection mechanism of MorphMix. In Danezis and Golle {13}, pages 368--383.
• 46: D. Wallach. A survey of peer-to-peer security issues. In M. Okada, B. Pierce, A. Scedrov, H. Tokuda, and A. Yonezawa, editors, International Symposium on Software Security, volume 2609 of Lecture Notes in Computer Science, pages 253--258. Springer, 2002.
• 47: M. Wright, M. Adler, B. N. Levine, and C. Shields. An analysis of the degradation of anonymous protocols. In P. van oorschot and V. Gligor, editors, Network and Distributed System Security Symposium, pages 39--50, Feb. 2002.
• 48: Matthew Wright , Micah Adler , Brian N. Levine , Clay Shields, Defending Anonymous Communications Against Passive Logging Attacks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.28, May 11-14, 2003
• 49: Matthew K. Wright , Micah Adler , Brian Neil Levine , Clay Shields, The predecessor attack: An analysis of a threat to anonymous communications systems, ACM Transactions on Information and System Security (TISSEC), v.7 n.4, p.489-522, November 2004 [doi>10.1145/1042031.1042032]
• 50: R. Wright and S. D. C. di Vimercati, editors. The 13th ACM Conference on Computer and Communications Security, New York, NY, USA, Oct. 2006. ACM.
• 51: R. Wright and P. Syverson, editors. The 14th ACM Conference on Computer and Communications Security, New York, NY, USA, 2007. ACM

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Security

Keywords:
anonymity, attacks, information leaks, peer-to-peer