[freehaven-cvs] finish discussing blending attacks

[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:
finish discussing blending attacks


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -d -r1.19 -r1.20
--- sync-batching.tex	22 Jan 2004 07:32:05 -0000	1.19
+++ sync-batching.tex	22 Jan 2004 09:09:32 -0000	1.20
@@ -18,6 +18,7 @@
 
 \begin{document}
 %\title{The Disadvantages of Cascade Mix Networks and How to Overcome Them}
+%\title{The Advantages of Free-Route Mix Networks
 %\title{Synchronous Batching:\\Cascade Networks vs Free-Route Networks
 \title{Synchronous Batching:\\From Cascade Networks to Free Routes
 \thanks{Portions of this paper were inspired by discussions with David
@@ -302,41 +303,57 @@
 mixing at that node \cite{web-mix}. Using this approach for cascades is
 clearly efficient, because Alice need obtain tickets only for her chosen
 cascade~\cite{disad-free-routes}, but her anonymity set is still limited
-to that one cascade. It is an open problem whether other topologies can
-give equivalent anonymity while still only requesting tickets from a small
-fraction of the mixes, but we suspect they can. A bigger problem with
-the ticket scheme, however, is the feasibility of requiring all users
+to that one cascade. We suggest that other topologies may be able to
+give equivalent anonymity while only requesting tickets from a fraction
+of the mixes, but we leave that proof to future work. A bigger problem
+with the ticket scheme, however, is the feasibility of requiring all users
 to register with the mixes: it is hard to imagine that attackers can be
-excluded from being registered (in an open network). Other prevention
+excluded from being registered in an open network~\cite{sybil}. Other
+prevention
 techniques use complex cryptography to provide \emph{robustness}
 \cite{flash-mix} --- messages are only delivered if a threshold of the
 mixes agree that the batch has been properly processed.
 
+Techniques to slow the blending attack are generally designed for
+asynchronous mix networks. In deployed mix networks like Mixmaster
+and Mixminion, the goal of the batching algorithm is to hide from
+the adversary when an outgoing message entered the mix. Mixes `pool'
+some messages from previous batches, to try to mix them as far back
+as possible. These approaches force the adversary to spend more time
+and messages on the attack \cite{trickle02}. Some designs allow a
+pool mix to commit to its choice of randomness to allow verifying
+its behavior~\cite{FGJP98,Jer2000}. Link encryption, as well as
+Babel's \emph{inter-mix detours}, aim to block a limited adversary
+from knowing when his message has exited the mix. In stop-and-go
+mixes~\cite{stop-and-go}, each sender specifies a time window for each
+mix in his path: as with synchronous batching designs, messages arriving
+outside the time window are dropped, so the attacker cannot arbitrarily
+delay messages without destroying them.
 
-slow:
-In deployed mix networks like Mixmaster and Mixminion, the goal of the
-batching algorithm is to hide from the adversary when an outgoing message
-entered the mix. Mixes `pool' some messages from previous batches, to
-try to mix them as far back as possible.
-pools: systems that allow a pool mix to commit to its choice of randomness
-\cite{FGJP98,Jer2000}
-link encryption to block a limited adversary from knowing when his
-message has exited. inter-mix detours in babel.
-stop-and-go is related to sync-batching.
-
-detect+punish:
-crazy ledger notion \cite{chaum-mix}
-and hey, mix-acc isn't so bad compared to the ticket scheme.
-and casc-rep for checking performance of mixes by mixes.
-rgb mixes, but there the adversary can still drop sender messages
-plus there's randomized partial checking.
-delayed messages cannot be reintroduced, so easier to notice dropped messages.
-
-adversaries: weak adversary beats cascades but not free-routes.
+Other approaches aim to detect misbehavior and discourage future
+misbehavior. Chaum suggests allowing each sender to examine the output
+of each mix~\cite{chaum-mix}, but this approach scales poorly. Danezis
+and Sassaman propose a `heartbeat' dummy scheme~\cite{danezis:wpes2003}
+for asynchronous pool mix networks: dummies are sent from a node in the
+network back to itself, creating an early warning system to detect if
+the adversary is launching a blending attack (but this approach does
+detect whether mixes drop messages directly from senders). Reliability
+mechanisms aim to improve a sender's long-term odds of choosing a
+mix path with well-behaving nodes. The witness-and-receipt system in
+\cite{mix-acc} provides such a reputation system for synchronous-batching
+networks. Another reputation system for cascades~\cite{casc-rep} allows
+mixes to send test messages into the network to detect misbehavior.
+Finally, randomized partial checking~\cite{randomized-checking} allows
+each mix to demonstrate evidence of its correctness by revealing a
+pseudo-randomly selected subset of its input-output relationships.
 
+%adversaries: weak adversary beats cascades but not free-routes.
 
-refer to a section later in the paper where we'll talk about impact
-of active attacks on entropy.
+Clearly much work has been done to address blending attacks, and the
+current solutions are as applicable to synchronous free-route networks
+as they are to cascade networks.
+%We further discuss the impact of blending
+%attacks on entropy in Section~\ref{subsec:blending}.
 
 \subsection{Danezis's restricted routes paper}
 
@@ -355,7 +372,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, butn one of which can comfortably handle all of the
+1/4 of the traffic, but none 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

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