October 2012 - tor-commits - lists.torproject.org

[torspec/master] Merge remote-tracking branch 'mikeperry/consensus-bootstrap'
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit 5c00b2d335a4c6aa0b01dc51069a2010667ae545 Merge: 273e77c 94e5674 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Oct 11 10:35:46 2012 -0400 Merge remote-tracking branch 'mikeperry/consensus-bootstrap' .../xxx-faster-headless-consensus-bootstrap.txt | 112 ++++++++++++++++++++ 1 files changed, 112 insertions(+), 0 deletions(-)

1 0

[torspec/master] Merge remote-tracking branch 'mikeperry/mapaddress-check'
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit fd5b1fdf1b24ab89fb11dbd43ad13158023e68b1 Merge: 7dd4523 ea37bb4 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Oct 11 10:37:41 2012 -0400 Merge remote-tracking branch 'mikeperry/mapaddress-check' proposals/xxx-mapaddress-tor-status.txt | 144 +++++++++++++++++++++++++++++++ 1 files changed, 144 insertions(+), 0 deletions(-)

1 0

[torspec/master] faster headless consensus bootstrapping is now proposal 210
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit 7dd452336e4df3e4bcc66b40f7cbbd56416bd6a2 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Oct 11 10:36:31 2012 -0400 faster headless consensus bootstrapping is now proposal 210 --- proposals/000-index.txt | 2 + .../210-faster-headless-consensus-bootstrap.txt | 113 ++++++++++++++++++++ .../xxx-faster-headless-consensus-bootstrap.txt | 112 ------------------- 3 files changed, 115 insertions(+), 112 deletions(-) diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 2863d79..64aea49 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -131,6 +131,7 @@ Proposals by number: 208 IPv6 Exits Redux [OPEN] 209 Limit reported bandwidth of unmeasured nodes [OPEN] 209 Tuning the Parameters for the Path Bias Defense [OPEN] +210 Faster Headless Consensus Bootstrapping [OPEN] Proposals by status: @@ -178,6 +179,7 @@ Proposals by status: 208 IPv6 Exits Redux [for 0.2.4.x] 209 Limit reported bandwidth of unmeasured nodes [for 0.2.4.x] 209 Tuning the Parameters for the Path Bias Defense [for 0.2.4.x+] + 210 Faster Headless Consensus Bootstrapping [for 0.2.4.x+] ACCEPTED: 117 IPv6 exits [for 0.2.4.x] 140 Provide diffs between consensuses diff --git a/proposals/210-faster-headless-consensus-bootstrap.txt b/proposals/210-faster-headless-consensus-bootstrap.txt new file mode 100644 index 0000000..6b1502b --- /dev/null +++ b/proposals/210-faster-headless-consensus-bootstrap.txt @@ -0,0 +1,113 @@ +Filename: 210-faster-headless-consensus-bootstrap.txt +Title: Faster Headless Consensus Bootstrapping +Author: Mike Perry +Created: 01-10-2012 +Status: Open +Target: 0.2.4.x+ + + +Overview and Motiviation + + This proposal describes a way for clients to fetch the initial + consensus more quickly in situations where some or all of the directory + authorities are unreachable. This proposal is meant to describe a + solution for bug #4483. + +Design: Bootstrap Process Changes + + The core idea is to attempt to establish bootstrap connections in + parallel during the bootstrap process, and download the consensus from + the first connection that completes. + + Connection attempts will be done in batches of three. Only one + connection will be performed to one of the canonical directory + authorities. Two connections will be performed to randomly chosen hard + coded directory mirrors. + + If no connections complete within 5 seconds, another batch of three + connections will be launched. Otherwise, the first connection to + complete will be used to download the consensus document and the others + will be closed, after which bootstrapping will proceed as normal. + + If at any time, the total outstanding bootstrap connection attempts + exceeds 15, no new connection attempts are to be launched until existing + connection attempts experience full timeout. + +Design: Fallback Dir Mirror Selection + + The set of hard coded directory mirrors from #572 shall be chosen using + the 100 Guard nodes with the longest uptime. + + The fallback weights will be set using each mirror's fraction of + consensus bandwidth out of the total of all 100 mirrors. + + This list of fallback dir mirrors should be updated with every + major Tor release. In future releases, the number of dir mirrors + should be set at 20% of the current Guard nodes, rather than fixed at + 100. + +Performance: Additional Load with Current Parameter Choices + + This design and the connection count parameters were chosen such that + no additional bandwidth load would be placed on the directory + authorities. In fact, the directory authorities should experience less + load, because they will not need to serve the consensus document for a + connection in the event that one of the directory mirrors complete their + connection before the directory authority does. + + However, the scheme does place additional TLS connection load on the + fallback dir mirrors. Because bootstrapping is rare and all but one of + the TLS connections will be very short-lived and unused, this should not + be a substantial issue. + + The dangerous case is in the event of a prolonged consensus failure + that induces all clients to enter into the bootstrap process. In this + case, the number of initial TLS connections to the fallback dir mirrors + would be 2*C/100, or 10,000 for C=500,000 users. If no connections + complete before the five retries, this could reach as high as 50,000 + connection attempts, but this is extremely unlikely to happen in full + aggregate. + + However, in the no-consensus scenario today, the directory authorities + would already experience C/9 or 55,555 connection attempts. The + 5-retry scheme increases their total maximum load to about 275,000 + connection attempts, but again this is unlikely to be reached + in aggregate. Additionally, with this scheme, even if the dirauths + are taken down by this load, the dir mirrors should be able to survive + it. + +Implementation Notes: Code Modifications + + The implementation of the bootstrap process is unfortunately mixed + in with many types of directory activity. + + The process starts in update_consensus_networkstatus_downloads(), + which initiates a single directory connection through + directory_get_from_dirserver(). Depending on bootstrap state, + a single directory server is selected and a connection is + eventually made through directory_initiate_command_rend(). + + There appear to be a few options for altering this code to perform + multiple connections. Without refactoring, one approach would be + to make multiple calls to directory_initiate_command_routerstatus() + from directory_get_from_dirserver() if the purpose is + DIR_PURPOSE_FETCH_CONSENSUS and the only directory servers available + are the authorities and the fallback dir mirrors. + + The code in directory_initiate_command_rend() would then need to be + altered to maintain a list of the dircons created for this purpose as + well as avoid immediately queuing the directory_send_command() request + for the DIR_PURPOSE_FETCH_CONSENSUS purpose. A flag would need to be set + on the dircon to be checked in connection_dir_finished_connecting(). + + The function connection_dir_finished_connecting() would need to be + altered to examine the list of pending dircons, determine if this one is + the first to complete, and if so, then call directory_send_command() to + download the consensus and close the other pending dircons. + + An additional timer would need to be installed to re-call + update_consensus_networkstatus_downloads() or a related helper after 5 + seconds. connection_dir_finished_connecting() would cancel this timer. + The helper would check the list of pending connections and ensure it + never exceeds 15. + diff --git a/proposals/xxx-faster-headless-consensus-bootstrap.txt b/proposals/xxx-faster-headless-consensus-bootstrap.txt deleted file mode 100644 index 8f5b079..0000000 --- a/proposals/xxx-faster-headless-consensus-bootstrap.txt +++ /dev/null @@ -1,112 +0,0 @@ -Title: Faster Headless Consensus Bootstrapping -Author: Mike Perry -Created: 01-10-2012 -Status: Open -Target: 0.2.4.x+ - - -Overview and Motiviation - - This proposal describes a way for clients to fetch the initial - consensus more quickly in situations where some or all of the directory - authorities are unreachable. This proposal is meant to describe a - solution for bug #4483. - -Design: Bootstrap Process Changes - - The core idea is to attempt to establish bootstrap connections in - parallel during the bootstrap process, and download the consensus from - the first connection that completes. - - Connection attempts will be done in batches of three. Only one - connection will be performed to one of the canonical directory - authorities. Two connections will be performed to randomly chosen hard - coded directory mirrors. - - If no connections complete within 5 seconds, another batch of three - connections will be launched. Otherwise, the first connection to - complete will be used to download the consensus document and the others - will be closed, after which bootstrapping will proceed as normal. - - If at any time, the total outstanding bootstrap connection attempts - exceeds 15, no new connection attempts are to be launched until existing - connection attempts experience full timeout. - -Design: Fallback Dir Mirror Selection - - The set of hard coded directory mirrors from #572 shall be chosen using - the 100 Guard nodes with the longest uptime. - - The fallback weights will be set using each mirror's fraction of - consensus bandwidth out of the total of all 100 mirrors. - - This list of fallback dir mirrors should be updated with every - major Tor release. In future releases, the number of dir mirrors - should be set at 20% of the current Guard nodes, rather than fixed at - 100. - -Performance: Additional Load with Current Parameter Choices - - This design and the connection count parameters were chosen such that - no additional bandwidth load would be placed on the directory - authorities. In fact, the directory authorities should experience less - load, because they will not need to serve the consensus document for a - connection in the event that one of the directory mirrors complete their - connection before the directory authority does. - - However, the scheme does place additional TLS connection load on the - fallback dir mirrors. Because bootstrapping is rare and all but one of - the TLS connections will be very short-lived and unused, this should not - be a substantial issue. - - The dangerous case is in the event of a prolonged consensus failure - that induces all clients to enter into the bootstrap process. In this - case, the number of initial TLS connections to the fallback dir mirrors - would be 2*C/100, or 10,000 for C=500,000 users. If no connections - complete before the five retries, this could reach as high as 50,000 - connection attempts, but this is extremely unlikely to happen in full - aggregate. - - However, in the no-consensus scenario today, the directory authorities - would already experience C/9 or 55,555 connection attempts. The - 5-retry scheme increases their total maximum load to about 275,000 - connection attempts, but again this is unlikely to be reached - in aggregate. Additionally, with this scheme, even if the dirauths - are taken down by this load, the dir mirrors should be able to survive - it. - -Implementation Notes: Code Modifications - - The implementation of the bootstrap process is unfortunately mixed - in with many types of directory activity. - - The process starts in update_consensus_networkstatus_downloads(), - which initiates a single directory connection through - directory_get_from_dirserver(). Depending on bootstrap state, - a single directory server is selected and a connection is - eventually made through directory_initiate_command_rend(). - - There appear to be a few options for altering this code to perform - multiple connections. Without refactoring, one approach would be - to make multiple calls to directory_initiate_command_routerstatus() - from directory_get_from_dirserver() if the purpose is - DIR_PURPOSE_FETCH_CONSENSUS and the only directory servers available - are the authorities and the fallback dir mirrors. - - The code in directory_initiate_command_rend() would then need to be - altered to maintain a list of the dircons created for this purpose as - well as avoid immediately queuing the directory_send_command() request - for the DIR_PURPOSE_FETCH_CONSENSUS purpose. A flag would need to be set - on the dircon to be checked in connection_dir_finished_connecting(). - - The function connection_dir_finished_connecting() would need to be - altered to examine the list of pending dircons, determine if this one is - the first to complete, and if so, then call directory_send_command() to - download the consensus and close the other pending dircons. - - An additional timer would need to be installed to re-call - update_consensus_networkstatus_downloads() or a related helper after 5 - seconds. connection_dir_finished_connecting() would cancel this timer. - The helper would check the list of pending connections and ensure it - never exceeds 15. -

1 0

[torspec/master] Add mapaddress-tor-status as proposal 211
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit 15904a880af765b3febfc80d91440ac29b6d0e9e Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Oct 11 10:38:28 2012 -0400 Add mapaddress-tor-status as proposal 211 --- proposals/000-index.txt | 2 + proposals/211-mapaddress-tor-status.txt | 145 +++++++++++++++++++++++++++++++ proposals/xxx-mapaddress-tor-status.txt | 144 ------------------------------ 3 files changed, 147 insertions(+), 144 deletions(-) diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 64aea49..2fa2be6 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -132,6 +132,7 @@ Proposals by number: 209 Limit reported bandwidth of unmeasured nodes [OPEN] 209 Tuning the Parameters for the Path Bias Defense [OPEN] 210 Faster Headless Consensus Bootstrapping [OPEN] +211 Internal Mapaddress for Tor Configuration Testing [OPEN] Proposals by status: @@ -180,6 +181,7 @@ Proposals by status: 209 Limit reported bandwidth of unmeasured nodes [for 0.2.4.x] 209 Tuning the Parameters for the Path Bias Defense [for 0.2.4.x+] 210 Faster Headless Consensus Bootstrapping [for 0.2.4.x+] + 211 Internal Mapaddress for Tor Configuration Testing [for 0.2.4.x+] ACCEPTED: 117 IPv6 exits [for 0.2.4.x] 140 Provide diffs between consensuses diff --git a/proposals/211-mapaddress-tor-status.txt b/proposals/211-mapaddress-tor-status.txt new file mode 100644 index 0000000..7cac4b7 --- /dev/null +++ b/proposals/211-mapaddress-tor-status.txt @@ -0,0 +1,145 @@ +Filename: 211-mapaddress-tor-status.txt +Title: Internal Mapaddress for Tor Configuration Testing +Author: Mike Perry +Created: 08-10-2012 +Status: Open +Target: 0.2.4.x+ + + +Overview + + This proposal describes a method by which we can replace the + https://check.torproject.org/ testing service with an internal XML + document provided by the Tor client. + +Motivation + + The Tor Check service is a central point of failure in terms of Tor + usability. If it is ever out of sync with the set of exit nodes on the + Tor network or down, user experience is degraded considerably. Moreover, + the check itself is very time-consuming. Users must wait seconds or more + for the result to come back. Worse still, if the user's software *was* + in fact misconfigured, the check.torproject.org DNS resolution and + request leaks out on to the network. + +Design Overview + + The system will have three parts: an internal hard-coded IP address + mapping (127.84.111.114:80), a hard-coded mapaddress to a DNS name + (selftest.torproject.org:80), and a DirPortFrontPage-style simple + HTTP server that serves an XML document for both addresses. + + Upon receipt of a request to the IP address mapping, the system will + create a new 128 bit randomly generated nonce and provide it + in the XML document. + + Requests to http://selftest.torproject.org/ must include a valid, + recent nonce as the GET url path. Upon receipt of a valid nonce, + it is removed from the list of valid nonces. Nonces are only valid + for 60 seconds or until SIGNAL NEWNYM, which ever comes first. + + The list of pending nonces should not be allowed to grow beyond 10 + entries. + + The timeout period and nonce limit should be configurable in torrc. + +Design: XML document format for http://127.84.111.114 + + To avoid the need to localize the message in Tor, Tor will only provide + a XML object with connectivity information. Here is an example form: + + <tor-test> + <tor-bootstrap-percent>100</tor-bootstrap-percent> + <tor-version-current>true</tor-version-current> + <dns-nonce>4977eb4842c7c59fa5b830ac4da896d9</dns-nonce> + <tor-test/> + + The tor-bootstrap-percent field represents the results of the Tor client + bootstrap status as integer percentages from bootstrap_status_t. + + The tor-version-current field represents the results of the Tor client + consensus version check. If the bootstrap process has not yet + downloaded a consensus document, this field will have the value + null. + + The dns-nonce field contains a 128-bit secret, encoded in base16. This + field is only present for requests that list the Host: header as + 127.84.111.114. + +Design: XML document format for http://selftest.torproject.org/nonce + + <tor-test> + <tor-bootstrap-percent>100</tor-bootstrap-percent> + <tor-version-current>true</tor-version-current> + <dns-nonce-valid>true</dns-nonce-valid> + <tor-test/> + + The first two fields are the same as for the IP address version. + + The dns-nonce-valid field is only true if the Host header matches + selftest.torproject.org and the nonce is current and valid. Upon + receipt of a valid nonce, that nonce is removed from the list of + valid nonces. + +Design: Request Servicing + + Care must be taken with the dns-nonce generation and usage, to prevent + users from being tracked through leakage of nonce value to application + content. While the usage of XML appears to make this impossible + due to stricter same-origin policy enforcement than JSON, same-origin + enforcement is still fraught with exceptions and loopholes. + + In particular: + + Any requests that contain the Origin: header MUST be ignored, + as the Origin: header is only included for third party web content + (CORS). + + dns-nonce fields MUST be omitted if the HTTP Host: header does not + match the IP address 127.84.111.114. + + Requests to selftest.torproject.org MUST return false for the + dns-nonce-valid field if the HTTP Host: header does not match + selftest.torproject.org, regardless of nonce value. + + Further, requests to selftest.torproject.org MUST validate that + 'selftest.torproject.org' was the actual hostname provided to + SOCKS4A, and not some alternate address mapping (due to DNS rebinding + attacks, for example). + +Design: Application Usage + + Applications will use the system in two steps. First, they will make an + HTTP request to http://127.84.111.114:80/ over Tor's SOCKS port and + parse the resulting XML, if any. + + If the request at this stage fails, the application should inform the + user that either their Tor client is too old, or that it is + misconfigured, depending upon the nature of the failure. + + If the request succeeds and valid XML is returned, the application + will record the value of the dns-nonce field, and then perform a second + request to http://selftest.torproject.org/nonce_value. If the second + request succeeds, and the dns-nonce-valid field is true, the application + may inform the user that their Tor settings are valid. + + If the second request fails, or does not provide the correct dns-nonce, + the application will inform the user that their Tor DNS proxy settings + are incorrect. + + If either tor-bootstrap-percent is not 100, or tor-version-current is + false, applications may choose to inform the user of these facts using + properly localized strings and appropriate UI. + +Security Considerations + + XML was chosen over JSON due to the risks of the identifier leaking + in a way that could enable websites to track the user[1]. + + Because there are many exceptions and circumvention techniques + to the same-origin policy, we have also opted for strict controls + on dns-nonce lifetimes and usage, as well as validation of the Host + header and SOCKS4A request hostnames. + + +1. http://www.hpenterprisesecurity.com/vulncat/en/vulncat/dotnet/javascript_hi… diff --git a/proposals/xxx-mapaddress-tor-status.txt b/proposals/xxx-mapaddress-tor-status.txt deleted file mode 100644 index 8475bd0..0000000 --- a/proposals/xxx-mapaddress-tor-status.txt +++ /dev/null @@ -1,144 +0,0 @@ -Title: Internal Mapaddress for Tor Configuration Testing -Author: Mike Perry -Created: 08-10-2012 -Status: Open -Target: 0.2.4.x+ - - -Overview - - This proposal describes a method by which we can replace the - https://check.torproject.org/ testing service with an internal XML - document provided by the Tor client. - -Motivation - - The Tor Check service is a central point of failure in terms of Tor - usability. If it is ever out of sync with the set of exit nodes on the - Tor network or down, user experience is degraded considerably. Moreover, - the check itself is very time-consuming. Users must wait seconds or more - for the result to come back. Worse still, if the user's software *was* - in fact misconfigured, the check.torproject.org DNS resolution and - request leaks out on to the network. - -Design Overview - - The system will have three parts: an internal hard-coded IP address - mapping (127.84.111.114:80), a hard-coded mapaddress to a DNS name - (selftest.torproject.org:80), and a DirPortFrontPage-style simple - HTTP server that serves an XML document for both addresses. - - Upon receipt of a request to the IP address mapping, the system will - create a new 128 bit randomly generated nonce and provide it - in the XML document. - - Requests to http://selftest.torproject.org/ must include a valid, - recent nonce as the GET url path. Upon receipt of a valid nonce, - it is removed from the list of valid nonces. Nonces are only valid - for 60 seconds or until SIGNAL NEWNYM, which ever comes first. - - The list of pending nonces should not be allowed to grow beyond 10 - entries. - - The timeout period and nonce limit should be configurable in torrc. - -Design: XML document format for http://127.84.111.114 - - To avoid the need to localize the message in Tor, Tor will only provide - a XML object with connectivity information. Here is an example form: - - <tor-test> - <tor-bootstrap-percent>100</tor-bootstrap-percent> - <tor-version-current>true</tor-version-current> - <dns-nonce>4977eb4842c7c59fa5b830ac4da896d9</dns-nonce> - <tor-test/> - - The tor-bootstrap-percent field represents the results of the Tor client - bootstrap status as integer percentages from bootstrap_status_t. - - The tor-version-current field represents the results of the Tor client - consensus version check. If the bootstrap process has not yet - downloaded a consensus document, this field will have the value - null. - - The dns-nonce field contains a 128-bit secret, encoded in base16. This - field is only present for requests that list the Host: header as - 127.84.111.114. - -Design: XML document format for http://selftest.torproject.org/nonce - - <tor-test> - <tor-bootstrap-percent>100</tor-bootstrap-percent> - <tor-version-current>true</tor-version-current> - <dns-nonce-valid>true</dns-nonce-valid> - <tor-test/> - - The first two fields are the same as for the IP address version. - - The dns-nonce-valid field is only true if the Host header matches - selftest.torproject.org and the nonce is current and valid. Upon - receipt of a valid nonce, that nonce is removed from the list of - valid nonces. - -Design: Request Servicing - - Care must be taken with the dns-nonce generation and usage, to prevent - users from being tracked through leakage of nonce value to application - content. While the usage of XML appears to make this impossible - due to stricter same-origin policy enforcement than JSON, same-origin - enforcement is still fraught with exceptions and loopholes. - - In particular: - - Any requests that contain the Origin: header MUST be ignored, - as the Origin: header is only included for third party web content - (CORS). - - dns-nonce fields MUST be omitted if the HTTP Host: header does not - match the IP address 127.84.111.114. - - Requests to selftest.torproject.org MUST return false for the - dns-nonce-valid field if the HTTP Host: header does not match - selftest.torproject.org, regardless of nonce value. - - Further, requests to selftest.torproject.org MUST validate that - 'selftest.torproject.org' was the actual hostname provided to - SOCKS4A, and not some alternate address mapping (due to DNS rebinding - attacks, for example). - -Design: Application Usage - - Applications will use the system in two steps. First, they will make an - HTTP request to http://127.84.111.114:80/ over Tor's SOCKS port and - parse the resulting XML, if any. - - If the request at this stage fails, the application should inform the - user that either their Tor client is too old, or that it is - misconfigured, depending upon the nature of the failure. - - If the request succeeds and valid XML is returned, the application - will record the value of the dns-nonce field, and then perform a second - request to http://selftest.torproject.org/nonce_value. If the second - request succeeds, and the dns-nonce-valid field is true, the application - may inform the user that their Tor settings are valid. - - If the second request fails, or does not provide the correct dns-nonce, - the application will inform the user that their Tor DNS proxy settings - are incorrect. - - If either tor-bootstrap-percent is not 100, or tor-version-current is - false, applications may choose to inform the user of these facts using - properly localized strings and appropriate UI. - -Security Considerations - - XML was chosen over JSON due to the risks of the identifier leaking - in a way that could enable websites to track the user[1]. - - Because there are many exceptions and circumvention techniques - to the same-origin policy, we have also opted for strict controls - on dns-nonce lifetimes and usage, as well as validation of the Host - header and SOCKS4A request hostnames. - - -1. http://www.hpenterprisesecurity.com/vulncat/en/vulncat/dotnet/javascript_hi…

1 0

[torspec/master] Add path bias tuning proposal.
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit 9b2886f674c5ed835962b6788f0272e38cc33977 Author: Mike Perry <mikeperry-git(a)fscked.org> Date: Wed Oct 10 16:51:45 2012 -0700 Add path bias tuning proposal. --- proposals/xxx-path-bias-tuning.txt | 196 ++++++++++++++++++++++++++++++++++++ 1 files changed, 196 insertions(+), 0 deletions(-) diff --git a/proposals/xxx-path-bias-tuning.txt b/proposals/xxx-path-bias-tuning.txt new file mode 100644 index 0000000..b6cf165 --- /dev/null +++ b/proposals/xxx-path-bias-tuning.txt @@ -0,0 +1,196 @@ +Title: Tuning the Parameters for the Path Bias Defense +Author: Mike Perry +Created: 01-10-2012 +Status: Open +Target: 0.2.4.x+ + + +Overview + + This proposal describes how we can use the results of network scans to + set reasonable limits for the Path Bias defense, which causes clients to + be informed about and ideally rotate away from Guards that provide + extremely low circuit success rates. + +Motivation + + The Path Bias defense is designed to defend against a type of route + capture where malicious Guard nodes deliberately fail circuits that + are determined to extend to non-colluding Exit nodes to maximize + their network utilization in favor of carrying only compromised + traffic. + + This attack was explored in the academic literature in [1], and a + variant involving cryptographic tagging was posted to tor-dev[2] in + March. + + 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. + +Design Description + + The Path Bias defense is a client-side accounting mechanism in Tor that + tracks the circuit failure rate for each of the client's guards. + + Clients maintain two integers for each of their guards: a count of the + number of times a circuit was extended at least one hop 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. + + The system should issue a notice log message when Guard success rate + falls below 70%, a warn when Guard success rate falls below 50%, and + should drop the Guard when the success rate falls below 30%. + + To ensure correctness, checks are performed to ensure that + we do not count successes without also counting the first hop. + + Similarly, to provide a moving average of recent Guard activity while + still preserving the ability to ensure correctness, we "scale" the + success counts by an integer divisor (currently 2) when the counts + exceed the moving average window (300) and when the division + does not produce integer truncation. + + No log messages should be displayed, nor should any Guard be + dropped until it has completed more than 150 first hops. + +Analysis: Simulation + + To test the defense in the face of various types of malicious and + non-malicious Guard behavior, I wrote a simulation program in + Python[3]. + + The simulation confirmed that without any defense, an adversary + that provides c/n of the network capacity is able to observe c/n + of the network flows using circuit failure attacks. + + It also showed that with the defense, an adversary that wishes to + evade detection has compromise rates bounded by: + + P(compromise) <= (c/n)^2 * (100/CUTOFF_PERCENT) + circs_per_client <= circuit_attempts*(c/n) + + In this way, the defense restores the O((c/n)^2) compromise property, + but unfortunately only over long periods of time (see Security + Considerations below). + + The spread between the cutoff values and the normal rate of circuit + success has a substantial effect on false positives. From the + simulation's results, the sweet spot for the size of this spread appears + to be 10%. In other words, we want to set the cutoffs such that they are + 10% below the success rate we expect to see in normal usage. + + The simulation also demonstrates that larger "scaling window" sizes + reduce false positives for instances where non-malicious guards + experience some ambient rate of circuit failure. + +Analysis: Live Scan + + Preliminary Guard node scanning using the txtorcon circuit scanner[4] + shows normal circuit completion rates between 80-90% for most Guard + nodes. + + However, it also showed that CPU overload conditions can easily push + success rates as low as 45%. Even more concerning is that for a brief + period during the live scan, success rates dropped to 50-60% + network-wide (regardless of Guard node choice). + + Based on these results, the notice condition should be 70%, the warn + condition should be 50%, and the drop condition should be 30%. + +Future Analysis: Deployed Clients + + It's my belief that further analysis should be done by deploying + loglines for all three thresholds in clients in the live network + and utilize user reports on how often high rates of circuit failure + are seen before we deploy changes to rotate away from failing Guards. + + I believe these log lines should be deployed in 0.2.3.x clients, + to maximize the exposure of the code to varying network conditions, + so that we have enough data to consider deploying the Guard-dropping + cutoff in 0.2.4.x. + +Security Considerations + + Circuit failure can occur for many reasons. The most common of which is + CPU resource exhaustion at high speed relays. + + While the scaling window does provide freshness, it also creates the + possibility of conditions where clients can be forced off their Guards + due to temporary network-wide or Guard-specific CPU DoS. This provides + another reason beyond false positive concerns to set the window as + large is reasonable. + + In my mind, the value to aim for here is a number of circuits large + enough to put this attack vector on par with the timescales used by + the bandwidth authorities to redirect client activity away from + loaded (ie DoSed) nodes. + + Simulation results show that a Guard node that previously + succeeded 80% of its circuits would need to be DoSed down to + 5% success rate for around 230 circuit attempts before the client + would reject it, using a scaling window of 300 circuits. + + Assuming one circuit per Guard per 10 minutes of normal client + activity, this is a sustained DoS attack of around 38 hours, + which is on the order of the bandwidth authority measurement + interval (nodes are measured every 1-2 days). + + The converse of this, though, is that larger values allow + Guard nodes to compromise clients for duty cycles of around the + size of this window (up to the (c/n)^2 * 100/CUTOFF_PERCENT + limit in aggregate), so we do have to consider that trade off. + +Implementation Notes: Log Messages + + Log messages need to be chosen with care to avoid alarming users. + I suggest: + + Notice: "It appears that your Guard %s is failing a larger number of + circuits than usual. This could mean that the Guard is overloaded, or + the Tor network is overloaded. Success counts are %d/%d." + + Warn: "It appears that your Guard %s is failing a very large number of + circuits. Most likely, this could mean that the Guard is overloaded, + or the Tor network is overloaded, but it could also mean an attack + against you or the Guard. Success counts are %d/%d." + + Drop: "It appears that your Guard %s is failing an extremely large + number of circuits. [Tor has disabled use of this Guard.] Success + counts are %d/%d." + + The second piece of the Drop message would not be present in 0.2.3.x, + since the Guard won't actually be dropped. + +Implementation Notes: Consensus Parameters + + The following consensus parameters reflect the constants listed + in the proposal. These parameters should also be available + for override in torrc. + + pb_mincircs=150 + The minimum number of first hops before we log or drop Guards. + + pb_noticepct=70 + The threshhold of circuit success below which we display a notice. + + pb_warnpct=50 + The threshhold of circuit success below which we display a warn. + + pb_disablepct=30 + The threshhold of circuit success below which we disable the guard. + + pb_scalecircs=300 + The number of first hops at which we scale the counts down. + + pb_scalefactor=2 + The integer divisor by which we scale. + + + +1. http://freehaven.net/anonbib/cache/ccs07-doa.pdf +2. https://lists.torproject.org/pipermail/tor-dev/2012-March/003347.html +3. https://gitweb.torproject.org/torflow.git/tree/HEAD:/CircuitAnalysis/PathBi… +4. https://github.com/meejah/txtorcon/blob/exit_scanner/apps/exit_scanner/fail…

1 0

[torspec/master] Rework security section.
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit a535071f141cefcf4a6de73b2ba5a4f8326e91ff Author: Mike Perry <mikeperry-git(a)fscked.org> Date: Wed Oct 10 20:44:55 2012 -0700 Rework security section. It seems it's actually not possible to target specific guard nodes for DoS with this scheme. --- proposals/xxx-path-bias-tuning.txt | 59 +++++++++++++++++++----------------- 1 files changed, 31 insertions(+), 28 deletions(-) diff --git a/proposals/xxx-path-bias-tuning.txt b/proposals/xxx-path-bias-tuning.txt index b6cf165..cd4a459 100644 --- a/proposals/xxx-path-bias-tuning.txt +++ b/proposals/xxx-path-bias-tuning.txt @@ -7,10 +7,11 @@ Target: 0.2.4.x+ Overview - This proposal describes how we can use the results of network scans to - set reasonable limits for the Path Bias defense, which causes clients to - be informed about and ideally rotate away from Guards that provide - extremely low circuit success rates. + This proposal describes how we can use the results of simulations in + combination with network scans to set reasonable limits for the Path + Bias defense, which causes clients to be informed about and ideally + rotate away from Guards that provide extremely low circuit success + rates. Motivation @@ -114,34 +115,36 @@ Future Analysis: Deployed Clients Security Considerations - Circuit failure can occur for many reasons. The most common of which is - CPU resource exhaustion at high speed relays. + While the scaling window does provide freshness and can help mitigate + "bait-and-switch" attacks, it also creates the possibility of conditions + where clients can be forced off their Guards due to temporary + network-wide CPU DoS. This provides another reason beyond false positive + concerns to set the scaling window as large as is reasonable. - While the scaling window does provide freshness, it also creates the - possibility of conditions where clients can be forced off their Guards - due to temporary network-wide or Guard-specific CPU DoS. This provides - another reason beyond false positive concerns to set the window as - large is reasonable. + A DoS directed at specific Guard nodes is unlikely to allow an + adversary to cause clients to rotate away from that Guard, because it + is unlikely that the DoS can be precise enough to allow first hops to + that Guard to succeed, but also cause extends to fail. This leaves + network-wide DoS as the primary vector for influencing clients. - In my mind, the value to aim for here is a number of circuits large - enough to put this attack vector on par with the timescales used by - the bandwidth authorities to redirect client activity away from - loaded (ie DoSed) nodes. - - Simulation results show that a Guard node that previously - succeeded 80% of its circuits would need to be DoSed down to - 5% success rate for around 230 circuit attempts before the client - would reject it, using a scaling window of 300 circuits. + Simulation results show that in order to cause clients to rotate away + from a Guard node that previously succeeded 80% of its circuits, an + adversary would need to induce a 25% success rate for around 350 circuit + attempts before the client would reject it or a 5% success rate + for around 215 attempts, using a scaling window of 300 circuits. Assuming one circuit per Guard per 10 minutes of normal client - activity, this is a sustained DoS attack of around 38 hours, - which is on the order of the bandwidth authority measurement - interval (nodes are measured every 1-2 days). - - The converse of this, though, is that larger values allow - Guard nodes to compromise clients for duty cycles of around the - size of this window (up to the (c/n)^2 * 100/CUTOFF_PERCENT - limit in aggregate), so we do have to consider that trade off. + activity, this is a sustained network-wide DoS attack of 60 hours + for the 25% case, or 38 hours for the 5% case. + + Presumably this is enough time for the directory authorites to respond + by altering the pb_disablepct consensus parameter before clients + rotate. + + The converse of this, though, is that larger values allow Guard nodes + to compromise clients for duty cycles of around the size of this window + (up to the (c/n)^2 * 100/CUTOFF_PERCENT limit in aggregate), so we do + have to consider that trade off. Implementation Notes: Log Messages

1 0

[torspec/master] Clean up verbage.
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit ddf945fd9136f062ab82c4fc76eb013e05da0b52 Author: Mike Perry <mikeperry-git(a)fscked.org> Date: Thu Oct 11 01:59:59 2012 -0700 Clean up verbage. --- proposals/xxx-path-bias-tuning.txt | 61 ++++++++++++++++++----------------- 1 files changed, 31 insertions(+), 30 deletions(-) diff --git a/proposals/xxx-path-bias-tuning.txt b/proposals/xxx-path-bias-tuning.txt index cd4a459..964aedb 100644 --- a/proposals/xxx-path-bias-tuning.txt +++ b/proposals/xxx-path-bias-tuning.txt @@ -15,11 +15,10 @@ Overview Motivation - The Path Bias defense is designed to defend against a type of route - capture where malicious Guard nodes deliberately fail circuits that - are determined to extend to non-colluding Exit nodes to maximize - their network utilization in favor of carrying only compromised - traffic. + The Path Bias defense is designed to defend against a type of route capture + where malicious Guard nodes deliberately fail circuits that extend to + non-colluding Exit nodes to maximize their network utilization in favor of + carrying only compromised traffic. This attack was explored in the academic literature in [1], and a variant involving cryptographic tagging was posted to tor-dev[2] in @@ -55,7 +54,7 @@ Design Description does not produce integer truncation. No log messages should be displayed, nor should any Guard be - dropped until it has completed more than 150 first hops. + dropped until it has completed at least 150 first hops (inclusive). Analysis: Simulation @@ -105,7 +104,7 @@ Future Analysis: Deployed Clients It's my belief that further analysis should be done by deploying loglines for all three thresholds in clients in the live network - and utilize user reports on how often high rates of circuit failure + to utilize user reports on how often high rates of circuit failure are seen before we deploy changes to rotate away from failing Guards. I believe these log lines should be deployed in 0.2.3.x clients, @@ -131,38 +130,40 @@ Security Considerations from a Guard node that previously succeeded 80% of its circuits, an adversary would need to induce a 25% success rate for around 350 circuit attempts before the client would reject it or a 5% success rate - for around 215 attempts, using a scaling window of 300 circuits. - - Assuming one circuit per Guard per 10 minutes of normal client + for around 215 attempts, both using a scaling window of 300 circuits. + + Assuming one circuit per Guard per 10 minutes of active client activity, this is a sustained network-wide DoS attack of 60 hours for the 25% case, or 38 hours for the 5% case. - Presumably this is enough time for the directory authorites to respond - by altering the pb_disablepct consensus parameter before clients - rotate. + Presumably this is enough time for the directory authorities to respond by + altering the pb_disablepct consensus parameter before clients rotate, + especially given that most clients are not active for even 38 hours on end, + and will tend to stop building circuits while idle. + + If we raised the scaling window to 500 circuits, it would require 1050 + circuits if the DoS brought circuit success down to 25% (175 hours), and + 415 circuits if the DoS brought the circuit success down to 5% (69 hours). - The converse of this, though, is that larger values allow Guard nodes - to compromise clients for duty cycles of around the size of this window - (up to the (c/n)^2 * 100/CUTOFF_PERCENT limit in aggregate), so we do - have to consider that trade off. + The tradeoff, though, is that larger scaling window values allow Guard nodes + to compromise clients for duty cycles of around the size of this window (up to + the (c/n)^2 * 100/CUTOFF_PERCENT limit in aggregate), so we do have to find + balance between these concerns. Implementation Notes: Log Messages Log messages need to be chosen with care to avoid alarming users. I suggest: - Notice: "It appears that your Guard %s is failing a larger number of - circuits than usual. This could mean that the Guard is overloaded, or - the Tor network is overloaded. Success counts are %d/%d." + Notice: "Your Guard %s is failing more circuits than usual. Most likely + this means the Tor network is overloaded. Success counts are %d/%d." - Warn: "It appears that your Guard %s is failing a very large number of - circuits. Most likely, this could mean that the Guard is overloaded, - or the Tor network is overloaded, but it could also mean an attack - against you or the Guard. Success counts are %d/%d." + Warn: "Your Guard %s is failing a very large amount of circuits. Most likely + this means the Tor network is overloaded, but it could also mean an attack + against you or potentially the Guard itself. Success counts are %d/%d." - Drop: "It appears that your Guard %s is failing an extremely large - number of circuits. [Tor has disabled use of this Guard.] Success - counts are %d/%d." + Drop: "Your Guard %s is failing an extremely large amount of circuits. [Tor + has disabled use of this Guard.] Success counts are %d/%d." The second piece of the Drop message would not be present in 0.2.3.x, since the Guard won't actually be dropped. @@ -177,13 +178,13 @@ Implementation Notes: Consensus Parameters The minimum number of first hops before we log or drop Guards. pb_noticepct=70 - The threshhold of circuit success below which we display a notice. + The threshold of circuit success below which we display a notice. pb_warnpct=50 - The threshhold of circuit success below which we display a warn. + The threshold of circuit success below which we display a warn. pb_disablepct=30 - The threshhold of circuit success below which we disable the guard. + The threshold of circuit success below which we disable the guard. pb_scalecircs=300 The number of first hops at which we scale the counts down.

1 0

[torspec/master] Merge remote-tracking branch 'mikeperry/path-bias-tuning'
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit 70ce8f9198c57b3652de88f8884d8d3e38d0df17 Merge: c68d6fb ddf945f Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Oct 11 10:32:59 2012 -0400 Merge remote-tracking branch 'mikeperry/path-bias-tuning' proposals/xxx-path-bias-tuning.txt | 200 ++++++++++++++++++++++++++++++++++++ 1 files changed, 200 insertions(+), 0 deletions(-)

1 0

[torspec/master] Make "path bias tuning" into proposal 209.
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit 273e77c2afafcfa8efbafac5f24059497727ac74 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Oct 11 10:34:52 2012 -0400 Make "path bias tuning" into proposal 209. --- proposals/000-index.txt | 4 + proposals/209-path-bias-tuning.txt | 201 ++++++++++++++++++++++++++++++++++++ proposals/xxx-path-bias-tuning.txt | 200 ----------------------------------- 3 files changed, 205 insertions(+), 200 deletions(-) diff --git a/proposals/000-index.txt b/proposals/000-index.txt index e2cd9cf..2863d79 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -129,6 +129,8 @@ Proposals by number: 206 Preconfigured directory sources for bootstrapping [OPEN] 207 Directory guards [OPEN] 208 IPv6 Exits Redux [OPEN] +209 Limit reported bandwidth of unmeasured nodes [OPEN] +209 Tuning the Parameters for the Path Bias Defense [OPEN] Proposals by status: @@ -174,6 +176,8 @@ Proposals by status: 206 Preconfigured directory sources for bootstrapping [for 0.2.4.x] 207 Directory guards [for 0.2.4.x] 208 IPv6 Exits Redux [for 0.2.4.x] + 209 Limit reported bandwidth of unmeasured nodes [for 0.2.4.x] + 209 Tuning the Parameters for the Path Bias Defense [for 0.2.4.x+] ACCEPTED: 117 IPv6 exits [for 0.2.4.x] 140 Provide diffs between consensuses diff --git a/proposals/209-path-bias-tuning.txt b/proposals/209-path-bias-tuning.txt new file mode 100644 index 0000000..004729e --- /dev/null +++ b/proposals/209-path-bias-tuning.txt @@ -0,0 +1,201 @@ +Filename: 209-path-bias-tuning.txt +Title: Tuning the Parameters for the Path Bias Defense +Author: Mike Perry +Created: 01-10-2012 +Status: Open +Target: 0.2.4.x+ + + +Overview + + This proposal describes how we can use the results of simulations in + combination with network scans to set reasonable limits for the Path + Bias defense, which causes clients to be informed about and ideally + rotate away from Guards that provide extremely low circuit success + rates. + +Motivation + + The Path Bias defense is designed to defend against a type of route capture + where malicious Guard nodes deliberately fail circuits that extend to + non-colluding Exit nodes to maximize their network utilization in favor of + carrying only compromised traffic. + + This attack was explored in the academic literature in [1], and a + variant involving cryptographic tagging was posted to tor-dev[2] in + March. + + 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. + +Design Description + + The Path Bias defense is a client-side accounting mechanism in Tor that + tracks the circuit failure rate for each of the client's guards. + + Clients maintain two integers for each of their guards: a count of the + number of times a circuit was extended at least one hop 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. + + The system should issue a notice log message when Guard success rate + falls below 70%, a warn when Guard success rate falls below 50%, and + should drop the Guard when the success rate falls below 30%. + + To ensure correctness, checks are performed to ensure that + we do not count successes without also counting the first hop. + + Similarly, to provide a moving average of recent Guard activity while + still preserving the ability to ensure correctness, we "scale" the + success counts by an integer divisor (currently 2) when the counts + exceed the moving average window (300) and when the division + does not produce integer truncation. + + No log messages should be displayed, nor should any Guard be + dropped until it has completed at least 150 first hops (inclusive). + +Analysis: Simulation + + To test the defense in the face of various types of malicious and + non-malicious Guard behavior, I wrote a simulation program in + Python[3]. + + The simulation confirmed that without any defense, an adversary + that provides c/n of the network capacity is able to observe c/n + of the network flows using circuit failure attacks. + + It also showed that with the defense, an adversary that wishes to + evade detection has compromise rates bounded by: + + P(compromise) <= (c/n)^2 * (100/CUTOFF_PERCENT) + circs_per_client <= circuit_attempts*(c/n) + + In this way, the defense restores the O((c/n)^2) compromise property, + but unfortunately only over long periods of time (see Security + Considerations below). + + The spread between the cutoff values and the normal rate of circuit + success has a substantial effect on false positives. From the + simulation's results, the sweet spot for the size of this spread appears + to be 10%. In other words, we want to set the cutoffs such that they are + 10% below the success rate we expect to see in normal usage. + + The simulation also demonstrates that larger "scaling window" sizes + reduce false positives for instances where non-malicious guards + experience some ambient rate of circuit failure. + +Analysis: Live Scan + + Preliminary Guard node scanning using the txtorcon circuit scanner[4] + shows normal circuit completion rates between 80-90% for most Guard + nodes. + + However, it also showed that CPU overload conditions can easily push + success rates as low as 45%. Even more concerning is that for a brief + period during the live scan, success rates dropped to 50-60% + network-wide (regardless of Guard node choice). + + Based on these results, the notice condition should be 70%, the warn + condition should be 50%, and the drop condition should be 30%. + +Future Analysis: Deployed Clients + + It's my belief that further analysis should be done by deploying + loglines for all three thresholds in clients in the live network + to utilize user reports on how often high rates of circuit failure + are seen before we deploy changes to rotate away from failing Guards. + + I believe these log lines should be deployed in 0.2.3.x clients, + to maximize the exposure of the code to varying network conditions, + so that we have enough data to consider deploying the Guard-dropping + cutoff in 0.2.4.x. + +Security Considerations + + While the scaling window does provide freshness and can help mitigate + "bait-and-switch" attacks, it also creates the possibility of conditions + where clients can be forced off their Guards due to temporary + network-wide CPU DoS. This provides another reason beyond false positive + concerns to set the scaling window as large as is reasonable. + + A DoS directed at specific Guard nodes is unlikely to allow an + adversary to cause clients to rotate away from that Guard, because it + is unlikely that the DoS can be precise enough to allow first hops to + that Guard to succeed, but also cause extends to fail. This leaves + network-wide DoS as the primary vector for influencing clients. + + Simulation results show that in order to cause clients to rotate away + from a Guard node that previously succeeded 80% of its circuits, an + adversary would need to induce a 25% success rate for around 350 circuit + attempts before the client would reject it or a 5% success rate + for around 215 attempts, both using a scaling window of 300 circuits. + + Assuming one circuit per Guard per 10 minutes of active client + activity, this is a sustained network-wide DoS attack of 60 hours + for the 25% case, or 38 hours for the 5% case. + + Presumably this is enough time for the directory authorities to respond by + altering the pb_disablepct consensus parameter before clients rotate, + especially given that most clients are not active for even 38 hours on end, + and will tend to stop building circuits while idle. + + If we raised the scaling window to 500 circuits, it would require 1050 + circuits if the DoS brought circuit success down to 25% (175 hours), and + 415 circuits if the DoS brought the circuit success down to 5% (69 hours). + + The tradeoff, though, is that larger scaling window values allow Guard nodes + to compromise clients for duty cycles of around the size of this window (up to + the (c/n)^2 * 100/CUTOFF_PERCENT limit in aggregate), so we do have to find + balance between these concerns. + +Implementation Notes: Log Messages + + Log messages need to be chosen with care to avoid alarming users. + I suggest: + + Notice: "Your Guard %s is failing more circuits than usual. Most likely + this means the Tor network is overloaded. Success counts are %d/%d." + + Warn: "Your Guard %s is failing a very large amount of circuits. Most likely + this means the Tor network is overloaded, but it could also mean an attack + against you or potentially the Guard itself. Success counts are %d/%d." + + Drop: "Your Guard %s is failing an extremely large amount of circuits. [Tor + has disabled use of this Guard.] Success counts are %d/%d." + + The second piece of the Drop message would not be present in 0.2.3.x, + since the Guard won't actually be dropped. + +Implementation Notes: Consensus Parameters + + The following consensus parameters reflect the constants listed + in the proposal. These parameters should also be available + for override in torrc. + + pb_mincircs=150 + The minimum number of first hops before we log or drop Guards. + + pb_noticepct=70 + The threshold of circuit success below which we display a notice. + + pb_warnpct=50 + The threshold of circuit success below which we display a warn. + + pb_disablepct=30 + The threshold of circuit success below which we disable the guard. + + pb_scalecircs=300 + The number of first hops at which we scale the counts down. + + pb_scalefactor=2 + The integer divisor by which we scale. + + + +1. http://freehaven.net/anonbib/cache/ccs07-doa.pdf +2. https://lists.torproject.org/pipermail/tor-dev/2012-March/003347.html +3. https://gitweb.torproject.org/torflow.git/tree/HEAD:/CircuitAnalysis/PathBi… +4. https://github.com/meejah/txtorcon/blob/exit_scanner/apps/exit_scanner/fail… diff --git a/proposals/xxx-path-bias-tuning.txt b/proposals/xxx-path-bias-tuning.txt deleted file mode 100644 index 964aedb..0000000 --- a/proposals/xxx-path-bias-tuning.txt +++ /dev/null @@ -1,200 +0,0 @@ -Title: Tuning the Parameters for the Path Bias Defense -Author: Mike Perry -Created: 01-10-2012 -Status: Open -Target: 0.2.4.x+ - - -Overview - - This proposal describes how we can use the results of simulations in - combination with network scans to set reasonable limits for the Path - Bias defense, which causes clients to be informed about and ideally - rotate away from Guards that provide extremely low circuit success - rates. - -Motivation - - The Path Bias defense is designed to defend against a type of route capture - where malicious Guard nodes deliberately fail circuits that extend to - non-colluding Exit nodes to maximize their network utilization in favor of - carrying only compromised traffic. - - This attack was explored in the academic literature in [1], and a - variant involving cryptographic tagging was posted to tor-dev[2] in - March. - - 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. - -Design Description - - The Path Bias defense is a client-side accounting mechanism in Tor that - tracks the circuit failure rate for each of the client's guards. - - Clients maintain two integers for each of their guards: a count of the - number of times a circuit was extended at least one hop 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. - - The system should issue a notice log message when Guard success rate - falls below 70%, a warn when Guard success rate falls below 50%, and - should drop the Guard when the success rate falls below 30%. - - To ensure correctness, checks are performed to ensure that - we do not count successes without also counting the first hop. - - Similarly, to provide a moving average of recent Guard activity while - still preserving the ability to ensure correctness, we "scale" the - success counts by an integer divisor (currently 2) when the counts - exceed the moving average window (300) and when the division - does not produce integer truncation. - - No log messages should be displayed, nor should any Guard be - dropped until it has completed at least 150 first hops (inclusive). - -Analysis: Simulation - - To test the defense in the face of various types of malicious and - non-malicious Guard behavior, I wrote a simulation program in - Python[3]. - - The simulation confirmed that without any defense, an adversary - that provides c/n of the network capacity is able to observe c/n - of the network flows using circuit failure attacks. - - It also showed that with the defense, an adversary that wishes to - evade detection has compromise rates bounded by: - - P(compromise) <= (c/n)^2 * (100/CUTOFF_PERCENT) - circs_per_client <= circuit_attempts*(c/n) - - In this way, the defense restores the O((c/n)^2) compromise property, - but unfortunately only over long periods of time (see Security - Considerations below). - - The spread between the cutoff values and the normal rate of circuit - success has a substantial effect on false positives. From the - simulation's results, the sweet spot for the size of this spread appears - to be 10%. In other words, we want to set the cutoffs such that they are - 10% below the success rate we expect to see in normal usage. - - The simulation also demonstrates that larger "scaling window" sizes - reduce false positives for instances where non-malicious guards - experience some ambient rate of circuit failure. - -Analysis: Live Scan - - Preliminary Guard node scanning using the txtorcon circuit scanner[4] - shows normal circuit completion rates between 80-90% for most Guard - nodes. - - However, it also showed that CPU overload conditions can easily push - success rates as low as 45%. Even more concerning is that for a brief - period during the live scan, success rates dropped to 50-60% - network-wide (regardless of Guard node choice). - - Based on these results, the notice condition should be 70%, the warn - condition should be 50%, and the drop condition should be 30%. - -Future Analysis: Deployed Clients - - It's my belief that further analysis should be done by deploying - loglines for all three thresholds in clients in the live network - to utilize user reports on how often high rates of circuit failure - are seen before we deploy changes to rotate away from failing Guards. - - I believe these log lines should be deployed in 0.2.3.x clients, - to maximize the exposure of the code to varying network conditions, - so that we have enough data to consider deploying the Guard-dropping - cutoff in 0.2.4.x. - -Security Considerations - - While the scaling window does provide freshness and can help mitigate - "bait-and-switch" attacks, it also creates the possibility of conditions - where clients can be forced off their Guards due to temporary - network-wide CPU DoS. This provides another reason beyond false positive - concerns to set the scaling window as large as is reasonable. - - A DoS directed at specific Guard nodes is unlikely to allow an - adversary to cause clients to rotate away from that Guard, because it - is unlikely that the DoS can be precise enough to allow first hops to - that Guard to succeed, but also cause extends to fail. This leaves - network-wide DoS as the primary vector for influencing clients. - - Simulation results show that in order to cause clients to rotate away - from a Guard node that previously succeeded 80% of its circuits, an - adversary would need to induce a 25% success rate for around 350 circuit - attempts before the client would reject it or a 5% success rate - for around 215 attempts, both using a scaling window of 300 circuits. - - Assuming one circuit per Guard per 10 minutes of active client - activity, this is a sustained network-wide DoS attack of 60 hours - for the 25% case, or 38 hours for the 5% case. - - Presumably this is enough time for the directory authorities to respond by - altering the pb_disablepct consensus parameter before clients rotate, - especially given that most clients are not active for even 38 hours on end, - and will tend to stop building circuits while idle. - - If we raised the scaling window to 500 circuits, it would require 1050 - circuits if the DoS brought circuit success down to 25% (175 hours), and - 415 circuits if the DoS brought the circuit success down to 5% (69 hours). - - The tradeoff, though, is that larger scaling window values allow Guard nodes - to compromise clients for duty cycles of around the size of this window (up to - the (c/n)^2 * 100/CUTOFF_PERCENT limit in aggregate), so we do have to find - balance between these concerns. - -Implementation Notes: Log Messages - - Log messages need to be chosen with care to avoid alarming users. - I suggest: - - Notice: "Your Guard %s is failing more circuits than usual. Most likely - this means the Tor network is overloaded. Success counts are %d/%d." - - Warn: "Your Guard %s is failing a very large amount of circuits. Most likely - this means the Tor network is overloaded, but it could also mean an attack - against you or potentially the Guard itself. Success counts are %d/%d." - - Drop: "Your Guard %s is failing an extremely large amount of circuits. [Tor - has disabled use of this Guard.] Success counts are %d/%d." - - The second piece of the Drop message would not be present in 0.2.3.x, - since the Guard won't actually be dropped. - -Implementation Notes: Consensus Parameters - - The following consensus parameters reflect the constants listed - in the proposal. These parameters should also be available - for override in torrc. - - pb_mincircs=150 - The minimum number of first hops before we log or drop Guards. - - pb_noticepct=70 - The threshold of circuit success below which we display a notice. - - pb_warnpct=50 - The threshold of circuit success below which we display a warn. - - pb_disablepct=30 - The threshold of circuit success below which we disable the guard. - - pb_scalecircs=300 - The number of first hops at which we scale the counts down. - - pb_scalefactor=2 - The integer divisor by which we scale. - - - -1. http://freehaven.net/anonbib/cache/ccs07-doa.pdf -2. https://lists.torproject.org/pipermail/tor-dev/2012-March/003347.html -3. https://gitweb.torproject.org/torflow.git/tree/HEAD:/CircuitAnalysis/PathBi… -4. https://github.com/meejah/txtorcon/blob/exit_scanner/apps/exit_scanner/fail…

1 0

[torspec/master] edits to proposals 206..208
by nickm＠torproject.org 11 Oct '12

11 Oct '12

commit c68d6fbc397bbe47f1bf9afc0cf15f25e4c95580 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Oct 11 10:31:49 2012 -0400 edits to proposals 206..208 --- proposals/206-directory-sources.txt | 26 +++++++++++++++----------- proposals/207-directory-guards.txt | 23 +++++++++++------------ proposals/208-ipv6-exits-redux.txt | 12 ++++++------ 3 files changed, 32 insertions(+), 29 deletions(-) diff --git a/proposals/206-directory-sources.txt b/proposals/206-directory-sources.txt index 585b9ea..8b8ce66 100644 --- a/proposals/206-directory-sources.txt +++ b/proposals/206-directory-sources.txt @@ -9,8 +9,8 @@ Target: 0.2.4.x Motivation and History: We've long wanted a way for clients to do their initial - bootstrapping, not from the directory authorities, but from some - other set of nodes expected to probably be up as the client is + bootstrapping not from the directory authorities, but from some + other set of nodes expected to probably be up when future clients are starting. We tried to solve this a while ago by adding a feature where we could @@ -23,7 +23,7 @@ Motivation and History: Then for a while we considered an "Extra-Stable" flag so that clients could use only nodes with a long history of existence from these - fallback networkstatus files. We never built it, though.x + fallback networkstatus files. We never built it, though. Instead, we can do this so much more simply. If we want to ship Tor with a list of initial locations to go for directory information, why @@ -33,21 +33,24 @@ Proposal: In the same way that Tor currently ships with a list of directory authorities, Tor should also ship with a list of directory sources -- - places to go for an initial consensus if you don't have a remotely + places to go for an initial consensus if you don't have a somewhat recent one. These need to include an address for the cache's ORPort, and its identity key. Additionally, they should include a selection weight. - Whenever Tor is starting without a consensus, and it would currently + They can be configured with a torrc option, just like directory + authorities are now. + + Whenever Tor is starting without a consensus, if it would currently ask a directory authority for a consensus, it should instead ask one of these preconfigured directory sources. I have code for this (see git branch fallback_dirsource_v2) in my public repository. - When we deploy this, we can (and should) rip out the Fallback- - NetworkstatusFile logic. + When we deploy this, we can (and should) rip out the Fallback + Networkstatus File logic. How to find nodes to make into directory sources: @@ -56,8 +59,8 @@ How to find nodes to make into directory sources: directory sources. First, we could try to vet them a little, with a light variant of the - authority stuff. We'd want to look for nodes where we knew the - operators, verify that they were okay with keeping the same IP for a + process we use for authorities. We'd want to look for nodes where we knew + the operators, verify that they were okay with keeping the same IP for a very long time, and so forth. Second, we could try to pick nodes for listing with each Tor release @@ -74,11 +77,12 @@ How to find nodes to make into directory sources: Some notes on security: - Directory source nodes have an opportunity to learn about more users + Directory source nodes have an opportunity to learn about new users connecting to the network for the first time. Once we have directory guards, that's going to be a fairly uncommon ability. We should be careful in any directory guard design to make sure that we don't fall - back to the directory sources any more than we need to. + back to the directory sources any more than we need to. See proposal 207. + diff --git a/proposals/207-directory-guards.txt b/proposals/207-directory-guards.txt index 1310e14..d0563be 100644 --- a/proposals/207-directory-guards.txt +++ b/proposals/207-directory-guards.txt @@ -17,37 +17,36 @@ Motivation: Proposal: - In the same way as they currently pick guard nodes as needed, adding - more as those nodes are down, clients should also pick a small-ish - set of directory guard nodes, to persist in Tor's state file. + In the same way as they currently pick guard nodes as needed, adding more + guards as those nodes are down, clients should also pick a small-ish set + of directory guard nodes, to persist in Tor's state file. Clients should not pick their own guards as directory guards, or pick their directory guards as regular guards. - When downloading a regular directory object (i.e., not a hidden + When downloading a regular directory object (that is, not a hidden service descriptor), clients should prefer their directory guards first. Then they should try more directories from a recent consensus (if they have one) and pick one of those as a new guard if the existing guards are down and a new one is up. Failing that, they should fall back to a directory authority (or a directory source, if - those get implemented). + those get implemented-- see proposal 206). - - When fetching multiple descriptors in parallel from their guards, - clients should add new guards and try them if only one of the - client's directory guards is running. + If a client has only one directory guard running, they should add new + guards and try them, and then use their directory guards to fetch multiple + descriptors in parallel. Discussion: - The rule that the set of guards and the set directory guards need to + The rule that the set of guards and the set of directory guards need to be disjoint, and the rule that multiple directory guards need to be providing descriptors, are both attempts to make it harder for a - single node to capture route. + single node to capture a route. Open questions and notes: What properties does a node need to be a suitable directory guard? - If we require that it have the Guard flag, we'll lose some nodes; + If we require that it have the Guard flag, we'll lose some nodes: only 74% of the directory caches have it (weighted by bandwidth). We may want to tune the algorithm used to update guards. diff --git a/proposals/208-ipv6-exits-redux.txt b/proposals/208-ipv6-exits-redux.txt index 3b468c0..6185d2a 100644 --- a/proposals/208-ipv6-exits-redux.txt +++ b/proposals/208-ipv6-exits-redux.txt @@ -8,7 +8,7 @@ Target: 0.2.4.x 1. Obligatory Motivation Section - Insert motivations for IPv6 here. Mention IPv4 address exhaustion. + [Insert motivations for IPv6 here. Mention IPv4 address exhaustion. Insert official timeline for official IPv6 adoption here. @@ -17,11 +17,11 @@ Target: 0.2.4.x Insert profession of firm conviction that eventually there will be something somebody wants to connect to which requires the ability to - connect to an IPv6 address. + connect to an IPv6 address.] 2. Proposal - Proposal 117 has been there since coderman wrote it 2007, and it's + Proposal 117 has been there since coderman wrote it in 2007, and it's still mostly right. Rather than replicate it in full, I'll describe this proposal as a patch to it. @@ -31,7 +31,7 @@ Target: 0.2.4.x been moving with IPv4 addresses) to summaries of which IPv6 ports are generally permitted. So let's allow server descriptors to include a list of accepted IPv6 ports, using the same format as the "p" line - in microdecsriptors, using the "ipv6-policy" keyword. + in microdescriptors, using the "ipv6-policy" keyword. "ipv6-policy" SP ("accept" / "reject") SP PortList NL @@ -43,7 +43,7 @@ Target: 0.2.4.x "p6" line in microdescriptors. - This change breaks the existing exit enclave idea for IPv6; but the + This change breaks the existing exit enclave idea for IPv6, but the exiting exit enclave implementation never worked right in the first place. If we can come up with a good way to support it, we can add that back in. @@ -118,7 +118,7 @@ Target: 0.2.4.x - IPv6 addresses are plentiful, which makes cacheing them dangerous + IPv6 addresses are plentiful, which makes caching them dangerous if you're hoping to avoid tracking over time. (With IPv4 addresses, it's harder to give every user a different IPv4 address for a target hostname with a long TTL, and then accept connections to those IPv4

1 0