Setting NumEntryGuards=2
Back in 2014, Tor moved from three guard nodes to one guard node: https://blog.torproject.org/improving-tors-anonymity-changing-guard-paramete... https://trac.torproject.org/projects/tor/ticket/12206 We made this change primarily to limit points of observability of entry into the Tor network for clients and onion services, as well as to reduce the ability of an adversary to track clients as they move from one internet connection to another by their choice of guards. At the time, I was in favor of two entry guards but did not have a strong preference, and we ended up choosing one guard. After seeing various consequences of using only one entry guard, I think a much stronger case can now be made for bumping back up to two. Roger suggested that I enumerate the pros and cons of this increase on this mailing list, so we can discuss and consider this switch. So here is my attempt at that list. Let's start with a more in-depth recap of the one-guard arguments, along with some recent observations that change things. Arguments for staying with just one guard: 1. One guard means less observability. As Roger put it in the above blog post: "I think the analysis of the network-level adversary in Aaron's paper is the strongest argument for restricting the variety of Internet paths that traffic takes between the Tor client and the Tor network." http://freehaven.net/anonbib/#ccs2013-usersrouted Unfortunately, we have since learned that Tor's path selection has the effect of giving the adversary the ability to generate at least one additional observation path. We first became aware of this in https://trac.torproject.org/projects/tor/ticket/14917, where the change to one guard allowed an adversary to discover your guard by choosing it as a rendezvous point and observing the circuit failure. After the fix for #14917, the onion service will build a connection to a second guard that it keeps in reserve. By using this attack (as well as a similar but more involved attack with unique exit policies and carefully chosen /16 exit node subnets), the adversary can force clients to be observed over two paths whenever they like. So while we may get benefit for moving from three guards to two guards, we don't get much (or any) benefit from moving to two guards to one guard against an active adversary that either connects to onion services, or serves content to clients and runs exits. 2. Guard fingerprintability is lower with one guard An adversary who is watching netflow connection records for an entire area is able to track users as they move from internet connection to internet connection through the degree of uniqueness of their guard choice. There is much less information in two guards than three, but still significantly more than with one guard: https://trac.torproject.org/projects/tor/ticket/9273#comment:3 But, even with one guard, if there are not very many Tor users in your area, you still may be trackable. "Guard bucket" designs are discussed on the blog post and in related tickets, but they are complicated and involve tricky tradeoffs (see https://trac.torproject.org/projects/tor/ticket/9273#comment:4). The best solution that I see to this is to make Tor maintain separate guard choices depending on the current SSID, BSSID, or default gateway router MAC from ARP. The default gateway ARP MAC is probably easiest for us to implement cross-platform and stable across wifi to ethernet. Arguments in favor of switching to two entry guards: 1. One guard allows course-grained netflow confirmation attacks The counterargument based on #14917 above also has an additional wrinkle: an adversary watching a suspect list of clients can easily observe the "temporarily use a second guard" activity using just connection-level ISP/AS netflow logs. To a large-scale netflow adversary, the use of a second guard only when the guard is chosen as the RP confirms not only guard choice, but the IP address of the onion service itself. Again, similar attacks may be possible against exit activity via cleverly crafted exit policies and /16 subnet choice. (Aside: if we allow routers to join any family they like without reciprocation, this attack becomes worse.) Having a dedicated second guard that is always in use will prevent the creation and exclusive use of a new TLS connection just for this request. Instead, the two TLS connections will both remain open and in regular use as long as the client is active. 2. More than one guard allows us to deploy conflux. As mentioned in the blog post, moving to one guard prevents us from deploying conflux -- a research design that improves Tor performance by combining two or more circuits together at an exit node or rendezvous point and load balancing between them: https://www.cypherpunks.ca/~iang/pubs/conflux-pets.pdf Conflux works by giving circuits a 256bit cookie that is send to the exit/RP, and circuits that are then built to the same exit/RP with the same cookie can then be fused together. Conflux was originally studied exclusively for performance, but the technique has other uses as well. If our conflux implementation includes packet acking, then circuits can still survive the loss of one guard node due to DoS, OOM, or churn because the second half of the path will remain open and usable. Furthermore, if exits remember this cookie for a short period of time after the last circuit is closed, the technique can be used to protect against DoS/OOM/guard downtime conditions that take down both guard nodes or destroy many circuits to confirm both guard node choices. In these cases, circuits could be rebuilt along an alternate path and resumed without end-to-end circuit connectivity loss. This same technique will also make things like ephemeral bridges (ie Snowflake/Flashproxy) more usable, because bridge uptime will no longer be so crucial to usability. It will also improve mobile usability by allowing us to resume connections after mobile Tor apps are briefly suspended, or if the user switches between cell and wifi networks. Furthermore, I believe that conflux will also be useful against traffic analysis and congestion attacks. Since the load balancing is dynamic and hard to predict by an external observer, traffic correlation and website traffic fingerprinting attacks will become harder, because the adversary can no longer be sure what percentage of the traffic they have seen (depending on their position and other potential concurrent activity). Similarly, it should also help dampen congestion attacks, since traffic will automatically shift away from a congested guard. So those are the major two arguments on each side. There are some additional minor arguments in favor of two guards (Circuit build timeout works better with more guards because it can avoid the slower guard, and a second guard will also prevent information leaks like https://trac.torproject.org/projects/tor/ticket/24487), but for brevity I decided to mention those only in passing. In terms of deployment, the switch to two guards is an extremely simple one. We should only need to set the NumEntryGuards=2 consensus parameter, and all recent clients will switch over immediately. What do we think? -- Mike Perry
Mike Perry:
2. Guard fingerprintability is lower with one guard
FWIW we at Tails have started working on this topic a couple years ago. We came up with a (far from perfect) plan that is documented there: https://tails.boum.org/blueprint/persistent_Tor_state/
Hello, Thank you for this great summary :) On 2018-03-20 04:57, Mike Perry wrote:
Regarding the question of observability, I would take the opportunity to point out that we have a proposal discussing that question on the mailing list, which changes the bandwidth-weights equations and constraints to achieve a balanced network with an adversary considered in the process (which is not currently). Prop: https://github.com/frochet/wf_proposal/blob/master/waterfilling-balancing-wi... Paper: https://www.freehaven.net/anonbib/#waterfilling-pets2017 This is somewhat linked to this "what would be a good number of entry guards" question since applying our technique increases path diversity (at network-wide scale, for whatever adversary type chosen), and reduces the efficiency of the hoovering adversary model trying to get as much as he can. This would argue is favor of 2 entry guards, because the situation is not as bad as we think. From discussion I had with Aaron at the meeting, it clearly appears that the scheme needs also some IP prefix limits to avoid worst-case scenarios if this technique is used against a relay-adversary model (but again, nothing prevents us to use it against other threat models). So, a bit of work remains but not that much.
I am really enthusiast about multipath, either at the Tor level or even at the transport level: we discussed QUIC at the meeting, but MultipathQUIC could also be a long-term option now that we discuss more than 1 entry guard. However, I would argue that it does not really help against traffic correlation. Our paper at pets18 exploits Tor's forward compatibility feature to design silent cheap, almost instantaneous and perfect active traffic confirmation that does not care about user traffic to succeed. See Section 5, https://petsymposium.org/2018/files/papers/issue2/popets-2018-0011.pdf Maybe the real debate would be to discuss what's the major threat between active/passive attackers, and what do we care about? The question is, why should we care about hardening passive attacker's work when the active form is always as easy? For website fingerprinting, it does seem to be interesting if the attack cannot link the two paths :) Anyway, I believe the 2 guards's benefit outweighs the inconvenience, especially if we also integrate ideas such as Waterfilling :) Best, Florentin
Florentin Rochet:
In this case, Tor's forward compatibility is a bug. The Tor protocol is now versioned at the feature layer, so Postel-style permissive forward compatibility is no longer required: https://gitweb.torproject.org/torspec.git/tree/proposals/264-subprotocol-ver... I have been bothered by the types of side channels you discuss in that paper for some time. They are tricky to remove, but not impossible. See https://trac.torproject.org/projects/tor/ticket/25574 and the child ticket and associated branch. Your paper also states that you got multiplier effects from various issues with Tor's protocol, which improved your results. If we remove these multiplier effects by fixing the protocol and behavior, then it seems to me that adaptive traffic routing will add further uncertainty to congestion-based attacks.
To your point: because I believe it is possible to make both active and passive attacker's jobs hard. I also believe that when we look deeply enough, we will find that improvements that make an active attacker's task harder will also improve things against many, if not all, classes of passive attacker. Roger made a related point that I want to inject here, so I remember to pick it up in the proposal: Roger said that we should consider active vs passive observers here. He contended that against passive observers, one guard is always better, and that we should not discount that benefit while considering an active attacker making circuits via a second guard. However, there are two main issues with calling the Tor-sometimes-uses-a-second-guard "attack" fully "active": 1. It is not always active. In day-to-day operation, clients will use a second guard whenever they pick an exit that is in the same family or /16 of their primary guard (this is because Tor rightly chooses exits first, to avoid leaking guard node choice via exit node choice). Clients will also do this when an onion service's IP, HSDIR, or RP is in the same /16 or family as their primary guard, or actually is that guard. In these cases, they will perform a request over a second guard, with no benefit from multiplexing it with other traffic. For clients unlucky enough to choose guards in popular /16s or in big families, they will be using secondary guards for unmultiplexed activity quite frequently. 2. The active observer and the passive observers here are independent actors. The passive observers can be logging connection activity simply due to the default configuration of their network routers. Active adversaries do not need their collusion in this attack to get the full benefit from being active -- they merely need to have the ability to ask passive observers for the logs they already have, independent of the attack.
For website fingerprinting, it does seem to be interesting if the attack cannot link the two paths :)
This is by far the easiest argument to make for both the switch to two guards, the switch to conflux, and for the addition of padding: we know from the research literature on website traffic fingerprinting that more multiplexing reduces attacker accuracy. Both conflux and always-on two guards increase overall multiplexing, and eliminate cases where lack of multiplexing bites us hard. However, the mere fact that this is true against website traffic fingerprinting suggests to me that increased multiplexing and traffic splitting is useful in other traffic analysis scenarios. -- Mike Perry
On 2018-03-26 20:34, Mike Perry wrote:
Great! Roger indeed told me you were exploring similar problems. As you said, it's tricky to remove because of false positives and because you loose protocol flexibility, and it is not clear to me what the consequences can be over the years. I think we can reason about this as a scalability problem, not in size, but in *time* with its underlying technical issues and security concerns depending on how much we scale the protocol flexibility. It is not really this thread's topic, so I prefer not to talk too much here, but I would be glad to discuss more those problems or to help on any proposal design, and code. Just ping me on IRC :) (Jaym).
Hard to tell, even if the intuition is on your side. It's probably possible to come up with something smarter than the various attacks I did. We will definitely need another round of analysis after any proposed change. While I feel that the various 'multiplier effects' should be removed, I don't really like the approach "patch the weaknesses quick and move on", often we miss to understand the root cause of the various problems, and we end up to add complexity to the software while there might be something better to do.
Also, I believe that there is a common misconception about the strength of a passive adversary against the Tor network. The passive adversary needs to see a sufficient amount of data to keep false positives quite low, and to have a reasonable chance of success, while the active form does not really care about such constraints (depending on the kind of confirmation attack, though). From my observations, most of Tor's traffic is short and unlikely to deliver enough information to a passive observer. Can a passive attacker correlates efficiently on the real network while most of Tor's flow size is below ~ 2000 cells? So, I don't feel that slightly increasing the surface area of passive adversaries is problematic right now, and as you said, the multiplexing effect of multipath may make their job even harder. I am more concerned by the increasing surface area of active attackers, and you seem to argue that the current situation "Tor-sometimes-uses-a-second-guard" is not fully active? So, moving to two guards favors active attackers compared to the current situation, right? I still believe that this problem can be balanced with our proposal, and that the opportunities raised by multipath circuits also worth such loss. Best, Florentin
Mike Perry <mikeperry@torproject.org> writes:
Hello Mike, thanks for writing this post. Thinking about entry guards is extremely important since guards and path selection is pretty much the whole security of Tor. However we should think hard here before flapping from one conf to another. In the grand scheme of things, I see the positives of moving to two guards but also the positives of staying with one guard; I think we need more data to decide what's best and for which threat models. In general, the main argument for me to stay with one guard is to minimize client exposure to guards over a period of time. If we choose two guards instead of one, clients will expose themselves to double the amount of guards over time (not to take into account flaky unreachable guards). Perhaps we could compensate that by increasing the lifetime of guards if we switch to two guards... I think simulations and graphs here to show exposure of guards per number of guards would be useful, and we have some of those already for prop247. OTOH the main arguments for me to switch to two guards is not so much security but performance improvements and reducing congestion of guard nodes.
Hmm, that's a fair point. However, the fact that this behavior exists currently does not mean that it's the best we can do with what we have. Example of what we can do to stop this bad behavior: instead of using our second guard when our "exit" conflicts with our first guard like this: [G2 -> M1 -> G1], we could instead make a 4-hop circuit as follows: [G1 -> M1 -> M2 -> G2]. This would stop us from using our second guard and would hide the obvious signal you are worrying about. (I see that dgoulet also suggested that in the ticket comment:7)
Agreed. I don't think guard fingerprintability was ever a serious argument for switching to a single guard node.
Devil's advocate: I'm not sure how big the suspect list we are thinking about is, or what kind of threat models we are considering here, and I think this matters quite a bit. Because if the suspect list is not big, and the threat models allows the attacker to cause the victim to build circuits, then the attacker could succeed even with simple traffic signals (or shutting down the internet) and traffic monitoring. Also, this whole point relies on our suboptimal fix to #14917. We could improve the situation here by doing more advanced fix like the one suggested above.
I also like the conflux idea a lot but IIUC we are still very far away from it being a reality, since the bridge from the research paper side to the reality side is huge and unbuilt. Seems to me that toggling NumEntryGuards from 1 to 2 is just a tiny part of the work required, and something that could also be done after all the rest of the work gets done... I don't see this as a major argument for switching to two guards, but please correct me if I'm not right.
On 22 Mar (13:46:36), George Kadianakis wrote:
For hidden service, I think you meant [G1 -> M1 -> M2 -> *G1*] considering that G1 is the chosen RP. But also, I think my comment was very wrong 3 years ago, a service already builds a 4 hops to the RP so it should then be this in your example?: [G1 -> M1 -> M2 -> M3 -> G1] This makes it VERY easy for a Guard node to learn that it is the guard of a specific .onion but considering an evil guard of a .onion, there are other effective methods to learn it so I'm not convinced that this path will be worst, just maybe bad for performance. But also this would violate tor protocol of "never having the same hop in the path" so overall making an exeception for this makes me worry a bit :S. I do agree with Mike on this one that we don't get benefit here from 1 to 2 because the code right now is basically a two guard system where the second guard is used rarely. Not only that but an attacker can force you to use that second Guard at will.
Agree with George here. I think 1 or 2 Guards here won't matter much in this attack as mentionned where Alice can just keep injecting traffic pattern on both Guards for identification at the netflow records level.
I'm a bit undecided on this whole switch to 2 Guards for now. For hidden service, there is probably a slight positive gain I would say that is using "equally" two guards instead of the second one being used rarely and on command by the client. I'm not convinced about the security arguments but rather the Guard congestion argument makes more sense for me. And this at the expense of exposing regular clients to more Guards. Although, the "changing Internet" problem is an important one for which I wonder if it could be fixed with its own solution instead of moving to 2 guards at large. Tough call.... Thanks! David -- hgJe5VGAkZPnC/W4iPXnCuf1HcG2evYQqVjeb8Ugb4Y=
David Goulet <dgoulet@torproject.org> writes:
Yep, you are right in everything here.
Why bad for performance? It will be the same length as currently.
But also this would violate tor protocol of "never having the same hop in the path" so overall making an exeception for this makes me worry a bit :S.
I think this is your main objection to this approach, and I understand it, but I'm not sure how well-enforced this tor protocol "rule" is, or how much we should respect it given that this is an important security edge-case that we can solve.
I don't think this is true anymore, if we accept [G1 -> M1 -> M2 -> M3 -> G1] as a reasonable solution.
George Kadianakis:
Even if we allow this case, we still run up against other path restrictions that enable the adversary to force the same new connection behavior though. If we allow the same guard in multiple points in the same circuit, new connections can be forced for the case where the RP is in the same /16 or same family as the guard. This is not the same level of info, but I still believe that the ability to force a new entry connection is an extremely bad property. We can only avoid that by abandoning all circuit restrictions for the RP/exit, or by having two guards. I feel vaguely uncomfortable abandoning all of Tor's path restrictions for certain circuits, but I don't have a good argument against doing that. However, given the other benefits from having two dedicated guards (especially traffic analysis and DoS resistance from conflux, but also performance), I do believe that always using two guards is clearly and strictly better than only using two guards for special cases that can be adversarially controlled. -- Mike Perry
David Goulet:
I strongly disagree. Dumping more traffic onto an already existing, otherwise in-use connection is not the same as the ability to force a new connection that is only used for a single request at a very specific time. These are completely different data retention resolutions, and if the netflow padding works as intended, dumping traffic onto an existing connection will be rolled up into all other traffic during that hour, or longer. At large scale, routers will likely be recording flows at just the connection level only, if that. What this means in practice is the ability for an adversary to go to large ISPs and say "Hey, give me connection logs you already have/can easily generate for these IPs during this specific time period" instead of "Hey, install this custom black box monitoring equipment for me and let me get arbitrary reports from it whenever I want". I know ISPs that have received and refused the black box request case because it was too intrusive. I also know ISPs that have given records over in the connection-level case. I will reply to the discussion of other options for the #14917 fix in the other branch of this thread. -- Mike Perry
On Thu, Mar 22, 2018 at 1:13 PM, Mike Perry <mikeperry@torproject.org> wrote:
Yes it's important to distinguish specific "netflow" style of records analysis, from more general statistical traffic analysis of packets flowing through a network, even if only from a limited to degenerate number (2) of observation / targeting points. Even the simplest of overlay networks could be considered at least a start against the former. While the latter is a hard problem for nearly all of todays networks and why few if any can claim to have resistance to anything resembling GPA / GAA. Listing proposed solutions to the latter, and why adoption of any of them into any overlay (or base layer) network be it existing or new, doesn't seem to really be happening yet... a fine topic for another thread.
Mike Perry:
Minor correction: I misremembered the default active flow timeout for most routers. It is actually 30 minutes, not one hour. (See Section 2.1 of https://gitweb.torproject.org/torspec.git/tree/padding-spec.txt and associated manual links). Also note that this active timeout value is the highest possible resolution of data retention *at the router*. Netflow logging systems also involve a "collector" machine that takes router records and aggregates them further for long term storage (this is also described in Section 2.1 of that spec).
-- Mike Perry
Mike Perry <mikeperry@torproject.org> writes:
Hello! Here is some small analysis of Sybil resistance on 1-guard vs 2-guards. I think this analysis is important even given the #14917 issue, since we could defend against that by lifting those particular path restrictions. I agree that's not ideal, but IMO it's definitely something we should consider as part of a thorough analysis, since by solving #14917 correctly we could still maintain connection to just 1-guard (assuming it's a stable node). === So on to Sybil resistance analysis: For a 5% bandwidth adversary and a single guard, an attacker would have 50% chance to Sybil your G1 (i.e. deanonymize you) after 14 rotations. For a 3.5 month rotation frequency, this means that you would expect your guard to be uncompromised by Sybil's for about 4 years. For a 10% adversary you need 7 rotations for 50% so that's 2 years. Now if we go to two guards, a 5% adversary would need 2 years to Sybil your G1, wheras a 10% adversary could do that in 1 year. All the above numbers are assuming a completely stable guard node, that you only switch because its lifetime expired and not because of reachability issues etc. So in the real world, the actual guarantees are probably lower. In general, I obviously feel more comfortable with the single guard results, but also the dual-guard results are not so bad. === Now with regards to engineering, here is also something to be said about how the prop271 algorithm will handle NumEntryGuards=2: IIRC, the way it's currently handled means that if any of the two first primary guards is down, the algorithm will skip that and choose between the two next available, potentially going into the third primary guard in the list [see how select_entry_guard_for_circuit() uses get_n_primary_guards_to_use()]. This might not be ideal, and perhaps we should tolerate some small unstabilities of the primary guards so that we don't get to expose ourselves to even more guards... Also, we need to look at how guard_selection_get_err_str_if_dir_info_missing() will work after we increase NumEntryGuards, since that function is what caused #21969, and we should make sure that it's not gonna get more annoying if we bump up the number of guards. That's it for now! :) Cheers!
participants (6)
-
David Goulet -
Florentin Rochet -
George Kadianakis -
grarpamp -
intrigeri -
Mike Perry