diff options
| -rw-r--r-- | bandwidth-file-spec.txt | 488 | ||||
| -rw-r--r-- | cert-spec.txt | 5 | ||||
| -rw-r--r-- | control-spec.txt | 17 | ||||
| -rw-r--r-- | dir-spec.txt | 21 | ||||
| -rw-r--r-- | proposals/000-index.txt | 6 | ||||
| -rw-r--r-- | proposals/295-relay-crypto-with-adl.txt | 402 | ||||
| -rw-r--r-- | proposals/295-relay-crypto-with-atl.txt | 263 | ||||
| -rw-r--r-- | proposals/299-ip-failure-count.txt | 174 | ||||
| -rw-r--r-- | proposals/301-dont-vote-on-package-fingerprints.txt | 73 |
9 files changed, 1103 insertions, 346 deletions
diff --git a/bandwidth-file-spec.txt b/bandwidth-file-spec.txt index a241108..1c36558 100644 --- a/bandwidth-file-spec.txt +++ b/bandwidth-file-spec.txt @@ -1,10 +1,10 @@ - Tor Bandwidth List Format + Tor Bandwidth File Format juga teor 1. Scope and preliminaries - This document describes the format of Tor's Bandwidth List, version + This document describes the format of Tor's Bandwidth File, version 1.0.0 and later. It is a new specification for the existing bandwidth file format, @@ -12,7 +12,7 @@ 1.1.0 and later, which are backwards compatible with 1.0.0 parsers. Since Tor version 0.2.4.12-alpha, the directory authorities use - the Bandwidth List file called "V3BandwidthsFile" generated by + the Bandwidth File file called "V3BandwidthsFile" generated by Torflow [1]. The details of this format are described in Torflow's README.spec.txt. We also summarise the format in this specification. @@ -36,15 +36,15 @@ The Tor directory protocol (dir-spec.txt [3]) sections 3.4.1 and 3.4.2, use the term bandwidth measurements, to refer to what - here is called Bandwidth List. + here is called Bandwidth File. - A Bandwidth List file contains information on relays' bandwidth + A Bandwidth File contains information on relays' bandwidth capacities and is produced by bandwidth generators, previously known as bandwidth scanners. 1.4. Format Versions - 1.0.0 - The legacy Bandwidth List format + 1.0.0 - The legacy Bandwidth File format 1.1.0 - Add a header containing information about the bandwidth file. Document the sbws and Torflow relay line keys. @@ -52,20 +52,38 @@ 1.2.0 - If there are not enough eligible relays, the bandwidth file SHOULD contain a header, but no relays. (To match Torflow's existing behaviour.) + Adds new KeyValue Lines to the Header List section with statistics about the number of relays included in the file. - Add new KeyValue Lines to the Relays' Bandwidth List section - with different bandwidth values. + Add new KeyValues to Relay Bandwidth Lines, with different + bandwidth values (averages and descriptor bandwidths). + + 1.3.0 - Adds scanner and destination countries to the header. + + 1.4.0 - Adds monitoring KeyValues to the header and relay lines. + + RelayLines for excluded relays MAY be present in the bandwidth + file for diagnostic reasons. Similarly, if there are not enough + eligible relays, the bandwidth file MAY contain all known relays. + + Diagnostic relay lines SHOULD be marked with vote=0, and + Tor SHOULD NOT use their bandwidths in its votes. All Tor versions can consume format version 1.0.0. - + All Tor versions can consume format version 1.1.0 and later, but Tor versions earlier than 0.3.5.1-alpha warn if the header contains any KeyValue lines after the Timestamp. + Tor versions 0.4.0.3-alpha, 0.3.5.8, 0.3.4.11, and earlier do not + understand "vote=0". Instead, they will vote for the actual bandwidths + that sbws puts in diagnostic relay lines: + * 1 for relays with "unmeasured=1", and + * the relay's measured and scaled bandwidth when "under_min_report=1". + 2. Format details - The Bandwidth List MUST contain the following sections: + The Bandwidth File MUST contain the following sections: - Header List (exactly once), which is a partially ordered list of - Header Lines (one or more times), then - Relay Lines (zero or more times), in an arbitrary order. @@ -76,6 +94,7 @@ The following nonterminals are defined in Tor directory protocol sections 1.2., 2.1.1., 2.1.3.: + bool Int SP (space) NL (newline) @@ -103,6 +122,11 @@ MasterKey ::= a base64-encoded Ed25519 public key, with padding characters omitted. DateTime ::= "YYYY-MM-DDTHH:MM:SS", as in ISO 8601 + CountryCode ::= Two capital ASCII letters ([A-Z]{2}), as defined in + ISO 3166-1 alpha-2 plus "ZZ" to denote unknown country + (eg the destination is in a Content Delivery Network). + CountryCodeList ::= One or more CountryCode(s) separated by a comma + ([A-Z]{2}(,[A-Z]{2})*). Note that key_value and value are defined in Tor directory protocol with different formats to KeyValue and Value here. @@ -237,9 +261,16 @@ [Zero or one time.] The percentage of relays in the consensus that SHOULD be - included in every generated bandwidth file. If there are not - enough eligible relays, the bandwidth file SHOULD contain a - header, but no relays. + included in every generated bandwidth file. + + If this threshold is not reached, format versions 1.3.0 and earlier + SHOULD NOT contain any relays. (Bandwidth files always include a + header.) + + Format versions 1.4.0 and later SHOULD include all the relays for + diagnostic purposes, even if this threshold is not reached. But these + relays SHOULD be marked so that Tor does not vote on them. + See section 1.4 for details. The minimum percentage is 60% in Torflow, so sbws uses 60% as the default. @@ -271,13 +302,172 @@ [Zero or one time.] - The minimum number of relays to include in the bandwidth file. + The minimum number of relays that SHOULD be included in the bandwidth + file. See minimum_percent_eligible_relays for details. This line SHOULD be equal to: number_consensus_relays * (minimum_percent_eligible_relays / 100.0) This Line was added in version 1.2.0 of this specification. + "scanner_country=" CountryCode NL + + [Zero or one time.] + + The country, as in political geolocation, where the generator is run. + + This Line was added in version 1.3.0 of this specification. + + "destinations_countries=" CountryCodeList NL + + [Zero or one time.] + + The country, as in political geolocation, or countries where the + destination Web server(s) are located. + The destination Web Servers serve the data that the generator retrieves + to measure the bandwidth. + + This Line was added in version 1.3.0 of this specification. + + "recent_consensus_count=" Int NL + + [Zero or one time.]. + + The number of the different consensuses seen in the last data_period + days. (data_period is 5 by default.) + + Assuming that Tor clients fetch a consensus every 1-2 hours, + and that the data_period is 5 days, the Value of this Key SHOULD be + between: + data_period * 24 / 2 = 60 + data_period * 24 = 120 + + This Line was added in version 1.4.0 of this specification. + + "recent_priority_list_count=" Int NL + + [Zero or one time.] + + The number of times that a list with a subset of relays prioritized + to be measured has been created in the last data_period days. + (data_period is 5 by default.) + + In 2019, with 7000 relays in the network, the Value of this Key SHOULD be + approximately: + data_period * 24 / 1.5 = 80 + Being 1.5 the approximate number of hours it takes to measure a + priority list of 7000 * 0.05 (350) relays, when the fraction of relays + in a priority list is the 5% (0.05). + + This Line was added in version 1.4.0 of this specification. + + "recent_priority_relay_count=" Int NL + + [Zero or one time.] + + The number of relays that has been in in the list of relays prioritized + to be measured in the last data_period days. (data_period is 5 by + default.) + + In 2019, with 7000 relays in the network, the Value of this Key SHOULD be + approximately: + 80 * (7000 * 0.05) = 28000 + Being 0.05 (5%) the fraction of relays in a priority list and 80 + the approximate number of priority lists (see + "recent_priority_list_count"). + + This Line was added in version 1.4.0 of this specification. + + "recent_measurement_attempt_count=" Int NL + + [Zero or one time.] + + The number of times that any relay has been queued to be measured + in the last data_period days. (data_period is 5 by default.) + + In 2019, with 7000 relays in the network, the Value of this Key SHOULD be + approximately the same as "recent_priority_relay_count", + assuming that there is one attempt to measure a relay for each relay that + has been prioritized unless there are system, network or implementation + issues. + + This Line was added in version 1.4.0 of this specification. + + "recent_measurement_failure_count=" Int NL + + [Zero or one time.] + + The number of times that the scanner attempted to measure a relay in + the last data_period days (5 by default), but the relay has not been + measured because of system, network or implementation issues. + + This Line was added in version 1.4.0 of this specification. + + "recent_measurements_excluded_error_count=" Int NL + + [Zero or one time.] + + The number of relays that have no successful measurements in the last + data_period days (5 by default). + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This Line was added in version 1.4.0 of this specification. + + "recent_measurements_excluded_near_count=" Int NL + + [Zero or one time.] + + The number of relays that have some successful measurements in the last + data_period days (5 by default), but all those measurements were + performed in a period of time that was too short (by default 1 day). + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This Line was added in version 1.4.0 of this specification. + + "recent_measurements_excluded_old_count=" Int NL + + [Zero or one time.] + + The number of relays that have some successful measurements, but all + those measurements are too old (more than 5 days, by default). + + Excludes relays that are already counted in + recent_measurements_excluded_near_count. + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This Line was added in version 1.4.0 of this specification. + + "recent_measurements_excluded_few_count=" Int NL + + [Zero or one time.] + + The number of relays that don't have enough recent successful + measurements. (Fewer than 2 measurements in the last 5 days, by + default). + + Excludes relays that are already counted in + recent_measurements_excluded_near_count and + recent_measurements_excluded_old_count. + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This Line was added in version 1.4.0 of this specification. + + "time_to_report_half_network=" Int NL + + [Zero or one time.] + + The time in seconds that it would take to report measurements about the + half of the network, given the number of eligible relays and the time + it took in the last days (5 days, by default). + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This Line was added in version 1.4.0 of this specification. + KeyValue NL [Zero or more times.] @@ -310,10 +500,10 @@ In version 1.0.0, Header List ends when the first relay bandwidth is found conforming to the next section. - + Implementations of version 1.1.0 and later SHOULD use a 5-character terminator. - + Tor 0.4.0.1-alpha and later look for a 5-character terminator, or the first relay bandwidth line. sbws versions 0.1.0 to 1.0.2 used a 4-character terminator, this bug was fixed in 1.0.3. @@ -334,7 +524,7 @@ If a parser does not recognize any extra material in a RelayLine, the extra material MUST be ignored. - Each RelayLine MUST include the following KeyValue pairs: + Each RelayLine includes the following KeyValue pairs: "node_id=" hexdigest @@ -346,6 +536,13 @@ 0.3.4.1-alpha, node_id MUST NOT be at the end of the Line. These authority versions are no longer supported. + Current Tor versions ignore master_key_ed25519, so node_id MUST be + present in each relay Line. + + Implementations of version 1.1.0 and later SHOULD include both node_id + and master_key_ed25519. Parsers SHOULD accept Lines that contain at + least one of them. + "master_key_ed25519=" MasterKey [Zero or one time.] @@ -354,9 +551,9 @@ without trailing "="s, to avoid ambiguity with KeyValue "=" character. - Implementations of version 1.1.0 SHOULD include both node_id and - master_key_ed25519. - Parsers SHOULD accept Lines that contain at least one of them. + This KeyValue pair SHOULD be present, see the note under node_id. + + This KeyValue was added in version 1.1.0 of this specification. "bw=" Bandwidth @@ -455,95 +652,259 @@ 2.4.2.1. Simple Bandwidth Scanner - sbws RelayLines may contain these keys: + sbws RelayLines contain these keys: - "node_id=" hexdigest SP + "node_id=" hexdigest As above. - "bw=" Bandwidth SP + "bw=" Bandwidth As above. - "nick=" nickname SP + "nick=" nickname [Exactly once.] The relay nickname. - "rtt=" Int SP + Torflow also has a "nick=" KeyValue. - [Exactly once.] + "rtt=" Int + + [Zero or one time.] The Round Trip Time in milliseconds to obtain 1 byte of data. - "time=" DateTime NL + This KeyValue was added in version 1.1.0 of this specification. + It became optional in version 1.3.0 or 1.4.0 of this specification. + + "time=" DateTime [Exactly once.] The date and time timestamp in ISO 8601 format and UTC time zone when the last bandwidth was obtained. - "success=" Int NL + This KeyValue was added in version 1.1.0 of this specification. + The Torflow equivalent is "measured_at=". + + "success=" Int [Zero or one time.] The number of times that the bandwidth measurements for this relay were successful. - "error_circ=" Int NL + This KeyValue was added in version 1.1.0 of this specification. + + "error_circ=" Int [Zero or one time.] The number of times that the bandwidth measurements for this relay failed because of circuit failures. - "error_stream=" Int NL + This KeyValue was added in version 1.1.0 of this specification. + The Torflow equivalent is "circ_fail=". + + "error_stream=" Int [Zero or one time.] The number of times that the bandwidth measurements for this relay failed because of stream failures. - "error_misc=" Int NL + This KeyValue was added in version 1.1.0 of this specification. + + "error_destination=" Int + + [Zero or one time.] + + The number of times that the bandwidth measurements for this relay + failed because the destination Web server was not available. + + This KeyValue was added in version 1.4.0 of this specification. + + "error_second_relay=" Int + + [Zero or one time.] + + The number of times that the bandwidth measurements for this relay + failed because sbws could not find a second relay for the test circuit. + + This KeyValue was added in version 1.4.0 of this specification. + + "error_misc=" Int [Zero or one time.] The number of times that the bandwidth measurements for this relay failed because of other reasons. - "bw_mean=" Int NL + This KeyValue was added in version 1.1.0 of this specification. + + "bw_mean=" Int [Zero or one time.] The measured bandwidth mean for this relay in bytes per second. - "bw_median=" Int NL + This KeyValue was added in version 1.2.0 of this specification. + + "bw_median=" Int [Zero or one time.] The measured bandwidth median for this relay in bytes per second. - "desc_bw_average=" Int NL + This KeyValue was added in version 1.2.0 of this specification. + + "desc_bw_average=" Int [Zero or one time.] The descriptor average bandwidth for this relay in bytes per second. - "desc_bw_obs_last=" Int NL + This KeyValue was added in version 1.2.0 of this specification. + + "desc_obs_bw_last=" Int [Zero or one time.] The last descriptor observed bandwidth for this relay in bytes per second. - "desc_bw_obs_mean=" Int NL + This KeyValue was added in version 1.2.0 of this specification. + + "desc_obs_bw_mean=" Int [Zero or one time.] The descriptor observed bandwidth mean for this relay in bytes per second. + This KeyValue was added in version 1.2.0 of this specification. + + "relay_recent_measurements_excluded_error_count=" Int + + [Zero or one time.] + + The number of recent relay measurement attempts that failed. + Measurements are recent if they are in the last data_period days + (5 by default). + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This KeyValue was added in version 1.4.0 of this specification. + + "relay_recent_measurements_excluded_near_count=" Int + + [Zero or one time.] + + When all of a relay's recent successful measurements were performed in + a period of time that was too short (by default 1 day), the relay is + excluded. This KeyValue contains the number of recent successful + measurements for the relay that were ignored for this reason. + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This KeyValue was added in version 1.4.0 of this specification. + + "relay_recent_measurements_excluded_old_count=" Int + + [Zero or one time.] + + The number of successful measurements for this relay that are too old + (more than data_period days, 5 by default). + + Excludes measurements that are already counted in + relay_recent_measurements_excluded_near_count. + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This KeyValue was added in version 1.4.0 of this specification. + + "recent_measurements_excluded_few_count=" Int + + [Zero or one time.] + + The number of successful measurements for this relay that were ignored + because the relay did not have enough successful measurements (fewer + than 2, by default). + + Excludes measurements that are already counted in + relay_recent_measurements_excluded_near_count or + relay_recent_measurements_excluded_old_count. + + (See the note in section 1.4, version 1.4.0, about excluded relays.) + + This KeyValue was added in version 1.4.0 of this specification. + + "under_min_report=" bool + + [Zero or one time.] + + If the value is 1, there are not enough eligible relays in the + bandwidth file, and Tor bandwidth authorities MAY NOT vote on this + relay. (Current Tor versions do not change their behaviour based on + the "under_min_report" key.) + + If the value is 0 or the KeyValue is not present, there are enough + relays in the bandwidth file. + + Because Tor versions released before April 2019 (see section 1.4. for + the full list of versions) ignore "vote=0", generator implementations + MUST NOT change the bandwidths for under_min_report relays. Using the + same bw value makes authorities that do not understand "vote=0" + or "under_min_report=1" produce votes that don't change relay weights + too much. It also avoids flapping when the reporting threshold is + reached. + + This KeyValue was added in version 1.4.0 of this specification. + + "unmeasured=" bool + + [Zero or one time.] + + If the value is 1, this relay was not successfully measured and + Tor bandwidth authorities MAY NOT vote on this relay. + (Current Tor versions do not change their behaviour based on + the "unmeasured" key.) + + If the value is 0 or the KeyValue is not present, this relay + was successfully measured. + + Because Tor versions released before April 2019 (see section 1.4. for + the full list of versions) ignore "vote=0", generator implementations + MUST set "bw=1" for unmeasured relays. Using the minimum bw value + makes authorities that do not understand "vote=0" or "unmeasured=1" + produce votes that don't change relay weights too much. + + This KeyValue was added in version 1.4.0 of this specification. + + "vote=" bool + + [Zero or one time.] + + If the value is 0, Tor directory authorities SHOULD ignore the relay's + entry in the bandwidth file. They SHOULD vote for the relay the same + way they would vote for a relay that is not present in the file. + + This MAY be the case when this relay was not successfully measured but + it is included in the Bandwidth File, to diagnose why they were not + measured. + + If the value is 1 or the KeyValue is not present, Tor directory + authorities MUST use the relay's bw value in any votes for that relay. + + Implementations MUST also set "bw=1" for unmeasured relays. + But they MUST NOT change the bw for under_min_report relays. + (See the explanations under "unmeasured" and "under_min_report" + for more details.) + + This KeyValue was added in version 1.4.0 of this specification. + 2.4.2.2. Torflow Torflow RelayLines include node_id and bw, and other KeyValue pairs [2]. @@ -552,6 +913,8 @@ References: 1. https://gitweb.torproject.org/torflow.git 2. https://gitweb.torproject.org/torflow.git/tree/NetworkScanners/BwAuthority/README.spec.txt#n332 + The Torflow specification is outdated, and does not match the current + implementation. See section A.1. for the format produced by Torflow. 3. https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt 4. https://gitweb.torproject.org/torspec.git/tree/version-spec.txt 5. https://semver.org/ @@ -562,7 +925,7 @@ The following has not been obtained from any real measurement. A.1. Generated by Torflow - This an example version 1.0.0 document: +This an example version 1.0.0 document: 1523911758 node_id=$68A483E05A2ABDCA6DA5A3EF8DB5177638A27F80 bw=760 nick=Test measured_at=1523911725 updated_at=1523911725 pid_error=4.11374090719 pid_error_sum=4.11374090719 pid_bw=57136645 pid_delta=2.12168374577 circ_fail=0.2 scanner=/filepath @@ -601,7 +964,7 @@ software_version=1.0.3 bw=38000 bw_mean=1127824 bw_median=1180062 desc_avg_bw=1073741824 desc_obs_bw_last=17230879 desc_obs_bw_mean=14732306 error_circ=0 error_misc=0 error_stream=1 master_key_ed25519=YaqV4vbvPYKucElk297eVdNArDz9HtIwUoIeo0+cVIpQ nick=Test node_id=$68A483E05A2ABDCA6DA5A3EF8DB5177638A27F80 rtt=380 success=1 time=2018-05-08T16:13:26 bw=1 bw_mean=199162 bw_median=185675 desc_avg_bw=409600 desc_obs_bw_last=836165 desc_obs_bw_mean=858030 error_circ=0 error_misc=0 error_stream=0 master_key_ed25519=a6a+dZadrQBtfSbmQkP7j2ardCmLnm5NJ4ZzkvDxbo0I nick=Test2 node_id=$96C15995F30895689291F455587BD94CA427B6FC rtt=378 success=1 time=2018-05-08T16:13:36 - When there are not enough eligible measured relays: +A.3.1. When there are not enough eligible measured relays: 1540496079 version=1.2.0 @@ -618,6 +981,55 @@ software=sbws software_version=1.0.3 ===== +A.4. Headers generated by sbws version 1.0.4 + +1523911758 +version=1.3.0 +latest_bandwidth=2018-04-16T20:49:18 +destinations_countries=TH,ZZ +file_created=2018-04-16T21:49:18 +generator_started=2018-04-16T15:13:25 +earliest_bandwidth=2018-04-16T15:13:26 +minimum_number_eligible_relays=3862 +minimum_percent_eligible_relays=60 +number_consensus_relays=6436 +number_eligible_relays=6000 +percent_eligible_relays=93 +scanner_country=SN +software=sbws +software_version=1.0.4 +===== + +A.5 Generated by sbws version 1.1.0 + +1523911758 +version=1.4.0 +latest_bandwidth=2018-04-16T20:49:18 +destinations_countries=TH,ZZ +file_created=2018-04-16T21:49:18 +generator_started=2018-04-16T15:13:25 +earliest_bandwidth=2018-04-16T15:13:26 +minimum_number_eligible_relays=3862 +minimum_percent_eligible_relays=60 +number_consensus_relays=6436 +number_eligible_relays=6000 +percent_eligible_relays=93 +recent_measurement_attempt_count=6243 +recent_measurement_failure_count=732 +recent_measurements_excluded_error_count=969 +recent_measurements_excluded_few_count=3946 +recent_measurements_excluded_near_count=90 +recent_measurements_excluded_old_count=0 +recent_priority_list_count=20 +recent_priority_relay_count=6243 +scanner_country=SN +software=sbws +software_version=1.1.0 +time_to_report_half_network=57273 +===== +bw=1 error_circ=1 error_destination=0 error_misc=0 error_second_relay=0 error_stream=0 master_key_ed25519=J3HQ24kOQWac3L1xlFLp7gY91qkb5NuKxjj1BhDi+m8 nick=snap269 node_id=$DC4D609F95A52614D1E69C752168AF1FCAE0B05F relay_recent_measurement_attempt_count=3 relay_recent_measurements_excluded_error_count=1 relay_recent_measurements_excluded_near_count=3 relay_recent_consensus_count=3 relay_recent_priority_list_count=3 success=3 time=2019-03-16T18:20:57 unmeasured=1 vote=0 +bw=1 error_circ=0 error_destination=0 error_misc=0 error_second_relay=0 error_stream=2 master_key_ed25519=h6ZB1E1yBFWIMloUm9IWwjgaPXEpL5cUbuoQDgdSDKg nick=relay node_id=$C4544F9E209A9A9B99591D548B3E2822236C0503 relay_recent_measurement_attempt_count=3 relay_recent_measurements_excluded_error_count=2 relay_recent_measurements_excluded_few_count=1 relay_recent_consensus_count=3 relay_recent_priority_list_count=3 success=1 time=2019-03-17T06:50:58 unmeasured=1 vote=0 + B. Scaling bandwidths B.1. Scaling requirements diff --git a/cert-spec.txt b/cert-spec.txt index 95c303f..d4dab2e 100644 --- a/cert-spec.txt +++ b/cert-spec.txt @@ -22,6 +22,11 @@ signed document is prefixed with a personalization string, which will be different in each case. +1.2 Integer encoding + + Network byte order (big-endian) is used to encode all integer values + in Ed25519 certificates unless explicitly specified otherwise. + 2. Document formats 2.1. Ed25519 Certificates diff --git a/control-spec.txt b/control-spec.txt index 78a842f..eb3089b 100644 --- a/control-spec.txt +++ b/control-spec.txt @@ -634,6 +634,10 @@ queries. [First implemented in 0.2.0.13-alpha.] [In 0.2.0.9-alpha this switched from v2 directory style to v3] + [In versions before 0.4.1.1-alpha we set the Running flag on + bridges when /ns/purpose/bridge is accessed] + [In 0.4.1.1-alpha we set the Running flag on bridges when the + bridge networkstatus file is written to disk] "desc/all-recent" -- the latest server descriptor for every router that Tor knows about. (See md note about "desc/id" and "desc/name" above.) @@ -3186,7 +3190,7 @@ HsDir = LongName / Fingerprint / "UNKNOWN" DescriptorID = 32*Base32Character / 43*Base64Character Reason = "BAD_DESC" / "QUERY_REJECTED" / "UPLOAD_REJECTED" / "NOT_FOUND" / - "UNEXPECTED" / "QUERY_NO_HSDIR" + "UNEXPECTED" / "QUERY_NO_HSDIR" / "QUERY_RATE_LIMITED" Replica = 1*DIGIT HSDirIndex = 64*HEXDIG @@ -3213,9 +3217,11 @@ - "NOT_FOUND" - HS descriptor with given identifier was not found. - "UNEXPECTED" - nature of failure is unknown. - "QUERY_NO_HSDIR" - No suitable HSDir were found for the query. + - "QUERY_RATE_LIMITED" - query for this service is rate-limited - For "QUERY_NO_HSDIR", the HsDir will be set to "UNKNOWN" which was - introduced in tor 0.3.1.0-alpha. + For "QUERY_NO_HSDIR" or "QUERY_RATE_LIMITED", the HsDir will be set to + "UNKNOWN" which was introduced in tor 0.3.1.0-alpha and 0.4.1.0-alpha + respectively. If Action is "CREATED", Tor SHOULD send Replica field as well. The Replica field contains the replica number of the generated descriptor. The Replica @@ -3261,8 +3267,9 @@ to "UNKNOWN". The HS_DESC event should be used to get more information on the failed request. - If the fetch fails for the QUERY_NO_HSDIR reason from the HS_DESC event, the - HsDir is set to "UNKNOWN". This was introduced in 0.3.1.0-alpha. + If the fetch fails for the QUERY_NO_HSDIR or QUERY_RATE_LIMITED reason from + the HS_DESC event, the HsDir is set to "UNKNOWN". This was introduced in + 0.3.1.0-alpha and 0.4.1.0-alpha respectively. It's expected to receive a reply relatively fast as in it's the time it takes to fetch something over the Tor network. This can be between a diff --git a/dir-spec.txt b/dir-spec.txt index 797f4e5..460d02a 100644 --- a/dir-spec.txt +++ b/dir-spec.txt @@ -440,9 +440,12 @@ the OR is willing to sustain in very short intervals. The "observed" value is an estimate of the capacity this relay can handle. The relay remembers the max bandwidth sustained output over any ten - second period in the past day, and another sustained input. The + second period in the past 5 days, and another sustained input. The "observed" value is the lesser of these two numbers. + Tor versions released before 2018 only kept bandwidth-observed for one + day. These versions are no longer supported or recommended. + "platform" string NL [At most once] @@ -649,13 +652,16 @@ Method = (KeywordChar | "_") + All bridges SHOULD include this line. Non-bridges MUST NOT include - it. (It is not currently implemented, or obeyed by Bridge DB.) + it. (It is currently ignored by Bridge DB.) BridgeDB SHOULD treat unrecognized Method values as if they were "none". (Default: "any") + [This line was introduced in 0.3.2.3-alpha, with a minimal backport + to 0.2.5.16, 0.2.8.17, 0.2.9.14, 0.3.0.13, 0.3.1.9, and later.] + "family" names NL [At most once] @@ -2087,6 +2093,11 @@ Min 1000. Max 4294967295. Default 50000. First-appeared: 0.3.3.6-rc. + "circpad_max_circ_queued_cells" -- The circuitpadding module will + stop sending more padding cells if more than this many cells are in + the circuit queue a given circuit. Min: 0. Max: 50000. Default 1000. + First appeared: 0.4.0.3-alpha. + "shared-rand-previous-value" SP NumReveals SP Value NL [At most once] @@ -2160,7 +2171,8 @@ If an authority is configured with a V3BandwidthsFile, but parsing fails, this line SHOULD appear in its vote, with the digest(s) of the unparseable file. - First-appeared: Tor 0.4.0.2-alpha + + First-appeared: Tor 0.4.0.4-alpha The authority section of a vote contains the following items, followed in turn by the authority's current key certificate: @@ -2680,7 +2692,8 @@ The bandwidth list format is described in bandwidth-file-spec.txt. - The standard URLs for bandwidth list files first-appeared in Tor 0.3.5. + The standard URLs for bandwidth list files first-appeared in + Tor 0.4.0.4-alpha. 3.5. Downloading missing certificates from other directory authorities diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 8b01392..a504c27 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -215,12 +215,13 @@ Proposals by number: 292 Mesh-based vanguards [ACCEPTED] 293 Other ways for relays to know when to publish [CLOSED] 294 TLS 1.3 Migration [DRAFT] -295 Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) [OPEN] +295 Using ADL for relay cryptography (solving the crypto-tagging attack) [OPEN] 296 Have Directory Authorities expose raw bandwidth list files [OPEN] 297 Relaxing the protover-based shutdown rules [CLOSED] 298 Putting family lines in canonical form [CLOSED] 299 Preferring IPv4 or IPv6 based on IP Version Failure Count [OPEN] 300 Walking Onions: Scaling and Saving Bandwidth [DRAFT] +301 Don't include package fingerprints in consensus documents [ACCEPTED] Proposals by status: @@ -250,7 +251,7 @@ Proposals by status: 285 Directory documents should be standardized as UTF-8 287 Reduce circuit lifetime without overloading the network 289 Authenticating sendme cells to mitigate bandwidth attacks - 295 Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) + 295 Using ADL for relay cryptography (solving the crypto-tagging attack) 296 Have Directory Authorities expose raw bandwidth list files 299 Preferring IPv4 or IPv6 based on IP Version Failure Count ACCEPTED: @@ -260,6 +261,7 @@ Proposals by status: 282 Remove "Named" and "Unnamed" handling from consensus voting [for 0.3.3.x] 288 Privacy-Preserving Statistics with Privcount in Tor (Shamir version) 292 Mesh-based vanguards + 301 Don't include package fingerprints in consensus documents META: 000 Index of Tor Proposals 001 The Tor Proposal Process diff --git a/proposals/295-relay-crypto-with-adl.txt b/proposals/295-relay-crypto-with-adl.txt new file mode 100644 index 0000000..f88f3cf --- /dev/null +++ b/proposals/295-relay-crypto-with-adl.txt @@ -0,0 +1,402 @@ +Filename: 295-relay-crypto-with-adl.txt +Title: Using ADL for relay cryptography (solving the crypto-tagging attack) +Author: Tomer Ashur, Orr Dunkelman, Atul Luykx +Created: 22 Feb 2018 +Last-Modified: 1 March 2019 +Status: Open + + +0. Context + + Although Crypto Tagging Attacks were identified already in the + original Tor design, it was not before the rise of the + Procyonidae in 2012 that their severity was fully realized. In + Proposal 202 (Two improved relay encryption protocols for Tor + cells) Nick Mathewson discussed two approaches to stymie tagging + attacks and generally improve Tor's cryptography. In Proposal 261 + (AEZ for relay cryptography) Mathewson puts forward a concrete + approach which uses the tweakable wide-block cipher AEZ. + + This proposal suggests an alternative approach to Proposal 261 + using the notion of Release (of) Unverified Plaintext (RUP) + security. It describes an improved algorithm for circuit + encryption based on CTR-mode which is already used in Tor, and an + additional component for hashing. + + Incidentally, and similar to Proposal 261, this proposal employs + the ENCODE-then-ENCIPHER approach thus it improves Tor's E2E + integrity by using (sufficient) redundancy. + + For more information about the scheme and a security proof for + its RUP-security see + + Tomer Ashur, Orr Dunkelman, Atul Luykx: Boosting + Authenticated Encryption Robustness with Minimal + Modifications. CRYPTO (3) 2017: 3-33 + + available online at https://eprint.iacr.org/2017/239 . + + For authentication between the OP and the edge node we use + the PIV scheme: https://eprint.iacr.org/2013/835 + +2. Preliminaries + +2.1 Motivation + + For motivation, see proposal 202. + +2.2. Notation + + Symbol Meaning + ------ ------- + M Plaintext + C_I Ciphertext + CTR Counter Mode + N_I A de/encryption nonce (to be used in CTR-mode) + T_I A tweak (to be used to de/encrypt the nonce) + T'_I A running digest + ^ XOR + || Concatenation + (This is more readable than a single | but must be adapted + before integrating the proposal into tor-spec.txt) + +2.3. Security parameters + + HASH_LEN -- The length of the hash function's output, in bytes. + + PAYLOAD_LEN -- The longest allowable cell payload, in bytes. (509) + + DIG_KEY_LEN -- The key length used to digest messages (e.g., + using GHASH). Since GHASH is only defined for 128-bit keys, we + recommend DIG_KEY_LEN = 128. + + ENC_KEY_LEN -- The key length used for encryption (e.g., AES). We + recommend ENC_KEY_LEN = 128. + +2.4. Key derivation (replaces Section 5.2.2) + + For newer KDF needs, Tor uses the key derivation function HKDF + from RFC5869, instantiated with SHA256. The generated key + material is: + + K = K_1 | K_2 | K_3 | ... + + where, if H(x,t) denotes HMAC_SHA256 with value x and key t, + and m_expand denotes an arbitrarily chosen value, + and INT8(i) is an octet with the value "i", then + K_1 = H(m_expand | INT8(1) , KEY_SEED ) + and K_(i+1) = H(K_i | m_expand | INT8(i+1) , KEY_SEED ), + in RFC5869's vocabulary, this is HKDF-SHA256 with info == + m_expand, salt == t_key, and IKM == secret_input. + + When used in the ntor handshake a string of key material is + generated and is used in the following way: + + Length Purpose Notation + ------ ------- -------- + HASH_LEN forward digest IV DF * + HASH_LEN backward digest IV DB * + ENC_KEY_LEN encryption key Kf + ENC_KEY_LEN decryption key Kb + DIG_KEY_LEN forward digest key Khf + DIG_KEY_LEN backward digest key Khb + ENC_KEY_LEN forward tweak key Ktf + ENC_KEY_LEN backward tweak key Ktb + DIGEST_LEN nonce to use in the * + hidden service protocol + + * I am not sure that we need these any longer. + + Excess bytes from K are discarded. + +2.6. Ciphers + + For hashing(*) we use GHASH with a DIG_KEY_LEN-bit key. We write + this as Digest(K,M) where K is the key and M the message to be + hashed. + + We use AES with an ENC_KEY_LEN-bit key. For AES encryption + (resp., decryption) we write E(K,X) (resp., D(K,X)) where K is an + ENC_KEY_LEN-bit key and X the block to be encrypted (resp., + decrypted). + + For a stream cipher, unless otherwise specified, we use + ENC_KEY_LEN-bit AES in counter mode, with a nonce that is + generated as explained below. We write this as Encrypt(K,N,X) + (resp., Decrypt(K,N,X)) where K is the key, N the nonce, and X + the message to be encrypted (resp., decrypted). + + (*) The terms hash and digest are used interchangeably. + +3. Routing relay cells + +3.1. Forward Direction + + The forward direction is the direction that CREATE/CREATE2 cells + are sent. + +3.1.1. Routing from the Origin + + Let n denote the integer representing the destination node. For + I = 1...n+1, T'_{I} is initialized to the 128-bit string consisting + entirely of '0's. When an OP sends a relay cell, they prepare the + cell as follows: + + The OP prepares the authentication part of the message: + + C_{n+1} = M + T_{n+1} = Digest(Khf_n,T'_{n+1}||C_{n+1}) + N_{n+1} = T_{n+1} ^ E(Ktf_n,T_{n+1} ^ 0) + T'_{n+1} = T_{n+1} + + Then, the OP prepares the multi-layered encryption: + + For I=n...1: + C_I = Encrypt(Kf_I,N_{I+1},C_{I+1}) + T_I = Digest(Khf_I,T'_I||C_I) + N_I = T_I ^ E(Ktf_I,T_I ^ N_{I+1}) + T'_I = T_I + + The OP sends C_1 and N_1 to node 1. + +3.1.2. Relaying Forward at Onion Routers + + When a forward relay cell is received by OR I, it decrypts the + payload with the stream cipher, as follows: + + 'Forward' relay cell: + + T_I = Digest(Khf_I,T'_I||C_I) + N_{I+1} = T_I ^ D(Ktf_I,T_I ^ N_I) + C_{I+1} = Decrypt(Kf_I,N_{I+1},C_I) + T'_I = T_I + + The OR then decides whether it recognizes the relay cell as + described below. If the OR recognizes the cell, it processes the + contents of the relay cell. Otherwise, it passes C_{I+1}||N_{I+1} + along the circuit if the circuit continues. + + For more information, see section 4 below. + +3.2. Backward Direction + + The backward direction is the opposite direction from + CREATE/CREATE2 cells. + +3.2.1. Relaying Backward at Onion Routers + + When a backward relay cell is received by OR I, it encrypts the + payload with the stream cipher, as follows: + + 'Backward' relay cell: + + T_I = Digest(Khb_I,T'_I||C_{I+1}) + N_I = T_I ^ E(Ktb_I,T_I ^ N_{I+1}) + C_I = Encrypt(Kb_I,N_I,C_{I+1}) + T'_I = T_I + + with C_{n+1} = M and N_{n+1}=0. Once encrypted, the node passes + C_I and N_I along the circuit towards the OP. + +3.2.2. Routing to the Origin + + When a relay cell arrives at an OP, the OP decrypts the payload + with the stream cipher as follows: + + OP receives relay cell from node 1: + + For I=1...n, where n is the end node on the circuit: + C_{I+1} = Decrypt(Kb_I,N_I,C_I) + T_I = Digest(Khb_I,T'_I||C_{I+1}) + N_{I+1} = T_I ^ D(Ktb_I,T_I ^ N_I) + T'_I = T_I + + If the payload is recognized (see Section 4.1), + then: + + The sending node is I. Stop, process the + payload and authenticate. + +4. Application connections and stream management + +4.1. Relay cells + + Within a circuit, the OP and the end node use the contents of + RELAY packets to tunnel end-to-end commands and TCP connections + ("Streams") across circuits. End-to-end commands can be initiated + by either edge; streams are initiated by the OP. + + The payload of each unencrypted RELAY cell consists of: + + Relay command [1 byte] + 'Recognized' [2 bytes] + StreamID [2 bytes] + Length [2 bytes] + Data [PAYLOAD_LEN-23 bytes] + + The 'recognized' field is used as a simple indication that the + cell is still encrypted. It is an optimization to avoid + calculating expensive digests for every cell. When sending cells, + the unencrypted 'recognized' MUST be set to zero. + + When receiving and decrypting cells the 'recognized' will always + be zero if we're the endpoint that the cell is destined for. For + cells that we should relay, the 'recognized' field will usually + be nonzero, but will accidentally be zero with P=2^-16. + + If the cell is recognized, the node moves to verifying the + authenticity of the message as follows(*): + + forward direction (executed by the end node): + + T_{n+1} = Digest(Khf_n,T'_{n+1}||C_{n+1}) + Tag = T_{n+1} ^ D(Ktf_n,T_{n+1} ^ N_{n+1}) + T'_{n+1} = T_{n+1} + + The message is authenticated (i.e., M = C_{n+1}) if + and only if Tag = 0 + + backward direction (executed by the OP): + + The message is authenticated (i.e., C_{n+1} = M) if + and only if N_{n+1} = 0 + + + The old Digest field is removed since sufficient information for + authentication is now included in the nonce part of the payload. + + (*) we should consider dropping the 'recognized' field + altogether and always try to authenticate. Note that this is + an optimization question and the crypto works just as well + either way. + + The 'Length' field of a relay cell contains the number of bytes + in the relay payload which contain real payload data. The + remainder of the payload is padding bytes. + +4.2. Appending the encrypted nonce and dealing with version-homogenic + and version-heterogenic circuits + + When a cell is prepared to be routed from the origin (see Section + 3.1.1) the encrypted nonce N is appended to the encrypted cell + (occupying the last 16 bytes of the cell). If the cell is + prepared to be sent to a node supporting the new protocol, S is + combined with other sources to generate the layer's + nonce. Otherwise, if the node only supports the old protocol, n + is still appended to the encrypted cell (so that following nodes + can still recover their nonce), but a synchronized nonce (as per + the old protocol) is used in CTR-mode. + + When a cell is sent along the circuit in the 'backward' + direction, nodes supporting the new protocol always assume that + the last 16 bytes of the input are the nonce used by the previous + node, which they process as per Section 3.2.1. If the previous + node also supports the new protocol, these cells are indeed the + nonce. If the previous node only supports the old protocol, these + bytes are either encrypted padding bytes or encrypted data. + +5. Security + +5.1. Resistance to crypto-tagging attacks + + A crypto-tagging attack involves a circuit with two colluding + nodes and at least one honest node between them. The attack works + when one node makes a change to the cell (tagging) in a way that + can be undone by the other colluding party. In between, the + tagged cell is processed by honest nodes which do not detect the + change. The attack is possible due to the malleability property + of CTR-mode: a change to a ciphertext bit effects only the + respective plaintext bit in a predicatble way. This proposal + frustrates the crypto-tagging attack by linking the nonce to the + encrypted message such that any change to the ciphertext results + in a random nonce and hence, random plaintext. + + Let us consider the following 3-hop scenario: the entry and end + nodes are malicious and colluding and the middle node is honest. + +5.1.1. forward direction + + Suppose that node I tags the ciphertext part of the message + (C'_{I+1} != C_{I+1}) then forwards it to the next node (I+1). As + per Section 3.1.2. Node I+1 digests C'_{I+1} to generate T_{I+1} + and N_{I+2}. Since C'_{I+2} is different than it should be, so + are the resulting T_{I+1} and N_{I+2}. Hence, decrypting C'_{I+2} + using these values results in a random string for C_{I+2}. Since + C_{I+2} is now just a random string, it is decrypted into a + random string and cannot be 'recognized' nor + authenticated. Furthermore, since C'_{I+1} is different than what + it should be, T'_{I+1} (i.e., the running digest of the middle + node) is now out of sync with that of the OP, which means that + all future cells sent through this node will decrypt into garbage + (random strings). + + Likewise, suppose that instead of tagging the ciphertext, Node I + node tags the encrypted nonce N'_{I+1} != N_{I+1}. Now, when Node + I+1 digests the payload the tweak T_{I+1} is find, but using it + to decrypt N'_{I+1} again results in a random nonce for + N_{I+2}. This random nonce is used to decrypt C_{I+1} into a + random C'_{I+2} which is not recognized by the end node. Since + C_{I+2} is now a random string, the running digest of the end + node is now out of sync, which prevents the end node from + decrypting further cells. + +5.1.2. Backward direction + + In the backward direction the tagging is done by Node I+2 + untagging by the Node I. Suppose first that Node I+2 tags the + ciphertext C_{I+2} and sends it to Node I+1. As per Section + 3.2.1, Node I+1 first digests C_{I+2} and uses the resulting + T_{I+1} to generate a nonce N_{I+1}. From this it is clear that + any change introduced by Node I+2 influences the entire payload + and cannot be removed by Node I. + + Unlike in Section 5.1.1., the cell is blindly delivered by Node I + to the OP which decrypts it. However, since the payload leaving + the end node was modified, the message cannot be authenticated by + the OP which can be trusted to tear down the circuit. + + Suppose now that tagging is done by Node I+2 to the nonce part of + the payload, i.e., N_{I+2}. Since this value is encrypted by Node + I+1 to generate its own nonce N_{I+1}, again, a random nonce is + used which affects the entire keystream of CTR-mode. The cell + again cannot be authenticated by the OP and the circuit is torn + down. + + We note that the end node can modify the plain message before + ever encrypting it and this cannot be discovered by the Tor + protocol. This vulnerability is outside the scope of this + proposal and users should always use TLS to make sure that their + application data is encrypted before it enters the Tor network. + +5.2. End-to-end authentication + + Similar to the old protocol, this proposal only offers end-to-end + authentication rather than per-hop authentication. However, + unlike the old protocol, the ADL-construction is non-malleable + and hence, once a non-authentic message was processed by an + honest node supporting the new protocol, it is effectively + destroyed for all nodes further down the circuit. This is because + the nonce used to de/encrypt all messages is linked to (a digest + of) the payload data. + + As a result, while honest nodes cannot detect non-authentic + messages, such nodes still destroy the message thus invalidating + its authentication tag when it is checked by edge nodes. As a + result, security against crypto-tagging attacks is ensured as + long as an honest node supporting the new protocol processes the + message between two dishonest ones. + +5.3 The Running Digest + + Unlike the old protocol, the running digest is now computed as + the output of a GHASH call instead of a hash function call + (SHA256). Since GHASH does not provide the same type of security + guarantees as SHA256, it is worth discussing why security is not + lost from computing the running digest differently. + + The running digets is used to ensure that if the same payload is + encrypted twice, then the resulting ciphertext does not remain + the same. Therefore, all that is needed is that the digest should + repeat with low probability. GHASH is a universal hash function, + hence it gives such a guarantee assuming its key is chosen + uniformly at random. diff --git a/proposals/295-relay-crypto-with-atl.txt b/proposals/295-relay-crypto-with-atl.txt deleted file mode 100644 index d2a24db..0000000 --- a/proposals/295-relay-crypto-with-atl.txt +++ /dev/null @@ -1,263 +0,0 @@ -Filename: 295-relay-crypto-with-atl.txt -Title: Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) -Author: Tomer Ashur, Orr Dunkelman, Atul Lyukx -Created: 09 Apr 2018 -Status: Open - -0. Context - - Although Crypto Tagging Attacks were identified already in the - original Tor design, it was not before the rise of the Procyonidae in - 2012 that their severity was fully realized. In Proposal 202 (Two - improved relay encryption protocols for Tor cells) Nick Mathewson - discussed two approaches to stymie tagging attacks and generally - improve Tor's cryptography. In Proposal 261 (AEZ for relay - cryptography) Mathewson puts forward a concrete approach which uses - the tweakable wide-block cipher AEZ. - -1. Motivation - - For motivations, see proposal 202. - -2. Summary and preliminaries - - This proposal suggests an alternative approach to Proposal 261 using - the notion of Release (of) Unverified Plaintexts (RUP-security). It - describes an improved algorithm for circuit encryption based on - CTR-mode which is already used in Tor, and an additional component - for hashing. When this additional component is GHash, a GCM-based - solution can be used from the OpenSSL library. - - Incidentally, and similar to Proposal 261, this proposal employs the - ENCODE-then-ENCIPHER approach thus it improves Tor's E2E integrity by - using (sufficiently enough) redundancy. - - For more information about the scheme and a security proof for its - RUP-security see - - Tomer Ashur, Orr Dunkelman, Atul Luykx: Boosting Authenticated - Encryption Robustness with Minimal Modifications. CRYPTO (3) - 2017: 3-33 available online at https://eprint.iacr.org/2017/239 . - -2.1. Cryptographic algorithms - - As an encryption primitive we use AES. We denote one call to the - primitive by E(ยท), e.g., - - Z = E_k(X) - - where k is a K-bit key, X is the input to AES and Z is the output. We - omit k where it is irrelevant or is clear from context. While we - propose to set K=256 to ensure long-term post-quantum resistance, we - stress that the solution also works for other key lengths. - - To encrypt, we use AES is counter mode and a nonce N to produce a - random bit stream, e.g., - - CTR(N) = E(N)||E(N+1)||...||E(N+l) = z_1||z_2||...||Z_{n+1} = Z - - and XOR Z with the message M to produce the ciphertext C, e.g., - - C = Z ^ M - - For authentication, we use the universal hash function GHASH and a - key k, e.g., - - T = H(K||X) = H_k(X) - - where K is a 256-bit key, X an arbitrary length string, and T a - unique authentication tag for X. While we propose to set K=256 to - ensure long-term post-quantum resistance, we stress that the solution - works for any universal hash function as well as for keys of length - K!=256. - -3. The proposed solution - -3.1 An overview of the proposed solution - - Noting that in CTR-mode the nonce is essential for the - encryption/decryption operations, the proposed solution is based on - linking the nonce and the transmitted data in such a way that any - change to the data (e.g., through a tagging attack) randomizes the - nonce and results in a random value Z' != Z for CTR(N' != N). - -3.1.1. 'Forward' direction (same direction as CREATE): - - When preparing a message to be sent in the forward direction, the - client is responsible for encrypting all layers. The client starts by - digesting the message to create a synthetic tweak T_0 = H_{k_fM}(M) - and uses this tweak to encrypt an all-zero string to create a - synthetic IV: S_0 = T_0 ^ E_{k_fE}(0 ^ T_0). - - The message and the synthetic IV (i.e., M||S_0) are passed as input - to the first encryption layer which uses S_0 to produce the random - stream Z = CTR_k1(S_0) and the ciphertext C = Z ^ M. Then, a tweak T - = H_k2(C) is generated by digesting the ciphertext of this - layer. Finally, S_0 is encrypted using AES and the tweak T to produce - an encrypted nonce S = T ^ E_k3(N ^ T) which is appended to the the - ciphertext and is used as the nonce for the next encryption layer. - - After encrypting 3 times, the client sends C||S to the guard. Whereas - the protocol previously required that the nonce be kept in sync - between each node and the client, this is no longer required as it - can now be recovered from C||S. To decrypt, the node first computes T - = H_k2(C) then uses it to obtain S = D_k3(S ^ T) ^ T. Finally, CTR(S) - is used to decrypt C into M. The once-decrypted nonce is appended to - the data and M||S is sent to the next node which repeats this - process. - - The exit verifies the integrity of the message by digesting it and - using the resulting T to decrypt S_0 into N. If N=0, the message is - authenticated. Otherwise, if the message has been changed by an - adversary, N!=0 and the circuit is destroyed. - -3.1.2 'Back' direction (opposite direction from CREATE): - - When sending back a message from the exit to the client, each node - adds an additional layer of encryption. The exit starts by digesting - the message to create a synthetic tweak T_0 = H_{k_bM}(M) and uses - this tweak to encrypt an all-zero string to create a synthetic IV: - S_0 = T_0 ^ E_{k_bE}(0 ^ T_0). The synthetic IV is then used to - produce the random stream Z = CTR_k1(S_0) and uses that to encrypt - the plaintext through C = Z ^ M. The nonce is appended to the - ciphertext and C||S_0 is sent to the next node. - - Receiving a message from the exit, the middle starts by producing a - tweak T = H_k2(C). The tweak is then used to encrypt the nonce - through S = T ^ E_k3(N ^ T) which is then used to produce the random - stream Z' = CTR_k1(S). Finally, the message is encrypted via C' = Z' - ^ C and the encrypted nonce is appended to C'. The message C'||S is - sent to the next node which repeats this procedure. - - When the message arrives at the client, the client peels each layer - using the nonce that is appended at the end of the message. The - decrypted layer is used to compute the tweak T = H_k2(P), which is - used to decrypt this layer's nonce into the next layer's nonce. - - The client verifies the integrity of the message by digesting it and using - the resulting T to decrypt S_0 into N. If N=0, the message is - authenticated. Otherwise, if the message has been changed by an adversary, - N!=0 and the circuit is destroyed. - -3.2 Circuit management - -3.2.1 Creating circuits - - The general process of creating a circuit remains the same (see - tor-spec.txt), except for step 5 where instead of creating a pair of - keys (kf_1,kb_1) for forward and backward communication, - respectively, 2 triplets of keys (kf_1,kf_2,kf_3) and - (kb_1,kb_2,kb_3) are created for communication in the forward and - backward directions, respectively. Two additional pairs of - "authentication keys" (k_fM,k_fE) and (k_bM,k_bE) are created between - the client and the exit in the forward and backward directions, - respectively. - - note: the keys can be created by running KDF-RFC5869 3 times in each - direction, or by running it once in each direction to create a - master-key and derive the rest as subkeys from this master key - -3.2.2 Routing relay cells - - When an OR receives a RELAY or RELAY_EARLY cell, it checks the cell's - circID and determines whether it has a corresponding circuit along - that connection. If not, the OR drops the cell. - - Otherwise, if the OR is not at the OP edge of the circuit (that is, - either an 'exit node' or a non-edge node), it de/encrypts the payload - with the stream cipher, as follows (the message structure is C||S): - - 'Forward' relay cell (same direction as CREATE) - (input structure is: C||S): - - 1. T = H_{kf_2}(T'||C); digest ciphertext (T' is a running digest - of all previous cells, i.e., last round's T) - - 2. N = T ^ D_{kf_3}(S ^ T); decrypt nonce - - 3. M = CTR_{kf_1}(N) ^ C; decrypt message - (output structure is M||N) - - 'Back' relay cell (opposite direction from CREATE) - (input structure is: M||N): - - 1. T = H_{kb_2}(T'||M); digest ciphertext (T' is a running digest - of all previous cells, i.e., last round's T) - - 2. S = T ^ E_{kb_3}(N ^ T); encrypt nonce - - 3. C = CTR_{kb_1}(S) ^ M; encrypt message - (output structure is C||S) - - Note that in counter mode, decrypt (D) and encrypt (E) are the same - operation. - - The OR then decides whether it recognizes the relay cell, by - inspecting the payload as described in Section 4.1 below. If the OR - recognizes the cell, it processes the contents of the relay cell. - Otherwise, it passes the decrypted relay cell along the circuit if - the circuit continues. If the OR at the end of the circuit - encounters an unrecognized relay cell, an error has occurred: the OR - sends a DESTROY cell to tear down the circuit. - -4. Application connections and stream management - -4.1 Relay cells - - Within a circuit, the OP and the exit node use the contents of RELAY - packets to tunnel end-to-end commands and TCP connections ("Streams") - across circuits. End-to-end commands can be initiated by either - edge; streams are initiated by the OP. - - The payload of each unencrypted RELAY cell consists of: - Relay command [1 byte] - 'Recognized' [2 bytes] - StreamID [2 bytes] - Length [2 bytes] - Data [PAYLOAD_LEN-23 bytes] - - The 'recognized' field is used for a simple indication if the cell - still encrypted or not. When sending cells, the unencrypted - 'recognized' MUST be set to zero. - - When receiving and decrypting cells the 'recognized' will always be - zero if we're the endpoint that the cell is destined for. For cells - that we should relay, the 'recognized' field will usually be nonzero, - but will accidentally be zero with P=2^-32. - - The old Digest field is removed, since sufficient information for - authentication is now included in the all-zero string used to create the - nonce for the first encryption layer. - - The 'Length' field of a relay cell contains the number of bytes in - the relay payload which contain real payload data. The remainder of - the payload is padded with NUL bytes. - -4.2 Appending the encrypted nonce - - When a cell is prepared by the client to be sent in the 'forward' - direction, as explained in Section 3.2.2, the encrypted nonce S is - appended to the encrypted cell (occupying the last 16 bytes of the - cell). If the cell is prepared to be sent to a node supporting the - new protocol, S is used as the nonce for the next round's - encryption. Otherwise, if the next node only supports the old - protocol, S is still appended to the encrypted cell, but a - synchronized nonce (as per the old protocol) is used for encryption. - - When a cell is sent along the circuit in the 'backward' direction, - nodes supporting the new protocol always assume that the last 16 - bytes of the input are the nonce used by the previous node, which - they process as per Section 3.2.2. If the previous node also supports - the new protocol, these cells are indeed the nonce. If the previous - node only supports the old protocol, these bytes are either encrypted - NUL bytes or encrypted data. - -4.3 Authenticating the message - - End-to-end authentication is performed in both directions in the same - way. Once the final layer of encryption is removed, the - message-to-be-authenticated is digested and this digest is used to - decrypt the nonce used in this layer. If the decrypted nonce is - all-zero, the message is authentic. Otherwise, if a change was made - to the ciphertext or the encrypted nonce somewhere along the circuit, - the nonce decrypts into a random value and the circuit is destroyed. diff --git a/proposals/299-ip-failure-count.txt b/proposals/299-ip-failure-count.txt index 60d35d4..496217e 100644 --- a/proposals/299-ip-failure-count.txt +++ b/proposals/299-ip-failure-count.txt @@ -29,44 +29,42 @@ Ticket: https://trac.torproject.org/projects/tor/ticket/27491 in the random decision used for choosing an IP family and the data fields used by the algorithm. -2. Failure Counter Design +2. Options To Enable The Failure Counter - I propose that the failure counter uses the following fields: + To enable the failure counter, we will add a flags to ClientAutoIPv6ORPort. + The new format for ClientAutoIPv6ORPort is: - * IPv4 failure count + ClientAutoIPv6ORPort 0|1 [flags] - * IPv4 failure count from no route (autofail) + The first argument is to enable the automatic selection between IPv4 and + IPv6 if it is 1. The second argument is a list of optional flags. - * IPv6 failure count + The only flag so far is "TrackFailures", which enables the tracking of + failures to make a better decision when selecting between IPv4 and IPv6. + The tracking of failures will be described in the rest of this proposal. - * IPv6 failure count from no route (autofail) + However, we should be open to more flags from future proposals as they + are written and implemented. - These entries will exist as internal counters for the current session, and - as a list of the previous counts of these counters from previous sessions in - the state file. +3. Failure Counter Design - These values will be stored as 32-bit unsigned integers for the current - session, and as comma seperated values in the statefile. + I propose that the failure counter uses the following fields: + + * IPv4 failure points - The list capacity will be the 4 most recent sessions for each field above - stored in the state file with the least recent first. This is for the - following reasons: + * IPv6 failure points - * We can forget about the oldest sessions without having to keep the - exact timestamp when a client failed. This prevents an attacker from - getting detailed failure information from the state file. + These entries will exist as internal counters for the current session, and + a calculated value from the previous session in the statefile. - * Some clients (mobile phones, laptops) may switch between networks of - which may be more or less reliable than the previous in terms of IPv4 - or IPv6. In this case, it makes less sense to remember old failures - caused on a different network from the current one. + These values will be stored as 32-bit unsigned integers for the current + session and in the statefile. - When Tor is being closed, and there are less than four entries for each - field, we will append the current session at the end. If there are four - entries, we will remove the oldest entry and then add the current session's - values at Tor's shutdown. + When a new session is loaded, we will load the failure count from the + statefile, and when a session is closed, the failure counts from the current + session will be stored in the statefile. -3. Failure Probability Calculation +4. Failure Probability Calculation The failure count of one IP version will increase the probability of the other IP version. For instance, a failure of IPv4 will increase the IPv6 @@ -92,26 +90,134 @@ Ticket: https://trac.torproject.org/projects/tor/ticket/27491 The failure points for both IPv4 and IPv6 is sum of the values in the state file plus the current session's failure values. The total failure points is - a sum of the IPv4 and IPv6 failure points. + a sum of the IPv4 and IPv6 failure points, and is updated when the failure + point count of an IP version is updated. The probability of a particular IP version is the failure points of the other version divided by the total number of failure points, multiplied - by 8 and stored as an integer. We will call this value the summarized + by 4 and stored as an integer. We will call this value the summarized failure point value (SFPV). The reason for this summarization is to - emulate a probability in 1/8 intervals by the random number generator. + emulate a probability in 1/4 intervals by the random number generator. In the random number generator, we will choose a random number between 0 - and 8. If the random number is less than the IPv6 SFPV, we will choose + and 4. If the random number is less than the IPv6 SFPV, we will choose IPv4. If it is equal or greater, we will choose IPv6. - If the probability is 0/8 with a SFPV value of 0, it will be rounded to - 1/8 with a SFPV of 1. Also, if the probability is 8/8 with a SFPV of 8, - it will be rounded to 7/8 with a SFPV of 7. The reason for this is to + If the probability is 0/4 with a SFPV value of 0, it will be rounded to + 1/4 with a SFPV of 1. Also, if the probability is 4/4 with a SFPV of 4, + it will be rounded to 3/4 with a SFPV of 3. The reason for this is to accomodate mobile clients which could change networks at any time (e.g. WiFi to cellular) which may be more or less reliable in terms of a particular IP family when compared to the previous network of the client. -4. Acknowledgements +5. Initial Failure Point Calculation + + When a client starts without failure points or if the FP value drops to 0, + we need a SFPV value to start with. The Initial SFPV value will be counted + based on whether the client is using a bridge or not and if the relays in + the bridge configuration or consensus have IPv6. + + For clients connecting directly to Tor, we will: + + * During Bootstrap: use the number of IPv4 and IPv6 capable fallback + directory mirrors during bootstrap. + + * After the initial consensus is received: use the number of IPv4 and + IPv6 capable guards in the consensus. + + The reason why the consensus will be used to calculate the initial failure + point value is because using the number of guards would bias the SFPV value + with whatever's dominant on the network rather than what works on the + client. + + For clients connecting through bridges, we will use the number of bridges + configured and the IP versions supported. + + The initial value of the failure points in the scenarios described in this + section would be: + + * IPv4 Faulure Points: Count the number of IPv6-capable relays + + * IPv6 Failure Points: Count the number of IPv4-capable relays + + If the consensus or bridge configuration changes during a session, we should + not update the failure point counters to generate a SFPV. + + If we are starting a new session, we should use the existing failure points + to generate a SFPV unless the counts for IPv4 or IPv6 are zero. + +6. Forgetting Old Sessions + + We should be able to forget old failures as clients could change networks. + For instance, a mobile phone could switch between WiFi and cellular. Keeping + an exact failure history would have privacy implications, so we should store + an approximate history. + + One way we could forget old sessions is by halving all the failure point + (FP) values before adding when: + + * One or more failure point values are a multiple of a random number + between 1 and 5 + + * One or more failure point values are greater than or equal to 100 + + The reason for halving the values at regular intervals is to forget old + sessions while keeping an approxmate history. We halve all FP values so + that one IP version doesn't dominante on the failure count if the other + is halved. This keeps an approximate scale of the failures on a client. + + The reason for halving at a multiple of a random number instead of a fixed + interval is so we can halve regularly while not making it too predictable. + This prevents a situation where we would be halving too often to keep an + approximate failure history. + + If we halve, we add the FP value for the failed IP version after halving all + FPs if done to account for the failure. If halving is not done, we will just + add the FP. + + If the FP value for one IP version goes down to zero, we will re-calculate + the SFPV for that version using the methods described in Section 4. + +7. Separate Concurrent Connection Limits + + Right now, there is a limit for three concurrent connections from a client. + at any given time. This limit includes both IPv4 and IPv6 connections. + This is to prevent denial of service attacks. I propose that a seperate + connection limit is used for IPv4 and IPv6. This means we can have three + concurrent IPv4 connections and three concurrent IPv6 connections at the + same time. + + Having seperate connection limits allows us to deal with networks dropping + packets for a particular IP family while still preventing potential denial + of service attacks. + +8. Pathbias and Failure Probability + + If ClientAutoIPv6ORPort is in use, and pathbias is triggered, we should + ignore "no route" warnings. The reason for this is because we would be + adding two failure points for the failed as described in Section 3 of this + proposal. Adding two failure points would make us more likely to prefer the + competing IP family over the failed one versus than adding a single failure + point on a normal failure. + +9. Counting Successful Connections + + If a connection to a particular IP version is successful, we should use + it. This ensures that clients have a reliable connection to Tor. Accounting + for successful connections can be done by adding one failure point to the + competing IP version of the successful connection. For instance, if we have + a successful IPv6 connection, we add one IPv4 failure point. + + Why use failure points for successful connections? This reduces the need for + separate counters for successes and allows for code reuse. Why add to the + competing version's failure point? Similar to how we should prefer IPv4 if + IPv6 fails, we should also prefer IPv4 if it is successful. We should also + prefer IPv6 if it is successful. + + Even on adding successes, we will still halve the failure counters as + described in Section 5. + +10. Acknowledgements Thank you teor for aiding me with the implementation of Happy Eyeballs in Tor. This would not have been possible if it weren't for you. diff --git a/proposals/301-dont-vote-on-package-fingerprints.txt b/proposals/301-dont-vote-on-package-fingerprints.txt new file mode 100644 index 0000000..125df86 --- /dev/null +++ b/proposals/301-dont-vote-on-package-fingerprints.txt @@ -0,0 +1,73 @@ +Filename: 301-dont-vote-on-package-fingerprints.txt +Title: Don't include package fingerprints in consensus documents +Author: Iain R. Learmonth +Created: 2019-02-21 +Status: Accepted +Ticket: #28465 + +0. Abstract + + I propose modifying the Tor consensus document to remove + digests of the latest versions of package files. These "package" + lines were never used by any directory authority and so add + additional complexity to the consensus voting mechanisms while + adding no additional value. + +1. Introduction + + In proposal 227 [1], to improve the integrity and security of + updates, a way to authenticate the latest versions of core Tor + software through the consensus was described. By listing a location + with this information for each version of each package, we can + augment the update process of Tor software to authenticate the + packages it downloads through the Tor consensus. This was + implemented in tor 0.2.6.3-alpha. + + When looking at modernising our network archive recently [2], I + came across this line for votes and consensuses. If packages are + referenced by the consensus then ideally we should archive those + packages just as we archive referenced descriptors. However, this + line was never present in any vote archived. + +2. Proposal + + We deprecate the "package" line in the specification for votes. + + Directory authorities stop voting for "package" lines in their + votes. Changes to votes do not require a new consensus method, so + this part of the proposal can be implemented separately. + + We allocate a consensus method when this proposal is implemented. + Let's call it consensus method N. + + Authorities will continue computing consensus package lines in the + consensus if the consensus method is between 19 and (N-1). If the + consensus method is N or later, they omit these lines. + +3. Security Considerations + + This proposal removes a feature that could be used for improved + security but currently isn't. As such it is extra code in the + codebase that may have unknown bugs or lead to bugs in the future + due to unexpected interactions. Overall this should be a good + thing for security of Core Tor. + +4. Compatability Considerations + + A new consensus method is required for this proposal. The + "package" line was always optional and so no client should be + depending on it. There are no known consumers of the "package" + lines (there are none to consume anyway). + +A. References + + [1] Nick Mathewson, Mike Perry. "Include package fingerprints in + consensus documents". Tor Proposal 227, February 2014. + [2] Iain Learmonth, Karsten Loesing. "Towards modernising data + collection and archive for the Tor network". Technical Report + 2018-12-001, December 2018. + +B. Acknowledgements + + Thanks to teor and Nick Mathewson for their comments and + suggestions on this proposal. |