Abstract
Low-latency anonymous communication networks require padding to resist timing analysis attacks, and dependent link padding has been proven to prevent these attacks with minimal overhead. In this paper we consider low-latency anonymity networks that implement dependent link padding, and examine various network topologies. We find that the choice of the topology has an important influence on the padding overhead and the level of anonymity provided, and that Stratified networks offer the best trade-off between them. We show that fully connected network topologies (Free Routes) are impractical when dependent link padding is used, as they suffer from feedback effects that induce disproportionate amounts of padding; and that Cascade topologies have the lowest padding overhead at the cost of poor scalability with respect to anonymity. Furthermore, we propose an variant of dependent link padding that considerably reduces the overhead at no loss in anonymity with respect to external adversaries. Finally, we discuss how Tor, a deployed large-scale anonymity network, would need to be adapted to support dependent link padding.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berthold, O., Federrath, H., Köpsell, S.: Web MIXes: A system for anonymous and unobservable Internet access. In: Federrath, H. (ed.) PET 2000. LNCS, vol. 2009, pp. 115–129. Springer, Heidelberg (2001)
Bohme, R., Danezis, G., Diaz, C., Kopsell, S., Pfitzmann, A.: Mix cascades vs. peer-to-peer: Is one concept superior? In: Martin, D., Serjantov, A. (eds.) PET 2004. LNCS, vol. 3424, pp. 243–255. Springer, Heidelberg (2005)
Danezis, G.: Mix-networks with restricted routes. In: Dingledine, R. (ed.) PET 2003. LNCS, vol. 2760, pp. 1–17. Springer, Heidelberg (2003)
Danezis, G., Dingledine, R., Mathewson, N.: Mixminion: Design of a Type III Anonymous Remailer Protocol. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 2–15. IEEE Computer Society, Los Alamitos (2003)
Diaz, C., Seys, S., Claessens, J., Preneel, B.: Towards measuring anonymity. In: Dingledine, R., Syverson, P.F. (eds.) PET 2002. LNCS, vol. 2482, pp. 54–68. Springer, Heidelberg (2003)
Dingledine, R., Mathewson, N., Syverson, P.: Tor: The second-generation onion router. In: Proceedings of the USENIX Security Symposium, pp. 303–320 (2004)
Dingledine, R., Shmatikov, V., Syverson, P.: Synchronous batching: From cascades to free routes. In: Martin, D., Serjantov, A. (eds.) PET 2004. LNCS, vol. 3424, pp. 186–206. Springer, Heidelberg (2005)
Goldschlag, D., Reed, M., Syverson, P.: Hiding routing information. In: Anderson, R. (ed.) IH 1996. LNCS, vol. 1174, pp. 137–150. Springer, Heidelberg (1996)
Houmansadr, A., Kiyavash, N., Borisov, N.: RAINBOW: A robust and invisible non-blind watermark for network flows. In: Proceedings of the Network and Distributed System Security Symposium (NDSS 2009). The Internet Society (2009)
Levine, B.N., Reiter, M., Wang, C., Wright, M.: Timing attacks in low-latency mix systems. In: Juels, A. (ed.) FC 2004. LNCS, vol. 3110, pp. 251–265. Springer, Heidelberg (2004)
Möller, U., Cottrell, L., Palfrader, P., Sassaman, L.: Mixmaster Protocol – Version 2. In: IETF Internet Draft (2003)
Murdoch, S.J., Zieliński, P.: Sampled traffic analysis by Internet-exchange-level adversaries. In: Borisov, N., Golle, P. (eds.) PETS 2007. LNCS, vol. 4776, pp. 167–183. Springer, Heidelberg (2007)
Pfitzmann, A., Pfitzmann, B., Waidner, M.: ISDN-MIXes: Untraceable communication with small bandwidth overhead. In: Kommunikation in Verteilten Systemen, Grundlagen, Anwendungen, Betrieb, GI/ITG-Fachtagung, pp. 451–463. Springer, Heidelberg (1991)
Reardon, J.: Improving Tor using a TCP-over-DTLS tunnel. Master’s thesis, University of Waterloo (2008)
Serjantov, A.: On the Anonymity of Anonymity Systems. PhD thesis, University of Cambridge (2004)
Serjantov, A., Danezis, G.: Towards an information theoretic metric for anonymity. In: Dingledine, R., Syverson, P.F. (eds.) PET 2002. LNCS, vol. 2482, pp. 41–53. Springer, Heidelberg (2003)
Shannon, C.: A mathematical theory of communication. The Bell System Technical Journal 27, 379–423 (1948)
Shmatikov, V., Wang, M.-H.: Timing analysis in low-latency mix networks: Attacks and defenses. In: Gollmann, D., Meier, J., Sabelfeld, A. (eds.) ESORICS 2006. LNCS, vol. 4189, pp. 18–33. Springer, Heidelberg (2006)
Syverson, P.F., Tsudik, G., Reed, M., Landwehr, C.: Towards an analysis of onion routing security. In: Federrath, H. (ed.) PET 2000. LNCS, vol. 2009, pp. 96–114. Springer, Heidelberg (2001)
Troncoso, C., Danezis, G.: The Bayesian analysis of mix networks. In: Proceedings of the ACM Conference on Computer and Communications Security (CCS 2009), p. 11. ACM, New York (2009)
Venkitasubramaniam, P., He, T., Tong, L.: Relay secrecy in wireless networks with eavesdroppers. In: Proceedings of the Allerton Conference on Communication, Control and Computing (2006)
Venkitasubramaniam, P., Tong, L.: Anonymous networking with minimum latency in multihop networks. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 18–32. IEEE Computer Society, Los Alamitos (2008)
Wang, W., Motani, M., Srinivasan, V.: Dependent link padding algorithms for low latency anonymity systems. In: Proceedings of the ACM Computer and Communications Security Conference (CCS 2008), pp. 323–332. ACM, New York (2008)
Wang, X., Chen, S., Jajodia, S.: Network flow watermarking attack on low-latency anonymous communication systems. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 116–130. IEEE Computer Society, Los Alamitos (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Diaz, C., Murdoch, S.J., Troncoso, C. (2010). Impact of Network Topology on Anonymity and Overhead in Low-Latency Anonymity Networks. In: Atallah, M.J., Hopper, N.J. (eds) Privacy Enhancing Technologies. PETS 2010. Lecture Notes in Computer Science, vol 6205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14527-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-14527-8_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14526-1
Online ISBN: 978-3-642-14527-8
eBook Packages: Computer ScienceComputer Science (R0)