Downlist modification is vulnerable to DOS attacks

[GoogleCodeExporter]

Downlist modification may seem like a good idea: it makes sense to notify other 
peers if certain contacts have very high RTTs or are unavailable. 
Unfortunately, it creates a major security flaw.

Any peer can send FIND_NODE RPCs to other members of the DHT, and malicious 
ones may decide to include high-throughput peers in their 'downlists'. This 
enables a small amount of malicious peers to wipe out large swaths of the 
keyspace.

The only effective defense is validation: when one peer receives a downlist, 
they should ping the indicted contacts and make sure they have high RTTs before 
expunging them. It's worth keeping in mind that this mimics the default 
Kademlia behavior, though.

/$0.02

Original issue reported on code.google.com by v...@vedantk.com on 1 Jan 2011 at 10:39

[GoogleCodeExporter]

Cheers for this. 

In our case we only send downlist mods to peers who gave us the contact info. 
So there are a couple of checks. Initially you must have the contact that has 
been downlisted in your routing table. We also require that a node is pinged 
before removal to ensure the downlist notification is just not from somebody 
who has problems connecting to some peers (network configs etc.) 

We are working on another implementation though, but not likely till our 
products are launched which will require no downlist at all. 

Your dead right though with your analysis, this is also a major problem for 
other protocols such as D1HT and the alerting mechanism used there, although 
these are supposed to be used in a secured environment I think.

Ideally using our dht in a secured environment (well public network, but with 
RSA keys) and implementing alerting and ranking is the best way forward, it's a 
wee bit complex but very good, as the network can handle attacks itself that 
way. 

Original comment by irvine.d...@gmail.com on 1 Jan 2011 at 11:00

[GoogleCodeExporter]

Can you expand a bit on how the downlist modification mimics default Kademlia 
behaviour please?

From what I recall, the downlist is sent to a node which has passed "bad" (i.e. 
effectively offline) contacts to another node.  In this way, the sender of the 
bad contact is aware much sooner that its routing table has stale information 
than would be the case for normal Kademlia.

Normally, a bad contact would be discovered only once the holder tried to 
contact the bad node itself, either during a lookup of its own, or during a 
bucket refresh, or if the bad contact was the last seen in that bucket and a 
new contact is set to replace it.

Thanks anyway for the heads-up.  As David says, I think we're OK as we do 
validate by checking the contact is in our routing table, and then pinging 
before removal.

Cheers,

Fraser.

Original comment by fraser.hutchison@gmail.com on 1 Jan 2011 at 11:59

• Changed state: Done
• Added labels: Type-Other
• Removed labels: Type-Defect

[GoogleCodeExporter]

Hi Fraser,

You're right, sending the downlist notifies peers about unresponsive contacts 
faster. I was referring to the fact that normal kademlia would discover them 
eventually, but it seems that this is a good optimization.

To David, I should mention that the checks that you have are very important 
(and secure). If you make changes to the way you handle downlists, be sure to 
enforce the rule only allowing contacts who give you unresponsive peers to 
include them in downlists. If that were relaxed, the original scenario would 
become a DDOS. The malicious peer would have valid peers do its work by making 
them relentlessly ping the entire keyspace ;).

You guys are really dedicated! Blazing fast response time. Good luck!

Original comment by v...@vedantk.com on 2 Jan 2011 at 12:42

[GoogleCodeExporter]

Thanks a lot, were expanding the team now to get through all this a little 
faster, so you should see some increase in code and products very soon. 

Thanks for the comments, your very welcome. 

Just a small bit of info, the downlist is measured to provide 19.8 out of 20 
valid nodes per k bucket as opposed to 13 out of 20 with a network that does 
not use it. So kademlia may find these but most likely it would take so long 
(network size makes a difference). All it means is the nodes with dead nodes in 
the k bucket keep giving them out, this is a problem especially in buckets 
relatively close to you as you may not contact the dead node for a good while 
(although not bucket 0 or 1). Also depends of k bucket refresh rules, which are 
pain and not well documented (as a lot of kademlia :-) ). 

Original comment by irvine.d...@gmail.com on 2 Jan 2011 at 1:00