% $Id: minion-systems.tex 949 2003-11-20 20:38:22Z arma $
\documentclass{llncs}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{amsmath}

\begin{document}

%\title{Mixminion: a Strong Anonymity System to Resist Traffic Analysis}
\title{Mixminion: Strong Anonymity for Financial Cryptography}
%\title{Mixminion: The Case for Strong Anonymity in Financial Cryptography}
\author{Nick Mathewson and Roger Dingledine}
\institute{The Free Haven Project\\
\email{\{nickm,arma\}@freehaven.net}}

\maketitle

\begin{center}Systems Track\end{center}
\begin{abstract}
Anonymous communication is a valuable but underused tool for securing
financial communications.  As early as the first commercial telegraph
codes, businesses have recognized the value of cryptography to protect
their communication from prying eyes.  But cryptography alone still
allows adversaries to discover confidential business relationships by
performing traffic analysis to reveal the {\it presence} of such
communication.

Mixminion is an open source, deployed system under active development.
% XXX call it free software?
It resists known forms of traffic analysis, allowing parties to
communicate without revealing their identities.
\end{abstract}

\begin{center}
Keywords: anonymity, privacy, traffic analysis, corporate espionage
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction: Anonymity and Digital Commerce}
In this paper, we argue that strongly anonymous (traffic analysis
resistant) communications are valuable to the business and finance
community, and we present Mixminion, an anonymous communication system
in active development.

As early as when the first business-related telegrams were received by an
untrusted telegraph operator, businesses have recognized the
importance of encrypting messages on communications networks.  Less
well-recognized, however, is the importance of protecting business
communications against traffic analysis.

Whenever data travels over public networks, an eavesdropper can
usually link messages to their senders and receivers with little
difficulty.  Although this linkage might initially seem of little
interest, there are many circumstances under which the volume of
communication between two sites can reveal sensitive information.  For
example, linking senders and recipients can reveal:
\begin{itemize}
\item Whether (and how often) the CEO of a Fortune 500 corporation has
  been exchanging email with the CEO of a rumored buyout partner.
\item Which suppliers' websites a given purchaser is visiting.
\item Which prospective customers a vendor has emailed and which of
  them responded via email.
\item In some digital cash designs, the volume and frequency of
  transactions between participants and between participants and
  banks.
\end{itemize}
When an organization is geographically distributed, its internal
communications can become a target of traffic analysis.  In this way,
an eavesdropper may learn:
\begin{itemize}
\item Which locations have employees working late.
\item Which locations have employees consulting job-hunting websites.
\item Which research groups are communicating with a company's patent
  lawyers.
\item What volume of communication an R\&D group is exchanging with a
  production line.
\end{itemize}
While firewalls or virtual private networks can conceal a network's
interior view, they do not provide any further privacy against traffic
analysis attacks.

These attacks are certainly feasible today.  On the simplest level,
corporate website administrators routinely survey logs to learn which
competitors and customers have viewed which parts of their websites,
and how often.  The more sophisticated attacks are almost certainly
within the capabilities of a nation able and inclined to use signals
intelligence resources for economic goals, as the US has (probably)
done with the NSA-backed ECHELON system.  Finally, in between the threat of
unsophisticated analysis and the threat of mid-sized foreign
governments, is the potentially more compelling threat of espionage
from competing companies.  The risk of a competitor bribing an
employee at a nearby telecom, or sneaking eavesdropping equipment into
a colocation facility, is not well explored in the public literature.

Traffic analysis resistance is also a critical component to more
advanced financial cryptography systems, such as anonymous digital
cash schemes and private auctions: without anonymous transport, these
schemes provide very little of the privacy that they promise.

\subsection{Background}
David Chaum launched the study of anonymous communications in 1981,
with his design for a network of anonymizing servers or \emph{mixes}
\cite{chaum-mix}.  In Chaum's design, message senders iteratively 
wrap their messages in the public keys of a sequence of mixes, then send
the messages to the first mix in the sequence.  Each mix in turn
removes a layer of encryption from the messages, waits until enough
messages have been received, then re-orders the messages and sends
them to the next mix in the sequence.  If any mix in the sequence
correctly hides the correlation between incoming and outgoing messages,
an eavesdropper should not be able to connect senders to recipients.

The first widespread public implementations of mixes were produced by
contributors to the Cypherpunks mailing list. These ``Type I''
\emph{anonymous remailers}
were inspired both by the problems surrounding the {\tt anon.penet.fi}
service \cite{helsingius}, and by theoretical work on mixes. Hughes
wrote the first Cypherpunk anonymous remailer \cite{remailer-history};
Finney followed closely with a collection of scripts that used Phil
Zimmermann's PGP to encrypt remailed messages. Later, Cottrell
implemented the Mixmaster system \cite{mixmaster-spec},
or ``Type II'' remailers, which added message padding, message pools,
and other mix features lacking in the original Cypherpunk remailers.
Unfortunately, Mixmaster does not support replies or anonymous
recipients.  Thus, people who need {\it bidirectional} anonymous
communication must use the older and less secure
Cypherpunk network. 

In parallel with the evolution of mix nets for mail-like
communication, other work has progressed on systems suitable for
faster communication. These systems range from the simple centralized
Anonymizer \cite{anonymizer}, to distributed sets of servers like Freedom
\cite{freedom2-arch} and Onion Routing \cite{tor-design},
to designs for totally decentralized peer-to-peer networks like Tarzan
\cite{tarzan:ccs02}
and MorphMix \cite{morphmix:wpes2002}.  But while these systems are
more suitable than mixes for low-latency applications such as web browsing,
chatting, and VoIP, they are more vulnerable to certain attacks than
are traditional high-latency mix-net designs.  Specifically, if an
eavesdropper can observe both sides of the communication, the
timing of message sending and delivery will quickly link
% XXX there's a paper to be presented before ours that claims to
%     help solve this. tone down / rephrase?
senders and recipients.  Although these systems block
certain kinds of traffic analysis, they cannot defend against an
adversary with significant eavesdropping abilities.

\section{Mixminion: Open source strong anonymity}
Mixminion is the reference implementation of the Type III mix-net,
which was first designed between 2001 and 2002 to address
weaknesses in Type II and also to reintroduce reply messages in a
secure manner, thus allowing us to retire the (insecure) Type I
network.  Mixminion's design was first published in
\cite{minion-design}; its specification is publicly available
\cite{mixminion-spec}.

The Type III mix-net design improves on previously deployed designs:
\begin{itemize}
\item {\bf Secure single-use reply blocks, with indistinguishable
  replies.}  In order to prevent attacks on earlier systems in which
  multiple-use
  reply channels can be used to break anonymity, Type III supports only
  single-use reply channels.  These replies are indistinguishable from
  forward messages to all parties except their senders and recipients.
\item {\bf Forward-secure, email-independent transfer protocol.}
  Integration with mail transfer agents (such as Sendmail) has made
  earlier remailer networks fragile.  Type III uses its own
  TLS-based transfer protocol to relay messages between mixes.  The
  protocol is forward-secure: that is, future mix compromises cannot
  compromise past traffic recorded by an eavesdropper.
\item {\bf Integrated directory design.}  Earlier deployed mix-nets
  have left the issue of mix discovery to a set of unspecified,
  uncoordinated, out-of-band keyservers.  Type III introduces
  synchronized directory servers to sign mix directories and avoid
  single-point-of-failure issues.
\item {\bf Integrated key rotation.}  Under Type I and Type II, key
  rotation occurs out of band, when a mix's administrator publicly
  announces a new key and tries to persuade other mixes and users to
  stop using the old key.  This process can take weeks to months.
  Type III's key rotation is more practical: mixes publish new keys to
  directories so that clients can retrieve them automatically.
\item {\bf Dummy traffic.} Type III introduces a simple cover traffic
  design to complicate traffic analysis within the network.
\end{itemize}

The first public version of Mixminion was released in December of
2002.  Since then, we have grown a deployed network of 22 testing
servers,\footnote{As of 8 September 2003.} operated by volunteers in
the US, Canada, and Europe.  (For comparison, the widely used Mixmaster
network currently has about 30 working mixes.)  The current codebase
implements anonymous messages, anonymous replies,
erasure-correcting fragmentation and
reassembly, address blocking, reliable message delivery, and an
automated server directory with key rotation.

\section{Future work}
Before Mixminion is ready for broad-scale user adoption, more
work remains, both in research and in implementation.  The largest
areas ahead are, broadly:
\begin{itemize}
\item {\bf Usability and client implementation.}  For an anonymity
  system to hide its users' communications, it must have many users to
  hide them among: thus usability directly affects security
  \cite{econymics,back01}.  The current Mixminion client runs only from a
  command line on Unix-like platforms, though a Windows32 client is
  planned within the next few months.  For maximum user acceptance,
  more work is needed to integrate Mixminion with existing email
  applications.
\item {\bf Distributed directory design.}  It is essential that all
  users of the Type III network have an identical view of which
  servers are available, reliable, and trustworthy.  The current
  implementation uses a centralized directory, which gives the entire
  network a single point of failure.  Our design calls for a more
  distributed directory implementation.
\item {\bf Pseudonymity.} Currently, there is no practical way to
  maintain a long-term pseudonymous identity via Type III reply
  blocks.  Although we have a specification for a workable pseudonym
  server, the server is not yet implemented.
\item {\bf Abuse prevention.} One of the best ways to attack users'
  anonymity is by mounting a denial of service (DoS) attack against some or
  all of the Type III mix-net, in order to force users onto
  compromised servers, or to force them to use other (less secure)
  channels. At the same time, we need a way to let uninterested recipients
  opt out of anonymous mail, without letting them deny service to
  legitimate users. We need more research on how much impact these
  DoS opportunities can have on anonymity.
\item {\bf Enterprise integration.}  The current implementation,
  because of its volunteer roots, assumes that most installations are
  for a single computer.  In an enterprise environment, however, it
  could be more reasonable to integrate a single Mixminion node as a
  part of the outgoing email server. This \emph{enclave firewall} model
  allows the enterprise's security administrators to do their jobs while
  still protecting the company's activities from outside observers.
\end{itemize} 

Beyond software development and research, much exploration remains
within the broader financial cryptography community to discover
appropriate applications and economic models for anonymous
communication channels.  Despite the potential applications of strong
traffic analysis resistance in the business world, little effort has
been spent in solving usability and scalability problems faced by
these users.

There is reason for hope.  The incentive structure of anonymity
systems strongly argues against in-house measures to block traffic
analysis: an organization using a ``private'' anonymity system cannot
hide its traffic among traffic from other organizations.  Thus,
finance organizations that need to resist traffic analysis have an
incentive to seek common solutions that not only meet their own needs,
but that will attract as many users as possible.\cite{econymics} The
same reasoning gives non-business users an
incentive to construct their systems to meet the needs of business and
financial communities.

Mixminion aims to be the first deployed anonymous communication system
that provides strong traffic analysis resistance, emphasizes
usability, supports bidirectional communication, and can be
sustained for the long term.  These goals require more
research on anonymity designs, more work on human/computer interaction
and interfaces, and more awareness of the need for privacy around the
world.  We feel that pushing the envelope on all fronts and exploring
the relationships between these requirements is the best way to bring
the world closer to ubiquitous securable communications.

\bibliographystyle{plain}
\bibliography{minion-systems}

\end{document}

