Opened 6 years ago

Closed 4 years ago

#12466 closed defect (fixed)

Possible primary guard node skip when some guards are down

Reported by: asn Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-guard, tor-client, 026-triaged-1, 027-triaged-1-out, tor-03-unspecified-201612
Cc: isis Actual Points:
Parent ID: Points:
Reviewer: Sponsor:


This is another possible guard node skip (similar to #12450), that can make Tor skip some of the higher priority guards and prefer guards in the lower end of the list.

#12450 applies even for NumEntryGuards=1, but this one applies only when NumEntryGuards is larger than 1.

So, this loop [0] in choose_random_entry_impl():
will try to add guards to live_entry_guards till it contains NumEntryGuards entry guards, which is 3 currently.

Finally this code [1] will pick one of them:

Let's assume that our state file contains many guards (50 or so), so we have plenty of nodes to add to our live_entry_guards. It also so happens that the third entry guard in our entry_guards list just went dead.

So, now we need to make a circuit. We go over loop [0], and add the first three guards to live_entry_guards, then [1] picks the third entry node to be used by the circuit. Unfortunately, since that node is down, the circuit dies. And we go back to choose_random_entry_impl() to get a new entry node.

So, now we go over the loop [0], and we add the first two entry guards and the fourth one (since the 3rd entry guard is now marked as unreachable). If [1] now picks the fourth entry guard, we have "skipped" our primary guards and selected a lower priority one.

As a matter of fact, we can imagine this procedure happening a lot of times, and if we are very unlucky, Tor will keep on adding new dead entry guards to our live_entry_guards list and then it will keep on choosing them. This will result in a live_entry_guards list always containing the first two entry guards (let's call them the primary entry guards) and then the 48th entry guard in our list. Then Tor will choose the 48th entry guard and succeed on making a circuit, and there you have it, we just picked a very low priority entry guard for our circuit.

This is theoretically possible, but not very likely to happen in practice. But since we are trying to pay more attention to guard node security, maybe it should be fixed.

Child Tickets

Change History (10)

comment:1 Changed 6 years ago by asn

I think part of the problem here, is that when we think of NumEntryGuards being 3, we think "There should only be 3 possible first-hops for any circuit.".

However, when choose_random_entry_impl() thinks of NumEntryGuards being 3, it thinks "For every entry guard selection for a circuit, I need to have 3 possible node picks.".

Since different circuits have different requirements (others need Stable nodes, other need DirCache, etc.), these two definitions are not equivalent (since the first 3 nodes in our entry guard list will probably not fulfil all those requirements.).

I call the first 3 nodes in our entry guard list the primary guards of a client. The rest of the nodes in our entry guard are auxiliary guards, used only when the first 3 cannot satisfy us (because they are down, or because they are not Fast, etc.).

To bring Tor's behavior closer to the first definition (which seems like the right one), maybe it makes sense to always try to pick a primary guard if it satisfies the requirements of a circuit, even if we don't have 3 possible choices to pick from.

Unfortunately, the implementation of this idea does not sound that easy, since the concept of a primary guard is not so clear in real life. For example, is a node that has been down for 2 weeks still a primary guard (even if it's on the top of the entry guard list)?

comment:2 Changed 6 years ago by nickm

Keywords: 026-triaged-1 added

comment:3 Changed 6 years ago by nickm

Milestone: Tor: 0.2.6.x-finalTor: 0.2.7.x-final

comment:4 Changed 6 years ago by nickm

Status: newassigned

comment:5 Changed 6 years ago by nickm

Keywords: 027-triaged-1-out added

Marking triaged-out items from first round of 0.2.7 triage.

comment:6 Changed 6 years ago by nickm

Milestone: Tor: 0.2.7.x-finalTor: 0.2.???

Make all non-needs_review, non-needs_revision, 027-triaged-1-out items belong to 0.2.???

comment:7 Changed 5 years ago by isis

Cc: isis added
Severity: Normal

comment:8 Changed 4 years ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:9 Changed 4 years ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:10 Changed 4 years ago by nickm

Resolution: fixed
Status: assignedclosed

Prop 271 makes the rules for skipping and retrying guards much more clear -- and hopefully much better.

Note: See TracTickets for help on using tickets.