[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Committing Claudia"s final changes.
Update of /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable
In directory moria.mit.edu:/tmp/cvs-serv1686
Modified Files:
mixvreliable.tex
Log Message:
Committing Claudia's final changes.
Index: mixvreliable.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable/mixvreliable.tex,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- mixvreliable.tex 29 Jun 2004 01:15:01 -0000 1.18
+++ mixvreliable.tex 30 Jun 2004 18:58:51 -0000 1.19
@@ -30,7 +30,7 @@
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
+input traffic shows that it 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
@@ -145,7 +145,10 @@
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]{/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}
@@ -160,7 +163,21 @@
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.
+it is sent out by the mix.
+
+The theoretical S-G mix design assumes that the delay parameter adapts
+to the traffic load, that is, the mix should set the delay parameter
+according to the amount of input traffic it is receiving. This feature
+is not implemented in Reliable, that has a static delay
+parameter. Another feature of S-G mixes is that they implement
+timestamps in order to prevent active attacks ($n-1$ attacks in
+particular). Reliable does not implement this feature given that it
+interoperates in a network with pool mixes, whose delays are
+unpredictable (these timestamps can only be generated if the whole
+chain of mixes is S-G and the user is choosing the delay for each
+hop in the path). Reliable, thus, does not provide any resistance to
+this kind of active attacks.
+
Reliable interoperates with Mixmaster on the protocol level by using the
Mixmaster message format for packet transfer. Reliable uses a variant of
@@ -173,8 +190,6 @@
many remailer operators may set them lower in order to provide a
faster service.
-% Danezis proves in \cite{} that the exponential delay is optimal for
-% continuous mixes.
\subsection{Dummy traffic}
\label{dummy}
@@ -200,7 +215,7 @@
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
+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$.
@@ -217,13 +232,11 @@
\section{Anonymity metrics}
\label{metrics}
-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
- set of subjects, the anonymity set''}.
+In this section we introduce the anonymity metrics for mixes and we
+present the attack model which 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
@@ -280,6 +293,11 @@
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,
@@ -292,7 +310,12 @@
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
+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 abstact 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 unfeasibility of implementing algorithms that compute the
@@ -307,7 +330,10 @@
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.
+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 $11.846$.
\section{Results}
\label{results}
@@ -333,7 +359,7 @@
is \emph{time-independent}.
In our statistical analysis we first \emph{assumed} that the process of arrivals
-\emph{is} a Poisson process and we estimated the parameter $\lambda$. The latter
+\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
@@ -348,8 +374,8 @@
level of $0.01$, the null hypothesis gets rejected (Chi-value=$826 208$)!
% END (Evelyne)
-In the right part of figure~\ref{arr-day} we show the number of messages arrived to
-the mix per hour. The left part (below) of figure~\ref{arr-day} shows
+In the left part of figure~\ref{arr-day} we show the number of messages arrived to
+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
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
@@ -362,20 +388,39 @@
\begin{figure}
\noindent
-\includegraphics[width=6cm, height=4cm]{/users/sista/dewitte/PHD/papers/source/hist-arr-hour.eps}
-\includegraphics[width=6cm, height=4cm]{/users/sista/dewitte/PHD/papers/source/hist-arr-day.eps}
+%\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 patters}
+\caption{Incoming traffic patterns}
\label{arr-day}
- \end{figure}
-\begin{figure}
\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}
+%\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}
- \end{figure}
+
+%\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}
@@ -386,20 +431,9 @@
anonymity value. In this section we show the results obtained in our
simulation.
-In figure~\ref{3d-sen} we draw a point per round\footnote{In pool mixes all
-messages of the same incoming round have the same recipient anonymity,
-and all the messages of the same outgoing round have the same sender
-anonymity}, 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. Figure~\ref{3d-sen} shows the same for sender anonymity.
-
-\begin{figure}
-\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}
-\caption{Recipient (left) and sender (right) anonymity for Mixmaster}
-\label{3d-sen}
-\end{figure}
+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
@@ -416,7 +450,7 @@
(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 delay of the messages doesn't take hight
+We also observe that the delays of the messages don't take hight
values, unless the traffic load getting to the mix is very low.
In order to study the behaviour of the mix under different traffic loads,
@@ -437,7 +471,8 @@
messages (data $> 41$).
\end{description}
-In figure~\ref{del-mm} we show the minutes of delay of every message.
+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
@@ -445,12 +480,14 @@
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 to the messages takes higher values.
+provided to the messages 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[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}
@@ -458,7 +495,8 @@
\begin{figure}
\begin{center}
-\includegraphics[width=10cm, height=4 cm]{/users/sista/dewitte/PHD/papers/source/mm-sanon.eps}
+%\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}
@@ -488,23 +526,28 @@
maximum values of Reliable's anonymity for this input are lower
than Mixmaster's maximums.
Figure~\ref{sen-rec} shows the correlation of sender and recipient
-anonymity. These values are highly correlated (as in the case of
-Mixmaster: $0.9789$). We can clearly see that some of the messages get nearly
-no anonymity.
+anonymity for Reliable and Mixmaster. These values are highly
+correlated. 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[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}
-\end{figure}
-\begin{center}
+
+\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}
-\caption{Correlation Sender-Recipient Anonymity for Reliable}
+%\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 Serder-Recipient anonymity for Reliable and Mixmaster}
\label{sen-rec}
-\end{center}
+\end{figure}
\subsection{Mixmaster vs. Reliable}
@@ -806,12 +849,15 @@
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 mixes are not suitable for use with systems
-that may have occurrences of low traffic on the network. While S-G mixes
-are an appropriate solution to low-latency applications such as web
-mixing, pool mixes should be used for higher latency systems with
-fluctuating traffic loads.
+mix implementations that Reliable mixes are not suitable for use with systems
+that may have occurrences of low traffic on the network. While
+Reliable mixes may be an appropriate solution for systems with a
+steady input rate, they are not suited for systems with variable input
+traffic. Misxmaster should be used for systems with fluctuating
+traffic loads.
+.
%%% end input Len
\subsection*{Acknowledgments}
@@ -896,11 +942,13 @@
$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=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=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}
@@ -911,9 +959,9 @@
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{\ yellow\ surface}\ ; \\
-P(D = d_2) &\approx& P(d_3 < D \leq d_2) = \mathrm{\ green\ surface}\ ; \\
-P(D = d_3) &\approx& P(0 < D \leq d_3) = \mathrm{\ blue\ surface}\ .
+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}.
@@ -946,12 +994,12 @@
$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$ cases, then the
+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
+From this distribution, the sender and recipient anonymity can be
computed for every message.
Unfortunately, due to the large amount of messages considered, the
@@ -1008,7 +1056,8 @@
Claudia Diaz and Bart Preneel.
\newblock Reasoning about the anonymity provided by pool mixes that generate
dummy traffic.
-\newblock In {\em Accepted submission at IH2004}, 2004.
+\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.
@@ -1016,10 +1065,16 @@
\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 n the 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 Enhacing Technologies}, LNCS, Dresden, Germany, April
+\newblock In {\em Privacy Enhacing Technologies}, LNCS 2760, Dresden, Germany, April
2003.
\bibitem[DSCP02]{Diaz02}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/