Abstract
Many anonymous communication networks (ACNs) rely on routing traffic through a sequence of proxy nodes to obfuscate the originator of the traffic. Without an accountability mechanism, exit proxy nodes may become embroiled in a criminal investigation if originators commit criminal actions through the ACN. We present BackRef, a generic mechanism for ACNs that provides practical repudiation for the proxy nodes by tracing back the selected outbound traffic to the predecessor node (but not in the forward direction) through a cryptographically verifiable chain. It also provides an option for full (or partial) traceability back to the entry node or even to the corresponding originator when all intermediate nodes are cooperating. Moreover, to maintain a good balance between anonymity and accountability, the protocol incorporates whitelist directories at exit proxy nodes. BackRef offers improved deployability over the related work, and introduces a novel concept of pseudonymous signatures that may be of independent interest.
We exemplify the utility of BackRef by integrating it into the onion routing (OR) protocol, and examine its deployability by considering several system-level aspects. We also present the security definitions for the BackRef system (namely, anonymity, backward traceability, no forward traceability, and no false accusation) and conduct a formal security analysis of the OR protocol with BackRef using ProVerif, an automated cryptographic protocol verifier, establishing the aforementioned security properties against a strong adversarial model.
Chapter PDF
Similar content being viewed by others
References
Chaum, D.: The dining cryptographers problem: Unconditional sender and recipient untraceability. J. Cryptology 1(1) (1988)
Corrigan-Gibbs, H., Ford, B.: Dissent: accountable anonymous group messaging. In: CCS, pp. 340–350 (2010)
Syverson, P.F., Goldschlag, D.M., Reed, M.G.: Anonymous connections and onion routing. In: IEEE Symposium on Security and Privacy (1997)
Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. CACM 24(2) (1981)
Mittal, P., Borisov, N.: Shadowwalker: peer-to-peer anonymous communication using redundant structured topologies. In: CCS, pp. 161–172 (2009)
Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second-generation onion router. In: USENIX Security (2004)
Möller, U., Cottrell, L., Palfrader, P., Sassaman, L.: Mixmaster Protocol— Version 2. IETF Internet Draft (2003), http://mixmaster.sourceforge.net/
Janssen, A.W.: Tor madness reloaded (2007), http://itnomad.wordpress.com/2007/09/16/tor-madness-reloaded/ (accessed January 2014)
AccusedOperator: Raided for operating a Tor exit node (2012), http://raided4tor.cryto.net/
Köpsell, S., Wendolsky, R., Federrath, H.: Revocable anonymity. In: Müller, G. (ed.) ETRICS 2006. LNCS, vol. 3995, pp. 206–220. Springer, Heidelberg (2006)
von Ahn, L., Bortz, A., Hopper, N.J., O’Neill, K.: Selectively traceable anonymity. In: Danezis, G., Golle, P. (eds.) PET 2006. LNCS, vol. 4258, pp. 208–222. Springer, Heidelberg (2006)
Diaz, C., Preneel, B.: Accountable anonymous communication. In: Security, Privacy, and Trust in Modern Data Management (2007)
Golle, P.: Reputable mix networks. In: Martin, D., Serjantov, A. (eds.) PET 2004. LNCS, vol. 3424, pp. 51–62. Springer, Heidelberg (2005)
Clark, J., Gauvin, P., Adams, C.: Exit node repudiation for anonymity networks. In: On the Identity Trail: Privacy, Anonymity and Identity in a Networked Society. Oxford University Press (2009)
Johnson, P.C., Kapadia, A., Tsang, P.P., Smith, S.W.: Nymble: Anonymous IP-address blocking. In: Borisov, N., Golle, P. (eds.) PET 2007. LNCS, vol. 4776, pp. 113–133. Springer, Heidelberg (2007)
Henry, R., Goldberg, I.: Formalizing anonymous blacklisting systems. In: IEEE Symposium on Security and Privacy, pp. 81–95 (2011)
Goldberg, I., Wagner, D., Brewer, E.: Privacy-enhancing technologies for the internet. In: IEEE Compcon. (1997)
Goldberg, I., Shostack, A.: Freedom network 1.0 architecture and protocols. Technical report, Zero-Knowledge Systems (2001)
Kate, A., Zaverucha, G.M., Goldberg, I.: Pairing-based onion routing with improved forward secrecy. ACM Trans. Inf. Syst. Secur. 13(4) (2010)
Danezis, G., Goldberg, I.: Sphinx: A compact and provably secure mix format. In: IEEE Symposium on Security and Privacy (2009)
Danezis, G., Dingledine, R., Mathewson, N.: Mixminion: design of a type iii anonymous remailer protocol. In: IEEE Symposium on Security and Privacy (2003)
Pfitzmann, A., Hansen, M.: A terminology for talking about privacy by data minimization v0.34, http://dud.inf.tu-dresden.de/literatur/Anon_Terminology_v0.34.pdf (August 2010)
Wolinsky, D.I., Corrigan-Gibbs, H., Ford, B., Johnson, A.: Dissent in numbers: making strong anonymity scale. In: OSDI (2012)
Corrigan-Gibbs, H., Wolinsky, D.I., Ford, B.: Proactively accountable anonymous messaging in verdict. In: USENIX Security (2013)
Danezis, G., Sassaman, L.: How to bypass two anonymity revocation schemes. In: Borisov, N., Goldberg, I. (eds.) PETS 2008. LNCS, vol. 5134, pp. 187–201. Springer, Heidelberg (2008)
TorProject: Exonerator Service (2012), https://exonerator.torproject.org/ (accessed January 2014)
Øverlier, L., Syverson, P.F.: Improving efficiency and simplicity of tor circuit establishment and hidden services. In: Borisov, N., Golle, P. (eds.) PET 2007. LNCS, vol. 4776, pp. 134–152. Springer, Heidelberg (2007)
Kate, A., Goldberg, I.: Using sphinx to improve onion routing circuit construction. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 359–366. Springer, Heidelberg (2010)
Backes, M., Kate, A., Mohammadi, E.: Ace: an efficient key-exchange protocol for onion routing. In: WPES (2012)
Catalano, D., Fiore, D., Gennaro, R.: Certificateless onion routing. In: CCS (2009)
Goldberg, I., Stebila, D., Ustaoglu, B.: Anonymity and one-way authentication in key exchange protocols. Designs, Codes and Cryptography (2012)
Camenisch, J.L., Lysyanskaya, A.: A formal treatment of onion routing. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 169–187. Springer, Heidelberg (2005)
Danezis, G., Diaz, C., Troncoso, C., Laurie, B.: Drac: An architecture for anonymous low-volume communications. In: Atallah, M.J., Hopper, N.J. (eds.) PETS 2010. LNCS, vol. 6205, pp. 202–219. Springer, Heidelberg (2010)
Shimshock, E., Staats, M., Hopper, N.: Breaking and provably fixing minx. In: Borisov, N., Goldberg, I. (eds.) PETS 2008. LNCS, vol. 5134, pp. 99–114. Springer, Heidelberg (2008)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
Haeberlen, A., Fonseca, P., Rodrigues, R., Druschel, P.: Fighting cybercrime with packet attestation. Technical report, MPI-SWS (2011)
Dingledine, R., Mathewson, N.: Tor Protocol Specification (2008), https://gitweb.torproject.org/torspec.git/tree/HEAD (accessed January 2014)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, p. 514. Springer, Heidelberg (2001)
Blake, I., Seroussi, G., Smart, N., Cassels, J.W.S.: Advances in Elliptic Curve Cryptography. Cambridge University Press (2005)
Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.-Y.: High-speed high-security signatures. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 124–142. Springer, Heidelberg (2011)
Abadi, M., Fournet, C.: Mobile values, new names, and secure communication. In: POPL (2001)
Blanchet, B.: An efficient cryptographic protocol verifier based on prolog rules. In: CSFW (2001)
BackRef: Introducing accountability to anonymity networks (proverif scripts), http://crypsys.mmci.uni-saarland.de/projects/BackRef/
Backes, M., Clark, J., Kate, A., Simeonovski, M., Druschel, P.: Backref: Introducing accountability to anonymity networks, http://arxiv.org/abs/1311.3151
Delaune, S., Kremer, S., Ryan, M.: Verifying privacy-type properties of electronic voting protocols, 435–487 (2009)
Chothia, T.: Analysing the MUTE anonymous file-sharing system using the pi-calculus. In: Najm, E., Pradat-Peyre, J.-F., Donzeau-Gouge, V.V. (eds.) FORTE 2006. LNCS, vol. 4229, pp. 115–130. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Backes, M., Clark, J., Kate, A., Simeonovski, M., Druschel, P. (2014). BackRef: Accountability in Anonymous Communication Networks. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds) Applied Cryptography and Network Security. ACNS 2014. Lecture Notes in Computer Science, vol 8479. Springer, Cham. https://doi.org/10.1007/978-3-319-07536-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-07536-5_23
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07535-8
Online ISBN: 978-3-319-07536-5
eBook Packages: Computer ScienceComputer Science (R0)