How much anonymity does network latency leak?

ABSTRACT

Low-latency anonymity systems such as Tor, AN.ON, Crowds, and Anonymizer.com aim to provide anonymous connections that are both untraceable by "local" adversaries who control only a few machines, and have low enough delay to support anonymous use of network services like web browsing and remote login. One consequence of these goals is that these services leak some information about the network latency between the sender and one or more nodes in the system. This paper reports on three experiments that partially measure the extent to which such leakage can compromise anonymity. First, using a public dataset of pairwise round-trip times (RTTs) between 2000 Internet hosts, we estimate that on average, knowing the network location of host A and the RTT to host B leaks 3.64 bits of information about the network location of B. Second, we describe an attack that allows a pair of colluding web sites to predict, based on local timing information and with no additional resources, whether two connections from the same Tor exit node are using the same circuit with 17% equal error rate. Finally, we describe an attack that allows a malicious website, with access to a network coordinate system and one corrupted Tor router, to recover roughly 6.8 bits of network location per hour.

REFERENCES

• 1: TOR (the onion router) servers. http://proxy.org/tor.shtml, 2007.
• 2: Jay Aikat , Jasleen Kaur , F. Donelson Smith , Kevin Jeffay, Variability in TCP round-trip times, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948241]
• 3: 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
• 4: Blum, A., Song, D., and Venkataraman, S. Detection of interactive stepping stones: Algorithms and confidence bounds. Proc. 7th Intl Symposium on Recent Advances in Intrusion Detection (RAID) (2004).
• 5: 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]
• 6: Brent Chun , David Culler , Timothy Roscoe , Andy Bavier , Larry Peterson , Mike Wawrzoniak , Mic Bowman, PlanetLab: an overlay testbed for broad-coverage services, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003 [doi>10.1145/956993.956995]
• 7: Manuel Costa , Miguel Castro , Antony Rowstron , Peter Key, PIC: Practical Internet Coordinates for Distance Estimation, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.178-187, March 24-26, 2004
• 8: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 9: Danezis, G. Statistical disclosure attacks: Traffic confirmation in open environments. In Proc. Security and Privacy in the Age of Uncertainty, (SEC2003) (Athens, May 2003), IFIP TC11, Kluwer, pp. 421--426.
• 10: 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
• 11: Díaz, C., and Serjantov, A. Generalising mixes. In Proc. 3rd Privacy Enhancing Technologies workshop (PET 2003) (March 2003), R. Dingledine, Ed., Springer-Verlag, LNCS 2760.
• 12: Dingledine, R., et al. Anonymity bibliography. http://freehaven.net/anonbib, 1999 - 2007.
• 13: 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
• 14: Tom Fawcett, An introduction to ROC analysis, Pattern Recognition Letters, v.27 n.8, p.861-874, June 2006 [doi>10.1016/j.patrec.2005.10.010]
• 15: Federrath, H., et al. JAP: Java anonymous proxy. http://anon.inf.tu-dresden.de/.
• 16: R. Fielding , J. Gettys , J. Mogul , H. Frystyk , L. Masinter , P. Leach , T. Berners-Lee, Hypertext Transfer Protocol -- HTTP/1.1, RFC Editor, 1999
• 17: Gil, T. M., Kaashoek, F., Li, J., Morris, R., and Stribling, J. The "King" data set.http://pdos.csail.mit.edu/p2psim/kingdata/, 2005.
• 18: Bamba Gueye , Artur Ziviani , Mark Crovella , Serge Fdida, Constraint-based geolocation of internet hosts, IEEE/ACM Transactions on Networking (TON), v.14 n.6, p.1219-1232, December 2006 [doi>10.1109/TNET.2006.886332]
• 19: Krishna P. Gummadi , Stefan Saroiu , Steven D. Gribble, King: estimating latency between arbitrary internet end hosts, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637203]
• 20: Hintz, A. Fingerprinting websites using traffic analysis. In Proc. 2nd Privacy Enhancing Technologies workshop (PET 2002) (April 2002), R. Dingledine and P. Syverson, Eds., Springer-Verlag, LNCS 2482.
• 21: jrandom, et al. I2P. http://www.i2p.net/, 2007.
• 22: Dogan Kesdogan , Jan Egner , Roland Büschkes, Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System, Proceedings of the Second International Workshop on Information Hiding, p.83-98, April 14-17, 1998
• 23: Ledlie, J., Gardner, P., and Seltzer, M. Network coordinates in the wild. In Proc. 4th USENIX Symposium on Network Systems Design and Implementation (April 2007).
• 24: Mathewson, N., and Dingledine, R. Practical traffic analysis: Extending and resisting statistical disclosure. In Proc. 4th Privacy Enhancing Technologies workshop (PET 2004) (May 2004), vol. 3424 of LNCS, pp. 17--34.
• 25: Moeller, U., Cottrell, L., Palfrader, P., and Sassaman, L. IETF draft: Mixmaster protocol version 2. http://www.ietf.org/internet-drafts/draft-sassaman-mixmaster-03.txt, 2005.
• 26: 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]
• 27: 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]
• 28: T. S. Eugene Ng , Hui Zhang, A network positioning system for the internet, Proceedings of the annual conference on USENIX Annual Technical Conference, p.11-11, June 27-July 02, 2004, Boston, MA
• 29: J. Oikarinen , D. Reed, Internet Relay Chat Protocol, RFC Editor, 1993
• 30: Lasse Overlier , Paul Syverson, Locating Hidden Servers, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.100-114, May 21-24, 2006 [doi>10.1109/SP.2006.24]
• 31: 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]
• 32: 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]
• 33: J. Rosenberg , H. Schulzrinne , G. Camarillo , A. Johnston , J. Peterson , R. Sparks , M. Handley , E. Schooler, SIP: Session Initiation Protocol, RFC Editor, 2002
• 34: Serjantov, A., and Sewell, P. Passive attack analysis for connection-based anonymity systems. In Proc. ESORICS 2003 (October 2003).
• 35: Neil Spring , David Wetherall , Tom Anderson, Scriptroute: a public internet measurement facility, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.17-17, March 26-28, 2003, Seattle, WA
• 36: 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
• 37: Bernard Wong , Ivan Stoyanov , Emin Gün Sirer, Geolocalization on the internet through constraint satisfaction, Proceedings of the 3rd conference on USENIX Workshop on Real, Large Distributed Systems, p.1-1, November 05, 2006, Seattle, WA
• 38: 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

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:
  E. Data
  E.3 DATA ENCRYPTION

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Measurement, Security

Keywords:
anonymity, latency