Defending against guard discovery attacks by pinning middle nodes
Hey Nick, this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001). I think we have some ideas on how to offer better protection against such attacks, mainly by keeping our middle nodes more static than we do currently. For example, we could keep our middle nodes for 3-4 days instead of choosing new ones for every circuit. As Roger has suggested, maybe we don't even need to write the static middle nodes on the state file, just use new ones if Tor has restarted. Keeping middle nodes around for longer will make those attacks much slower (it restricts them to one attack attempt every 3-4 days), but are there any serious negative implications? For example, if you were unlucky and you picked an evil middle node, and you keep it for 3-4 days, that middle node will always see your traffic coming through your guard (assuming a single guard per client). If we assume you use a non-popular guard node (with only a few clients using it), the middle guard might be able to think "Ah, the circuit that comes from that guard node is always user X" making your circuits a bit linkable from the PoV of your middle node. What other attacks should we be wary about? Maybe partitioning attacks based on client behavior? And how should we move this forward if we decide it's worth it? Should we start writing a Tor proposal? Thanks!
On Fri, Jul 11, 2014 at 01:44:36PM +0300, George Kadianakis wrote:
Hey Nick,
this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001).
I think we have some ideas on how to offer better protection against such attacks, mainly by keeping our middle nodes more static than we do currently.
For example, we could keep our middle nodes for 3-4 days instead of choosing new ones for every circuit. As Roger has suggested, maybe we don't even need to write the static middle nodes on the state file, just use new ones if Tor has restarted.
Keeping middle nodes around for longer will make those attacks much slower (it restricts them to one attack attempt every 3-4 days), but are there any serious negative implications?
For example, if you were unlucky and you picked an evil middle node, and you keep it for 3-4 days, that middle node will always see your traffic coming through your guard (assuming a single guard per client). If we assume you use a non-popular guard node (with only a few clients using it), the middle guard might be able to think "Ah, the circuit that comes from that guard node is always user X" making your circuits a bit linkable from the PoV of your middle node.
And similarly at the exit node: the exit will now know that circuits coming from the same middle are more likely to be the same client. That's a little more worrying to me than the above. - Ian
11.07.2014 14:31, Ian Goldberg:
On Fri, Jul 11, 2014 at 01:44:36PM +0300, George Kadianakis wrote:
Hey Nick,
this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001). (...)
HS stands for hidden-service, if I'm not mistaking.
And similarly at the exit node: the exit will now know that circuits coming from the same middle are more likely to be the same client. That's a little more worrying to me than the above.
If the proposed change applies to hidden-services alone, "regular" usage of Tor (Client > Guard > Middle > Exit > Destination) is not affected. My reading was that the middle node for hidden-service connections are kept longer. Could anyone please clarify the proposed change? Regards, Sebastian G.
"Sebastian G. <bastik.tor>" <bastik.tor@googlemail.com> writes:
11.07.2014 14:31, Ian Goldberg:
On Fri, Jul 11, 2014 at 01:44:36PM +0300, George Kadianakis wrote:
Hey Nick,
this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001). (...)
HS stands for hidden-service, if I'm not mistaking.
And similarly at the exit node: the exit will now know that circuits coming from the same middle are more likely to be the same client. That's a little more worrying to me than the above.
If the proposed change applies to hidden-services alone, "regular" usage of Tor (Client > Guard > Middle > Exit > Destination) is not affected.
My reading was that the middle node for hidden-service connections are kept longer.
Even though guard discovery attacks affect mainly (only?) HSes, this is probably not a change that could only be applied to HSes. Mainly because it's easy for an entry guard to learn whether a client has static middle nodes or not, and hence distinguish the HS circuit from a normal Tor client circuit. Also, the middle guard itself will probably be able to do this distinction too. However, to be honest, those actors can probably already distinguish between normal circuits and rendezvous circuits, by looking at frequency and size of Tor cells passing. As always, more research is needed...
On Fri, Jul 11, 2014 at 08:31:05AM -0400, Ian Goldberg wrote:
On Fri, Jul 11, 2014 at 01:44:36PM +0300, George Kadianakis wrote:
Hey Nick,
this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001).
I think we have some ideas on how to offer better protection against such attacks, mainly by keeping our middle nodes more static than we do currently.
For example, we could keep our middle nodes for 3-4 days instead of choosing new ones for every circuit. As Roger has suggested, maybe we don't even need to write the static middle nodes on the state file, just use new ones if Tor has restarted.
Keeping middle nodes around for longer will make those attacks much slower (it restricts them to one attack attempt every 3-4 days), but are there any serious negative implications?
For example, if you were unlucky and you picked an evil middle node, and you keep it for 3-4 days, that middle node will always see your traffic coming through your guard (assuming a single guard per client). If we assume you use a non-popular guard node (with only a few clients using it), the middle guard might be able to think "Ah, the circuit that comes from that guard node is always user X" making your circuits a bit linkable from the PoV of your middle node.
And similarly at the exit node: the exit will now know that circuits coming from the same middle are more likely to be the same client. That's a little more worrying to me than the above.
Right. Lasse and I suggested and explored the idea of layered guards when we introduced guards. There are lots of possibilities here. You can have a set of midguards per guard. Don't remember if it made it into the paper, but when Roger, Nick, Aaron, and I did the downhill paths paper we also talked about having a rotation rate for choice of middle guards that was faster than for guards but not simply a new weighted-random midnode for each circuit. Gotta run. -Paul
Paul Syverson <paul.syverson@nrl.navy.mil> writes:
On Fri, Jul 11, 2014 at 08:31:05AM -0400, Ian Goldberg wrote:
On Fri, Jul 11, 2014 at 01:44:36PM +0300, George Kadianakis wrote:
Hey Nick,
this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001).
I think we have some ideas on how to offer better protection against such attacks, mainly by keeping our middle nodes more static than we do currently.
For example, we could keep our middle nodes for 3-4 days instead of choosing new ones for every circuit. As Roger has suggested, maybe we don't even need to write the static middle nodes on the state file, just use new ones if Tor has restarted.
Keeping middle nodes around for longer will make those attacks much slower (it restricts them to one attack attempt every 3-4 days), but are there any serious negative implications?
For example, if you were unlucky and you picked an evil middle node, and you keep it for 3-4 days, that middle node will always see your traffic coming through your guard (assuming a single guard per client). If we assume you use a non-popular guard node (with only a few clients using it), the middle guard might be able to think "Ah, the circuit that comes from that guard node is always user X" making your circuits a bit linkable from the PoV of your middle node.
And similarly at the exit node: the exit will now know that circuits coming from the same middle are more likely to be the same client. That's a little more worrying to me than the above.
Right. Lasse and I suggested and explored the idea of layered guards when we introduced guards. There are lots of possibilities here. You can have a set of midguards per guard. Don't remember if it made it into the paper, but when Roger, Nick, Aaron, and I did the downhill paths paper we also talked about having a rotation rate for choice of middle guards that was faster than for guards but not simply a new weighted-random midnode for each circuit. Gotta run.
I've been trying to understand how useful layered guards would be in the current Tor network purely from a Sybil attack perspective (even if we disregard the attacks that me and Ian mentioned previously in this thread). For example, let's assume a simplified 5% adversary. That is, an adversary whose relays have 5% chance of getting picked everytime we sample a relay for a Tor circuit [0]. This allows us to model relay sampling as a coin toss with Pr[head] = 0.95 and Pr[tail] = 0.05. We are going to toss the coin a few times and hope we never get tail. Also, let's assume that HS traffic correlation is easy if you control one of the relays of the HS circuit. I believe this is reasonable to assume, since the attacker can force the HS to send/receive traffic at any point [1]. And here is a server-side HS circuit: HS -> guard -> middle -> exit -> RP == Guard compromise attacks == So, let's start with guard compromise attacks (worse than guard discovery): Everytime we pick a new guard node, we have 0.05 of failing. Since #12206, we use a single guard node and we pick a new one every 2-3 months. This means that after a year (6 coin tosses), the probability of getting owned (guard compromise) is: Pr[at least one tail] = 1 - Pr[all heads] = 1 - 0.95^6 = 0.26~ This means that there is 1/4 chance that you will get owned after a year. This is not a particularly encouraging probability, but it's not the main point of this post and it's a powerful attack that lasts for a year, so let's just accept it. == Guard discovery attacks == Now, let's try to understand how much security layered guards can offer against guard discovery attacks. So let's say that along with our guard, we also pick 6 second-tier guards (middle nodes) that also get pinned for 2-3 months. This makes us look like this: -> middle1 -> middle2 HS -> guard -> middle3 -> <exit> -> RP -> middle4 -> middle5 -> middle6 (where the <exit> is chosen from the set of all relays (not static).) Since guard picks are independent, the probability of one of your 6 middles being compromised is the same probability as the one from the section above: of your main guard getting owned after 6 rotations. This means that every 2-3 months, your guard has 1/4 chance of getting discovered [2]. This means that after a few rotations your guard is guaranteed to be leaked. Some thoughts: a) To reduce the ownage probabilities we could pick a single middle node instead of 6. That will greatly improve guard discovery probabilities, and make us look like this: HS -> guard -> middle -> <exit> -> RP (where <exit> is chosen from the set of all relays) However, that will definitely degrade HS performance. I'm not sure if Tor relays are able to handle all that concentrated HS traffic. Specifically, the guards/middles that get picked by popular HSes will get flooded with traffic that is never accounted for in Tor's load balancing equations (since HS traffic is not counted) and they will get hammered both by HS traffic and regular Tor traffic. b) To reduce the ownage probabilities we need to extend the guard lifetime period. If we switched guards every 9 months, instead of every 2 months, we would have much lower chance of getting compromised in the long run. Actually, the probabilities would even look encouraging (but still nowhere near cryptographic quality). However, if guard discovery attacks are still possible, having guards last for 9 months gives the attacker a much larger window for attacks. Maybe we need to solve guard discovery attacks and increase the lifetime period at the same time? c) To reduce the ownage probabilities we need the Tor network to grow, so that it's harder for adversaries to reach high guard probabilities. The good thing with this is that we don't need to grow Exit nodes, since middle/guard nodes are also sufficient for HS purposes. Anyway, I believe that guard discovery attacks are very serious and I'm trying to think of a solution or improvement that could be incorporated in the new HS spec (rend-spec-ng.txt) so that it gets developed "soon". [0]: This is a powerful but realistic adversary. In compass, you can see many relays with guard probability between 1.2% to 0.5%. If the adversary plants 5-10 such relays, she can get to 5% total guard probability. If the adversary controls a few ISPs, the probability can increase further. [1]: The 'Trawling for Tor Hidden Services' paper successfully launches this guard discovery attack. See section 'VII. REVEALING GUARD NODES OF HIDDEN SERVICES'. [2]: Of course, you can reduce the attack probability by only picking 2 or 3 middle nodes per rotation period, but that will only make you last for another rotation period or two.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On 13/09/14 14:07, George Kadianakis wrote:
a) To reduce the ownage probabilities we could pick a single middle node instead of 6. That will greatly improve guard discovery probabilities, and make us look like this:
HS -> guard -> middle -> <exit> -> RP (where <exit> is chosen from the set of all relays)
However, that will definitely degrade HS performance. I'm not sure if Tor relays are able to handle all that concentrated HS traffic. Specifically, the guards/middles that get picked by popular HSes will get flooded with traffic that is never accounted for in Tor's load balancing equations (since HS traffic is not counted) and they will get hammered both by HS traffic and regular Tor traffic.
Hi George, Could you explain what it means to say that HS traffic isn't counted in the load balancing equations? Why is that so, and can it be changed if that would allow a more secure HS design? Cheers, Michael -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQEcBAEBCAAGBQJUFEODAAoJEBEET9GfxSfMkicH/RJFaXcI2fmgq9Qm9xV5C3Hj cTQ2DxsMFN8TmyusdesfzbD9+2TuDGNgIP9h773mgGzUsLll6RB8QNnLgL9kHDVF +I3KibOY7qfQ0Fu0auVeYj+9jNda+cvQggQuGBtHyiYZkbirrodOW7HfthL96RCJ HMw+HuSFFH/62idQjuVIbqjv88Ft1y5MgwRfplslkzc1aXO+bOOmHTf7qFXLXEq9 82X57rF1XLc/pTCCiHp3uVmJF5Dwp6unXBNPQf8L8yumTjgTfgLwYBkC8NOp6X+B Cty1cD6RalKrR++fGAmOifKHz73GAYG9VRSeAfSHYltIHHo0JRReXdLyAgUKrrU= =x/pl -----END PGP SIGNATURE-----
Michael Rogers <michael@briarproject.org> writes:
On 13/09/14 14:07, George Kadianakis wrote:
a) To reduce the ownage probabilities we could pick a single middle node instead of 6. That will greatly improve guard discovery probabilities, and make us look like this:
HS -> guard -> middle -> <exit> -> RP (where <exit> is chosen from the set of all relays)
However, that will definitely degrade HS performance. I'm not sure if Tor relays are able to handle all that concentrated HS traffic. Specifically, the guards/middles that get picked by popular HSes will get flooded with traffic that is never accounted for in Tor's load balancing equations (since HS traffic is not counted) and they will get hammered both by HS traffic and regular Tor traffic.
Hi George,
Could you explain what it means to say that HS traffic isn't counted in the load balancing equations? Why is that so, and can it be changed if that would allow a more secure HS design?
Hello Michael, this is an area that I don't really understand so I might be totally wrong, but Tor has the concept of bandwidth weights: https://gitweb.torproject.org/torspec.git/blob/ebc5a935ee4aa0c123829706671a3... where directory authorities calculate how much Guard/Middle/Exit bandwidth is available, and then they specify some parameters that clients use to load balance better. For example, if there is not much Guard bandwidth, clients will be asked to use Guards mainly for Guard purposes and not for Middle/Exit purposes. Now that we have reduced the number of guard nodes to 1, there are some HSes that receive lots of traffic and are hidden behind a single guard. That guard is probably receiving/pushing quite some HS traffic that is not really considered during client load balancing. So normal clients will keep on pushing that node to become their guard, and at the same time HS clients will push that node for HS traffic. If we now pin both the guard and the middle (as discussed in my post), now middle nodes that protect popular HSes, will also get a surge of HS traffic that is not accounted by Tor's bandwidth weight load balancing. I might be wrong in all the above.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On 13/09/14 15:34, George Kadianakis wrote:
Michael Rogers <michael@briarproject.org> writes:
Hi George,
Could you explain what it means to say that HS traffic isn't counted in the load balancing equations? Why is that so, and can it be changed if that would allow a more secure HS design?
Hello Michael,
this is an area that I don't really understand so I might be totally wrong, but Tor has the concept of bandwidth weights: https://gitweb.torproject.org/torspec.git/blob/ebc5a935ee4aa0c123829706671a3...
where directory authorities calculate how much Guard/Middle/Exit
bandwidth is available, and then they specify some parameters that clients use to load balance better. For example, if there is not much Guard bandwidth, clients will be asked to use Guards mainly for Guard purposes and not for Middle/Exit purposes.
Now that we have reduced the number of guard nodes to 1, there are some HSes that receive lots of traffic and are hidden behind a single guard. That guard is probably receiving/pushing quite some HS traffic that is not really considered during client load balancing. So normal clients will keep on pushing that node to become their guard, and at the same time HS clients will push that node for HS traffic.
If we now pin both the guard and the middle (as discussed in my post), now middle nodes that protect popular HSes, will also get a surge of HS traffic that is not accounted by Tor's bandwidth weight load balancing.
I might be wrong in all the above.
Thanks for the explanation! If I understand right (probably not), this issue isn't specific to hidden services. Any client that sends or receives a lot of traffic will create a hotspot of load on its guard. If there are multiple layers of guards there will be a hotspot at each layer. But that load won't be taken into consideration by other clients picking guards, because relays report how much bandwidth they're willing to provide, but not how much of it has been used. So hotspots are invisible to the directory authorities. Is that anywhere near the mark? Cheers, Michael -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQEcBAEBCAAGBQJUIFkYAAoJEBEET9GfxSfMKlcH/0cRiUaWKvHYbQqOqI8rfXfX h4v/hwRrVOfPtlLaIcryFTG2iDBAORfZjxZ7hABk+ymkiasfYPCQxfbXd2h3i80h 4558eqnfHGn8NCVdKyjLz4IzSDFWJXu42M6ZSWYg0Q5L4UrbNc37KhE34AYwb53V TwzYMy8gXBA6yZKgPWKcmZ103pwK8vXT9kdO0M7LynMojy7/9b5K8Q9nYAueBb7n Flw2vkLj2hzmVJeZjXDQCUGHRK4SErL/CUh349TRc7mXcDQZg6QMQ8DYCQIVHWmd JbW/6QEK8qOCjziAGTLdIo5FmFYSdoNyAxn2819YJ6FP+YtP3cHFb0+FjW82YR8= =aPDI -----END PGP SIGNATURE-----
On Sat, Sep 13, 2014 at 04:07:13PM +0300, George Kadianakis wrote:
So let's say that along with our guard, we also pick 6 second-tier guards (middle nodes) that also get pinned for 2-3 months. This makes us look like this:
-> middle1 -> middle2 HS -> guard -> middle3 -> <exit> -> RP -> middle4 -> middle5 -> middle6
(where the <exit> is chosen from the set of all relays (not static).)
Since guard picks are independent, the probability of one of your 6 middles being compromised is the same probability as the one from the section above: of your main guard getting owned after 6 rotations. This means that every 2-3 months, your guard has 1/4 chance of getting discovered [2]. This means that after a few rotations your guard is guaranteed to be leaked.
Yeah, I think having so many middle-guards will undermine your goal of rarely picking a bad middle-guard. Incidentally, it looks like the math is about the same for the case where you pick only one middle-guard but you rotate it every 1/3 months?
Some thoughts:
a) To reduce the ownage probabilities we could pick a single middle node instead of 6. That will greatly improve guard discovery probabilities, and make us look like this:
HS -> guard -> middle -> <exit> -> RP (where <exit> is chosen from the set of all relays)
However, that will definitely degrade HS performance. I'm not sure if Tor relays are able to handle all that concentrated HS traffic. Specifically, the guards/middles that get picked by popular HSes will get flooded with traffic that is never accounted for in Tor's load balancing equations (since HS traffic is not counted) and they will get hammered both by HS traffic and regular Tor traffic.
Seems like in this case you'd want to pick your middle hop the same way you picked your guard hop. If approximately no Tor users (x=0%) picked their paths this way, then the current load balancing should still work fine. If all Tor users (x=100%) picked their paths this way, we would basically push out all middle (non-guard non-exit) relays, and we should double up the load that our load balancing algorithms assign to guards. Were you thinking of doing this modification for just hidden service users? If so, and assuming we could measure (an approximation of) how many total Tor circuits, and how many total Tor bytes, are hidden service related, then it seems like we could weight the shift from middle to guard load according to this value x.
b) To reduce the ownage probabilities we need to extend the guard lifetime period. If we switched guards every 9 months, instead of every 2 months, we would have much lower chance of getting compromised in the long run. Actually, the probabilities would even look encouraging (but still nowhere near cryptographic quality).
Don't get distracted by the fact that some other fields can get great security results. :)
However, if guard discovery attacks are still possible, having guards last for 9 months gives the attacker a much larger window for attacks. Maybe we need to solve guard discovery attacks and increase the lifetime period at the same time?
What does HS -> guard -> guard -> <middle> -> RP look like, where the first two hops are rotated every 9 months? --Roger
Roger Dingledine <arma@mit.edu> writes:
On Sat, Sep 13, 2014 at 04:07:13PM +0300, George Kadianakis wrote:
So let's say that along with our guard, we also pick 6 second-tier guards (middle nodes) that also get pinned for 2-3 months. This makes us look like this:
-> middle1 -> middle2 HS -> guard -> middle3 -> <exit> -> RP -> middle4 -> middle5 -> middle6
(where the <exit> is chosen from the set of all relays (not static).)
Since guard picks are independent, the probability of one of your 6 middles being compromised is the same probability as the one from the section above: of your main guard getting owned after 6 rotations. This means that every 2-3 months, your guard has 1/4 chance of getting discovered [2]. This means that after a few rotations your guard is guaranteed to be leaked.
Yeah, I think having so many middle-guards will undermine your goal of rarely picking a bad middle-guard.
Incidentally, it looks like the math is about the same for the case where you pick only one middle-guard but you rotate it every 1/3 months?
Indeed. I suggested multiple middle-guards so that the HS traffic gets load balanced. However, I mainly mentioned it to demonstrate the flaws of this scheme. I think the correct solution is having a single middle-guard :)
Some thoughts:
a) To reduce the ownage probabilities we could pick a single middle node instead of 6. That will greatly improve guard discovery probabilities, and make us look like this:
HS -> guard -> middle -> <exit> -> RP (where <exit> is chosen from the set of all relays)
However, that will definitely degrade HS performance. I'm not sure if Tor relays are able to handle all that concentrated HS traffic. Specifically, the guards/middles that get picked by popular HSes will get flooded with traffic that is never accounted for in Tor's load balancing equations (since HS traffic is not counted) and they will get hammered both by HS traffic and regular Tor traffic.
Seems like in this case you'd want to pick your middle hop the same way you picked your guard hop.
If approximately no Tor users (x=0%) picked their paths this way, then the current load balancing should still work fine.
If all Tor users (x=100%) picked their paths this way, we would basically push out all middle (non-guard non-exit) relays, and we should double up the load that our load balancing algorithms assign to guards.
Were you thinking of doing this modification for just hidden service users? If so, and assuming we could measure (an approximation of) how many total Tor circuits, and how many total Tor bytes, are hidden service related, then it seems like we could weight the shift from middle to guard load according to this value x.
Yes, I was mainly considering this modification just for hidden service traffic but it's still unclear to me whether this is a good idea. If _all_ Tor clients (both clients and HSes) were to use single middle-guards, we would indeed have to do major modifications to the network's load balancing. OTOH, just changing the HS logic might be easier for the network even though we would still need to perform load balancing changes similar to the ones you suggested. A more important question is what's the anonymity impact of changing the HS circuit establishment logic. That will make circuits much easier to distinguish as HS-related, by their guard node, middle-guard or exit node. However, this is also currently possible if those actors carefully inspect the rates of incoming/outgoing cells, etc. More research is required...
b) To reduce the ownage probabilities we need to extend the guard lifetime period. If we switched guards every 9 months, instead of every 2 months, we would have much lower chance of getting compromised in the long run. Actually, the probabilities would even look encouraging (but still nowhere near cryptographic quality). p> Don't get distracted by the fact that some other fields can get great security results. :)
However, if guard discovery attacks are still possible, having guards last for 9 months gives the attacker a much larger window for attacks. Maybe we need to solve guard discovery attacks and increase the lifetime period at the same time?
What does HS -> guard -> guard -> <middle> -> RP look like, where the first two hops are rotated every 9 months?
Let's consider HS -> guard -> guard -> <middle> -> RP. That's the single middle-guard case: In this case, the chance of getting your guard discovered is the same as picking a compromised guard: which is optimal. That is, against a 5% adversary an HS does a coin flip (with 1/20 fail chance) every 9 months. An HS that hopes to be up for 5 years (that's around 7 coin flips) has a 0.7 probability (that's (19/20)^7) of being safe. Of course, now we are entering the game where the adversary becomes the <middle> node, and learns your second-tier guard node. and then the attacker has to own the second-tier guard node, and then own the guard node to win. This is definitely an improvement over the current situation (one more box to own), but 9 months is a long time... Maybe the optimal situation here is the static tunnel: HS -> guard -> guard -> guard -> RP which increases the number of nodes such an attacker needs to compromise to three. However, such a setup will increase the guard load even more, and it might also allow other weird attacks (since the last node is pinned now, RPs know better which HS they are serving).
George Kadianakis:
Roger Dingledine <arma@mit.edu> writes:
On Sat, Sep 13, 2014 at 04:07:13PM +0300, George Kadianakis wrote:
So let's say that along with our guard, we also pick 6 second-tier guards (middle nodes) that also get pinned for 2-3 months. This makes us look like this:
-> middle1 -> middle2 HS -> guard -> middle3 -> <exit> -> RP -> middle4 -> middle5 -> middle6
(where the <exit> is chosen from the set of all relays (not static).)
Since guard picks are independent, the probability of one of your 6 middles being compromised is the same probability as the one from the section above: of your main guard getting owned after 6 rotations. This means that every 2-3 months, your guard has 1/4 chance of getting discovered [2]. This means that after a few rotations your guard is guaranteed to be leaked.
Yeah, I think having so many middle-guards will undermine your goal of rarely picking a bad middle-guard.
Incidentally, it looks like the math is about the same for the case where you pick only one middle-guard but you rotate it every 1/3 months?
Indeed.
I suggested multiple middle-guards so that the HS traffic gets load balanced. However, I mainly mentioned it to demonstrate the flaws of this scheme. I think the correct solution is having a single middle-guard :)
Some thoughts:
a) To reduce the ownage probabilities we could pick a single middle node instead of 6. That will greatly improve guard discovery probabilities, and make us look like this:
HS -> guard -> middle -> <exit> -> RP (where <exit> is chosen from the set of all relays)
However, that will definitely degrade HS performance. I'm not sure if Tor relays are able to handle all that concentrated HS traffic. Specifically, the guards/middles that get picked by popular HSes will get flooded with traffic that is never accounted for in Tor's load balancing equations (since HS traffic is not counted) and they will get hammered both by HS traffic and regular Tor traffic.
Seems like in this case you'd want to pick your middle hop the same way you picked your guard hop.
If approximately no Tor users (x=0%) picked their paths this way, then the current load balancing should still work fine.
If all Tor users (x=100%) picked their paths this way, we would basically push out all middle (non-guard non-exit) relays, and we should double up the load that our load balancing algorithms assign to guards.
Were you thinking of doing this modification for just hidden service users? If so, and assuming we could measure (an approximation of) how many total Tor circuits, and how many total Tor bytes, are hidden service related, then it seems like we could weight the shift from middle to guard load according to this value x.
Yes, I was mainly considering this modification just for hidden service traffic but it's still unclear to me whether this is a good idea.
If _all_ Tor clients (both clients and HSes) were to use single middle-guards, we would indeed have to do major modifications to the network's load balancing.
OTOH, just changing the HS logic might be easier for the network even though we would still need to perform load balancing changes similar to the ones you suggested.
A more important question is what's the anonymity impact of changing the HS circuit establishment logic. That will make circuits much easier to distinguish as HS-related, by their guard node, middle-guard or exit node. However, this is also currently possible if those actors carefully inspect the rates of incoming/outgoing cells, etc.
More research is required...
b) To reduce the ownage probabilities we need to extend the guard lifetime period. If we switched guards every 9 months, instead of every 2 months, we would have much lower chance of getting compromised in the long run. Actually, the probabilities would even look encouraging (but still nowhere near cryptographic quality). p> Don't get distracted by the fact that some other fields can get great security results. :)
However, if guard discovery attacks are still possible, having guards last for 9 months gives the attacker a much larger window for attacks. Maybe we need to solve guard discovery attacks and increase the lifetime period at the same time?
What does HS -> guard -> guard -> <middle> -> RP look like, where the first two hops are rotated every 9 months?
Let's consider HS -> guard -> guard -> <middle> -> RP. That's the single middle-guard case:
In this case, the chance of getting your guard discovered is the same as picking a compromised guard: which is optimal.
That is, against a 5% adversary an HS does a coin flip (with 1/20 fail chance) every 9 months. An HS that hopes to be up for 5 years (that's around 7 coin flips) has a 0.7 probability (that's (19/20)^7) of being safe.
Of course, now we are entering the game where the adversary becomes the <middle> node, and learns your second-tier guard node. and then the attacker has to own the second-tier guard node, and then own the guard node to win. This is definitely an improvement over the current situation (one more box to own), but 9 months is a long time...
Maybe the optimal situation here is the static tunnel:
HS -> guard -> guard -> guard -> RP
which increases the number of nodes such an attacker needs to compromise to three. However, such a setup will increase the guard load even more, and it might also allow other weird attacks (since the last node is pinned now, RPs know better which HS they are serving).
I am worried that anything involving a simple additional layer of guards will only make things worse. The core problem with these multi-layered guard defenses is that you're not addressing the two things that actually make hidden services vulnerable: 1. The adversary gets to force you to create many circuits through the Tor network by sending tons of client requests your way. 2. They *also* get to tear down your RPs to force you to make even more circuits by sending DESTROY or similar teardown-inducing cells that for some reason are not dropped at the RP. Even with these multilayer guard schemes, if these two properties are not removed, it will be still very easy to determine the middle guard because the "exit" will change rapidly based on the adversary's connection attempts and destroy cells, allowing an adversary's exit to be chosen very quickly. Once you get that middle guard, you just start the coercion attacks there (warrants, seizures, or extralegal rubber-hose attacks**), knowing that that middle guard will quickly give up the first guard, and then off you go to similarly coerce the first guard to find the service location. As I've suggested before, I really really think you should also analyze an I2P-like scheme where HSs try really hard to maintain path persistence to their RPs for some fixed time period on the order of an hour (but which can be parameterized and analyzed to give the expected time for guard discovery). In fact, with a fixed-duration for RP paths and such parameterized analysis, we can actually set the guard node lifetime to match the exptected time before guard node discovery. In other words: instead of making many fresh RP circuits that can be destroyed, you pick a few RP paths, and maintain them for all circuits for a while, regardless of the activity that your HS sees, and also keep retrying these paths regardless of any circuit failure/teardown you experience. These RP paths would still have guards that last on the order of several months (or whatever duration matches the expected Guard discovery time from the analysis above), but the adversary would lose the ability to move up the chain by causing your circuits to fail from the client end or by driving a ton of activity at you. We should also independently find ways such that clients cannot destroy the whole 6 hop HS circuit from their end. Any destruction-inducing messages should stop at the RP. ** Sure, having a random police force show up to take your computers is a pretty bad situation to be in, in many areas of the world.. But having the Zeta cartel or ISIL show up and threaten to behead you is way worse. -- Mike Perry
As I've suggested before, I really really think you should also analyze an I2P-like scheme where HSs try really hard to maintain path persistence to their RPs for some fixed time period on the order of an hour (but which can be parameterized and analyzed to give the expected time for guard discovery). ... In other words: instead of making many fresh RP circuits that can be destroyed, you pick a few RP paths, and maintain them for all circuits for a while, regardless of the activity that your HS sees, and also keep retrying these paths regardless of any circuit failure/teardown you experience. These RP paths would still have guards that last on the order of several months (or whatever duration matches the expected Guard discovery time from the analysis above), but the adversary would lose the ability to move up the chain by causing your circuits to fail from the client end or by driving a ton of activity at you.
I agree that it would be an improvement to remove the ability of an adversary to force the selection of new paths to the RP. For security purposes, it seems the same as adding additional layers of “guards” that have shorter expiration times. And that does suggest one benefit of *shorter* lifetimes for secondary or tertiary guards: you may make expiration faster than an adversary can begin surveillance. The trick is to make the expiration time just under the speed of surveillance. If expiration is too fast, the adversary can just as well wait for you to choose one of his relays. Suppose the third hop from the HS was changed every hour, and the adversary controlled 1% of all consensus weight. Then it would take a little over 4 days in expectation to choose an adversarial relay and thereby expose the second hop. Assuming the second and first hops rotate slower than surveillance speed, the adversary can at that point move up the chain via surveillance to identify the HS. If the HS can hold onto that third hop for as long as a day, then it would take a little over 14 weeks in expectation for an adversarial relay to be selected. These number don’t seem great to me, but they do seem like an improvement. Aaron
"A. Johnson" <aaron.m.johnson@nrl.navy.mil> writes:
As I've suggested before, I really really think you should also analyze an I2P-like scheme where HSs try really hard to maintain path persistence to their RPs for some fixed time period on the order of an hour (but which can be parameterized and analyzed to give the expected time for guard discovery). ... In other words: instead of making many fresh RP circuits that can be destroyed, you pick a few RP paths, and maintain them for all circuits for a while, regardless of the activity that your HS sees, and also keep retrying these paths regardless of any circuit failure/teardown you experience. These RP paths would still have guards that last on the order of several months (or whatever duration matches the expected Guard discovery time from the analysis above), but the adversary would lose the ability to move up the chain by causing your circuits to fail from the client end or by driving a ton of activity at you.
I agree that it would be an improvement to remove the ability of an adversary to force the selection of new paths to the RP. For security purposes, it seems the same as adding additional layers of “guards” that have shorter expiration times. And that does suggest one benefit of *shorter* lifetimes for secondary or tertiary guards: you may make expiration faster than an adversary can begin surveillance. The trick is to make the expiration time just under the speed of surveillance. If expiration is too fast, the adversary can just as well wait for you to choose one of his relays.
Suppose the third hop from the HS was changed every hour, and the adversary controlled 1% of all consensus weight. Then it would take a little over 4 days in expectation to choose an adversarial relay and thereby expose the second hop. Assuming the second and first hops rotate slower than surveillance speed, the adversary can at that point move up the chain via surveillance to identify the HS. If the HS can hold onto that third hop for as long as a day, then it would take a little over 14 weeks in expectation for an adversarial relay to be selected.
These number don’t seem great to me, but they do seem like an improvement.
Good thoughts! It seems to me that we want to defend against (at least) two different attacks here: Sybil attack: We want to defend against a Sybil attack where attackers sign up relays to the network so that they eventually become the guards (or second/third guards) of HS circuits. The suggested way to deal with this attack is to rotate guards slowly. We currently rotate guards every 2-3 months, but we are considering changing this to 9 months or so according to proposal 236 Coercion attack: However, we also want to defend against "coercion" attacks, where attackers can compromise (pwn/seize/etc.) guards of HS circuits. A way to solve this, assuming that compromising Tor relays takes non-trivial time, would be to rotate guards fast. The idea is that by the time the attacker has compromised a guard, the HS has already rotated that guard and moved to another one. Let's say that compromising a relay takes 5 days. Then a good strategy would be to rotate every guard layer every 5 days. The obvious problem here is that if you assume an attacker that can pull off both attacks, the proposed solutions are incompatible. A system that defends against one attack is left open to the other. And I guess that's why the last few posts are suggesting to combine the two defences. They suggest having long-term guards (anti-sybil) near the HS, and short-term guards (anti-coercion) near the RP. Ignoring all sorts of load balancing and bandwidth issues, let's consider the following circuit: HS -> 3 months guard_1 -> 3 months guard_2 -> 5 days guard_3 -> RP and see how an adversary would attack it: The adversary starts off as being the RP, and hence learns the identity of guard_3 [0]. To learn the next hop, and since it doesn't have enough time to do a coercion attack, it has to do a sybil attack. A 5% adversary (like CERT) starts getting over 50% probability of becoming your next hop after about 13 rotations. So after about 2 months (13*5 days), the adversary will become your guard_3, and hence learn the identity of guard_2.
From that point, he just needs to walk the coercion chain for two hops. So basically, after 5 days he compromises guard_2 and then after 5 more days he compromises guard_1. Total time to deanonymization is 75 days. Not good. FWIW, using the same model, the time to deanonymization with the current HS circuits is just 5 days, that is a single coercion attack.
Some notes: * It seems that the only reason it took 75 days to the adversary is because the first hop took him 65 days to crack: Sybil attacks are slow in this case. Unfortunately, it doesn't really make sense to add two '5 day guards' in a circuit, since a Sybil adversary has equal chances to pop at the guard nearest to the HS. * While more hops are useless for Sybil attacks, they actually help against coercion attacks. Unfortunately, they only add 5 days per extra hop to the time to deanonymization. * It seems that coercion attacks are noisy. At least in this case, relays got seized (why?) and people got notified that something was going on. It would be nice if we could make coercion attacks even more noisy, so that adversaries can't do them without tipping off the whole network. * The more I think about this problem, the more I realize that our solutions are quite hacky. Maybe guards are not the right layer to fix this problem, and we should try to fix the guard discovery problem in circuit establishment as Mike has been suggesting? Unfortunately, the virtual circuits idea seems hard to analyze and do securely. [0]: It seems to me that in all low-latency anonymity schemes based on rendezvous, the adversary is able to trivially learn the first hop of a chain that eventually leads to the HS.
It seems to me that we want to defend against (at least) two different attacks here:
Sybil attack: ... Coercion attack:
Yes, I also am currently thinking about the problem in this way.
Unfortunately, it doesn't really make sense to add two '5 day guards' in a circuit, since a Sybil adversary has equal chances to pop at the guard nearest to the HS.
Yup.
* While more hops are useless for Sybil attacks, they actually help against coercion attacks. Unfortunately, they only add 5 days per extra hop to the time to deanonymization.
And yes again. In this model, an ultra-mega-secret HS should use a long chain of guards. Of course, at some point, it is easier to do a congestion attack to identify the first guard being used by the HS. That is still a win, though, in that such an attack takes more technical skill and effort.
* It seems that coercion attacks are noisy. At least in this case, relays got seized (why?) and people got notified that something was going on. It would be nice if we could make coercion attacks even more noisy, so that adversaries can't do them without tipping off the whole network.
I’m not optimistic about this. Surveillance is no good if the target is aware of it, and so it can be expected to be difficult to detect.
* The more I think about this problem, the more I realize that our solutions are quite hacky. Maybe guards are not the right layer to fix this problem, and we should try to fix the guard discovery problem in circuit establishment as Mike has been suggesting? Unfortunately, the virtual circuits idea seems hard to analyze and do securely.
What do you mean by "the guard discovery problem in circuit establishment”? Do you mean using some level of traffic padding to make it difficult to determine when your relay is directly observing an HS guard? This seems straightforward to do just by making every relay see the same type and number of cells in every non-terminal position in the circuit during circuit creation (some will have no effect, detectable only by the last relay). I do worry about how the cell RTTs could still leak your relative circuit position. Ignoring that, maybe you can make it so that the adversary either (i) has to start surveillance on an observed hop and hope that it is a relatively static guard close to the HS or (ii) has to wait until some relay is observed *multiple* times from the malicious relays to be sure that it is in some layer of guards for the targeted HS. Cheers, Aaron
A. Johnson:
It seems to me that we want to defend against (at least) two different attacks here:
Sybil attack: ... Coercion attack:
Yes, I also am currently thinking about the problem in this way.
Unfortunately, it doesn't really make sense to add two '5 day guards' in a circuit, since a Sybil adversary has equal chances to pop at the guard nearest to the HS.
Yup.
* While more hops are useless for Sybil attacks, they actually help against coercion attacks. Unfortunately, they only add 5 days per extra hop to the time to deanonymization.
And yes again. In this model, an ultra-mega-secret HS should use a long chain of guards. Of course, at some point, it is easier to do a congestion attack to identify the first guard being used by the HS. That is still a win, though, in that such an attack takes more technical skill and effort.
I think this brings up another good point about hidden services that the "you must use a single guard forever" model causes us to ignore. Imagine if we had k-Conflux routing, where you could pick 1-k guards, and send packets to a single exit or RP. Under this model, congestion attacks would be more difficult, because you have to also do the combinatorics to choke out the Choose(N, k) combinations of k of N total guards. If you only choked a subset, conflux would rebalance to the remaining free paths (assuming good, responsive flow control).
* It seems that coercion attacks are noisy. At least in this case, relays got seized (why?) and people got notified that something was going on. It would be nice if we could make coercion attacks even more noisy, so that adversaries can't do them without tipping off the whole network.
I’m not optimistic about this. Surveillance is no good if the target is aware of it, and so it can be expected to be difficult to detect.
* The more I think about this problem, the more I realize that our solutions are quite hacky. Maybe guards are not the right layer to fix this problem, and we should try to fix the guard discovery problem in circuit establishment as Mike has been suggesting? Unfortunately, the virtual circuits idea seems hard to analyze and do securely.
What do you mean by "the guard discovery problem in circuit establishment”? Do you mean using some level of traffic padding to make it difficult to determine when your relay is directly observing an HS guard? This seems straightforward to do just by making every relay see the same type and number of cells in every non-terminal position in the circuit during circuit creation (some will have no effect, detectable only by the last relay). I do worry about how the cell RTTs could still leak your relative circuit position. Ignoring that, maybe you can make it so that the adversary either (i) has to start surveillance on an observed hop and hope that it is a relatively static guard close to the HS or (ii) has to wait until some relay is observed *multiple* times from the malicious relays to be sure that it is in some layer of guards for the targeted HS.
I think padding and other defenses against introducing active side channels are fine longer-term plans, but I think what George means is that we should re-design HS path selection specifically for this guard discovery threat, taking it as a given that the adversary is able to use *some* side channel to determine that it is in the path and knows its position. While I find passive timing attacks skeptical at scale, I am not so crazy as to believe that it is impossible to *actively* encode a reliable side channel in a traffic pattern that you control (which is used in the HS guard discovery research). Conflux may also make these types of side channels more difficult to construct, but I suspect that just means you have to send more data as an attacker. Since you can send a bunch of data at the HS for most application layer protocols (HTTP POST comes to mind), this is probably not a huge barrier. After reading your back-of-the-envelope calculations on node rotation and guard lifetime for multi-tiered guards in your parent reply, I think that it stands to reason that some topology like this is best (with Conflux): HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP The idea would be that Guard_3 would rotate on the order of hours, Guard_2 would come from a set that is rotated on the order of days (based on the expected duration for the adversary to become Guard_3), and Guard_1 would rotate on the order of months (based on the expected duration for the adversary to become Guard_2). Based on your math in your parent reply, this now does strike me as superior to what I actually proposed with "virtual circuits", since if the whole virtual circuit had a lifetime of hours, you'd still have only days before the adversary ended up in the Guard_2 position. I would prefer if we had closed-form or code-based versions of this calculation, though, so we could play with set sizes and lifespans for the 3 hops. We also want to play with questions like "How many circuits should we use at a time?" and "How big should the set of middle nodes we choose from be?" Making all of that parameterized will help us tune it. Heck, the surface might even be plottable or traversable with gradient descent. -- Mike Perry
And yes again. In this model, an ultra-mega-secret HS should use a long chain of guards. Of course, at some point, it is easier to do a congestion attack to identify the first guard being used by the HS. That is still a win, though, in that such an attack takes more technical skill and effort.
I think this brings up another good point about hidden services that the "you must use a single guard forever" model causes us to ignore.
Imagine if we had k-Conflux routing, where you could pick 1-k guards, and send packets to a single exit or RP.
Under this model, congestion attacks would be more difficult, because you have to also do the combinatorics to choke out the Choose(N, k) combinations of k of N total guards. If you only choked a subset, conflux would rebalance to the remaining free paths (assuming good, responsive flow control).
That is a good point, and if you had a set of guards for which you had high collective trust, then I think multiple guards for load balancing and making congestion attacks more difficult would be a good idea. I think you need them to be collectively trustworthy because otherwise each added guard gives the adversary another chance to be selected, which multiplies his ability to observe user traffic in the network. I am skeptical that you wouldn’t be able to apply the congestion attack to the guards one-by-one, because the load balancing would take some time to notice the throughput drop and adjust. If you had multiple guards, then you could use them to provide stronger protection against discovery via congestion by redundantly sending the same packet to each one (PF Syverson and I analyzed this idea in a PETS10 paper <http://ohmygodel.com/publications/active-pets10.pdf>).
After reading your back-of-the-envelope calculations on node rotation and guard lifetime for multi-tiered guards in your parent reply, I think that it stands to reason that some topology like this is best (with Conflux):
HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP
The idea would be that Guard_3 would rotate on the order of hours, Guard_2 would come from a set that is rotated on the order of days (based on the expected duration for the adversary to become Guard_3), and Guard_1 would rotate on the order of months (based on the expected duration for the adversary to become Guard_2).
Why set guard 2 to expire in days? If that is less than surveillance speed, then once the adversary had guard 3, it’s game over.
I would prefer if we had closed-form or code-based versions of this calculation, though, so we could play with set sizes and lifespans for the 3 hops. We also want to play with questions like "How many circuits should we use at a time?" and "How big should the set of middle nodes we choose from be?" Making all of that parameterized will help us tune it. Heck, the surface might even be plottable or traversable with gradient descent.
I took a stab at this by writing a quick Monte Carlo simulator (in python). Calculating exact probabilities gets incredibly complicated when you have several parameters and somewhat complicated compromise scenarios, and simulation in this case is nearly as accurate and reasonably fast. The simulator considers the HS to use just one circuit, and each node on the circuit expires at an individual rate. It outputs the distribution of how long it takes for the adversary to identify the HS. The parameters you might modify (set near the end of the script) are 1. node_expiration_times: a list of node expirations in order from HS (in hours), e.g. [3,2,1] means the first hop (aka the HS’s entry guard) expires in 3 hours, the second hop expires 2 hours, and the third hop in 1 hour 2. surveillance_time: time needed by the adversary to accomplish surveillance (in hours), e.g. if 24 then the adversary compromises a node that expires in 24 or more hours from the current time 3. adv_relay_probs: list containing the probability of selecting an adversarial relay in each position, ordered from HS, e.g. [0.05, 0.01, 0.01] means that the adversary controls 0.05 of entry guard consensus weight, 0.01 of second (aka middle) hop weight, and 0.01 of third-hop weight The script is attached. I hope it is useful. If so, maybe I can develop it more next week. Best, Aaron
The idea would be that Guard_3 would rotate on the order of hours, Guard_2 would come from a set that is rotated on the order of days (based on the expected duration for the adversary to become Guard_3), and Guard_1 would rotate on the order of months (based on the expected duration for the adversary to become Guard_2).
Why set guard 2 to expire in days? If that is less than surveillance speed, then once the adversary had guard 3, it’s game over.
Sorry, I should have stated this more clearly as "If that is greater than the time needed for surveillance”. And I can imagine rotating guard 2 faster than guard 1 for performance reasons (faster rotation more quickly takes advantage of new capacity in the network). But the only reason that I can see treating guard 2 differently than guard 1 is that you judge the “cost" of the attack starting from guard 2 to be higher, thus compensating for the increase in attack speed. That is, if guard 2 rotates to a malicious relay, the adversary still has to identify and then do a targeted compromised of guard 1, while if a malicious relay is selected as guard 1, then the target HS can be relatively easily observed directly. Such an argument is hard to evaluate carefully, because the costs in terms of added technical and legal complexity are hard to estimate. For example, at what point is it “cheaper" to run more malicious nodes and/or wait longer in hopes of obtaining guard 1 than to try and identify guard 2 but then have to perform surveillance on an identified guard 1? So I would argue to protect guard 2 as much as guard 1, and then look for other, better understood, methods to improve performance. Some fun methods that come to mind are (i) carefully choosing number of primary and secondary guards and (ii) trying to reduce the HS path length, and (iii) allowing HSes to pay for improved performance (yes, I haven’t given up on this idea, haha). Exposing to the HS operator the options controlling the security/performance tradeoff may also be a good option. Cheers, Aaron
A. Johnson:
The idea would be that Guard_3 would rotate on the order of hours, Guard_2 would come from a set that is rotated on the order of days (based on the expected duration for the adversary to become Guard_3), and Guard_1 would rotate on the order of months (based on the expected duration for the adversary to become Guard_2).
Why set guard 2 to expire in days? If that is less than surveillance speed, then once the adversary had guard 3, it’s game over.
Sorry, I should have stated this more clearly as "If that is greater than the time needed for surveillance”. And I can imagine rotating guard 2 faster than guard 1 for performance reasons (faster rotation more quickly takes advantage of new capacity in the network). But the only reason that I can see treating guard 2 differently than guard 1 is that you judge the “cost" of the attack starting from guard 2 to be higher, thus compensating for the increase in attack speed. That is, if guard 2 rotates to a malicious relay, the adversary still has to identify and then do a targeted compromised of guard 1, while if a malicious relay is selected as guard 1, then the target HS can be relatively easily observed directly. Such an argument is hard to evaluate carefully, because the costs in terms of added technical and legal complexity are hard to estimate. For example, at what point is it “cheaper" to run more malicious nodes and/or wait longer in hopes of obtaining guard 1 than to try and identify guard 2 but then have to perform surveillance on an identified guard 1?
Well, based on your analysis, I was actually proposing a hybrid scheme somewhere between "virtual circuits" (which win out for load balancing) and "two layers of single guards" (which may win out for security, but only if you make certain assumptions about how the adversary can compromise nodes). Going back to my diagram: HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP. The idea is that Guard_1 is a single node that you choose and keep for O(6 months, or as long as possible), but Guard_2 actually comes from a set of 3-6 or so nodes that you keep for O(weeks), and Guard_3 you rotate something like O(hours). The reason they then are "treated differently" in terms of rotation lifespan is that this hybrid scheme naturally exposes you to more of the network in a given time period in the Guard_2 position, and even more in the Guard_3 position. So these two positions would have shorter durations for a given probability of compromise (by selecting a malicious node), simply because they rotate faster. In other words, these timespans are based entirely on compromise probabilities over many rotation periods, and have less to do with how long it takes to compromise a node once you discover it. The hope behind my reasoning is that if it is incredibly likely for you to rotate your guard(s) before they are discovered, guard discovery attacks lose their value. OTOH, perhaps I am reasoning about this wrong, and it is operationally better to stick with a guard node in the second position for as long as you stick with your first guard. In my mind, having identical rotation periods is only better if you subscribe to the theory that compromising a node is a noisy process, and unlikely to succeed in repeated succession. In which case, you probably just want a static route of exactly three (and only three) guard nodes, fixed for the lifetime of your HS. At least, if you want the most security in this threat model. Does this make sense?
So I would argue to protect guard 2 as much as guard 1, and then look for other, better understood, methods to improve performance. Some fun methods that come to mind are (i) carefully choosing number of primary and secondary guards and (ii) trying to reduce the HS path length, and (iii) allowing HSes to pay for improved performance (yes, I haven’t given up on this idea, haha). Exposing to the HS operator the options controlling the security/performance tradeoff may also be a good option.
Do you subscribe to the "it's cumbersome and noisy to compromise a node (and therefore you should sit on your routes as long as possible until they break)" threat model, or the "it's likely quiet and/or quick (and therefore all we can do is try to improve the statistics to reduce the likelihood of compromise early in the rotation period)" threat model? Or is there an additional threat model/goal we should be aiming to satisfy here? It sounds like you subscribe to the first "it's cumbersome to compromise a node, so keep a fixed route" threat model and goal, right? Would it make you more nervous if the exit was also fixed? If so, why? If not, why not? If we agree that is the best threat model (and I'm not fully convinced yet, but I could be), then it does sound like we're arriving at three or four different path selection algorithms that are successively worse for security under this threat model, but better for performance (three layer guards, two layer guards, variable position sets+lifespans, and virtual circuits). -- Mike Perry
HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP.
The idea is that Guard_1 is a single node that you choose and keep for O(6 months, or as long as possible), but Guard_2 actually comes from a set of 3-6 or so nodes that you keep for O(weeks), and Guard_3 you rotate something like O(hours). ... The hope behind my reasoning is that if it is incredibly likely for you to rotate your guard(s) before they are discovered, guard discovery attacks lose their value.
This doesn’t make sense - do you mean "if it is likely for you to rotate your guards *after” they are discovered"?
OTOH, perhaps I am reasoning about this wrong, and it is operationally better to stick with a guard node in the second position for as long as you stick with your first guard. In my mind, having identical rotation periods is only better if you subscribe to the theory that compromising a node is a noisy process, and unlikely to succeed in repeated succession. In which case, you probably just want a static route of exactly three (and only three) guard nodes, fixed for the lifetime of your HS. At least, if you want the most security in this threat model.
Does this make sense?
I don’t follow your reasoning. Even if compromising is a completely deterministic process, it would be better to have one quickly rotating node at the end of the HS-side circuit because if each hop rotated slowly the adversary would have enough time upon discovery of each hop to set up surveillance of the next (where the last hop is always immediately discovered by the adversarially-chosen RP). Having a quickly-rotating final hop from the HS means the adversary has to wait until the HS rotates to an adversarially-controlled relay.
Do you subscribe to the "it's cumbersome and noisy to compromise a node (and therefore you should sit on your routes as long as possible until they break)" threat model, or the "it's likely quiet and/or quick (and therefore all we can do is try to improve the statistics to reduce the likelihood of compromise early in the rotation period)" threat model? Or is there an additional threat model/goal we should be aiming to satisfy here?
I do actually suspect that it's cumbersome and noisy, but the solution I have argued for doesn’t depend on that (indeed, it is based on a deterministic compromise model).
It sounds like you subscribe to the first "it's cumbersome to compromise a node, so keep a fixed route" threat model and goal, right? Would it make you more nervous if the exit was also fixed? If so, why? If not, why not?
As I was saying above, a fixed exit would allow compromise in the time it takes to begin surveillance (times three). We can likely do better than that. Aaron
By the way, I actually can think of a good reason to include multiple rotation speeds: to deal with both your uncertainty about surveillance speed and its randomness. Suppose that you think it takes somewhere between 3 hours and 1 month, but don’t have a much better guess than that. Then a good idea might be to have a different relay rotation at a different timescale, say one every 3 hours, one every 3 days, one every 10 weeks, and an entry guard for many months (yes, I realize that is four relays just on the HS side…). Then you can protect pretty well against a range of possible speeds, instead of making it fragile to the possibility that your rotation speed is *just* slower than what would have stymied the adversary. Aaron On Nov 11, 2014, at 7:22 PM, A. Johnson <aaron.m.johnson@nrl.navy.mil> wrote:
HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP.
The idea is that Guard_1 is a single node that you choose and keep for O(6 months, or as long as possible), but Guard_2 actually comes from a set of 3-6 or so nodes that you keep for O(weeks), and Guard_3 you rotate something like O(hours). ... The hope behind my reasoning is that if it is incredibly likely for you to rotate your guard(s) before they are discovered, guard discovery attacks lose their value.
This doesn’t make sense - do you mean "if it is likely for you to rotate your guards *after” they are discovered"?
OTOH, perhaps I am reasoning about this wrong, and it is operationally better to stick with a guard node in the second position for as long as you stick with your first guard. In my mind, having identical rotation periods is only better if you subscribe to the theory that compromising a node is a noisy process, and unlikely to succeed in repeated succession. In which case, you probably just want a static route of exactly three (and only three) guard nodes, fixed for the lifetime of your HS. At least, if you want the most security in this threat model.
Does this make sense?
I don’t follow your reasoning. Even if compromising is a completely deterministic process, it would be better to have one quickly rotating node at the end of the HS-side circuit because if each hop rotated slowly the adversary would have enough time upon discovery of each hop to set up surveillance of the next (where the last hop is always immediately discovered by the adversarially-chosen RP). Having a quickly-rotating final hop from the HS means the adversary has to wait until the HS rotates to an adversarially-controlled relay.
Do you subscribe to the "it's cumbersome and noisy to compromise a node (and therefore you should sit on your routes as long as possible until they break)" threat model, or the "it's likely quiet and/or quick (and therefore all we can do is try to improve the statistics to reduce the likelihood of compromise early in the rotation period)" threat model? Or is there an additional threat model/goal we should be aiming to satisfy here?
I do actually suspect that it's cumbersome and noisy, but the solution I have argued for doesn’t depend on that (indeed, it is based on a deterministic compromise model).
It sounds like you subscribe to the first "it's cumbersome to compromise a node, so keep a fixed route" threat model and goal, right? Would it make you more nervous if the exit was also fixed? If so, why? If not, why not?
As I was saying above, a fixed exit would allow compromise in the time it takes to begin surveillance (times three). We can likely do better than that.
Aaron _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
A. Johnson:
HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP.
The idea is that Guard_1 is a single node that you choose and keep for O(6 months, or as long as possible), but Guard_2 actually comes from a set of 3-6 or so nodes that you keep for O(weeks), and Guard_3 you rotate something like O(hours). ... The hope behind my reasoning is that if it is incredibly likely for you to rotate your guard(s) before they are discovered, guard discovery attacks lose their value.
This doesn’t make sense - do you mean "if it is likely for you to rotate your guards *after” they are discovered"?
Err, right, my argument for the different rotation periods hinges on minimizing the time after discovery happens during which the adversary gets to try to set up surveillance.
OTOH, perhaps I am reasoning about this wrong, and it is operationally better to stick with a guard node in the second position for as long as you stick with your first guard. In my mind, having identical rotation periods is only better if you subscribe to the theory that compromising a node is a noisy process, and unlikely to succeed in repeated succession. In which case, you probably just want a static route of exactly three (and only three) guard nodes, fixed for the lifetime of your HS. At least, if you want the most security in this threat model.
Does this make sense?
I don’t follow your reasoning. Even if compromising is a completely deterministic process, it would be better to have one quickly rotating node at the end of the HS-side circuit because if each hop rotated slowly the adversary would have enough time upon discovery of each hop to set up surveillance of the next (where the last hop is always immediately discovered by the adversarially-chosen RP). Having a quickly-rotating final hop from the HS means the adversary has to wait until the HS rotates to an adversarially-controlled relay.
It sounds like you subscribe to the first "it's cumbersome to compromise a node, so keep a fixed route" threat model and goal, right? Would it make you more nervous if the exit was also fixed? If so, why? If not, why not?
As I was saying above, a fixed exit would allow compromise in the time it takes to begin surveillance (times three). We can likely do better than that.
Ok, this was my assumption behind arguing for staggering these rotation periods, too. I don't think that having a fixed exit is a good idea, and this same conclusion has led me to believe that the rotation times should be staggered. I am having a hard time understanding why two layers of guards of the same rotation lifespan is necessarily better than one, especially since the sybil attack to determine the second guard from a fast rotating exit is likely to succeed within a few days. However, I also see that if we're talking about those middle nodes rotating on the order of a week, that might be a long time for an adversary to play with to determine the first guard, even if we minimize that expected time period between discovering it and rotation. I guess it depends on what we expect that overlap to be, but it probably is O(rotation_time/2) given that we're dealing with uniform disributions over time here. I willl try to find some time to play with your script to see if I can fully convince myself that rotation doesn't help for the middle node even under a coercive threat model. -- Mike Perry
As I was saying above, a fixed exit would allow compromise in the time it takes to begin surveillance (times three). We can likely do better than that.
Ok, this was my assumption behind arguing for staggering these rotation periods, too. I don't think that having a fixed exit is a good idea, and this same conclusion has led me to believe that the rotation times should be staggered. I am having a hard time understanding why two layers of guards of the same rotation lifespan is necessarily better than one, especially since the sybil attack to determine the second guard from a fast rotating exit is likely to succeed within a few days.
Here are some benefits from two (or more!) layers of long-lived guards: 1. The adversary has to perform two rounds of installing surveillance and detecting the next hop. This costs him time and money. It also makes it more likely that one of the guards expires or the HS relocates in the meantime. 2. It increases the chance the one of the guards is in a location that doesn’t cooperate or that the surveillance effort just happens to take longer than the median. 3. It increases the chance that some node operator gets tipped off to the surveillance. 4. If there is any chance of a false positive at any hop (unclear to me, depending on how the next hop is detected), this would increase the overall chance that the adversary gets sent down the wrong path.
I willl try to find some time to play with your script to see if I can fully convince myself that rotation doesn't help for the middle node even under a coercive threat model.
I think that in the attack model we’ve been discussing, the second hop rotation speed doesn’t affect things much as long as it is, say, an order of magnitude slower than the third hop’s rotation speed and slower than surveillance speed. Then the adversary is much more likely to be chosen as third hop and then perform two surveillance attacks than he is to be chosen is the second hop and perform one surveillance attack. And actually the same argument is true for setting the rotation speed of first hop. However, as I said in a separate email, I now can see a reason to increase rotation speed with each hop from the HS: you don’t actually know surveillance speed (or the fraction of adversarial relays, for that matter), and a sequence of increasing rotation speeds helps you defend pretty well against the full range of possibilities. BTW, new script attached (also available at <https://github.com/ohmygodel/hs-guard-selection.git>). This one allows you to set the number of guards at each hop from the HS by setting them in the num_guards list. Cheers, Aaron
Mike Perry <mikeperry@torproject.org> writes:
A. Johnson:
The idea would be that Guard_3 would rotate on the order of hours, Guard_2 would come from a set that is rotated on the order of days (based on the expected duration for the adversary to become Guard_3), and Guard_1 would rotate on the order of months (based on the expected duration for the adversary to become Guard_2).
Why set guard 2 to expire in days? If that is less than surveillance speed, then once the adversary had guard 3, it’s game over.
Sorry, I should have stated this more clearly as "If that is greater than the time needed for surveillance”. And I can imagine rotating guard 2 faster than guard 1 for performance reasons (faster rotation more quickly takes advantage of new capacity in the network). But the only reason that I can see treating guard 2 differently than guard 1 is that you judge the “cost" of the attack starting from guard 2 to be higher, thus compensating for the increase in attack speed. That is, if guard 2 rotates to a malicious relay, the adversary still has to identify and then do a targeted compromised of guard 1, while if a malicious relay is selected as guard 1, then the target HS can be relatively easily observed directly. Such an argument is hard to evaluate carefully, because the costs in terms of added technical and legal complexity are hard to estimate. For example, at what point is it “cheaper" to run more malicious nodes and/or wait longer in hopes of obtaining guard 1 than to try and identify guard 2 but then have to perform surveillance on an identified guard 1?
Hello, I'm also a bit confused for similar reasons as Aaron. I think I'm missing something.
Well, based on your analysis, I was actually proposing a hybrid scheme somewhere between "virtual circuits" (which win out for load balancing) and "two layers of single guards" (which may win out for security, but only if you make certain assumptions about how the adversary can compromise nodes). Going back to my diagram:
HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP.
The idea is that Guard_1 is a single node that you choose and keep for O(6 months, or as long as possible), but Guard_2 actually comes from a set of 3-6 or so nodes that you keep for O(weeks), and Guard_3 you rotate something like O(hours).
Let me analyze this scheme with the simple model from here: https://lists.torproject.org/pipermail/tor-dev/2014-November/007728.html (which is closer to your "it's likely quiet and/or quick to compromise a node" threat model since the adversary can compromise a node in 5 days and no one notices). Let's say that the 5% adversary starts from the RP and needs to walk the chain up to the HS: Guard_3 rotates fast, so Adversary does a Sybil attack against it. Let's say that you keep Guard_3 for a day (keeping it for less is even worse), a 5% Sybil adversary will have entered that circuit position with 50% chance after about 14 days. So now he knows Guard_2. Guard_2 rotates in weeks, so it's faster for the adversary to do a coercion attack that only takes 5 days. After 5 days Guard_2 is compromised and the adversary knows Guard_1. Another coercion attack (5 days) is enough to compromise Guard_1 and the adversary has deanonymized the HS. Total time: 24 days. If you check 007728.html, I suggested some rotation speeds that "maximize" the time to compromise in this totally arbitrary security model. With the 5 days coercion attack time, I couldn't get it to more than 75 days... which is less than a summer time. BTW, this security model might be bollocks. Let's now consider another arbitrary security model where the attacker can't do coercion attacks and can only rely on Sybil attacks. In that case, rotating Guard_2 faster than Guard_1 is a bad idea, since the attacker will be able to penetetrate the Guard_2 circuit position faster. What is wrong with our security models and what other security models are there? Can you find the time to compromise of your scheme under _your_ security model? Like Aaron, I believe that in most (all?) security models, the final hop needs to rotate a tiny bit faster than the time it takes the adversary to do a coercion attack, so that the adversary is forced to do a sybil attack. However, in subsequent hops you need to do slower rotations because you really don't want to get Sybil'ed in the first or second hop.
The reason they then are "treated differently" in terms of rotation lifespan is that this hybrid scheme naturally exposes you to more of the network in a given time period in the Guard_2 position, and even more in the Guard_3 position. So these two positions would have shorter durations for a given probability of compromise (by selecting a malicious node), simply because they rotate faster.
In other words, these timespans are based entirely on compromise probabilities over many rotation periods, and have less to do with how long it takes to compromise a node once you discover it.
The hope behind my reasoning is that if it is incredibly likely for you to rotate your guard(s) before they are discovered, guard discovery attacks lose their value.
OTOH, perhaps I am reasoning about this wrong, and it is operationally better to stick with a guard node in the second position for as long as you stick with your first guard. In my mind, having identical rotation periods is only better if you subscribe to the theory that compromising a node is a noisy process, and unlikely to succeed in repeated succession. In which case, you probably just want a static route of exactly three (and only three) guard nodes, fixed for the lifetime of your HS. At least, if you want the most security in this threat model.
Does this make sense?
So I would argue to protect guard 2 as much as guard 1, and then look for other, better understood, methods to improve performance. Some fun methods that come to mind are (i) carefully choosing number of primary and secondary guards and (ii) trying to reduce the HS path length, and
It's interesting to reduce the HS path length, but that would reduce the length of the chain that the adversary has to walk, which is bad :/ The rendezvous model is a bit restricting isn't it :(
George Kadianakis <desnacked@riseup.net> writes:
Mike Perry <mikeperry@torproject.org> writes:
A. Johnson:
The idea would be that Guard_3 would rotate on the order of hours, Guard_2 would come from a set that is rotated on the order of days (based on the expected duration for the adversary to become Guard_3), and Guard_1 would rotate on the order of months (based on the expected duration for the adversary to become Guard_2).
Why set guard 2 to expire in days? If that is less than surveillance speed, then once the adversary had guard 3, it’s game over.
Sorry, I should have stated this more clearly as "If that is greater than the time needed for surveillance”. And I can imagine rotating guard 2 faster than guard 1 for performance reasons (faster rotation more quickly takes advantage of new capacity in the network). But the only reason that I can see treating guard 2 differently than guard 1 is that you judge the “cost" of the attack starting from guard 2 to be higher, thus compensating for the increase in attack speed. That is, if guard 2 rotates to a malicious relay, the adversary still has to identify and then do a targeted compromised of guard 1, while if a malicious relay is selected as guard 1, then the target HS can be relatively easily observed directly. Such an argument is hard to evaluate carefully, because the costs in terms of added technical and legal complexity are hard to estimate. For example, at what point is it “cheaper" to run more malicious nodes and/or wait longer in hopes of obtaining guard 1 than to try and identify guard 2 but then have to perform surveillance on an identified guard 1?
Hello,
I'm also a bit confused for similar reasons as Aaron. I think I'm missing something.
Well, based on your analysis, I was actually proposing a hybrid scheme somewhere between "virtual circuits" (which win out for load balancing) and "two layers of single guards" (which may win out for security, but only if you make certain assumptions about how the adversary can compromise nodes). Going back to my diagram:
HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP.
The idea is that Guard_1 is a single node that you choose and keep for O(6 months, or as long as possible), but Guard_2 actually comes from a set of 3-6 or so nodes that you keep for O(weeks), and Guard_3 you rotate something like O(hours).
Let me analyze this scheme with the simple model from here: https://lists.torproject.org/pipermail/tor-dev/2014-November/007728.html (which is closer to your "it's likely quiet and/or quick to compromise a node" threat model since the adversary can compromise a node in 5 days and no one notices).
Let's say that the 5% adversary starts from the RP and needs to walk the chain up to the HS:
Guard_3 rotates fast, so Adversary does a Sybil attack against it. Let's say that you keep Guard_3 for a day (keeping it for less is even worse), a 5% Sybil adversary will have entered that circuit position with 50% chance after about 14 days. So now he knows Guard_2.
Guard_2 rotates in weeks, so it's faster for the adversary to do a coercion attack that only takes 5 days. After 5 days Guard_2 is compromised and the adversary knows Guard_1.
Another coercion attack (5 days) is enough to compromise Guard_1 and the adversary has deanonymized the HS. Total time: 24 days.
If you check 007728.html, I suggested some rotation speeds that "maximize" the time to compromise in this totally arbitrary security
* just to get notation right, I meant "time to deanonymize" there.
model. With the 5 days coercion attack time, I couldn't get it to more than 75 days... which is less than a summer time.
BTW, this security model might be bollocks.
Let's now consider another arbitrary security model where the attacker can't do coercion attacks and can only rely on Sybil attacks. In that case, rotating Guard_2 faster than Guard_1 is a bad idea, since the attacker will be able to penetetrate the Guard_2 circuit position faster.
What is wrong with our security models and what other security models are there? Can you find the time to compromise of your scheme under _your_ security model?
Like Aaron, I believe that in most (all?) security models, the final hop needs to rotate a tiny bit faster than the time it takes the adversary to do a coercion attack, so that the adversary is forced to do a sybil attack. However, in subsequent hops you need to do slower rotations because you really don't want to get Sybil'ed in the first or second hop.
The reason they then are "treated differently" in terms of rotation lifespan is that this hybrid scheme naturally exposes you to more of the network in a given time period in the Guard_2 position, and even more in the Guard_3 position. So these two positions would have shorter durations for a given probability of compromise (by selecting a malicious node), simply because they rotate faster.
In other words, these timespans are based entirely on compromise probabilities over many rotation periods, and have less to do with how long it takes to compromise a node once you discover it.
The hope behind my reasoning is that if it is incredibly likely for you to rotate your guard(s) before they are discovered, guard discovery attacks lose their value.
OTOH, perhaps I am reasoning about this wrong, and it is operationally better to stick with a guard node in the second position for as long as you stick with your first guard. In my mind, having identical rotation periods is only better if you subscribe to the theory that compromising a node is a noisy process, and unlikely to succeed in repeated succession. In which case, you probably just want a static route of exactly three (and only three) guard nodes, fixed for the lifetime of your HS. At least, if you want the most security in this threat model.
Does this make sense?
So I would argue to protect guard 2 as much as guard 1, and then look for other, better understood, methods to improve performance. Some fun methods that come to mind are (i) carefully choosing number of primary and secondary guards and (ii) trying to reduce the HS path length, and
It's interesting to reduce the HS path length, but that would reduce the length of the chain that the adversary has to walk, which is bad :/
The rendezvous model is a bit restricting isn't it :( _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
It's interesting to reduce the HS path length, but that would reduce the length of the chain that the adversary has to walk, which is bad :/
Yeah, security in this attack model pushes towards a long path.
The rendezvous model is a bit restricting isn't it :(
Agreed, modifying path selection just raises the attack time and effort some (although that “some” is a real improvement IMHO). Clearly users with a powerful global adversary should be able to survive eventual compromise of a server. It might be fun to build a system that would provide fault tolerance and protect the private HS information against individual server compromise. “Survivable HSes”? This seems doable :-) Cheers, Aaron
Ian Goldberg <iang@cs.uwaterloo.ca> writes:
On Fri, Jul 11, 2014 at 01:44:36PM +0300, George Kadianakis wrote:
Hey Nick,
this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001).
I think we have some ideas on how to offer better protection against such attacks, mainly by keeping our middle nodes more static than we do currently.
For example, we could keep our middle nodes for 3-4 days instead of choosing new ones for every circuit. As Roger has suggested, maybe we don't even need to write the static middle nodes on the state file, just use new ones if Tor has restarted.
Keeping middle nodes around for longer will make those attacks much slower (it restricts them to one attack attempt every 3-4 days), but are there any serious negative implications?
For example, if you were unlucky and you picked an evil middle node, and you keep it for 3-4 days, that middle node will always see your traffic coming through your guard (assuming a single guard per client). If we assume you use a non-popular guard node (with only a few clients using it), the middle guard might be able to think "Ah, the circuit that comes from that guard node is always user X" making your circuits a bit linkable from the PoV of your middle node.
And similarly at the exit node: the exit will now know that circuits coming from the same middle are more likely to be the same client. That's a little more worrying to me than the above.
That's a good point and it pretty much kills the idea. We don't have enough users or powerful nodes, to be able to provide any kind of anonymity set for the circuits coming from the same pinned middle node. I guess a stupid way of dodging that problem is instead of applying the "semi-static middle nodes" idea to all Tor clients, maybe we can only apply it to HS rendezvous circuits. The idea is that an exit node being able to link the rendezvous circuits of an HS *might* not be that dangerous (compared to the exit node being able to link the HTTP traffic of Tor clients). If we are worrying about reducing Tor's anonymity set by partitioning our circuits to "rendezvous circuits" and "regular circuits" one can argue that this is the case currently too, since the nodes of a rendezvous circuit are probably able to statistically determine whether the circuit is a rendezvous circuit or a regular Tor circuit by the cells/data flow. (To be honest, I don't really like this idea, but I'm just stating it here for brainstorming.)
participants (8)
-
A. Johnson -
George Kadianakis -
Ian Goldberg -
Michael Rogers -
Mike Perry -
Paul Syverson -
Roger Dingledine -
Sebastian G. <bastik.tor>