Opened 12 months ago

Last modified 7 weeks ago

#26137 new enhancement

Integrate AS-aware circuit selection

Reported by: cypherpunks Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: needs-proposal tor-client traffic-analysis path-selection
Cc: cypherpunks Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

The "ASToria" Tor client has been available since 2015, but I haven't seen any analysis of it from Tor Project or any plans to integrate any of the ideas. The general idea behind ASToria is to improve path selection to minimize the risk of AS-level traffic correlation. It is effectively an enhanced version of Tor's current naïve path-selection behavior which simply involves avoiding circuits with relays that share too small of a subnet. This is a similar proposal to #10221, which was created before this paper was published.

Tor should integrate AS-aware circuit selection (whether by including the ASToria code or creating a bespoke solution), or at the very least integrate AS-aware circuit measurement to make potential transition easier in the future. Additionally, this change would require no modifications of the Tor protocol and would be completely backwards-compatible with the network. From the paper's abstract:

We find that up to 40% of all circuits created by Tor are vulnerable to attacks by traffic correlation from Autonomous System (AS)-level adversaries, 42% from colluding AS-level adversaries, and 85% from state-level adversaries. In addition, we find that in some regions (notably, China and Iran) there exist many cases where over 95% of all possible circuits are vulnerable to correlation attacks, emphasizing the need for AS-aware relay-selection.

Astoria reduces the number of vulnerable circuits to 2% against AS-level adversaries, under 5% against colluding AS-level adversaries, and 25% against state-level adversaries. In addition, Astoria load balances across the Tor network so as to not overload any set of relays.

Key points:

  • The code has already been written and just needs a cleanup and some review.
  • Load balancing is done to prevent individual relays from being overloaded.
  • No changes to the protocol are needed, making this fully backwards-compatible.
  • AS-level traffic analysis risk is reduced from 40% to 2% for any given circuit.

https://arxiv.org/abs/1505.05173
https://github.com/sbunrg/Astoria

Child Tickets

Change History (6)

comment:1 Changed 12 months ago by teor

Keywords: needs-proposal added
Priority: HighMedium

This needs a proposal, and then it can go on the roadmap.

Any proposal should analyse the impact of related proposals, particularly 271 and 291:
https://gitweb.torproject.org/torspec.git/tree/proposals

comment:2 in reply to:  1 ; Changed 12 months ago by cypherpunks

Replying to teor:

This needs a proposal, and then it can go on the roadmap.

I wasn't sure if it required a proposal since the code is already written and an analysis of the idea (implementation details rather than just raw code, etc) is present in the research paper.

Any proposal should analyse the impact of related proposals, particularly 271 and 291:
https://gitweb.torproject.org/torspec.git/tree/proposals

It would have no impact whatsoever on those proposals, since the AS-aware path selection does not depend on any particular guard rotation schedule. It will simply take into account what AS the guards are in when it selects the other two relays. This means it's also future-proofed for any changes to guard rotation behavior that happens down the road.

As someone who has never written a proposal for Tor, is there anything I can do to speed up the process? I have extensive experience in information security, but do not know the ins and outs of the Tor protocol itself or the proposal process, so I would not feel comfortable writing the proposal without knowing more about the general requirements (other than those described in 001-process.txt).

Last edited 12 months ago by cypherpunks (previous) (diff)

comment:3 in reply to:  2 ; Changed 12 months ago by teor

Replying to cypherpunks:

Replying to teor:

This needs a proposal, and then it can go on the roadmap.

I wasn't sure if it required a proposal since the code is already written and an analysis of the idea (implementation details rather than just raw code, etc) is present in the research paper.

We require a proposal so that we specify precisely what the code is meant to do. Then we can write tests to ensure that's what the code actually does.

Also, our experience of research code is that it often needs significant work to be suitable for long-term use on millions of tor clients.

Any proposal should analyse the impact of related proposals, particularly 271 and 291:
https://gitweb.torproject.org/torspec.git/tree/proposals

It would have no impact whatsoever on those proposals, since the AS-aware path selection does not depend on any particular guard rotation schedule. It will simply take into account what AS the guards are in when it selects the other two relays. This means it's also future-proofed for any changes to guard rotation behavior that happens down the road.

I would encourage you to read the proposals and the relevant threads on the tor-dev mailing list.

In particular, the "Eliminate path restrictions entirely" section of proposal 291 is relevant, because it conflicts with adding AS path restrictions:
https://lists.torproject.org/pipermail/tor-dev/2018-April/013057.html

As someone who has never written a proposal for Tor, is there anything I can do to speed up the process? I have extensive experience in information security, but do not know the ins and outs of the Tor protocol itself or the proposal process, so I would not feel comfortable writing the proposal without knowing more about the general requirements (other than those described in 001-process.txt).

We get a lot of proposals that are someone's first proposal.

You could read proposal 291, and use it as a model to write a draft proposal. Then you can send it to the tor-dev mailing list, and ask for help improving it.

comment:4 in reply to:  3 Changed 12 months ago by cypherpunks

Replying to teor:

Also, our experience of research code is that it often needs significant work to be suitable for long-term use on millions of tor clients.

That's very true. Luckily, the code is not too convoluted.

In particular, the "Eliminate path restrictions entirely" section of proposal 291 is relevant, because it conflicts with adding AS path restrictions:
https://lists.torproject.org/pipermail/tor-dev/2018-April/013057.html

Wait, is this section advocating for allowing a single relay to be used as both a guard and exit in a single circuit? Or does it just mean that the guard can be used for the RP, IP, or HSDir? Anyway, it would not necessarily conflict with that as it could be entirely optional and controlled by the configuration file (just like the use of a limited number of guards itself is technically optional).

We get a lot of proposals that are someone's first proposal.

You could read proposal 291, and use it as a model to write a draft proposal. Then you can send it to the tor-dev mailing list, and ask for help improving it.

That sounds like a good idea. I think I will consider doing that.

Last edited 12 months ago by cypherpunks (previous) (diff)

comment:5 Changed 9 months ago by nickm

Milestone: Tor: unspecified

comment:6 Changed 7 weeks ago by cypherpunks

Cc: cypherpunks added
Note: See TracTickets for help on using tickets.