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

[Roger Dingledine <arma@xxxxxxx>]

On Sun, Mar 11, 2007 at 11:33:22PM -0400, Nick Mathewson wrote:
> I've added the original proposal as "109-no-sharing-ips.txt", retitled
> it to No more than one server per IP address, and merged in Roger's
> suggestions (except for those that represent an alternative approach;
> I've put those at the end).

You should push your changes to the repository so the rest of us
can see them too. :)

> > Should we consider enforcing this on /16 networks rather than /32, like
> > we already do for servers-in-the-same-circuit? In many cases being next
> > door too isn't so much harder.
> 
> This isn't such a good idea; /16s are much bigger geographically in
> some places than others.  For example, here's our current top-5 /16s, along
> with their count of networkstatus entries:
> 
>   12 62.75
>   13 85.25
>   15 81.169
>   22 88.198
>   30 85.214
> 
> If we do /24 instead, the top 6 are:
> 
>   3 18.244.0
>   3 217.20.117
>   3 85.31.187
>   3 88.211.140
>   4 85.214.29
>   5 149.9.0

Ok. I guess my reaction for now is that we should wait for people to do
more research on the location diversity question (the followon to the
paper Nick Feamster and I had at WPES), and implement just /32 until we
know more.

> > Also, if we're trying to avoid letting the adversary attract too much
> > bandwidth, should we be thinking "no more than 5MB/s advertised bandwidth
> > total" rather than "no more than 5 servers total"? On the other hand,
> > there are a very few cases where we choose a random node without regard
> > for advertised bandwidth, so maybe number-of-servers would be good
> > too.
> 
> Two caps sound best: one on total BW-per-IP and one on servers-per-IP.

Yep.

>  [...]
> > None of these are super compelling, other than the first, and I guess we
> > could make an 'exceptions' list, though that would be code bloat. I'd be
> > more comfortable putting the limit pretty high though (say, 5 servers
> > or 5MB/s to start), because that will still block Sybils yet give us
> > some flexibility to see how Tor use evolves.
> 
> Please, don't say "block Sybils" here.  Remember, the Sybil attack
> says nothing about requiring the adversary to have a nicely limited
> number of IP addresses.

Agreed.

> > > Specification:
> > > 	We propose that the directory servers check if an incoming Tor router
> > >     IP address is already registered under another router. If this is 
> > >     the case, then prevent this router from joining the network.
> > 
> > By "registered", do you mean "Named"? Or just "Running"? Or just "in the
> > network status"?
> 
> Another problem at this point:  there is a race here.  Suppose there are
> two servers running on some IP address, A and B.  Suppose that A
> publishes to directory authority AUTH1 before B does, but that B
> publishes to directory authority AUTH2 before A does.  Now AUTH1 will
> reject B as a Sybil, but AUTH2 will reject A as a Sybil.  That's no
> good; we probably need a different rule to keep the authorities from
> getting arbitrarily out of sync with each other.

Does my proposal have this same race?

"We should pick Named servers to keep first, and among those sort by
bandwidth, so we keep the "best" available servers usable."

To be a bit more clear, order by:

  Named server with best bandwidth
  ...
  Named server with worst bandwidth
  Unnamed server with best bandwidth
  ...
  Unamed server with worst bandwidth

I guess this has the flaw that only a few authorities assign the Named
flag, so we could still be out of sync. An easier approach would be to
order by:
  Server with best bandwidth
  ...
  Server with worst bandwidth
and ignore Named.

--Roger