Re: Proposal: Avoiding infinite length circuits

[Paul Syverson <syverson@xxxxxxxxxxxxxxxx>]

On Tue, Dec 02, 2008 at 03:16:45PM -0500, Roger Dingledine wrote:
> On Tue, Mar 13, 2007 at 11:15:47PM -0400, Roger Dingledine wrote:
> >   Right now, an attacker can add load to the Tor network by extending a
> >   circuit an arbitrary number of times. Every cell that goes down the
> >   circuit then adds N times that amount of load in overall bandwidth
> >   use. This vulnerability arises because servers don't know their position
> >   on the path, so they can't tell how many nodes there are before them
> >   on the path.
> > 
> >   We propose a new set of relay cells that are distinguishable by
> >   intermediate hops as permitting extend cells. This approach will allow
> >   us to put an upper bound on circuit length relative to the number of
> >   colluding adversary nodes; but there are some downsides too.
> 
> In talking to Peter Eckersley, he discovered a variation on this attack
> that our defense doesn't cover.
> 
> Our defense is to let intermediate relays count how many extend operations
> could have happened after them on the circuit, and that way we can limit
> circuit lengths to (say) 8 hops.
> 
> But what if the attacker builds an 8-hop Tor circuit, and then exits to
> a Tor entry guard and pretends that it's a Tor client? At that point it
> can talk Tor-inside-Tor and build eight more hops. Then repeat.
> 
Right. I didn't think the proposal was ever meant to cover that.
What it does is prevent simple indefinite iterative extensions.
More clever ways of building long circuits will always be available
without more complicated protections (and maybe even then).


> Peter suggested one way to defend against it would be a latency test --
> if you're too slow at answering an extend cell, then we assume we're
> being tricked. That seems very brittle though.
> 
> Another approach would be to refuse exits to known Tor server IP:ports.
> That's also not a complete solution, since a) there is a slight time
> lag between when a new relay goes online and when the other relays know
> about it, b) we want to one day make it so each relay doesn't need the
> complete list of other relays, and c) there are other open proxies out
> there (or heck, Tor bridge relays) that can be used as glue between
> attacker circuits.
> 
It may be brittle, but if you are really worried about DoS from this
attack then I think you are stuck with Peter's suggestion, or in any
case something other than what you propose. Given that things (1) not
costing the attacker resources and (2) able to open circuits through
the Tor network, are available---as in your (c)---you will not be able
to prevent indefinite extensions by using anything involving checking
whether a new circuit request is going between known Tor nodes, on
either the exit side (as above) or the entrance side (as below).


> (The flip side of this approach would be to instead refuse incoming TLS
> connections from IP addresses that have a Tor relay running, if the TLS
> connection doesn't provide a cert saying it's really the relay connecting
> to you. I like this approach less though, because it still has the
> problems from above but it also impairs usability for relay operators.)
> 
> The long-circuit attack becomes a bigger deal when we consider that it's
> not just a DoS attack, but it can be leveraged into an anonymity attack
> because it makes clogging attacks low-cost again.
> 
> Hm.

I'll talk to you about clogging attacks on anonymity another time, (I
think they're probably easily addressed, but haven't had too much time
to consider). But, ignoring them, it is indeed a hmmm to ponder
whether it is worth countering just extension attacks for DoS.  What
is to keep someone who wants to DoS the network from setting up just
two zombies and having them open as many connections as they can
between them (even default 3 hop connections, but preferably as long
as can be allowed) and dump as much stuff as they can over
these? (This could be viewed as a variant of the extension attack if
each circuit is dumping into the next one on a given zombie; although
that may be more conceptually nice than the most effective way to do
the DoS).  Now use a botnet of zombie pairs if you want to multiply
this. Admittedly this requires him to obtain some zombies rather than
finding bridges or nonTor open proxies and building circuits himself.
That is harder/riskier. And it would be worse if the zombies could do
indefinite extensions too. But the current idea is easy-to-do,
low-overhead, not (obviously) engendering of other attacks,
etc. Trying to counter more complicated extensions may not be worth it
(unless you are also accomplishing something else thereby besides
reducing the threat of extension-based DoS) given that it seems too
easy to do it in other ways. Thus, e.g., keeping the latency test in
your quiver might make some sense because might facilitate other
resource or QoS management in the network.

-Paul