[freenet-dev] New approach to tunneling

[Matthew Toseland]

On Thursday 12 June 2008 23:02, Matthew Toseland wrote:
> I and others have been recently coming to the conclusion that premix routing 
> is not the next generation security enhancement that we had hoped it would 
> be.
> 
> The objective here is to make various attacks harder. The two attacks we are 
> most interested in:
> - Correlation attacks: What is my peer doing? This relies on recognising a 
> splitfile (or a series of FMS posts for example) and doing statistics on it 
> to see how likely it is that the peer is the originator.
> - Adaptive search: The attacker picks up a few requests from a splitfile 
(e.g. 
> a big insert). Each one gives him a predecessor sample, and the precise key 
> being fetched gives him a vague idea of where the originator is. On opennet, 
> and to some degree on darknet, he can use this information to move closer to 
> the target. If he is successful, the number and accuracy of samples 
increases 
> as he moves closer to the target, leading to exponential growth in the 
> effectiveness of the attack. Hence for a big insert or long lived identity 
> there's a good chance of finding the target in a relatively short period.
> 
> A partial solution to the latter is the recent obfuscated inserts proposal. 
> This prevents the attacker from moving towards the target until after the 
key 
> for the insert has been announced (or the top block inserted in the case of 
a 
> well known SSK), even if he can guess the content. But he may still be able 
> to get a good idea of the originator's location if he has logged enough 
> blocks.
> 
> Encrypted tunnels (e.g. premix routing) would also solve the datastore 
probing 
> attack mentioned in The Register a while ago, and may enable some 
significant 
> optimisations such as Bloom filters (which would likely save quite a few 
hops 
> on many requests).
> 
> Basically, premix routing as we have envisaged it up until recently would 
> divide the (darknet) network up into semi-permanent cells. Within each cell, 
> all nodes are reasonably densely/directly connected, and all nodes are kept 
> up to date on the status of other nodes in the cell. When we make a new 
> request, we choose two nodes from the cell at random and create an encrypted 
> tunnel from ourself (the start point) to the first node and then to the 
> second node. Then the requests exit the tunnel and begin their journey. 
> Hence, a request from one node in a cell is indistinguishable (we hope) from 
> a request from any other node, and you have a definite anonymity set: the 
> cell.
> 
> The main disadvantages:
> - It will cost around twice the diameter of the cell, in hops, at the 
> beginning of a request. Note that this is an encrypted tunnel so caches 
> cannot be checked during these hops.
> - It only protects the beginning of the request, *not* the main request 
> routing phase. You can hide within the cell, but the attacker will 
eventually 
> be able to trace your requests back to the cell. If the cell is small 
enough, 
> and/or the attacker powerful enough, he may simply seize every node in the 
> cell...
> - We can enlarge the cell but only at the expense of increasing the number 
of 
> hops at the beginning of the request, as well as the required co-ordination 
> traffic.
> 
> Hence a better approach is needed. Michael Rogers and I discussed this 
fairly 
> extensively at the anonymity summit on Monday. One paper that was presented 
> there showed fairly convincingly that no current structured peer to peer 
> system is likely to achieve better than c/n security, so that may be an 
> acceptable goal. By this I mean a roughly c/n chance of a tunnel being 
> compromised given that c nodes out of n have been compromised. Tor (not a 
> structured network, every node knows about all nodes) achieves roughly 
> c^2/n^2 in theory however there are attacks that may reduce that to c/n.
> 
> Unencrypted tunnels:
> 
>  We would simply bundle a load of requests together and route them together 
> (randomly, or to a random location) for a few hops. After that, they go on 
> their way as normal. If the attacker doesn't manage to see the requests 
> during the tunnel phase, instead of getting one predecessor sample for every 
> request (4G insert = 270,000 requests), he would get one predecessor sample 
> for each tunnel, which hopefully would carry very many requests. However, if 
> he controls any of the nodes involved in the tunnel setup (probability 
around 
> [tunnel length] * c / n), he gains a much stronger predecessor sample. One 
> advantage with unencrypted tunnels, apart from simplicity, is that we can 
> check the datastore on each node on the tunnel; on the other hand, we can't 
> use Bloom filters and it doesn't solve The Register's datastore probing 
> attack as we will still have to cache local requests locally.
> 
> Encrypted tunnels via rendezvous at a location: 
> 
> We would create a key, split it into 2 or 3 parts (which can be XORed 
together 
> or concatenated to recover the original), and choose a location and a unique 
> ID. The first part would be routed directly to the target location. The 
> second and third (or more) parts would be random routed for some hops and 
> then routed to the target location. Once they exit the random routing phase 
> they look exactly the same as the first part. Each "anchor" continues until 
> it rendezvous's with the others, or it runs out of hops (randomly or with an 
> HTL or some hybrid). If all parts meet, a tunnel completion message 
> (including the hash of the complete key) is sent back to the originating 
> node, along the shortest path (either explicitly identify the first one, but 
> we lose some data; or have a random number which starts the same for all 3 
> but is incremented on each hop; or even go by the first one). Then we use 
> this to set up an encrypted tunnel to send requests through. We should have 
> an anonymity set roughly equal to the whole network. One problem is that we 
> may have to go a significant number of hops. In terms of attacks, we give 
the 
> attacker more location samples (on the direct-routed path), and more 
> predecessor samples (on the random-routed prefixes). That's the main 
> disadvantage: the search will visit lots of nodes, giving the attacker many 
> opportunities to intercept it. If he manages to get all the pieces, he can 
> decrypt the requests.

IMHO we should, in the near future, try a prototype of this. It would not be 
difficult to implement something that attempts the rendezvous described 
above, without actually setting a tunnel up, and with reporting the number of 
hops taken. Of course, the tunnels may be too long to be practical at the 
moment. The "Routing enhancement" thread proposes a possible solution to 
this, it would certainly be interesting to compare before and after.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://emu.freenetproject.org/pipermail/devl/attachments/20080612/0fae371f/attachment.pgp