Bandwidth throttling (was Re: Padding)

[Andrei Serjantov]

Hi,

Paul: I both liked and hated your email!

Sorry for the long discussion which follows. Shout if you don't
understand.

Yes, we need to think about weakening the threat model because without
analysing any of the proposed solutions quantitatively and carefully, we
cannot make any claims. Let me, however, have a go at describing a few
threat models and attacks which we know about so far. Maybe we can then
settle on an acceptable one.

Threat Models:
--------------

1)(A/P) Global Passive Adversary + a few compromised COR's

This is the model which, I think we use for Mixmaster and other email
anonymity systems.

2)Active/Passive (A/P) Global Passive Adversary

Active means he can delay traffic so as to mount timing attacks. These
attacks need careful analysis, but we expect them to be *strong*.

3)(A/P) Traffic Confirming Attacker who sees *all* OP -> COR and COR ->
recipient links.

Traffic confirming attackers see no COR -> COR links.

4)(A/P) Traffic Confirming Attacker who sees *some* OP -> COR and COR ->
recipient links.

4.5) Same as 4, but the attacker can change the links which he can see.

5)Roving Adversary (as before)

I agree with Paul's argument above that the connections are too
short-lived for anyone to compromise COR's while the connection is up.

-------------------------------------------------------------------------
If we assume Local COR configuration (the attacker has no access to the OP
-> COR link, even if any of the above threat models say he does!), then
the (A/P) traffic confirming attackers cannot do anything.

If assume remote COR config, but pad OP -> COR link to a small constant
bandwidth (which I find vaguely acceptable), and do assume that the
attacker can see it (the link), then the passive attackers 3,4 get
nothing, the active attackers get a chance of performing the timing attack
(eg.  active CREATE/DESTROY issues discussed previously or the attacks
described by Paul). This is interesting to investigate and as Paul says
hard to protect against (although we have a starting point).

However, allowing the attackers access to the OP -> COR link also allows
tagging attacks (only for active attackers, naturally) which we discussed
before. I don't think there was a proposed solution to those in the case
of backward connections (when *en*cryption is done). Oh, Dear! And this is
all "end to end" attacks.

If we do not pad OP -> COR link, there is a weaker passive CREATE/DESTROY
attack, and basic cell counting provides traffic confirmation. So we are
vulnerable to Passive 3,4. Should we go any weaker that 3,4?????

Let us now move to a Global Passive Adversary. I think that if we allow
the attacker to see the bandwidth on each COR -> COR link, the anonymity
of a low-load network becomes non-existent as there would not be enough
mixing. Side remark: Full impractical n^2 padding would provide much more
anonymity as you basically guarantee that each connection gets mixed with
each other one passing through at the same time (provided timing attack
protection).

Global active adversary gets more powerful versions of the timing attacks
mentioned above -- he can bridge each COR one by one and the only way of
protecting against that would be to delay packets which we want to do not
do as this would ruin usability. Grrrrr.

So the questions here are:

* Does allowing the attacker to see COR -> COR bandwidth in the
high-volume case yield new attacks?

* Is it worth padding for the low-volume case?

Let us now move on to 1), the most powerful attacker. Long range OP ->>>
COR's padding is now required, we do not know how to do this properly yet
(although suggestions have been flying about) and it needs to be analysed.
Otherwise, 1st and last compromised COR destroys anonymity.

I think this all summarises our knowledge of the attacks grouped into my
arbitrary categories of attackers. We could have more categories...

I spent a while thinking about and writing this, so would appreciate some
feedback! Even if it's "Rubbish!".

Thanks,

A.

------------------
Andrei Serjantov
Queens' College
Cambridge CB3 9ET
http://www.cl.cam.ac.uk/~aas23/