[freehaven-cvs] Threat model and mixnet topology descriptions.

[syverson@seul.org]

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

Modified Files:
	sync-batching.tex 
Log Message:
Threat model and mixnet topology descriptions.


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.27
retrieving revision 1.28
diff -u -d -r1.27 -r1.28
--- sync-batching.tex	23 Jan 2004 19:57:26 -0000	1.27
+++ sync-batching.tex	23 Jan 2004 21:23:21 -0000	1.28
@@ -115,10 +115,10 @@
 in turn decrypts, delays, and re-orders messages, before relaying them
 toward their destinations.
 
-A mix-net design groups messages into batches and chooses paths;
+A mixnet design groups messages into batches and chooses paths;
 its design choices affect the degree of anonymity it can provide
 \cite{trickle02}.
-We might define ideal anonymity for a mix-net to be when an attacker can
+We might define ideal anonymity for a mixnet to be when an attacker can
 gain no information about the linkage between messages entering and
 leaving the network, other than that the maximum time between them is
 equal to the maximum network latency.
@@ -145,7 +145,7 @@
 is related to the maximum desired latency; a typical value
 could be 3 hours.  Messages entering the network in each batch
 period are queued until the beginning of the next period. They are
-then sent through the mix-net synchronously, at a rate of one hop per
+then sent through the mixnet synchronously, at a rate of one hop per
 {\em hop period}. All paths are a fixed length $\ell$ hops, so that if
 no messages are dropped, the messages introduced in a given batch will
 progress through their routes in lock-step, and will all be transmitted
@@ -153,7 +153,7 @@
 message, once decrypted, specifies the hop period in which it must be
 received, so that it cannot be delayed by an attacker.
 
-Define the {\em width} $w$ of a mix-net using synchronous batching to
+Define the {\em width} $w$ of a mixnet using synchronous batching to
 be the number of nodes that simultaneously process messages in each hop
 period. (If this is not constant, we can still talk about the maximum,
 minimum and mean width.) Thus when $w=1$ we have a cascade.
@@ -211,8 +211,8 @@
 trustworthy, then the achievable anonymity is distinctly lower in a mix
 network compared to a synchronously working mix cascade.} The actual
 conclusion should be: If only one mix of a route is trustworthy, then
-the achievable anonymity is distinctly lower in an asynchronous mix-net
-than in a synchronous mix-net (whether it uses free routes or cascades).
+the achievable anonymity is distinctly lower in an asynchronous mixnet
+than in a synchronous mixnet (whether it uses free routes or cascades).
 
 {\bf{Determining the next mix:}} An adversary owning most nodes
 in the network can attack the honest mixes: he can link senders
@@ -333,24 +333,32 @@
 solutions appear applicable to synchronous free-route networks
 as well as cascade networks.
 
-\section{Scenarios}
+\section{Threat model and Mixnet Topologies}
 \label{sec:scenarios}
 
-explain threat model: adversary can see all incoming and outgoing
-messages at the network edges
-and has a chance for each node of compromising it
-Which system is advantageous depends on the adversary model and the
-desired security properties. Against an adversary who can observe only a
-relatively small percentage of nodes, links, or mixnet entry and exit
-points a free route has trememdous advantage in protecting average
-expected anonymity over a cascade. This is because the adversary will
-not be able to see as many messages; he is simply spread to thin. In
-a cascade the adversary can focus on the head and tail and see all the
-messages entering or leaving the network. On the other hand,
-A completely free route network will have the advantage in a network
-where the adversary can only choose a small number of points because
-messages can enter and exit the network anywhere.
+The threat model we consider is a slight variant of the standard one,
+for example as given in \cite{disad-free-routes}.  Senders of messages
+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{?} for more
+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.
@@ -358,12 +366,35 @@
 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.)
 
-assume we have 16 nodes, each of which can comfortably handle
-1/4 of the traffic, but none of which can comfortably handle all of the
-traffic. so what topology is best?
+]
+
+
+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
+have a reasonably fair comparison of available resources.  Besides
+being a tractable size for analysis, this is also a fairly good
+approximation of actually deployed mixnets. (Mixmaster typically 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 mxinet batch at the same time.
+In general we describe networks as  $n$x$\ell$, where $n$ 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
+messages pass through four cascades of length four; a 4x4
+\emph{stratified} mixnet, in which all messages pass through four
+layers of disjoint nodes such that messages may pass from any node at
+one layer to any node at the next layer; and a 16x4 free-route mixnet,
+in which all nodes may receive messages at all layers. Note that
+because free-route nodes are reused, `16x4' does not imply 64 nodes.
+
+Examples of a 2x2 cascade mixnet, a 2x2 stratified mixnet, and a 4x2
+free-route mixnet are illustrated in Figures~\ref{fig:casc-2x2},
+\ref{fig:sa-2x2}, and \ref{fig:free-4x2}, respectively.
 
-We use the information theory approach from \cite{Diaz02,Serj02} to
-measure expected entropy for each scenario.
 
 \begin{figure}
 \begin{minipage}[t]{3.5cm}
@@ -391,6 +422,8 @@
 
 
 \subsection{further Assumptions}
+[Safe to cut now? Anything in this subsec not covered elsewhere? -PS]
+
 also discuss how scenario 3 makes a different assumption about the
 adversary, since watching all the nodes requires more power than just
 watching the entry and exit columns.
@@ -517,7 +550,7 @@
 $m=128$, then we find that only 1\% of the cases fall outside this value.
 
 Danezis also considers this issue of variance from average entropy for his
-mix-net design based on sparse expander graphs~\cite{danezis:pet2003}. He
+mixnet design based on sparse expander graphs~\cite{danezis:pet2003}. He
 argues that having at least one message on each link is sufficient for
 basic protection, and he uses a similar approach to show that his design
 achieves this distribution with high probability. He further raises the
@@ -722,6 +755,7 @@
 size.
 
 \subsection{Robustness of Anonymity}
+\label{subsec:anonymity-robustness}
 
 Robustness of anonymity against active attacks is harder to determine
 as these can take on such a variety of forms. In the simplest case
@@ -731,25 +765,16 @@
 are techniques
 to detect and/or punish more selective attacks.
 
-The threat model we consider in this section is a variant of the one
-we have been using all along. Senders of messages input to the mixnet
-and receivers of messages output from the mixnet can be observed. But
-hostile nodes may now also crash, failing to deliver any of their
-input messages.  It is assumed that selective forwarding will be
-discovered. While selective-forwarding remains 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. While they may use internal observations to decide how to
-attack the mixnet, we assume that these are memoryless observations,
-and only the resulting mixnet I/O after attacks are mounted are
-visible to the adversary.  A combination of active attacks and
-observations (including some internal observations) should prove the
-most devastating to anonymity. However, we leave examination of this
-for future work.
+The threat model we consider in this section is an extension of the
+one in Section~\ref{sec:scenarios}. As before, senders of messages
+input to the mixnet and receivers of messages output from the mixnet
+can be observed. But now, besides failing to mix, hostile nodes may
+also crash, failing to deliver any of their input messages.  A
+combination of active attacks and observations (including some
+internal observations) should prove the most devastating to anonymity.
+However, we leave full examination of this for future work. Here we
+concentrate on the effect of such intentional crash failures on
+entropy for a mixnet periphery observer.
 
 Anonymity of cascades are unaffected by this threat model.  Since each
 cascade batch is independent of the others, any node that crashes will wipe
@@ -843,7 +868,7 @@
 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
+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

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