Matthew K. Wright
Brian Neil Levine
Abstract
There have been a number of protocols proposed for anonymous network communication. In this paper, we investigate attacks by corrupt group members that degrade the anonymity of each protocol over time. We prove that when a particular initiator continues communication with a particular responder across path reformations, existing protocols are subject to the attack. We use this result to place an upper bound on how long existing protocols, including Crowds, Onion Routing, Hordes, Web Mixes, and DC-Net, can maintain anonymity in the face of the attacks described. This provides a basis for comparing these protocols against each other. Our results show that fully connected DC-Net is the most resilient to these attacks, but it suffers from scalability issues that keep anonymity group sizes small. We also show through simulation that the underlying topography of the DC-Net affects the resilience of the protocol: as the number of neighbors a node has increases the strength of the protocol increases, at the cost of higher communication overhead.
- Berthold, O., Federrath, H., and Kohntopp, M. 2000. Project anonymity and unobservability in the internet. In Computers Freedom and Privacy Conference 2000 (CFP 2000) Workshop on Freedom and Privacy by Design.]] Google Scholar
Digital Library
- Bertsekas, D. and Gallager, R. 1987. Data Networks. Prentice-Hall, Englewood Cliffs, NJ.]] Google ScholarDigital Library
- Chaum, D. 1981. Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24, 2 (Feb.), 84--88.]] Google ScholarDigital Library
- Chaum, D. 1988. The dining cryptographers problem: Unconditional sender and receipient untraceability. J. Cryptography 1, 1, 65--75.]] Google ScholarDigital Library
- Figueiredo, D. R., Nain, P., and Towsley, D. 2004. On the analysis of the predecessor attack on anonymous protocols. Technical Report 04-65 (July), University of Massachusetts CMPSCI.]]Google Scholar
- Freedman, M. J. and Morris, R. 2002. Tarzan: A peer-to-peer anonymizing network layer. In Proceedings of ACM Conference on Computer and Communications Security (CCS 2002).]] Google ScholarDigital Library
- Goldberg, I. and Wagner, D. 1998. Taz servers and the rewebber network: Enabling anonymous publishing on the world wide web. First Monday.]]Google Scholar
- Harmon, A. 1998. Exploration of the world wide web tilts from eclectic to mundane. New York Times (Aug. 26). National Desk.]]Google Scholar
- Kesdogan, D., Egner, J., and Buschkes, R. 1998. Stop-and-go-mixes providing probabilistic anonymity in an open system. In Information Hiding.]]Google Scholar
- Kung, H. T., Bradner, S., and Tan, K.-S. 2002. An ip-layer anonymizing infrastructure. In Proceedings of MILCOM: Military Communications Conference.]]Google Scholar
- Levine, B. N., Reiter, M., Wang, C., and Wright, M. 2004. Stopping timing attacks in low-latency mix-based systems. In Proceedings of Financial Cryptography.]]Google Scholar
- Martin, D. 1999. Local Anonymity in the Internet. Ph.D Thesis, Boston, MA.]] Google ScholarDigital Library
- Motawani, R. and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, UK, chap. 4.]] Google ScholarDigital Library
- Pfitzmann, A., Pfitzmann, B., and Waidner, M. 1991. Isdnmixes: Untraceable communication with very small bandwidth overhead. In GI/ITG Conference: Communication in Distributed Systems.]] Google ScholarDigital Library
- Reed, M., Syverson, P., and Goldschlag, D. 1998. Anonymous connections and onion routing. IEEE Journal on Selected Areas in Communication. Special Issue on Copyright and Privacy Protection.]] Google ScholarDigital Library
- Reiter, M. K. and Rubin, A. D. 1998. Crowds: Anonymity for Web Transactions. ACM Transactions on Information and System Security 1, 1 (Nov.), 66--92.]] Google ScholarDigital Library
- Rennhard, M. and Plattner, B. 2002. Introducing morphmix: Peer-to-peer based anonymous internet usage with collusion detection. In Proceedings of 2002 ACM Workshop on Privacy in the Electronic Society (WPES).]] Google ScholarDigital Library
- Scarlatta, V., Levine, B., and Shields, C. 2001. Responder anonymity and anonymous peer-to-peer file sharing. In Proceedings of IEEE International Conference on Network Protocols (ICNP).]] Google ScholarDigital Library
- Schneier, B. 1996. Applied Cryptography. Wiley, New York.]]Google Scholar
- Sherwood, R., Bhattacharjee, B., and Srinivasan, A. 2002. P5: A protocol for scalable anonymous communication. In Proceedings of 2002 IEEE Symposium on Security and Privacy.]] Google ScholarDigital Library
- Shields, C. and Levine, B. 2000. A Protocol for anonymous communication over the internet. In Proceedings of 7th ACM Conference on Computer and Communication Security (ACM CCS 2000).]] Google ScholarDigital Library
- Shmatikov, V. 2002. Probabilistic analysis of anonymity. In IEEE Computer Security Foundations Workshop (CSFW). 119--128.]] Google ScholarDigital Library
- Staniford-Chen, S. and Heberlein, L. 1995. Holding intruders accountable on the internet. In Proceedings of the 1995 IEEE Symposium on Security and Privacy (Oakland, CA). 39--49.]] Google ScholarDigital Library
- Syverson, P. and Stubblebine, S. 1999. Group principals and the formalization of anonymity. In FM'99---Formal Methods, vol. I, J. Wing, J. Woodcock, and J. Davies, Eds. Lecture Notes in Computer Science, vol. 1708. Springer, Berlin, 814--833.]] Google ScholarDigital Library
- Syverson, P., Tsudik, G., Reed, M., and Landwehr, C. 2000. Towards an analysis of onion routing security. In Workshop on Design Issues in Anonymity and Unobservability.]] Google ScholarDigital Library
- Waidner, M. and Pfitzmann, B. 1989a. The dining cryptographers in the disco: Unconditional sender and recipient untraceability with computationally secure serviceability. In Eurocrypt '89.]] Google ScholarDigital Library
- Waidner, M. and Pfitzmann, B. 1989b. Unconditional sender and recipient untraceability in spite of active attacks---Some remarks. Technical Report, Fakultat fur Informatik, Universitat Karlsruhe.]]Google Scholar
- Wright, M., Adler, M., Levine, B., and Shields, C. 2002. An analysis of the degradation of anonymous protocols. In ISOC Symposium on Network and Distributed System Security.]]Google Scholar
- Wright, M., Adler, M., Levine, B., and Shields, C. 2003. Defending anonymous communications against passive logging attacks. In IEEE Symposium on Security and Privacy.]] Google ScholarDigital Library
- Xiao, L., Xu, Z., and Zhang, X. 2001. Low-cost and reliable mutual anonymity protocols in peer-to-peer networks. Technical Report HPL-2001-204 (Aug.), Hewlett Packard Laboratories.]]Google Scholar
- Yoda, K. and Etoh, H. 2000. Finding a connection chain for tracing intruders. In Proceedings of the 6th European Symposium on Research in Computer Security (2000). ESORICS.]] Google ScholarDigital Library
- Zhang, Y. and Paxson, V. 1999. Stepping stone detection. A Presentation at SIGCOMM'99, New Areas of Research.]]Google Scholar
Index Terms
- The predecessor attack: An analysis of a threat to anonymous communications systems
Recommendations
On anonymity in an electronic society: A survey of anonymous communication systems
The past two decades have seen a growing interest in methods for anonymous communication on the Internet, both from the academic community and the general public. Several system designs have been proposed in the literature, of which a number have been ...
k-anonymous message transmission
CCS '03: Proceedings of the 10th ACM conference on Computer and communications securityInformally, a communication protocol is sender k - anonymous if it can guarantee that an adversary, trying to determine the sender of a particular message, can only narrow down its search to a set of k suspects. Receiver k-anonymity places a similar ...
How to Find Hidden Users: A Survey of Attacks on Anonymity Networks
Communication privacy has been a growing concern, particularly with the Internet becoming a major hub of our daily interactions. Revelations of government tracking and corporate profiling have resulted in increasing interest in anonymous communication ...
Comments