Sybil Attack Review

The Sybil Attack Review
Review By: Troy Ronda

Redundancy is employed to mitigate security threats from faulty or
malicious nodes. The underlying assumption is that data will be spread
among *different* hosts (entities). A Sybil attack forges multiple
identities on one host. It has the goal of controlling a substantial
fraction of the system. This, of course, undermines redundancy. A central
trusted authority, creating mappings between identity and hosts, is
necessary to prevent Sybil attacks. Without a central authority, peers
must accept identities from each other. They will only accept identities
from peers it can directly validate (somehow). An example of direct
validation is requiring that two hosts perform a task that a single host
cannot do alone. The paper shows that, in the direct case, even under
severe resource constraints, a faulty node can still counterfeit a
constant number of identities. Even worse, unless a host simultaneously
validates all identities, a malicious host can create an unbounded number
of identities. Indirect validation allows for peers being vouched for by
another peer that was previously accepted. Likewise in this case,
counterfeiting can still occur. A set of hosts can counterfeit an
unbounded number of identities. If hosts in the system do not perform
identity validations concurrently then a constant number of identities can
be forged. The argument follows that it is practically impossible to
operate a peer-to-peer system under these security constraints. Hence, a
validation authority is necessary.

This short paper demonstrates the shortcomings of peer-to-peer redundancy
when malicious or faulty hosts are operating in the system. It is
certainly true that if somebody controls a large set of the identities in
the system then they will also control a proportional amount of the data.
It is immediately obvious that redundancy will be compromised under these
conditions. If the mechanism for verifying mapping of identity to host is
a resource check then I believe the lemmas stated in the paper. They were
both easy to read and as the authors stated, trivial. It was a
well-written, enjoyable to read paper. If we can actually find a central
authority that everybody trusts, does not charge, and privacy is not an
issue then we are all set. I have not read the CFS paper but it seems
their apparent reliance on Ipv4 may be a problem. It is good that the
authors mentioned IP6 as I was at first skeptical as to why identifiers
couldnt be based in part on IP addresses.

Of course, all of the usual issues with a central authority apply (single
point of failure, trust, privacy, etc). Even the DNS system has to work
through politics (eg. USA vs UN). Beyond that, it seems that a host
controlling a substantial number of identities might create a DoS attack
on themselves. Not only must they perform validation checks requiring
resources but will also be hit with a proportional amount of overhead
traffic. This, of course, is okay if the attackers objective is merely to
disrupt the system. I still wonder if a centralized authority can solve
all Sybil problems. What if the attacker steals (or controls) a number of
certificates? It seems to be harder to steal (or coordinate) certificates
than forge identities without a certificate authority (I think). Another
possibility of mitigating Sybil effects is to spread redundancy with
Internet distance. In this case, forging identities will not help because
redundancy is spread to nodes known to be physically separate. Perhaps a
challenge system should also work, such that the indirect host must be
known to be physically separate from the new host.
Received on Thu Nov 17 2005 - 09:00:26 EST