Re: Bandwidth throttling (was Re: Padding)

[Roger Dingledine <arma@mit.edu>]

On Mon, Jul 08, 2002 at 03:22:16AM -0400, Matej Pfajfar wrote:
> > The problem is that padding cells don't trigger rebroadcasts. So if
> > there's only one circuit open, the only people broadcasting will be
> > people who are part of that circuit.
> Hmmm - you're right. But can we not make padding cells trigger broadcasts 
> as well (again impose a cut-off point where we just pad the whole link to 
> make this scalable)?
> 
> I think that's still better than doing full-scale padding outright? What 

True. Basically, in this scenario what we want is for everybody to
broadcast whenever *anybody* broadcasts. I wonder how we could coordinate
this. It turns more into a DC-net like structure then.

An alternative here is to do quite a bit of padding when the network is
active, and less when it's not, as per the traffic shaping proposal. But
this is still different, because you're saying the traffic between two
*unused* nodes should increase when data cells are present anywhere on
the network. That's a nice idea. I wonder how it could be done.

Andrei, you said you wanted to do some analysis, right? Tell us how much
anonymity we lose with the various approaches. ;) (Or give us a shove
in the right direction, at least.)

> > Instead, when a new onion arrives and we're full of circuits, we should
> > choose the "most blocked circuit" and tear it down. We can choose this
> > by [...] "number of bytes queued but unwritable."
> Yes but what about genuine slow connections? I can also (alas this is much 

Genuine slow connections which are queuing a whole lot of bytes and
refusing to read them at the server *are* denial of service attacks. If
nobody's attacking us and we can handle the load, there's no problem. If
somebody's attacking us, and some legitimate connection is doing a
better job at DoSing us than the adversary, then I say we kill that
connection. :)

The denial of service worry is precisely than we will have our buffers too
full, so we should pick the connections which are making us most full, and
remove them. Are there any protocols in which an honest connection tries
to write lots of bits but the server won't read? (There may well be. Hm.)

> I agree in that dropping cells shifts the buffering problem to some other 
> "victim" but we can make the onion proxy do this and not bother the core 
> routing nodes?

I'm hoping that the time saved in not having to deal with reimplementing
tcp-over-streams will offset the problems we might have with strong
adversaries knocking out weak circuits. I guess we'll see down the road.

(Do you still think we should drop cells, or have the previous arguments
convinced you?)

> Yes that's a bitch. But even if you don't ocontrol any onion routers you 
> can still confirm the relationship between Alice and Bob by observing the 
> network for a longer period of time and corrleating the times of 
> connections.

Yep. Well, I think a broader statement to make is that people using these
anonymity networks really can't afford to send more than one message
to a given recipient. Having long-term-linkable "conversations" is not
a behavior that we can safely support now, either in onion routing or
in Mixminion.

> Again, with heavy traffic on the network you have to do this several times 
> to confirm the relationship with some certainty. In general, timing 
> attacks are a killer - do you think they are plausible attacks in 
> practice?

It depends who our adversary is. A global passive adversary is a very
strong adversary, and I think timing attacks will benefit him greatly.
Perhaps we should back off on our threat model?

> Your attack here is very plausible - but if a router wants to 
> destroy/corrupt a circuit going through it, it can simply refuse to 
> forward the data. We need some sort of redundancy for this. We'll probably 
> have to tackle this at some point down the line.

Stopping the circuit is an attack, yes. But I think these flooding attacks
(where any node in the circuit can inject an arbitrary number of cells)
are much scarier anonymity-wise.

> > Assuming we're pretty good at ordering Bobs based on suspicion, this sort
> > of attack is very effective. Can anybody improve on my attacks? Are they
> > attacks we're willing to live with?
> As yo usuggest below there are ways of dealing with the attacks - the 
> one that worries me is the simple "observe the connection times and 
> correlate" - how do other anonymity systems deal with that, if at all?

The long-term intersection attack is an open problem.

Said another way, no, there are no defenses. :(

We really need end-to-end dummy traffic, which is sent at regular
intervals regardless of whether Alice or Bob are online. Check out the
paper by Heinrich Langos on dummy traffic against long-term intersection
attacks (hopefully I'll have a link to it soon, from the pet2002.org
page). Basically, he proposes a dummy database to which you give
convincing-looking dummies before you go offline, and volunteers pull
down messages and send them for you while you're gone. It's got a long
way before it's a reasonable design, unfortunately.

I was muttering something to Paul and Andrei at the workshop about a
p2p design that does the same thing without any centralized db, but I
think we got sidetracked at some point.

> I like this approach. But I don't think it would work for long-range dummy 
> cells - the first node in the circuit can still just drop the bad-hash 
> cells. Since they come from the onion proxy which is unlikely to corrupt 
> its own data stream, it can assume that they are all dummy padding.

No, the hashes work out correctly (and thus those data cells are
indistinguishable from real data cells), up to the point in the path
where the hash is incorrect. That node, if it's honest, drops the cell.
We can make all hashes from that point onward incorrect, so the first
honest node drops the cell.

> With regards to return data - 
> Dummy cells :
> I think we can tell each node how to generate dummy cells (embed this in 
> the onion) - the other nodes won't be able to recognize them and they will 
> get forwarded all the way to the onion proxy (which will discard them) but 
> this isn't much of a problem. It will still prevent other nodes (with the 
> exception of the exit node) from learning the true number of cells being 
> transmitted. The nly way to beat this is to control all the nodes in a 
> circuit, which is a killer anyway.

Ah! So the idea isn't to have the exit node instruct some of its data
cells to be dropped along the circuit on the way back, but instead to
have each node in the circuit randomly choose to *add* cells, which the
onion proxy can recognize as dummies.

Yes, that's very good.

(Except for that whole hash thing. ;) But as argued in my mail about
tagging attacks, perhaps hashes are less necessary for the return path.)

--Roger