
%% 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.




