Re: : Export END_CIRC_REASON_* to controler

[Mike Perry <mikepery@xxxxxxxxxx>]

Thus spake Paul Syverson (syverson@xxxxxxxxxxxxxxxx):

> On Fri, Oct 13, 2006 at 01:14:53AM -0500, Mike Perry wrote:
> > 
> > One issue I would like to guard against/watch for is an adversary
> > destroying circuits if they do not detect one of their colluders at
> > each end.  Adversaries doing this would be able to ensure that the
> > only time they waste bandwidth on a connection is if they know they
> > are able to determine its origin, thus gaining an advantage over the
> > expected rate of O((c/n)^2).
> > 
> > For the scanner to detect this, there shouldn't be any way a node can
> > make us mistake a malicious closure from one that should happen
> > normally (ie was requested by us). Taking the reason right from the
> > wire enables a node to do this.
> > 
> 
> I'm probably not getting some key assumption here, but I don't see how
> this can be prevented without some major developments.  This sort of
> attack is roughly how the experiments to detect hidden servers were
> conducted
> (http://www.onion-router.net/Publications.html#locating-hidden-servers)
> In that case we controlled the requesting client so could easily drop
> the circuit without doing anything otherwise odd.  But I don't see why
> any entry or exit node can't simply stop sending if a colluder is not
> detected on the other end.  Then he can close the circuit or others
> on the circuit will close it for him, and there will be no easy way to
> recognize that node as the culprit.  One coud construct testing and
> reputation mechanisms to recognize nodes that do this flagrantly and
> repeatedly. But some of us have worked on that and it can get tricky
> quickly, plus framing other nodes becomes a big issue.

Yeah, not prevented, just detected. The thought is that to really get
an advantage over the (c/n)^2 two-node selection, you would have to do
this excessively, and report fraudluent stastistics (essentially to
increase your bandwidth by a ratio of 1-(c/n)^2 I think) to the dir
servers so you would recieve lots of extra connection attempts, and
then just drop the ones you don't notice your adversary on. Since you
expect to be dropping 1-(c/n)^2 of them, your final bandwidth
consumption should be roughly optimal.

Furthermore, with a clever hack on the Tor protocol fields, you may be
able to do this collusion with as little as one cell (say by XORing
some field, onion-encrypted or not, with a unique stamp that your
peer must undo or else there will be a TORPROTOCOL or similar
error).


I'm not trying to detect this instantly, just in aggregate using
several scanners, running over a period of days, weeks, or even
months. I also realize that nodes doing this partially will be harder
to detect, but they also will have less of an advantage, which means
that the attack has at least been mitigated to a degree.

For detection, right now, a circuit or stream failure means "any
circuit or stream closure, timeout, or other error/reason that the Tor
client/controller did not specifically request".

When a circuit or stream fails (I count both equally at this point,
which should cover your stop sending issue) fails or times out without
the ability for a specific node to be blamed, all of them share the
failure count equally. 

Right now, the expected failure rate for nodes seems to be about 20%..
I don't yet break it down by failure type though. That may reveal some
more interesting things, and will separate stream failures due to the
fact that shitty nodes just happen to be selected 20% of the time.

Statistically over time, even in this case the actual culprit will
have significantly higher failure rates than other nodes, quite near
100%-(c/n)^2, in fact, where as other nodes, even those it was
attempting to frame, would not, since they would only be selected to
be its neighbor in (1/n) of the (c/n) times it was selected.


Also, this is just one of the things that this scanner should be
useful for. I'm thinking it may actually see more immediate usefulness
as a QA tool to help minimize circuit failures, and a general perf
tool to help flag poorly operating nodes as undesirable.



-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs