Route selection

[Roger Dingledine]

On Fri, Dec 05, 2003 at 03:05:53PM -0500, Paul Syverson wrote:
> Note a tradeoff, a bad node who determines a connection came from a
> targeted/interesting client can just break the connection in the hopes
> of increasing the odds that a bad-first-last circuit will be made
> by the repeated attempt. Helper nodes can play a role here perhaps.

This doesn't seem like the end of the world, even if helper nodes don't
turn out to help here. We can't be everything.

> > So we don't exit from the middle, we don't reextend, etc. On the other
> > hand, I believe that currently if a circuit breaks, streams will exit
> > from the new last node in that circuit, but the circuit's dirtiness
> > is unaffected.
> 
> Right, this seems to be the worst possible response as it means any
> bad node in a circuit can become the exit for all streams on that circuit,
> it doesn't have to hope for the luck of being the exit node.
> Please tell me the above is not true of our current implementation
> if the circuit breaks after just one node, because if so we really are
> at just c/n protection for all connections.

Hey, nobody said the current implementation provides anonymity. :)

> We don't know the relative possibility of attacks on whole path
> reconstructions vs partial, whether or not helper nodes are used, etc.
> 
> But, as an initial gut sense of what to do here for now I would suggest.
> 
> 1. Broken circuits are closed completely

I just changed it so when a 'truncated' cell comes back (this happens
when a connection to an OR broke, or when an 'extend' attempt failed),
the whole circuit gets torn down.

> 2. It is made relatively easy to switch that default so we can experiment
>    with the different possible circuit building and recovery approaches.

There are a lot of pieces to circuit-building, so it's not trivial to
play with it, but it will be possible to experiment with various options.

Note that we still haven't implemented all the infrastructure to have
streams exit from intermediate nodes; it's quite possible there remain
some bugs there. We haven't needed it yet, and I'll continue putting it
off while other issues remain.

> I think working out the adversary distributions, traffic situations,
> etc.  for which a helper node is advantageous and those for which it
> is disadavantageous is a major open problem for us to get a handle on.
> I would be astounded if one or the is always the correct choice.  I
> would be at least surprised if we could let the threat concerns of the
> end users dictate whether they use a helper node without this
> affecting the anonymity of others. That nifty problem that I noted to
> someone recently of when it might be possible to selfishly pursue
> better anonymity for me and actually get it, but at the expense of
> others. Generally it seems that anonymity favors cooperation, but
> maybe there are cases where it doesn't.

How about you get us started on that research path? :)

> > A fixed entry hop seems safer than a fixed exit hop -- the end websites
> 
> True for anonymous surfing, but for road warrior or enclave-to-enclave
> circuits the "end websites" are assumed to not be bad. So it may be
> worth having these protections.

Makes sense.

> And, we probably don't even want to
> broach how this all fits in to rendezvous points, although we will
> want to someday.

Establishing a rendezvous point is similar to forward-onion-routing.
An entry helper node will help as normal (however much that is). Choosing
a fixed rendezvous node is a nice idea, but remember that we will be
choosing quite a few rendezvous nodes so it may not be that easy (but
nonetheless we can choose a fixed set of nodes. This is a good idea
anyway so the advertised rendezvous points don't need to change much).

Intermediate nodes can also get information, by connecting to the
rendezvous point and requesting a rendezvous, then doing timing/counting
attacks. In a sense this is like normal, because an adversary who
happens to be the first node in the path and also the webserver can do
confirmation attacks; but in this case the adversary can opt to 'be the
webserver'. So it seems weaker. Darn.

Since the rendezvous request notifications don't need to be immediate,
the rendezvous point could queue or batch them. But that doesn't seem
like it'll solve the problem.

> > Other questions revolve around Preferred Entry Nodes and Preferred Exit
>
> Yep. Yep. and Yep. I'm thinking that we need to set a more detailed
> prioritized research agenda than we have had previously, which had
> been driven by either the things that just couldn't wait or were just
> too cool to let me think about anything else. There
> will be way more on it than we can handle in reasonable time.
> I'm thinking that a good next step may be to have a coordinated
> research effort with the general anonymity research community.
> I'll get right on that, when I can find the time ;>)

Ok. I look forward to it. ;)

--Roger