[p2p-hackers] Chord comments

[Roger Dingledine]

On Mon, Jul 30, 2001 at 03:59:32PM -0500, Brandon K. Wiley wrote:
> So if you have 65k addresses and the network has 65k nodes, then your odds
> of being closest for a given key are 50%. Your odds for winning on two
> keys are 25%, etc.. So if you have the entire IP resources of a
> university, you can *almost* be assured of censoring one file, but if you
> want to, say, censor 65k files (one file per node), then you get .5 ^ 65k,
> which is really small.
 
I've been thinking about this off and on for a while, and I think you're
right. This is an excellent point -- Chord may be vulnerable to a large
adversary gunning for a specific file, but that adversary has to do a
separate attack for each file he wants to censor. "Getting control of
one file does not get him significantly closer to controlling any other."

> > b) Determine which IPs would be useful to you, and break into machines
> >    on their subnets.
> 
> Right now I'm just trying to defend against attackers that use legal
> measures such as scanning IPs. If you can take over arbitrary machines at
> will then I don't know of any currently existing system which will help
> you.
 
No, my attack was very different from compromising arbitrary machines.
I don't have to compromise *your* machine -- I just have to compromise
any machine out there that has (or has access to) an IP better than
yours. I think this is a much more feasible attack.

> > But when a node is "fixing" the Chord network due to
> > loss/addition of a node, how do you know that he's fixing it right? Nodes
> > can flat-out give you a new routing table which is made up entirely of
> > dead nodes, thus cutting you out of the ring. If you verify that new
> > routes you get work, then the adversary can transition you onto his fake
> > ring, and then drop you all at once (or just watch all your queries).
> 
> An adversary cannot give you an entirely new routing table. Well, he can,
> but you will only use those parts of the new routing table which are
> actually better than what you already have. The adversary does not know
> what your routing table currently contains, so cannot know what keys it
> controls are better than what you already have. However, since the keys
> which you desire are relative to your own key, your key is based on your
> IP, and the adversary has your IP, the adversary can generate a routing
> table for you which contains the best keys under its control for the
> various slots in your routing table. The odds of the adversary taking over
> your entire routing table are, as before, (evil / (evil+good)) ^ keys. So
> given a 65k network and 65k addresses under the control of the adversary,
> the odds of taking over your entire routing table are .5 ^ 160 = 6.8e-49.
> If any good entries are left in your routing table then when the evil node
> drops you, you can rebuild your routing table from the good node. Chances
> are that the evil node isn't the best node for one of the slots in your
> routing table, so there is a possibility that it will be replaced by
> another node and then you won't get bad references anymore.
> 
> http://www.pdos.lcs.mit.edu/papers/chord:sigcomm01/
 
Ok, I take back my earlier claim. You're right -- since the finger tables
try to remember specific locations in the ring (rather than "somebody
from that segment of the ring" as I'd originally thought), you need to
to get IPs which are better than every entry in the target's finger table.

I still think a strong adversary can win against a given individual
target by identifying which IPs would be useful and getting them.
(Your math above is fishy, but that's a topic for a later post.)

The neat feature which Chord provides is separation of targets: if I'm
attacking a given target in the Chord ring, then my attack (with high
probability) is not useful against any other target. Said a different
way, I can't "pre-attack" a target without first knowing his IP. (Or
equivalently, I can't "pre-attack" a file without first knowing its
contents (hash)).

Anybody else buy this?
--Roger