diff options
Diffstat (limited to 'spec/path-spec/detecting-route-manipulation.md')
| -rw-r--r-- | spec/path-spec/detecting-route-manipulation.md | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/spec/path-spec/detecting-route-manipulation.md b/spec/path-spec/detecting-route-manipulation.md new file mode 100644 index 0000000..76be4d1 --- /dev/null +++ b/spec/path-spec/detecting-route-manipulation.md @@ -0,0 +1,202 @@ +<a id="path-spec.txt-7"></a> + +# Detecting route manipulation by Guard nodes (Path Bias) {#pathbias} + +The Path Bias defense is designed to defend against a type of route +capture where malicious Guard nodes deliberately fail or choke circuits +that extend to non-colluding Exit nodes to maximize their network +utilization in favor of carrying only compromised traffic. + +In the extreme, the attack allows an adversary that carries c/n +of the network capacity to deanonymize c/n of the network +connections, breaking the O((c/n)^2) property of Tor's original +threat model. It also allows targeted attacks aimed at monitoring +the activity of specific users, bridges, or Guard nodes. + +There are two points where path selection can be manipulated: +during construction, and during usage. Circuit construction +can be manipulated by inducing circuit failures during circuit +extend steps, which causes the Tor client to transparently retry +the circuit construction with a new path. Circuit usage can be +manipulated by abusing the stream retry features of Tor (for +example by withholding stream attempt responses from the client +until the stream timeout has expired), at which point the tor client +will also transparently retry the stream on a new path. + +The defense as deployed therefore makes two independent sets of +measurements of successful path use: one during circuit construction, +and one during circuit usage. + +The intended behavior is for clients to ultimately disable the use +of Guards responsible for excessive circuit failure of either type +(for the parameters to do this, see ["Parameterization"](#parameters) below); +however known issues with the Tor network currently +restrict the defense to being informational only at this stage +(see ["Known barriers to enforcement"](#barriers)). + +<a id="path-spec.txt-7.1"></a> + +## Measuring path construction success rates {#construction-success-rate} + +Clients maintain two counts for each of their guards: a count of the +number of times a circuit was extended to at least two hops through that +guard, and a count of the number of circuits that successfully complete +through that guard. The ratio of these two numbers is used to determine +a circuit success rate for that Guard. + +[Circuit build timeouts](./learning-timeouts.md) +are counted as construction failures if the +circuit fails to complete before the 95% "right-censored" timeout +interval, not the 80% timeout condition. + +If a circuit closes prematurely after construction but before being +requested to close by the client, this is counted as a failure. + +<a id="path-spec.txt-7.2"></a> + +## Measuring path usage success rates {#usage-success-rate} + +Clients maintain two usage counts for each of their guards: a count +of the number of usage attempts, and a count of the number of +successful usages. + +A usage attempt means any attempt to attach a stream to a circuit. + +Usage success status is temporarily recorded by state flags on circuits. +Guard usage success counts are not incremented until circuit close. A +circuit is marked as successfully used if we receive a properly +recognized RELAY cell on that circuit that was expected for the current +circuit purpose. + +If subsequent stream attachments fail or time out, the successfully used +state of the circuit is cleared, causing it once again to be regarded +as a usage attempt only. + +Upon close by the client, all circuits that are still marked as usage +attempts are probed using a RELAY_BEGIN cell constructed with a +destination of the form 0.a.b.c:25, where a.b.c is a 24 bit random +nonce. If we get a RELAY_COMMAND_END in response matching our nonce, +the circuit is counted as successfully used. + +If any unrecognized RELAY cells arrive after the probe has been sent, +the circuit is counted as a usage failure. + +If the stream failure reason codes DESTROY, TORPROTOCOL, or INTERNAL +are received in response to any stream attempt, such circuits are not +probed and are declared usage failures. + +Prematurely closed circuits are not probed, and are counted as usage +failures. + +<a id="path-spec.txt-7.3"></a> + +## Scaling success counts {#scaling} + +To provide a moving average of recent Guard activity while +still preserving the ability to verify correctness, we periodically +"scale" the success counts by multiplying them by a scale factor +between 0 and 1.0. + +Scaling is performed when either usage or construction attempt counts +exceed a parametrized value. + +To avoid error due to scaling during circuit construction and use, +currently open circuits are subtracted from the usage counts before +scaling, and added back after scaling. + +<a id="path-spec.txt-7.4"></a> + +## Parametrization {#parameters} + +The following consensus parameters tune various aspects of the +defense. + +```text + pb_mincircs + Default: 150 + Min: 5 + Effect: This is the minimum number of circuits that must complete + at least 2 hops before we begin evaluating construction rates. + + pb_noticepct + Default: 70 + Min: 0 + Max: 100 + Effect: If the circuit success rate falls below this percentage, + we emit a notice log message. + + pb_warnpct + Default: 50 + Min: 0 + Max: 100 + Effect: If the circuit success rate falls below this percentage, + we emit a warn log message. + + pb_extremepct + Default: 30 + Min: 0 + Max: 100 + Effect: If the circuit success rate falls below this percentage, + we emit a more alarmist warning log message. If + pb_dropguard is set to 1, we also disable the use of the + guard. + + pb_dropguards + Default: 0 + Min: 0 + Max: 1 + Effect: If the circuit success rate falls below pb_extremepct, + when pb_dropguard is set to 1, we disable use of that + guard. + + pb_scalecircs + Default: 300 + Min: 10 + Effect: After this many circuits have completed at least two hops, + Tor performs the scaling described in + ["Scaling success counts"](#scaling). + + pb_multfactor and pb_scalefactor + Default: 1/2 + Min: 0.0 + Max: 1.0 + Effect: The double-precision result obtained from + pb_multfactor/pb_scalefactor is multiplied by our current + counts to scale them. + + pb_minuse + Default: 20 + Min: 3 + Effect: This is the minimum number of circuits that we must attempt to + use before we begin evaluating construction rates. + + pb_noticeusepct + Default: 80 + Min: 3 + Effect: If the circuit usage success rate falls below this percentage, + we emit a notice log message. + + pb_extremeusepct + Default: 60 + Min: 3 + Effect: If the circuit usage success rate falls below this percentage, + we emit a warning log message. We also disable the use of the + guard if pb_dropguards is set. + + pb_scaleuse + Default: 100 + Min: 10 + Effect: After we have attempted to use this many circuits, + Tor performs the scaling described in + ["Scaling success counts"](#scaling). +``` + +<a id="path-spec.txt-7.5"></a> + +## Known barriers to enforcement {#barriers} + +Due to intermittent CPU overload at relays, the normal rate of +successful circuit completion is highly variable. The Guard-dropping +version of the defense is unlikely to be deployed until the ntor +circuit handshake is enabled, or the nature of CPU overload induced +failure is better understood. |