On Thursday 20 December 2007 13:03, Michael Rogers wrote: > The second part of Nikita Borisov's thesis [1] is an anonymising DHT > that does something similar to your proposal: each lookup is forwarded > randomly for a small number of hops, then forwarded greedily to the > target. He uses the mixing time of the graph to show how many random > hops are necessary to make it equally likely that any node was the > initiator. His DHT is based on Koorde [2] because it has the fastest > mixing time of any DHT. I don't know how to work out the mixing time of > Kleinberg graphs but I guess Oskar will, in which case we can work out > how many random hops we need, at least in an ideal network.
It probably depends on how you route. If you route randomly on each hop I'd expect to on average not get very far, because *most links are short links* on a small-world network. On the other hand if you choose a random location and consistently route towards it you should have an equal chance of ending up anywhere on the network. The catch is that if you route lots of requests to different random locations, and the attacker can connect the requests, he can gradually narrow down the locations you could have started in. One big problem with random routing is if on average we random route for 5 hops, there is a 20% chance that any specific request an attacker receives (which is still in random routing) originates on its direct predecessor. So your effective anonymity set is pretty poor when you factor in the fact that it will probably be possible to connect different splitfiles (tunnel IDs) together, even if you use one tunnel ID for each splitfile. Premix routing solves this, but at the expense of a small and predictable anonymity set once the attacker has located the cell. The attacker doesn't necessarily know that a request is forwarded from the local premix cell, he can only guess based on correlation of linked requests and their locations. If he can correlate enough requests, and is directly connected to one of the cell (or a few hops away and gets a LOT of easily linkable requests), he can be fairly confident of that node being the originator of the request and therefore that the real originator is in the cell. The question then is how big can we make a cell? Part of the problem is that we need to traverse it twice before starting to route, although we will be able to compute optimal paths in theory (subject to traffic conditions!). The other part is that we need to keep up to date info on each node and each connection broadcast across the cell. On a cell of 10,000 nodes, if on average each node goes down once a day, and this impacts on 10 other nodes, we have ~ 100,000 messages ... perhaps hundreds of megabytes, so it may be that cells this big are feasible. In which case, we're getting somewhere: Arresting 10,000 people to find one is going to be problematic even in the nastiest of places, especially if some of them are in other countries. And it'd be a lot of work to get to the point of identifying the cell, if we're clever, although IMHO it will be possible. -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 189 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20071221/12cb7c9b/attachment.pgp>
