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.
> REQUEST UIDS
> Several kinds of requests were easily exploitable for #2. All that is needed
> - 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
> 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
> - 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.
> 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
> 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
> 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
> 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.