Proposal 109: No more than one server per IP address [was Re: Sybil Attack Countermeasures]

[Nick Mathewson]

On Mon, Mar 12, 2007 at 01:25:08AM -0400, Roger Dingledine wrote:
 [...]

On consideration, I think I'm in favor of this proposal.  My first
reaction was something like "This is a silly bandaid that will never
solve the Sybil attack."  And it won't: the Sybil attack is, under the
terms of the original paper[1], quite hard to solve[2].  But it will
raise the cost of the Sybil attack by requiring that the attacker
actually go out and get a bunch of IPs, rather than just running a
bunch of servers on a single IP.

The open questions in the proposal seem to be:
1) What do we use for the network size (/16, /24, /32)?

   I think the only reasonable thing to do right now is /32; later,
   limiting by AS or something more geographically aware _might_ help,
   but we need to think carefully about goals.  What we want is not a
   measure of locality so much as a measure of effort needed per
   additional address, given that you already have one address on a
   given network. That's not an easy thing to approximate, so let's
   stick to /32 for now.  (Remember, to change this, we only need to
   change the authorities, and that's not a lot of computers to upgrade.)

2) What do we use for the per-IP bandwidth limit?

   I'd go with 8 MB/s or so, but this is totally bikeshed.[3]

3) How many servers do we allow per IP?

   I'd go with 3, but again, bikeshed.

4) How should authorities list excess servers?

   Roger suggested "list, but not as Valid", then changed his mind to
   "list, but not as Running."  I'm going to suggest "list, but not as
   valid _or_ as Running", as the safest.

5) How do we pick which servers are excess?

   'Order by bandwidth' seems safest.  The Named hack doesn't seem
   worthwhile for now: it's additional complexity; hard to resolve for
   non-Naming authorities; and this whole thing shouldn't come up
   enough for it to really matter a lot.

I think there's enough consensus on these that unless I hear
otherwise, I should add them to the proposal, mark it accepted,
implement, merge, and close.

[1] http://www.cs.rice.edu/Conferences/IPTPS02/101.pdf
[2] The original paper has proofs.  Basically: If you believe other
    potentially faulty entities, Sybil works.  If you don't, then Sybil
    still works, only a bit less.
[3] See http://en.wikipedia.org/wiki/Bikeshed

yrs,
-- 
Nick Mathewson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 652 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20070315/2a02a3a3/attachment.pgp>