Opened 5 months ago

Closed 5 months ago

#25870 closed defect (fixed)

Fix vanguard restrictions

Reported by: mikeperry Owned by:
Priority: Medium Milestone: Tor: 0.3.4.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords:
Cc: asn Actual Points:
Parent ID: #25546 Points:
Reviewer: asn Sponsor:

Description

asn pointed out that Tor relays forbid and will warn if clients create paths of the form A - B - A or A - A - A. The vangaurd path restrictions currently will do this, though.

Additionally, they apply exit restrictions while choosing a guard, which I think we should disable. Since vanguard paths are all at least 3 hops before a chosen exit, this is a simple change.

Child Tickets

Change History (18)

comment:1 Changed 5 months ago by mikeperry

Status: newneeds_review

Ok. https://oniongit.eu/mikeperry/tor/commits/bug25870 prevents A - B - A paths and also allows the last hop to be the same as the first.

It still leaves node family and /16 restrictions disabled, which is what we want until we sort out how we want to alter path creation and vanguard selection to make all of that consistent.

I think this should eventually be backported to 0.3.3, since the vanguard script with 0.3.3 could cause warns to be generated at relays if it ever tries to build an A - B - A path (or an A - A path).

comment:2 Changed 5 months ago by mikeperry

Milestone: Tor: 0.3.4.x-final

comment:3 Changed 5 months ago by asn

Reviewer: asn

comment:4 Changed 5 months ago by asn

Hey Mike, can you explain how the branch prevents Tor from building A - B - A paths as it claims?

IIUC, commit 4b61ba2a98 starts allowing A - B - A paths since it removes the guard-to-exit restriction. Then commit ac348ffbae modifies build_middle_exclude_list() which should only exclude possibilities for the middle nodes, hence blocking paths like A - A - B or A - B - B. Am I wrong?

comment:5 in reply to:  4 Changed 5 months ago by mikeperry

Replying to asn:

Hey Mike, can you explain how the branch prevents Tor from building A - B - A paths as it claims?

IIUC, commit 4b61ba2a98 starts allowing A - B - A paths since it removes the guard-to-exit restriction.

This commit by itself only allows A - B - C - A paths. Specifically, it allows C - G - L2 - L3 - G and C - G - L2 - L3 - M - G paths. Remember that vanguard paths are always at least 4 hops long, and sometimes 5. See route_len_for_purpose(). This is done to prevent the adversary from having influence over guard node choice (as you proposed on tor-dev).

Then commit ac348ffbae modifies build_middle_exclude_list() which should only exclude possibilities for the middle nodes, hence blocking paths like A - A - B or A - B - B. Am I wrong?

To see the whole picture, you have to go up to circuit_establish_circuit(). The steps are as follows:

  1. Call onion_pick_cpath_exit(), which picks the exit node. The exit node is either pre-specified (HSDIR, I, RP) or it is chosen randomly.
  2. Call onion_populate_cpath(), which then loops calling onion_extend_cpath() for each hop in the circuit.
  3. The first time through, onion_extend_cpath() calls choose_good_entry server(), which will now choose the entry guard without considering the exit already chosen.
  4. The second time through, it calls choose_good_middle_server(), which calls build_middle_exclude_list(). The exclude list will now contain only the entry guard and the exit (but not any other nodes from their families or /16). Then pick_vanguard_middle_node() uses the exclude list to pick an L2 that is not the guard or the exit.
  5. The third time through, choose_good_middle_server() is called again. Now the exclude list contains G, L2, and E. pick_vanguard_middle_node() then chooses an L3 that is not G, L2, or E.
  6. If the desired_path_len is 4 (from route_len_for_purpose()), we are done. Our path is G - L2 - L3 - E, where G can be E, but neither G or E can be L2 or L3, and L3 cannot be G, L2, or E.
  7. If desired_path_len is 5 (again from route_len_for_purpose()), onion_extend_cpath() is called once more. It again calls choose_good_middle_server(). The exclude list now contains G, L2, L3, E. But this time, middle_node_must_be_vanguard() returns false, and a completely random middle node is chose, but one that cannot be G, L2, L3, or E.

So there can be no A - A - B, A - B - B, or A - B - A sub-paths, since build_middle_exclude_list() is building up the exclude list starting with the exit, and then after that, outwards from the guard, forbidding *any* duplicate node choices for all but the guard and exit positions.

comment:6 Changed 5 months ago by asn

OK, the explanation above makes sense but it's also quite complicated. I'm gonna try to write some unittests and see if I can get a bit more confidence.

Another design-level question: Why are we doing this change just for vanguard circuits and not for all circuits? Is it because we only aim to protect against guard-discovery attacks like #14917 only in vanguard circuits? Or because vanguard-circuits are naturally not 3-hops and so it's eaier to block A - B -A type circs? Or something else?

comment:7 in reply to:  6 Changed 5 months ago by mikeperry

Replying to asn:

OK, the explanation above makes sense but it's also quite complicated. I'm gonna try to write some unittests and see if I can get a bit more confidence.

Another design-level question: Why are we doing this change just for vanguard circuits and not for all circuits? Is it because we only aim to protect against guard-discovery attacks like #14917 only in vanguard circuits? Or because vanguard-circuits are naturally not 3-hops and so it's eaier to block A - B -A type circs? Or something else?

I decided to do the first commit because it is a simple way to prevent the adversary from being able to influence your guard choice without completely changing how we build paths. I only did it for vanguards because we did not agree on a solution for how we want to handle restrictions in the general case. And also yes, with vanguards it does not create any degenerate conditions that induce warnings, but it would with normal circuits.

I decided to do the second commit because the HSLayerN options will generate warnings on relays as-is. I originally removed all restrictions for vanguard circuits because of issues discovered during testing of #13837 and #24487. With two entry guards (which we can also do easily with vanguards) and this patch, #24487 no longer leaks information to later layers, and the HSLayerN options will no longer cause warnings.

Last edited 5 months ago by mikeperry (previous) (diff)

comment:8 Changed 5 months ago by mikeperry

This post provides some more justification: https://lists.torproject.org/pipermail/tor-dev/2018-April/013098.html

This ticket is the first steps towards the proposal at the bottom of that post, which I think covers all of the properties we want.

I would like to figure out how to get a strong version of property #6 in the short term too, though. Right now, with S - G - L2 - L3 - M - RP, the RP gets to learn the guard if we're using one primary guard (because we haven't set the consensus param, or because we have set it but one of the guards is temporarily down). We could add a hack to let that M also be G...

comment:9 Changed 5 months ago by asn

Please see branch bug25870 in my github repo which does some doc clarifications (which I hope you agree with), and also introduces a unittest that does some basic tests on vanguard path selection.

The unittest doesn't actually test many aspects of this ticket (apart from the fact that vanguard circuits need to be longer than 4 hops), but extending it to check the lifting of path restrictions is not so hard. Perhaps I can open a ticket about this and do it before the closing of 034 but after merging this ticket.

comment:10 Changed 5 months ago by asn

Mike's patch looks good to me. Mike please merge my branch to your branch (if you like it), and feel free to mark it as merge_ready.

Also, Mike, it might be worth adding to your commit messages that the changes only affect vanguard circuits and should not affect general-purpose circuits.

comment:11 Changed 5 months ago by mikeperry

Ok I edited the commit message to clarify that A - B - A is for sub-paths. I also added a commit for Property 6. Otherwise asn's commits are taken as-is.

https://oniongit.eu/mikeperry/tor/commits/bug25870_v2

Leaving as needs_review for asn to have a look at the last commit on that branch, which does the refactoring he asked for on IRC, and gives us "strong" property 6.

comment:12 in reply to:  11 ; Changed 5 months ago by asn

Replying to mikeperry:

Ok I edited the commit message to clarify that A - B - A is for sub-paths. I also added a commit for Property 6. Otherwise asn's commits are taken as-is.

https://oniongit.eu/mikeperry/tor/commits/bug25870_v2

Leaving as needs_review for asn to have a look at the last commit on that branch, which does the refactoring he asked for on IRC, and gives us "strong" property 6.

Sounds good. Please check my branch bug25870_rebase which tidies up the _v2
branch a bit by squashing a few commits and giving a more logical flow. Feel
free to not use if you don't like it. Check the diff between bug25870_rebase
and bug25870_v2 to see that the diff is just comments.

BTW, should we use DEFAULT_ROUTE_LEN+1 in the latest commit? What happens in
the case of even longer RP/IP/HSDir circuits that could occur because of
cannibalization? e.g. I remember that Tor clients extend failed IP circuits by
one hop to connect to the next IP, this means that those circuits can end up
being more than 5 hops.

comment:13 in reply to:  12 Changed 5 months ago by mikeperry

Replying to asn:

Replying to mikeperry:

Ok I edited the commit message to clarify that A - B - A is for sub-paths. I also added a commit for Property 6. Otherwise asn's commits are taken as-is.

https://oniongit.eu/mikeperry/tor/commits/bug25870_v2

Leaving as needs_review for asn to have a look at the last commit on that branch, which does the refactoring he asked for on IRC, and gives us "strong" property 6.

Sounds good. Please check my branch bug25870_rebase which tidies up the _v2
branch a bit by squashing a few commits and giving a more logical flow. Feel
free to not use if you don't like it. Check the diff between bug25870_rebase
and bug25870_v2 to see that the diff is just comments.

If you like this better I'm fine with it. I pushed a version to mikeperry/bug25870_rebase that resets the author on the commits that lost it during your rebase.

BTW, should we use DEFAULT_ROUTE_LEN+1 in the latest commit? What happens in
the case of even longer RP/IP/HSDir circuits that could occur because of
cannibalization? e.g. I remember that Tor clients extend failed IP circuits by
one hop to connect to the next IP, this means that those circuits can end up
being more than 5 hops.

I think the current code is what we want. It checks cur_len, which is not the desired length, but the current position in the circuit construction. So when we cannibalize a circuit to add another hop, it will be cur_len = 5/6/more. The guard node will already have been allowed in the 4th position (and in the IP/RP). We could consider adding cases to allow those additional positions to also be the guard... I am not sure if that matters/is worth it though?

comment:14 Changed 5 months ago by asn

Status: needs_reviewmerge_ready

Sounds good. I think we good here! Let's have nickm take a peek at it! Cheers!

The branch to review is at mikeperry/bug25870_rebase.

comment:15 Changed 5 months ago by nickm

Looks plausible to me; running it through travis now.

Is there a spec branch for this?

comment:16 Changed 5 months ago by nickm

(Travis likes it fine; I'll merge it once there's a relevant spec branch to go with it.)

comment:17 Changed 5 months ago by mikeperry

Ok. I added a commit to mikeperry/bug25870_rebase to document the path restriction changes in the manpage.

There is also a small spec patch in mikeperry/bug25870 in my torspec remote.

comment:18 Changed 5 months ago by nickm

Resolution: fixed
Status: merge_readyclosed

Merged!

Note: See TracTickets for help on using tickets.