Big hype on small worlds. (was Re: Dijjer and Freenet (RE: [p2p-hackers] clustering))

[Alen Peacock]

On 3/21/06, Oskar Sandberg <ossa at math.chalmers.se> wrote:
>
> The kind of attack I
> mean is wide scale sybil type attack with a user spawning millions of
> fake identities for his node, giving nodes faulty neighbors and
> misinforming them about the size of the network etc.

Isn't the sybil attack against kademlia mitigated by the fact that the
routing table has a "LRU with live nodes never evicted from k-buckets"
strategy?  It seems to me that this preference for old contacts would
make it unlikely that a sybil attack against an established kademlia
DHT could have much success.  Admittedly, churn rate comes into play
here, but the fact that a sybil attack could *never* purge currently
connected valid nodes from a peer's routing table means that such a
peer would always have at least some valid contacts.  And the fact
that each peer has some valid contacts implies that a valid route can
always resolve, doesn't it (admittedly, with some decrease in
performance/efficiency)?


> There are other
> more devious attacks such as those attempting to upset just routes for
> one particular key value as well.

There are defenses against targetted key attacks (in addition to the
old contacts preference).  For example, make each node choose its own
Ku/Kr pair before joining, with nodeID = H(Ku).  A node would have to
'prove' its identity before any of its operations or results are
accepted (through challenge/response or signatures).  Under such a
scheme, an adversary could still spawn millions of sybil identities,
but it wouldn't be able to choose a specific ID space to target.  The
millions of nodes /could/ try to upset some specific route, but
preference for old contacts still makes this rather difficult.

If you wanted to get really paranoid, you could introduce a
trust/reputation system on top of a strong ID system like that
mentioned above.  This would even further diminish the effectiveness
of sybil attacks of this nature.

I hope I'm not being naive or unimaginitive by proposing that these
countermeasures make such attacks less effective.  I'd love to see
further discussion on why these are insufficient, as well as further
discussion on attackability of DHTs.

Alen