\documentclass[runningheads]{llncs}
\usepackage{amsmath, amssymb}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{psfrag}
\usepackage{amsfonts}
\usepackage{picins} %ADDED

\title{Comparison between two practical mix designs}  

\author{Claudia D\'{\i}az\inst{1} \and Len Sassaman\inst{2} \and Evelyne Dewitte\inst{1}}

%foo

\institute{K. U. Leuven ESAT-COSIC \\
Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium
\email{\{claudia.diaz,dewitte\}@esat.kuleuven.ac.be}
\and
{\tt rabbi@abditum.com}}

%foo

\bibliographystyle{alpha}

\date{}

\begin{document}

\maketitle

\begin{abstract}

We evaluate the anonymity provided by two popular email mix
implementations, Mixmaster and Reliable, and compare their effectiveness
through the use of simulations which model the algorithms used by these
mixing applications. Our simulations are based on actual traffic data
obtained from a public anonymous remailer (mix node). We determine that
assumptions made in previous literature about the distribution of mix
input traffic are incorrect: in particular, the input traffic does not
follow a Poisson distribution. We establish for the first time that a
lower bound exists on the anonymity of Mixmaster, and discover that under
certain circumstances the algorithm used by Reliable provides no
anonymity. We find that the upper bound on anonymity provided by Mixmaster
is slightly higher than that provided by Reliable.

We identify flaws in the software in Reliable that further compromise
its ability to provide anonymity, and review key areas that are necessary
for the security of a mix in addition to a sound algorithm. Our analysis
can be used to evaluate under which circumstances the two mixing
algorithms should be used to best achieve anonymity and satisfy their
purpose. Our work can also be used as a framework for establishing a
security review process for mix node deployments.

\end{abstract}


\section{Introduction}


The Internet was initially perceived as a rather anonymous environment.
Now we know that it can be a powerful surveillance tool: anyone capable of
listening to the communication links can spy on Internet users, while data
mining techniques are becoming increasingly powerful and more widely
accessible.

Preserving privacy does not only mean keeping information confidential; it
also means not revealing information about who is communicating with whom.
Anonymous remailers (also called \emph{mixes}) allow their users to send
emails without disclosing the identity of the recipient to a third party.
They also allow the sender of a message to stay anonymous to the
recipient.

The objective of this work is to have quantitative results on the
anonymity actually provided by two mix software implementations in wide
deployment, to test the actual anonymity provided to the users of the
remailer service, and to compare the two different designs. We evaluate
anonymity in a single-node context. To assess the anonymity provided by
the entire remailer network, additional considerations are necessary. As
individual nodes are the basic component to the network of mixes, we aim
to provide information to be considered when choosing this component.  We
have used as input real-life data gathered from a popular remailer, and
simulated the behavior of the mix.


\section{Mixes}
\label{mixes}

Mixes are the essential building block of anonymous email services. A mix
is a router that hides the relationship between incoming and outgoing
messages. The mix changes the appearance and the flow of the message
traffic. In order to make messages indistinguishable from each other the
mix uses techniques such as padding and encryption, which provide bitwise
unlinkability between inputs and outputs. Techniques such as reordering
messages delaying them, and generating dummy traffic are used to modify the
flow of messages. This modification of the traffic flow is needed to
prevent timing attacks that could disclose the relationship between
input and output messages by observing the time the messages arrived at
and left from the mix.

The idea of mixes was introduced by Chaum~\cite{chaum-mix}.  This first
design was a \emph{threshold mix}, a mix that collects a certain number of
messages and then flushes them. Since then, variants on this first design
have been proposed in the literature. In this paper, we focus on two
practical mix designs that have been implemented and are part of the
Mixmaster remailer network~\cite{mixmaster-announce}, which has been
providing anonymous email services since 1995.

The first design is called ``Mixmaster'' (as the remailer network) because
it is descended from the original software program designed by Cottrell
\cite{remailer-attacks,mixmaster-spec}. The second design, called
``Reliable'', uses a different reordering strategy~\cite {RProcess}. The
details of the two remailers are explained in the following sections. We
compare version 3.0 of the Mixmaster software and version 1.0.5 of
Reliable.

\subsection{Mixmaster}

Mixmaster\footnote{Mixmaster version 3.0, as well as Reliable, also
  optionally supports the older ``Cypherpunk'' remailer message
  format. For the purposes of this paper, we are assuming that the
  remailers are being operated without this support. As anonymity sets
  for the two protocols generally do not overlap, this does not impact
  our results. The Cypherpunk remailer protocol is known to contain
  numerous flaws, and should not be used if strong anonymity is
  required~\cite{remailer-attacks,mixminion}.}  
is a \emph{pool} mix. Pool mixes process the messages in batches. They
collect messages for some time, place them in the pool (memory of the
mix), and select some of them for flushing in random order when the
flushing condition is fulfilled.
Mixmaster is a timed mix that has a \emph{timeout} of 15
minutes. During this period of time, it collects messages that are
placed in the pool of the mix. When the timeout expires, the mix takes
a number of messages from the pool that are forwarded to their next
destination, which may be another mix or a final recipient. 
The number $s$ of messages sent
in a \emph{round} (one cycle of the mix) is a function of the number
$n$ of messages in the pool:
\begin{verbatim}
if (n<45) s=0;
else if (0.35*n < 45) s=n-45;
else s=0.65*n;
\end{verbatim}

Mixmaster is represented in the generalized mix model (GMM) proposed by
D\'{\i}az and Serjantov~\cite{DS03} as shown in
Figure~\ref{fig-mm}. In this model, the mix is represented at the time of
flushing. The function $P(n)$ represents the probability that a message is
flushed by the mix, as a function of the number $n$ of
messages in the pool. Note that $P(n)=s/n$.
\begin{figure}
\begin{center}
%\includegraphics[width=7cm,
%height=3cm]{/users/sista/dewitte/PHD/papers/source/mixmaster.eps}
\includegraphics[width=7cm, height=3cm]{source/mixmaster.eps}

\caption{Mixmaster in the GMM}
\label{fig-mm}
\end{center}
\end{figure}

\subsection{Reliable}

Reliable is loosely based on the Stop-and-Go (\emph{S-G Mix}) mix proposed
by Kesdogan \emph{et al.} in~\cite{stop-and-go}. In S-G mixes (also called
\emph{continuous mixes}), the users generate a random delay from an
exponential distribution. The mix holds the message for the specified
delay and then forwards it. The messages are reordered by the randomness
of the delay distribution. This mix sends messages continuously: when it
has been kept for the delay time it is sent out by the mix.

Reliable interoperates with Mixmaster on the protocol level by using the
Mixmaster message format for packet transfer. Reliable uses a variant of
the \emph{S-G mix} design.\footnote{The theoretical S-G mix design assumes
that the delay parameter adapts to the traffic load, that is, the users
should set the delay parameter according to the amount of input traffic
the mix is receiving. This feature is not implemented in Reliable, which
has a static delay parameter. True S-G mixes also implement timestamps in
order to prevent active attacks ($n-1$ attacks in particular). Previous
work has argued that this method is unlikely to be effective, since the
senders must be able to determine the appropriate delay for each mix in
the path~\cite{sds}. True S-G mixes would require a service provide such
information to senders. Regardless, as the message protocol was originally
designed with only a pool mix network in mind, these timestamps are not
used. Reliable thus does not provide any resistance to this kind of active
attack.}

In Reliable, the delay may be chosen by the sender from an exponential
distribution of mean one hour. If the sender does not provide any delay to
the mix, then the mix itself picks a delay from a \emph{uniform} distribution of
one and four hours. Note that these parameters of the delay distributions
are configurable, and therefore many remailer operators may set them lower
to provide a faster service.


\subsection{Dummy traffic}
\label{dummy}

A dummy message is a \emph{fake} message introduced into the mix network
to make it more difficult for an attacker to deploy attacks that
compromise the anonymity of a message. The dummy messages are produced by
the mixes, and use a chain of mix nodes that terminates at a mix instead
of a real recipient.

Dummies are indistinguishable from real messages as they travel in the mix
network. Since they are introduced to prevent traffic analysis, the dummy
policy should maximize the number of possible destinations for the
messages flushed by the mix. Dummy traffic has an impact when analyzing
the mix network as a whole. We have made measurements that show that the
impact of dummies on the anonymity provided by a single mix is very small.
To make the comparison of Mixmaster and Reliable easier, we have not taken
into account the dummy policies of these two mixes in the results
presented in this paper.

\paragraph{Dummy policy of Mixmaster}
Each time a message is received by Mixmaster, $d_1$ dummies are generated
and inserted in the pool of the mix. The number $d_1$ of dummies generated
follow a geometrical distribution whose parameter has the default value of
$1/10$. In addition, each time Mixmaster flushes messages, it generates a
number $d_2$ of dummies that are sent along with the messages. The number
$d_2$ of dummies follows a geometrical distribution whose parameter has
the default value $1/30$.


\paragraph{Dummy policy of Reliable}
Reliable's default dummy policy consists of the generation of $25$ dummies
every 6 hours. The time these dummies are kept in the mix is selected from
a uniform distribution whose minimum value is $0$ and maximum is $6$
hours.



\section{Anonymity metrics}
\label{metrics}

In this section we introduce the anonymity metrics for mixes and we
present the attack model that we have considered. Let us first define
anonymity in this context. \emph{Anonymity} was defined by Pfitzmann
and K\"ohntopp~\cite{Pfitzmann00} as \emph{``the state of being not
  identifiable within a   set of subjects, the anonymity set''}.

The use of the information theoretical concept of entropy as a metric for
anonymity was simultaneously proposed by Serjantov and Danezis
in~\cite{Serj02} and by D\'{\i}az \emph{et al.} in \cite{Diaz02}. The
difference between the two models for measuring anonymity is that
in~\cite{Diaz02} the entropy is normalized with respect to the number of
users. In this paper we will use the non-normalized flavor of the metric.

The anonymity provided by a mix can be computed for the incoming or for
the outgoing messages. We call this \emph{sender anonymity} and
\emph{recipient anonymity}.

\paragraph{Sender anonymity.} 
To compute the sender anonymity, we want to know the effective
size of the anonymity set of senders for a message output by the mix.  
Therefore, we compute the entropy of the probability distribution that
relates our target outgoing message with all the possible inputs.

\paragraph{Recipient anonymity.}
To compute the effective recipient anonymity set size of an
incoming message that goes through the mix, we have to compute the entropy
of the probability distribution that relates the chosen input with all
possible outputs. 
\\

Note that in these two cases, the metric computes the anonymity of a
\emph{particular} input or output message; it does not give a general
value for a mix design and it is dependent on the traffic pattern. The
advantage of this property is that mixes may offer information about the
\emph{current} anonymity they are providing. The disadvantage is that it
becomes very difficult to compare theoretically different mix designs.
Nevertheless, it is possible to measure on real systems (or simulations)
the anonymity obtained for a large number of messages and provide
comparative statistics, as we do in this paper.

To measure Mixmaster's sender and recipient anonymity, we have applied the
formulas provided by D\'{\i}az and Preneel in~\cite{diaz_ih04}. The anonymity
of Reliable has been measured using the formulas presented in
Appendix~\ref{form-reliable}. Note that we could not apply the method used
by Kesdogan~\cite{stop-and-go} because we did not make any assumption on
the distribution of the mix's incoming traffic (Kesdogan assumes incoming
Poisson traffic).


\subsection{Attack model}


The anonymity metric computes the uncertainty about the sender or the
recipient of a message, given that some information is available. In
our case, we assume that the mix is observed by a passive attacker,
who can see the incoming and outgoing messages of the mix. The
attacker knows all internal parameters of the mix so he can
effectively compute the anonymity set size for every incoming and
outgoing message. 

Previous work by Serjantov \emph{et al.}~\cite{sds} has focused on
active attacks on several mix designs. We refer to this paper for
complementary information on the resistance of several mixes to active
attackers. 


\section{Simulators} \label{sims} We have implemented Java simulators for
Reliable and Mixmaster. We have fed the simulated mixes with real input,
obtained by logging a timestamp each time a message arrived to a working
Mixmaster node (note that the information we logged does not threaten the
anonymity of the users of the mix). We have used four months of incoming
traffic (July-November 2003) to obtain the results presented in
Section~\ref{results}.

In order to make a fair comparison, we have set the mean of the
exponential delay of Reliable (default $1$ hour) to be the same as
provided by Mixmaster for the given four months of input ($43$
minutes)\footnote{We have made some simulations for Reliable with mean
$1$ hour, and the results obtained do not differ significantly from
the ones presented in this paper (i.e., some messages do not get any
anonymity at all). We do not include these figures here due to a lack
of space, but they will be added to an extended abstract version of the
paper.}. We have assumed 
users choose their delays from an exponential distribution. The
mix-chosen uniform delay option has not been taken into account, due
to the infeasibility of implementing algorithms that compute the
anonymity for such a delay distribution without making assumptions on
the traffic pattern, as explained in
Appendix~\ref{form-reliable}. 

The simulators log the delay and the anonymity for every
message. Mixes are empty at the beginning of the simulation. The
first message that is taken into account for the results is the one
that arrives when the first input has been flushed with $99\%$
probability. All messages flushed after the last arrival to the mix
are also discarded for the results. This is done in order to eliminate
the transitory initial and final phases. In our simulations, the
number of rounds discarded in the initial phase is $3$, and the number
of rounds discarded in the final phase is $39$. The total number of
rounds for our input traffic is $11846$.  

\section{Results}
\label{results}

In this section we present and analyze the results we have obtained
with the simulations. 


\subsection{Analysis of the input traffic}

It is a common assumption in the literature that the arrivals at a mix
node follow a Poisson process. We have analyzed the input traffic, and
found that it does not follow a Poisson distribution nor can it be modeled 
with a single time-independent parameter. 

% ADDED (Evelyne)
A Poisson process is modeled by a single parameter $\lambda$ representing the
expected amount of arrivals per (fixed) time interval. If the arrivals to a 
mix are assumed to follow a Poisson process with an average of $\lambda$ 
arrivals per time interval $\Delta t$ and we denote the number of arrivals
in such a time interval by $X$, then $X$ is Poisson distributed with parameter
$\lambda$: $X \sim \mathrm{Poiss}(\lambda)$. It is important to note that $\lambda$
is \emph{time-independent}.

In our statistical analysis we first \emph{assumed} that the process of arrivals
\emph{was} a Poisson process and we estimated the parameter $\lambda$. The
latter was done by taking the maximum likelihood estimate given the number
of arrivals per time interval $\Delta t = 15$ minutes ($N=11800$). We also
constructed a $95$\% confidence interval for this estimate. In this way we
found
$\hat{\lambda} = 19972$ with confidence region $[19891 ; 20052]$.  Then we
performed a goodness-of-fit test to determine if we can reject the hypothesis
\begin{equation*}
H_0: \mathrm{the\ number\ of\ arrivals\ per\ time\ interval\ } \sim\ \mathrm{Poiss}(\bar\lambda)\ ,
\end{equation*}
where $\bar{\lambda}$ varies over the constructed confidence
interval. The goodness-of-fit test we used is the well-known Chi-square
test (df=$n-1$=$11802$).  Using a significance level of $0.01$, the null
hypothesis gets rejected (Chi-value=$826208$)! 
% END (Evelyne)

In the left part of Figure~\ref{arr-day} we show the number of messages
received by the mix per hour. The right part of Figure~\ref{arr-day} shows
the evolution of the arrivals per day. We can observe that the traffic
that arrived at the mix during the first month is much heavier than in the
following three months. This shows that the input traffic pattern that
gets to a mix node is highly unpredictable and that the assumption of
lambda being time-independent cannot hold.

Figure~\ref{frec-day} shows the frequency in hours and in days of receiving a
certain number of arrivals. We can see that in most of the hours 
the mix receives less than $20$ messages.

\begin{figure}
    \noindent
%\includegraphics[width=6cm,
%height=4cm]{/users/sista/dewitte/PHD/papers/source/hist-arr-hour.eps}
\includegraphics[height=5cm]{source/hist-arr-hour.eps}
%\includegraphics[width=6cm,
%height=4cm]{/users/sista/dewitte/PHD/papers/source/hist-arr-day.eps} 
\includegraphics[height=5cm]{source/hist-arr-day.eps} 
%\caption{Frequency analysis of inputs}
\caption{Incoming traffic patterns}
 \label{arr-day}
    \noindent
%\includegraphics[width=6cm, height=4cm]{/users/sista/dewitte/PHD/papers/source/arr-hour.eps}
%\includegraphics[width=6cm, height=4cm]{/users/sista/dewitte/PHD/papers/source/arr-days.eps} 
\vspace{0.5cm}

\includegraphics[height=5cm]{source/arr-hour.eps}
\includegraphics[height=5cm]{source/arr-days.eps} 
\caption{Frequency analysis of inputs}
%\caption{Incoming traffic patters}
\label{frec-day}

%\includegraphics[width=5cm, height=5cm]{/users/sista/dewitte/PHD/papers/source/3Dplot_Recip.eps}
%\includegraphics[width=5cm, height=5cm]{/users/sista/dewitte/PHD/papers/source/3Dplot_Sender.eps}
\vspace{0.5cm}
%\includegraphics[width=5cm, height=5cm]{source/3Dplot_Recip.eps}
%\includegraphics[width=5cm, height=5cm]{source/3Dplot_Sender.eps}
\includegraphics[height=5cm]{source/PlotCorr_Dela_Recip_Message.eps}
\includegraphics[height=5cm]{source/PlotCorr_Dela_Send_Message.eps}

\caption{Correlation Delay-Anonymity for Mixmaster}
\label{3d-sen}

\end{figure}


\subsection{Analysis of Mixmaster}

We have simulated a Mixmaster node as explained in Section~\ref{sims}.
Mixmaster is a pool mix and processes messages in batches. The recipient
anonymity of each message in a given round is the same. Equivalently, all
outputs of a round have the same sender anonymity value. In this section
we show the results obtained in our simulation.

In Figure~\ref{3d-sen} we show the correlation between the recipient anonymity
and the delay for every message. Figure~\ref{3d-sen} shows the
same for sender anonymity. 

The first conclusion we come to when observing the figures is that
there is a lower bound to the anonymity of Mixmaster. It is worth
noting that, so far, we do not know any theoretical analysis of pool
mixes able to predict the anonymity a pool mix provides, and prior to this
analysis there were no figures on the anonymity that Mixmaster was
actually providing. With this simulation,
we can clearly see that Mixmaster guarantees a minimum sender and
recipient anonymity of about $7$. This means that the sender
(recipient) of a message gets a minimum anonymity equivalent to perfect
indistinguishability among $2^7=128$ senders (recipients). 

We can see that the minimum anonymity is provided when the traffic
(arrivals) is low. As the traffic increases, anonymity increases,
getting maximum values of about $10$ (i.e., equivalent to perfect
indistinguishability among $2^{10}=1024$) senders or recipients. 
We also observe that the delays of the messages don't take high 
values, unless the traffic load getting to the mix is very low.

In order to study the behavior of the mix under different traffic loads,
we have plotted values of delay and anonymity obtained in the simulation 
for the rounds with few arrivals (low traffic), intermediate number of 
arrivals (medium traffic), and many arrivals (high traffic).

We have selected the low, medium, and high traffic taking into account 
the data statistics of the arrival process:
\begin{description}
\item[Low traffic:] all rounds where the number of arrivals was 
between the first and third quartile ($1 \leq$\ data $\leq\ 17$); 
hence $50$ percent of the rounds
are denoted as normal traffic.
\item[Medium traffic:] all rounds where the number of arrivals was greater
than the third quartile but lower than the outlier bound ($17 <$\ data $\leq\ 41$).
\item[High traffic:] all rounds with outlier values for the incoming
messages (data $> 41$).
\end{description}

In Figure~\ref{del-mm} we show the minutes of delay of every message (the
x-axis indicates the evolution in time).  We can see that the delay only
takes high values when the traffic is low. The fact that some messages
appear as having a delay close to zero in the low traffic figure is due to
the fact that we have more samples, so there are messages that arrive just
before the flushing and are forwarded immediately. In Figure~\ref{an-mm}
we show the recipient anonymity of every message (the sender anonymity
presents very similar characteristics). We can see that as the traffic
increases, the anonymity provided takes higher values. No matter how low
the traffic load is, the anonymity provided by Mixmaster is always above
$7$.
 
\begin{figure}
\begin{center}
%\includegraphics[width=10cm, height=5 cm]{/users/sista/dewitte/PHD/papers/source/mm-del.eps}
\includegraphics[height=5cm]{source/mm-del.eps}
\caption{Delay values for Mixmaster}
\label{del-mm}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
%\includegraphics[width=10cm, height=4 cm]{/users/sista/dewitte/PHD/papers/source/mm-sanon.eps}
\includegraphics[height=5cm]{source/mm-sanon.eps}
\caption{Anonymity values for Mixmaster}
\label{an-mm}
\end{center}
\end{figure}


\subsection{Analysis of Reliable}


The theoretical method proposed in~\cite{stop-and-go} that gives a 
probabilistic prediction on the anonymity provided by Reliable is 
based on the assumption of Poisson traffic. As we have seen, this assumption
is definitely not correct for email mix traffic. 

We have simulated a Reliable mix as explained in
Section~\ref{sims}. 
Reliable treats every message independently: when it receives a message
it delays it for a predetermined amount of time (selected from an exponential
distribution) and then forwards it. We represent a star, '*', per message.

In Figure~\ref{rel-sen} we present the sender and recipient anonymity
provided by Reliable 
for the real stream of inputs we have considered.
We can see that the
anonymity takes minimum values close to zero, which means that some of
the messages can be trivially traced by a passive attacker. The
maximum values of Reliable's anonymity for this input are lower  
than Mixmaster's maximums.
Figure~\ref{sen-rec} shows the highly correlated values of sender and
recipient anonymity for both Reliable and Mixmaster. We can clearly see
that for Reliable some of the messages get nearly no anonymity, while the
ones of Mixmaster get at least sender and recipient anonymity $7$.

\begin{figure}
    \noindent
%    \includegraphics[width=5cm, height=3cm]{/users/sista/dewitte/PHD/papers/source/rel-sen.eps}
%    \includegraphics[width=5cm, height=3cm]{/users/sista/dewitte/PHD/papers/source/rel-rec.eps}
    \includegraphics[height=6cm]{source/rel-sen.eps}
    \includegraphics[height=6cm]{source/rel-rec.eps}
\caption{Correlation Delay-Anonymity for Reliable}
    \label{rel-sen}

\vspace{0.5cm}
%\includegraphics[width=5cm, height=3cm]{/users/sista/dewitte/PHD/papers/source/PlotCorr_Send_Recip_Message.eps}
%\includegraphics[width=5cm, height=3cm]{/users/sista/dewitte/PHD/papers/source/sen-rec.eps}
\includegraphics[height=6cm]{source/sen-rec.eps}
\includegraphics[height=6cm]{source/PlotCorr_Send_Recip_Message.eps}
\caption{Correlation Sender-Recipient Anonymity for Reliable and Mixmaster}
\label{sen-rec}
\end{figure}


\subsection{Mixmaster vs. Reliable}

As we have shown in the previous two sections, Mixmaster and Reliable
have very different behaviors for the same traffic stream. Note that
we have modified the default ($1$ hour) mean delay of Reliable, so that
the average delay is the same as Mixmaster for comparison purposes.

Mixmaster prioritizes the anonymity over the delay, and it provides a
minimum recipient (sender) anonymity of around $7$, equivalent to perfect
indistinguishability among $2^7=128$ input (output) messages. When the
traffic load decreases, Mixmaster provides a larger latency to keep the
anonymity at high levels.

Reliable delays messages according to an exponential distribution,
regardless of the traffic load. This has an effect on the anonymity,
in that it will only have high values when there is a high traffic
load. When the traffic load decreases, the anonymity provided by
Reliable drops to very low values. In some cases of very low load,
Reliable does not provide anonymity at all.

Our conclusion is that a continuous mix like Reliable is not
appropriate to provide anonymous services for applications that do not
have real-time requirements (like email). A pool mix like Mixmaster
should be used instead. 

Continuous mixes like Reliable may be useful for real-time
applications with tight delay constraints (like web
browsing). Nevertheless, in order to provide acceptable levels of
anonymity, the traffic load should be kept high.

\section{Other factors that influence anonymity}

We have evaluated the anonymity strength of the mixing algorithms
implemented in Mixmaster and Reliable. Additional factors have a direct
impact on the anonymity provided by the system. Concerns such as the
security of the underlying operating system, host server integrity, proper
implementation of the cryptographic functions provided by the remailer
software, and likelihood of administration mistakes all contribute to the
overall anonymity these software packages can provide. We assume that no
active attacks against the software occurred during the development or
compilation process, though additional concerns are present in that
area~\cite{trusting-trust}.

This paper does not aim to be an in-depth analysis of the full spectrum of
host-attacks against remailer nodes. Nevertheless, it is important to
mention some significant differences between Reliable and Mixmaster that
may affect their ability to provide adequate anonymity for their users.

\subsection{Host server integrity}

The security of an operating mix is dependent on the security of the
underlying host server. Many factors can impact the underlying system's
security. Some considerations include shared access to the system by
untrusted users, access to key material on disk or in memory, and the
ability to insert shims to intercept dynamically loaded libraries called by
the remailer software~\cite{slimjim}.

Reliable is limited to operation on the Windows platform. Mixmaster is
portable, and has been known to run on a wide variety of operating
systems.\footnote{There have been instances of remailers based on the
Mixmaster 3.0 codebase operating on SunOS, Solaris, SunOS, AIX, Irix,
BeOS, MacOS X, Windows NT (natively and through the use of Cygwin),
Windows 2000 (natively and through the use of Cygwin), Windows XP (through
the use of Cygwin), FreeBSD, NetBSD, OpenBSD, and multiple versions of
Linux.}

Host server security is ultimately the responsibility of the remailer
operator.

\subsection {UI issues}

% Good UI is important, though server operation requires skill in general.
% Hobbyists will find Reliable easier to use, Mixmaster needs UI
% improvements, or maybe this doesn't matter because hobbyists that can't
% figure out Mixmaster probably can't satisfy the requirements in the above
% section.

In a privacy application client, an intuitive user interface is essential
in order to ensure that the software is used consistently and
correctly~\cite{sassaman-lisa}. A greater level of skill can safely be
assumed when designing privacy software that is intended to be operated as
a service, however. Most anonymity systems, including mix implementations,
do imply a significant degree of complexity. Since the operation of a
public Internet service involves the correct configuration and maintenance
of the host server, this necessary complexity is acceptable as long as the
operator's skill level is sufficient. The level of skill required to
properly install, configure, and operate a mix node should not exceed that
required to properly install, configure, and operate the server itself.

The software packages we evaluated differed with regard to their interface
complexity in a number of areas.

In general, Reliable has a greater ``ease of use'' factor with respect to
its interface. Mixmaster automates many important tasks, such as adaptive
dummy generation, key rotation and key expiration announcement, and
integrates more easily with the host MTA.\footnote{Mail Transport Agent,
e.g. sendmail or postfix} Reliable's installation process is easier, but
its build process requires the use of third-party commercial applications
and assumes experience with Windows development, so most users will
install a pre-compiled binary. Compilation of Mixmaster is performed
through a simple shell script.

At first glance, it appears that Reliable will be easier for hobbyists to
operate than Mixmaster. However, Mixmaster's difficulty does not rise
above the difficulty of maintaining a secure Internet-connected server,
and thus has little effect on the overall security of a mix node
deployment.

\subsection{Programming language}

While the most critical factor in the creation of secure code is the
manner in which it is written, some languages lend themselves to greater
risk of exploitable mistakes. An inexperienced or unskilled programmer
will always be in danger of making an application insecure. The choice of
programming language merely sets the bar for the required level of
experience and ability necessary to develop applications in that language
safely. Thus, when evaluating the likelihood of the existence of
exploitable code in an application, it is worthwhile to consider the
programming language used to create that application. Mixmaster is written
in C, while Reliable is written in Visual Basic. Since neither Mixmaster
nor Reliable was written by seasoned software developers, we assume a
level of experience that would allow for simplistic security
mistakes.\footnote{The bulk of the code for Mixmaster 3.0 was written by
Ulf M\"oller as his first major software development project while
completing his undergraduate computer science
degree~\cite{personal-corresp-ulf}. He has since gained respect as a
skilled cryptographic software developer for his open source and
proprietary development projects. Reliable was authored under a pseudonym,
and we can only speculate about the level of experience of its author.
(There has been no known communication with the author of Reliable since
February, 2000).}

\subsection{Source code documentation}

To facilitate source code review and verification of an application's
correctness with regard to its implementation of a protocol, it is
beneficial for there to be both good commenting in the source code and a
clear specification for its behavior.

While neither program is sufficiently commented or written clearly enough
to allow a reviewer to easily learn how either system works by reading the
source code alone, there exists a complete specification of the Mixmaster
node behavior~\cite{mixmaster-spec}. No such specification or description
exists for Reliable.

\subsection{Included libraries} 

In addition to the standard POSIX libraries provided by the compilation
OS, Mixmaster 3.0 (the version of Mixmaster evaluated in this paper)
requires that the zlib~\cite{rfc-1950} and OpenSSL~\cite{OpenSSL}
libraries be included. Optionally, Mixmaster also links against
pcre~\cite{pcre} and ncurses~\cite{ncurses}.

Reliable requires many native Windows system calls as well as the
third-party application, Mixmaster 2.0.4.\footnote{Mixmaster 2.0.x has an
entirely different codebase than that of Mixmaster 3.0. While Reliable
relies on the Mixmaster 2.0.4 binary for some of its functionality,
Reliable is an independent application in its own right, and should not be
considered a mere extension to the Mixmaster codebase.}

\subsection{Cryptographic functions}

Both Mixmaster and Reliable avoid direct implementation of cryptographic
algorithms when possible. Mixmaster 3.0 relies strictly on OpenSSL for
these cryptographic functions. Any attackable flaws in the cryptographic
library used to build Mixmaster that affect the security of the
algorithms\footnote{It is understood that flaws in the cryptographic
algorithms will affect the security of software that relies upon those
algorithms. However, since most attacks on cryptographic applications are
due to flaws in the implementation, care must be taken when evaluating the
shared cryptographic libraries.} used by Mixmaster may be an attack
against Mixmaster as well.

Reliable abstracts the cryptographic operations one step further. To
support the Mixmaster message format, Reliable acts as a wrapper around
the DOS version of Mixmaster 2.0.4. Thus, any attack against the Mixmaster
message format due to implementation flaws in Mixmaster 2.0.x will work
against Reliable as well. Mixmaster 2.0.4 relies on the cryptographic
library OpenSSL or its predecessor SSLeay for the MD5, EDE-3DES, and RSA
routines.\footnote {Prior to the expiration of the RSA patent, versions of
Mixmaster 2.0.x offered support for the RSAREF and BSAFE libraries as well.
Use of these versions of Mixmaster is largely abandoned.}

\subsection{Entropy sources}

The quality of the entropy source plays an extremely important role in
both the pool mix and S-G mix schemes. In pool mix systems, the mixing in
the pool must be cryptographically random in order to mix the traffic in a
non-deterministic way. The timestamps that determine how long a message
should be held by an S-G mix implementation must also be from a strong
entropy source for the same reasons. In addition, the Mixmaster message
format specifies the use of random data for its message and header
padding.

Software is dependent on its underlying operating system for a good source
of entropy. Cryptographic quality entropy is a scarce resource on most
systems,\footnote{Systems that employ the use of noisy diodes or other
plentiful sources of entropy have less of a concern for entropy pool
exhaustion.} and therefore the entropy sources provided by most modern
operating systems actually provide PRNG output which has been seeded with
truly-random data.

Mixmaster uses OpenSSL's rand\_ functions.\footnote{OpenSSL relies on its
internal PRNG seeded with various system sources to provide
cryptographically strong entropy.} Reliable uses the standard Windows
system call, Rnd(), when obtaining entropy, with the exception of message
and header padding (which is done by the supporting Mixmaster 2.0.4
binary). The Rnd() function is not a cryptographically strong source of
entropy~\cite{MSKBVB-Rnd}. Rnd() starts with a seed value and generates 
numbers which fall within a limited range. Previous work has demonstrated
that systems that use a known seed to a deterministic PRNG are trivially
attackable~\cite{daw-ian-netscape}. While its use of Rnd() to determine
the latency for a message injected into the mix is the most devastating,
Reliable uses Rnd() for many other critical purposes as well.

\subsection{Network timing attacks}

By analyzing the input and output traffic of a mix, a skilled attacker may
be able to deduce the value of pool variables by timing observation. This
affects pool mixes more than S-G mixes, and possibly aids an attacker in
some non-host based active attacks such as $(n-1)$ attacks. The anonymity
strength of a remailer should not require pool values to be hidden, and
countermeasures to this class of active attacks should be
taken~\cite{rgb-mix}.


\section{Conclusions and future work}
\label{conclusions}

In this paper we have analyzed the traffic pattern of a real traffic
stream going through a working mix node and found that the traffic is not
Poisson, as it is commonly assumed in the literature. The traffic pattern
is highly unpredictable. Therefore, no assumptions on the traffic should
be made when designing a mix.

We measure the anonymity of the pool mix scheme used in Mixmaster by
applying a metric previously proposed in the literature. We provide our
own metric for evaluating the anonymity of the S-G mix variant used in
Reliable that does not assume a Poisson traffic pattern.

Our comparison of the two predominant mixing applications shows that
Mixmaster provides superior anonymity, and is better suited for the
anonymization of email messages than Reliable. Mixmaster provides a
minimum level of anonymity at all times; Reliable does not. Reliable's
anonymity drops to nearly zero if the traffic is very low. In high-traffic
situations, Mixmaster provides a higher maximum anonymity than Reliable
for the same stream of input: $10.5$ of Mixmaster versus $10$ of Reliable.
We have shown that Mixmaster provides higher average anonymity than
Reliable for the same input and same average delay. Due to its nature as a
pool mix, Mixmaster provides higher delays than Reliable in low traffic
conditions. Comparatively, due to the nature of S-G mixes, Reliable's
delay is not dependent on the traffic.

In addition, we have identified a number of key points of attack and
weakness in mix software to which anonymity software designers need to pay
particular attention. In addition to the areas of theoretical weakness
that we have identified, we discovered a fatal flaw in the use of
randomness in Reliable, which diminishes its ability to provide anonymity,
independent of our findings with regard to the S-G mix protocol.

We can conclude from our analysis of the mixing algorithms used by these
mix implementations that S-G mix variants such as the one used in Reliable
are not suitable for use with systems that may have occurrences of low
traffic on the network. While such S-G mixes may be an appropriate
solution for systems with a steady input rate, they are not suited for
systems with variable input traffic. Pool mixes such as Mixmaster should
be preferred for systems with fluctuating traffic loads and relaxed
latency contraints.

\subsection*{Acknowledgments}

Claudia D\'{\i}az is funded by a research grant of the K.U.Leuven.  
This work was also partially supported by the IWT STWW project on
Anonymity and Privacy in Electronic Services (APES), and by the
Concerted Research Action (GOA) Mefisto-2000/06 of the Flemish
Government. 

Evelyne Dewitte is a research assistant with the I.W.T. 
(Flemish Institute for Scientific and Technological Research in Industry).
Research supported by Research Council KUL: GOA-Mefisto 666, several PhD/postdoc \& fellow grants;
Flemish Government:
FWO: PhD/postdoc grants, projects, G.0240.99 (multilinear algebra), {G.0407.02 (support vector machines)}, G.0197.02 (power islands), 
G.0141.03 (identification and cryptography), G.0491.03 (control for intensive care glycemia), G.0120.03 (QIT), research communities (ICCoS, ANMMM);
AWI: Bil. Int. Collaboration Hungary/ Poland;
IWT: PhD Grants, Soft4s (softsensors),
Belgian Federal Government: DWTC (IUAP IV-02 (1996-2001) and IUAP V-22 (2002-2006)), PODO-II (CP/40: TMS and Sustainability);
EU: CAGE; ERNSI; Eureka 2063-IMPACT; Eureka 2419-FliTE;
Contract Research/agreements: Data4s, Electrabel, Elia, LMS, IPCOS, VIB.


The authors also wish to thank Jasper Scholten for an assessment of the
feasibility of some simulation algorithms; Peter Palfrader for his
comments on our conclusions, as well as assistance with the gathering of
input data for our simulations; members of The Shmoo Group for discussion
of secure programming issues; and Roger Dingledine, Ben Laurie and the
anonymous reviewers for valuable comments.


\appendix

\section{Method to compute the anonymity of Reliable} 
\label{form-reliable}

% BEGIN ADDITION EVELYNE
To formalize the behavior of the mixes, we define:
\begin{itemize}
\item
$X_{s}$ : an incoming message arriving at time $s$;
\item
$Y_{t}$ : an outgoing message leaving at time $t$;
\item
$D$ : the amount of time a message has been delayed.
\end{itemize}
We know that the mixes delay the messages exponentially and we have set the 
mean to $1$ hour: $D \sim \exp(1)$:
\begin{eqnarray*}
\mathrm{pdf:\ } f(d) &=& e^{- d} \qquad \mathrm{\ for\ all\ }d \geq 0\ ; \\[3pt]
                     &=& 0 \qquad \mathrm{elsewhere} \ ;\\[3pt]
\mathrm{cdf:\ } F(d) &=& P(D \leq d) = 1-e^{- d} \qquad \mathrm{\ for\ all\ }d \geq 0\ ; \\[3pt]
                     &=& 0 \qquad \mathrm{elsewhere} \ .
\end{eqnarray*}

All delay times are independent.\\

Crucial to note in this setup is that the sequence of outgoing messages is not a Poisson process. 
This would only be true if all inputs would arrive at the same time, hence belong
to the mix when the delaying starts or if the sequence of arrivals are a Poisson process. 
But in our case, messages arrive at distinct moments in 
time, each being exponentially delayed upon their arrival times.\\

Mixes flush at fixed time moments which are observed by the attacker: 
\[ t \in \{ \mathrm{out}_{1},\ \mathrm{out}_{2},\ \ldots,\ \mathrm{out}_{M} \}.  \] He also observes
the arrival times: \[  s \in \{ \mathrm{in}_{1},\ \mathrm{in}_{2},\ \ldots,\ \mathrm{in}_{N} \}.  \]

If a message leaves the mix at time $t$, what are then the probabilities for the arrival times? Suppose the
departure time $t=$\emph{out} is fixed. We then look for the probability that the message that left at time 
\emph{out} is the same message as the one that entered the mix at time $s$:

\begin{equation*}
P( Y_{\mathrm{out}} = X_s ) = P( D = \mathrm{out} - s )\ .
\end{equation*}

We can hence rephrase the problem in terms of the delay: which values for the delay times are the most probable? 
Clearly, negative delay is impossible so only arrival times prior to \emph{out} are probable. These arrival times
form a set $\{ \mathrm{in}_{1},\ \mathrm{in}_{2},\ \ldots,\ \mathrm{in}_{k}  \}$ with $\mathrm{in}_{k} <$ \emph{out}. The 
matching delay times are then \{ \emph{out}-$\mathrm{in}_{1}$, \emph{out}-$\mathrm{in}_{2}$,\ldots, 
\emph{out}-$\mathrm{in}_{k}$  \} to which we will refer to as $ \{ d_1, d_2, \ldots, d_k \}$. Note that $d_1 > 
d_2 > \ldots > d_k$. We are almost at
the solution as the density function of the delay times is known! Caution has to be taken however as the exponential
function is a continuous function which means that the probability of the delay taking a single value is zero:
$P( D=d_1 ) = \ldots = P( D=d_k ) = 0$!\\

\begin{center}
%\includegraphics[height=4cm]{/users/sista/dewitte/PHD/pictures_claudia/delaytimes23.eps}
\includegraphics[height=5cm]{source/delaytimes23.eps}
\caption{\small An example of an exponential probability density function } \label{evie1}
\end{center}
\begin{center}
%\includegraphics[height=4cm]{/users/sista/dewitte/PHD/pictures_claudia/expCDFsubplots.eps}
\includegraphics[height=5cm]{source/expCDFsubplots.eps}
\caption{\small The matching exponential cumulative density function } \label{evie2}   
\end{center}

How can we then calculate the probabilities of the delay times? To make this clear, let us look at Figure~\ref{evie1} and suppose 
that we only have three arrival times prior to \emph{out}. We have thus three possible delays $d_1 > d_2 > d_3$. Let us now 
assume for simplicity reasons that $d_1=3$ hours, $d_2=2$ hours and $d_3=1$ hour. 
The variable delay is continuous and can theoretically take every value in the interval $[0,3]$. However, we know that 
we only flush at three particular times and that hence only three particular delays can occur. We can exploit this knowledge 
in the following way:
\begin{eqnarray*}
P(D = d_1) &\approx& P(d_2 < D \leq d_1) = \mathrm{\ light\ surface}\ ;  \\
P(D = d_2) &\approx& P(d_3 < D \leq d_2) = \mathrm{\ medium\ surface}\ ;  \\
P(D = d_3) &\approx& P(0 < D \leq d_3) = \mathrm{\ dark\ surface}\ .  
\end{eqnarray*}  
In this way one can clearly see that the biggest surface corresponds to the most probable delay! This is straightforward for
more than three delays. For computation we make use of the cumulative distribution function (cdf) which is graphed in Figure~\ref{evie2}. 
Cumulative probabilities are listed in tables and known in statistical software. For reasons of simplicity we put the mean
of the exponential to be $1$ hour (easy parameterization):
\begin{eqnarray*}
P(D = d_1) &\approx& F(d_1)-F(d_2) = 0.9502 - 0.8647 = 0.0855\ ;  \\
P(D = d_2) &\approx& F(d_2)-F(d_1) = 0.8647 - 0.6321 = 0.2326\ ;  \\
P(D = d_3) &\approx& F(d_3) = 0.6321\ .  
\end{eqnarray*}  
In our little example, the message corresponds most likely with the one that entered the mix $1$ hour before \emph{out}.
You can also clearly see this on Figure~\ref{evie1}. In practical applications however, many possible delays will occur so that
visual inspections will not be efficient and calculations have to made and compared.
% END ADDITION EVELYNE

\subsection{Uniform Delays}

Reliable allows for mix-chosen uniform delays if the users do not
specify any delay for their messages. 

We have found a method to compute the anonymity provided by a mix that
delays inputs uniformly from a distribution $U[a,b]$. The method
consists in creating a tables with all inputs and outputs. Then we
search for all possible combinations input-output that are possible
from an external observer's point of view (i.e., those that assign to
every input that arrives at time $T$ an output that leaves between
$T+a$ and $T+b$). Let us call the total number of combinations $C$. 

Then, to compute the recipient (sender) anonymity of message
$m_i$, we need to find the distribution of probabilities that link
this input (output) to all outputs (inputs).

If input $m_i$ appears matching output $s_j$ in $P$ combinations, then the
probability assigned to $s_j$ is $P/C$.

The probability of an input of matching an
output is computed as possible cases divided by total cases. 
From this distribution, the sender and recipient anonymity can be
computed for every message. 

Unfortunately, due to the large amount of messages considered, the
implementation of this algorithm in our case is not feasible. 


%\bibliography{Anon}
\begin{thebibliography}{MCPS03}

\bibitem[BHRPD]{ncurses}
Z.~Ben-Halim, E.~Raymond, J.~Pfeifer, and T.~Dickey.
\newblock Ncurses.


\bibitem[CEHL]{OpenSSL}
M.~Cox, R.~Engelschall, S.~Henson, and B.~Laurie.
\newblock {The OpenSSL Project}.

\bibitem[Cha81]{chaum-mix}
David Chaum.
\newblock Untraceable electronic mail, return addresses, and digital
  pseudonyms.
\newblock {\em Communications of the ACM}, 4(2):84--88, February 1981.

\bibitem[Cor]{MSKBVB-Rnd}
Microsoft Corporation.
\newblock Visual basic language reference--{R}nd function.
\newblock {\em {MSDN Library}}.


\bibitem[Cot]{remailer-attacks}
Lance Cottrell.
\newblock Mixmaster and remailer attacks.


\bibitem[Cot95]{mixmaster-announce}
Lance Cottrell.
\newblock {Announcement: Mixmaster 2.0 remailer release!}
\newblock Usenet post, May 1995.


\bibitem[DDM03]{mixminion}
George Danezis, Roger Dingledine, and Nick Mathewson.
\newblock {Mixminion: Design of a Type III Anonymous Remailer Protocol}.
\newblock In {\em Proceedings of the 2003 IEEE Symposium on Security and
  Privacy}, May 2003.

\bibitem[DG96]{rfc-1950}
P.~Deutsch and J-L. Gailly.
\newblock {ZLIB Compressed Data Format Specification version 3.3}.
\newblock Request for Comments: 1950, May 1996.

\bibitem[DP04]{diaz_ih04}
Claudia Diaz and Bart Preneel.
\newblock Reasoning about the anonymity provided by pool mixes that generate
  dummy traffic.
\newblock In {\em proceedings of the 6th Information Hiding Workshop
  (IH2004)}, LNCS, Toronto (Canada). May 2004.

\bibitem[DS03a]{rgb-mix}
George Danezis and Len Sassaman.
\newblock Heartbeat traffic to counter (n-1) attacks.
\newblock In {\em {Proceedings of the Workshop on Privacy in the Electronic
  Society (WPES 2003)}}, Washington, DC, USA, October 2003.

\bibitem[SDS]{sds}
Andrei Serjantov, Roger Dingledine and Paul Syverson.
\newblock From a trickle to a flood: Active attacks in several mix types.
\newblock In {\em Proceedings of Information Hiding Workshop (IH
  2002)}, LNCS 2578. October 2002.

\bibitem[DS03b]{DS03}
Claudia Diaz and Andrei Serjantov.
\newblock Generalising mixes.
\newblock In {\em Privacy Enhancing Technologies}, LNCS 2760, Dresden, Germany, April
  2003.

\bibitem[DSCP02]{Diaz02}
Claudia Diaz, Stefaan Seys, Joris Claessens, and Bart Preneel.
\newblock Towards measuring anonymity.
\newblock In Roger Dingledine and Paul Syverson, editors, {\em Proceedings of
  Privacy Enhancing Technologies Workshop (PET 2002)}. Springer-Verlag, LNCS
  2482, April 2002.

\bibitem[GW96]{daw-ian-netscape}
Ian Goldberg and David Wagner.
\newblock Randomness and the {N}etscape browser.
\newblock {\em Dr. Dobb's Journal}, January 1996.

\bibitem[Haz]{pcre}
Philip Hazel.
\newblock Perl compatible regular expressions.

\bibitem[KEB98]{stop-and-go}
Dogan Kesdogan, Jan Egner, and Roland B\"uschkes.
\newblock Stop-and-go {MIX}es: Providing probabilistic anonymity in an open
  system.
\newblock In {\em Proceedings of Information Hiding Workshop (IH 1998)}.
  Springer-Verlag, LNCS 1525, 1998.

\bibitem[M\"ol02]{personal-corresp-ulf}
Ulf M\"oller.
\newblock Personal communication.
\newblock Private email to Len Sassaman, August 2002.

\bibitem[MCPS03]{mixmaster-spec}
Ulf M\"oller, Lance Cottrell, Peter Palfrader, and Len Sassaman.
\newblock Mixmaster {P}rotocol --- {V}ersion 2.
\newblock {\tt{http://www.abditum.com/mixmaster-spec.txt}}, July 2004.

\bibitem[PK00]{Pfitzmann00}
Andreas Pfitzmann and Marit Kohntopp.
\newblock Anonymity, unobservability and pseudonymity --- a proposal for
  terminology.
\newblock In {\em Designing Privacy Enhancing Technologies: Proceedings of the
  International Workshop on the Design Issues in Anonymity and Observability},
  pages 1--9, July 2000.

\bibitem[RPr99]{RProcess}
RProcess.
\newblock Selective denial of service attacks.
\newblock Usenet post, September 1999.

\bibitem[Sas02]{sassaman-lisa}
Len Sassaman.
\newblock The promise of privacy.
\newblock Invited talk, LISA XVI, November 2002.

\bibitem[SD02]{Serj02}
Andrei Serjantov and George Danezis.
\newblock Towards an information theoretic metric for anonymity.
\newblock In Roger Dingledine and Paul Syverson, editors, {\em Proceedings of
  Privacy Enhancing Technologies Workshop (PET 2002)}. Springer-Verlag, LNCS
  2482, April 2002.

\bibitem[Tha03]{slimjim}
Rodney Thayer.
\newblock Slim{J}im: shared library shimming for password harvesting.
\newblock Presentation, {T}oor{C}on 2003, September 2003.

\bibitem[Tho84]{trusting-trust}
K.~Thompson.
\newblock Reflections on trusting trust.
\newblock {\em Communications of the ACM}, 27(8), August 1984.

\end{thebibliography}

\end{document}
