Alen Peacock wrote:
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)?
But you cannot discount churn from this equation - this is a distributed P2P scenario, nobody is up 24/7. And, on the flipside, never changing neighbors will means that once an attacker is in, he can do a lot of damage without being replaced.
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.
I don't understand the problem. Trying to target your ID to a certain piece of data is on the order of the size of the network, so it won't be a problem to find something that hashes "close enough".
Hashing a public key will work only if the key has to be signed by some certificate authority, but that isn't desirable in most p2p scenarios. The only other option I know is having the ID be the hash of the nodes IP adress, which feels very hackish and dependent on a hopefully transient situation (the shortage of IPv4 addresses). (Of course, one also make it the hash of the computers TCPA fingerprint...)
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 don't think a trust system can do much at all. Because the graph in the DHT (however you do it) prescribes at least a distribution regarding who should be linking whom (based on ID), there are certain other nodes you have to talk to, whether you have reason to trust them or not. The only system of integrating trust I know is the new Freenet system which allows only verified, trusted, connections, but that has it's own set of headaches.
// oskar _______________________________________________ p2p-hackers mailing list p2p-hackers@zgp.org http://zgp.org/mailman/listinfo/p2p-hackers _______________________________________________ Here is a web page listing P2P Conferences: http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
