Bandwidth throttling (was Re: Padding)

[Roger Dingledine]

On Thu, Jul 04, 2002 at 05:04:17AM -0400, Matej Pfajfar wrote:
> An interesting solution that I read in some paper (and I need to find out 
> which!) is this: when a node receives a cell destined to go over one of 
> its longstanding connections - it transmits the cell and also sends a 
> single padding cell on all of the other longstanding connections it is 
> adjacent to. No other padding.

I like this idea. It sounds very appealing. We should think about it some
more.

For instance: Imagine you're on a network that has no traffic. The
adversary is passively watching much of the network. Suddenly a request
arrives at a node, and it broadcasts with horizon one. Then a nearby
node broadcasts with horizon one. Then a node beyond that broadcasts
with horizon one.

So it seems that for a very lightly loaded network, this approach doesn't
buy you the anonymity you want. And since the amount of padding scales
linearly with load, this approach becomes less desirable at high loads. At
some point (and I don't know when), it becomes cheaper to just do traffic
shaping or link padding.

> > A) To prevent too many data cells from coming in to a node, we introduce
> > 'sendme' cells for flow control. Each circuit has a window parameter at
> > each hop, which is the number of data cells it's allowed to send. If
> > the circuit's window reaches 0, it stops sending data cells. When a
> > sendme cell arrives, the window is incremented by a value specified in
> > the payload of the sendme.
> Yes that's the sort of idea I had with ACK/NACK cells - but there is no 
> provision for discarding cells. I think we need to be able to drop cells
> (at each node, in whichever way we like) to protect against DoS. In this 
> idea, a node can't drop a cell once it has received it because it isn't 
> being buffered anywhere else. So should we not consider end-to-end (OP -> 
> COR_last) flow control?

I don't think dropping cells solves our problem. If you are going to have
to drop the cell, then you shouldn't be reading it in the first place. If
we allow dropping cells, then we must buffer it at the previous hop -- so
we've got a very similar problem there. So to answer your above question,
I don't think that "we need to be able to drop cells to protect against
DoS" -- I think my design about protects against DoS. So we want to start
looking at other parameters like throughput, latency, how easy it is to
code, etc.

Invoking the term "end-to-end" is very good for your argument, since
we computer scientists have been trained to believe that end-to-end is
always the right approach. :) I'll have to consider this one some more.

> > Now, an aside before we get too much further: is there really anything
> > we can do against the active (node-owning) adversary? Perhaps, if we
> > introduce dummy traffic that looks legitimate to some nodes in the
> > circuit. Paul, can you elaborate on this more? In any case, I'm scared
> > to death of DoS, so this is it for now.
> OK, I need some more help with this - are you worried about an active 
> adversary discovering the bandwidth of individual circuits?
> A way of preventing this (just a quick idea, not thought about this) is to 
> introduce another 
> "command" field to the cell. A node will forward all non-padding cells 
> unless the new field matches some certain value (which we could put in the 
> onion). It will also replace the field with a new value for the next hop 
> (also contained in the onion). The OP could then introduce random dummy 
> traffic which only some nodes would recognize as dummy. 

Seems reasonable.

Could somebody take a stab at describing our threat model please? I
know I've read a bunch of onion routing papers, but for some reason it's
never quite sunk in. I guess I can't comprehend why we would assume our
adversary is really good at some things and really bad at others. :)

--Roger