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
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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Hello Paul,
Nice to hear the issue and our work is of interest to you. I see you already noted the link to my full thesis, but meanwhile I can already answer your question about using somewhat overlapping circuits. This was indeed not considered in the thesis but is something I've have been thinking of in the past few weeks. The method considered was along the lines what you propose, where the client would choose at random if to assign a new stream to an older or a fresher circuit. The old circuit would be kept open, as you propose, for a randomized period of time. This would smoothen the transition from a circuit to another one and should make it much more difficult / impossible to use this as a distinguishing feature. Combined with randomizing the circuit lifetimes, it's likely this would sufficiently negate the attack. The downside I see is that you spend slightly more resources building overlapping circuits, but I can't say if it would have any significant impact on the relays. I'm under the impression some work is already underway to randomize the circuit lifetimes, is this correct?
- Otto
2014-09-19 16:25 GMT+03:00 Paul Syverson paul.syverson@nrl.navy.mil:
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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-
Otto Huhta -
Paul Syverson