Bandwidth throttling (was Re: Padding)

[Roger Dingledine]

On Thu, Jul 04, 2002 at 12:27:43PM +0100, Andrei Serjantov wrote:
> > Ow. I don't know what Internet you live on, but this is a lot. :) For 50
> > nodes, that's 25 Megabits per second each way per node. I think we must
> > take a lesson from Freedom here, and look for less expensive approaches.
> 
> I was thinking about a small-scale case, say 5 routers which are basically
> uncompromised. So I think we are just talking about different things here.

With 5 routers, we're still looking at over 300 kilobytes per second
each way. Moria can handle this, but it would definitely be noticed on
the network. I would not be willing to put up a node with that level of
sustained traffic.

> Fine. But presumably all these cells are not just sent as fast as
> possible, are they? (This is the missing bit of your email, I expect)

Right. Give me some time to get the next mails written. But don't hold
your breath. :)

> > (We could have the flow control be connection-wide rather than for
> > individual circuits, but then we end up with DoS vulnerabilities a
> > la Pipenet.)
> 
> I don't understand this comment, please elaborate.

A connection is any tcp socket. So there are connections between ORs,
connections to web servers ("exit connections"), etc. A connection between
ORs is what Paul calls a thick-pipe. (A node is a computer that's running
our program. I call it node because as our program is currently written,
it can take the role of OR, OP, or both.) A circuit, on the other hand,
is a single conversation. So we multiplex circuits onto connections. (At
exit or AP connections, there is only one circuit associated with that
connection.)

So the idea under consideration (and ultimately to be thrown out)
is having a window for the entire connection (where the window is
decremented for every data packet sent over the connection, regardless
of which circuit it belongs to).

Now, how does a node decide when to stop sending sendme cells back?

Option one: anytime any window for any forward connection is zero,
we stop sending sendme cells backward. Unfortunately, any server can
now DoS the whole system, a la Pipenet. You do this by refusing to read
new cells from the network, so the nodes right behind you get congested,
and then the nodes behind them, etc. If a congested node refuses to read
any new data cells from anywhere, then the congestion quickly spreads
to the entire network, and the whole thing stalls.

Option two: if a window for a given n_connection is zero, then we stop
sending sendmes to any p_connection for which there is a circuit between
them. I like this option more, because it's harder for the adversary
to break the whole network. But he can still wreak havoc, for instance
by controlling two endpoints of a circuit, sending lots of data, and
refusing to read it. Thus the congestion will spread over the nodes
that he targeted for that circuit. He can then make new circuits with
new target nodes.

> > The adversary can observe some of the nodes, learn which ones are stalled,
> > and correlate circuits and thus bridge honest nodes. But simple packet
> > counting attacks will already bridge nodes.
> 
> What do you mean by stalled nodes?

A stalled node is one which doesn't want to read any more cells from its
p_connections, because it doesn't have permission from the n_connections
to write any more.

If we choose option two above, an adversary who controls nodes B and D in
a given path can intentionally stall node C. Since the stalling happens
connection-wide rather than circuit-wide, all circuits going from B to
C that will go on to D are now stalled. Thus he can learn which circuits
are taking the same path.

But my next realization was that if he owns B and D he can already just
watch data cells go from B to C, and look for corresponding patterns
(number and timing) of data cells going from C to D. With this approach,
unless we add multi-hop padding cells as Matej described in the other
mail, the adversary doesn't even need to stall connections. He can just
observe the traffic.

Make sense so far?

> > Traffic padding may foil passive adversaries, but not adversaries who
> > are part of the network. So with this lighter threat model, where we
> > don't worry about correlation attacks, we can afford to have the
> > granularity of per-circuit flow control.
> 
> Sorry, you really have to explain this.

It seems that doing flow control on a per-circuit basis leaks more
anonymity (because the adversary at D can stall specific circuits at C
until B notices that one is stalled -- so he can pinpoint exactly which
circuit is which).

But given that packet counting attacks work, it turns out we don't
have to worry about whether our flow control algorithms leak anonymity:
the adversary already has easier and more powerful attacks.

> > 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.
> 
> So even in the original OR design (+ OP -> OR padding) if the first node
> of a connection is compromised (i.e. the attacker knows how much traffic
> comes from the user) and the attacker can observe the entire network, the

He doesn't even need to observe the entire network. He just needs to
get lucky and own the exit node too. So if the adversary is curious
whether Alice is talking to Bob, and can take over the first OR Alice
chooses and happens to own the exit node she chooses (we call this attack
'traffic confirmation'), onion routing is totally broken. Of course,
the next step if he's trying to watch Alice is to go observe keystrokes,
monitor emissions, etc. Onion routing also does not address this.

> anonymity of that connection is compromised. I don't think we can do
> anything about that. (Mat, interestingly enough, we never thought of this
> when suggesting the OP -> OR padding idea). On the threat model question,
> I think we should not try to protect against compromised COR's (the
> above).  This is not as bad as it sounds -- the people who run COR's are
> nto the ones who run the network. Although this is definitely a
> significant reduction in security.

If we're not worried about compromised CORs, why are we making data
payloads look different at each hop? Isn't the link encryption enough?

Surely we're *sort of* worried about them. We really need to clarify this.

> Maybe you *can* do something about this, though.
> 
> Side note: I am actively thinking of dummies (although more for Mixmaster)
> and this may provide an anonymity protection scheme applicable for OR
> which is not too expensive.

Sounds good. Definitely lots of stuff to keep thinking about.

--Roger