[freehaven-cvs] Added abstract, made grammar fixes. Getting ready to...

[rabbi@seul.org]

Update of /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable
In directory moria.mit.edu:/tmp/cvs-serv21433

Modified Files:
	mixvreliable.tex 
Log Message:
Added abstract, made grammar fixes. Getting ready to submit!


Index: mixvreliable.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable/mixvreliable.tex,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- mixvreliable.tex	26 Mar 2004 06:07:51 -0000	1.8
+++ mixvreliable.tex	26 Mar 2004 09:55:21 -0000	1.9
@@ -22,7 +22,27 @@
 
 \begin{abstract}
 
-Len
+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. In order to draw accurate conclusions about the
+operation of these mixes, we use as our input to these simulations 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, and our analysis of the
+input traffic shows that it follows no known 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 code in Reliable that further compromise its ability
+to provide anonymity, and review key areas which 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 utilized 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}
 
 
@@ -42,11 +62,11 @@
 They also allow the sender of a message to stay anonymous to the
 recipient.
 
-The objective of this work was to have quantitative results on the
+The objective of this work is to have quantitative results on the
 anonymity actually provided by two mix software implementations in wide
 deployment, in order 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; in order to assess the anonymity
+anonymity in a single-node context. In order 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
@@ -54,7 +74,7 @@
 remailer, and simulated the behaviour of the mix.
 
 
-(Len) Summary of what we have done
+% (Len) Summary of what we have done
 
 % (Len) Roadmap of the paper
 
@@ -62,9 +82,9 @@
 \label{mixes}
 
 Mixes are the essential building block to provide anonymous email
-services. A mix is a router that hides the correspondence between incoming
+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
-messages. In order to change the appearance of the messages, the mix uses
+messages. In order to change the appearance of the messages the mix uses
 some techniques, such as padding and encryption, thus providing bitwise
 unlinkability between inputs and outputs. Techniques like reordering and
 delaying messages, and generating dummy traffic are used to modify the
@@ -73,20 +93,21 @@
 input and an output messages by looking at the time the message arrived to
 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, which have been implemented and are
-part of the Mixmaster remailer network\cite{mixmaster-announce}, that has been
+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 corresponds to the original design 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.
+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}
 
@@ -100,7 +121,7 @@
   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
+mix), and select some of them for flushing in random order when the
 flushing condition is fulfilled.
 Mixmaster is a timed mix which has a \emph{timeout} of 15
 minutes. During this period of time, it collects messages that are
@@ -139,10 +160,10 @@
 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: every time a message has been kept for the delay time,
+continuously: every time a message has been kept for the delay time
 it is sent by the mix.   
 
-Reliable inter-operates with Mixmaster on the protocol level by using the
+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. In Reliable, the delay may be chosen by the
 user from an exponential distribution of mean one hour. If the user
@@ -162,8 +183,8 @@
 A dummy message is a \emph{fake} message introduced in the mix network
 in order to make it more difficult for an attacker to deploy attacks
 that can compromise the anonymity of a message. The dummy message is
-normally produced by the mixes, and they have as destination another
-mix, instead of a real recipient.
+normally produced by the mixes, and they select as destination another
+mix instead of a real recipient.
 
 Dummies are indistinguishable from real messages as they travel in the
 mix network. As they are introduced to prevent traffic analysis, the
@@ -197,9 +218,9 @@
 \section{Anonymity metrics}
 \label{metrics}
 
-In this section we introduce the anonymity metrics for mixes. We
-remark the particularities of some mix designs (binomial mixes and
-threshold mixes). Also, we present the attack model considered.
+In this section we introduce the anonymity metrics for mixes. We remark on
+the particularities of some mix designs (binomial mixes and threshold
+mixes). Also, we present the attack model which we have considered.
 
 \emph{Anonymity} was defined by Pfitzmann and K\"ohntopp
 \cite{Pfitzmann00} as \emph{``the state of being not identifiable within a
@@ -230,22 +251,22 @@
 possible outputs. 
 \\
 
-Note that in the two cases, the metric computes the anonymity of a
-\emph{particular} input or output message; it does not give a general
+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 simulate) the
-anonymity obtained for a large number of messages and provide comparative
-statistics, as we do in this paper.
+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.
 
 In order to measure the Mixmaster's sender and recipient anonymity, we
 have applied the formulas provided by D\'iaz 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' incoming
+we did not make any assumption on the distribution of the mix's incoming
 traffic (Kesdogan assumes incoming Poisson traffic).  
 
 
@@ -261,15 +282,13 @@
 outgoing message. 
 
 
-\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 every time a message arrived to a working Mixmaster node
-(note that the information logged does not threaten the anonymity of
-the users of the mix). We have used four months of incoming traffic
-(July-November 2003) in order to obtain the results presented in
-Section~\ref{results}. 
+\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 every 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) in order 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
@@ -536,16 +555,16 @@
 
 \section{Other factors which influence anonymity}
 
-We have evaluated the anonymity strength provided by the mixing algorithms
-chosen for both 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}.
+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

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/