The ultimate goal of Internet anonymization is to allow a host to communicate with an arbitrary server in such a manner that nobody can determine the host's identity. Toward this goal, we envision a system that uses an Internet-wide pool of nodes, numbered in the thousands, to relay each others' traffic to gain anonymity.
Different entities may be interested in exposing the host's identity, each with varying capabilities to do so: curious individuals or groups may run their own participating machines to snoop on traffic; parties skirting legality may break into a limited number of others' machines; and large, powerful organizations may tap and monitor Internet backbones.
Clearly, each type of adversary suggests different design criteria for an anonymizing system. Prior systems have either underestimated the ease of cracking or crashing individual machines, or discounted the prevalence of wide-spread eavesdropping capabilities, exemplified by the ``Great Firewall of China'', the FBI's Carnivore system, or subpoenas of Tier-1 ISP traffic for copy right-protection compliance.
We propose a practical system aimed at realizing anonymity against all three flavors of adversary. First, however, we discuss why less ambitious approaches are not adequate.
In the simplest alternative, a host sends messages to a server through a proxy, such as Anonymizer.com. This system fails if the proxy reveals a user's identity or if an adversary can observe the proxy's traffic. Furthermore, servers can easily block these centralized proxies and adversaries can prevent usage with denial-of-service attacks.
To overcome this single point of failure, a host can connect to a server through a set of mix relays. The anonymous remailer system, Onion Routing , and Zero-Knowledge's Freedom offer such a model, providing anonymity through a small, fixed core set of relays. However, if a corrupt relay receives traffic from a non-core node, the relay can identify that node as the ultimate origin of the traffic. Colluding entry and exit relays can use timing analysis to determine both source and destination. Even an external adversary can mount the same attack. Therefore, the connecting host remains vulnerable to individual relay failures, and these relays provide obvious targets for attacking or blocking.
Few of these systems attempt to provide anonymity against an adversary that can passively observe all network traffic. Such protection requires fixing traffic patterns or using cover traffic to make such traffic analysis more difficult. Proposals that do exist have several shortcomings, however. Some protect only the core of the static mix network and thus allow traffic analysis on its edges. Some simulate full synchrony and thus trivial DoS attacks halt their operation in entirety. And some require central control and knowledge of the entire network.
Our system, on the other hand, does not suffer from these same weaknesses. Its main contributions are two-fold.
First, we extend known mix-net designs to a peer-to-peer environment. System nodes communicate over sequences of mix relays chosen from an open-ended pool of volunteer nodes, without any centralized component. We present techniques to securely discover and select other nodes as communication relays: All peers are potential originators of traffic; all peers are potential relays. Such a scalable design lessens the significance of targeted attacks and inhibits network-edge analysis, as a relay cannot tell if it is the first hop in a mix path. Furthermore, we leverage our new concept of a domain to remove potential adversarial bias: An adversary may run hundreds of virtual machines, yet is unlikely to control hundreds of different IP subnets.
Second, we introduce a scalable and practical technique for cover traffic that uses a restricted topology for packet routing: Packets can be routed only between mimics, or pairs of nodes assigned by the system in a secure and universally-verifiable manner. This technique is practical in that it does not require network synchrony and consumes only a small factor more bandwidth than the data traffic to be hidden, and it is powerful as it shields all network participants, not only core routers.
The system allows client applications on participating hosts to talk to non-participating Internet servers through special IP tunnels. The two ends of a tunnel are a system node running a client application and a node running a network address translator; the latter forwards the client's traffic to its ultimate Internet destination. The system is transparent to both client applications and servers, though it must be installed and configured on participating nodes.
The system supports a systems-engineering position: anonymity can be built-in at the transport layer, transparent to most systems, trivial to incorporate, and with a tolerable loss of efficiency compared to its non-anonymous counterpart. This approach immediately reduces the effort required for application writers to incorporate anonymity into existing designs, and for users to add anonymity without changing existing non-anonymous applications. In the long term, the ability for individual anonymizing relays to easily participate in multiple kinds of traffic may make it easier to achieve a critical mass of anonymizing relays.
Site last updated on October 7th, 2003.