[freehaven-cvs] Merging in Claudia"s changes.

[rabbi@seul.org]

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

Modified Files:
	mixvreliable.tex 
Log Message:
Merging in Claudia's changes.


Index: mixvreliable.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable/mixvreliable.tex,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- mixvreliable.tex	15 Mar 2004 21:34:24 -0000	1.4
+++ mixvreliable.tex	22 Mar 2004 23:16:52 -0000	1.5
@@ -44,7 +44,7 @@
 The objective of this work was 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 sevice, and to compare the two different designs. We evaluate
+the remailer service, and to compare the two different designs. We evaluate
 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
@@ -84,35 +84,115 @@
 
 The first design is called ``Mixmaster'' (as the remailer network) because
 it corresponds to the original design by Cottrell \cite{Cott94,Mix_prot}.
-The second desing, called ``Reliable'', uses a different reordering
+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 verrsion foo of Reliable.
+software and version 1.0.5 of Reliable.
 
 \subsection{Mixmaster}
 
-\footnote{Mixmaster version 3.0, as well as Reliable, also optionally
-support 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{cottrell,mixminion}.}
+Mixmaster\footnote{Mixmaster version 3.0, as well as Reliable, also
+  optionally support 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{cottrell,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 which 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 algorithm that determines the number $s$ of messages that are 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 generalised mix model proposed by
+D\'iaz 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 probability of a message
+of being 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}
+\epsfig{file=mixmaster.eps, width=10cm}
+\caption{Mixmaster in the GMM}
+\label{fig-mm}
+\end{center}
+\end{figure}
+
 
 \subsection{Reliable}
 
+Reliable is based on the Stop-and-Go (\emph{SG Mix}) mix proposed by
+Kesdogan \emph{et al.} in \cite{stop-and-go}. In SG 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: 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
 Mixmaster message format for packet transfer. Reliable uses a variant of
-the \emph{S-G Mix} design proposed by Kesdogan. 
+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
+does not provide any delay to the mix, then the mix itself picks a
+delay from a uniform distribution, being the maximum and minimum of
+the uniform one and four hours, respectively. Note that these
+parameters of the delay distributions are configurable, and therefore
+many remailer operators may set them lower in order to provide a
+faster service. 
 
-% Explain details of Reliable's s-g.
+% Danezis proves in \cite{} that the exponential delay is optimal for
+% continuous mixes. 
 
-\section{Dummy traffic}
+\subsection{Dummy traffic}
 \label{dummy}
 
-\subsection{Dummy policy of Mixmaster}
+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.
+
+Dummies are indistinguishable from real messages as they travel in the
+mix network. As 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. In order to make the fair 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}
+Every time a message is received by Mixmaster, an algorithm runs to
+generate $d_1$ dummies that are 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$. Moreover, every time
+Mixmaster flushes messages, it generated 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 in generation $25$ dummies
+every 6 hours. The time these dummies are kept in the mix is generated
+from a uniform distribution whose minimum value is $0$ and maximum is
+$6$ hours.
 
-\subsection{Dummy policy of Reliable}
 
 
 \section{Anonymity metrics}
@@ -159,29 +239,127 @@
 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.
+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
+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. We
-compute the metric from the point of view of an attacker, whose powers
-must be clearly specified.
+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. 
 
 
 \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}. 
 
-% Describe exactly what it was that we logged on randseed here, and for
-% how long?
+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). 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 unfeasibility 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}. Moreover, the choice of a uniform delay for
+the messages is completely non-standard.
+
+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.  
+
+\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 to a mix
+node follow a Poisson process. We have analyzed the input traffic, and
+found that it does not follow a Poisson distribution, nor any other
+known distribution. 
+
+In Figure~\ref{arr-round} we show the number of messages arrived to
+the mix in every period of $15$ minutes. Figure~\ref{arr-day} shows
+the evolution of the arrivals per day. We can observe that the traffic
+arrived to 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 is highly impredictable.
+
+Evelyne -> some smarter comments on the inputs :-)
+
+Figs inputs (4 or 6, depending on space)
+
+%\begin{figure}
+%    \noindent
+%    \centerline{ \epsfig{file=NumArrivalsPerHour.eps, width=6cm}
+%                 \epsfig{file=NumArrivalsPerDay.eps, width=6cm} }
+%      \hspace*{3.2cm}(a) \hspace*{5.5cm}(b)
+%    \caption{Incoming Traffic Pattern}
+%    \label{arr-day}
+% \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 all inputs of a round is the
+same. Equivanlently, all outputs of a round have the same sender
+anonymity value. In this section we show the results obtained in our
+simulation. 
+
+Figure~\ref{3d-rec} displays a point per message, located in the space
+defined by the delay (amount of time the message spends on the mix),
+arrivals (number of inputs received by the mix together with the
+message) and recipient anonymity of the message.
+
+... FINISH Claudia
+
+%shows the recipient anonymity provided by the mix as a  
+
+
+\subsection{Analysis of Reliable}
+
+Claudia
+
+\subsection{Mixmaster vs. Reliable}
+
+Claudia
 
-\section{Results of the simulations}
 
 \section{Other factors which influence anonymity}
 
 We have evaluated the anonymity strength provided by the mixing algorithms
-and dummy policies chosen for both Mixmaster and Reliable. Additional
+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
@@ -331,7 +509,14 @@
 function uses the system time as its primary entropy seed, and previous
 work has demonstrated that systems which use a known seed to a
 deterministic PRNG are trivially
-attackable~\cite{daw-ian-netscape,MS-knowledgebase}.
+attackable~\cite{daw-ian-netscape,MS-knowledgebase}. While its use of
+Rand() to determine the latency for a message injected into the mix is the
+most devistating, Reliable uses Rand() for many other critical purposes as
+well~\cite{ishtar}.
+
+% ishtar cite: http://groups.google.com/groups?selm=6881f2424f3814e408691e984f11d984%40cypherpunks.to&output=gplain
+
+
 
 \subsection{Network timing attacks}
 
@@ -348,6 +533,7 @@
 
 \subsection*{Acknowledgments}
 
+% Evelyne? 
 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
@@ -360,8 +546,19 @@
 Shmoo Group for discussion of secure programming issues.
 
 
+\appendix
 
-\bibliography{Bib}
+\section{Method to compute the anonymity of Reliable} 
+\label{form-reliable}
+
+
+Evelyne
+
++ Claudia on uniform
+%METRICS RELIABLE, UNIFORM DELAY NOT POSSIBLE TO COMPUTE ANON
+
+
+\bibliography{Anon}
 
 
 \end{document}

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