[freehaven-cvs] Fix and more discussion of anonymity robustness. Twe...

[syverson@seul.org]

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

Modified Files:
	sync-batching.tex 
Log Message:
Fix and more discussion of anonymity robustness. Tweaks on message robustness.


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- sync-batching.tex	21 Jan 2004 23:47:11 -0000	1.16
+++ sync-batching.tex	22 Jan 2004 01:51:20 -0000	1.17
@@ -311,7 +311,7 @@
 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
+1/4 of the traffic, butn one of which can comfortably handle all of the
 traffic. so what topology is best?
 
 We use the information theory approach from \cite{Diaz02,Serj02} to
@@ -425,6 +425,9 @@
 reasonably large values of $G+B$ (total number of nodes), the shift
 in probability distribution is negligible.
 
+
+\subsection{Robustness of Message Delivery}
+
 % Mention that we have that entropy different for each of \ell hops.
 % But it's just \ell times the above negligible difference, right? -RD
 
@@ -433,8 +436,6 @@
 % reduce entropy in scenarios with low adversary density, because he
 % knows she doesn't exit from her entry node. Hm. -RD
 
-\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
@@ -446,47 +447,130 @@
 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.
+makes such a network very brittle. 
 
 A 4x4 cascade network 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.
+is only a .035 probability that these will be distributed so as to
+block 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.
+In a 4x4 stratified topology, 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.
+messages. At least as significant is that this is the expected
+fraction of messages blocked regardless of which four nodes fail.
+
+\subsection{Robustness of Anonymity}
 
 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
+crash, 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 devastating.
+to detect and/or punish more selective attacks.
+
+The threat model we consider in this section is a varient 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
+this for future work.
+
+Anonymity of cascades are unaffected by this threat model.  Since each
+cascade batch is independent of another, any node that crashes will wipe
+out all the messages in the anonymity set.  Anonymity robustness of
+stratified and free-route topologies is more complex.
+
+For a stratified network, if any entry node fails, the number of
+messages drops by one quarter, causing a reduction in entropy of .42.
+If two entry nodes fail, the entropy drops by 1. If 3 entry nodes
+fail, entropy drops by 2. If all fail, entropy remains the same as if
+none fail.  If a second layer node fails, assuming a balanced
+layer-two distribution, anonymity of all messages are unaffected since
+there is no change to the probability that an exiting message was any
+incoming message. Note this is so even if the distribution of messages
+across entry nodes is highly skewed. If the layer-two distribution is
+skewed, then a node may fail with some effect on entropy. However, the
+ability to affect anonymity in this way should be very small for
+randomly chosen routes.  Ignoring the small effect of such
+non-entry-layer failures, we see that the anonymity of a stratified
+network given node crashes is usually better and at worst equal
+to that of the cascade topology.
+
+For free routes, it is even more difficult to determine the anonymity
+effect of node crash. For entry layer nodes, obviously the initial
+effect of each crash is smaller. However, since nodes are used at
+multiple layers, a message that reaches a crashed node at a given
+layer could not have been routed through that node at any earlier
+layer. And, by crashing nodes in order, some additional information
+may be gained. Add to this that, as the ratio of input messages to
+width of a layer shrinks, it becomes more likely that nodes at a given
+layer will only receive messages from a subset of nodes at the
+previous layer or, in any case, that the layer distribution will
+unbalanced between nodes to a significant degree. On the other hand,
+because nodes are recycled for use at multiple layers, it is much
+harder to plan an attack.  Crashing an entry node to reduce the
+anonymity of a message at another node may cause that message to be
+blocked when it must traverse the crashed node at a later layer. If
+nodes have the ability to crash intermittently, then this issue goes
+away. But, it will generally be hard to predict when to come up beyond
+a few layers, because the targeted message will likely be coming from
+any of the remaining nodes after that much mingling (route mixing).
+
+To get some handle on this, we will consider a very lucky adversary.
+The adversary controls a quarter of the nodes in a 16x4 recycling
+free-route.  Suppose a message enters the mixnet at a node not under
+adversary control, and the adversary crashes all of its nodes.
+Messages drop by a quarter. If the layer-2 distribution is such that
+the layer-1 node that received the target does not send any messages
+to the four adversary nodes, they remain crashed. Assuming that a
+quarter of the remaining messages are addressed to them at layer-2,
+remaining messages are now .56 of the original batch. Repeat for
+layer-3 and layer-4. Remaining messages are down to .32 of the
+original mixnet batch. In this case, despite all the luck of the
+adversary, the anonymity is thus still better than that of a message
+sent into a cascade processing a quarter of the original messages. And
+this is also better than the anonymity of the stratified 4x4 network
+with just two hostilely crashed entry nodes.
+
+We have not considered all possible active attacks. But for those we
+have considered, the best choice for anonymity robustness of those
+topologies investigated appears to be the free route, and worst is the
+cascade.
+
+Change terminology: 
+
+[Should note somewhere that stratified is like classic systolic arrays
+in that a layer can process a new batch as soon as it has sent the
+last with no additional overhead. That's not true of free routes.]
+
 
-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.

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