Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#5956 closed defect (implemented)

Thresholds of nodes to build circuits should be tunable and maybe consider weights too

Reported by: nickm Owned by: mikeperry
Priority: Very High Milestone: Tor: 0.2.4.x-final
Component: Core Tor/Tor Version:
Severity: Keywords: maybe-proposal tor-client MikePerry201301
Cc: Actual Points:
Parent ID: #5456 Points:
Reviewer: Sponsor:

Description

On #5343, Mike notes that he doesn't like the 1/3 threshold for having sufficient exit nodes to build circuits.

Arguably, this threshold (and the other threshold changed in #3196) should be consensus parameters too.

Arguably, there should also (or instead?) be a minimum threshold by weight.

I'm marking this for 0.2.4.x, but it's likely to be very backportable.

Child Tickets

Change History (26)

comment:1 Changed 7 years ago by mikeperry

Parent ID: #5456

comment:2 Changed 7 years ago by mikeperry

Should we also include the parameter tuning for #5458 under this ticket, or will that need its own ticket?

It's my opinion that the #5458 parameters should start on the lenient side, and then tighten as we get more data.

comment:3 in reply to:  2 Changed 7 years ago by nickm

Replying to mikeperry:

Should we also include the parameter tuning for #5458 under this ticket, or will that need its own ticket?

I believe that in my version of the #5458 patch, I already added the parameters. So calling that question moot.

comment:4 Changed 7 years ago by mikeperry

I'm sorry, I misbrained the title of this ticket. I've created #6135 for tuning these parameters and the ones for #5458.

comment:5 Changed 7 years ago by nickm

Keywords: maybe-proposal added

comment:6 Changed 7 years ago by nickm

Keywords: tor-client added

comment:7 Changed 7 years ago by nickm

Component: Tor ClientTor

comment:8 Changed 7 years ago by mikeperry

What forms of this can we call "small-feature" and not "proposal-needed"?

I like the idea of doing the consensus weight threshold in combination with the exit count threshold. My gut says "wait until (70% consensus-weight && 40% node count)", or some nearby numbers. I could also see 75% weight && 33% node count, if we like fractions.

comment:9 Changed 7 years ago by nickm

It's not like it needs over one or two pages worth of proposal. it does indeed seem like a small thing to me.

I think you'd want to have other thresholds too, like the way that we insist on a threshold of exit nodes. Perhaps we should also insist on a threshold of guards before picking guards. Perhaps we should care about other stuff too!

comment:10 Changed 7 years ago by mikeperry

Oh, yah. We should probably use all of the consensus bandwidth weights and compute the real smartlist_choose_by_bandwidth total weight for each rule, and set limits for each of these rule weight fractions of the consensus we have.

I still think this is small-feature. I don't think anybody else is really going to care about it anyways. Nobody else but me seemed to care about your initial choices. Even lodger seems to have wondered off already ;).

comment:11 Changed 7 years ago by nickm

Milestone: Tor: 0.2.4.x-finalTor: 0.2.5.x-final

comment:12 Changed 7 years ago by mikeperry

Keywords: MikePerry201301 added
Milestone: Tor: 0.2.5.x-finalTor: 0.2.4.x-final
Owner: set to mikeperry
Priority: normalcritical
Status: newassigned

Directory guards actually make this pretty damn important for 0.2.4.x. I'm willing to postpone Firefox work to get this done. I'd rather have our users vulnerable to remote exec for a couple extra days than route capture/deanonymization for 6mos to 1yr.

comment:13 Changed 7 years ago by nickm

Is there a design for what this code should do for 0.2.4.x? Can you write one real quick?

Easiest version would be "require X% of nodes; X% of exits." with both Xs being a consensus parameter. Next-easiest would be "require X% of node and X% of exit bandwidth", with both Xs being a consensus parameter. Is that what you had in mind?

comment:14 Changed 7 years ago by arma

Early thoughts from skimming ticket:

A) We saw a variety of bugs in testingtornetworks when combined with raising these thresholds like we did in 0.2.3. They had to do with not retrying certain things quickly, and combined with not being willing to build circuits until you have enough things, caused Tors to be dead in the water for long periods of time before they start. I'm not sure if any of these bugs matter in non-testingtornetwork scenarios, but maybe they do. So I'd be wary of cranking up the numbers any more without further investigation.

B) That said, my gut is to agree with the "it matters even more now that we have directory guards" point. Maybe we should require some bigger thresholds before we're willing to choose guards? I guess in the past we fetched dir info before picking guards, but now there are more chickens-and-eggs to consider. I begin to wonder if our switch to directory guards was premature?

comment:15 Changed 7 years ago by nickm

Status: assignedneeds_review

Oh hey, that wasn't too hard. See branch "bug5956" in my public repository.

comment:16 Changed 7 years ago by mikeperry

Ok, I've reviewed this branch. I think FRAC_USABLE_NEEDED should be a consensus parameter for the reasons Roger mentions in his #A thoughts. Also, since we went with the product-of-probabilities implementation, it is possible (but probably less likely than Roger's concern) that we will later discover that the value we thought was appropriate for the #define is not a good one at all (due to surprise interactions with node positioning and node flag weight).

I realize I may have bit of a fetish for consensus over-parameterization, but I do think it's better to have the option to fix this threshold retroactively than require people to upgrade (again) for their clients to work properly/safely.

Unrelated to this bug, but also present in the diff delta: circuit_build_times_get_bw_scale() has a horrible name. It has nothing to do with CBT. It's returning a consensus param that's only used for bandwidth weights. Maybe we should just change it to network_balancing_weights_get_scale_param() or similar while we're at it?

Other than that, I don't see any major issues.

comment:17 Changed 7 years ago by nickm

Thanks, Mike!

I've pushed a patch to make it parameterized and configurable to "bug5956."

I'm fine renaming circuit_build_times_get_bw_scale to network_balancing_weights_get_scale_parameter or whatever if you like; if you make a patch, I will apply it ... but only if it includes Doxygen documentation for that function. I think one reason that function might be misnamed is that nobody ever actually explained what it was supposed to do.

I'm writing a torspec patch for this branch too.

comment:18 in reply to:  17 Changed 7 years ago by rransom

Replying to nickm:

I'm fine renaming circuit_build_times_get_bw_scale to network_balancing_weights_get_scale_parameter or whatever if you like; if you make a patch, I will apply it ... but only if it includes Doxygen documentation for that function. I think one reason that function might be misnamed is that nobody ever actually explained what it was supposed to do.

It doesn't do anything in 0.2.4.x. In 0.2.3.x and earlier, it allows dirauths to scale relays' selection probabilities down to less than 1 so that clients with the old broken side-channel-bugged relay-selection routine won't choose them.

comment:19 Changed 7 years ago by nickm

The spec change is bug5956 in my public repository.

comment:20 Changed 7 years ago by nickm

Whoops, make that "The spec change is 'bug5956-spec' in my public torspec repository."

comment:21 Changed 7 years ago by andrea

Starting code review:

42c4418bed2cdad029404cca39fc60f7d7235aab: Looks straightforward and unobjectionable.

d602241687c771feb5d0344b5d5643039ac601c6: Looks correct to me; there is a typo ('decriptor') in comment for frac_nodes_with_decriptors(), though.

86ee5a6bd15ef9f564eeeb1b723ef3ec101e579c: What's the '/* that's a bug actually. */' in count_usable_descriptors() about?

7e6f79619c0aba125888d20bf3aaa5f39f11d4c5: Just formatting.

d602241687c771feb5d0344b5d5643039ac601c6:

The calculation looks correct to me; the assumption that it's a straightforward product like that does depend on the path-usability function (i.e., a boolean-valued function of a path indicating if we can use it) is just a logical AND of analogous usability functions for each node, so all node-to-node links are permissible. This will have to get rethought if we ever permit IPv6-only nodes.

Observation: we base our belief in whether a node is usable for this purpose just on whether we get a descriptor. If most of the entry points we have descriptors for are unreachable, what do we do? Do we keep trying until we find one? If a prospective censor went to the trouble of running a high-bandwidth middle node long enough for it to get the guard flag, and then blocked connections to most or all other nodes, could they force users in their network onto the entry of their choice and thus get the probability they can deanonymize down to linear in the fraction of exits they control?

e23371bf55b2f880af8675e883b6f48876c18428: How does min_paths_for_circs_pct get into the consensus for this? Is making that work going to be a separate thing?

End code review. I think this is okay to merge.

comment:22 Changed 7 years ago by mikeperry

Random thought that may be a horrible idea: Do we want to make compute_frac_paths_available() return only f_mid*f_exit if guards have already been chosen? Ie if this is a re-bootstrap of a previously used client?

comment:23 in reply to:  21 Changed 7 years ago by nickm

Replying to andrea:

Starting code review:
d602241687c771feb5d0344b5d5643039ac601c6: Looks correct to me; there is a typo ('decriptor') in comment for frac_nodes_with_decriptors(), though.
86ee5a6bd15ef9f564eeeb1b723ef3ec101e579c: What's the '/* that's a bug actually. */' in count_usable_descriptors() about?

Fixed in fixup! commits on that branch.

d602241687c771feb5d0344b5d5643039ac601c6:

The calculation looks correct to me; the assumption that it's a straightforward product like that does depend on the path-usability function (i.e., a boolean-valued function of a path indicating if we can use it) is just a logical AND of analogous usability functions for each node, so all node-to-node links are permissible. This will have to get rethought if we ever permit IPv6-only nodes.

Right.

Observation: we base our belief in whether a node is usable for this purpose just on whether we get a descriptor. If most of the entry points we have descriptors for are unreachable, what do we do? Do we keep trying until we find one? If a prospective censor went to the trouble of running a high-bandwidth middle node long enough for it to get the guard flag, and then blocked connections to most or all other nodes, could they force users in their network onto the entry of their choice and thus get the probability they can deanonymize down to linear in the fraction of exits they control?

Good observation; that's not the attack this tries to stop, though. If we can come up with a good defense/detection mechanism for that, we should have a design for it and try to build it.

e23371bf55b2f880af8675e883b6f48876c18428: How does min_paths_for_circs_pct get into the consensus for this? Is making that work going to be a separate thing?

AUthorities have a torrc option they can use to vote on things.

End code review. I think this is okay to merge.

Great; thanks!

comment:24 in reply to:  22 Changed 7 years ago by nickm

Replying to mikeperry:

Random thought that may be a horrible idea: Do we want to make compute_frac_paths_available() return only f_mid*f_exit if guards have already been chosen? Ie if this is a re-bootstrap of a previously used client?

I think that's a find thing to analyze for a proposal for 0.2.5 or later, if it turns out to be wise. My personal intuition says that the complexity might not be worth it, but design-by-intuition gets bad designs. :)

comment:25 Changed 7 years ago by nickm

Resolution: implemented
Status: needs_reviewclosed

Squashed and merged. Thanks, all!

comment:26 Changed 7 years ago by mikeperry

athena: FYI, we've been brainstorming guard-blocking defenses in #5462. It's sounds like a simple thing to detect at first, but differentiating between guard blocking and port blocking makes it a little trickier. Couple that with network connectivity issues and a potentially active and reactive adversary, and it's something that might take a bit to get right. I think we've got a good start on the ideas in #5462 such that a proposal could be written on the 0.2.5.x timeframe, but your input would probably be helpful.

Note: See TracTickets for help on using tickets.