On 2013/07/23 (Jul), at 11:54 AM, Matthew Toseland wrote: > We haven't quantified this. Maybe we should, but it doesn't seem a good use > of scarce resources to implement a toolkit for an attack that we're not sure > how to beat! At least not if I do it.
I don't think we'd need a full toollkit, just some stats on: (1) the porportionality of long links [and how long they are] (I think we actually have a target value for this), (2) the probability of being able to insert your node "between" two others (routing-wise), (3) the average "width" of the network (in number of connections), ... and maybe some reasonable assumptions concerning how often an insert takes place (e.g. once a day?). As I see the attack, it would go much like a binary search: (1) effectively divide the network in half (i.e. most request going from one half to the other cross one of your nodes), (2) wait for a predicted insert to cross the tripwire (statistically you'll catch 1-in-4, so +4 days?) (3) divide the originating half-address-space in half again (works best with 50% more nodes [for three partitions]) (4) wait for another insert (now you'll catch 3/4 of "most"/50% requests, so that is 3-in-8 requests, so +2 days?) (5) move the stray partition to subdivide the wedge the request came from (6) wait for another insert (now at 7/8 address space, so another +2 days?) So under ideal attack conditions (where the target has but one unchanging peer connection, and the attacker has an as-of-yet-unmeasured number of nodes at his disposal), with an arbitrarily guessed network size of 10k... it would take 16 days to zero in on the target; and 18d for 20k, 20d for 40k, etc. What is the current network size, anyway? :-) The problem is, we focus on how easy steps 2/4/6 are, when I'm not even sure how feasible the rest is. Suppose that in the above case I have *more* than one peer connection, and even just the first hop of an insert is randomized (no random routing code required; just a random routable peer). Then that 16 day estimate is effectively multiplied by my number of peers, and becomes 1 year (and the attacker has to account for the fact that he might be chasing my peers rather than me, but that wouldn't be too hard... hmmm, maybe if they change). But in terms of the attack cost, we would need to know how many nodes it would take to "divide the network in half". I agree that this would be *significantly* cheaper than connecting to every node, but IMO the payoff for the attacker is very slow and unsure; what's more, one could only target *one* source, so it would have to be a high-value target (IMO). I would be happy to just ensure that the current code starts inserts at a random peer. -- Robert Hailey
