[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] rewrite/tighten sections 1, 2, 3
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:
rewrite/tighten sections 1, 2, 3
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -d -r1.21 -r1.22
--- sync-batching.tex 22 Jan 2004 12:57:35 -0000 1.21
+++ sync-batching.tex 22 Jan 2004 23:40:24 -0000 1.22
@@ -59,51 +59,49 @@
message's path. They suggest instead a \emph{cascade network} topology,
where all senders choose from a few fixed paths through the mix network.
-Here we argue that the cascade design resolves the attacks not because
-of its network topology but because of a property of its batching
-strategy. We investigate this \emph{synchronous batching} approach in a
-variety of topologies, and find that it provides the following properties:
-%over Mixminion:
+In this paper we argue that the cascade design resolves the attacks not
+because of its network topology, but because of a property of its batching
+strategy. We find that this \emph{synchronous batching} approach prevents
+the attacks in \cite{disad-free-routes}, even when free routes are used.
+We explore three topologies with synchronous batching---cascade,
+stratified (a restricted route), and free-route---and find that the
+free-route network provides the highest expected anonymity as well as
+the best robustness to node failure.
-\begin{tightlist}
-\item It prevents the attacks in \cite{disad-free-routes}, even when free
-routes are used.
-\item It provides comparable latency to a cascade topology, even when free
-routes are used.
-\item It allows senders to verify message processing, enabling reputation
-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.
+%and provides comparable latency to a cascade topology,
+
+%\item It allows senders to verify message processing, enabling reputation
+%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.
% * exit policies impose differentiation anyway. might as well make it
% formally part of the topology.
-% * the one-to-a-sender ticket schemes can work
-
-\end{tightlist}
-We investigate synchronous batching in three network topologies:
-cascade, stratified (a restricted route), and free-route. We find that
-the free-route network provides the highest expected anonymity as well
-as the best robustness to node failure.
-
-%In Section~\ref{sec:sync-batching},
-Next we describe the synchronous batching model in more
-detail. Then in Section~\ref{sec:related} we relate previous work
-to synchronous batching, including refuting each of the arguments in
-\cite{disad-free-routes}. Section~\ref{sec:scenarios} presents the three
-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 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.
+In Section~\ref{sec:sync-batching} we describe the synchronous batching
+model. Then in Section~\ref{sec:related} we relate previous work
+to synchronous batching, including refuting each of the arguments
+from~\cite{disad-free-routes}. Section~\ref{sec:scenarios} presents the
+three topologies in detail, and walks through calculating their entropy
+(average anonymity the sender expects from the network). We use a model
+checker to automatically compute entropy for networks with 16 nodes:
+we present our results in Section~\ref{sec:graphs} and assess the
+assumptions behind those results in Section~\ref{sec:other}. We go on in
+Section~\ref{sec:metrics} to consider other metrics such as bandwidth
+requirements and robustness, and wrap up in Section~\ref{sec:conclusion}
+with future work and possible extensions.
\section{Synchronous batching}
\label{sec:sync-batching}
-A mix-net design groups messages into batches and chooses paths; the
-approaches it uses affect the degree of anonymity it can provide
+Chaum proposed hiding the correspondence between sender and recipient
+by wrapping messages in layers of public-key cryptography, and relaying
+them through a path composed of \emph{mixes} \cite{chaum-mix}. Each mix
+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;
+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
gain no information about the linkage between messages entering and
@@ -112,29 +110,25 @@
This ideal is not achieved by protocols like Mixminion that use locally
computed random delays: if the maximum latency of such a network is $t$,
-%then the anonymity set of a message leaving the network may be much
-%smaller than all messages that entered over a time $t$.
-%More precisely,
the probability that an output message corresponds to a particular
input message might be considerably higher than for other messages that
-have entered over a time $t$.
-(In principle, because of its pool mode, the maximum latency for a
-message that has just been
-sent could be infinite, but that's not a significant improvement
+have entered over that time. (In principle, because of its pool mode,
+a message's maximum latency could be infinite, but that's not a
+significant improvement
in practice: if the probability of a given latency $t$ drops off
exponentially with $t$, then so does the probability that
-a message that is leaving the network could have been sent that long
-ago \cite{Diaz02,Serj02}.)
+a message leaving the network could have been sent that long
+ago \cite{Serj02}.)
Also, because Mixmaster is both {\em asynchronous} (messages can enter
and leave the network at any time) and uses free routes, it is subject
to the attacks from \cite{disad-free-routes} described in
Section~\ref{subsec:disad} below.
-In the \emph{synchronous batching} approach,
-the network has a fixed {\em batch period}, $t_\mathrm{batch}$, which
-is closely related to the maximum desired latency; a typical value
-could be 3--6 hours. Messages entering the network in each batch
+A network that uses \emph{synchronous batching}
+has a fixed {\em batch period}, $t_\mathrm{batch}$, which
+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
{\em hop period}. All paths are a fixed length $\ell$ hops, so that if
@@ -142,26 +136,22 @@
progress through their routes in lock-step, and will all be transmitted
to their final destinations $\ell$ hop periods later. Each layer of a
message, once decrypted, specifies the hop period in which it must be
-received, so that it
-cannot be delayed by an attacker.
+received, so that it cannot be delayed by an attacker.
-Define the {\em width} $w$ of a mix network using synchronous batching to
+Define the {\em width} $w$ of a mix-net 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.)
The latency is between $\ell t_\mathrm{hop}$ and $t_\mathrm{batch} +
\ell t_\mathrm{hop}$, depending on when the message is submitted.
-
-we have two choices for $t_\mathrm{hop}$ --- do we make it tbatch/ell,
-or do we make it tbatch? which we want depends on other requirements,
-stay tuned.
-
-[Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/\ell$, so the
-latency is at most $2t_\mathrm{batch}$, independent of the path length.
-Or for free-route topology, we could let $t_\mathrm{hop}$ be
-$t_\mathrm{batch}$, and now it takes $\ell$ batch times to go through,
-but it mixes with the other batches.]
+Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/\ell$,
+so the latency is at most $2t_\mathrm{batch}$, independent of the
+path length. Thus the entire batch is processed and delivered before
+the next batch enters the network. Under this constraint, we can give
+nodes the maximum opportunity to make use of the available bandwidth,
+and the best chance at delivery robustness, by setting $t_\mathrm{hop}
+\simeq t_\mathrm{batch}/\ell$.
\section{Related work}
\label{sec:related}
@@ -174,10 +164,10 @@
step-by-step instructions for senders and mixes to use the network and
judge whether messages have arrived in time.
-The paper also describes a receipt and witness system by which senders and
-mixes can prove that a given mix failed to pass on a given message. These
-receipts allow a reputation system where nodes that drop messages lose
-reputation, discouraging misbehavior.
+That paper also describes a receipt and witness system by which senders
+and mixes can prove that a given mix failed to pass on or accept a given
+message. These receipts allow a reputation system: senders can recognize
+which nodes tend to drop messages.
\subsection{The Disadvantages of Free Mix Routes}
\label{subsec:disad}
@@ -192,9 +182,10 @@
batching.
{\bf{Position in mix route:}} This attack partitions messages that go
-through a given node based on how many hops each message has travelled so
-far. Because the adversary owns all nodes in the network but this node,
-he can distinguish messages at different positions in their path, and
+through a given honest node based on how many hops each message has
+travelled so far. If the adversary owns all other nodes in the network,
+he can distinguish messages at different positions in their path (say,
+one has passed two mixes already, and another has passed three), and
thus learn the sender and recipient of each message. The authors note:
\emph{Eventually, a message is only unobservable in that group of messages
which have this mix on the same routing position.} But in the synchronous
@@ -213,45 +204,47 @@
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. Even if senders
+and not 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,
-not whether it uses free routes. All messages in a batch exit the
-network together after the last hop, so messages cannot be partitioned
-based on when they exit the network. Free-route protocols where each
-sender fixes his path are vulnerable to attacks (e.g. tagging attacks
-\cite{disad-free-routes,raymond00}) that free-route protocols with
-randomly chosen paths can resist \cite{minion-design}, but so long
-as they use synchronous batching, they are not vulnerable to this
-particular attack.
+not whether it uses free routes. In a synchronous batching design,
+all messages in a batch exit the network together after the last
+hop, so messages cannot be partitioned based on when they exit
+the network.\footnote{Free-route protocols where each sender
+fixes his path are in fact vulnerable to attacks (e.g. tagging
+attacks~\cite{disad-free-routes,raymond00}) that free-route protocols
+with randomly chosen paths can resist~\cite{minion-design}, but so
+long as they use synchronous batching, they are not vulnerable to this
+particular attack.}
{\bf{Probability of Unobservability:}} The authors explain that the
cascade topology optimizes for the case that only one mix node is
-honest. They compare a 4-node cascade with 3 compromised nodes to a
-20-node free-route mix network with 75\% compromised nodes, and find that
-whereas the cascade provides complete protection, a user choosing four
+honest. They compare a 4-node cascade (with 3 compromised nodes) to
+a 20-node free-route mix network (with 75\% compromised nodes), and
+find that whereas
+the cascade provides complete protection, a user choosing four
nodes in the free-route network has a non-trivial chance of picking an
entirely compromised path. But this is a false comparison. A better
comparison would consider a cascade network with 20 nodes---thus
-the cascade network also has a chance of fully-compromised paths. In
-Section~\ref{sec:graphs} we show that whereas the cascade network only
-mixes $1/w$ of the messages in each cascade, a free-route network can
-mix all the messages from the batch and thus achieves significantly
-stronger anonymity even with 75\% compromised nodes.
+the cascade network also has a chance of fully-compromised paths.
+In Section~\ref{sec:graphs} we show that while each cascade in the cascade
+network only mixes $1/w$ of the messages from the batch, a free-route
+network can mix all the messages from the batch and thus achieves
+significantly stronger anonymity even with 75\% compromised nodes.
{\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
+less overt, 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
+approaches have been developed that also work in a free-route
environment. We discuss them next.
\subsection{Blending attacks}
@@ -263,28 +256,27 @@
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. We conjecture that other topologies may be able to
-give equivalent anonymity while only requesting tickets from a fraction
-of the mixes, but we leave that analysis 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~\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.
+One prevention technique requires each sender to acquire a \emph{ticket}
+for each mix in his path before joining a given batch (the senders
+receive blinded tickets \cite{chaum-blind} so the mixes cannot
+trivially link them to their messages). Mixes ensure their messages
+come from distinct senders, so Alice can expect good mixing at each
+honest node in her path~cite{web-mix}. For cascades this approach is
+clearly efficient, because Alice only needs tickets for her chosen
+cascade~\cite{disad-free-routes}, but her anonymity set is still
+limited to that one cascade. We conjecture that other topologies
+can give equivalent anonymity while only obtaining tickets from a
+fraction of the mixes, but we leave that analysis 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~\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
+asynchronous mix networks. In 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
@@ -293,38 +285,38 @@
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
+from knowing when his message has exited the mix~\cite{babel}. 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.
-Other approaches aim to detect misbehavior and discourage future
-misbehavior. Chaum suggests allowing each sender to examine the output
+Other approaches aim to detect and deter 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.
+the adversary is launching a blending attack.
+%(but this approach does not
+%detect whether mixes drop messages directly from senders)
+\emph{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 show evidence
+of its correctness by revealing a pseudo-randomly selected subset of
+its input-output relationships, while the mix network as a whole still
+protects linkability with high probability.
%adversaries: weak adversary beats cascades but not free-routes.
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}.
-
-
+current solutions appear applicable to synchronous free-route networks
+as well as cascade networks.
\section{Scenarios}
\label{sec:scenarios}
@@ -560,8 +552,6 @@
Let $T_\mathrm{batch}$ be the expected throughput in a single batch period,
i.e.~the number of messages that go through the network in a batch.
-We can give nodes the maximum opportunity to make use of the available
-bandwidth by setting $t_\mathrm{hop} \simeq t_\mathrm{batch}/\ell$.
If the available nodes were used optimally (this is a big if),
the bandwidth required through each node in this simplified case
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/