Dependent link padding algorithms for low latency anonymity systems

ABSTRACT

Low latency anonymity systems are susceptive to traffic analysis attacks. In this paper, we propose a dependent link padding scheme to protect anonymity systems from traffic analysis attacks while providing a strict delay bound. The covering traffic generated by our scheme uses the minimum sending rate to provide full anonymity for a given set of flows. The relationship between user anonymity and the minimum covering traffic rate is then studied via analysis and simulation. When user flows are Poisson processes with the same sending rate, the minimum covering traffic rate to provide full anonymity to m users is O(log m). For Pareto traffic, we show that the rate of the covering traffic converges to a constant when the number of flows goes to infinity. Finally, we use real Internet trace files to study the behavior of our algorithm when user flows have different rates.

REFERENCES

• 1: 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]
• 2: G. Danezis, "The traffic analysis of continuous-time mixes," in Proceedings of Privacy Enhancing Technologies Workshop (PET), 2004.
• 3: Xinyuan Wang , Shiping Chen , Sushil Jajodia, Tracking anonymous peer-to-peer VoIP calls on the internet, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102133]
• 4: U. Moeller, L. Cottrell, P. Palfrader, and L. Sassaman, "IETF draft: Mixmaster protocol version 2," http://www.ietf.org/internet-drafts/draft-sassaman-mixmaster-03.txt, 2004.
• 5: M. Reed, P. Syverson, and D. Goldschlag, "Anonymous connections and onion routing," IEEE Journal on Selected Areas in Communications, vol. 16, no. 4, pp. 482--494, 1998.
• 6: 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
• 7: 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]
• 8: A. Serjantov and P. Sewell, "Passive Attack Analysis for Connection--Based Anonymity Systems," in Proceedings of European Symposium on Research in Computer Security, 2003.
• 9: V. Anantharam and S. Verdu, "Bits through queues," IEEE Trans. on Information Theory, vol. 42, no. 1, pp. 4--18, 1996.
• 10: Xinyuan Wang , Shiping Chen , Sushil Jajodia, Network Flow Watermarking Attack on Low-Latency Anonymous Communication Systems, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.116-130, May 20-23, 2007 [doi>10.1109/SP.2007.30]
• 11: P. Venkitasubramaniam, T. He, and L. Tong, "Relay secrecy in wireless networks with eavesdroppers," in Proceedings of Allerton Conference on Communication, Control and Computing, 2006.
• 12: Andreas Pfitzmann , Birgit Pfitzmann , Michael Waidner, ISDN-MIXes: Untraceable Communication with Small Bandwidth Overhead, Kommunikation in Verteilten Systemen, Grundlagen, Anwendungen, Betrieb, GI/ITG-Fachtagung, p.451-463, February 20-22, 1991
• 13: Parvathinathan Venkitasubramaniam , Lang Tong, Anonymous Networking with Minimum Latency in Multihop Networks, Proceedings of the 2008 IEEE Symposium on Security and Privacy (sp 2008), p.18-32, May 18-21, 2008 [doi>10.1109/SP.2008.18]
• 14: P. Boucher, A. Shostack, and I. Goldberg, "Freedom systems 2.0 architecture,"White paper, Zero Knowledge Systems, Inc., December 2000.
• 15: S. J. Murdoch and P. Zielinski, "Sampled traffic analysis by internet-exchange-level adversaries," in Proceedings of Privacy Enhancing Technologies Workshop (PET), 2007.
• 16: 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]
• 17: 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]
• 18: Xinwen Fu , Bryan Graham , Riccardo Bettati , Wei Zhao, On Effectiveness of Link Padding for Statistical Traffic Analysis Attacks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.340, May 19-22, 2003
• 19: V. Shmatikov and M. Wang, "Timing analysis in low-latency mix networks: attacks and defenses?" in Proceedings of ESORICS, 2006.
• 20: A. Serjantov and G. Danezis, "Towards an information theoretic metric for anonymity," in Proceedings of Privacy Enhancing Technologies Workshop (PET), 2002.
• 21: C. Diaz, S. Seys, J. Claessens, and B. Preneel, "Towards measuring anonymity," in Proceedings of Privacy Enhancing Technologies Workshop (PET), 2002.
• 22: B. Bollobas, Modern Graph Theory. Springer, 1998.
• 23: A. Blum, D. Song, and S. Venkataraman, "Detection of interactive stepping stones: Algorithms and confidence bounds," in Proceedings of International Symposium on Recent Advances In Intrusion Detection, 2004.
• 24: T. He and L. Tong, "Detecting information flows: Improving chaff tolerance by joint detection," in Proceedings of Annual Conference Information Sciences and Systems (CISS), 2007.
• 25: Gaston H. Gonnet, Expected Length of the Longest Probe Sequence in Hash Code Searching, Journal of the ACM (JACM), v.28 n.2, p.289-304, April 1981 [doi>10.1145/322248.322254]
• 26: Michael David Mitzenmacher , Alistair Sinclair, The power of two choices in randomized load balancing, University of California, Berkeley, 1996
• 27: A. Papoulis and S. U. Pillai, Probability, Random Variables and Stochastic Processes. 4th Ed. McGraw Hill, 2002.
• 28: P. Venkitasubramaniam, T. He, and L. Tong, "Anonymous networking amidst eavesdroppers," IEEE Transactions on Information Theory, vol. 54, no. 6, pp. 2770--2784, 2008.
• 29: J. W. Cohen, The Single Server Queue. North-Holland, 1982.
• 30: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 31: N. L. for Applied Network Research., "Auckland-viii data set," http://pma.nlanr.net/Special/auck8.html, 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)

General Terms:
Algorithms, Performance, Security

Keywords:
anonymity systems, link padding, traffic analysis attack