[freehaven-cvs] Is the adversary really randomly distributed?

[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:
	sync-batching.tex 
Log Message:
Is the adversary really randomly distributed?
plus finish the node flooding subsec


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.28
retrieving revision 1.29
diff -u -d -r1.28 -r1.29
--- sync-batching.tex	23 Jan 2004 21:23:21 -0000	1.28
+++ sync-batching.tex	23 Jan 2004 21:33:01 -0000	1.29
@@ -358,17 +358,6 @@
 discussion on this point. We have only described a passive attacks,
 active attacks are discribed in Section~\ref{subsec:anonymity-robustness}.
 
-[Save these points until see what Roger has done for section ?
-
-he can't control which node he gets, because we use a
-communal-randomness-based topology randomization a la casc-rep.
-(though still, some nodes will refuse to be exit nodes, and some will be
-ok with it, so compromising the ones that are ok with it will give you
-a better shot at owning an exit node in the resulting topology.)
-
-]
-
-
 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 the same number for all mixnets so as to
@@ -476,6 +465,29 @@
 \section{Other considerations in the analysis}
 \label{sec:other}
 
+\subsection{Is the adversary really randomly distributed?}
+
+To keep our model tractable, we have assumed that each node has an
+equal chance of being controlled by the adversary. A real adversary
+might prefer to control certain key nodes in the topology.
+
+To justify our assumption, we might assume that secure nodes (or
+equivalently, vulnerable nodes) are randomly distributed. That is,
+rather than letting the adversary have his pick of nodes, we instead
+let the adversary control all the machines that have some security
+vulnerability. A related approach would be place particularly secure
+and trusted (or at least jurisdictionally separate) nodes in key places
+in the topology: if such nodes are discouragingly secure, they are no
+longer an appealing target.
+
+Alternatively, the mixes can periodically generate a communally random
+seed that determines a new network topology \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:
+e.g.~nodes that refuse to deliver messages to the final recipients
+shouldn't be chosen as exit nodes, so they may be less appealing targets.
+
 \subsection{Choosing the same node twice in a row}
 
 Conventional wisdom (see e.g.~\cite{minion-design}) suggests that
@@ -573,17 +585,14 @@
 batching strategy \cite{trickle02}, where messages from the adversary
 will influence the behavior (and thus entropy) of Alice's message.
 
-On the other hand, there's also the issue that directed floods can fill up
-nodes. we might use techniques where mixes can prove that
-they passed the message on from before \cite{phillipe-manuscript};
-thus we can be certain that floods start at the beginning of the batch.
-
-point out that this flooding issue is a problem for sync-batching in any
-topology. argue that fraction of adversary messages is proportional to
-the max size of the flooding attack.
-
-but it's a hard problem.
-
+On the other hand, directed floods can overflow node capacity. We
+might use techniques where mixes can prove that any output message was
+derived from an input message, which reduces the problem to detecting
+or stopping floods at the beginning of the batch. We might also argue
+that the fraction of adversary messages in the batch limits the maximum
+size of the flooding attack---honest messages will still be randomly
+distributed. In general, this flooding issue is an unsolved problem for
+all mix-net designs; more research remains.
 
 \section{Other metrics for comparison}
 \label{sec:metrics}
@@ -707,7 +716,7 @@
 \end{table}
 
 \begin{table}
-\caption{Exp.\ percent messages delivered: Random adversary dist.}
+\caption{Expected percent messages delivered: Random adversary dist.}
 \label{table:expected-delivery}
 \renewcommand{\arraystretch}{1.3}
 \begin{center}

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