Batching Strategy and Network Structure

[Roger Dingledine <arma@mit.edu>]

[George: you should read this and give your opinion, even though you're
busy. :) ]
[Len: I've got a couple questions in here for you. Search for Len.]

David Hopwood just committed a very controversial subsec to the paper. I'm
going to bring the thread over to the -dev list so we can try to hash
it out farther.

>\subsection{Batching Strategy and Network Structure}
>\label{subsec:batching}
>
>% This needs more work. I hadn't realised how close we were to the
>% deadline, but I'll commit it anyway for now. -DH
>
>Ideal security for a MIX-net is achieved when each message leaving the
>network, could correspond to any message entering the network during a
>period approximately equal to the maximum network latency, and vice-versa.

An alternate ideal is when each message leaving the network could
correspond to any message that ever entered the network. How do you
decide which ideal is better?

This is something that needs more research; but I'm not sure we've got
the space in the mixminion paper, or that the mixminion paper is the
right place for an in-depth analysis. So I'm tempted to try to scale
this subsec back to a "discussion and current thoughts" rather than
"this is our plan" or even "this is our recommendation".

[Also, this topic overlaps in part with another paper I'm writing with
Andrei Serjantov and Paul Syverson, on working out a taxonomy of various
batching and pooling strategies and how well each resists trickle/flooding
attacks. But from the looks of it it doesn't overlap that far.]

>This ideal is not achieved by protocols like Mixmaster that use random
>delays [[explain why]].
>If such networks also use free routes, they are subject to attacks
>described in \cite{disad-free-routes}. [[summarize them]]

They're also subject to flooding/trickle attacks, where an attacker
targeting a specific message going into a mix can manipulate the batch
of messages entering that mix so the only unknown message in the batch
is the target message.

In fact, I'll paste a couple more paragraphs I wrote yesterday about
this:

|The tools that we give honest MIXes to protect against these blending
|attacks are precisely the tools that dishonest MIXes use to launch
|them. \emph{Uncertainty} comes from not letting observers know when
|a given message might leave the MIX; \emph{inexactness} comes from
|not letting observers know how many messages are currently inside the
|MIX. This flexibility allows a MIX to prevent the adversary from learning
|the details of message flow, but at the same time it allows a compromised
|MIX to manipulate message flow, for example by delaying a message until
|it's ready to launch a trickle attack on the downstream hop. 
|
|Many basic MIX verification schemes, such as that proposed in
|\cite{chaum81untraceable} where senders observe the batches exiting
|a MIX to confirm it processed their messages, require schemes where
|the messages come out with the next MIX flush. More complex
|robustness schemes \cite{flash-mix} enforce timely message processing
|if the adversary does not own a threshold of participating MIXes. The
|receipt and witness scheme of \cite{mix-acc} works because a MIX loses
|reputation if it hasn't obtained a receipt from the next hop within
|the allowed timeframe. All of these systems are designed to ensure that
|messages will leave each MIX predictably.
|
|In some topologies, such as free-route MIX-nets, a widespread delaying
|attack is difficult to perform because the adversary must control all
|MIXes that are sending messages to the target MIX. In this case we may
|gain more by allowing MIXes to protect against blending attacks than we
|lose by permitting compromised nodes to manipulate messages. At the other
|extreme, in a cascade topology, a single compromised MIX has absolute
|control over the downstream message batch. In this case verification of
|correct processing is critical, to prevent wholescale (unobservable!)
|anonymity compromise. Methods to detect an attack afterwards, e.g. by
|checking for successful delivery of test messages at the end of the
|cascade \cite{casc-rep}, can help detect misbehaving MIXes --- but they
|still allow the adversary to uncover a few messages before he's noticed.
|As we design new protocols and batching approaches, we must consider
|this tradeoff between protection from blending attacks and protection
|from verifiability.

The work on evaluating resistance to the $n-1$ attack came in part out of
the work done for pet2002 on an information-theoretic model for anonymity:
Andrei and George had a paper there showing that pool mixes provide
'more' anonymity than threshold mixes (under some plausible assumptions).

So I think there's a tension between hiding message flow (with pools)
and ensure predictable message flow. I haven't made a decision yet which
way I stand.

>To both maximize anonymity sets and prevent the above attacks, we
>propose to use a strategy called {\em synchronous batching}.
>The network has a fixed {\em batch period}, $t_{batch}$, which is closely
>related to the maximum desired latency; a typical value could be 24 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 $n$ 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 $n$
>hop periods later.

This is a very tempting idea. It resolves a lot of the
diverse-user-behavior problems. On the other hand, it puts a lower
bound on the performance we're going to get from the system. So we need
to run it by the remailer folks: Len? What do you think about having
all messages always take n days to traverse the mixnet? It reduces the
number of actual users we'll get (possibly by a whole lot), and it may
kill deployment. Even though we talk about having the best known designs
against traffic analysis, we have to moderate that with choosing a design
that people will actually use.

Hm.

>The latency is between $nt_{hop}$ and $t_{batch} + nt_{hop}$, depending
>on when the message was submitted.
>
>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?]]
>
>[[Messages are tied to a given time period so that they cannot be delayed.
>Explain why this prevents the attacks in [disad-free-routes], even
>for free-route networks.

I'd be curious to see the explanation for this one. The attacks in
disad-free-routes are really nasty when there are fixed-length paths
and the adversary owns most of the nodes.

> 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).]]

There are lots of tradeoffs in both directions between free-route
and cascade. Another big one is that link padding at an O(n) scale
(e.g. cascade) is plausible, but at an O(n^2) scale (eg free-route)
is nuts.

>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.
>
>Let $T_{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_{hop} \simeq t_{batch}/n$.
>
>%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}}$.
>
>For any particular network structure, bandwidth constraints, and
>assumed traffic levels, it is straightforward to calculate the
>minimum width of the network, and therefore the maximum sizes of
>mini-batches.
>
>For example in the limiting case $w = 1$, the network consists of a
>single MIX cascade (this is the situation considered in Section ??
>of \cite{babel}).
>
>Let $N$ be the number of nodes in the network. An interesting case
>is $w = n = N$; in that case we could use a set of $N$ cascades
>arranged as a Latin square.\footnote{[[define Latin square]]}
>This ensures that all nodes make full use of the available bandwidth;
>however it gives users no choice in the set of nodes used.
>
>In practice, there are other considerations beside maximizing the
>size of mini-batches:
>
>\begin{enumerate}
>\item reliability

I think this is going to be the killer. If we want to impose a structure
on the messages and MIX-net topology it's got to be based on reliability
so we can arrange appropriate redundancy and node grouping. It's going
to be really hard. It would be a nice thing to investigate once we've
got Mixminion going -- so then we can start trying out new things like
reputation systems and alternate network topologies.

>\item giving users a choice of node sets?
>\item anything else?
>\end{enumerate}
>
>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.

Agreed.

--Roger