[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] clean up everything, mark unfinished subsections
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching
Modified Files:
badnodes.eps badnodes.pdf model-app.tex model.tex
sync-batching.bib sync-batching.pdf sync-batching.tex
Log Message:
clean up everything, mark unfinished subsections
Index: badnodes.eps
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/badnodes.eps,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- badnodes.eps 24 Jan 2004 08:32:42 -0000 1.3
+++ badnodes.eps 26 Jan 2004 03:55:52 -0000 1.4
@@ -1,7 +1,7 @@
%!PS-Adobe-3.0
%%Title: entropy.xls
%%Creator: PScript5.dll Version 5.2
-%%CreationDate: 1/23/2004 23:21:38
+%%CreationDate: 1/24/2004 1:14:17
%%For: shmat
%%BoundingBox: (atend)
%%Pages: (atend)
@@ -602,8 +602,8 @@
4294 3708 M (100%)[61 62 62 61 61 61 0 0]zS
; /F0S9C F0 [156 0 0 -156 0 0 ] mFS
F0S9C Ji
-1092 4218 M (Probability that a random node is hostile)[104 61 95 95 87 95 43 43 43 52 86 43 52 95 87 52 43 87 43 61 87 95 95 95 139 43 95 95 95 87 43 43
-87 43 95 95 87 52 43 43 0]xS
+1087 4218 M (probability of compromise for each node)[95 61 95 95 87 95 43 43 43 52 86 43 95 52 43 87 95 139 95 61 95 139 43 87 87 43 52 95 61 43 87 87
+87 95 43 95 95 95 0]xS
/F0S00IFFFFFF64 F0 [0 -156 -156 0 0 0 ] mFS
F0S00IFFFFFF64 Ji
626 2799 M (entropy)[-87 -95 -52 -61 -95 -95 0]yS
Index: badnodes.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/badnodes.pdf,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
Binary files /tmp/cvscUadlS and /tmp/cvsesp8CA differ
Index: model-app.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model-app.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- model-app.tex 24 Jan 2004 04:52:08 -0000 1.3
+++ model-app.tex 26 Jan 2004 03:55:52 -0000 1.4
@@ -4,7 +4,7 @@
\subsection{Cascade.}
-Consider a 2x2 cascade network as in fig.~\ref{fig:casc-2x2}. Assume
+Consider a 2x2 cascade network as in Figure~\ref{fig:casc-2x2}. Assume
there are 128 messages in a batch, and that any node has $\frac{1}{4}$
chance of having been compromised. Let $m$ be the targeted message,
and suppose the adversary observed that the sender of $m$ chose $A$
Index: model.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- model.tex 24 Jan 2004 04:52:08 -0000 1.4
+++ model.tex 26 Jan 2004 03:55:52 -0000 1.5
@@ -88,8 +88,8 @@
holds if $\varphi$ eventually becomes true.)
We use a probabilistic model checker called PRISM~\cite{Pri} to compute
-these probabilities automatically. To simplify exposition, we omit
-the details of the underlying model checking algorithms. A detailed
+these probabilities automatically. We omit
+the details of the underlying model checking algorithms; a detailed
explanation of how probabilistic model checking is used to analyze
randomized routing protocols can be found in~\cite{S04}.
@@ -104,17 +104,24 @@
mix can be interpreted as permutation in a virtual buffer of size $K$.
In particular, the targeted message $m$ appears in any of the $K$
output positions with equal probability after passing through the mix.
-Therefore, each mix can be modeled by the following simple Markov chain
+Therefore, each mix can be modeled by a simple Markov chain
(recall that state $s$ represents the current position of message $m$,
-and let $t$ be the sequential number of the current hop):
+and let $t$ be the sequential number of the current hop). The compromised
+mix performs no mixing at all, and thus does not change
+the position of any message it processes.
+\begin{figure}
+\begin{minipage}[ht]{5.75cm}
+\caption{Model of a good mix}
\includegraphics[scale=0.3]{goodmix}
-
-If the mix has been compromised, we assume that it performs no mixing
-at all, and thus does not change the position of any message it processes:
-
+\end{minipage}
+\hfill
+\begin{minipage}[ht]{5.75cm}
+\caption{Model of a bad mix}
\includegraphics[scale=0.3]{badmix}
-
+\end{minipage}
+\hfill
+\end{figure}
\subsection{Network model}
Index: sync-batching.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.bib,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- sync-batching.bib 24 Jan 2004 04:52:08 -0000 1.6
+++ sync-batching.bib 26 Jan 2004 03:55:52 -0000 1.7
@@ -14,7 +14,7 @@
Pool-Mode Attacks}},
year = 1998,
booktitle = {3rd Australasian Conference on Information Security and
- Privacy (ACISP'98},
+ Privacy (ACISP'98)},
editor = {C. Boyd and E. Dawson},
number = 1438,
series = {LNCS},
@@ -58,10 +58,8 @@
volume = {4},
number = {2},
month = {February},
- note = {\url{http://www.eskimo.com/~weidai/mix-net.txt}},
}
-
-
+ note = {\url{http://www.eskimo.com/~weidai/mix-net.txt}},
@InProceedings{chaum-blind,
author = {David Chaum},
@@ -104,8 +102,8 @@
year = 2001,
editor = {Ira S. Moskowitz},
publisher = {Springer-Verlag, LNCS 2137},
- note = {\url{http://www.freehaven.net/papers.html}}
}
+ note = {\url{http://www.freehaven.net/papers.html}}
@inproceedings{trickle02,
@@ -140,7 +138,6 @@
editor = {Roger Dingledine and Paul Syverson},
publisher = {Springer-Verlag, LNCS 2482},
month = {April},
- note = {\url{http://www.freehaven.net/papers.html}}
}
@@ -396,8 +393,8 @@
booktitle = {Principles of Distributed Computing - {PODC} '99},
year = {1999},
publisher = {ACM Press},
- note = {\newline \url{http://citeseer.nj.nec.com/jakobsson99flash.html}},
}
+ note = {\newline \url{http://citeseer.nj.nec.com/jakobsson99flash.html}},
@inproceedings{randomized-checking,
title = {Making mix nets robust for electronic voting by randomized partial checking},
Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
Binary files /tmp/cvsYMxEwW and /tmp/cvsgHGQzL differ
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.39
retrieving revision 1.40
diff -u -d -r1.39 -r1.40
--- sync-batching.tex 24 Jan 2004 23:18:48 -0000 1.39
+++ sync-batching.tex 26 Jan 2004 03:55:52 -0000 1.40
@@ -21,18 +21,26 @@
% \setlength{\topsep}{0mm}
}}{\end{list}}
+% Cut down on whitespace above and below figures displayed at head/foot of
+% page.
+\setlength{\textfloatsep}{3mm}
+% Cut down on whitespace above and below figures displayed in middle of page
+\setlength{\intextsep}{3mm}
+
\begin{document}
%\title{The Disadvantages of Cascade Mix Networks and How to Overcome Them}
-%\title{Synchronous Batching:\\From Cascade Networks to Free Routes
+\title{Synchronous Batching:\\From Cascade Networks to Free Routes
%\title{Mixing in Step:\\Synchronous Batching from Cascade Networks to
% Free Routes
%\title{Groove Mixing:\\Synchronous Batching from Cascade Networks to Free Routes
%\title{Synchronous Batching:\\Beat Mixing from Cascade Networks to Free Routes
%\title{Heartbeat Mixing: Synchronous Batching from Cascade Networks to Free Routes
-\title{Synchronous Mixnets: From Cascades to Free Routes
+%\title{Synchronous Mixnets: From Cascades to Free Routes
\thanks{Portions of this paper were inspired by discussions with David
-Hopwood. We would consider him an author, but have been unable to contact
-him since beginning the paper. We'll keep trying.}}
+Hopwood. We invite him to be an author, but we have not been able
+to contact him. We'll keep trying.}}
+%but we have been unable to contact
+%him since beginning the paper. We'll keep trying.}}
\author{Roger Dingledine\inst{1} and Vitaly Shmatikov\inst{2} and Paul Syverson\inst{3}}
\institute{The Free Haven Project \email{(arma@freehaven.net)} \and
@@ -43,8 +51,15 @@
%======================================================================
\begin{abstract}
-Synchronous mixnets are vastly superior to asynchorous mixnets in
-many ways.
+%Tradeoffs between
+%Choosing between
+%Comparing
+%various
+The variety of possible anonymity network topologies has spurred much
+debate in recent years.
+%Topology in anonymity systems has been hotly disputed in recent years.
+%Synchronous mixnets are vastly superior to asynchronous mixnets in
+%many ways.
In a synchronous batching design, each batch of messages enters the
mix network together, and the messages proceed in lock step through
the network. We show that a synchronous batching strategy can be used
@@ -111,8 +126,8 @@
we present our results and assess the assumptions behind them in
Section~\ref{sec:graphs}. We go on in
Section~\ref{sec:metrics} to consider other metrics such as bandwidth
-requirements and robustness, and wrap up in Section~\ref{sec:conclusion}
-with future work and possible extensions.
+requirements and robustness. %, and wrap up in Section~\ref{sec:conclusion}
+%with future work and possible extensions.
\section{Synchronous batching}
\label{sec:sync-batching}
@@ -190,7 +205,7 @@
That paper also describes a receipt and witness system by which senders
and mixes can prove that a given mix failed to pass on or accept a given
message. These receipts allow a reputation system: senders can recognize
-which nodes tend to drop messages.
+which nodes tend to drop messages, and avoid them in the future.
\subsection{The Disadvantages of Free Mix Routes}
\label{subsec:disad}
@@ -236,7 +251,7 @@
not whether it uses free routes. In a synchronous batching design,
all messages in a batch exit the network together after the last
hop, so messages cannot be partitioned based on when they exit
-the network.%\footnote{Free-route protocols where each sender
+the network. %\footnote{Free-route protocols where each sender
%fixes his path are in fact vulnerable to attacks (e.g. tagging
%attacks~\cite{disad-free-routes,raymond00}) that free-route protocols
%with randomly chosen paths can resist~\cite{minion-design}, but so
@@ -251,7 +266,7 @@
the cascade provides complete protection, a user choosing four
nodes in the free-route network has a non-trivial chance of picking an
entirely compromised path. But this is a false comparison. A better
-comparison would consider a cascade network with 20 nodes---thus
+comparison would consider a network of five $\ell=4$ cascades---thus
the cascade network also has a chance of fully-compromised paths.
In Section~\ref{sec:graphs} we show that while each cascade in a cascade
network of width $w$ only mixes $1/w$ of the messages from the batch,
@@ -340,8 +355,6 @@
its input-output relationships, while the mix network as a whole still
protects linkability with high probability.
-%adversaries: weak adversary beats cascades but not free-routes.
-
Clearly much work has been done to address blending attacks; the
solutions apply to synchronous free-route networks
as well as cascade networks.
@@ -349,6 +362,8 @@
\section{Threat model and mixnet topologies}
\label{sec:scenarios}
+[This section still draft -RD]
+
We consider a slight variant on the traditional powerful
adversary~\cite{disad-free-routes}. Senders of messages that are
input to the mixnet and receivers of messages output from the mixnet
@@ -438,7 +453,16 @@
\label{fig:badnodes}
\end{figure}
-Discuss the graphs.
+Figure~\ref{fig:badnodes} shows the entropy that Alice can expect when
+using each of the three topology choices we investigated. Because
+the cascade network immediately divides the incoming batch by the
+number of cascades, it provides substantially less protection even
+when many nodes in the network are compromised. The stratified and
+free-route topologies have similar expected entropy. In this section
+and Section~\ref{sec:metrics} we will examine other metrics for deciding
+which is best. Further graphs in Appendix~\ref{sec:entropy-per-hop}
+indicate how much entropy is achieved after a given number of steps
+through each network.
\subsection{Is the adversary really randomly distributed?}
\label{subsec:random-adversary}
@@ -481,17 +505,21 @@
chance of selecting a bad node next is $\frac{B-1}{G+B}$ if
the current node is bad and $\frac{B}{G+B}$ otherwise.
The difference is only $\frac{1}{G+B}$: it does not depend on what
-fraction of the nodes are bad. For a 16x4 free-route mixnet with
-4 bad nodes, the difference amounts to a 2\% chance of an all bad
-path if the same node cannot be picked twice in a row and a 3.9\% chance
-if it can. With 8 bad nodes, this becomes 5.1\% and 6.3\% respectively.
-As the percent of bad nodes grows, the shift in probability becomes
-more negligible. This is also true as the network size grows.
-For example, for a 32x4 mixnet with half bad nodes, the difference
-is 5.7\% vs.\ 6.3\% . At what point this difference can safely
-be ignored is a question that can only be answered in context.
-We will assume it to be of no practical significance for the
-remainder of the paper.
+fraction of the nodes are bad. As the network size grows,
+the shift in probability distribution becomes negligible.
+
+%%This is good analysis, but we don't have space for it. :( -RD
+% For a 16x4 free-route mixnet with
+%4 bad nodes, the difference amounts to a 2\% chance of an all bad
+%path if the same node cannot be picked twice in a row and a 3.9\% chance
+%if it can. With 8 bad nodes, this becomes 5.1\% and 6.3\% respectively.
+%As the percent of bad nodes grows, the shift in probability becomes
+%more negligible. This is also true as the network size grows.
+%For example, for a 32x4 mixnet with half bad nodes, the difference
+%is 5.7\% vs.\ 6.3\% . At what point this difference can safely
+%be ignored is a question that can only be answered in context.
+%We will assume it to be of no practical significance for the
+%remainder of the paper.
% Mention that we have that entropy different for each of \ell hops.
% But it's just \ell times the above negligible difference, right? -RD
@@ -601,6 +629,8 @@
\subsection{Capacity, throughput, delay, reliability}
+[This section still draft -RD]
+
One parameter we cannot control is the rate that messages arrive to the
mixnet. Similarly, we cannot control the latency that users will be
willing to accept. To make the analysis more concrete, assume we choose
@@ -654,25 +684,25 @@
coordinate messages from multiple batches to flood a given node at the
same time (as would be possible in the uniform systolic case).
-[Drop everything from here to end of the subsection? -PS]
+%[Drop everything from here to end of the subsection? -PS]
-Note that synchronous batching does not necessarily mean a "one
-latency fits all" approach. People who want a larger anonymity set can
-agree to send their messages only at intervals of $k \cdot
-t_\mathrm{batch}$, so those batches will have more messages (but at
-the expense of the other batches). This implies a fair degree of coordination
-and the flip side is a freedom to flood the network to some extent.
-It may also attract attackers to such cabals so that the net anonymity
-does not increase.
+%Note that synchronous batching does not necessarily mean a "one
+%latency fits all" approach. People who want a larger anonymity set can
+%agree to send their messages only at intervals of $k \cdot
+%t_\mathrm{batch}$, so those batches will have more messages (but at
+%the expense of the other batches). This implies a fair degree of coordination
+%and the flip side is a freedom to flood the network to some extent.
+%It may also attract attackers to such cabals so that the net anonymity
+%does not increase.
-[like S-G mixes, the sender chooses to delay at certain nodes, which
-improves anonymity. no reason why we couldn't too, really.]
+%[like S-G mixes, the sender chooses to delay at certain nodes, which
+%improves anonymity. no reason why we couldn't too, really.]
-Possible extension: for the purpose of discussion, let's use
-$t_\mathrm{batch}$ = 3 hours and $t_\mathrm{hop}$ = 1 hour / n. Then
-the latency is between
-1 and 4 hours, and the anonymity set is the set of messages sent in a
-3 hour period.
+%Possible extension: for the purpose of discussion, let's use
+%$t_\mathrm{batch}$ = 3 hours and $t_\mathrm{hop}$ = 1 hour / n. Then
+%the latency is between
+%1 and 4 hours, and the anonymity set is the set of messages sent in a
+%3 hour period.
We can improve this by having a "delay until next batch" option in
the message subheader; that would delay the message by $t_\mathrm{batch}$ and
@@ -683,13 +713,12 @@
receives delayed messages, in which case the anonymity set for those
users is still 3 hours).
-Can anyone attack the "delay until next batch" option? I don't think
-the fact that those messages can be distinguished by the node is any
-more harmful than Mixminion's "swap" operation, etc. [It seems a bit
-more harmful: in Mixminion, all messages have a swap point somewhere in
-the path. In this scheme, messages that ask to be delayed are inherently
-more interesting. -RD]
-
+%Can anyone attack the "delay until next batch" option? I don't think
+%the fact that those messages can be distinguished by the node is any
+%more harmful than Mixminion's "swap" operation, etc. [It seems a bit
+%more harmful: in Mixminion, all messages have a swap point somewhere in
+%the path. In this scheme, messages that ask to be delayed are inherently
+%more interesting. -RD]
\subsection{Robustness of Message Delivery}
@@ -856,23 +885,26 @@
\subsection{Robustness in async vs sync}
+[This section still draft -RD]
+
But there's a deeper issue: in asynchronous-batching designs, a
late message still arrives. in this system, a late message is lost.
this is not very convenient for the user.
-\section{Comparison with Asynchronous Batching Designs}
+\subsection{Comparison with Asynchronous Batching Designs}
-The next step is to begin comparing synchronous free-routes with the
-more traditional asynchronous free-routes, with the goal of presenting
-a plausible design for a realistic protocol that could provide more
-security than Mixminion. Synchronous batching does away with the need
-for a replay cache (each message is labelled with its batch), removes
-partitioning attacks from key rotation, and generally provides clearer
-anonymity guarantees. On the other hand, our design is less robust to
-transient failures (dropped messages are bad for usability), and because
-the pool batching strategy spreads out the probability distributions,
-our design may fall more quickly to long-term statistical disclosure
-attacks~\cite{statistical-disclosure}.
+Now that we have shown synchronous free-routes can provide good anonymity,
+we must also begin comparing this design to the more traditional
+asynchronous free-route design, with the goal of presenting a plausible
+design that achieves better anonymity than Mixminion. Synchronous
+batching does away with the need for a replay cache (each message is
+labelled with its batch), removes partitioning attacks from key rotation,
+and generally provides clearer anonymity guarantees. On the other hand,
+because Mixminion's pool batching strategy spreads out message probability
+distributions between batches, our design may fall more quickly to
+long-term statistical disclosure attacks~\cite{statistical-disclosure}. It
+is also less robust to transient failures---dropped messages are bad
+for usability. We leave further comparison to future work.
\section{Summary}
\label{sec:conclusion}
@@ -884,11 +916,10 @@
synchronous batching compare favorably to cascade networks. We invite
further analysis of the trade-offs between each topology.
-
\section*{Acknowledgements}
-David Hopwood for the initial impetus and ideas; Camilla Fox, Rachel
-Greenstadt, LiWu Chang, Chris Laas, Ira Moskowitz,
-and Itamar Shtull-Trauring for probability discussions;
+We acknowledge David Hopwood for the initial impetus and ideas; and
+we thank Camilla Fox, Rachel Greenstadt, LiWu Chang, Chris Laas, Ira
+Moskowitz, and Itamar Shtull-Trauring for probability discussions.
%======================================================================
@@ -897,8 +928,9 @@
\appendix
-
+\newpage
\section{Entropy vs number of hops, for each topology}
+\label{sec:entropy-per-hop}
\begin{figure}[ht]
\centering
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/