[freehaven-cvs] Tweaks to threat model presentation.

[syverson@seul.org]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/tmp/cvs-serv18603/sync-batching

Modified Files:
	sync-batching.bib sync-batching.pdf sync-batching.tex 
Log Message:
Tweaks to threat model presentation.


Index: sync-batching.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.bib,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- sync-batching.bib	23 Jan 2004 08:02:39 -0000	1.4
+++ sync-batching.bib	23 Jan 2004 23:33:44 -0000	1.5
@@ -61,6 +61,18 @@
    note =        {\url{http://www.eskimo.com/~weidai/mix-net.txt}},
 }
 
+
+
+@InProceedings{chaum-blind,
+  author = 	 {David Chaum},
+  title = 	 {Blind Signatures for Untraceable Payments},
+  booktitle = 	 {Advances in Cryptology:Proceedings of Crypto 82},
+  pages =	 {199--203},
+  year =	 1983,
+  editor =	 {D. Chaum and R.L. Rivest and A.T. Sherman},
+  publisher =	 {Plenum Press}
+}
+
 @inproceedings{pet2003-diaz,
   title = {Generalising Mixes},
   author = {Claudia D\'iaz and Andrei Serjantov},

Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
Binary files /tmp/cvs3E48qb and /tmp/cvsWPOJhd differ

Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.31
retrieving revision 1.32
diff -u -d -r1.31 -r1.32
--- sync-batching.tex	23 Jan 2004 23:26:31 -0000	1.31
+++ sync-batching.tex	23 Jan 2004 23:33:44 -0000	1.32
@@ -24,11 +24,11 @@
 %\title{The Disadvantages of Cascade Mix Networks and How to Overcome Them}
 %\title{The Advantages of Free-Route Mix Networks
 %\title{Synchronous Batching:\\Cascade Networks vs Free-Route Networks
-\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
-\thanks{Portions of this paper were inspired by discussions with David
+\title{Synchronous Batching:\\Beat Mixing from Cascade Networks 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.}}
 
@@ -53,6 +53,11 @@
 
 \end{abstract}
 %======================================================================
+\begin{quotation}
+\emph{I saw the best minds of my generation destroyed by madness...}
+\end{quotation}
+%\hspace*{\fill}--Allen Ginsberg in ``Howl''
+
 \section{Introduction}
 \label{sec:intro}
 
@@ -95,7 +100,7 @@
 
 In Section~\ref{sec:sync-batching} we describe the synchronous batching
 model. Then in Section~\ref{sec:related} we relate previous work
-to synchronous batching, including refuting each of the arguments
+to synchronous batching, including responding to each of the arguments
 from~\cite{disad-free-routes}. Section~\ref{sec:scenarios} presents the
 three topologies in detail, and walks through calculating their entropy
 (average anonymity the sender expects from the network). We use a model
@@ -190,11 +195,13 @@
 % This section is based on notes from David Hopwood. Will the real
 % David Hopwood please come forward and become an author?
 
-Berthold et al.~argue \cite{disad-free-routes} that cascades are safer
+Berthold et al.\ argue \cite{disad-free-routes} that cascades are safer
 than free-route mix networks against a strong adversary who watches all
-links and controls many of the mixes. We refute each of their attacks
-below with respect to a free-route mix network that uses synchronous
-batching.
+links and controls many of the mixes. We consider each of their attacks
+below and find in each case that the arguments of \cite{disad-free-routes}
+do not apply if the free-route network is synchronous. Indeed, against
+some of attacks the free-route network is substantially stronger than
+the cascade.
 
 {\bf{Position in mix route:}} This attack partitions messages that go
 through a given honest node based on how many hops each message has
@@ -226,12 +233,12 @@
 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
-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
-long as they use synchronous batching, they are not vulnerable to this
-particular attack.}
+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
+%long as they use synchronous batching, they are not vulnerable to this
+%particular attack.}
 
 {\bf{Probability of Unobservability:}} The authors explain that the
 cascade topology optimizes for the case that only one mix node is
@@ -243,10 +250,11 @@
 entirely compromised path. But this is a false comparison. A better
 comparison would consider a cascade network with 20 nodes---thus
 the cascade network also has a chance of fully-compromised paths.
-In Section~\ref{sec:graphs} we show that while each cascade in the cascade
-network only mixes $1/w$ of the messages from the batch, a free-route
-network can mix all the messages from the batch and thus achieves
-significantly stronger anonymity even with 75\% compromised nodes.
+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,
+a free-route network can mix all the messages from the batch and thus
+achieves significantly stronger anonymity even with 75\% compromised
+nodes.
 
 {\bf{Active Attacks:}} The authors discuss an active attack called a
 trickle attack \cite{babel}, wherein the adversary prevents legitimate
@@ -260,7 +268,8 @@
 The authors of \cite{disad-free-routes} present some approaches to
 mitigating this attack in a cascade environment, but a variety of other
 approaches have been developed that also work in a free-route
-environment. We discuss them next.
+environment. We discuss them next. Other active attacks are described
+in Section~\ref{subsec:anonymity-robustness}.
 
 \subsection{Blending attacks}
 \label{subsec:blending}
@@ -333,30 +342,39 @@
 solutions appear applicable to synchronous free-route networks
 as well as cascade networks.
 
-\section{Threat model and Mixnet Topologies}
+\section{Threat model and mixnet topologies}
 \label{sec:scenarios}
 
 We consider a slight variant on the traditional powerful
-adversary~\cite{disad-free-routes}. Senders of messages
+adversary~\cite{disad-free-routes}. Senders of messages that are
 input to the mixnet and receivers of messages output from the mixnet
 can be observed.  It is assumed that selective forwarding will be
 discovered and prevented, or the misfunctioning node will be removed
-from the network (see Section~\ref{subsec:blending}).  While selective
-forwarding may remain viable as at least a one-time attack, we will
-not say more about it. We are also focused on sender anonymity of
-independent messages. We will not say anything about receiver
-anonymity, or sender anonymity in the face of pseudonymous profiles,
-that is, when messages in one or more exit batches can be suspected of
-coming from the same sender. An adversary is also assumed to only
-watch messages entering and leaving the mixnet. This is admittedly
-weaker than an adversary that can observe some links inside the
-network as well as at the periphery. However, a hostile node can see
-more than an adversary that observes its network connections. In this
-sense our model subsumes such a threat provided the adversary is not
-global.  Adversaries are also assumed to compromise nodes at random
-rather than in a targeted fashion. See Section~\ref{subsec:random-adversary} for more
-discussion on this point. We have only described passive attacks,
-active attacks are described in Section~\ref{subsec:anonymity-robustness}.
+from the network (see Section~\ref{subsec:blending}). 
+
+Concerning an adversary  intersecting individual batches, see
+Section~\ref{subsec:disad} under ``determining the next mix''.
+Concerning long term intersection attacks, we say nothing. All mixnets
+in this paper, indeed all designs published to date, remain vulnerable
+to these. A response has been proposed \cite{langos02}, but no adequate
+solution has yet appeared.
+
+An adversary is assumed to only watch messages entering and leaving
+the mixnet. This is admittedly weaker than an adversary that can
+observe some links inside the network as well as at the periphery.
+However, a hostile node can see more than an adversary that observes
+that node's network connections. In this sense our model subsumes such
+a threat provided that the link-observing adversary is not global.
+Adversaries are also assumed to compromise nodes at random rather than
+in a targeted fashion. See Section~\ref{subsec:random-adversary} for
+more discussion on this point. We have only mentioned passive attacks
+above.  Active attacks are described in
+Section~\ref{subsec:anonymity-robustness}.
+
+Lastly before turning to mixnet topologies, we are examining sender
+anonymity. Though many of the advantages of synchronous batching carry
+over to receiver anonymity, we will not specifically discuss it in
+this paper.
 
 For all of our analyses, we assume a 16 node mixnet with all messages
 following a four node path. (We do say a few things about a 16 node
@@ -499,7 +517,8 @@
 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.
-% but we will ignore it for the present.
+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
@@ -509,26 +528,6 @@
 % reduce entropy in scenarios with low adversary density, because he
 % knows she doesn't exit from her entry node. Hm. -RD
 
-\subsection{Reputations and Node Preferences}
-
-Most deployed systems let users choose a preferred entry or exit hop,
-e.g.~based on trust. A skewed distribution of messages only at the entry
-or exit of the network should not impact entropy too much---we see from
-Figures \ref{fig:caschops}-\ref{fig:freehops} that much of each network's
-entropy is achieved after just a few hops.
-
-Reputation systems, on the other hand, encourage users to preferentially
-choose nodes \emph{throughout} the network. Further, reputation
-information can be exploited by an adversary to reduce anonymity,
-for example by predicting the user's behavior based on reputation
-statistics, or by attracting more traffic by building a strong reputation
-or degrading the reputation of others. One approach to working within
-these constraints would be to put like-reputationed nodes in the same
-layer of the stratified network, or in the same row of the cascade
-network \cite{casc-rep}, so reputation distribution (at each hop or
-in each cascade, respectively) will be more uniform. We leave this
-investigation to future work.
-
 \subsection{Average Entropy vs Actual Entropy}
 \label{subsec:average-actual}
 
@@ -863,30 +862,36 @@
 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}
+\section{Extensions and Future Work}
+\label{sec:conclusion}
 
-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}.
+In practice, several considerations have to be balanced when choosing
+a batching strategy and network structure. These include maximizing
+anonymity sets (both batch sizes through each node and the overall
+anonymity sets of users); bandwidth considerations; reliability;
+enabling users to choose nodes that they trust; and interactions with
+the reputation system.
 
-\section{Summary}
-\label{sec:conclusion}
+Further analysis of the trade-offs will be needed before choosing a
+final network structure. Note that a planned structure, where each
+users' software follows the plan consistently when constructing
+routes, will generally be able to achieve stronger and more easily
+analysed security properties than less constrained approaches.
 
-Previously, only cascade networks were considered secure against very
-powerful adversaries~\cite{disad-free-routes}. In this paper we show that
-other topologies can use the synchronous batching strategy to achieve
-similar protection. Further, we show that free-route topologies with
-synchronous batching compare favorably to cascade networks. We invite
-further analysis of the trade-offs between each topology.
+Comparison to Mixminion: No need for a replay cache. But less robust to
+transient failures.
 
+Reputations and node preference
+Most deployed systems let users choose their preferred entry or exit
+hops, e.g.~based on trust. which will mess with our distribution. but
+this is ok because after just a few hops of mixing, the distribution of
+the incoming batch doesn't matter as much anymore.
+Reputation systems \`{a} la mix-acc and casc-rep make people prefer one node
+over another, \emph{throughout} the mix network, not just at entries or
+exits. but we have to tolerate this sort of thing. one approach would
+be to put like-reputationed nodes in the same column of the SA or in
+the same row of the cascade \cite{casc-rep}, so distribution (at each
+hop or in each cascade, respectively) will be more uniform.
 
 
 \section*{Acknowledgements}

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