Sybil Attack Countermeasures

[Roger Dingledine]

On Fri, Mar 09, 2007 at 04:28:34PM -0700, Kevin Bauer wrote:
> Overview:
> 	This document describes a solution to a Sybil attack
>     vulnerability in the directory servers. Currently, it 
>     is possible for a single IP address to host an arbitrarily 
>     high number of Tor routers.

An extra sentence to add here: "While Tor never uses more than one
server from a given /16 in the same circuit, an attacker with multiple
servers in the same place is still dangerous because he can get around
the per-server bandwidth cap that is designed to prevent a single server
from attracting too much of the overall traffic."

>     We propose that the directory
>     servers limit the number of Tor routers that may be registered
>     at a particular IP address to some small (fixed) number, perhaps
>     just one Tor router per IP address.
> 
> Motivation:
> 	Since it is possible for an attacker to register an arbitrarily large
>     number of Tor routers, it is possible for malicious parties to 
>     do this to as part of a traffic analysis attack.
> 
> Security implications:
> 	This countermeasure will increase the number of IP addresses that an
>     attacker must control in order to carry out traffic analysis.

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.

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.

In any case, this is tricky -- there's a tradeoff between letting people
volunteer to help grow the network and keeping ourselves secure from
potential attackers. Since the Tor network is so strapped for bandwidth
these days, I'm hesitant to add in anything that will turn away real
volunteers.

Here are some cases where we might see multiple Tor servers on the same
IP address:
  * Testing. moria1, moria2, peacetime, and other morias all run on
    my computer at MIT, because that way we get testing. Some are
    run by me, and peacetime is run by Nick.
  * NAT. If there are several servers but they port-forward through the
    same IP address, ... then I guess we can hope that the operators
    coordinate with each other. Also, we should recognize that while
    they help the network in terms of increased capacity, they don't
    help as much as they could in terms of location diversity. But our
    approach so far has been to take what we can get.
  * People who have more than 1.5MB/s and want to help out more. For
    example, for a while Tonga was offering 10MB/s and its Tor server
    would only make use of a bit of it. So I suggested that he run
    two Tor servers, to use more.

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.

> 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"?

My first thought is that we can let him join, but just not declare him
Valid if there are too many in a given location. But this still lets the
attacker sign up a thousand nodes that will be used only in the middle
hop, which doesn't seem so dangerous but probably would turn out to be.
My second thought is to just not declare him Running, then.

[Digression: is there a DoS opportunity if the attacker signs up a
bazillion non-working nodes with intent to bloat the networkstatuses?
Yes, probably; we should not list non-running servers if there are
too many. But that's for another proposal I guess.]

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

> Compatibility:
> 	Upon inspection of a directory server, we found that the following
>     IP addresses have more than one Tor router:
> 
> 	Scruples    68.5.113.81     ip68-5-113-81.oc.oc.cox.net     443
> 	WiseUp      68.5.113.81     ip68-5-113-81.oc.oc.cox.net     9001
> 	Unnamed     62.1.196.71     pc01-megabyte-net-arkadiou.megabyte.gr  9001
> 	Unnamed     62.1.196.71     pc01-megabyte-net-arkadiou.megabyte.gr  9001
> 	Unnamed     62.1.196.71     pc01-megabyte-net-arkadiou.megabyte.gr  9001
> 	aurel       85.180.62.138   e180062138.adsl.alicedsl.de     9001
> 	sokrates    85.180.62.138   e180062138.adsl.alicedsl.de     9001

Probably only one of these two was listed as Running, right? I hope? :)
And similarly, only one of the Unnameds above?

> 	moria1      18.244.0.188    moria.mit.edu   9001
> 	peacetime   18.244.0.188    moria.mit.edu   9100

moria2 is secretly running on the same host as these two, but it's
using a different IP address. See comments above about /16. :)

> 	There may exist compatibility issues with this proposed fix. It is unclear
>     why more than one router would need to be on the same IP address.

Thanks!
--Roger