Okay, first lets explain why we have to do it this way. We need to decide: - a random number - the product of the distances from each of the two nodes to each of their neighbours, at present, and after the proposed swap
We can either send the locations of the neighbours, or we can send the product: [16:09] <toad_> A sends B: my ID is X, my product with my current location is Y [16:09] <toad_> B sends A: my ID is X1, my product with my current location is Y1, my product with your current location is Z1 [16:10] <toad_> A sends B: my product with your current location is Z (they would also exchange random numbers) The problem with doing it this way is that either side can cheat very effectively. A sends X = what he wants B to swap to, Y ~= 1.0, then he sends Z ~= 0. This will force the swap to complete regardless of which B he happens to be connected to. Now, with the currently implemented algorithm, cheating is much harder. Because A has to choose what to say about not only its location but also the locations of its neighbours, before sending the SwapRequest, it has to target a specific node, then have its fictitous neighbours take locations very close to the target location. If it hits the right node, the swap will definitely succeed, but if it hits the wrong node, the swap will probably fail. And since SwapRequest's are randomly routed, unless he is targeting an immediate neighbour there is a very low chance of hitting the right node. Because we limit the number of swap requests that can be sent on a given link in a given amount of time, this greatly reduces the attacker's effectiveness. On Wed, Mar 15, 2006 at 03:01:03PM +0000, Matthew Toseland wrote: > The location swapping algorithm, as implemented at present, ALREADY > exposes the network topology. We are constantly sending swap requests > around the network; these are routed for 6 hops. Once accepted, both > sides send a list of their adjacent locations (on the first pass they > send a hash of these), and their own location. These are not encrypted, > as they are to an unknown target; they are randomly routed for those 6 > hops. > > We could do a diffie-hellman setup, but even if this was successful - > and it is of doubtful value as it can easily be subverted given that we > are random routing - a node would still be able to view all the swap > requests that it accepted. And a hostile node could accept all swap > requests which passed its way. > > Reducing the swap frequency is also of debatable value. There will > inevitably be periods of high swapping due to churn on the network, and > if there aren't any the attacker can create one. Even if he doesn't, if > he simply waits and listens to the low level traffic this is probably > still enough to give him a good idea of the network topology - even with > periodic node location randomization! > > So the bottom line is that it is already possible to reconstruct the > topology of the network and the keyspace locations of the nodes on it. > IIRC swap requests only take into account connections which are actually > online (this seems reasonable on the grounds that if a connection is > offline it is of little use; the counterargument is obviously that we > are trading short-term optimality for churn), meaning that we can even > detect node/connection uptimes! > > > What, if anything, should be done about this?! > > Questions: > - Is it a big deal for the network topology within a radius of 6 hops to > be exposed to an internal attacker? Well, if he can do traffic analysis > on the underlying fabric, then maybe. Also he may be able to determine > which nodes are worth targetting, since he knows the locations; this > may also help him in targetting a specific location, maybe with bogus > swap requests. > - On the other hand, if all this is public, we can do a good deal of > enforcement and deviancy detection. We can determine when nodes are > not following the swap protocol, and identify when nodes are behaving > in a suspicious way. > - Is it a big deal for node/link up/down status to be revealed to an > internal attacker? Surely! Presumably the best fix is to, in a swap, > show all reasonably reliable connections, rather than all currently > open connections... We need a heuristic for this; it will also help to > stabilize the network, although at the cost of some optimality. > - Are there other possible practical formulations of the > Metropolis-Hastings algorithm? > -- > Matthew J Toseland - toad at amphibian.dyndns.org > Freenet Project Official Codemonkey - http://freenetproject.org/ > ICTHUS - Nothing is impossible. Our Boss says so. > _______________________________________________ > Tech mailing list > Tech at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/tech -- Matthew J Toseland - toad at amphibian.dyndns.org Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20060315/9db64fdc/attachment.pgp>
