Re: Batching Strategy and Network Structure

[David Hopwood <david.hopwood@zetnet.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----

Roger Dingledine wrote:
> >\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.

That's unachievable unless the maximum latency is the lifetime of the
MIX-net so far, in which case it's the same. The above is the best
achievable ideal - note that it says *maximum* network latency (over
all messages that eventually get through the network).

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.

George wrote:
| I think that anonymity is not about messages themselves but about their 
| metadata. Therefore I would say that perfect anonymity is achieved when a 
| message received by a principal is equally likely to have been sent by any 
| other principal in the universe (maybe we should restrict that to: that 
| uses mixminion).

The definition in terms of messages implies the definition in terms
of metadata, I think. Also, if metadata includes timing, then a
(sender, time-sent) pair effectively determines a message, or a small
set of messages.

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

We need to discuss this in the paper because it affects everything else.
For example, with synchronous batching the position of a message on the
route is not secret, and that has implications for whether length hiding
is needed, and how we do replies.

So, I'd like to include some discussion of batching even if it's rather
incomplete. (This is "only" the peer-review version of the paper, right?)

> 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".

OK, I've no problem with that. I knew it would be controversial :-)

> [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.

All designs are subject to that attack, I think. It's mitigated by
preventing messages from being delayed: in that case, an attacker cannot
reintroduce the messages that it removed, it has to permanently trash
everyone's messages that are not in the trickle, and this will hopefully
be noticed. It can only be noticed after the fact, but I don't see how
to do better (at least not without impractical assumptions, like
assuming that all users can see and check all intermediate messages).

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

That's another reason to prevent messages from being delayed.

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

This is very good, I agree completely.

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

I'll have to think about that, but I suspect that pools don't really help
much against an attacker who can "blend" several consecutive (mini-)batches.

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

Exactly - it makes it easy to enforce that all information used to decide
how the route is chosen is up-to-date. For example:

 - the client asks the first hop what the current batch period is (client
   clocks are often way out, but nodes can be assumed to have the correct
   time). If the client's meta-info is out of date, it is updated (possibly
   authenticated by a threshold signature).

 - if the first hop lies about the time, then the message will just be
   dropped at the first honest node.

> On the other hand, it puts a lower
> bound on the performance we're going to get from the system.

[ITYM lower bound on latency, upper bound on performance.]

> 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?

t_batch + n*t_hop < 2*t_batch, not n*t_batch. That's the whole point:
t_hop can be much smaller than t_batch, but the anonymity set is
determined by the network throughput over t_batch.

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

Len wrote:
| Also, "ideal" for anonymity may be infeasible if it makes the system too
| inefficient for its users. If people have to wait more than a few hours
| for their messages to clear the system, they will most likely not use the
| remailer network.

OK, 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 hop
header; 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 "swap", etc.

A generalisation of this is a "source-timed" network: use the timing model
from the mix-acc paper (with or without receipts), where t_hop corresponds
to one time unit, but in each hop header 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.

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

George wrote:
| Hm. I quite like mixing strategies that are adaptive to the volume of 
| traffic so that if there are enough messages to build good anonymity sets 
| you do not need to wait 10 days.

We can easily use a longer term adaptive approach that uses information
from previous batch periods to determine the current period's strategy.

I *don't* like strategies that rely on more immediate feedback than that:
they give an attacker more opportunities to try to manipulate the strategy.

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

OK. Here's a summary of the attacks from Section 4 of [disad-free-routes]:

=====
# Section 4.2
# Position in MIX route. Based on our attacker model, each user should be
# anonymous, even if his messages only pass one trustworthy MIX. In a MIX
# network a certain MIX may be on different positions on the individual
# routes of the messages he receives. In comparison a MIX of a cascade
# will always have the same position because the route is static as long
# as the cascade exists. The question is: is a MIX of a MIX network able
# to detect his position in a route of a certain message

Yes, but this is not a problem in itself.

# and if so, can he use this knowledge to partition the input batch?

No.
The following statement is still true:

# Eventually, a message is only unobservable in that group of messages
# which have this MIX on the same routing position.

but in the synchronous design, that's not a problem because this group
is large (if only one MIX is trustworthy, 1/w of all messages in the
batch, which is what it would be anyway).

# Conclusion: If only one MIX of a route is trustworthy, then the achievable
# anonymity is distinctly lower in a MIX network compared to a synchronously
# working MIX cascade.

The conclusion should actually be, "If only one MIX of a route is
trustworthy, then the achievable anonymity is distinctly lower in an
asynchronous MIX-net than in a synchronous MIX-net (whether it uses
free routes or cascades).

# Determining the next MIX. The previous section describes an attack
# which is especially successful, if the users select different
# routes for each message. Now we want to explain an attack, which
# could be done, if the users send all messages using the same
# individual route.
# A trustworthy MIX of a MIX network receives messages sent by users
# and other MIXes. The MIX forwards these messages either to users
# or to other MIXes.

A synchronous network is more like a cascade in this respect: apart
from the last hop, messages are always forwarded to other MIXes.

# An attacker knows the senders of all messages, which came directly
# from users. Additionally, he knows all senders of messages which
# passed only attacking MIXes.
# Because a MIX forwards the messages only to some other MIXes or
# users, only they could be possible receivers of an incoming message.
# If there are only a few trustworthy MIXes, only those users which
# are connected by the described graph, are members of the anonymity
# group of a received message.
# If the users send their messages, using always the same route, an
# attacker only needs to observe a trustworthy MIX at those times,
# when this MIX forwards a message of a sender the attacker is
# interested in. A MIX network doesn't work synchronously, so the
# batches always generate different anonymity groups.

Again, the important property is whether the network is synchronous,
not whether it uses free routes. Fixed-free-route designs do have
potential attacks that random-free-route designs don't (for example,
the route can be revealed by a tagging attack unless tagging is
*completely* prevented), but they're not vulnerable to the specific
attack described in the paper.

# 4.3 Probability of Unobservability
# If we use a MIX cascade, then we optimize for the case that only
# one MIX is trustworthy. Based on the functionality of each MIX,
# also in this case the transported messages are unobservable, at
# least if no active attacks occur. In the following section, we
# calculate the probability, that at least one MIX of a randomly
# selected route of a MIX network is trustworthy.

The analysis in this section is valid, and is one reason why I suggest
a hybrid approach: the cascade part of the route ensures that the
probability of at least one MIX being trustworthy is at least as high
as it would be for a simple cascade.

(Of course this requires longer routes, but the latency doesn't
need to be much larger, since that depends mainly on the batch period,
not the hop period.)

# 4.4 Active Attacks
# [stuff about message blocking attacks being very dangerous]
# There exist several different basic approaches for the MIX cascade,
# in order to solve this problem.
# Users verifying the MIXes. In this case all messages a MIX receives
# are sent to all users. So each user can check that his message has
# arrived at the MIX. If that's true, he sends an acknowledgement to
# the MIX. The MIX forwards the batch only to the following MIX, if he
# receives these acknowledgements from all users.

This is very similar to the "public ledger" approach in early drafts
of mix-acc, and is just as impractical. The more practical receipt
approach *can* be used with synchronous batching (as I said above,
mix-acc works without modification, with t_hop as the time unit).

Receipts don't allow detecting a "blending" attack until after it
has succeeded. But I don't think the approach being suggested by
the paper for cascades is feasible at all, so even if there are more
problems applying it to free routes, that shouldn't be considered a
disadvantage.

Also the following part of the analysis doesn't apply if, for example,
we are using end-to-end receipts:

# - A MIX network doesn't work synchronically, so the user has to
#   decide, if his message has been blocked or if it only arrived late
#   for being processed in the current batch. A successful attack could
#   be to delay n - 1 messages for one batch.

The synchronous batch design does work synchronously, and it causes
delayed messages to be dropped. So either the end-to-end receipt will
be received at a known time, or it will never be received.

# Ticket-method. A new idea developed by our group is, that the MIX
# only accepts messages which come verifiabl[y] from the group of
# registered participants. Each registered participant gets exactly
# one ticket from every MIX, which is only valid for a certain batch.
# If a MIX processes a batch, he verifies, that every message contains
# such a valid ticket. Because each participant gets only one ticket
# for each batch, he can only send one message. So the attacker could
# only generate as many messages as the number of users he controls.
# A MIX couldn't link a ticket to the belonging user, because we use
# blind signatures. The whole procedure is explained in detail in [2]
# (contained in this book).

([2] is [web-mix], i.e. <http://vip.poly.edu/mehdi/papers/00668973.pdf>.)

I'm not convinced that it's reasonable to assume that attackers can
be excluded from being registered (in an open network), but let's
suppose that it is.

# This procedure is only badly applicable in a MIX network, because:
# - The user has to request tickets from every MIX in the world,
#   whereas in a cascade, the user only has to request tickets from
#   each MIX in the cascade he/she intends to use.

This is a false comparison: in either case, if MIXes are chosen from
a set S, then the user has to request tickets from all MIXes in S.
The fact that S *can* be chosen to be larger for a free-routed network
shouldn't be considered a disadvantage. Note that the maximum size of
anonymity sets for that user increases as S increases.

# - The user doesn't know exactly, which batch will contain his message.
#   [...]

This is not correct for synchronous batching.

# - And finally only a part of these ticket would be used so that a
#   MIX could only ensure, that no additional messages sent by an
#   attacker would be processed. But the attacker could decrease the
#   anonymity group by blocking some messages. in the cascade, the
#   number of tickets issued could exactly match the batch size.

That's true, but one possibility is to choose a random ordering of
a fixed set of MIXes (this increases the anonymity set in much the
same way as an unconstrained free route, but still allows clients
to be issued with exactly the right number of tickets).
=====

That's all the attacks in the paper.

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

What I was thinking of was:
  random secret free-route -> one of $w$ cascades -> random secret free-route.

That way you guarantee security at least as good as a cascade, but the
anonymity set is determined by the throughput of the network rather than
the throughput of a single cascade. I'm not sure that link padding is
really very important, anyway (although it could still be done for the
cascade part).

The optimal structure depends a lot on how the available bandwidth
constrains the actual width. (I did some back-of-the-envelope
calculations that suggested even a single cascade could handle the
current traffic through cypherpunks and Mixmaster, but I can't find
those notes, and I'd better post this now.)

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

If that's what we're going to do, then we should try to make the protocol
quite general, e.g. by implementing source-timing and several possible
ways of doing replies, decided by the hop header (which is always
non-malleable). Then we can experiment with different batching techniques
just by changing clients, not nodes or the protocol itself. As long as
the options that are actually used are constrained, the only difference
this makes is that the attacker can introduce messages that don't follow
the preferred batching technique. This probably doesn't make much
difference: at least for interval batching, adding messages should never
reduce the anonymity sets of the other messages.

Later we could simplify the protocol depending on the batching approach
we decide to use, in case the extra generality could enable any attacks.

> >\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.

Good. I'll try to clean up the batching section by, say, 20:00 UTC
today (Tuesday).

- -- 
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPNdrxzkCAxeYt5gVAQF3lwf/Woyb8leCDey8OPiTxXaiF+4/us2iy+sU
meUsIpZjfSoRQVkMKSg2Ql7q1XKudVrJb33nBFhX2MizJ9ef81CNdksDcZQYvJ+q
SxuHFUoz9w0uC10N89xq7BtxwolUXTfc0I7Q71ha/PTG2W+a3FADns4LhYnbV5ei
SG8GIAx4Emy8GyI7c2p13We0jdLXWxkCFNrMkpP11K7KMj0gKA6MjGivG/LbiEy6
EFxHecMYkrsYi/5dcVu3MNhwroHJzMXpAI+HGh+dB1W1/VzJSuM18KfTjr8657xl
SPk1kbXScD4Z9VrShrcPn1UmwPerP9uaELDS0ni4/DrOpagjLXs1rQ==
=YY50
-----END PGP SIGNATURE-----