[tor-dev] Attack linking Tor circuits

[Paul Syverson]

Sorry. I thought I was seeing the full message on my screen but
didn't notice there were a few more lines. I'll check out your thesis.
-Paul

On Fri, Sep 19, 2014 at 09:25:02AM -0400, Paul Syverson wrote:
> Hi Otto,
> 
> This looks cool and complements nicely research that I have
> back-burnered for a long time now around what middle relays can
> observe from guards and how this is affected by the number of guards,
> amongst other things. The plans to move to a single guard are indeed
> well underway, so your work is timely. 
> 
> You considered randomizing circuit lifetime, but did you also consider
> the mitigating effect of randomizing circuit lifetime overlap? That
> is, if clients did not mostly use exactly one circuit at a time but
> continued making new connections for a (random length) period over an
> existing circuit even after they started using a new circuit how that
> would affect things?  It sounds like this was not considered.  I have
> similar timing questions about circuit build times, although for
> pre-emptively built circuits I would think there is a likely advantage
> to some synchronization and mixing across the network.  Anyway cool
> stuff. I'd like to hear more about it.  Are there drafts of your work
> available?
> 
> aloha,
> Paul
> 
> On Fri, Sep 19, 2014 at 01:10:06PM +0300, Otto Huhta wrote:
> > Dear Tor developers,
> > 
> > 
> > 
> > We’ve been working on an MSc Thesis project looking into an attack that
> > links different Tor circuits back to the same user, using only information
> > available to a Tor middle node. We’ve discovered that an adversary can
> > quite accurately determine if two consecutive circuits are used by the same
> > user just by looking at when these circuits are built and destroyed or when
> > they begin and stop relaying traffic. This is mainly the result of the
> > fixed 10 minute circuit lifetime and the fact that the transition to using
> > a new circuit is quite sharp. According to our measurements, circuits
> > belonging to the same user are built at very close to 10 minute intervals.
> > Also, when one circuit stops relaying traffic another one suddenly becomes
> > active, at almost the very same moment.
> > 
> > 
> > 
> > Thanks to these properties we could train a classifier to quite efficiently
> > identify matching pairs of circuits (9% EER). We looked into the threat
> > posed by this attack to Tor users and concluded that because of entry
> > guards the threat is real, given that an adversary can control a
> > significant portion of middle node traffic. Finding matches among all
> > possible Tor circuits would result in too many false positives but thanks
> > to entry guards an adversary can focus only on circuits built through these
> > specific nodes and quite efficiently determine if two circuits belong to
> > the same user. Possible plans of moving to using only a single guard node
> > make the situation much more severe: we concluded that for a user picking a
> > slow guard node, the adversary can find almost all circuits belonging to a
> > same user (again assuming control of a large portion of middle node
> > bandwidth). We thus see that before moving on with any such plans, one
> > should consider the effect of our findings on the threat posed by a middle
> > node linking user circuits.
> > 
> > 
> > 
> > As a final note, we considered the effects of randomizing the circuit
> > lifetime (e.g. between 5-15 minutes) to mitigate this threat but concluded
> > that it would not necessarily solve the problem. The most prominent feature
> > linking two circuits together seems to be the time difference between
> > traffic ending on one circuit and beginning on another circuit, and this
> > link cannot be broken by varying the circuit lifetime. However, if someone
> > were to devise such a modification, we would be happy to re-run our tests
> > to see what kind of an effect this would have on the success rate of an
> > adversary.
> > 
> > 
> > 
> > For those interested in our findings, the full thesis Linking Tor Circuits
> > can be found at:
> > 
> > http://www0.cs.ucl.ac.uk/staff/G.Danezis/students/Huhta14-UCL-Msc.pdf
> > 
> > 
> > 
> > Best regards,
> > 
> > Otto Huhta, UCL
> 
> > _______________________________________________
> > tor-dev mailing list
> > tor-dev at lists.torproject.org
> > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
> 
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev