%% This section contains related work on anonymous channels %% used for communication. \section{Anonymous Channels} \label{sec:related-comm} \footnote{This section was written by Michael Freedman and David Molnar.} Several approaches have been proposed to achieve anonymity on an Internet communications channel. This section describes several real-world projects, which we analyze in terms of anonymity provided and resistance to various types of attack. We include a more in-depth review of anonymous communications channels in appendix \ref{app:related-comm-appendix}, truncated here for length and readability. \subsection{Proxy Servers: Anonymizer} Proxy services provide one of the most basic forms of anonymity, inserting a third party between the sender and recipient of a given message. Proxy services are characterized as having only one centralized layer of separation between message sender and recipient. The proxy serves as a ``trusted third party,'' responsible for removing distinguishing information from sender requests. The Anonymizer was one of the first examples of a \emph{form-based web proxy} \cite{anonymizer}. Users point their browsers at the Anonymizer page at {\tt www.anonymizer.com}. Once there, they enter their destination URL into a form displayed on that page. The Anonymizer then acts as an {\tt http} proxy for these users, stripping off all identifying information from {\tt http} requests and forwarding them on to the destination URL. The functionality is limited. Only {\tt http} requests are proxied, and the Anonymizer does not handle cgi scripts. In addition, unless the user chains several proxies together, he or she may be vulnerable to an adversary which tries to correlate incoming and outgoing {\tt http} requests. Only the data stream is anonymized, not the connection itself. Therefore, the proxy does not prevent traffic analysis attacks like tracking data as it moves through the network. Proxies only provide unlinkability between sender and receiver, given that the proxy itself remains uncompromised. This unlinkability does not have the quality of perfect forward anonymity, as proxy users often connect from the same IP address. Therefore, any future information used to gain linkability between sender and receiver (i.e., intersection attacks, traffic analysis) can be used against previously recorded communications. Sender and receiver anonymity is lost to an adversary that may monitor incoming traffic to the proxy. While the actual contents of the message might still be computationally secure via encryption, the adversary can correlate the message to a sender/receiver agent. This loss of sender/receiver anonymity plagues all systems which include external clients which interact through a separate communications channel -- that is, we can define some distinct edge of the channel. If an adversary can monitor this edge link or the first-hop node within the channel, this observer gains agent-message correlation. Obviously, the ability to monitor this link or node depends on the adversary's resources and the number of links and nodes which exist. In a proxy system, this number is small. In a globally-distributed mixnet, this number could be very large. The adversary's ability also depends on her focus: whether she is observing messages and agents at random, or if she is monitored specific senders/receivers on purpose. \subsection{Mixmaster Remailer} The pursuit of anonymity on the Internet was kicked off by David Chaum in 1981 with a paper in Communications of the ACM describing a system called a ``Mix-net'' \cite{chaum-mix}. This system uses a very simple technique to provide anonymity: a sender and receiver are linked by a chain of servers called Mixes. Each Mix in the chain strips off the identifying marks on incoming messages and then sends the message to the next Mix, based on routing instructions which are encrypted with its public key. Comparatively simple to understand and implement, this Mix-net (or ``mix-net'' or ``mixnet'') design is used in almost all of today's practical anonymous channels. Until the rise of proxy-based and TCP/IP-based systems, the most popular form of anonymous communication was the \emph{anonymous remailer}: a form of mix which works for e-mail sent over SMTP. We describe the development of remailer systems in greater depth in appendix \ref{app:related-comm-appendix}; in short, the evolution of remailers has led to the Mixmaster Type II remailer, designed by Lance Cottrell \cite{mixmaster}. Each Mixmaster remailer has an RSA public key and uses a hybrid symmetric-key encryption system. Every message is encrypted with a separate 3DES key for each mix node in a chain between the sender and receiver; these 3DES keys are in turn encrypted with the public keys of each mix node. All Mixmaster messages are padded to the same length. When a message reaches a mix node, it decrypts the header, decrypts the body of the message, and then places the message in a ``message pool.'' Once enough messages have been placed in the pool, the node picks a random message to forward. As the underlying next-hop header in the message has been decrypted, the node knows to which destination to send this message. In this way a chain of remailers can be built, such that the first remailer in the chain knows the sender, the last remailer knows the recipient, and the middle remailers know neither. Remailers also allow for \emph{reply blocks}. These consist of a series of routing instructions for a chain of remailers which define a route through the remailer net to an address. Reply blocks allow users to create and maintain pseudonyms which receive e-mail. By prepending the reply block to a message and sending the two together to the first remailer in the chain, a message can be sent to a party without knowing his or her real e-mail address. \subsection{Rewebber} Goldberg and Wagner applied Mixes to the task of designing an anonymous publishing network called Rewebber\cite{taz-rewebber}. Rewebber uses URLs which contain the name of a Rewebber server and a packet of encrypted information. When typed into a web browser, the URL sends the browser to the Rewebber server, which decrypts the associated packet to find the address of either another Rewebber server or a legitimate web site. In this way, web sites can publish content without revealing their location. Mapping between intelligible names and Rewebber URLs is performed by a name server called the Temporary Autonomous Zone (TAZ), named after a novel by Hakim Bey. The point of the ``Temporary'' in the name of the nameserver (and the novel) is that static structures are vulnerable to attack. Continually refreshing the Rewebber URL makes it harder for an adversary to gain information about the server to which it refers. \subsection{Onion Routing} The Onion Routing system designed by Syverson, et. al. creates a mix-net for TCP/IP connections \cite{onion-routing-paper, onion-router}. In the Onion Routing system, a mixnet packet, or ``onion'', is created by successively encrypting a packet with the public keys of several mix servers, or ``onion routers.'' When a user places a message into the system, an ``onion proxy'' determines a route through the anonymous network and onion encrypts the message accordingly. Each onion router which receives the message peels the topmost layer, as normal, then adds some key seed material to be used to generate keys for the anonymous communication. As usual, the changing nature of the onion -- the ``peeling'' process -- stops message coding attacks. Onions are numbered and have expire times, to stop replay attacks. Onion routers maintain network topology by communicating with neighbors, using this information to initially build routes when messages are funneled into the system. By this process, routers also establish shared DES keys for link encryption. The routing is performed on the application layer of onion proxies, the path between proxies dependent upon the underlying IP network. Therefore, this type of system is comparable to loose source routing. Onion Routing is mainly used for sender-anonymous communications with non-anonymous receivers. Users may wish to Web browse, send email, or use applications such as {\tt rlogin}. In most of these real-time applications, the user supplies the destination hostname/port or IP address/port. Therefore, this system only provides receiver-anonymity from a third-party, not from the sender. Furthermore, Onion Routing makes no attempt to stop timing attacks using traffic analysis at the network endpoints. They assume that the routing infrastructure is uniformly busy, thus making passive intra-network timing difficult. However, the network might not be statistically uniformly busy, and attackers can tell if two parties are communicating via increased traffic at their respective endpoints. This endpoint-linkable timing attack remains a difficulty for all low-latency networks. \subsection{ZKS Freedom} Recently, the Canadian company Zero Knowledge Systems has begun the process of building the first mix-net operated for profit, known as Freedom \cite{zks}. They have deployed two major systems, one for e-mail and another for TCP/IP. The e-mail system is broadly similar to Mixmaster, and the TCP/IP system similar to Onion Routing. ZKS's ``Freedom 1.0'' application is designed to allow users to use a nym to anonymously access web pages, use IRC, etc. The anonymity comes from two aspects: first of all, ZKS maintains what it calls the Freedom Network, which is a series of nodes which route traffic amongst themselves in order to hide the origin and destination of packets, using the normal layered encryption mixnet mechanism. All packets are of the same size. The second aspect of anonymity comes from the fact that clients purchase ``tokens'' from ZKS, and exchange these token for nyms -- supposedly even ZKS isn't able to correlate identities with their use of their nyms. The Freedom Network looks like it does a good job of actually demonstrating an anonymous mixnet that functions in real-time. The system differs from Onion Routing in several ways. First of all, the system maintains Network Information Query and Status Servers, which are databases which provide network topology, status, and ratings information. Nodes also query the key servers every hour to maintain fresh public keys for other nodes, then undergo authenticated Diffie-Hellman key exchange to allow link encryption. This system differs from online inter-node querying that occurs with Onion Routing. Combined with centralized nym servers, time synchronization, and key update/query servers, the Freedom Network is not fully decentralized \cite{freedom-architecture}. Second, the system does not assume uniform traffic distribution, but instead uses a basic ``heartbeat'' function that limits the amount of inter-node communication. Link padding, cover traffic, and a more robust traffic-shaping algorithm have been planned and discussed, but are currently disabled due to engineering difficulty and load on the servers. ZKS recognizes that statistical traffic analysis is possible \cite{freedom-security}. Third, Freedom loses anonymity for the primary reason that it is a commercial network operated for profit. Users must purchase the nyms used in pseudonymous communications. Purchasing is performed out-of-band via an online Web store, through credit-card or cash payments. ZKS uses a protocol of issuing serial numbers, which are reclaimed for nym tokens, which in turn are used to anonymously purchase nyms. However, this system relies on ``trusted third party'' security: the user must trust that ZKS is not logging IP information or recording serial--token exchanges that would allow them to correlate nyms to users \cite{freedom-nyms}. \subsection{Web Mixes} Another more recent effort to apply a Mix network to web browsing is due to Federrath et. al.\cite{web-mix} who call their system, appropriately enough, ``Web Mixes.'' From Chaum's mix model, similar to other real-time systems, they use: layered public-key encryption, prevention of replay, constant message length within a certain time period, and reordering outgoing messages. The Web Mixes system incorporates several new concepts. First, they use an adaptive ``chop-and-slice'' algorithm that adjusts the length used for all messages between time periods according to the amount of network traffic. Second, dummy messages are sent from user clients as long as the clients are connected to the Mix network. This cover traffic makes it harder for an adversary to perform traffic analysis and determine when a user sends an anonymous message, although the adversary can still tell when a client is connected to the mixnet. Third, Web Mixes attempt to restrict insider and outsider flooding attacks by limited either available bandwidth or the number of used time slices for each user. To do this, users are issued a set number of blind signature tickets for each time slice, which are spent to send anonymous messages. Lastly, this effort includes an attempt to build a statistical model which characterizes the knowledge of an adversary attempting to perform traffic analysis. \subsection{Crowds} The Crowds system was proposed and implemented by Michael Reiter and Avi Rubin at T\&T Research, and named for collections of users that are used to achieve partial anonymity for Web browsing \cite{crowds}. A user initially joins some crowd and her system begins acting as a node, or anonymous {\it jondo}, within that crowd. In order to instantiate communications, the user creates some path through the crowd by a random-walk of {\it jondos}, in which each {\it jondo} has some small probability of sending the actual {\tt http} request to the end server. A symmetric key is shared amongst these path {\it jondos} to ensure link-encryption within a crowd. Once established, this path remains static as long as the user remains a member of that crowd. The Crowds system does not use dynamic path creation so that colluding crowd eavesdroppers are not able to probabilistically determine the initiator (i.e., the actual sender) of requests, given repeated requests through a crowd. The {\it jondos} in a given path also share a secret {\it path key}, such that local listeners, not part of the path, only see an encrypted end server address until the request is finally sent off. The Crowds system also includes some optimizations to handle timing attacks against repeated requests, as certain HTML tags cause browsers to automatically issue re-requests. Similar to other real-time anonymous communication channels (Onion Routing, the Freedom Network, Web Mixes), Crowds is used for senders to communicate with a known destination. The system attempts to achieve sender-anonymity from the receiver and a third-party adversary. Receiver-anonymity is only meant to be protected from adversaries, not from the sender herself. The Crowds system serves primarily to achieve sender and receiver anonymity from an attacker, not provide unlinkability between the two agents. Due to high availibility of data -- real-time access is faster that mix-nets as Crowds does not use public key encryption -- an adversary can more easily use traffic analysis or timing attacks. However, Crowds differs from all other systems we have discussed, as users are {\it members} of the communications channel, rather than merely communicating {\it through} it. Sender-anonymity is still lost to a local eavesdropper that can observe all communications to and from a node. However, other colluding {\it jondos} along the sender's path -- even the first-hop -- cannot expose the sender as originated the message. Reiter and Rubin show that as the number of crowd members goes to infinity, the probable innocence of the last-hop being the sender approaches one.