[freehaven-cvs] check in an initial scattered skeletal outline

[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

Added Files:
	sync-batching.tex 
Log Message:
check in an initial scattered skeletal outline


--- NEW FILE: sync-batching.tex ---

\documentclass{llncs}

\usepackage{url}
\usepackage{amsmath}

\renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\XXXX[1]{{\small\bf [XXXX #1]}}

\newenvironment{tightlist}{\begin{list}{$\bullet$}{
  \setlength{\itemsep}{0mm}
    \setlength{\parsep}{0mm}
    %  \setlength{\labelsep}{0mm}
    %  \setlength{\labelwidth}{0mm}
    %  \setlength{\topsep}{0mm}
    }}{\end{list}}

\begin{document}
\title{Improved Anonymity via Synchronous Batching}
% need a better title

\author{Roger Dingledine\inst{1} and Vitaly Shmatikov\inst{2} and Paul Syverson\inst{3}}
\institute{The Free Haven Project, \email{arma@freehaven.net} \and
Vitaly's affiliation \and
Naval Research Lab, \email{syverson@itd.nrl.navy.mil}}

\maketitle
\centerline{\LARGE\bf *DRAFT* --- not for publication}
%======================================================================
\begin{abstract}

\end{abstract}
%======================================================================
\section{Introduction}
\label{sec:intro}

Modern deployed mix networks, including Mixmaster \cite{mixmaster} and
its successor Mixminion \cite{minion-design}, are subject to partitioning
attacks: a passive adversary can observe the network until a target
message happens to stand out from the others \cite{disad-free-routes},
and an active adversary can manipulate the network to separate one
message from the others via blending attacks \cite{trickle02}.

Berthold et al argue in \cite{disad-free-routes} that partitioning
opportunities arise because the networks use a \emph{free-route} topology:
one where the sender can choose the mixes that make up her message's
path. They suggest instead a \emph{cascade} topology, where all senders
use the same fixed path through the mix network.

Here we argue that topology is not the issue. We investigate a strategy
called \emph{synchronous batching}, which provides the following
advantages over Mixminion:

\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 makes blending attacks harder 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.
* the one-to-a-sender ticket schemes can work

\end{tightlist}

We investigate using synchronous batching in three topologies: cascade,
restricted-route matrix, and free-route. We find that the restricted-route
matrix topology provides the highest expected anonymity of these three.

%Specifically, whereas
%with \emph{asynchronous batching} strategies each message is forwarded
%through the network based on local decisions at each mix, in a synchronous
%batching design, each batch of messages enters the mix network together,
%and the messages proceed in lock step 


\section{Synchronous batching}

A mix-net design groups messages into batches and chooses paths; the
approaches it uses 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
leaving the network, other than that the maximum time between them is
equal to the maximum network latency.

This ideal is not achieved by protocols like Mixminion that use locally
chosen 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$.
% This is handwaving, and the problem is more that the distribution
% isn't uniform rather than the actual size of the anonymity set.
%In principle, the maximum latency for a message that has just been
%sent 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, for example, then so does the probability that
%a message that is leaving the network could have been sent that long
%ago.

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 described in Section 4 of \cite{disad-free-routes}. (See
Section \ref{subsec:disad} below.)

Here we present a strategy called {\em synchronous batching}. This
approach seems to prevent these attacks even when free routes are used,
and seems to improve the trade-off between latency and anonymity.

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
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
no messages are dropped, the messages introduced in a given batch will
progress through their routes in lock-step, and will all be transmitted
to their final destinations $\ell$ hop periods later. Each subheader of a
message specifies the hop period in which it must be received, so that it
cannot be delayed by an attacker (which would be fatal for this design).
%[[Explain why this prevents the attacks in [disad-free-routes], even
%for free-route networks. Also explain why we need to use a hybrid
%free-route/cascade approach (otherwise the anonymity set is limited by
%the bandwidth that can be handled by a single cascade).]]

The set of messages sent to a node in a given hop period is called a
mini-batch, to distinguish it from the set of messages being sent
through the network as a whole. [[need better name?]]

Define the {\em width} $w$ of a mix network 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.)

An important constraint on the network structure is the maximum
bandwidth (traffic in unit time) through any given node.
Assume that sending a message over a single hop consumes a fixed
amount of network traffic; we can then use that as the unit for
traffic.

The latency is between $\ell t_\mathrm{hop}$ and $t_\mathrm{batch} +
\ell t_\mathrm{hop}$, depending on when the message is submitted.
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
$\ell$.

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
will be $\frac{T_{batch}}{wt_{hop}} = \frac{nT_{batch}}{wt_{batch}}$.

mix-acc review

\section{Related work}

\subsection{The disadvantages of free MIX routes}
\label{subsec:disad}

\subsection{Blending attacks}

\subsection{Mixminion}

\subsection{S-G mixes}

\subsection{Robust mixes}
flash

\section{Scenarios}

\section{Graphs and Analysis}

\section{Extensions and Future Work}

In practice, several considerations have to be balanced when choosing
a batching strategy and network structure. These include maximizing
anonymity sets (both batch sizes through each node and the overall
anonymity sets of users); bandwidth considerations; reliability;
enabling users to choose nodes that they trust; and interactions with
the reputation system.

Further analysis of the trade-offs will be needed before choosing a
final network structure. Note that a planned structure, where each
users' software follows the plan consistently when constructing
routes, will generally be able to achieve stronger and more easily
analysed security properties than less constrained approaches.

Possible extension: Note that synchronous batching does not necessarily
mean a "one latency fits all" approach. People who want a larger anonymity
set can agree to send their messages only at intervals of k*t_batch,
so those batches will have more messages (but at the expense of the
other batches).

Possible extension: for the purpose of discussion, let's use
t_batch = 3 hours and t_hop = 1 hour / n. Then the latency is between
1 and 4 hours, and the anonymity set is the set of messages sent in a
3 hour period.

We can improve this by having a "delay until next batch" option in
the message subheader; that would delay the message by t_batch and
re-introduce it at the same point in the path. If each message is either
delayed once or not delayed, that gives us a latency of 1 to 4 hours for
non-delayed messages, 4 to 7 hours for delayed messages, and a 6-hour
anonymity set (unless the attacker knows that someone never sends or
receives delayed messages, in which case the anonymity set for those
users is still 3 hours).

Can anyone attack the "delay until next batch" option? I don't think
the fact that those messages can be distinguished by the node is any
more harmful than Mixminion's "swap" operation, etc. [It seems a bit
more harmful: in Mixminion, all messages have a swap point somewhere in
the path. In this scheme, messages that ask to be delayed are inherently
more interesting. -RD]

A generalisation of this is a "source-timed" network: use the timing model
from \cite{mix-acc} (with or without receipts), where t_hop corresponds
to one time unit, but in each subheader specify "drop if not received in
period t1" and "send in period t2".

Even more general would be "drop if not received between t1_start and
t1_end" and "send between t2_start and t2_end, chosen uniformly at random".
This can support almost all batching designs.

%\section*{Acknowledgements}

%======================================================================

\bibliographystyle{plain}
\bibliography{sync-batching}

\end{document}


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