Route selection

[Paul Syverson <syverson@itd.nrl.navy.mil>]

So I woke up some time ago thinking that we were wrong to bother with
voting on network state in the directory servers, that they should
just be voting on membership and maybe exit policy. Working on it for
a while I now think we probably still want a voted network state at
least c. every hour or so, since `simpler' ideas now seem even more
complicated, but I think I uncovered another issue.

I was thinking about connection breaks.  By breaking a circuit, under
our current design and policy, information does not propagate back to
earlier nodes that the break has happened. But, solving one attack
creates another, and in this case I think much worse. What this does
allow is a node breaking circuits until we choose a next hop they like,
ideally just exiting from that last node before the break.  If
deterministically iterated, this guarantees a path compromise any time
the initiator is already identified with a circuit, but even if it is
only done statistically, the advantage is there. Any bad node in a
route who knows the initiator can get the responder with uncomfortably
high probability. (We just moved from c^2/n^2 much closer to c/n).  We
should look at strategies such as pulling back at least to the
penultimate to a break node before extending to reduce this threat.
This brings it back from needing for this attack just first node and
any other bad node in the path to needing the first node and two
successive other bad nodes in the path. We need to establish a default
circuit break policy cognizant of this attack.

Here's a stab. We should have a route selection strategy wherein you
pick the far node (random wrt the exit policy or other constraints you
have).  Then you get to that node however you do, but you don't let
the network complete a route to an unknown point for you. If you are
going enclave to enclave, then this far node is actually the
penultimate node (the ultimate being the far-end enclave node).
Whether it is better to rebuild a whole route from scratch or not
will require much more thought. I suspect that for Onion Routing
this is a bigger problem than the much ballyhooed predecessor attacks,
but that's just a gut. Obviously there's a tension between how we
deal with each of these. Various things we might try, longer routes
with predesignated break points, etc.

Gotta go for now.
Paul