[freehaven-cvs] progress on section 3

[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:
progress on section 3


Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- sync-batching.tex	22 Jan 2004 02:32:42 -0000	1.18
+++ sync-batching.tex	22 Jan 2004 07:32:05 -0000	1.19
@@ -73,7 +73,6 @@
 systems such as those described in \cite{mix-acc,casc-rep}.
 \item It helps block blending attacks compared to asynchronous batching,
 because mixes cannot delay messages without permanently dropping them.
-% though rgb, but there the adversary can still drop sender messages
 
 % * exit policies impose differentiation anyway. might as well make it
 %   formally part of the topology.
@@ -94,10 +93,10 @@
 topologies in detail, and provides a walk-through of calculating entropy
 (average anonymity the sender expects from the network) for each. Then we
 use a model checker to automatically calculate the entropy for networks
-with 16 nodes, and present results in Section~\ref{sec:graphs}. We go on
-in Section~\ref{sec:other} to consider other metrics such as robustness,
-and wrap up in Section~\ref{sec:conclusion} with future work and other
-possible extensions.
+with 16 nodes, and present our results in Section~\ref{sec:graphs}. We
+go on in Section~\ref{sec:other} to consider other metrics such as
+robustness, and wrap up in Section~\ref{sec:conclusion} with future work
+and possible extensions.
 
 \section{Synchronous batching}
 \label{sec:sync-batching}
@@ -245,7 +244,7 @@
 to messages entering honest mixes, and he can link receivers to
 messages exiting honest mixes. Thus the target messages will only
 be mixing with other messages that enter the mix node at that time,
-rather than with other messages elsewhere in the network. If senders
+rather than with other messages elsewhere in the network. Even if senders
 use the same path for multiple messages, the authors point out that
 \emph{the batches always generate different anonymity groups.} Again,
 the important property is whether the network uses synchronous batching,
@@ -272,39 +271,72 @@
 mix all the messages from the batch and thus achieves significantly
 stronger anonymity even with 75\% compromised nodes.
 
-{\bf{Active Attacks:}}
-
-first knock down their crazy ledger notion.
-
-then knock down the assumption that you can register all your users.
-
-and hey, mix-acc isn't so bad compared to the ticket scheme.
+{\bf{Active Attacks:}} The authors discuss an active attack called a
+trickle attack \cite{babel}, wherein the adversary prevents legitimate
+messages from entering the batch, or removes some messages from the
+batch, so he can more easily trace Alice's message. To make the attack
+less obvious, he can send his own messages into the batch, or replace
+the messages already in the batch with his own messages. These attacks
+where the adversary \emph{blends} his messages with Alice's message
+threaten both synchronous-batching and asynchronous-batching networks in
+all topologies, and a complete solution is not known \cite{trickle02}.
+The authors of \cite{disad-free-routes} present some approaches to
+mitigating this attack in a cascade environment, but a variety of other
+approaches have been developed recently that also work in a free-route
+environment. We discuss them next.
 
-plus there's randomized partial checking.
+\subsection{Blending attacks}
 
+Active attacks where the adversary targets a message by manipulating
+the other messages in the system are a widespread problem in mix-based
+systems. Solutions fall into three categories: attempts to \emph{prevent}
+the attack, attempts to \emph{slow} the attack, and attempts to
+\emph{detect and punish} the attacker.
 
+One prevention technique requires senders to acquire a \emph{ticket}
+for each mix in his path before submitting his message to the given
+batch (the senders receive blinded tickets \cite{chaum-blind} so the
+mixes cannot trivially link them to their messages). This approach
+allows the mixes to be certain they are receiving messages from distinct
+senders; so long as one node in her path is honest, Alice is sure of good
+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 register with the mixes: it is hard to imagine that attackers can be
+excluded from being registered (in an open network). 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.
 
-\subsection{Blending attacks}
 
+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. This technique aims to defend
-against \emph{blending attacks} such as the $n-1$ or \emph{trickle}
-attack, where the adversary submits all but one messages in a batch,
-and then learns the destination of the target message. In the synchronous
-batching design, on the other hand, the goal is to mix a message with the
-other messages in its batch. Blending attacks are somewhat mitigated by
-preventing messages from being delayed. An attacker cannot reintroduce
-the messages that he removed; he must permanently trash all the messages
-that are not in the trickle, which will hopefully be noticed.
+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.
 
-talk about active attacks. how effective they can be on
-free-routes. and particularly on cascades. talk about
-pools, and tickets, and rgb mixes, and mix-acc. refer to a
-section later in the paper where we'll talk about active
-attacks on the stratified topology.
+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.
 
 \subsection{Danezis's restricted routes paper}
 
@@ -692,6 +724,12 @@
 row of the cascade \cite{casc-rep}, so distribution (at each hop or in each
 cascade, respectively) will be more uniform.
 
+\subsection{Comparison to Mixminion}
+
+No need for a replay cache.
+
+But less robust to transient failures.
+
 \section{Extensions and Future Work}
 \label{sec:conclusion}
 

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