[freehaven-cvs] polish threat model + topologies

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching

Modified Files:
	model.tex sync-batching.tex 
Log Message:
polish threat model + topologies
start polishing the model checker section
add some numbers back in to picking-twice-in-a-row


Index: model.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- model.tex	26 Jan 2004 03:55:52 -0000	1.5
+++ model.tex	26 Jan 2004 12:58:34 -0000	1.6
@@ -9,10 +9,10 @@
 \section{Modeling Methodology}
 
 The basic model underlying our comparative study of mix network topologies
-is \emph{mixing as probabilistic permutation}.  At the cost of making a
-few simplifying, yet realistic assumptions about distribution of message
+is \emph{mixing as probabilistic permutation}.  At the cost of a
+few simplifying but reasonable assumptions about distribution of message
 traffic in the network, we obtain a tractable Markov chain model,
-and use a fully automated probabilistic model checking techniques to
+and use a fully automated probabilistic model checking technique to
 compute probability distributions for different network topologies and
 configurations.  We use \emph{entropy} of each topology's respective
 distribution as our comparison metric, in the spirit of~\cite{Serj02}.
@@ -20,10 +20,10 @@
 
 \subsection{Mixing as permutation}
 
-Consider a single batch of messages entering the mix network in the same
-batch period.  We can view each message $m_1,\ldots,m_N$ as occupying
-a certain position in a (virtual) input array of length $N$, where $N$
-is the size of the batch.  Suppose the adversary targets a particular
+Consider a single batch of $N$ messages entering the mix network together.
+We can view each message $m_1,\ldots,m_N$ as occupying
+a certain position in a (virtual) input array of length $N$.
+Suppose the adversary targets a particular
 message $m$ in position $i$.  Without loss of generality, assume that
 $i=1$ (we can always re-number the input array so that the targeted
 message is in the first slot).
@@ -63,8 +63,8 @@
 \subsection{Overview of the model}
 
 We use the standard techniques of probabilistic verification and model the
-mixnet network as a discrete-time Markov chain.  Formally, a \emph{Markov
-chain} consists in a finite set of states $S$, the initial state $s_0$,
+mix network as a discrete-time Markov chain.  Formally, a \emph{Markov
+chain} consists of a finite set of states $S$, the initial state $s_0$,
 the transition relation $T:S\times S\rightarrow[0,1]$ such that 
 $\forall s\in S\ \sum_{s'\in S} T(s,s')=1$, and a labeling function.
 

Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.41
retrieving revision 1.42
diff -u -d -r1.41 -r1.42
--- sync-batching.tex	26 Jan 2004 04:22:58 -0000	1.41
+++ sync-batching.tex	26 Jan 2004 12:58:34 -0000	1.42
@@ -250,7 +250,7 @@
 the important property is whether the network uses synchronous batching,
 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
+hop, so messages cannot be partitioned based on when they enter or 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
@@ -362,50 +362,50 @@
 \section{Threat model and mixnet topologies}
 \label{sec:scenarios}
 
-[This section still draft -RD]
+Our analysis considers a slight variant on the traditional
+powerful adversary who observes globally and controls a fraction
+of the nodes~\cite{disad-free-routes}. We assume the adversary
+compromises nodes at random rather than in a targeted fashion (see
+Section~\ref{subsec:random-adversary} for more discussion on this point).
+Along with being able to control some of the nodes, our adversary can
+observe messages from senders to the mixnet and from the mixnet to
+receivers, but he cannot observe the links between honest nodes in
+the mixnet (in Section~\ref{subsec:average-actual} we argue that
+with high probability, observing these links will not yield much
+new information anyway).
 
-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
-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}). 
+This paper only examines sender anonymity, though many of the advantages
+of synchronous batching carry over to receiver anonymity.
 
-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.
 
-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
+We assume that selective forwarding will be discovered, and either the
+attack will be prevented or the malfunctioning node will be removed
+from the network (see Section~\ref{subsec:blending}). We address the
+attack of intersecting individual batches in Section~\ref{subsec:disad}
+(under ``determining the next mix''), but unsurprisingly, we leave the
+long-term intersection attack~\cite{langos02,statistical-disclosure}
+unsolved. Further active attacks to degrade anonymity 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
-path free route.) We use the same number for all mixnets to
-have a reasonably fair comparison of available resources.  Besides
-being a tractable size for analysis, this is also a fairly good
+We analyze a 16 node mixnet where all messages follow a four node path.
+%(We do say a few things about a 16 node
+%path free route.)
+%We use the same number for all mixnets to
+%have a reasonably fair comparison of available resources.
+Besides
+being a tractable size for analysis, 16 nodes is also a fairly good
 approximation of actually deployed mixnets. (Mixminion currently has
 between 20 and 30 active nodes.)
 
 Messages proceed through all of our networks in \emph{layers}; all of the
 nodes in a layer process messages of one mixnet batch at the same time.
-In general we describe networks as $n$x$\ell$, where $n$ is the number
+In general we describe networks as $w$x$\ell$, where $w$ is the number
 of nodes at each layer and $\ell$ is the number of nodes in a path.
 
 We consider three basic topologies: a 4x4 cascade mixnet in which all
@@ -446,10 +446,10 @@
 \section{Graphs and Analysis}
 \label{sec:graphs}
 
-\begin{figure}[ht]
+\begin{figure}[t]
 \centering
-\mbox{\epsfig{angle=270,figure=badnodes,width=3in}}
-\caption{Entropy vs chance of bad node (16 nodes)}
+\caption{Entropy vs probability of compromise for each node (16 nodes)}
+\mbox{\epsfig{angle=270,figure=badnodes,width=4in}}
 \label{fig:badnodes}
 \end{figure}
 
@@ -481,7 +481,7 @@
 longer an appealing target.
 
 Alternatively, the mixes can periodically generate a communally random
-seed that determines a new network topology \cite{casc-rep}. Thus,
+seed to reorganize the network \cite{casc-rep}. Thus,
 being able to control or sign up a node does not allow the adversary to
 dictate its position in the topology. This may be a satisfactory solution,
 though it is not a complete solution because not all nodes are equal:
@@ -490,12 +490,11 @@
 
 \subsection{Choosing the same node twice in a row}
 
-Conventional wisdom (see e.g.~\cite{minion-design}) suggests that
-in a free-route network, Alice should never choose the same node twice
-in a row when picking her path. The goal is to reduce the chance that
-the path contains only bad nodes. We find that for a sufficiently
-large network, this increased complexity in path selection has little
-impact on Alice's entropy. 
+Conventional wisdom (see e.g.~\cite{minion-design}) suggests that in
+a free-route network, Alice should never choose the same node twice in
+a row when picking her path, to reduce her risk of picking only bad
+nodes. We find that for a sufficiently large network, this increased
+complexity in path selection has little impact on Alice's entropy.
 
 Intuitively, when the adversary density is low, entropy will be high
 in either case; whereas when most nodes are owned by the adversary,
@@ -505,10 +504,13 @@
 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. As the network size grows,
-the shift in probability distribution becomes negligible.
+fraction of the nodes are bad. 
+%As the network size grows,
+%the shift in probability distribution becomes negligible.
+Specifically, for a 16x4 free-route mixnet (8 bad nodes), it's a 5.1\%
+chance of an all bad path if a node cannot be picked twice in a row,
+and 6.3\% chance if it can. With 32x4, it's 5.7\% vs.\ 6.3\%.
 
-%%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

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