Swapping improvements

The current swapping algorithm is relatively slow: it stabilises in O(n) swap attempts per node. Vive has written a paper∞ explaining our swapping algorithm and proposing several significantly faster algorithms. However, there is much work to be done before they can be implemented - more simulations, for a start.

It has long been known that the swapping algorithm is vulnerable to bogus swap requests generated by an attacker. Worse, simply by users joining the network and then leaving, we have a similar effect: Locations end up too sparsely distributed across the keyspace, sticking too closely together; locations which are far away from the main blobs get lost, and so it worsens.

We periodically randomize each node's location (Oskar first suggested this around the time we started implementing Freenet, but it wasn't implemented until late 2007). This seems to effectively prevent join-leave churn from causing such problems, but probably would not foil an active attack.

See http://crisp.cs.du.edu/pitchblack/∞ and the paper "Routing in the Dark: Pitch Black" by Evans, GauthierDickey and Grothoff, Colorado Research Institute for Security and Privacy, University of Denver, 2007 (published in ACSAC).

Another existing countermeasure is a commit/reveal protocol: Swapping is a four-message process, we send in the first two a hash of the data which we will reveal in the last two. So by the time we know what the locations of the other side are, it's too late to pull out: we can only timeout, or accept the swap and then not change our location.

A countermeasure which has been discussed is to attempt to "enforce" swapping: make it harder for an attacker to make up completely bogus swap requests by publishing the local network topology for N hops, including locations. This will be necessary (minus locations) for premix routing, and given premix routing it won't be a big risk to privacy (and anyway normal swap requests expose that info albeit less reliably). So if an honest node is adjacent to an attacker node, and it sees the node accept a swap, and the swap succeeds, yet the attacker node doesn't change its location in some period, it can complain to the node's peers. Of course the attacker might just only send the location change to that node - but if it does, it can forward it to the node's peers when complaining. This works even if the honest node is a few hops away. Location change announcements could refer to the specific swap that succeeded, and random verification would be possible. It would also be feasible to ensure that the claimed locations of peer nodes are not completely bogus (or at least are consistent with the public view of the network). Whole potentially malicious subnetworks (which presumably have relatively poor connectivity to the rest of the darknet) would need to be segregated off by the subnetwork detection code. Obviously this only works on Darknet.

Recent simulations suggest it may even be possible to resurrect NGR by combining location information with expected fetch times. Stay tuned!

See IRCLog090807Swapping.