Filename: 354-relaxed-restrictions.md
Title: Relaxing Path Restrictions in Arti
Author: Mike Perry
Created: 20 Feb 2025
Status: Open

Background

Tor has the following client-side restrictions on paths:

  • No two relays from same /16 subnet
  • No two relays from same relay-provided family
  • No two relays from same user configured node families
  • The same relay can't be used in a circuit twice (except between two halves of a Rend circuit)
  • Different Guards for each leg in a conflux set
  • Different middles for each leg in a conflux set

Additionally, Tor relays will enforce the following restrictions:

  • No self-extends allowed (relay A forbids A-A)
  • No repeat-extends allowed (relay B forbids A-B-A)

C Tor also makes some exceptions to these rules (which we will not document here), in certain cases related to Bridges, Vanguards, and onion service circuits.

Problems with restrictions

Restrictions can leak path information to local network observers, relays, websites, and services, in the following cases:

  1. When restrictions prevent certain Rendezvous Points from being connected to by onion services, onion clients can determine which Guard(s) are in use by that service, with repeat connections.

  2. When restrictions prevent certain Rendezvous Points from being chosen by clients due to their Guard(s), onion services can learn the Guard being used (by causing repeat reconnections).

  3. When restrictions prevent certain Vanguards from being used due to the Guards currently in use, Guard discovery is possible, using repeat connections.

  4. When restrictions cause clients to use additional Guard nodes than the ones they usually use, the local network adversary knows where the client exited from, or what HSDir, Intro Point, or Rend Point they accessed.

  5. When restrictions prevent certain Exit relays from being chosen, websites learn information about the Guard nodes in use, especially when users log in over the long-term.

  6. When restrictions prevent the use of certain IP and HSDirs, a malicious service can learn the Guard or Bridge being used by clients (by causing repeat connections).

These issues vary depending on the number of Guards/Bridges configured. They are worst with one hard-coded Guard or one Bridge, but can also reappear with multiple Guards/Bridges when conflux is involved, or when both Guards are in the same family or /16 as other Exits.

C-Tor tries to work around most of these issues by exempting cases, using more than one Guard by default, and not applying restrictions to Bridge use. Since these exemptions were arrived at piecemeal due to specific bugs and attacks, a redesign is warranted.

One way to look at these problems is that restrictions represent a trade-off between preventing Guard discovery attacks versus preventing end-to-end correlation attacks.

However, this is a lop-sided tradeoff, because restrictions only prevent end-to-end traffic correlation by honest relays. Malicious relays can omit families and avoid being in the same /16 as peers.

Additionally, traffic analysis attacks performed by ISPs are less accurate than those performed by relays, due to circuit multiplexing. This is true even for clients with minimal concurrent activity. Relays also provide far superior vectors for side channels. The adversary is motivated to run malicious relays for these reasons, rather than try to observe specific /16s. See Proposal 344 for these details.

Furthermore, in all of these cases, the information leaked by obeying restrictions actually aides in traffic analysis, rather than hinders it. Effectively, this additional information changes traffic correlation attacks into significantly easier traffic confirmation attacks, because the adversary can use the leaked information to drastically reduce the set of traffic they must consider (such as only monitoring a specific Guard node at a specific adversary controlled time).

In fact, all successful real-world traffic analysis attacks against Tor have relied on either Guard discovery or other ways to get additional information about the local network, to reduce false positives and make the set of traffic that needs to be observed manageable. (See Section 2 of Proposal 344).

There have been no known real-world cases of end-to-end correlation being used by any relays of Tor, without the aid of Guard discovery and supporting side channels.

Short-Term Proposal

In the short term, we can reduce the harm caused by restrictions by applying the following rules during node selection:

  • Choose the Exit, HSDir, IP, or RP without considering restrictions
  • Choose Guard, Bridge, and Vanguards hops without considering restrictions
  • Choose any remaining middle nodes such that subnet, relay family, and user family restrictions apply with respect to the next hop (Exit, HSDir, IP, or RP)
  • Reject any resulting circuits with A-A and A-B-A sub-paths
  • If building a conflux leg: Reject any circuits that share relays with the other conflux leg(s) in the current conflux set.

Note: We specify these as rule form for ease of explanation; however a naive implementation that performs these rules in a loop (where the reject rules cause a full restart of circuit selection) could end up failing to terminate. See "Remaining Issues" directly below.

Effectively, this will mean that our family and /16 restrictions are used only to prevent an entire path from being built from relays in the same family or subnet.

Note: This means that we believe that having the same node A in A-B-C-A position in onion service RP circuits is no more harmful than A-B-C-A', where A' is a different node instance run by a malicious operator who omits Family information. We can come up with no way to store side channel or even full correlation state internally in a Tor relay that could not also be transmitted in time to another relay instance A'. Furthermore, trying to prevent this case by using different Guards actually gives the adversary additional traffic analysis information, by letting them control Guard (non-)usage via RP selection.

When onion service circuits stubs are pre-built without a known HSDir, IP, or RP, the set of pre-built stubs MUST be checked for these rules when the HSDir, IP, or RP becomes known. Because Guards and Vanguards are exempt from most restrictions, these checks are limited to the A-A, A-B-A checks, as well as those stubs that have a non-Vanguard random Middle node appended to them.

Remaining issues

Unfortunately, this still leaks information in the conflux Exit case, if the user is unlucky enough to have a Guard+Exit as one of their two Guards, because this would result in A-B-A on one of the legs.

Since Exits are usually scarce, is it very rare for Guard+Exits to actually be used as Guards. So, for now, we should still use a third Guard when using this Exit, as we hope to completely eliminate Guard+Exit flagged relays, making this case impossible.

Since conflux onion services use two separate Rend Points, and join at the service, we do not expect them to have this issue.

Finally, there is a UX issue where users can be surprised by the same hop appearing twice in their path, such as in this reddit post.

Arti's notion of a "flexible" relay restriction can be used to exclude the same relay from being chosen twice, to avoid these kinds of scary-looking (but not actually dangerous) paths. A flexible restriction is one that we ignore if it prevents us from finding any relays that work. Care needs to be taken not to use extra Guards, or avoid using specific relays based on Guards, Bridges, or Vanguards, in this case, even if that may "work" via other choices. Many of these info leaks can use repeated connections. Even if all connections "work", it is still possible to infer Guards/Bridges/Vanguards based on what relays are simply not used for certain hops in the path, across multiple connections.

C-Tor and Spec migration

C-Tor's patchwork of exemptions does not have any known serious problems; however it is easy to re-introduce problems, and there may be additional exceptions that leak information depending on certain configuration options (especially Bridge usage). We will not be making changes to C-Tor for this proposal.

We will need to update Path-Spec and Vanguards-Spec, to reflect these updates to restrictions, to avoid confusion.

Long-Term Notes

In the long term, we expect the following changes to routing:

  • The consensus stops assigning combined Guard+Exit flags to relays
  • The consensus assigns exactly enough Guard BW to Guard flag position to avoid Guard use in middles or Exits (ie: variable Guard flag bw cutoff)
  • Vanguards (and other middles) are chosen only from Stable, and not Guard+Stable (because there will be no Guard+Stable)
  • GuardSets allow us to safely group guards together in sets of 3-5, based on AS, Family, etc

Right now, the main benefit we get from these long term changes is that removing Guard+Exit flagged nodes fixes the conflux 3rd Guard problem described above.

However, it may be the case that these changes allow us to re-enable further restrictions, as well.

Alternative Ideas

Various changes make it possible to preserve restrictions, but with even more complexity than currently exists in C-Tor.

These include:

  • Making sure primary Guards are not in the same family
  • Making sure L2/L3 Vanguards represent multiple families
  • Making bridges unwilling to serve as Ipt/RPt/HsDir
  • Making Guards unwilling to serve as Ipt/Rpt/HsDir
  • Making Ipt locations "sticky", so that when you need to make a new intro point circuit, you try to make it to the same node as your last one if possible.
  • When people configure bridges - especially when they configure guards as bridges - maybe recommend that they configure at least two.