Exit Balancing Patch

[Mike Perry]

Thus spake Roger Dingledine (arma at mit.edu):

> The first vulnerability is that fast nodes attract a disproportionate
> amount of Tor traffic. If we actually had a node that could handle 1GBit,
> and we added it to the network, then suddenly there would be a single
> point where an attack would yield really good results. So we want to
> avoid making the network "too" lopsided -- and one of the open research
> questions here is finding the right tradeoff between how lopsided we
> can afford vs how much performance penalty we should force on users to
> ensure that they get a diverse network.
> 
> The second vulnerability is that somebody who wants to attract Tor
> traffic can run a small node, claim to have a whole lot of bandwidth,
> and be in an improved position to attack Tor. Our current defense here
> is a MAX_BELIEVABLE_BANDWIDTH cutoff (currently at 1.5MB/s), which makes
> sure we avoid allocating more traffic than a certain cap to any given
> node. Future proposed defenses include limiting the number of Tor servers
> on a given IP address (proposal 109), and doing spot checks to see if a
> given server is performing much worse than expected -- one metric would be
> "is his performance much worse than other servers at the same level?"
>
> Now, the 1.5MB/s cap is relevant to both of the [follwingvulnerabilities.
> Regarding the second issue, I agree that it is a good idea to raise the
> number, and I don't think anybody will object. Regarding the first issue,
> I think you're right, but I don't think we've explored it well enough yet;
> we should do that at some point.

Yeah, while these issues are a concern, I do maintain they don't
warrant keeping the the limit this low. In the first case, I'm not
advocating getting rid of the limit, I just think it should be high
enough that it is not hit within the lifespan of the current Tor
release, which should be about 10Mbytes/sec or so.

As an aside though, an adversary that can afford a 1GB link can do all
sorts of crazy things with that bandwidth even with the limit in
place: the first one likely being mounting a sybil attack from a ton of
disperate IP ranges possibly all from that same link. But yeah, it
would make that node a nice point of surveilance for an external
adversary.

The second issue should be adressed by scanning, but see my points
below as to why we've got a chicken/egg problem.

> We should think about how we can get automated scanning into place. The
> fact that we *can* do a check is great, but we need to work on the next
> step which is having it automatically and constantly look for anomalies.
>
> What is the limiting factor here? Code? High-speed network connections?
> Humans to oversee it? Ways to present the results usefully?

Again, the reason why I am pushing so hard for quick adoption of these
fixes (including expiring poorly chosen guards) is that an unbalanced
network makes it *very* hard to find anomalies.. Once you get past
about the 15th percentile, a lot of nodes begin to look anomalous
(high circuit failure, low capacity, etc). There still is too much
noise for me to make heads or tails of what is cause in every case.
Some are obvious, such as nodes having obscene exit policies, etc. But
some nodes have high circuit loss and no capacity for no good reason,
especially once you get into the 35-50th percentiles. Probably just
load, but could also be liars/active attackers. I just can't tell.

If you balance the network/accept my patches to do so, I will build
continous, automated centralized scanning (though it does have some
weaknesses in that it can be detected/gamed in some cases... I will
also be exploring a distributed method of scanning bandwidth which I
will describe in my Black Hat/Defcon talks).

But yeah, I won't turn away offers to help display results nicely or
people who would like to scan themselves. I will try to elaborate in
the README a bit once I figure out the most reliable way to get good
results.

> > But we should set it high
> > enough that we do not have to raise it for a good while.
> 
> This is an important enough point that I'll elaborate on it. It's not
> just a matter of trying to avoid needing this discussion again in 6
> months when 8MB/s servers are common. Rather, we're trying to pick a
> number to give all the clients right now, so that in 6 months today's
> clients won't be back to harming the load balancing again. So we should
> try to pick a number that will still not be reached at the end of the
> expected lifetime of today's Tor release.
> 
> (There's also a minor partitioning attack here, in the form of a
> statistical leak based on whether you're weighting your node choices like
> the people with the new number or like the people with the old number; but
> I don't think that's a big deal compared to the other big deals we have.)
> 
> > Also, I think the exit weighting formula is wrong. If that portion of
> > my patch is not to be applied, I would like some sort of justification
> > as to why what is currently there is better than what I proposed (or
> > is even correct), but that is the least of my concerns, since exit
> > bandwidth is usually scarce.
> 
> I've asked Nick to look at it and compare it to the equation he produced
> earlier. His initial response was similar -- that he wanted some kind
> of justification for why this new one was better.
> 
> My plan is to sit down sometime and look at both equations and try
> to figure out how they compare, but it's low on my priority list, so
> hopefully before then one or the other of you will get beyond the "well,
> I wrote one, and that other one is confusing to me, so why not use mine"
> stage. :)

Heheh, yeah, Nick's analysis was excellent. I came up with the value
mostly by intuition and demonstrated it correct by summing over the
resulting total weighted exit bandwidth to make sure it came out to
how much bandwidth was left over for exits to use as non-exit hops.
Admittedly, his derivation is much better.  It should go into
path-spec. 

Also, I think we should consider doing a similar weighting for
choosing guards for middle nodes. Guard bandwidth is also somewhat of
a scarcity, though not as much as exits (40% by my measure).

-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20070729/fc33eef0/attachment.pgp>