(FWD) Re: Message splitting and Mixminion

[Roger Dingledine <arma@xxxxxxx>]

[Forwarding since Andrei isn't on the list. -RD]

----- Forwarded message from owner-mixminion-dev@xxxxxxxxxxxxx -----

Date: Tue, 7 Jun 2005 21:53:24 +0100
From: Andrei Serjantov <schnur@xxxxxxxxx>
Reply-To: Andrei Serjantov <schnur@xxxxxxxxx>
To: Nick Mathewson <nickm@xxxxxxxxxxxxx>, 
	Mixminion Developers <mixminion-dev@xxxxxxxxxxxxx>, schnur@xxxxxxxxx, 
	steven.murdoch@xxxxxxxxxxxx
Subject: Re: Message splitting and Mixminion

Nick,=20

Thanks for starting out thsi thread and apologies for the dealy in replying=
.

Against the GPA - quite right. A side point: in the paper Steven and I
assume the attacker is *already* able to distinguish between the 10x10
and 1x100 cases (as we assume that the sender sends his messages to
receivers as soon as he has them).

I think the way to fix it is to treat the total number of packets the
sender is about to send as one logical message. i.e. use the geometric
distribution whether or not you have 10x10 or 1x100. (it took me a
long time to come up with this solution, please check)

In our model, there is some probability that they are also mix as the
attacker might not observe enough traffic to distinguish the 100 vs
10. This is an interesting point and I decided to do some more work.

First, I ignored padding and took the following scenario: 100 messages
to send, 10 mixes, 9 of them watched by the attacker. First, I wanted
to solve the following problem: assuming a very simple geometric
distribuion, how many messages would the sender send to each mix?
This is not entirely trivial, but I came up with the following:

1.4050    1.9740    2.7735    3.8968    5.4750    7.6923   10.8077 =20
15.1849   21.3347   29.9753

rounded, it is:

     1     2     3     4     5     8    11    15    21    30

and the expectation (as expected!) is 10.

Now, this means that if the attacker watches 9 out of 10 nodes, then
on average the attacker will observe 90 messages (and hence the
100-packet message will be mixed with
a 90-packet one). Of course, a uniform sending policy would also yield
the same result (expected observation =3D 90 messages), but the variance
here is higher, I leave this argument aside for the moment.

In fact, there is enough here already, everyone must be bored.

BTW, can someone solve the following for x analytically, I am feeling stupi=
d!

\[
sum_{i=3D1}^{10} x^i =3D 100
\]

Thanks,

A.

On 6/4/05, Nick Mathewson <nickm@xxxxxxxxxxxxx> wrote:
> So everybody but Andrei and Steven should go read Andrei and Steven's
> paper before they read the rest of this message.
>=20
>    http://www.cl.cam.ac.uk/users/sjm217/papers/pet05msgsplit.pdf
>=20
> Done?  Good.
>=20
> So the basic idea is: against a certain kind of adversary, when
> sending a large number of packets to a recipient, it is better to send
> them over different paths.  Okay, great.  We already do that.  But
> another result is that it's better to choose the initial nodes
> according to a geometric distribution rather than a uniform
> distribution.  Otherwise, an attacker who is watching a single mix and
> sees you send 10 packets can guess that you are likely to be sending
> 10M packets total, where M is the number of mixes.  [If this makes no
> sense, read the paper.]
>=20
> The question is, should we do something like this with Mixminion?
>=20
> One reason that the answer isn't a straightforward "yes" is that the
> paper doesn't (if I understand Andrei correctly) address the case
> where an attacker is watching the sender.  If the attacker *is*
> watching the sender, then using the paper's recommended splitting
> algorithm can leak information.
>=20
> For example, suppose Alice sends 10 packets each to 10 recipients, and
> Bob sends 100 packets to 1 recipient.  Suppose they're observed by an
> attacker.  If they choose their entry mixes uniformly, then they look
> the same.  But if they do what the paper suggests, an attacker can
> tell them apart, and Alice provides less cover for Bob than before --
> not more.
>=20
> So, what's the right answer here?
>=20
> yours,
> --
> Nick Mathewson
>=20
>=20
>


----- End forwarded message -----