Denial of service or denial of security?

ABSTRACT

We consider the effect attackers who disrupt anonymous communications have on the security of traditional high- and low-latency anonymous communication systems, as well as on the Hydra-Onion and Cashmere systems that aim to offer reliable mixing, and Salsa, a peer-to-peer anonymous communication network. We show that denial of service (DoS) lowers anonymity as messages need to get retransmitted to be delivered, presenting more opportunities for attack. We uncover a fundamental limit on the security of mix networks, showing that they cannot tolerate a majority of nodes being malicious. Cashmere, Hydra-Onion, and Salsa security is also badly affected by DoS attackers. Our results are backed by probabilistic modeling and extensive simulations and are of direct applicability to deployed anonymity systems.

REFERENCES

• 1: 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]
• 2: S. M. Bellovin and D. A. Wagner, editors. IEEE Symposium on Security and Privacy, Berkeley, CA, May 2003. IEEE Computer Society.
• 3: Oliver Berthold , Andreas Pfitzmann , Ronny Standtke, The disadvantages of free MIX routes and how to overcome them, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.30-45, January 2001, Berkeley, California, United States
• 4: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 5: 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
• 6: 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
• 7: Roger Dingledine , Michael J. Freedman , David Hopwood , David Molnar, A Reputation System to Increase MIX-Net Reliability, Proceedings of the 4th International Workshop on Information Hiding, p.126-141, April 25-27, 2001
• 8: R. Dingledine and N. Mathewson. Anonymity loves company: Usability and the network effect. In R. Anderson, editor, Fifth Workshop on the Economics of Information Security (WEIS), Cambridge, UK, June 2006.
• 9: 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
• 10: R. Dingledine, V. Shmatikov, and P. F. Syverson. Synchronous batching: From cascades to free routes. In D. Martin and A. Serjantov, editors, 4th Privacy Enhancing Technologies Workshop (PET), volume 3424 of Lecture Notes in Computer Science, pages 186--206, Toronto, Canada, May 2004. Springer Berlin/Heidelberg.
• 11: R. Dingledine and P. F. Syverson. Reliable MIX cascade networks through reputation. In M. Blaze, editor, Financial Cryptography, volume 2357 of Lecture Notes in Computer Science, pages 253--268, Southampton, Bermuda, 2003. Springer Berlin/Heidelberg.
• 12: 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
• 13: International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, January 2001
• 14: Jun Furukawa , Kazue Sako, An Efficient Scheme for Proving a Shuffle, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.368-387, August 19-23, 2001
• 15: Philippe Golle , Ari Juels, Parallel mixing, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030113]
• 16: M. Gomułkiewicz, M. Klonowski, and M. Kutyłowski. Provable unlinkability against traffic analysis already after O(log(n)) steps! In K. Zhang and Y. Zheng, editors, Information Security Conference, volume 3225 of Lecture Notes in Computer Science, pages 354--366, Palo Alto, CA, Sept. 2004. Springer Berlin/Heidelberg.
• 17: Ceki Gulcu , Gene Tsudik, Mixing Email with Babel, Proceedings of the 1996 Symposium on Network and Distributed System Security (SNDSS '96), p.2, February 22-23, 1996
• 18: J. Iwanik, M. Klonowski, and M. Kutyłowski. DUO-Onions and Hydra-Onions. failure and adversary resistant onion protocols. In IFIP TC-6TC-11 Conference on Communications and Multimedia Security, pages 1--15, Windermere, United Kingdom, September 2004. Springer Boston.
• 19: Markus Jakobsson , Ari Juels , Ronald L. Rivest, Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking, Proceedings of the 11th USENIX Security Symposium, p.339-353, August 05-09, 2002
• 20: U. Möller, L. Cottrell, P. Palfrader, and L. Sassaman. Mixmaster Protocol - Version 2. Draft, available at: http://www.abditum.com/mixmaster-spec.txt, July 2003.
• 21: 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]
• 22: C. Andrew Neff, A verifiable secret shuffle and its application to e-voting, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502000]
• 23: L. Øverlier and P. Syverson. Valet services: Improving hidden servers with a personal touch. In Sixth Workshop on Privacy Enhancing Technologies (PET), volume 4258 of Lecture Notes in Computer Science, pages 223--244, Cambridge, UK, June 2006. Springer Berlin/Heidelberg.
• 24: P. Palfrader. Number of Running Tor Routers. http://www.noreply.org/tor-running-routers/, 2007.
• 25: Choonsik Park , Kazutomo Itoh , Kaoru Kurosawa, Efficient anonymous channel and all/nothing election scheme, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.248-259, January 1994, Lofthus, Norway
• 26: 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
• 27: 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
• 28: M. Wright, M. Adler, B. N. Levine, and C. Shields. An analysis of the degradation of anonymous protocols. In Network and Distributed Security Symposium (NDSS). Internet Society, February 2002.
• 29: 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
• 30: Li Zhuang , Feng Zhou , Ben Y. Zhao , Antony Rowstron, Cashmere: resilient anonymous routing, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.301-314, May 02-04, 2005

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:
Reliability, Security

Keywords:
anonymity, attacks, denial of service, reliability