On Tue, Sep 4, 2012 at 12:29 PM, Matthew Toseland
<toad at amphibian.dyndns.org> wrote:
> The paper, "A Traceback Attack on Freenet" ( 
> http://www.ee.hawaii.edu/~dong/traceback/1569649421.pdf ) presents a new 
> attack which relies on being able to 1) quickly connect to a node via 
> announcement and 2) Query it to determine whether a given request UID has 
> visited this node. The attack allows them (prior to 1411) to trace a request 
> back to its originator.
> 1411 makes this dramatically more difficult by not tracking UIDs of completed 
> requests. However, it may still be possible to do some variant of this 
> attack, and we should improve things further.
> =========
> Several kinds of requests were easily exploitable for #2. All that is needed 
> is:
> - Send a bogus request, which will be parsed lazily.
> - If it's not been seen, it will be Accepted, and then fail because it fails 
> to parse, so it won't pollute the attacker's search space.
> - If it has been seen, it will be RejectedLoop.
> Several kinds of requests allowing this have been fixed:
> - Old-style probe requests (removed)
> - Announcements (fixed)
> However, for inserts, especially CHK inserts, this does not appear to be 
> easily fixable:
> A -> B: I want to do an insert
> B -> A: Accepted, send me the data
> A -> B: Here is the data ...
> B routes the insert onwards once the data transfer starts.
> The data transfer fails, so B *stops routing the insert*, as do downstream 
> nodes.
> For SSK inserts, we don't route onwards until we have all 3 components (data, 
> headers, and pubkey). Sometimes we don't need to send the pubkey, and given 
> there are a lot more SSKs than CHKs,
> In both cases, we currently accept or reject the insert before we have all 
> the data.
> Possible solution for CHKs:
> - Always route to the end even if the data transfer fails. Cost relatively 
> low as we don't need to wait for the data transfers, so it's close to a 
> normal failing request. Messy to implement but only because CHKInsertSender 
> is messy. Also we'd have to turn off kill-on-fatalTimeout (temporarily) 
> before deploying this. AND
> - Combine the DataInsert with the initial InsertRequest. All it really 
> includes is the transfer UID. However do not start sending the data until we 
> get the Accepted (may require that we tolerate a slightly longer timeout on 
> the first block received). Slight improvement in latency, so this is actually 
> beneficial; no bandwidth wasted.
> Related issues for CHKs:
> - One day, we may want bulk inserts and requests to transfer and verify the 
> whole block before relaying. The basic advantage is we could then do a kind 
> of non-onion mixing to confuse traffic analysis.
> Solution for SSKs:
> - Don't check the UID until after we have received all the data.
> Related issues for SSKs:
> - We don't send the pubkey unless asked for it in the accepted message. This 
> is marginally bad in that it allows a relatively easy way to probe the 
> datastore for an SSK pubkey. On the other hand it's a useful bandwidth 
> optimisation, especially given the sheer numbers of SSK requests, and remote 
> datastore probing is trivial anyway (and not much use given we don't store 
> locally requested stuff in it).
> - We could always send the pubkey, or just send it when doing a realtime 
> request.
> - Currently we have two ways to send an SSK request - one just sends the key, 
> the other sends the data and headers as well. We could always send the data 
> and headers; this would reduce latency but would waste bandwidth when we are 
> rejected. So it may make sense for realtime inserts only. Obviously we'd want 
> the message to indicate whether to expect such data, so we can get rid of it 
> even if we reject.
> More general issue:
> Maybe we should check for overload before we check for loops? This would 
> require some new (and slightly hacky) structures, and would mean we have to 
> get rid of or alter some less important current load heuristics. But it would 
> allow us to avoid wasting bandwidth in the case of SSK inserts (we check for 
> overload, send accepted, then wait for all the data, then check for loops, 
> then relay), and would reduce the amount of information leaked in all cases.
> Overload is much more common than loops, although some small darknets may 
> have a lot of loops.
> Overall impact of UID-level fixes: The group of nodes with UIDs equal to the 
> original request is clouded by the attacker's requests. He might still be 
> able to make some progress but only if he correlates the same procedure for 
> multiple nodes. In which case he's probably better off doing some of the 
> other known opennet attacks, or combining it ... However, see Ian's solution.
> Opennet/Announcement:
> ===============
> Section IIIA:
> - Perverse effects of the current replacement heuristics? The dominant 
> heuristic is that any of the neighbour categories has served at least 10 
> requests... This means if you do requests near the node's location you can 
> get your node accepted. Can we improve on this? I do think the principle of 
> limiting by the number of requests makes sense - we don't want the nodes to 
> get dropped immediately after their 5 minute grace period expires, by the 
> first request that happens and tries to path fold, or by announcements? One 
> thing we could do would be make sure the inter-accept interval is more than 
> the average request time?
> We could cripple announcement, to make it a bit slower to reach targeted 
> nodes. However this would reduce first time performance. Freenet 0.4/5 used a 
> collaborative random number generation algorithm and hoped the node would 
> migrate to where it should be, I don't think it worked well. We could reduce 
> the precision of announcement a bit perhaps, as a partial solution, but again 
> it would reduce first time performance *and* it would reduce performance on a 
> slashdot.
> Paper's solution
> ==========
> The paper suggests we get rid of the various different failure modes. 
> Unfortunately we need most of them:
> - RejectedOverload: We need this to be distinct for load management.
> - RouteNotFound: This is non-fatal, and reduces the number of hops.
> - DataNotFound: This is fatal, and terminates the request.
> Combining RejectedLoop with RNF might be possible. I'm not sure whether or 
> not there would be enough information to figure out when it's a loop and when 
> it's a genuine RNF; although the attacker may know your peers, lots of things 
> can affect routing, e.g. per-node failure tables.
> We definitely need to reduce the number of distinct failure messages.
> Purely random termination (no HTL) might allow for major simplifications, as 
> well as reducing the information on the requests, but it would greatly 
> increase the variability of request completion times (making timeouts more 
> difficult), and might undermine some of the more important optimisations such 
> as per-node failure tables. (I'm not sure whether that's absolutely certain, 
> as it acts only after multiple requests...)
> Ian's solution
> ========
> Get rid of RejectedLoop. Always accept, never route to the same peer as we've 
> already routed that UID to, and RNF if we can't find any more nodes to route 
> to.
> I am worried about what this could do to routing. I don't think we should 
> implement it without some theoretical/simulation analysis? I can see that it 
> might improve things, but we need more than that given it could be fairly 
> significant.
> However it is the most comprehensive way to get rid of these problems, and 
> might have the least performance impact.

I like this solution. It was my immediate reaction to the problem description.

It will make local minimums harder to escape. Basically, you prevent
duplicating an edge along a route, rather than a node. That's a much
less powerful approach to avoiding minimums. I suspect FOAF routing
helps a lot here, but that seems like it might be problematic from a
security perspective as well.

In general, making routing better (link length distribution, mainly)
will make this less of an issue; local minimums are a problem that
results when you have too few short links, which is the current
problem with the network.

> ======
> Best solution is to make darknet easy!
> We also need to fix darknet. That means fixing Pitch Black.

Among other problems. Location stability interactions with datastore,
and opennet/darknet hybrid nodes, in particular.

It also means we need to focus on the user experience when setting up
darknet, which currently sucks.

Evan Daniel

Reply via email to