[freehaven-cvs] Mostly added a robustness discussion

[syverson@seul.org]

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

Modified Files:
	sync-batching.tex 
Log Message:
Mostly added a robustness discussion


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- sync-batching.tex	20 Jan 2004 20:58:01 -0000	1.10
+++ sync-batching.tex	21 Jan 2004 00:52:25 -0000	1.11
@@ -1,4 +1,3 @@
-
 \documentclass{llncs}
 
 \usepackage{url}
@@ -173,6 +172,21 @@
 \subsection{The disadvantages of free MIX routes}
 \label{subsec:disad}
 
+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. 
+
 go through the claims in the paper and refute them
 
 \subsection{Blending attacks}
@@ -322,6 +336,17 @@
 
 * compare the entropy between 16 nodes: cascade, SA, and free-route
 
+%\begin{figure}
+%\begin{minipage}[t]{4in}
+%\mbox{\epsfig{angle=0,figure=badnodes,width=4in}}
+%\caption{Entropy vs chance of bad node, for four topologies (16 nodes)}
+%\label{fig:badnodes}
+%\end{minipage}
+%\hfill
+%\end{figure}
+
+
+
 \begin{figure}[ht]
 \centering
 \mbox{\epsfig{angle=270,figure=badnodes,width=4in}}
@@ -360,6 +385,64 @@
 for low-adversary-percentage? or always better?
 
 \subsection{Robustness}
+
+[Would a graph or three help illustrate these robustness points? -PS]
+
+It might seem from Fig.~\ref{fig:?} that the best anonymity is
+achieved with a 16x16 free-route network. There is almost no falloff
+in entropy until nearly ninety percent of the nodes are compromised.
+But this ignores robustness of message delivery. (Robustness of
+anonymity is discussed below.) With only a single node failure, for
+randomly chosen routes through this mixnet, nearly two thirds of
+messages will be undelivered (because they will need to pass through
+it at some point). With any quarter of the nodes nonfunctional, only
+one percent of messages will be delivered through the network. This
+makes such a network very brittle.
+
+A 4x4 cascade mixnet does much better. A single failed node affects
+only one quarter of the messages. And two failed nodes have a one in
+ten chance of being no worse than a single failed node. On the other
+hand there is a ninety percent chance that half the messages are
+blocked by two failed nodes. With a quarter of the nodes down, there
+is only a .035 probability that this will result in blocking all of
+the messages.
+
+In a 4x4 SA, a single failed node also stops a quarter of the
+messages.  Given a balanced distribution across all layers of the
+array, a second failed node will always affect more messages. But,
+there is only a ten percent chance that two node failures chosen at
+random will block half the messages. And, with a quarter of the nodes
+gone there is only a $5.5 \times 10^{-4}$ probability that this will
+happen in a way that blocks all the messages.
+
+Of the scenarios we have considered, a 16x4 free route is the most
+robust.  For randomly chosen routes, a single failed node can be
+expected to block delivery of only 6.7 percent of the messages.  Four
+failed nodes can be expected to block delivery on only a third of the
+messages. And, this is the expected fraction of messages blocked
+regardless of which four nodes fail.
+
+Robustness of anonymity against active attacks is harder to determine
+as these can take on such a variety of forms. In the simplest case
+though, we can consider the effect on anonymity of simple node
+failure, since this is the most straightforward way to actively shrink
+anonymity. Also, as discussed in Section~\ref{?}, there are techniques
+to detect and punish more selective attacks; although a combination of
+active and passive attacks should prove the most devestating.
+
+We can use the observations of the above paragraphs to note that the
+16x16 free route has the worst anonymity in the face of any node
+failure at all. And the 16x4 free route has the best. The anonymity of
+4x4 cascades are unaffected by node failure since any node that fails
+will wipe out the entire anonymity set.  The 4x4 systolic fairs better
+than the cascades until node failure causes the entropy to drop by
+two.  This can happen many ways, but the simplest is when three nodes
+in the same layer all fail at once.
+
+-----------------------------\\
+Below was previously in robustness subsec.
+
+
 scenario 4 is clearly least robust. 1-3 are the same,
 maybe 3b is a bit bad.
 

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