Re: Proposal: Avoiding infinite length circuits

[Nick Mathewson <nickm@xxxxxxxxxxxxx>]

On Tue, Dec 02, 2008 at 03:16:45PM -0500, Roger Dingledine wrote:
 [...]
> 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.
> 
> 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.

An easier-to-implement but still brittle approach would be to refuse
any VERSIONS cell that took too long to arrive after we sent our own
VERSIONS cell.  This would indicate that the TLS connection from the
client to server had a very large latency, perhaps indicating that it
was coming over a tunnel of some kind.

This approach was suggested by "wood" on the #tor IRC channel, along
with this sample patch:

--- command.c	 Wed Aug  6 00:30:42 2008
+++ command.110plus.c	  Fri Dec  5 19:07:22 2008
@@ -558,6 +558,12 @@
     apparent_skew = now - timestamp;
   }
 
+  if (labs(now - conn->handshake_state->sent_versions_at) > 5) {
+    log_fn(LOG_PROTOCOL_WARN, LD_OR,
+           "Received a NETINFO cell on high-latency connection;
Closing.");
+    connection_mark_for_close(TO_CONN(conn));
+    return;
+  }
   my_addr_type = (uint8_t) cell->payload[4];
   my_addr_len = (uint8_t) cell->payload[5];
   my_addr_ptr = cell->payload + 6;


Personally, I am unconvinced that there is a setting for the max
latency value that makes this attack ineffective without also stopping
lots of legitimate users.  But let's see.
 
> 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's a pretty good start, though, and would make an attack like this
a bit harder.

> (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.)

Agreed.

Another observation: The usual engineering solution here would be to
add a "hey, I'm a connection from a Tor server/hey, you are now
connecting to a Tor server" indicator to the protocol.  But our
anti-blocking designs make that basically impossible for us to do.  We
could take a probing-style approach, and have exit servers connect to
suspect ports, and see whether a Tor server answers, but that seems
questionable.  In any case, it would hurt the probing-resistance stuff
we've been kicking around.


Still another observation: There are two asymmetries that make the
attack work here.  First, bandwidth asymmetry: in an N-hop circuit,
the client uses ~512 bytes of bandwidth to send a cell whereas the
network uses ~512*2*N.  We can't do anything about that.  Second,
computational asymmetry: once the circuit is established, an
ill-behaved client can sent junk cells for the cost of the TLS crypto,
and the network will spend ~2*N TLS operations and ~N AES operations
per cell.  [This is because RELAY cells with bogus contents are
basically undetectable until they reach the end of the circuit.]

We could mitigate the second one if our next protocol version did
something to keep corrupted relay cells from spreading too far down
the circuit.  This might not be worthwhile, though: the bandwidth DoS
could be bad enough to make the CPU DoS irrelevant.

-- 
Nick