Proposal: minimum advertised bandwidth guarantees fast/guard

[Mike Perry]

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

> Hi folks,
> 
> This is a quick proposal, based on my post in Mike Perry's recent thread
> at http://archives.seul.org/or/dev/Jul-2007/msg00022.html
> Please feel free to flesh it out; also somebody should please write us
> a patch to the specs.
> 
> The issue is the same attack as in proposal 107: an attacker who signs
> up a thousand servers each claiming 10MB/s bandwidth will cause the
> median bandwidth to be 10MB/s, and all current guards will lose their
> guard status -- causing their users to abandon them and pick one of the
> new adversary-controlled nodes. The bug is that while we cap bandwidth
> at 1.5MB/s when considering load balancing, we failed to do it when
> considering median bandwidth for guard qualification.
> 
> I've attached a patch; but there are still some design questions to
> ponder and maybe improve:
>
> A) I picked 500KB/s as the cutoff. Is there a better way to pick this?

Current natural cutoff is 53KB/sec. Currently 115 "Guard" flagged
routers live between 53KB/sec and 500KB/sec. Only 64 are above.

Guards greater than 500KB/sec account for 78MB/sec of all guard
bandwidth, Guards less than 500KB/sec account for 25MB/sec of all
guard bandwidth.

Since guard selection is still largely uniform instead of weighted, this 
500KB cutoff will allow an attacker to still displace the guards of
approx 64% of Tor users. :(

Here are some other stats:
400k:
Routers above: 79 bw: 84M
Routers below: 101 bw: 19M

300k:
Routers above: 96 bw: 90M
Routers below: 83 bw: 13M

250k:
Routers above: 100 bw: 91M
Routers below: 79 bw: 12M

200k:
Routers above: 121 bw: 96M
Routers below: 58 bw: 7M

125k:
Routers above: 147 bw: 100M
Routers below: 32 bw: 3M

If everyone were weighting guards by bandwidth, 300-400k would
probably be a fine cutoff. But since we haven't yet decided to expire
people's already uniformly chosen guards, the limit should probably be
somewhere around 125k if you really don't want half of the existing
tor users to continue to be vulnerable to this attack.

Alternatively, we could make 0.1.2.16/0.2.0.3 expire all guards for
all versions prior, which would also help the network balancing. That
would be nice. :)

> C) Since we defined is_possible_guard to require is_fast, there was
> another turtle underneath this turtle. I fixed this by declaring that
> anybody with at least 100KB/s of bandwidth is automatically Fast. We
> could also fix it by getting rid of the is_fast requirement; but I think
> if we do that I'll be doing a new proposal later about how somebody can
> sign up 8000 new servers and suddenly no other servers count as Fast. ;)

Ouch.
 
> D) Why 100KB/s? Is there a better number?

The natural cutoff seems to be currently ~20K/sec FWIW.

30k:
Routers above: 711 bw: 222M
Routers below: 125 bw: 4M

40k:
Routers above: 621 bw: 220M
Routers below: 221 bw: 6M

60k:
Routers above: 502 bw: 214M
Routers below: 340 bw: 12M

80k:
Routers above: 425 bw: 209M
Routers below: 417 bw: 17M

100k:
Routers above: 392 bw: 206M
Routers below: 450 bw: 20M

Since Fast nodes are chosen in proportion to bandwidth, this limit can
probably safely be set much higher proporitionally. 100k looks like it
may even work.


-- 
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/20070720/993588fe/attachment.pgp>