\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}