Proposal 151: Path Selection Improvements

[Nick Mathewson]

On Sun, Jul 06, 2008 at 04:38:56PM -0700, Mike Perry wrote:
 [...]
> I've updated this proposal in svn to include plans for migrating away
> from guards with high failure rates that Fallon and I discussed last
> night.
> 
> For convenience:
> https://tor-svn.freehaven.net/svn/tor/trunk/doc/spec/proposals/151-path-selection-improvements.txt
> 

Hi, Mike!  The proposal's too preliminary to accept right now, but I
thought I'd put in some comments and questions wrt the version in svn.
(This doesn't prevent the proposal from getting into 0.2.1.x: Changing
the number of guards and/or the CircuitBuildTimeout should be
relatively easy and low-risk, and the rest doesn't sound too
destabilizing either.)

Something I didn't see in the proposal (forgive me if it's already
there) is: is this a static or dynamic solution?  Is the idea to
examine the network once and pick the right values for NumGuards and
CircuitBuildTimeout [static], or to examine the network continually,
and pick the values based on up-to-date statistics [dynamic]?  A
dynamic approach seems better to me, since it won't get stuck
optimizing parameters for the network of today.

If we're taking a dynamic approach... who is to do the measurements?
Clients, or authorities?  Having authorities do measurements seems
more efficient, and more resiliant to attack where the adversary acts
differently towards different clients in order to change their view of
the network parameters, or make them use different guards, or such.

On CircuitBuildTimeout, a question: for general-purpose circuits,
perhaps the behavior of CircuitBuildTimeout is just plain wrong.
Perhaps the sensible behavior is, instead of discarding the circuit,
launching a new circuit.  This way, if the circuit is just being slow,
it can still get used instead of discarded.

WRT this paragraph:
> In addition, we have noticed that some entry guards are much more
> failure prone than others. In particular, the circuit failure rates for
> the fastest entry guards was approximately 20-25%, where as slower
> guards exhibit failure rates as high as 45-50%.

I'm very curious about the causes and symptoms of these failures.
What makes them happen?  How do they look to the client?  This seems
excessively high, and in addition to responding to these rates (as 151
proposes) we might also do well to look into reducing them.

> In [1], it was
> demonstrated that failing guard nodes can deliberately bias path
> selection to improve their success at capturing traffic. For both these
> reasons, failing guards should be avoided. 
>
> We propose increasing the number of entry guards to five, and gathering
> circuit failure statistics on each entry guard. Any guards that exceed
> the average failure rate of all guards by 10% after we have
> gathered ncircuits_to_observe circuits will be replaced.

If clients make their own measurements on this, there's actually a
neat class of attack that we'd be enabling.  Instead of a malicious
guard failing in response to the client building a circuit through a
non-compromised path, malicious second hops can fail in response to
circuits built through targetted non-compromised guards.  If they
manage to raise failure rates for non-malicious guards high enough,
those guards will stop getting used.

Here's a more interesting attack: Suppose that we have a couple of bad
guards and they're targetting us in particular.  Let's say that they
have the same failure rate as average (based on CPU limits or
connectivity or limited bandwidth or whatever), but that they can
divert their resources towards particular circuits.  These malicious
guards should devote extra resources towards some users, and fail all
the time for the users they aren't targetting.  If they do this, they
may be able to get the target users to abandon other guards in favor
of them.

[As an aside: reputation-like systems on anonymity networks are the
best example I know of the principle in security that when you amend a
design, the attacker gets to make up attacks based on _your_ design,
and isn't restricted to the attacks that worked on the last one.]

yrs,
-- 
Nick