Matthew Toseland wrote:
> PROPOSAL:
> Add a flag RandomRoute. This may be set when a request starts (up to the
> user). There is a 50% chance of its being unset. So on average it adds 2 hops
> to the journey - but there is a small chance of requests going much further
> than that. The advantage is that it greatly obscures the picture for a
> distant attacker, by starting off in a somewhat random part of the keyspace.
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.
> NOTES:
> We could not overload HTL=10 because HTL is reset to 10 every time we get
> closer to the target: we *do not* want to go into random route mode just
> because we got a bit closer to the target!
Yup, IMHO we should get rid of the hop counter and use a weighted coin
to decide when to switch from random to greedy forwarding, and another
weighted coin to decide when the request has run out of hops. (I realise
this will sometimes lead to long paths, but at least we can analyse how
much information it leaks. AFAIK that's not possible with the current
hop counter.)
> PROBLEMS:
> It reveals that the request is relatively early. This will make local
> correlation attacks even easier. So we should do it *after* we have premix
> routing, at which point that won't be a problem any more.
This could actually be used in place of premix routing: instead of
constructing cells we use random "tunnel IDs". Messages belonging to the
same splitfile are marked by their initiator with the same tunnel ID.
During the random phase, each hop chooses the next hop or switches to
greedy forwarding pseudo-randomly based on the tunnel ID, so messages
with the same tunnel ID follow the same pseudo-random path and switch to
greedy forwarding at the same point. Thus no predecessor attacks are
possible during the random phase. Predecessor attacks during the greedy
phase will lead the attacker to the last hop of the random phase, which
will provide no information about the location of the initiator if the
number of random hops is sufficient.
Tunnels will sometimes break due to churn, but the same can happen with
cells - no matter what system we use, churn will always allow
predecessor attacks because it forces initiators to choose new paths.
Cheers,
Michael
[1] http://www.crhc.uiuc.edu/~nikita/papers/phd-thesis.pdf
[2] http://iptps03.cs.berkeley.edu/final-papers/koorde.ps
_______________________________________________
Devl mailing list
Devl@freenetproject.org
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
