On Jan 31, 2008, at 5:33 AM, Michael Rogers wrote: > On Jan 30 2008, Robert Hailey wrote: >> No, in the way I am thinking this is even expected; a node can >> advertise whatever network-id it wants (just an integer), it is up to >> the peers to make sense of it. > > I don't see how that can be made robust against malicious nodes.
Because for any particular peer, we only take the id that they supply as a seed for enumerating the networks (suggestion/starting point), and not as *any* indication that they actually belong to that network. For all decisions particularly with regards to routing, we *only* use the network id that we finally assign to them. For a malicious node to be able to manipulate the system to get us to accept there network id, they would have to have a number of peer connections (in which case, we are already vulnerable); and the other nodes outside of the sybil attack would still not accept it, so it is only that one (confused/ attacked node). >> Some time in the future, using (for example) routed pings it breaks >> up >> it's peers into groups. e.g. I can ping peer #3 through peer#2, so >> they are on the same network. > > How do you authenticate the routed pings, to prevent an attacker from > replying on behalf of another node? Excellent question. Surely the "true/false" response of present is woefully inadequate. Since we have a direct connection to the peer that we are pinging a challange-and-response mechanism is easy, no? Consider node "B" who is between "A" & "C" (A-B-C). He tells "C" a UID & Secret [a randomly generated long?], and "C" stores that secret/uid as part of our peernode record. Node "B" then sends node "A" a routed ping with the same UID, and if node "A" returns the pong with the correct secret it is a success. Surely dropping (or sabatoging) the pings would only get a malicious node could only negatively effect him; that is, it would only get him stuffed into his own 'network' box by us. > How do you prevent an attacker from > forwarding pings but dropping (selected) requests? I think that this is a fundamental problem even now. Whereas dropping the request would cause a backoff, I presume you mean DNF. This amounts to allowing a node to be labeled as in the network they are actually in, but they play unfair. > The attacker isn't necessarily interested in creating a dungeon > (certainly > not a detectable one) - he might just want to control a large region > of the > key space, either to monitor it or to censor selected keys, while > responding normally to other requests. But creating a new subnet does not control a keyspace region, particularly if it is correctly identified as a subnet. What it does is create a duplicate keyspace region, which may-or-may-not be routed into (presently the code is undecerning). > >> Processing in order of largest-group first: for all these groups, we >> advertise the most-common network id in that group towards all of >> them; unless that id is taken by a larger group (already processed), >> in which case a random id is assigned to that group (or the next-most >> common?). Which is to say every 'group' has a distinct network id >> (assigned & advertised by-us) favoring what they are advertising >> already. > > Sorry, I don't understand the purpose of advertising - are nodes > supposed > to pay attention to what we think their network ID should be? What > if an > attacker sends hundreds of different network IDs to each node, or > hundreds > of copies of the same network ID that appear to originate from > different > nodes? No, no... advertising in the sense that a network location is presently 'advertised' it is a single value that we remember per-peer, and not a thing to be flooded or forwarded. For each peer-node we would now additionally need to remember four things: (1) a CRAM-UID, (2) a CRAM-Secret, (3) a network-id-they-advertise, and (4) a network-id that we assign to them. >> We choose our network id based on successes; I don't think it even >> matters specifically how... Since all peers are advertising >> (possibly- >> different) ids to us, we take the most-common id among peer's from >> which >50% of our successes come from (for example). > > Anything that uses "most common" as a criterion is vulnerable to > flooding > and/or Sybil attacks. True, and in this case they would need to control a large number of our peers. This is already a known problem. Having a majority of peers and then artificially delaying response times, for example, will absolutely DoS a node (MAX_PING_TIME/bug#2006). >> I suspect it >> would work even if we simply took the network id advertised to us by >> the peer of our last successful request. > > An attacker could respond normally to requests but advertise a > different > network ID each time to prevent network IDs from stabilising. Not so. Good-behaving nodes would only re-examine there network id every 'x' minutes/seconds, without respect to when or how often their peers change the network id that they advertise. >> We would need (1) a routing table, and (2) to be notified of other >> networks somehow. > > Sorry to be negative but I don't think we're going to come up with a > back-of-an-envelope solution to this problem. Routing in untrusted > networks > has received a lot of research attention recently because the US > military > is starting to deploy ad hoc wireless networks, and so far there are > no > good solutions that don't depend on a trusted certificate authority. > Here's > a review of some of the relevant literature: > > http://www.cs.ucl.ac.uk/staff/mrogers/literature-review.html#robust-routing > http://www.cs.ucl.ac.uk/staff/mrogers/literature-review.html#anonymous-manet Admittedly, the routing-to-a-distant-network portion is the weakest portion of this idea; Matthew has called it 'escape routes'. >> And since there could be a *lot* of junk-network >> information, we just keep a psuedo-LRU of recently seen network ids >> (where multiple peers having the same network success: favoring the >> peer with the more recent success than higher htl? but probably >> promoting them both). Keep, say, 100-1000 network ids. > > An attacker could respond normally to most requests, advertising a > different network ID each time to flood the LRU. Correct, and any node in the chain could manipulate the incoming network ids from a distant success. I suppose that if this were to be implemented as proposed, we would need a separate LRU per peer, and some kind of probabilistic filtering with respect to the net id's we forward (e.g. only if it is our network-id or is "established"?). -- Robert Hailey _______________________________________________ Devl mailing list Devl@freenetproject.org http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
