A Model of Onion Routing with Provable Anonymity
Onion routing is a scheme for anonymous communication that is designed for practical use. Until now, however, it has had no formal model and therefore no rigorous analysis of its anonymity guarantees. We give an IO-automata model of an onion-routing proto
- PDF / 486,182 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 32 Downloads / 197 Views
Yale University {Joan.Feigenbaum, aaron.johnson}@yale.edu 2 Naval Research Laboratory [email protected]
Abstract. Onion routing is a scheme for anonymous communication that is designed for practical use. Until now, however, it has had no formal model and therefore no rigorous analysis of its anonymity guarantees. We give an IO-automata model of an onion-routing protocol and, under possibilistic definitions, characterize the situations in which anonymity and unlinkability are guaranteed. Keywords: Security, privacy, anonymity, onion routing.
1
Introduction
Anonymity networks allow users to communicate while hiding their identities from one another and from third parties. We would like to design such networks with strong anonymity guarantees but without incurring high communication overhead or much added latency. Many designs have been proposed that meet these goals to varying degrees [1]. Of the many design proposals, onion routing [8] has had notable success in practice. Several implementations have been made [8,13,6], and there was a similar commercial system, Freedom [2]. As of September 2006, the most recent iteration of the basic design, Tor [6], consists of over 750 routers, each processing an average of 100KB/s. Onion routing is a practical anonymity-network scheme with relatively low overhead and latency. It provides two-way, connection-based communication and does not require that the destination participate in the anonymity-network protocol. These features make it useful for anonymizing much of the communication that takes place over the Internet today, such as web browsing, chatting, and remote login. Many Tor users communicate with web-based businesses and financial services. Chaum [4] was the first to note that even the best ecash design fails to be anonymous if the network identifies the customer. Even if a client is not hidden from the service, e.g., she’s using ordinary credit cards, she may desire privacy
Supported in part by NSF grants 0331548 and 0428422. Supported by NSF grant 0428422. Supported by ONR.
S. Dietrich and R. Dhamija (Eds.): FC 2007 and USEC 2007, LNCS 4886, pp. 57–71, 2007. c IFCA/Springer-Verlag Berlin Heidelberg 2007
58
J. Feigenbaum, A. Johnson, and P. Syverson
from her network-service provider, which might be her employer or just an ISP that is not careful with logs of its users’ activities. Examples of the threat posed by both of these situations have been all too frequent in the news. Businesses also make integral use of Tor to protect their commercial interests from competitors or to investigate the public offerings of their competitors without being observed. One vendor discovered by using Tor that its competitor had been offering a customized web site just for connections from the vendor’s IP address. Low latency and other performance characteristics of Tor can be demonstrated experimentally; anonymity-preserving properties cannot. Also, even with careful design, vulnerabilities can persist. The initial Tor authentication protocol had a cryptographic-
Data Loading...
