diff options
46 files changed, 2514 insertions, 489 deletions
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index d40f0e1..6f56955 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -49,4 +49,4 @@ pages: paths: - public only: - - master + - main @@ -6,9 +6,9 @@ the reader to implement a compatible implementation of Tor without ever having to read the Tor source code. The [proposals](/proposals) directory holds our design proposals. These -include historical documents that have now been merged into . For more -information on the proposal process, including an explanation of how to -make new proposals, see, see +include historical documents that have now been merged into the main +specifications. For more information on the proposal process, including an +explanation of how to make new proposals, see [001-process.txt](/proposals/001-process.txt). ## What you can find here diff --git a/rend-spec-v2.txt b/attic/rend-spec-v2.txt index 0306f4b..0306f4b 100644 --- a/rend-spec-v2.txt +++ b/attic/rend-spec-v2.txt diff --git a/bandwidth-file-spec.txt b/bandwidth-file-spec.txt index 58ce83c..d9f4db6 100644 --- a/bandwidth-file-spec.txt +++ b/bandwidth-file-spec.txt @@ -1161,7 +1161,7 @@ B.1. Scaling requirements B.2. A linear scaling method - If scaling is required, here is a simple linear bandwith scaling + If scaling is required, here is a simple linear bandwidth scaling method, which ensures that all bandwidth votes contain approximately the same total bandwidth: diff --git a/bridgedb-spec.txt b/bridgedb-spec.txt index 5ccce92..51f6e5d 100644 --- a/bridgedb-spec.txt +++ b/bridgedb-spec.txt @@ -94,7 +94,7 @@ Table of Contents in the bridge network status parsed earlier or if the bridge does not have the Running flag. BridgeDB discards bridge descriptors which have a different purpose - than "bridge". BridgeDB can be configured to only accept descriptors + than "bridge". BridgeDB can be configured to only accept descriptors with another purpose or not discard descriptors based on purpose at all. BridgeDB memorizes the IP addresses and OR ports of the remaining diff --git a/control-spec.txt b/control-spec.txt index 1feb250..9295580 100644 --- a/control-spec.txt +++ b/control-spec.txt @@ -1023,7 +1023,7 @@ Table of Contents "net/listeners/dir" - Listeners for Tor directory protocol, as decribed in dir-spec.txt. + Listeners for Tor directory protocol, as described in dir-spec.txt. "net/listeners/socks" @@ -1805,7 +1805,7 @@ Table of Contents ClientBlob = Authorization data for the client, in an opaque format specific to the authorization method (v2 only). - V3Key = The client's base32-encoded ed25519 public key, using only the key + V3Key = The client's base32-encoded x25519 public key, using only the key part of rend-spec-v3.txt section G.1.2 (v3 only). The server reply format is: @@ -2425,6 +2425,14 @@ Table of Contents "DETACHED" / ; Detached from circuit; still retriable "CONTROLLER_WAIT" ; Waiting for controller to use ATTACHSTREAM ; (new in 0.4.5.1-alpha) + "XOFF_SENT" ; XOFF has been sent for this stream + ; (new in 0.4.7.5-alpha) + "XOFF_RECV" ; XOFF has been received for this stream + ; (new in 0.4.7.5-alpha) + "XON_SENT" ; XON has been sent for this stream + ; (new in 0.4.7.5-alpha) + "XON_RECV" ; XON has been received for this stream + ; (new in 0.4.7.5-alpha) Target = TargetAddress ":" Port Port = an integer from 0 to 65535 inclusive @@ -2699,7 +2707,7 @@ Table of Contents [NOTE: This feature was removed in Tor 0.3.2.1-alpha.] - Tor generates this event when it's an directory authority, and + Tor generates this event when it's a directory authority, and somebody has just uploaded a server descriptor. Syntax: @@ -3430,14 +3438,21 @@ Table of Contents "WRITTEN=" BytesWritten SP "TIME=" Time SP "DELIVERED_READ=" DeliveredBytesRead SP "OVERHEAD_READ=" OverheadBytesRead SP - "DELIVERED_WRITTEN=" DeliveredBytesWritten CRLF + "DELIVERED_WRITTEN=" DeliveredBytesWritten SP "OVERHEAD_WRITTEN=" OverheadBytesWritten SP + "SS=" SlowStartState SP + "CWND=" CWNDCells SP + "RTT=" RTTMilliseconds SP + "MIN_RTT=" RTTMilliseconds CRLF BytesRead = 1*DIGIT BytesWritten = 1*DIGIT OverheadBytesRead = 1*DIGIT OverheadBytesWritten = 1*DIGIT DeliveredBytesRead = 1*DIGIT DeliveredBytesWritten = 1*DIGIT + SlowStartState = 0 or 1 + CWNDCells = 1*DIGIT + RTTMilliseconds= 1*DIGIT Time = ISOTime2Frac BytesRead and BytesWritten are the number of bytes read and written @@ -3465,6 +3480,16 @@ Table of Contents The Time field is provided only in versions 0.3.2.1-alpha and later. It records when Tor created the bandwidth event. + The SS, CWND, RTT, and MIN_RTT fields are present only if the circuit + has negotiated congestion control to an onion service or Exit hop (any + intermediate leaky pipe congestion control hops are not examined here). + SS provides an indication if the circuit is in slow start (1), or not (0). + CWND is the size of the congestion window in terms of number of cells. + RTT is the N_EWMA smoothed current RTT value, and MIN_RTT is the minimum + RTT value of the circuit. The SS and CWND fields apply only to the + upstream direction of the circuit. The slow start state and CWND values + of the other endpoint may be different. + These events are generated about once per second per circuit; no events are generated for circuits that had no attached stream writing or reading. @@ -3474,6 +3499,8 @@ Table of Contents [DELIVERED_READ, OVERHEAD_READ, DELIVERED_WRITTEN, and OVERHEAD_WRITTEN were added in Tor 0.3.4.0-alpha] + [SS, CWND, RTT, and MIN_RTT were added in Tor 0.4.7.5-alpha] + 4.1.23. Per-circuit cell stats The syntax is: @@ -3736,7 +3763,7 @@ Table of Contents Program = The program path as defined in the *TransportPlugin configuration option. Tor accepts relative and full path. - Transport = This value indicate a hint on what the PT is such as the + Transport = This value indicates a hint on what the PT is such as the name or the protocol used for instance. Message = The status message that the PT sends back to the tor parent process minus the "STATUS" string prefix. Formatted as diff --git a/dir-list-spec.txt b/dir-list-spec.txt index c2d83f4..65af536 100644 --- a/dir-list-spec.txt +++ b/dir-list-spec.txt @@ -358,7 +358,7 @@ Table of Contents recent Tor versions. weight was removed in version 2.0.0, but is documented because it - may be of interest to libraries implementing Tor's fallaback + may be of interest to libraries implementing Tor's fallback behaviour. DQUOTE SP+ key_value DQUOTE SP* NL @@ -457,7 +457,7 @@ Table of Contents Libraries SHOULD consider the potential load on the authorities, and whether other sources can meet their needs. - Libraries that require high-uptime availablility of Tor directory + Libraries that require high-uptime availability of Tor directory information should investigate the following options: * OnionOO: https://metrics.torproject.org/onionoo.html diff --git a/dir-spec.txt b/dir-spec.txt index 873225d..0de986f 100644 --- a/dir-spec.txt +++ b/dir-spec.txt @@ -395,7 +395,7 @@ Table of Contents upload after this time. (0.4.4.1-alpha was the first version to reject votes in this way.) - Note: Refusing late uploaded votes minimises the chance of a consensus + Note: Refusing late uploaded votes minimizes the chance of a consensus split, particular when authorities are under bandwidth pressure. If an authority is struggling to upload its vote, and finally uploads to a fraction of authorities after this period, they will compute a consensus @@ -711,7 +711,6 @@ Table of Contents - Any OOM invocation due to memory pressure - Any ntor onionskins are dropped - TCP port exhaustion - - DNS timeout reached The timestamp is when at least one metrics was detected. It should always be at the hour and thus, as an example, "2020-01-10 13:00:00" is an @@ -1331,6 +1330,8 @@ Table of Contents is first added after the relay has been running for at least 24 hours. + (Introduced in tor-0.4.6.1-alpha) + "hidserv-rend-relayed-cells" SP NUM SP key=val SP key=val ... NL [At most once.] "hidserv-rend-v3-relayed-cells" SP NUM SP key=val SP key=val ... NL @@ -1351,6 +1352,8 @@ Table of Contents integer and included as 'NUM'. Note that the overall reported value can be negative. + (Introduced in tor-0.4.6.1-alpha) + "hidserv-dir-onions-seen" SP NUM SP key=val SP key=val ... NL [At most once.] "hidserv-dir-v3-onions-seen" SP NUM SP key=val SP key=val ... NL @@ -1366,6 +1369,8 @@ Table of Contents of this line. Note that the overall reported value can be negative. + (Introduced in tor-0.4.6.1-alpha) + "transport" transportname address:port [arglist] NL [Any number.] @@ -1429,7 +1434,7 @@ Table of Contents The "{read|write}-overload-count" are the counts of how many times the reported limits of burst/rate were exhausted and thus the maximum - between the read and write count occurances. To make the counter more + between the read and write count occurrences. To make the counter more meaningful and to avoid multiple connections saturating the counter when a relay is overloaded, we only increment it once a minute. @@ -2241,7 +2246,7 @@ Table of Contents [At most once] - See shared-rand-current-value decription above. + See shared-rand-current-value description above. The authority section of a consensus contains groups of the following items, in the order given, with one group for each authority that contributed to @@ -2288,10 +2293,11 @@ Table of Contents signed (that is, not including the signature) by the RSA identity key (see section 1.3.), encoded in base64. - "Publication" is the publication time of its most recent descriptor, - in the form YYYY-MM-DD HH:MM:SS, in UTC. Implementations MAY base - decisions on publication times in the past, but MUST NOT reject - publication times in the future. + "Publication" was once the publication time of the router's most + recent descriptor, in the form YYYY-MM-DD HH:MM:SS, in UTC. Now + it is only used in votes, and may be set to a fixed value in + consensus documents. Implementations SHOULD ignore this value + in non-vote documents. "IP" is its current IP address; ORPort is its current OR port, "DirPort" is its current directory port, or "0" for "none". @@ -2329,8 +2335,13 @@ Table of Contents "Fast" if the router is suitable for high-bandwidth circuits. "Guard" if the router is suitable for use as an entry guard. "HSDir" if the router is considered a v2 hidden service directory. + "MiddleOnly" if the router is considered unsuitable for + usage other than as a middle relay. Clients do not need + to handle this option, since when it is present, the authorities + will automatically vote against flags that would make the router + usable in other positions. (Since 0.4.7.2-alpha.) "NoEdConsensus" if any Ed25519 key in the router's descriptor or - microdesriptor does not reflect authority consensus. + microdescriptor does not reflect authority consensus. "Stable" if the router is suitable for long-lived circuits. "StaleDesc" if the router should upload a new descriptor because the old one is too old. @@ -2342,7 +2353,7 @@ Table of Contents "Valid" if the router has been 'validated'. Clients before 0.2.9.4-alpha would not use routers without this flag by default. Currently, relays without this flag are omitted - fromthe consensus, and current (post-0.2.9.4-alpha) clients + from the consensus, and current (post-0.2.9.4-alpha) clients assume that every listed relay has this flag. "V2Dir" if the router implements the v2 directory protocol or higher. @@ -2638,6 +2649,13 @@ Table of Contents authority believes that it's been up for at least 96 hours (or the current value of MinUptimeHidServDirectoryV2). + "MiddleOnly" -- An authority should vote for this flag if it believes + that a relay is unsuitable for use except as a middle relay. When + voting for this flag, the authority should also vote against "Exit", + "Guard", "HsDir", and "V2Dir". When voting for this flag, if the + authority votes on the "BadExit" flag, the authority should vote in + favor of "BadExit". (This flag was added in 0.4.7.2-alpha.) + "NoEdConsensus" -- authorities should not vote on this flag; it is produced as part of the consensus for consensus method 22 or later. @@ -2935,7 +2953,7 @@ Table of Contents entries. * If consensus-method 26 or later is in use, then we initialize - bandwith weights to 1 in our calculations, to avoid + bandwidth weights to 1 in our calculations, to avoid division-by-zero errors on unusual networks. * If consensus method 27 or later is used, the microdesc consensus @@ -2957,6 +2975,17 @@ Table of Contents "bwweightscale" and "maxunmeasuredbw" parameters correctly when computing votes. + * If consensus method 32 or later is used, authorities handle the + "MiddleOnly" flag specially when computing a consensus. When the + voters agree to include "MiddleOnly" in a routerstatus, they + automatically remove "Exit", "Guard", "V2Dir", and "HSDir". If + the BadExit flag is included in the consensus, they automatically + add it to the routerstatus. + + * If consensus method 33 or later is used, and the consensus + flavor is "microdesc", then the "Publication" field in the "r" + line is set to "2038-01-01 00:00:00". + The signatures at the end of a consensus document are sorted in ascending order by identity digest. @@ -3026,7 +3055,7 @@ Table of Contents "11" -- Don't consider BadExits when calculating bandwidth weights "12" -- Params are only included if enough auths voted for them "13" -- Omit router entries with missing microdescriptors. - "14" -- Adds support for "a" lines in ns consensues and microdescriptors. + "14" -- Adds support for "a" lines in ns consensuses and microdescriptors. "15" -- Adds support for "p6" lines. "16" -- Adds ntor keys to microdescriptors "17" -- Adds "Unmeasured=1" flags to "w" lines @@ -3039,7 +3068,7 @@ Table of Contents "24" -- No longer lists routers that are not Valid in the consensus. "25" -- Vote on recommended-protocols and required-protocols. "26" -- Initialize bandwidth weights to 1 to avoid division-by-zero. - "27" -- Adds support for "a" lines in microdescriptor consensues. + "27" -- Adds support for "a" lines in microdescriptor consensuses. "28" -- Removes "a" lines from microdescriptors. "29" -- Canonicalizes families in microdescriptors. "30" -- Removes padding from ntor-onion-key. @@ -3560,7 +3589,7 @@ Table of Contents they're about to serve match the right hashes (either the hashes from the fetch URL or the hashes from the consensus, respectively). - (NOTE: Due to squid proxy url limitations at most 92 microdescrriptor hashes + (NOTE: Due to squid proxy url limitations at most 92 microdescriptor hashes can be retrieved in a single request.) 4.4. Downloading extra-info documents from directory authorities @@ -4162,10 +4191,20 @@ C. Converting a curve25519 public key to an ed25519 public key [Recomputing the sign bit from the private key every time sounds rather strange and inefficient to me… —isis] - Alternatively, without access to the corresponding ed25519 private - key, one may use the Montgomery u-coordinate to recover the - Montgomery v-coordinate by computing the right-hand side of the - Montgomery curve equation: + Note that in addition to its coordinates, an expanded Ed25519 private key + also has a 32-byte random value, "prefix", used to compute internal `r` + values in the signature. For security, this prefix value should be + derived deterministically from the curve25519 key. The Tor + implementation derives it as SHA512(private_key | STR)[0..32], where + STR is the nul-terminated string: + + "Derive high part of ed25519 key from curve25519 key\0" + + + On the client side, where there is no access to the curve25519 private + keys, one may use the curve25519 public key's Montgomery u-coordinate to + recover the Montgomery v-coordinate by computing the right-hand side of + the Montgomery curve equation: bv^2 = u(u^2 + au +1) diff --git a/dos-spec.md b/dos-spec.md new file mode 100644 index 0000000..04470b2 --- /dev/null +++ b/dos-spec.md @@ -0,0 +1,97 @@ +# Denial-of-service prevention mechanisms in Tor + +This document is incomplete; it describes some mechanisms that Tor +uses to avoid different kinds of denial-of-service attacks. + +## Handling low-memory conditions + +(See also `tor-spec.txt`, section 8.1.) + +The Tor protocol requires clients, onion services, relays, and +authorities to store various kind of information in buffers and +caches. But an attacker can use these buffers and queues to queues +to exhaust the memory of the a targeted Tor process, and force the +operating system to kill that process. + +Worse still, the ability to kill targeted Tor instances can be used +to facilitate traffic analysis. (For example, see +[the "Sniper Attack" paper](https://www.freehaven.net/anonbib/#sniper14) +by Jansen, Tschorsch, Johnson, and Scheuermann. + +With this in mind, any Tor implementation—especially one that +runs as a relay or onion service—must take steps to prevent +memory-based denial-of-service attacks. + +### Detecting low memory + +The easiest way to notice you're out of memory would, in theory, be +getting an error when you try to allocate more. Unfortunately, some +systems (e.g. Linux) won't actually give you an "out of memory" +error when you're low on memory. Instead, they overcommit and +promise you memory that they can't actually provide… and then later on, +they might kill processes that actually try to use more memory than +they wish they'd given out. + +So in practice, the mainline Tor implementation uses a different +strategy. It uses a self-imposed "MaxMemInQueues" value as an +upper bound for how much memory it's willing to allocate to certain +kinds of queued usages. This value can either be set by the user, +or derived from a fraction of the total amount of system RAM. + +As of Tor 0.4.7.x, the MaxMemInQueues mechanism tracks the following +kinds of allocation: + * Cells queued on circuits. + * Per-connection read or write buffers. + * On-the-fly compression or decompression state. + * Half-open stream records. + * Cached onion service descriptors (hsdir only). + * Cached DNS resolves (relay only). + * GEOIP-based usage activity statistics. + +Note that directory caches aren't counted, since those are stored on +disk and accessed via mmap. + +### Responding to low memory + +If our allocations exceed MaxMemInQueues, then we take the following +steps to reduce our memory allocation. + +*Freeing from caches*: For each of our onion service descriptor +cache, our DNS cache, and our GEOIP statistics cache, we check +whether they account for greater than 20% of our total allocation. +If they do, we free memory from the offending cache until the total +remaining is no more than 10% of our total allocation. + +When freeing entries from a cache, we aim to free (approximately) +the oldest entries first. + +*Freeing from buffers*: After freeing data from caches, we see +whether allocations are still above 90% of MaxMemInQueues. If they +are, we try to close circuits and connections until we are below 90% +of MaxMemInQueues. + +When deciding to what circuits to free, we sort them based on the +age of the oldest data in their queues, and free the ones with the +oldest data. (For example, a circuit on which a single cell has +been queued for 5 minutes would be freed before a circuit where 100 +cells have been queued for 5 seconds.) "Data queued on a circuit" +includes all data that we could drop if the circuit were destroyed: +not only the cells on the circuit's cell queue, but also any bytes +queued in buffers associated with streams or half-stream records +attached to the circuit. + +We free non-tunneled directory connections according to a similar +rule, according to the age of their oldest queued data. + +Upon freeing a circuit, a "DESTROY cell" must be sent in both +directions. + +### Reporting low memory. + +We define a "low threshold" equal to 3/4 of MaxMemInQueues. Every +time our memory usage is above the low threshold, we record +ourselves as being "under memory pressure". + +(This is not currently reported.) + + diff --git a/ext-orport-spec.txt b/ext-orport-spec.txt index ec88244..6b8f8e1 100644 --- a/ext-orport-spec.txt +++ b/ext-orport-spec.txt @@ -63,14 +63,14 @@ Table of Contents We define one authentication type: SAFE_COOKIE. Its AuthType value is 1. It is based on the client proving to the bridge that - it can access a given "cookie" file on disk. The purpose of + it can access a given "cookie" file on disk. The purpose of authentication is to defend against cross-protocol attacks. If the Extended ORPort is enabled, Tor should regenerate the cookie file on startup and store it in $DataDirectory/extended_orport_auth_cookie. - The location of the cookie can be overriden by using the + The location of the cookie can be overridden by using the configuration file parameter ExtORPortCookieAuthFile, which is defined as: @@ -139,7 +139,7 @@ Table of Contents Status [1 octet] Where, - + Status is 1 if the authentication was successfull. If the + + Status is 1 if the authentication was successful. If the authentication failed, Status is 0. 3. The extended ORPort protocol diff --git a/guard-spec.txt b/guard-spec.txt index 883c2bf..357583b 100644 --- a/guard-spec.txt +++ b/guard-spec.txt @@ -421,11 +421,15 @@ Table of Contents {CONFIRMED_GUARDS} and {FILTERED_GUARDS}, and take the first {N_PRIMARY_GUARDS} elements. If there are fewer than {N_PRIMARY_GUARDS} elements, append additional elements to - PRIMARY_GUARDS chosen from ({FILTERED_GUARDS} - {CONFIRMED_GUARDS}) in - sample order. + PRIMARY_GUARDS chosen from ({FILTERED_GUARDS} - {CONFIRMED_GUARDS}), + ordered in "sample order" (that is, by {ADDED_ON_DATE}). Once an element has been added to {PRIMARY_GUARDS}, we do not remove it until it is replaced by some element from {CONFIRMED_GUARDS}. + That is: if a non-primary guard becomes confirmed and not every primary + guard is confirmed, then the list of primary guards list is regenerated, + first from the confirmed guards (as before), and then from any + non-confirmed primary guards. Note that {PRIMARY_GUARDS} do not have to be in {USABLE_FILTERED_GUARDS}: they might be unreachable. @@ -715,15 +719,15 @@ A.1. Parameters with suggested values. [Section:PARAM_VALS] {param:N_PRIMARY_GUARDS} -- 3 {param:PRIMARY_GUARDS_RETRY_SCHED} - -- every 30 minutes for the first 6 hours. - -- every 2 hours for the next 3.75 days. - -- every 4 hours for the next 3 days. + -- every 10 minutes for the first six hours, + -- every 90 minutes for the next 90 hours, + -- every 4 hours for the next 3 days, -- every 9 hours thereafter. - {param:GUARDS_RETRY_SCHED} -- 1 hour - -- every hour for the first 6 hours. - -- every 4 hours for the next 3.75 days. - -- every 18 hours for the next 3 days. + {param:GUARDS_RETRY_SCHED} -- + -- every hour for the first six hours, + -- every 4 hours for the 90 hours, + -- every 18 hours for the next 3 days, -- every 36 hours thereafter. {param:INTERNET_LIKELY_DOWN_INTERVAL} -- 10 minutes diff --git a/padding-spec.txt b/padding-spec.txt index 825f1d7..511ea01 100644 --- a/padding-spec.txt +++ b/padding-spec.txt @@ -143,6 +143,12 @@ Table of Contents user traffic in that time period is multiplexed over a single connection (as it is with Tor). + Though flow measurement in principle can be bidirectional (counting cells + sent in both directions between a pair of IPs) or unidirectional (counting + only cells sent from one IP to another), we assume for safety that all + measurement is unidirectional, and so traffic must be sent by both parties + in order to prevent record splitting. + 2.2. Implementation Tor clients currently maintain one TLS connection to their Guard node to @@ -154,35 +160,41 @@ Table of Contents connections, and pad them, but otherwise not pad between normal relays. Both clients and Guards will maintain a timer for all application (ie: - non-directory) TLS connections. Every time a non-padding packet is sent or - received by either end, that endpoint will sample a timeout value from - between 1.5 seconds and 9.5 seconds using the max(X,X) distribution - described in Section 2.3. The time range is subject to consensus + non-directory) TLS connections. Every time a padding packet sent by an + endpoint, that endpoint will sample a timeout value from + the max(X,X) distribution described in Section 2.3. The default + range is from 1.5 seconds to 9.5 seconds time range, subject to consensus parameters as specified in Section 2.6. - If the connection becomes active for any reason before this timer - expires, the timer is reset to a new random value between 1.5 and 9.5 - seconds. If the connection remains inactive until the timer expires, a - single CELL_PADDING cell will be sent on that connection. + (The timing is randomized to avoid making it obvious which cells are + padding.) - In this way, the connection will only be padded in the event that it is - idle, and will always transmit a packet before the minimum 10 second inactive - timeout. + If another cell is sent for any reason before this timer expires, the timer + is reset to a new random value. -2.3. Padding Cell Timeout Distribution Statistics + If the connection remains inactive until the timer expires, a + single CELL_PADDING cell will be sent on that connection (which will + also start a new timer). + + In this way, the connection will only be padded in a given direction in + the event that it is idle in that direction, and will always transmit a + packet before the minimum 10 second inactive timeout. - It turns out that because the padding is bidirectional, and because both - endpoints are maintaining timers, this creates the situation where the time - before sending a padding packet in either direction is actually - min(client_timeout, server_timeout). + (In practice, an implementation may not be able to determine when, + exactly, a cell is sent on a given channel. For example, even though the + cell has been given to the kernel via a call to `send(2)`, the kernel may + still be buffering that cell. In cases such as these, implementations + should use a reasonable proxy for the time at which a cell is sent: for + example, when the cell is queued. If this strategy is used, + implementations should try to observe the innermost (closest to the wire) + queue that they practically can, and if this queue is already nonempty, + padding should not be scheduled until after the queue does become empty.) - If client_timeout and server_timeout are uniformly sampled, then the - distribution of min(client_timeout,server_timeout) is no longer uniform, and - the resulting average timeout (Exp[min(X,X)]) is much lower than the - midpoint of the timeout range. +2.3. Padding Cell Timeout Distribution Statistics - To compensate for this, instead of sampling each endpoint timeout uniformly, - we instead sample it from max(X,X), where X is uniformly distributed. + To limit the amount of padding sent, instead of sampling each endpoint + timeout uniformly, we instead sample it from max(X,X), where X is + uniformly distributed. If X is a random variable uniform from 0..R-1 (where R=high-low), then the random variable Y = max(X,X) has Prob(Y == i) = (2.0*i + 1)/(R*R). @@ -206,9 +218,6 @@ Table of Contents 15000 7499.5 7995 4999.5 9999.5 20000 9900.5 10661 6666.2 13332.8 - In this way, we maintain the property that the midpoint of the timeout range - is the expected mean time before a padding packet is sent in either - direction. 2.4. Maximum overhead bounds @@ -253,6 +262,13 @@ Table of Contents CELL_PADDING_NEGOTIATE to instruct the relay not to pad, and then does not send any further padding itself. + Currently, clients negotiate padding only when a channel is created, + immediately after sending their NETINFO cell. Recipients SHOULD, however, + accept padding negotiation messages at any time. + + Clients and bridges MUST reject padding negotiation messages from relays, + and close the channel if they receive one. + 2.6. Consensus Parameters Governing Behavior Connection-level padding is controlled by the following consensus parameters: @@ -277,11 +293,22 @@ Table of Contents - Default: 14000 * nf_conntimeout_clients - - The number of seconds to keep circuits opened and available for - clients to use. Note that the actual client timeout is randomized - uniformly from this value to twice this value. This governs client - OR conn lifespan. Reduced padding clients use half the consensus + - The number of seconds to keep never-used circuits opened and + available for clients to use. Note that the actual client timeout is + randomized uniformly from this value to twice this value. + - The number of seconds to keep idle (not currently used) canonical + channels are open and available. (We do this to ensure a sufficient + time duration of padding, which is the ultimate goal.) + - This value is also used to determine how long, after a port has been + used, we should attempt to keep building predicted circuits for that + port. (See path-spec.txt section 2.1.1.) This behavior was + originally added to work around implementation limitations, but it + serves as a reasonable default regardless of implementation. + - For all use cases, reduced padding clients use half the consensus value. + - Implementations MAY mark circuits held open past the reduced padding + quantity (half the consensus value) as "not to be used for streams", + to prevent their use from becoming a distinguisher. - Default: 1800 * nf_pad_before_usage diff --git a/param-spec.txt b/param-spec.txt index b2882a6..67c809d 100644 --- a/param-spec.txt +++ b/param-spec.txt @@ -17,7 +17,6 @@ Table of Contents 9. Denial-of-service parameters 10. Padding-related parameters 11. Guard-related parameters - 12. Relay behavior X. Obsolete parameters 1. Network protocol parameters @@ -83,7 +82,7 @@ Table of Contents "perconnbwrate" and "perconnbwburst" -- if set, each relay sets up a separate token bucket for every client OR connection, and rate limits - that connection indepedently. Typically left unset, except when used for + that connection independently. Typically left unset, except when used for performance experiments around trac entry 1750. Only honored by relays running Tor 0.2.2.16-alpha and later. (Note that relays running 0.2.2.7-alpha through 0.2.2.14-alpha looked for bwconnrate and @@ -191,6 +190,62 @@ Table of Contents Min: 0. Max: 1. Default: 0. First-appeared: 0.2.3.11-alpha + "overload_dns_timeout_scale_percent" -- This value is a percentage of how + many DNS timeout over N seconds we accept before reporting the overload + general state. It is scaled by a factor of 1000 in order to be able to + represent decimal point. As an example, a value of 1000 means 1%. + Min: 0. Max: 100000. Default: 1000. + First-appeared: 0.4.6.8 + Deprecated: 0.4.7.3-alpha-dev + + "overload_dns_timeout_period_secs" -- This value is the period in seconds + of the DNS timeout measurements (the N in the + "overload_dns_timeout_scale_percent" parameter). For this amount of + seconds, we will gather DNS statistics and at the end, we'll do an + assessment on the overload general signal with regards to DNS timeouts. + Min: 0. Max: 2147483647. Default: 600 + First-appeared: 0.4.6.8 + Deprecated: 0.4.7.3-alpha-dev + + "overload_onionskin_ntor_scale_percent" -- This value is a percentage of + how many onionskin ntor drop over N seconds we accept before reporting the + overload general state. It is scaled by a factor of 1000 in order to be + able to represent decimal point. As an example, a value of 1000 means 1%. + Min: 0. Max: 100000. Default: 1000. + First-appeared: 0.4.7.5-alpha + + "overload_onionskin_ntor_period_secs" -- This value is the period in + seconds of the onionskin ntor overload measurements (the N in the + "overload_onionskin_ntor_scale_percent" parameter). For this amount of + seconds, we will gather onionskin ntor statistics and at the end, we'll do + an assessment on the overload general signal. + Min: 0. Max: 2147483647. Default: 21600 (6 hours) + First-appeared: 0.4.7.5-alpha + + "assume-reachable" -- If true, relays should publish descriptors + even when they cannot make a connection to their IPv4 ORPort. + Min: 0. Max: 1. Default: 0. + First appeared: 0.4.5.1-alpha. + + "assume-reachable-ipv6" -- If true, relays should publish + descriptors even when they cannot make a connection to their IPv6 + ORPort. + Min: 0. Max: 1. Default: 0. + First appeared: 0.4.5.1-alpha. + + "exit_dns_timeout" -- The time in milliseconds an Exit sets libevent to + wait before it considers the DNS timed out. The corresponding libevent + option is "timeout:". + Min: 1. Max: 120000. Default: 1000 (1sec) + First appeared: 0.4.7.5-alpha. + + "exit_dns_num_attempts" -- How many attempts _after the first_ should an + Exit should try a timing-out DNS query before calling it hopeless? (Each of + these attempts will wait for "exit_dns_timeout" independently). The + corresponding libevent option is "attempts:". + Min: 0. Max: 255. Default: 2 + First appeared: 0.4.7.5-alpha. + 8. V3 onion service parameters "hs_intro_min_introduce2", "hs_intro_max_introduce2" -- @@ -324,7 +379,7 @@ Table of Contents Min: 0. Max: 1. Default: 0. First appeared: 0.2.6 - "guard-lifetime-days" -- Controls guard lifetime. If a unconfirmed + "guard-lifetime-days" -- Controls guard lifetime. If an unconfirmed guard has been sampled more than this many days ago, it should be removed from the guard sample. Min: 1. Max: 3650. Default: 120. @@ -363,8 +418,9 @@ Table of Contents "guard-extreme-restriction-percent" -- Warn the user if they have configured tor to exclude so many guards that the available guard bandwidth is less than this percentage of the total. - Min: 1. Max: INT32_MAX. Default: 1. - First appeared: 0.3.0 + Min: 1. Max: 100. Default: 1. + First appeared: 0.3.0. MAX was INT32_MAX, which would have no meaningful + effect. MAX lowered to 100 in 0.4.7. "guard-min-filtered-sample-size" -- If fewer than this number of guards is available in the sample after filtering out unusable @@ -394,7 +450,7 @@ Table of Contents Min: 1. Max: INT32_MAX. Default: 15 First appeared: 0.3.0 - "guard-nonprimary-guard-idle-timeout" -- When trying to confirm + "guard-nonprimary-guard-idle-timeout" -- When trying to confirm nonprimary guards, if a guard doesn't answer for more than this long in seconds, treat it as down. Min: 1. Max: INT32_MAX. Default: 600 @@ -406,19 +462,6 @@ Table of Contents Min: 1. Max: 3650. Default: 20. First appeared: 0.3.0 -12. Relay behavior - - "assume-reachable" -- If true, relays should publish descriptors - even when they cannot make a connection to their IPv4 ORPort. - Min: 0. Max: 1. Default: 0. - First appeared: 0.4.5.1-alpha. - - "assume-reachable-ipv6" -- If true, relays should publish - descriptors even when they cannot make a connection to their IPv6 - ORPort. - Min: 0. Max: 1. Default: 0. - First appeared: 0.4.5.1-alpha. - X. Obsolete parameters "NumDirectoryGuards", "NumEntryGuards" -- Number of guard nodes diff --git a/path-spec.txt b/path-spec.txt index b1c9fde..33d50e5 100644 --- a/path-spec.txt +++ b/path-spec.txt @@ -183,7 +183,7 @@ Tables of Contents (F is as above.) * Having a descriptor for every one of the first - NUM_GUARDS_TO_USE guards among our primary guards. (see + NUM_USABLE_PRIMARY_GUARDS guards among our primary guards. (see guard-spec.txt) We define the "fraction of bandwidth-weighted paths" as the product of @@ -192,7 +192,7 @@ Tables of Contents * The fraction of descriptors that we have for nodes with the Guard flag, weighted by their bandwidth for the guard position. * The fraction of descriptors that we have for all nodes, - weighted by their bandwidth for the middle position position. + weighted by their bandwidth for the middle position. * The fraction of descriptors that we have for nodes with the Exit flag, weighted by their bandwidth for the exit position. @@ -491,7 +491,7 @@ Tables of Contents used directly as Xm. Instead of using the mode of discrete build times directly, Tor clients - compute the Xm parameter using the weighted average of the the midpoints + compute the Xm parameter using the weighted average of the midpoints of the 'cbtnummodes' (10) most frequently occurring 10ms histogram bins. Ties are broken in favor of earlier bins (that is, in favor of bins corresponding to shorter build times). @@ -511,7 +511,7 @@ Tables of Contents All times below Xm are counted as having the Xm value via the MAX(), because in Pareto estimators, Xm is supposed to be the lowest value. - However, since clients use mode averaging to estimatre Xm, there can be + However, since clients use mode averaging to estimate Xm, there can be values below our Xm. Effectively, the Pareto estimator then treats that everything smaller than Xm happened at Xm. One can also see that if clients did not do this, alpha could underflow to become negative, which @@ -577,7 +577,7 @@ Tables of Contents to the point 'cbtclosequantile' (default 99) on the Pareto curve, or 60 seconds, whichever is greater. - The actual completion times for these measurements circuits should be + The actual completion times for these measurement circuits should be recorded. Implementations should completely abandon a circuit and ignore the circuit @@ -633,8 +633,8 @@ Tables of Contents Default: 20 Min: 3 Max: 1000 - Effect: This is the number of circuit build times to keep track of - for the following option. + Effect: This is the number of circuit build outcomes (success vs + timeout) to keep track of for the following option. cbtmaxtimeouts Default: 18 @@ -644,6 +644,10 @@ Tables of Contents circuit attempts, the client should discard all of its history and begin learning a fresh timeout value. + Note that if this parameter's value is greater than the value + of 'cbtrecentcount', then the history will never be + discarded because of this feature. + cbtmincircs Default: 100 Min: 1 @@ -651,6 +655,12 @@ Tables of Contents Effect: This is the minimum number of circuits to build before computing a timeout. + Note that if this parameter's value is higher than 1000 (the + number of time observations that a client keeps in its + circular buffer), circuit build timeout calculation is + effectively disabled, and the default timeouts are used + indefinitely. + cbtquantile Default: 80 Min: 10 diff --git a/proposals/000-index.txt b/proposals/000-index.txt index cb9a9fa..7d518c1 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -80,7 +80,7 @@ Proposals by number: 157 Make certificate downloads specific [CLOSED] 158 Clients download consensus + microdescriptors [CLOSED] 159 Exit Scanning [INFORMATIONAL] -160 Authorities vote for bandwidth offsets in consensus [FINISHED] +160 Authorities vote for bandwidth offsets in consensus [CLOSED] 161 Computing Bandwidth Adjustments [CLOSED] 162 Publish the consensus in multiple flavors [CLOSED] 163 Detecting whether a connection comes from a client [SUPERSEDED] @@ -152,7 +152,7 @@ Proposals by number: 229 Further SOCKS5 extensions [REJECTED] 230 How to change RSA1024 relay identity keys [OBSOLETE] 231 Migrating authority RSA1024 identity keys [OBSOLETE] -232 Pluggable Transport through SOCKS proxy [FINISHED] +232 Pluggable Transport through SOCKS proxy [CLOSED] 233 Making Tor2Web mode faster [REJECTED] 234 Adding remittance field to directory specification [REJECTED] 235 Stop assigning (and eventually supporting) the Named flag [CLOSED] @@ -162,7 +162,7 @@ Proposals by number: 239 Consensus Hash Chaining [OPEN] 240 Early signing key revocation for directory authorities [OPEN] 241 Resisting guard-turnover attacks [REJECTED] -242 Better performance and usability for the MyFamily option [RESERVE] +242 Better performance and usability for the MyFamily option [SUPERSEDED] 243 Give out HSDir flag only to relays with Stable flag [CLOSED] 244 Use RFC5705 Key Exporting in our AUTHENTICATE calls [CLOSED] 245 Deprecating and removing the TAP circuit extension protocol [NEEDS-REVISION] @@ -193,22 +193,22 @@ Proposals by number: 270 RebelAlliance: A Post-Quantum Secure Hybrid Handshake Based on NewHope [OBSOLETE] 271 Another algorithm for guard selection [CLOSED] 272 Listed routers should be Valid, Running, and treated as such [CLOSED] -273 Exit relay pinning for web services [DRAFT] +273 Exit relay pinning for web services [RESERVE] 274 Rotate onion keys less frequently [CLOSED] -275 Stop including meaningful "published" time in microdescriptor consensus [ACCEPTED] +275 Stop including meaningful "published" time in microdescriptor consensus [CLOSED] 276 Report bandwidth with lower granularity in consensus documents [DEAD] 277 Detect multiple relay instances running with same ID [OPEN] 278 Directory Compression Scheme Negotiation [CLOSED] 279 A Name System API for Tor Onion Services [NEEDS-REVISION] 280 Privacy-Preserving Statistics with Privcount in Tor [SUPERSEDED] 281 Downloading microdescriptors in bulk [RESERVE] -282 Remove "Named" and "Unnamed" handling from consensus voting [FINISHED] +282 Remove "Named" and "Unnamed" handling from consensus voting [ACCEPTED] 283 Move IPv6 ORPorts from microdescriptors to the microdesc consensus [CLOSED] 284 Hidden Service v3 Control Port [CLOSED] 285 Directory documents should be standardized as UTF-8 [ACCEPTED] 286 Controller APIs for hibernation access on mobile [REJECTED] 287 Reduce circuit lifetime without overloading the network [OPEN] -288 Privacy-Preserving Statistics with Privcount in Tor (Shamir version) [ACCEPTED] +288 Privacy-Preserving Statistics with Privcount in Tor (Shamir version) [RESERVE] 289 Authenticating sendme cells to mitigate bandwidth attacks [CLOSED] 290 Continuously update consensus methods [META] 291 The move to two guard nodes [NEEDS-REVISION] @@ -221,7 +221,7 @@ Proposals by number: 298 Putting family lines in canonical form [CLOSED] 299 Preferring IPv4 or IPv6 based on IP Version Failure Count [SUPERSEDED] 300 Walking Onions: Scaling and Saving Bandwidth [INFORMATIONAL] -301 Don't include package fingerprints in consensus documents [FINISHED] +301 Don't include package fingerprints in consensus documents [OPEN] 302 Hiding onion service clients using padding [CLOSED] 303 When and how to remove support for protocol versions [OPEN] 304 Extending SOCKS5 Onion Service Error Codes [CLOSED] @@ -230,44 +230,47 @@ Proposals by number: 307 Onion Balance Support for Onion Service v3 [RESERVE] 308 Counter Galois Onion: A New Proposal for Forward-Secure Relay Cryptography [OPEN] 309 Optimistic SOCKS Data [OPEN] -310 Towards load-balancing in Prop 271 [FINISHED] +310 Towards load-balancing in Prop 271 [CLOSED] 311 Tor Relay IPv6 Reachability [ACCEPTED] 312 Tor Relay Automatic IPv6 Address Discovery [ACCEPTED] 313 Tor Relay IPv6 Statistics [ACCEPTED] -314 Allow Markdown for proposal format [FINISHED] -315 Updating the list of fields required in directory documents [OPEN] +314 Allow Markdown for proposal format [CLOSED] +315 Updating the list of fields required in directory documents [CLOSED] 316 FlashFlow: A Secure Speed Test for Tor (Parent Proposal) [DRAFT] 317 Improve security aspects of DNS name resolution [NEEDS-REVISION] 318 Limit protover values to 0-63 [CLOSED] 319 RELAY_FRAGMENT cells [OPEN] 320 Removing TAP usage from v2 onion services [REJECTED] -321 Better performance and usability for the MyFamily option (v2) [OPEN] +321 Better performance and usability for the MyFamily option (v2) [ACCEPTED] 322 Extending link specifiers to include the directory port [OPEN] 323 Specification for Walking Onions [OPEN] 324 RTT-based Congestion Control for Tor [OPEN] 325 Packed relay cells: saving space on small commands [OPEN] 326 The "tor-relay" Well-Known Resource Identifier [OPEN] 327 A First Take at PoW Over Introduction Circuits [DRAFT] -328 Make Relays Report When They Are Overloaded [DRAFT] +328 Make Relays Report When They Are Overloaded [CLOSED] 329 Overcoming Tor's Bottlenecks with Traffic Splitting [DRAFT] 330 Modernizing authority contact entries [OPEN] 331 Res tokens: Anonymous Credentials for Onion Service DoS Resilience [DRAFT] -332 Ntor protocol with extra data, version 3 [OPEN] -333 Vanguards lite [DRAFT] -334 A Directory Authority Flag To Mark Relays As Middle-only [OPEN] +332 Ntor protocol with extra data, version 3 [FINISHED] +333 Vanguards lite [FINISHED] +334 A Directory Authority Flag To Mark Relays As Middle-only [SUPERSEDED] +335 An authority-only design for MiddleOnly [CLOSED] +336 Randomized schedule for guard retries [ACCEPTED] +337 A simpler way to decide, "Is this guard usable?" [ACCEPTED] +338 Use an 8-byte timestamp in NETINFO cells [ACCEPTED] +339 UDP traffic over Tor [ACCEPTED] +340 Packed and fragmented relay messages [OPEN] Proposals by status: DRAFT: - 273 Exit relay pinning for web services [for n/a] 294 TLS 1.3 Migration 316 FlashFlow: A Secure Speed Test for Tor (Parent Proposal) 327 A First Take at PoW Over Introduction Circuits - 328 Make Relays Report When They Are Overloaded 329 Overcoming Tor's Bottlenecks with Traffic Splitting 331 Res tokens: Anonymous Credentials for Onion Service DoS Resilience - 333 Vanguards lite NEEDS-REVISION: 212 Increase Acceptable Consensus Age [for 0.2.4.x+] 219 Support for full DNS and DNSSEC resolution in Tor [for 0.2.5.x] @@ -285,30 +288,32 @@ Proposals by status: 287 Reduce circuit lifetime without overloading the network 295 Using ADL for relay cryptography (solving the crypto-tagging attack) 296 Have Directory Authorities expose raw bandwidth list files + 301 Don't include package fingerprints in consensus documents 303 When and how to remove support for protocol versions 306 A Tor Implementation of IPv6 Happy Eyeballs 308 Counter Galois Onion: A New Proposal for Forward-Secure Relay Cryptography 309 Optimistic SOCKS Data - 315 Updating the list of fields required in directory documents 319 RELAY_FRAGMENT cells - 321 Better performance and usability for the MyFamily option (v2) 322 Extending link specifiers to include the directory port 323 Specification for Walking Onions 324 RTT-based Congestion Control for Tor 325 Packed relay cells: saving space on small commands 326 The "tor-relay" Well-Known Resource Identifier 330 Modernizing authority contact entries - 332 Ntor protocol with extra data, version 3 - 334 A Directory Authority Flag To Mark Relays As Middle-only + 340 Packed and fragmented relay messages ACCEPTED: 265 Load Balancing with Overhead Parameters [for 0.2.9.x] - 275 Stop including meaningful "published" time in microdescriptor consensus [for 0.3.1.x-alpha] + 282 Remove "Named" and "Unnamed" handling from consensus voting [for 0.3.3.x] 285 Directory documents should be standardized as UTF-8 - 288 Privacy-Preserving Statistics with Privcount in Tor (Shamir version) 292 Mesh-based vanguards 311 Tor Relay IPv6 Reachability 312 Tor Relay Automatic IPv6 Address Discovery 313 Tor Relay IPv6 Statistics + 321 Better performance and usability for the MyFamily option (v2) + 336 Randomized schedule for guard retries + 337 A simpler way to decide, "Is this guard usable?" + 338 Use an 8-byte timestamp in NETINFO cells + 339 UDP traffic over Tor META: 000 Index of Tor Proposals 001 The Tor Proposal Process @@ -318,13 +323,9 @@ Proposals by status: 257 Refactoring authorities and making them more isolated from the net 290 Continuously update consensus methods FINISHED: - 160 Authorities vote for bandwidth offsets in consensus [for 0.2.1.x] - 232 Pluggable Transport through SOCKS proxy [in 0.2.6] 260 Rendezvous Single Onion Services [in 0.2.9.3-alpha] - 282 Remove "Named" and "Unnamed" handling from consensus voting [for 0.3.3.x] - 301 Don't include package fingerprints in consensus documents - 310 Towards load-balancing in Prop 271 - 314 Allow Markdown for proposal format + 332 Ntor protocol with extra data, version 3 + 333 Vanguards lite [in 0.4.7.1-alpha] CLOSED: 101 Voting on the Tor Directory System [in 0.2.0.x] 102 Dropping "opt" from the directory format [in 0.2.0.x] @@ -360,6 +361,7 @@ Proposals by status: 155 Four Improvements of Hidden Service Performance [in 0.2.1.x] 157 Make certificate downloads specific [for 0.2.4.x] 158 Clients download consensus + microdescriptors [in 0.2.3.1-alpha] + 160 Authorities vote for bandwidth offsets in consensus [for 0.2.1.x] 161 Computing Bandwidth Adjustments [for 0.2.1.x] 162 Publish the consensus in multiple flavors [in 0.2.3.1-alpha] 166 Including Network Statistics in Extra-Info Documents [for 0.2.2] @@ -395,6 +397,7 @@ Proposals by status: 224 Next-Generation Hidden Services in Tor [in 0.3.2.1-alpha] 227 Include package fingerprints in consensus documents [in 0.2.6.3-alpha] 228 Cross-certifying identity keys with onion keys + 232 Pluggable Transport through SOCKS proxy [in 0.2.6] 235 Stop assigning (and eventually supporting) the Named flag [in 0.2.6, 0.2.7] 236 The move to a single guard node 237 All relays are directory servers [for 0.2.7.x] @@ -408,6 +411,7 @@ Proposals by status: 271 Another algorithm for guard selection [in 0.3.0.1-alpha] 272 Listed routers should be Valid, Running, and treated as such [in 0.2.9.3-alpha, 0.2.9.4-alpha] 274 Rotate onion keys less frequently [in 0.3.1.1-alpha] + 275 Stop including meaningful "published" time in microdescriptor consensus [for 0.3.1.x-alpha] [in 0.4.8.1-alpha] 278 Directory Compression Scheme Negotiation [in 0.3.1.1-alpha] 283 Move IPv6 ORPorts from microdescriptors to the microdesc consensus [for 0.3.3.x] [in 0.3.3.1-alpha] 284 Hidden Service v3 Control Port @@ -418,7 +422,12 @@ Proposals by status: 302 Hiding onion service clients using padding [in 0.4.1.1-alpha] 304 Extending SOCKS5 Onion Service Error Codes 305 ESTABLISH_INTRO Cell DoS Defense Extension + 310 Towards load-balancing in Prop 271 + 314 Allow Markdown for proposal format + 315 Updating the list of fields required in directory documents [in 0.4.5.1-alpha] 318 Limit protover values to 0-63 [in 0.4.5.1-alpha] + 328 Make Relays Report When They Are Overloaded + 335 An authority-only design for MiddleOnly [in 0.4.7.2-alpha] SUPERSEDED: 112 Bring Back Pathlen Coin Weight 113 Simplifying directory authority administration @@ -438,12 +447,14 @@ Proposals by status: 194 Mnemonic .onion URLs 210 Faster Headless Consensus Bootstrapping 225 Strawman proposal: commit-and-reveal shared rng + 242 Better performance and usability for the MyFamily option 247 Defending Against Guard Discovery Attacks using Vanguards 249 Allow CREATE cells with >505 bytes of handshake data 252 Single Onion Services 266 Removing current obsolete clients from the Tor network 280 Privacy-Preserving Statistics with Privcount in Tor 299 Preferring IPv4 or IPv6 based on IP Version Failure Count + 334 A Directory Authority Flag To Mark Relays As Middle-only DEAD: 100 Tor Unreliable Datagram Extension Proposal 115 Two Hop Paths @@ -502,11 +513,12 @@ Proposals by status: 211 Internal Mapaddress for Tor Configuration Testing [for 0.2.4.x+] 223 Ace: Improved circuit-creation key exchange 226 "Scalability and Stability Improvements to BridgeDB: Switching to a Distributed Database System and RDBMS" - 242 Better performance and usability for the MyFamily option 255 Controller features to allow for load-balancing hidden services 256 Key revocation for relays and authorities 262 Re-keying live circuits with new cryptographic material + 273 Exit relay pinning for web services [for n/a] 281 Downloading microdescriptors in bulk + 288 Privacy-Preserving Statistics with Privcount in Tor (Shamir version) 307 Onion Balance Support for Onion Service v3 INFORMATIONAL: 159 Exit Scanning diff --git a/proposals/001-process.txt b/proposals/001-process.txt index d6717bf..7211c3b 100644 --- a/proposals/001-process.txt +++ b/proposals/001-process.txt @@ -145,6 +145,12 @@ What should go in a proposal: can avoid really expensive performance regressions, and so we can avoid wasting time on insignificant gains. +How to format proposals: + + Proposals may be written in plain text (like this one), or in Markdown. + If using Markdown, the header must be wrapped in triple-backtick ("```") + lines. Whenever possible, we prefer the Commonmark dialect of Markdown. + Proposal status: Open: A proposal under discussion. diff --git a/proposals/160-bandwidth-offset.txt b/proposals/160-bandwidth-offset.txt index de9c6e4..8ad4d18 100644 --- a/proposals/160-bandwidth-offset.txt +++ b/proposals/160-bandwidth-offset.txt @@ -2,7 +2,7 @@ Filename: 160-bandwidth-offset.txt Title: Authorities vote for bandwidth offsets in consensus Author: Roger Dingledine Created: 4-May-2009 -Status: Finished +Status: Closed Target: 0.2.1.x 1. Motivation diff --git a/proposals/232-pluggable-transports-through-proxy.txt b/proposals/232-pluggable-transports-through-proxy.txt index f4fa1ce..03cee07 100644 --- a/proposals/232-pluggable-transports-through-proxy.txt +++ b/proposals/232-pluggable-transports-through-proxy.txt @@ -2,7 +2,7 @@ Filename: 232-pluggable-transports-through-proxy.txt Title: Pluggable Transport through SOCKS proxy Author: Arturo Filastò Created: 28 February 2012 -Status: Finished +Status: Closed Implemented-In: 0.2.6 Overview diff --git a/proposals/242-better-families.txt b/proposals/242-better-families.txt index 8a79fa2..5f4ac47 100644 --- a/proposals/242-better-families.txt +++ b/proposals/242-better-families.txt @@ -2,7 +2,8 @@ Filename: 242-better-families.txt Title: Better performance and usability for the MyFamily option Author: Nick Mathewson Created: 2015-02-27 -Status: Reserve +Status: Superseded +Superseded-by: 321-happy-families.md 1. Problem statement. diff --git a/proposals/266-removing-current-obsolete-clients.txt b/proposals/266-removing-current-obsolete-clients.txt index bc3592b..a4cc75c 100644 --- a/proposals/266-removing-current-obsolete-clients.txt +++ b/proposals/266-removing-current-obsolete-clients.txt @@ -110,7 +110,7 @@ Superseded-by: 264, 272. 2.1. Dropping connections based on link protocols. - Tor versions before before 0.2.3.6-alpha use a renegotiation-based + Tor versions before 0.2.3.6-alpha use a renegotiation-based handshake instead of our current handshake. We could detect these handshakes and close the connection at the relay side if the client attempts to renegotiate. @@ -137,7 +137,7 @@ Superseded-by: 264, 272. behavior would probably be the same, though.) If we throttled connections rather than closing them, we'd only get - one connnection per authority per hour, but authorities would have to + one connection per authority per hour, but authorities would have to keep open a potentially huge number of sockets. 2.2. Blocking circuit creation under certain circumstances @@ -210,7 +210,7 @@ A. How to "pull the switch." TIME 0: Implement the client/relay side of proposal 264, backported - to every currently existant Tor version that we still + to every currently extant Tor version that we still support. At the same time, add support for the new consensus type to @@ -227,7 +227,7 @@ A. How to "pull the switch." LATER: - At some point after nearly all clients and relays hav + At some point after nearly all clients and relays have upgraded to the versions released at Time 0 or later, we could make the switchover to publishing the new consensus type. diff --git a/proposals/273-exit-relay-pinning.txt b/proposals/273-exit-relay-pinning.txt index 91c3763..4a83a00 100644 --- a/proposals/273-exit-relay-pinning.txt +++ b/proposals/273-exit-relay-pinning.txt @@ -2,7 +2,7 @@ Filename: 273-exit-relay-pinning.txt Title: Exit relay pinning for web services Author: Philipp Winter, Tobias Pulls, Roya Ensafi, and Nick Feamster Created: 2016-09-22 -Status: Draft +Status: Reserve Target: n/a 0. Overview diff --git a/proposals/275-md-published-time-is-silly.txt b/proposals/275-md-published-time-is-silly.txt index 355782b..e08e9a8 100644 --- a/proposals/275-md-published-time-is-silly.txt +++ b/proposals/275-md-published-time-is-silly.txt @@ -2,14 +2,17 @@ Filename: 275-md-published-time-is-silly.txt Title: Stop including meaningful "published" time in microdescriptor consensus Author: Nick Mathewson Created: 20-Feb-2017 -Status: Accepted +Status: Closed Target: 0.3.1.x-alpha +Implemented-In: 0.4.8.1-alpha 0. Status: As of 0.2.9.11 / 0.3.0.7 / 0.3.1.1-alpha, Tor no longer takes any special action on "future" published times, as proposed in section 4. + As of 0.4.0.1-alpha, we implemented a better mechanism for relays to know + when to publish. (See proposal 293.) 1. Overview diff --git a/proposals/282-remove-named-from-consensus.txt b/proposals/282-remove-named-from-consensus.txt index 4c3ba13..7fc28f0 100644 --- a/proposals/282-remove-named-from-consensus.txt +++ b/proposals/282-remove-named-from-consensus.txt @@ -2,7 +2,7 @@ Filename: 282-remove-named-from-consensus.txt Title: Remove "Named" and "Unnamed" handling from consensus voting Author: Nick Mathewson Created: 12-Sep-2017 -Status: Finished +Status: Accepted Target: 0.3.3.x 1. Summary diff --git a/proposals/288-privcount-with-shamir.txt b/proposals/288-privcount-with-shamir.txt index 62faa1d..109c743 100644 --- a/proposals/288-privcount-with-shamir.txt +++ b/proposals/288-privcount-with-shamir.txt @@ -3,7 +3,7 @@ Title: Privacy-Preserving Statistics with Privcount in Tor (Shamir version) Author: Nick Mathewson, Tim Wilson-Brown, Aaron Johnson Created: 1-Dec-2017 Supercedes: 280 -Status: Accepted +Status: Reserve 0. Acknowledgments diff --git a/proposals/301-dont-vote-on-package-fingerprints.txt b/proposals/301-dont-vote-on-package-fingerprints.txt index 0a2f146..8e8b63a 100644 --- a/proposals/301-dont-vote-on-package-fingerprints.txt +++ b/proposals/301-dont-vote-on-package-fingerprints.txt @@ -2,7 +2,7 @@ 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: Finished +Status: Open Ticket: #28465 0. Abstract diff --git a/proposals/310-bandaid-on-guard-selection.txt b/proposals/310-bandaid-on-guard-selection.txt index 74842dc..2001994 100644 --- a/proposals/310-bandaid-on-guard-selection.txt +++ b/proposals/310-bandaid-on-guard-selection.txt @@ -3,7 +3,7 @@ Title: Towards load-balancing in Prop 271 Author: Florentin Rochet, Aaron Johnson et al. Created: 2019-10-27 Supersedes: 271 -Status: Finished +Status: Closed 1. Motivation and Context diff --git a/proposals/314-allow-markdown-proposals.md b/proposals/314-allow-markdown-proposals.md index 99677f0..8469757 100644 --- a/proposals/314-allow-markdown-proposals.md +++ b/proposals/314-allow-markdown-proposals.md @@ -3,7 +3,7 @@ Filename: 314-allow-markdown-proposals.md Title: Allow Markdown for proposal format. Author: Nick Mathewson Created: 23 April 2020 -Status: Finished +Status: Closed ``` # Introduction diff --git a/proposals/315-update-dir-required-fields.txt b/proposals/315-update-dir-required-fields.txt index c22536c..1761a03 100644 --- a/proposals/315-update-dir-required-fields.txt +++ b/proposals/315-update-dir-required-fields.txt @@ -2,7 +2,13 @@ Filename: 315-update-dir-required-fields.txt Title: Updating the list of fields required in directory documents Author: Nick Mathewson Created: 23 April 2020 -Status: Open +Status: Closed +Implemented-In: 0.4.5.1-alpha + +Notes: + + The "hidden-service-dir" field was not made assumed-present; all other + fields were updated. 1. Introduction diff --git a/proposals/321-happy-families.md b/proposals/321-happy-families.md index f9ac7b4..c06cce2 100644 --- a/proposals/321-happy-families.md +++ b/proposals/321-happy-families.md @@ -3,7 +3,7 @@ Filename: 321-happy-families.md Title: Better performance and usability for the MyFamily option (v2) Author: Nick Mathewson Created: 27 May 2020 -Status: Open +Status: Accepted ``` ## Problem statement. @@ -62,8 +62,10 @@ We add a new entry to microdescriptors: `family-keys`. This line contains one or more space-separated strings describing families to which the node belongs. These strings MUST be sorted in -lexicographic order. Clients MUST NOT depend on any particular property -of these strings. +lexicographic order. These strings MAY be base64-formated nonpadded +ed25519 family keys, or may represent some future encoding. + +Clients SHOULD accept unrecognized key formats. ## Changes to voting algorithm @@ -125,7 +127,9 @@ family if ANY of these is true: in its family line, and B's descriptor lists A in its family line. * Client A has descriptors for A and B, and they both contain the - same entry in their family-keys or family-cert. + same entry in their family-keys or family-cert. (Note that a + family-cert key may match a base64-encoded entry in the family-keys + entry.) ## Migration diff --git a/proposals/324-rtt-congestion-control.txt b/proposals/324-rtt-congestion-control.txt index f4397b6..78b6789 100644 --- a/proposals/324-rtt-congestion-control.txt +++ b/proposals/324-rtt-congestion-control.txt @@ -51,6 +51,9 @@ be found at: An exhaustive list of citations for further reading is in Section [CITATIONS]. +A glossary of common congestion control acronyms and terminology is in +Section [GLOSSARY]. + 1. Overview [OVERVIEW] @@ -115,15 +118,14 @@ RELAY_COMMAND_SENDME relay cells every CIRCWINDOW_INCREMENT (100) cells of received RELAY_COMMAND_DATA. This allows those endpoints to measure the current circuit RTT, by -measuring the amount of time between sending of every 100th data cell -and the arrival of the SENDME command that the other endpoint -immediately sends to ack that 100th cell. - -Circuits will record the current RTT measurement as a field in their -circuit_t data structure. The current RTT is N-EWMA smoothed[27] over a -'cc_ewma_cwnd_cnt' multiple of congestion window worth of sendme acks. +measuring the amount of time between sending a RELAY_COMMAND_DATA cell +that would trigger a SENDME from the other endpoint, and the arrival of +that SENDME cell. This means that RTT is measured every 'cc_sendme_inc' +data cells. -Circuits will also record the minimum and maximum RTT seen so far. +Circuits will record the minimum and maximum RTT measurement, as well as +a smoothed value of representing the current RTT. The smoothing for the +current RTT is performed as specified in [N_EWMA_SMOOTHING]. Algorithms that make use of this RTT measurement for congestion window update are specified in [CONTROL_ALGORITHMS]. @@ -146,11 +148,39 @@ If the time delta is 0, that is always treated as a clock stall. If we have measured at least 'cc_bwe_min' RTT values or we have successfully exited slow start, then every sendme ACK, the new candidate RTT is compared to -the stored EWMA RTT. If the new RTT is either 100 times larger than the EWMA -RTT, or 100 times smaller than the stored EWMA RTT, then we do not record that +the stored EWMA RTT. If the new RTT is either 5000 times larger than the EWMA +RTT, or 5000 times smaller than the stored EWMA RTT, then we do not record that estimate, and do not update BDP or the congestion control algorithms for that SENDME ack. +Moreover, if a clock stall is detected by *any* circuit, this fact is +cached, and this cached value is used on circuits for which we do not +have enough data to compute the above heueristics. This cached value is +also exported for use by the edge connection rate calculations done by +[XON_ADVISORY]. + +2.1.2. N_EWMA Smoothing [N_EWMA_SMOOTHING] + +Both RTT estimation and SENDME BDP estimation require smoothing, to +reduce the effects of packet jitter. + +This smoothing is performed using N_EWMA[27], which is an Exponential +Moving Average with alpha = 2/(N+1): + + N_EWMA = BDP*2/(N+1) + N_EWMA_prev*(N-1)/(N+1). + +Flow control rate limiting uses this function + +For both RTT and SENDME BDP estimation, N is the number of SENDME acks +between congestion window updates, divided by the value of consensus +parameter 'cc_ewma_cwnd_pct', and then capped at a max of 'cc_ewma_max', +but always at least 2: + + N = MAX(MIN(CWND_UPDATE_RATE(cc)*cc_ewma_cwnd_pct/100, cc_ewma_max), 2); + +CWND_UPDATE_RATE is normally just round(CWND/cc_sendme_inc), but after +slow start, it is round(CWND/(cc_cwnd_inc_rate*cc_sendme_inc)). + 2.2. SENDME behavior changes We will make four major changes to SENDME behavior to aid in computing @@ -168,19 +198,9 @@ congestion, since the RTT will be measured more often. If experimentation in Shadow shows that more frequent SENDMEs reduce congestion and improve performance but add significant overhead, we can reduce SENDME overhead by allowing SENDME cells to carry stream data, as -well, using Proposal 325. - - TODO: Refer to or include final version of the negotiation proposal for - this: https://gitlab.torproject.org/tpo/core/tor/-/issues/40377 - -Second, all end-to-end relay cells except RELAY_COMMAND_DROP and SENDME -itself will count towards SENDME cell counts. The details behind how these -cells are handled is addressed in section [SYSTEM_INTERACTIONS]. - - XXX: Hrmm, this is not strictly necessary for this proposal to function. - It may make conflux easier though, but we can defer it to then. The - current implementation only counts RELAY_COMMAND_DATA towards sendme - acks, which is the same behavior as the old fixed sendme implementation. +well, using Proposal 325. The method for negotiating a common value of +cc_sendme_inc on a circuit is covered in [ONION_NEGOTIATION] and +[EXIT_NEGOTIATION]. Third, authenticated SENDMEs can remain as-is in terms of protocol behavior, but will require some implementation updates to account for @@ -297,23 +317,11 @@ BDP. We specify all three because they are all useful in various cases. These cases are broken up and combined to form the Piecewise BDP estimator. -The SENDME estimator is smoothed through N-EWMA averaging on these -estimators[27], to smooth out temporary effects. This is accomplished by using -an EWMA function with alpha = 2/(N+1): - - N_EWMA = BDP*2/(N+1) + N_EWMA_prev*(N-1)/(N+1). - -N is specified in terms of the number of current congestion windows worth of -SENDMEs to average, via consensus parameter 'cc_ewma_cwnd_cnt'. - -The cwnd and inflight estimators also use N-EWMA smoothing in the same way, -but only smooth the current RTT estimate, not the congestion window value. - 3.1.1. SENDME arrival BDP estimation -The most accurate way to estimate BDP is to measure the amount of time between -SENDME acks. In this period of time, we know that the endpoint successfully -received 'cc_sendme_inc' cells. +It is possible to directly measure BDP via the amount of time between SENDME +acks. In this period of time, we know that the endpoint successfully received +'cc_sendme_inc' cells. This means that the bandwidth of the circuit is then calculated as: @@ -337,7 +345,7 @@ With this, the calculation becomes: Note that because we are counting the number of cells *between* the first and last sendme of the congestion window, we must subtract 1 from the number -of sendmes actually recieved. Over the time period between the first and last +of sendmes actually received. Over the time period between the first and last sendme of the congestion window, the other endpoint successfully read (num_sendmes-1) * cc_sendme_inc cells. @@ -346,17 +354,22 @@ truncation, we compute the BDP using multiplication first: BDP = (num_sendmes-1) * cc_sendme_inc * RTT_min / num_sendme_timestamp_delta -Note that the SENDME BDP estimation will only work after two (2) SENDME acks -have been received. Additionally, it tends not to be stable unless at least -five (5) num_sendme's are used, due to ack compression. This is controlled by -the 'cc_bwe_min' consensus parameter. Finally, if [CLOCK_HEURISTICS] have -detected a clock jump or stall, this estimator is not updated. +After all of this, the BDP is smoothed using [N_EWMA_SMOOTHING]. + +This smoothing means that the SENDME BDP estimation will only work after two +(2) SENDME acks have been received. Additionally, it tends not to be stable +unless at least 'cc_bwe_min' sendme's are used. This is controlled by the +'cc_bwe_min' consensus parameter. Finally, if [CLOCK_HEURISTICS] have detected +a clock jump or stall, this estimator is not updated. If all edge connections no longer have data available to send on a circuit and all circuit queues have drained without blocking the local orconn, we stop updating this BDP estimate and discard old timestamps. However, we retain the actual estimator value. +Unfortunately, even after all of this, SENDME BDP estimation proved unreliable +in Shadow simulation, due to ack compression. + 3.1.2. Congestion Window BDP Estimation Assuming that the current congestion window is at or above the current BDP, @@ -425,8 +438,9 @@ and RTT_current. These are measured using the time delta between every measured arbitrarily, so long as it is larger than what we would get from SENDME. -RTT_current is N-EWMA smoothed over 'cc_ewma_cwnd_cnt' congestion windows -worth of SENDME acks. +RTT_current is N-EWMA smoothed over 'cc_ewma_cwnd_pct' percent of +congestion windows worth of SENDME acks, up to a max of 'cc_ewma_max' acks, as +described in [N_EWMA_SMOOTHING]. Recall that BOOTLEG_RTT_TOR emits a congestion signal when the current RTT falls below some fractional threshold ('cc_westwood_rtt_thresh') fraction @@ -447,9 +461,10 @@ each ack. Congestion signals are only evaluated when it reaches 0. Note that because the congestion signal threshold of TOR_WESTWOOD is a function of RTT_max, and excessive queuing can cause an increase in RTT_max, -TOR_WESTWOOD may have a runaway condition. For this reason, we specify a -cc_westwodd_rtt_m backoff parameter, which can reduce RTT_max by a percentage -of the difference between RTT_min and RTT_max, in the event of congestion. +TOR_WESTWOOD may have runaway conditions. Additionally, if stream activity is +constant, but of a lower bandwidth than the circuit, this will not drive the +RTT upwards, and this can result in a congestion window that continues to +increase in the absence of any other concurrent activity. Here is the complete congestion window algorithm for Tor Westwood. This will run each time we get a SENDME (aka sendme_process_circuit_level()): @@ -504,27 +519,29 @@ Thus, Vegas estimates estimates the queue use caused by congestion as: queue_use = cwnd - BDP -Original TCP Vegas used a cwnd BDP estimator only. However, because the SENDME -BDP estimate is more accurate, and because Piecewise BDP allows us to back off -more when the local OR connection is blocked, we use Piecewise BDP here. - -For testing, we also parameterize this queue_use calculation as a tunable +Original TCP Vegas used a cwnd BDP estimator only. We added the ability to +switch this BDP estimator in the implementation, and experimented with various +options. We also parameterized this queue_use calculation as a tunable weighted average between the cwnd-based BDP estimate and the piecewise -estimate (consensus parameter 'cc_vegas_bdp_mix'). +estimate (consensus parameter 'cc_vegas_bdp_mix'). After much testing of +various ways to compute BDP, we were still unable to do much better than the +original cwnd estimator. So while this capability to change the BDP estimator +remains in the C implementation, we do not expect it to be used. -Additionally, if the local OR connection is blocked at the time of SENDME ack -arrival, this is treated as an immediate congestion signal. +However, it was useful to use a local OR connection block at the time of +SENDME ack arrival, as an immediate congestion signal. -(We can also optionally use the ECN signal described in -ideas/xxx-backward-ecn.txt, to exit Slow Start.) +(As an additional optimization, we could also use the ECN signal described in +ideas/xxx-backward-ecn.txt, but this is not implemented. It is likely only of +any benefit during Slow Start, and even that benefit is likely small.) Congestion signals from RTT, blocked OR connections, or ECN are processed only once per congestion window. This is achieved through the next_cc_event flag, which is initialized to a cwnd worth of SENDME acks, and is decremented each ack. Congestion signals are only evaluated when it reaches 0. -Here is the complete pseudocode for TOR_VEGAS, which is run once per SENDME -ack: +Here is the complete pseudocode for TOR_VEGAS, which is run every time +an endpoint receives a SENDME ack: # Update acked cells inflight -= cc_sendme_inc @@ -545,18 +562,30 @@ ack: if in_slow_start: if queue_use < cc_vegas_gamma and not orconn_blocked: - cwnd = MAX(cwnd * cc_cwnd_inc_pct_ss, BDP) # Exponential or BDP + # Increment by slow start %, or at least 2 sendme_inc's worth + cwnd = cwnd + MAX(cwnd * cc_cwnd_inc_pct_ss, 2*cc_sendme_inc) + # If our BDP estimator thinks the BDP is still larger, use that + cwnd = MAX(cwnd, BDP) else: - cwnd = BDP + cwnd = BDP + cc_vegas_gamma in_slow_start = 0 else: - if queue_use > cc_vegas_beta or orconn_blocked: - cwnd += cc_cwnd_inc - elif queue_use < cc_vegas_alpha: + if queue_use > cc_vegas_delta: + cwnd = BDP + cc_vegas_delta - cc_cwnd_inc + elif queue_use > cc_vegas_beta or orconn_blocked: cwnd -= cc_cwnd_inc + elif queue_use < cc_vegas_alpha: + cwnd += cc_cwnd_inc cwnd = MAX(cwnd, cc_circwindow_min) - next_cc_event = cwnd / (cc_cwnd_inc_rate * cc_sendme_inc) + + # Count the number of sendme acks until next update of cwnd, + # rounded to nearest integer + if in_slow_start: + next_cc_event = round(cwnd / cc_sendme_inc) + else + # Never increment faster in slow start, only steady state. + next_cc_event = round(cwnd / (cc_cwnd_inc_rate * cc_sendme_inc)) 3.4. Tor NOLA: Direct BDP tracker [TOR_NOLA] @@ -604,6 +633,12 @@ following functions: - connection_edge_package_raw_inbuf() - circuit_resume_edge_reading() +The decision on when a stream is blocked is performed in: + - sendme_note_stream_data_packaged() + - sendme_stream_data_received() + - sendme_connection_edge_consider_sending() + - sendme_process_stream_level() + Tor currently maintains separate windows for each stream on a circuit, to provide individual stream flow control. Circuit windows are SENDME acked as soon as a relay data cell is decrypted and recognized. Stream @@ -637,50 +672,161 @@ either have to commit to allocating a full congestion window worth memory for each stream, or impose a speed limit on our streams. Hence, we will discard stream windows entirely, and instead use a -simpler buffer-based design that uses XON/XOFF as a backstop. This will -allow us to make full use of the circuit congestion window for every -stream in combination, while still avoiding buffer buildup inside the -network. +simpler buffer-based design that uses XON/XOFF to signal when this +buffer is too large. Additionally, the XON cell will contain advisory +rate information based on the rate at which that edge connection can +write data while it has data to write. The other endpoint can rate limit +sending data for that stream to the rate advertised in the XON, to avoid +excessive XON/XOFF chatter and sub-optimal behavior. + +This will allow us to make full use of the circuit congestion window for +every stream in combination, while still avoiding buffer buildup inside +the network. 4.1. Stream Flow Control Without Windows [WINDOWLESS_FLOW] -Each endpoint (client, Exit, or onion service) should send circuit-level +Each endpoint (client, Exit, or onion service) sends circuit-level SENDME acks for all circuit cells as soon as they are decrypted and -recognized, but *before* delivery to their edge connections. If the edge -connection is blocked because an application is not reading, data will -build up in a queue at that endpoint. - -Three consensus parameters will govern the max length of this queue: -xoff_client, xoff_exit, and xoff_mobile. These will be used for Tor -clients, exits, and mobile devices, respectively. These cutoffs will be -a percentage of current 'cwnd' rather than number of cells. Something -like 5% of 'cwnd' should be plenty, since these edge connections should -normally drain *much* faster than Tor itself. - -If the length of an application stream queue exceeds the size provided -in the appropriate consensus parameter, a RELAY_COMMAND_STREAM_XOFF will -be sent, which instructs the other endpoint to stop sending from that -edge connection. This XOFF cell can optionally contain any available -stream data, as well. - -As soon as the queue begins to drain, a RELAY_COMMAND_STREAM_XON will -sent, which allows the other end to resume reading on that edge -connection. Because application streams should drain quickly once they -are active, we will send the XON command as soon as they start draining. -If the queues fill again, another XOFF will be sent. If this results in -excessive XOFF/XON flapping and chatter, we will also use consensus -parameters xon_client, xon_exit, and xon_mobile to optionally specify -when to send an XON. These parameters will be defined in terms of cells -below the xoff_* levels, rather than percentage. The XON cells can also -contain stream data, if any is available. - -Tor's OOM killer will be invoked to close any streams whose application -buffer grows too large, due to memory shortage, or malicious endpoints. - -Note that no stream buffer should ever grow larger than the xoff level -plus 'cwnd', unless an endpoint is ignoring XOFF. So, -'xoff_{client,exit,mobile} + cwnd' should be the hard-close stream -cutoff, regardless of OOM killer status. +recognized, but *before* delivery to their edge connections. + +This means that if the edge connection is blocked because an +application's SOCKS connection or a destination site's TCP connection is +not reading, data will build up in a queue at that endpoint, +specifically in the edge connection's outbuf. + +Consensus parameters will govern the length of this queue that +determines when XON and XOFF cells are sent, as well as when advisory +XON cells that contain rate information can be sent. These parameters +are separate for the queue lengths of exits, and of clients/services. + +(Because clients and services will typically have localhost connections +for their edges, they will need similar buffering limits. Exits may have +different properties, since their edges will be remote.) + +The trunnel relay cell payload definitions for XON and XOFF are: + +struct xoff_cell { + u8 version IN [0x00]; +} + +struct xon_cell { + u8 version IN [0x00]; + + u32 kbps_ewma; +} + +4.1.1. XON/XOFF behavior + +If the length of an edge outbuf queue exceeds the size provided in the +appropriate client or exit XOFF consensus parameter, a +RELAY_COMMAND_STREAM_XOFF will be sent, which instructs the other endpoint to +stop sending from that edge connection. + +Once the queue is expected to empty, a RELAY_COMMAND_STREAM_XON will be sent, +which allows the other end to resume reading on that edge connection. This XON +also indicates the average rate of queue drain since the XOFF. + +Advisory XON cells are also sent whenever the edge connection's drain +rate changes by more than 'cc_xon_change_pct' percent compared to +the previously sent XON cell's value. + +4.1.2. Edge bandwidth rate advertisement [XON_ADVISORY] + +As noted above, the XON cell provides a field to indicate the N_EWMA rate which +edge connections drain their outgoing buffers. + +To compute the drain rate, we maintain a timestamp and a byte count of how many +bytes were written onto the socket from the connection outbuf. + +In order to measure the drain rate of a connection, we need to measure the time +it took between flushing N bytes on the socket and when the socket is available +for writing again. In other words, we are measuring the time it took for the +kernel to send N bytes between the first flush on the socket and the next +poll() write event. + +For example, lets say we just wrote 100 bytes on the socket at time t = 0sec +and at time t = 2sec the socket becomes writeable again, we then estimate that +the rate of the socket is 100 / 2sec thus 50B/sec. + +To make such measurement, we start the timer by recording a timestamp as soon +as data begins to accumulate in an edge connection's outbuf, currently 16KB (32 +cells). We use such value for now because Tor write up to 32 cells at once on a +connection outbuf and so we use this burst of data as an indicator that bytes +are starting to accumulate. + +After 'cc_xon_rate' cells worth of stream data, we use N_EWMA to average this +rate into a running EWMA average, with N specified by consensus parameter +'cc_xon_ewma_cnt'. Every EWMA update, the byte count is set to 0 and a new +timestamp is recorded. In this way, the EWMA counter is averaging N counts of +'cc_xon_rate' cells worth of bytes each. + +If the buffers are non-zero, and we have sent an XON before, and the N_EWMA +rate has changed more than 'cc_xon_change_pct' since the last XON, we send an +updated rate. Because the EWMA rate is only updated every 'cc_xon_rate' cells +worth of bytes, such advisory XON updates can not be sent more frequent than +this, and should be sent much less often in practice. + +When the outbuf completely drains to 0, and has been 0 for 'cc_xon_rate' cells +worth of data, we double the EWMA rate. We continue to double it while the +outbuf is 0, every 'cc_xon_rate' cells. The measurement timestamp is also set +back to 0. + +When an XOFF is sent, the EWMA rate is reset to 0, to allow fresh calculation +upon drain. + +If a clock stall or jump is detected by [CLOCK_HEURISTICS], we also +clear the fields, but do not record them in ewma. + +NOTE: Because our timestamps are microseconds, we chose to compute and +transmit both of these rates as 1000 byte/sec units, as this reduces the +number of multiplications and divisions and avoids precision loss. + +4.1.3. Oomkiller behavior + +A malicious client can attempt to exhaust memory in an Exits outbufs, by +ignoring XOFF and advisory XONs. Implementations MAY choose to close specific +streams with outbufs that grow too large, but since the exit does not know +with certainty the client's congestion window, it is non-trival to determine +the exact upper limit a well-behaved client might send on a blocked stream. + +Implementations MUST close the streams with the oldest chunks present in their +outbufs, while under global memory pressure, until memory pressure is +relieved. + +4.1.4. Sidechannel mitigation + +In order to mitigate DropMark attacks[28], both XOFF and advisory XON +transmission must be restricted. Because DropMark attacks are most severe +before data is sent, clients MUST ensure that an XOFF does not arrive before +it has sent the appropriate XOFF limit of bytes on a stream ('cc_xoff_exit' +for exits, 'cc_xoff_client' for onions). + +Clients also SHOULD ensure that advisory XONs do not arrive before the +minimum of the XOFF limit and 'cc_xon_rate' full cells worth of bytes have +been transmitted. + +Clients SHOULD ensure that advisory XONs do not arrive more frequently than +every 'cc_xon_rate' cells worth of sent data. Clients also SHOULD ensure than +XOFFs do not arrive more frequently than every XOFF limit worth of sent data. + +Implementations SHOULD close the circuit if these limits are violated on the +client-side, to detect and resist dropmark attacks[28]. + +Additionally, because edges no longer use stream SENDME windows, we alter the +half-closed connection handling to be time based instead of data quantity +based. Half-closed connections are allowed to receive data up to the larger +value of the congestion control max_rtt field or the circuit build timeout +(for onion service circuits, we use twice the circuit build timeout). Any data +or relay cells after this point are considered invalid data on the circuit. + +Recall that all of the dropped cell enforcement in C-Tor is performed by +accounting data provided through the control port CIRC_BW fields, currently +enforced only by using the vanguards addon[29]. + +The C-Tor implementation exposes all of these properties to CIRC_BW for +vanguards to enforce, but does not enforce them itself. So violations of any +of these limits do not cause circuit closure unless that addon is used (as +with the rest of the dropped cell side channel handling in C-Tor). 5. System Interactions [SYSTEM_INTERACTIONS] @@ -788,15 +934,6 @@ delivery of SENDMEs will still allow a full congestion window full of data to arrive. This will also require tuning and experimentation, and optimum results will vary between simulator and live network. - TODO: Can we use explicit SENDME sequence number acking to make a - connection-resumption conflux, to recover from circuit collapse - or client migration? I am having trouble coming up with a design - that does not require Exits to maintain a full congestion - window full of data as a retransmit buffer in the event of - circuit close. Such reconnect activity might require assistance - from Guard relays so that they can help clients discover which - cells were sent vs lost. - 6. Performance Evaluation [EVALUATION] @@ -810,13 +947,23 @@ determine how stable the RTT measurements of circuits are across the live Tor network, to determine if we need more frequent SENDMEs, and/or need to use any RTT smoothing or averaging. - These experiments were performed using onion service clients and services on the live Tor network. From these experiments, we tuned the RTT and BDP estimators, and arrived at reasonable values for EWMA smoothing and the minimum number of SENDME acks required to estimate BDP. -We should check small variations in the EWMA smoothing and minimum BDP ack +Additionally, we specified that the algorithms maintain previous congestion +window estimates in the event that a circuit goes idle, rather than revert to +slow start. We experimented with intermittent idle/active live onion clients +to make sure that this behavior is acceptable, and it appeared to be. + +In Shadow experimentation, the primary thing to test will be if the OR conn on +Exit relays blocks too frequently when under load, thus causing excessive +congestion signals, and overuse of the Inflight BDP estimator as opposed +to SENDME or CWND BDP. It may also be the case that this behavior is optimal, +even if it does happen. + +Finally, we should check small variations in the EWMA smoothing and minimum BDP ack counts in Shadow experimentation, to check for high variability in these estimates, and other surprises. @@ -847,44 +994,93 @@ parameter for them. This will allow us to set more reasonable parameter values, without waiting for all clients to upgrade. Because custom congestion control can be deployed by any Exit or onion -service that desires better service, we will need to be particularly -careful about how congestion control algorithms interact with rogue -implementations that more aggressively increase their window sizes. -During these adversarial-style experiments, we must verify that cheaters -do not get better service, and that Tor's circuit OOM killer properly -closes circuits that seriously abuse the congestion control algorithm, -as per [SECURITY_ANALYSIS]. This may requiring tuning CircuitEWMAHalfLife, -as well as the oomkiller cutoffs. - -Additionally, we specified that the algorithms maintain previous congestion -window estimates in the event that a circuit goes idle, rather than revert -to slow start. We should experiment with intermittent idle/active clients -to make sure that this behavior is acceptable. +service that desires better service, we will need to be particularly careful +about how congestion control algorithms interact with rogue implementations +that more aggressively increase their window sizes. During these +adversarial-style experiments, we must verify that cheaters do not get +better service, and that Tor's circuit OOM killer properly closes circuits +that seriously abuse the congestion control algorithm, as per +[SECURITY_ANALYSIS]. This may requiring tuning 'circ_max_cell_queue_size', +and 'CircuitPriorityHalflifeMsec'. + +Additionally, we will need to experiment with reducing the cell queue limits +on OR conns before they are blocked (OR_CONN_HIGHWATER), and study the +interaction of that with treating the or conn block as a congestion signal. + +Finally, we will need to monitor our Shadow experiments for evidence of ack +compression, which can cause the BDP estimator to over-estimate the congestion +window. We will instrument our Shadow simulations to alert if they discover +excessive congestion window values, and tweak 'cc_bwe_min' and +'cc_sendme_inc' appropriately. We can set the 'cc_cwnd_max' parameter value +to low values (eg: ~2000 or so) to watch for evidence of this in Shadow, and +log. Similarly, we should watch for evidence that the 'cc_cwnd_min' parameter +value is rarely hit in Shadow, as this indicates that the cwnd may be too +small to measure BDP (for cwnd less than 'cc_sendme_inc'*'cc_bwe_min'). 6.3. Flow Control Algorithm Experiments -We will need to tune the xoff_* consensus parameters to minimize the -amount of edge connection buffering as well as XON/XOFF chatter for -Exits. This can be done in simulation, but will require fine-tuning on -the live network. +Flow control only applies when the edges outside of Tor (SOCKS application, +onion service application, or TCP destination site) are *slower* than Tor's +congestion window. This typically means that the application is either +suspended or reading too slow off its SOCKS connection, or the TCP destination +site itself is bandwidth throttled on its downstream. + +To examine these properties, we will perform live onion service testing, where +curl is used to download a large file. We will test no rate limit, and +verify that XON/XOFF was never sent. We then suspend this download, verify +that an XOFF is sent, and transmission stops. Upon resuming this download, the +download rate should return to normal. We will also use curl's --limit-rate +option, to exercise that the flow control properly measures the drain rate and +limits the buffering in the outbuf, modulo kernel socket and localhost TCP +buffering. + +However, flow control can also get triggered at Exits in a situation where +either TCP fairness issues or Tor's mainloop does not properly allocate +enough capacity to edge uploads, causing them to be rate limited below the +circuit's congestion window, even though the TCP destination actually has +sufficient downstream capacity. + +Exits are also most vulnerable to the buffer bloat caused by such uploads, +since there may be many uploads active at once. + +To study this, we will run shadow simulations. Because Shadow does *not* +rate limit its tgen TCP endpoints, and only rate limits the relays +themselves, if *any* XON/XOFF activity happens in Shadow *at all*, it is +evidence that such fairness issues can ocurr. + +Just in case Shadow does not have sufficient edge activity to trigger such +emergent behavior, when congestion control is enabled on the live network, we +will also need to instrument a live exit, to verify that XON/XOFF is not +happening frequently on it. Relays may also report these statistics in +extra-info descriptor, to help with monitoring the live network conditions, but +this might also require aggregation or minimization. + +If excessive XOFF/XON activity happens at Exits, we will need to investigate +tuning the libevent mainloop to prioritize edge writes over orconn writes. +Additionally, we can lower 'cc_xoff_exit'. Linux Exits can also lower the +'net.ipv[46].tcp_wmem' sysctl value, to reduce the amount of kernel socket +buffering they do on such streams, which will improve XON/XOFF responsiveness +and reduce memory usage. -Additionally, we will need to experiment with reducing the cell queue -limits on OR conns before they are blocked, and study the interaction -of that with treating the or conn block as a congestion signal. +6.4. Performance Metrics [EVALUATION_METRICS] - TODO: We should make the cell queue highwater value into a consensus - parameter in the flow control implementation. +The primary metrics that we will be using to measure the effectiveness +of congestion control in simulation are TTFB/RTT, throughput, and utilization. -Relays may report these statistics in extra-info descriptor, to help with -monitoring the live network conditions, but this might also require -aggregation or minimization. +We will calibrate the Shadow simulator so that it has similar CDFs for all of +these metrics as the live network, without using congestion control. -6.4. Performance Metrics [EVALUATION_METRICS] +Then, we will want to inspect CDFs of these three metrics for various +congestion control algorithms and parameters. + +The live network testing will also spot-check performance characteristics of +a couple algorithm and parameter sets, to ensure we see similar results as +Shadow. -Because congestion control will affect so many aspects of performance, -from throughput to RTT, to load balancing, queue length, overload, and -other failure conditions, the full set of performance metrics will be -required: +On the live network, because congestion control will affect so many aspects of +performance, from throughput to RTT, to load balancing, queue length, +overload, and other failure conditions, the full set of performance metrics +will be required, to check for any emergent behaviors: https://gitlab.torproject.org/legacy/trac/-/wikis/org/roadmaps/CoreTor/PerformanceMetrics We will also need to monitor network health for relay queue lengths, @@ -909,13 +1105,18 @@ These are sorted in order of importance to tune, most important first. use, as an integer. - Range: [0,3] (0=fixed, 1=Westwood, 2=Vegas, 3=NOLA) - Default: 2 - - Tuning Values: 0-3 + - Tuning Values: [2,3] - Tuning Notes: These algorithms need to be tested against percentages of current fixed alg client competition, in Shadow. Their optimal parameter values, and even the optimal algorithm itself, will likely depend upon how much fixed sendme traffic is in competition. See the algorithm-specific parameters for additional tuning notes. + - Shadow Tuning Results: + Westwood exhibited responsiveness problems, drift, and overshoot. + NOLA exhibited ack compression resulting in over-estimating the + BDP. Vegas, when tuned properly, kept queues low and throughput + high, but even. cc_bwe_min: - Description: @@ -923,7 +1124,7 @@ These are sorted in order of importance to tune, most important first. estimate bandwidth (and thus BDP). - Range: [2, 20] - Default: 5 - - Tuning Values: 3-5 + - Tuning Values: 4-10 - Tuning Notes: The lower this value is, the sooner we can get an estimate of the true BDP of a circuit. Low values may lead to massive @@ -935,11 +1136,15 @@ These are sorted in order of importance to tune, most important first. when the congestion window is small. If we need small congestion windows, we should also lower cc_sendme_inc, which will get us more frequent acks with less data. + - Shadow Tuning Results: + Regarless of how high this was set, there were still cases where + queues built up, causing BDP over-estimation. As a result, we disable + use of the BDP estimator, and only use the Vegas CWND estimator. cc_sendme_inc: - Description: Specifies how many cells a SENDME acks - - Range: [1, 5000] - - Default: 50 + - Range: [1, 255] + - Default: 31 - Tuning Values: 25,33,50 - Tuning Notes: Increasing this increases overhead, but also increases BDP @@ -947,14 +1152,22 @@ These are sorted in order of importance to tune, most important first. and the old code sent sendmes at both every 50 cells, and every 100, we can set this as low as 33 to have the same amount of overhead. + - Shadow Tuning Results: + This was optimal at 31-32 cells, which is also the number of + cells that fit in a TLS frame. Much of the rest of Tor has + processing values at 32 cells, as well. + - Consensus Update Notes: + This value MUST only be changed by a factor of 2, every 4 hours. + If greater changes are needed, they MUST be spread out over + multiple consensus updates. cc_cwnd_init: - Description: Initial congestion window for new congestion control Tor clients. This can be set much higher than TCP, since actual TCP to the guard will prevent buffer bloat issues at local routers. - - Range: [100, 10000] - - Default: 500 + - Range: [31, 10000] + - Default: 4*31 - Tuning Values: 150,200,250,500 - Tuning Notes: Higher initial congestion windows allow the algorithms to @@ -962,17 +1175,42 @@ These are sorted in order of importance to tune, most important first. and latency. Ultimately, the ICW should be set to approximately 'cc_bwe_min'*'cc_sendme_inc', but the presence of competing fixed window clients may require higher values. + - Shadow Tuning Results: + Setting this too high caused excessive cell queues at relays. + 4*31 ended up being a sweet spot. + - Consensus Update Notes: + This value must never be set below cc_sendme_inc. cc_cwnd_min: - Description: The minimum allowed cwnd. - - Range: [cc_sendme_inc, 1000] - - Tuning Values: [50, 100, 150] + - Range: [31, 1000] + - Default: 31 + - Tuning Values: [100, 150, 200] - Tuning Notes: If the cwnd falls below cc_sendme_inc, connections can't send enough data to get any acks, and will stall. If it falls below cc_bwe_min*cc_sendme_inc, connections can't use SENDME BDP estimates. Likely we want to set this around cc_bwe_min*cc_sendme_inc, but no lower than cc_sendme_inc. + - Shadow Tuning Results: + We set this at 31 cells, the cc_sendme_inc. + - Consensus Update Notes: + This value must never be set below cc_sendme_inc. + + cc_cwnd_max: + - Description: The maximum allowed cwnd. + - Range: [500, INT32_MAX] + - Default: INT32_MAX + - Tuning Values: [5000, 10000, 20000] + - Tuning Notes: + If cc_bwe_min is set too low, the BDP estimator may over-estimate the + congestion window in the presence of large queues, due to SENDME ack + compression. Once all clients have upgraded to congestion control, + queues large enough to cause ack compression should become rare. This + parameter exists primarily to verify this in Shadow, but we preserve it + as a consensus parameter for emergency use in the live network, as well. + - Shadow Tuning Results: + We kept this at INT32_MAX. circwindow: - Description: Initial congestion window for legacy Tor clients @@ -997,38 +1235,69 @@ These are sorted in order of importance to tune, most important first. only be updated once every cwnd worth of packets. We may find it better to update more frequently, but this is probably unlikely to help a great deal. + - Shadow Tuning Results: + Increasing this during slow start caused overshoot and excessive + queues. Increasing this after slow start was suboptimal for + performance. We keep this at 1. - cc_ewma_cwnd_cnt: + cc_ewma_cwnd_pct: - Description: This specifies the N in N-EWMA smoothing of RTT and BDP - estimation. It allows us to average these values over 1 - or more congestion windows. - - Range: [1, 100] - - Default: 2 - - Tuning Values: [1,2,3] + estimation, as a percent of the number of SENDME acks + in a congestion window. It allows us to average these RTT + values over a percentage of the congestion window, + capped by 'cc_ewma_max' below, and specified in + [N_EWMA_SMOOTHING]. + - Range: [1, 255] + - Default: 50,100 + - Tuning Values: [25,50,100] - Tuning Notes: Smoothing our estimates reduces the effects of ack compression and other ephemeral network hiccups; changing this much is unlikely to have a huge impact on performance. + - Shadow Tuning Results: + Setting this to 50 seemed to reduce cell queues, but this may also + have impacted performance. + + cc_ewma_max: + - Description: This specifies the max N in N_EWMA smoothing of RTT and BDP + estimation. It allows us to place a cap on the N of EWMA + smoothing, as specified in [N_EWMA_SMOOTHING]. + - Range: [2, INT32_MAX] + - Default: 10 + - Tuning Values: [10,20] + - Shadow Tuning Results: + We ended up needing this to make Vegas more responsive to + congestion, to avoid overloading slow relays. Values of 10 or 20 + were best. cc_cwnd_inc: - Description: How much to increment the congestion window by during steady state, every cwnd. - Range: [1, 1000] - - Default: 50 + - Default: 31 - Tuning Values: 25,50,100 - Tuning Notes: We are unlikely to need to tune this much, but it might be worth trying a couple values. + - Shadow Tuning Results: + Increasing this negatively impacted performance. Keeping it at + cc_sendme_inc is best. cc_cwnd_inc_pct_ss: - Description: Percentage of the current congestion window to increment by during slow start, every cwnd. - - Range: [10, 300] + - Range: [1, 500] + - Default: 50 - Tuning Values: 50,100,200 - Tuning Notes: On the current live network, the algorithms tended to exit slow start early, so we did not exercise this much. This may not be the case in Shadow, or once clients upgrade to the new algorithms. + - Shadow Tuning Results: + Setting this above 50 caused excessive queues to build up in + Shadow. This may have been due to imbalances in Shadow client + allocation, though. Values of 50-100 will be explored after + examining Shadow Guard Relay Utilization. cc_bdp_alg: - Description: The BDP estimation algorithm to use. @@ -1036,9 +1305,21 @@ These are sorted in order of importance to tune, most important first. - Default: 7 (Piecewise EWMA) - Tuning Notes: We don't expect to need to tune this. + - Shadow Tuning Results: + We leave this as-is, but disable it in Vegas instead, below. 6.5.2. Westwood parameters + Westwood has runaway conditions. Because the congestion signal threshold of + TOR_WESTWOOD is a function of RTT_max, excessive queuing can cause an + increase in RTT_max. Additionally, if stream activity is constant, but of + a lower bandwidth than the circuit, this will not drive the RTT upwards, + and this can result in a congestion window that continues to increase in the + absence of any other concurrent activity. + + For these reasons, we are unlikely to spend much time deeply investigating + Westwood in Shadow, beyond a simulaton or two to check these behaviors. + cc_westwood_rtt_thresh: - Description: Specifies the cutoff for BOOTLEG_RTT_TOR to deliver @@ -1084,14 +1365,18 @@ These are sorted in order of importance to tune, most important first. 6.5.3. Vegas Parameters - - cc_vegas_alpha: - cc_vegas_beta: - cc_vegas_gamma: + cc_vegas_alpha_{exit,onion,sos,vg,sbws}: + cc_vegas_beta_{exit,onion,sos,vg,sbws}: + cc_vegas_gamma_{exit,onion,sos,vg,sbws}: + cc_vegas_delta_{exit,onion,sos,vg,sbws}: - Description: These parameters govern the number of cells that [TOR_VEGAS] can detect in queue before reacting. - - Range: [1, 1000] - - Defaults: 6*cc_sendme_inc for gamma and beta; 3*cc_sendme_inc for alpha + - Range: [0, 1000] (except delta, which has max of INT32_MAX) + - Defaults: + alpha: path_len*2*31-31 + beta: path_len*2*31 + gamma: path_len*2*31 + delta: path_len*2*31 + 2*31 - Tuning Notes: The amount of queued cells that Vegas should tolerate is heavily dependent upon competing congestion control algorithms. The specified @@ -1100,18 +1385,30 @@ These are sorted in order of importance to tune, most important first. clients using fixed windows is reduced (or circwindow is lowered), we can reduce these parameters, which will result in less overall queuing and congestion on the network. + - Shadow Tuning Results: + We found that the best values for 3-hop Exit circuits was to set + beta and gamma to the size of the outbufs times the number of hops. + This has the effect that Vegas detects congestion and backs off + when this much queue delay is detected. Alpha is set to one TLS + record/sendme_inc below this value. If the queue length is detected + to be below that, we increase the congestion window. We still + need to verify that the path length multiplier still holds for + other types of circuits, specifically onion services. cc_vegas_bdp_mix: - Description: This parameter allows us to specify a weighted percent average between the cwnd BDP estimator and the piecewise estimator. - Range: [0, 100] - - Default: 0 (use 100% Piecewise EWMA) + - Default: 100 (use 100% CWND estimator) - Tuning Notes: The original Vegas literature specified the CWND estimator, but the Piecewise estimator is very likely more suited for our use case. This parameter allows us to average them. We're unlikely to need it. + - Shadow Tuning Results: + Because the BDP estimator had ack compression and over-estimation, + we the CWND estimator. 6.5.4. NOLA Parameters @@ -1129,26 +1426,182 @@ These are sorted in order of importance to tune, most important first. absent any more agressive competition, we do not need to overshoot the BDP estimate. - 6.5.5. Flow Control Parameters - TODO: These may expand, particularly to include cell_queue_highwater + As with previous sections, the parameters in this section are sorted with + the parameters that are most impportant to tune, first. - xoff_client - xoff_mobile - xoff_exit - - Description: Specifies the stream queue size as a percentage of - 'cwnd' at an endpoint before an XOFF is sent. - - Range: [1, 100] - - Default: 5 + These parameters have been tuned using onion services. The defaults are + believed to be good. - xon_client - xon_mobile - xon_exit - - Description: Specifies the how many cells below xoff_* before - an XON is sent from an endpoint. - - Range: [1, 10000000] - - Default: 10000 + cc_xoff_client + cc_xoff_exit + - Description: Specifies the outbuf length, in relay cell multiples, + before we send an XOFF. + - Range: [1, 10000] + - Default: 500 + - Tuning Values: [500, 1000] + - Tuning Notes: + This threshold plus the sender's cwnd must be greater than the + cc_xon_rate value, or a rate cannot be computed. Unfortunately, + unless it is sent, the receiver does not know the cwnd. Therefore, + this value should always be higher than cc_xon_rate minus + 'cc_cwnd_min' (100) minus the xon threshhold value (0). + + cc_xon_rate + - Description: Specifies how many full packed cells of bytes must arrive + before we can compute a rate, as well as how often we can + send XONs. + - Range: [1, 5000] + - Default: 500 + - Tuning Values: [500, 1000] + - Tuning Notes: + Setting this high will prevent excessive XONs, as well as reduce + side channel potential, but it will delay response to queuing. + and will hinder our ability to detect rate changes. However, low + values will also reduce our ability to accurately measure drain + rate. This value should always be lower than 'cc_xoff_*' + + 'cc_cwnd_min', so that a rate can be computed solely from the outbuf + plus inflight data. + + cc_xon_change_pct + - Description: Specifies how much the edge drain rate can change before + we send another advisory cell. + - Range: [1, 99] + - Default: 25 + - Tuning values: [25, 50, 75] + - Tuning Notes: + Sending advisory updates due to a rate change may help us avoid + hitting the XOFF limit, but it may also not help much unless we + are already above the advise limit. + + cc_xon_ewma_cnt + - Description: Specifies the N in the N_EWMA of rates. + - Range: [2, 100] + - Default: 2 + - Tuning values: [2, 3, 5] + - Tuning Notes: + Setting this higher will smooth over changes in the rate field, + and thus avoid XONs, but will reduce our reactivity to rate changes. + + +6.5.6. External Performance Parameters to Tune + + The following parameters are from other areas of Tor, but tuning them + will improve congestion control performance. They are again sorted + by most important to tune, first. + + cbtquantile + - Description: Specifies the percentage cutoff for the circuit build + timeout mechanism. + - Range: [60, 80] + - Default: 80 + - Tuning Values: [70, 75, 80] + - Tuning Notes: + The circuit build timeout code causes Tor to use only the fastest + 'cbtquantile' percentage of paths to build through the network. + Lowering this value will help avoid congested relays, and improve + latency. + + CircuitPriorityHalflifeMsec + - Description: The CircEWMA half-life specifies the time period after + which the cell count on a circuit is halved. This allows + circuits to regain their priority if they stop being bursty. + - Range: [1, INT32_MAX] + - Default: 30000 + - Tuning Values: [5000, 15000, 30000, 60000] + - Tuning Notes: + When we last tuned this, it was before KIST[31], so previous values may + have little relevance to today. According to the CircEWMA paper[30], values + that are too small will fail to differentiate bulk circuits from interactive + ones, and values that are too large will allow new bulk circuits to keep + priority over interactive circuits for too long. The paper does say + that the system was not overly sensitive to specific values, though. + + CircuitPriorityTickSecs + - Description: This specifies how often in seconds we readjust circuit + priority based on their EWMA. + - Range: [1, 600] + - Default: 10 + - Tuning Values: [1, 5, 10] + - Tuning Notes: + Even less is known about the optimal value for this parameter. At a + guess, it should be more often than the half-life. Changing it also + influences the half-life decay, though, at least according to the + CircEWMA paper[30]. + + KISTSchedRunInterval + - If 0, KIST is disabled. (We should also test KIST disabled) + + +6.5.7. External Memory Reduction Parameters to Tune + + The following parameters are from other areas of Tor, but tuning them + will reduce memory utilization in relays. They are again sorted by most + important to tune, first. + + circ_max_cell_queue_size + - Description: Specifies the minimum number of cells that are allowed + to accumulate in a relay queue before closing the circuit. + - Range: [1000, INT32_MAX] + - Default: 50000 + - Tuning Values: [1000, 2500, 5000] + - Tuning Notes: + Once all clients have upgraded to congestion control, relay circuit + queues should be minimized. We should minimize this value, as any + high amounts of queueing is a likely violator of the algorithm. + + cellq_low + cellq_high + - Description: Specifies the number of cells that can build up in + a circuit's queue for delivery onto a channel (from edges) + before we either block or unblock reading from streams + attached to that circuit. + - Range: [1, 1000] + - Default: low=10, high=256 + - Tuning Values: low=[0, 2, 4, 8]; high=[16, 32, 64] + - Tuning Notes: + When data arrives from edges into Tor, it gets packaged up into cells + and then delivered to the cell queue, and from there is dequeued and + sent on a channel. If the channel has blocked (see below params), then + this queue grows until the high watermark, at which point Tor stops + reading on all edges associated with a circuit, and a congestion + signal is delivered to that circuit. At 256 cells, this is ~130k of + data for *every* circuit, which is far more than Tor can write in a + channel outbuf. Lowering this will reduce latency, reduce memory + usage, and improve responsiveness to congestion. However, if it is + too low, we may incur additional mainloop invocations, which are + expensive. We will need to trace or monitor epoll() invocations in + Shadow or on a Tor exit to verify that low values do not lead to + more mainloop invocations. + - Shadow Tuning Results: + After extensive tuning, it turned out that the defaults were optimal + in terms of throughput. + + orconn_high + orconn_low + - Description: Specifies the number of bytes that can be held in an + orconn's outbuf before we block or unblock the orconn. + - Range: [509, INT32_MAX] + - Default: low=16k, high=32k + - Tuning Notes: + When the orconn's outbuf is above the high watermark, cells begin + to accumulate in the cell queue as opposed to being added to the + outbuf. It may make sense to lower this to be more in-line with the + cellq values above. Also note that the low watermark is only used by + the vanilla scheduler, so tuning it may be relevant when we test with + KIST disabled. Just like the cell queue, if this is set lower, congestion + signals will arrive sooner to congestion control when orconns become + blocked, and less memory will occupy queues. It will also reduce latency. + Note that if this is too low, we may not fill TLS records, and we may + incur excessive epoll()/mainloop invocations. Tuning this is likely + less beneficial than tuning the above cell_queue, unless KIST is + disabled. + + MaxMemInQueues + - Should be possible to set much lower, similarly to help with + OOM conditions due to protocol violation. Unfortunately, this + is just a torrc, and a bad one at that. 7. Protocol format specifications [PROTOCOL_SPEC] @@ -1317,85 +1770,96 @@ also be used as a side channel. So we must limit its use to a couple of cells per circuit, at most. https://blog.torproject.org/tor-security-advisory-relay-early-traffic-confirmation-attack -9. Onion Services + +9. Onion Service Negotiation [ONION_NEGOTIATION] Onion service requires us to advertise the protocol version and congestion control parameters in a different way since the end points do not know each -other like a client knows all the relays and what they support. +other like a client knows all the relays and what they support. Additionally, +we cannot use ntorv3 for onion service negotiation, because it is not +supported at all rendezvous and introduction points. To address this, this is done in two parts. First, the service needs to -advertise to the world that it supports congestion control. This is done -through a new line in the descriptor, see section 9.1 below. +advertise to the world that it supports congestion control, and its view of +the current cc_sendme_inc consensus parameter. This is done through a new +line in the onion service descriptor, see section 9.1 below. Second, the client needs to inform the service that it wants to use congestion -control on the rendezvous circuit and with wich parameters. This is done -through the INTRODUCE cell as an extension, see section 9.2 below. +control on the rendezvous circuit. This is done through the INTRODUCE cell as +an extension, see section 9.2 below. -9.1. Descriptor +9.1. Onion Service Descriptor -We propose to add a new line to advertise the flow control protocol version: +We propose to add a new line to advertise the flow control protocol version, +in the encrypted section of the onion service descriptor: - "flow-control" SP version-number NL + "flow-control" SP version-range SP sendme-inc NL - The "version-number" value is the same as the protocol version FlowCtrl - that relay advertises which is defined earlier in this proposal. Current - value can only be "2". + The "version-range" value is the same as the protocol version FlowCtrl + that relay advertises which is defined earlier in this proposal. The + current value is "1-2". -Clients that are able to parse this line and know the protocol version can then -send in the INTRODUCE1 cell congestion control parameters that they would like -to use which is detailed in the next section. + The "sendme-inc" value comes from the service's current cc_sendme_inc + consensus parameter. -This line MUST be removed from the descriptor if the consensus disables -congestion control by setting "cc_alg=0". In other words, a service should only -advertise its flow control version if congestion control is enabled network -wide. +Clients MUST ignore additional unknown versions in "version-range", and MUST +ignore any additional values on this line. -9.2 INTRODUCE cell extension +Clients SHOULD use the highest value in "version-range" to govern their +protocol choice for "FlowCtrl" and INTRODUCE cell format, as per Section 9.2 +below. -We propose a new extension to the INTRODUCE cell which can be used to send -congestion control parameters down to the service. It is important to mention -that this is an extension to be used in the encrypted setion of the cell and -not its readable section by the introduction point. +If clients do not support any of the versions in "version-range", they SHOULD +reject the descriptor. (They MAY choose to ignore this line instead, but doing +so means using the old fixed-window SENDME flow control, which will likely be +bad for the network). -If used, it needs to be encoded within the N_EXTENSIONS field of the ENCRYPTED -section of the INTRODUCE1 cell defined in rend-spec-v3.txt section 3.3. The -content is defined as follow: +Clients that are able to parse this line and know the protocol version +MUST validate that the "sendme-inc" value is within a multiple of 2 of the +"cc_sendme_inc" in the consensus that they see. If "sendme-inc" is not within +range, they MUST reject the descriptor. - EXT_FIELD_TYPE: +If their consensus also lists a non-zero "cc_alg", they MAY then send in the +INTRODUCE1 cell congestion control request extention field, which is detailed +in the next section. - [01] -- Congestion Control Parameters. +A service should only advertise its flow control version if congestion control is +enabled. It MUST remove this line if congestion control is disabled. - If this flag is set, the extension should be used by the service to learn - what are the congestion control parameters to use on the rendezvous - circuit. +If the service observes a change in 'cc_sendme_inc' consensus parameter since +it last published its descriptor, it MUST immediately close its introduction +points, and publish a new descriptor with the new "sendme-inc" value. The +additional step of closing the introduction points ensures that no clients +arrive using a cached descriptor, with the old "sendme-inc" value. - EXT_FIELD content format is: +9.2 INTRODUCE cell extension - N_PARAMS [1 byte] - N_PARAMS times: - PARAM_TYPE [1 byte] - PARAM_VALUE [8 byte] +We propose a new extension to the INTRODUCE cell which can be used to send +congestion control parameters down to the service. It is important to mention +that this is an extension to be used in the encrypted setion of the cell and +not its readable section by the introduction point. - The PARAM_TYPE possible values are: +If used, it needs to be encoded within the ENCRYPTED section of the INTRODUCE1 +cell defined in rend-spec-v3.txt section 3.3. The content is defined as follow: - [01] -- Newest protocol version supported - The newest protocol version that the client supports. + EXT_FIELD_TYPE: - [02] -- SENDME increment - The initial SENDME increment that should be used by both end points - when using congestion control. + [01] -- Congestion Control Request. - The PARAM_VALUE size is 8 bytes in order to accomodate 64bit values. It - MUST match the specified limits for the following PARAM_TYPE: +This field is has zero payload length. Its presence signifies that the client wants to +use congestion control. The client MUST NOT set this field, or use +ntorv3, if the service did not list "2" in the "FlowCtrl" line in the +descriptor. The client SHOULD NOT provide this field if the consensus parameter +'cc_alg' is 0. - [01] -- Min: 2, Max: 255 - [02] -- Min: 1, Max: 5000 (same as "cc_sendme_inc") +The service MUST ignore any unknown fields. 9.3 Protocol Flow First, the client reads the "flow-control" line in the descriptor and gets the -maximum value from what it supports and the service supports. As an example, if -the client supports 2-3-4 and the service supports 2-3, then 3 is chosen. +maximum value from that line's "version-range" and the service supports. As an +example, if the client supports 2-3-4 and the service supports 2-3, then 3 is +chosen. It then sends that value along its desired cc_sendme_inc value in the INTRODUCE1 cell in the extension. @@ -1406,7 +1870,7 @@ then applied to the rendezvous circuit. 9.4 Circuit Behavior -If the extension is not found in the cell, the service MUST not use congestion +If the extension is not found in the cell, the service MUST NOT use congestion control on the rendezvous circuit. Any invalid values received in the extension should result in closing the @@ -1424,15 +1888,159 @@ everyone looks the same again. The new extension is located in the encrypted part of the INTRODUCE1 cell and thus the introduction point can't learn its content. -10. Acknowledgements + +10. Exit negotiation [EXIT_NEGOTIATION] + +Similar to onion services, clients and exits will need to negotiate the +decision to use congestion control, as well as a common value for +'cc_sendme_inc', for a given circuit. + +10.1. When to negotiate + +Clients decide to initiate a negotiation attempt for a circuit if the +consensus lists a non-zero 'cc_alg' parameter value, and the protover line +for their chosen exit includes a value of 2 in the "FlowCtrl" field. + +If the FlowCtrl=2 subprotocol is absent, a client MUST NOT attempt negotiation. + +If 'cc_alg' is absent or zero, a client SHOULD NOT attempt +negotiation, or use ntorv3. + +If the protover and consensus conditions are met, clients SHOULD negotiate +with the Exit if the circuit is to be used for exit stream activity. Clients +SHOULD NOT negotiate congestion control for one-hop circuits, or internal +circuits. + +10.2. What to negotiate + +Clients and exits need not agree on a specific congestion control algorithm, +or any aspects of its behavior. Each endpoint's management of its congestion +window is independent. However, because the new algorithms no longer use +stream SENDMEs or fixed window sizes, they cannot be used with an endpoint +expecting the old behavior. + +Additionally, each endpoint must agree on the the SENDME increment rate, in +order to synchronize SENDME authentication and pacing. + +For this reason, negotiation needs to establish a boolean: "use congestion +control", and an integer value for SENDME increment. + +No other parameters need to be negotiated. + +10.3. How to negotiate + +Negotiation is performed by sending an ntorv3 onionskin, as specified in +Proposal 332, to the Exit node. The encrypted payload contents from the +clients are encoded as an extension field, as in the onion service INTRO1 +cell: + + EXT_FIELD_TYPE: + + [01] -- Congestion Control Request. + +As in the INTRO1 extension field, this field is has zero payload length. + +Its presence signifies that the client wants to use congestion control. +Again, the client MUST NOT set this field, or use ntorv3, if this exit did not +list "2" in the "FlowCtrl" version line. The client SHOULD NOT set this to 1 +if the consensus parameter 'cc_alg' is 0. + +The Exit MUST ignore any additional unknown extension fields. + +The server's encrypted ntorv3 reply payload is encoded as: + + EXT_FIELD_TYPE: + + [02] -- Congestion Control Response. + + If this flag is set, the extension should be used by the service to learn + what are the congestion control parameters to use on the rendezvous + circuit. + + EXT_FIELD content payload is a single byte: + + sendme_inc [1 byte] + +The Exit MUST provide its current view of 'cc_sendme_inc' in this payload if it +observes a non-zero 'cc_alg' consensus parameter. Exits SHOULD only include +this field once. + +The client MUST use the FIRST such field value, and ignore any duplicate field +specifiers. The client MUST ignore any unknown additional fields. + +10.5. Client checks + +The client MUST reject any ntorv3 replies for non-ntorv3 onionskins. + +The client MUST reject an ntorv3 reply with field EXT_FIELD_TYPE=02, if the +client did not include EXT_FIELD_TYPE=01 in its handshake. + +The client SHOULD reject a sendme_inc field value that differs from the +current 'cc_sendme_inc' consensus parameter by more than a factor of 2, in +either direction. + +If a client rejects a handshake, it MUST close the circuit. + +10.6. Managing consenus updates + +The pedantic reader will note that a rogue consensus can cause all clients +to decide to close circuits by changing 'cc_sendme_inc' by a large margin. + +As a matter of policy, the directory authorities MUST NOT change +'cc_sendme_inc' by more than a factor of two (2), within a four (4) hour +window, for this reason. + +In Shadow simulation, the optimal 'cc_sendme_inc' value to be ~31 cells, or +one (1) TLS record worth of cells. We do not expect to change this value +significantly. + + +11. Acknowledgements Immense thanks to Toke Høiland-Jørgensen for considerable input into all aspects of the TCP congestion control background material for this proposal, as well as review of our versions of the algorithms. +12. Glossary [GLOSSARY] + +ACK - Acknowledgment. In congestion control, this is a type of packet that +signals that the endpoint received a packet or packet set. In Tor, ACKs are +called SENDMEs. + +BDP - Bandwidth Delay Product. This is the quantity of bytes that are actively +in transit on a path at any given time. Typically, this does not count packets +waiting in queues. It is essentially RTT*BWE - queue_delay. + +BWE - BandWidth Estimate. This is the estimated throughput on a path. + +CWND - Congestion WiNDow. This is the total number of packets that are allowed +to be "outstanding" (aka not ACKed) on a path at any given time. An ideal +congestion control algorithm sets CWND=BDP. -11. [CITATIONS] +EWMA - Exponential Weighted Moving Average. This is a mechanism for smoothing +out high-frequency changes in a value, due to temporary effects. + +ICW - Initial Congestion Window. This is the initial value of the congestion +window at the start of a connection. + +RTT - Round Trip Time. This is the time it takes for one endpoint to send a +packet to the other endpoint, and get a response. + +SS - Slow Start. This is the initial phase of most congestion control +algorithms. Despite the name, it is an exponential growth phase, to quickly +increase the congestion window from the ICW value up the path BDP. After Slow +Start, changes to the congestion window are linear. + +XOFF - Transmitter Off. In flow control, XOFF means that the receiver is +receiving data too fast and is beginning to queue. It is sent to tell the +sender to stop sending. + +XON - Transmitter On. In flow control, XON means that the receiver is ready to +receive more data. It is sent to tell the sender to resume sending. + + +13. [CITATIONS] 1. Options for Congestion Control in Tor-Like Networks. https://lists.torproject.org/pipermail/tor-dev/2020-January/014140.html @@ -1514,3 +2122,14 @@ as well as review of our versions of the algorithms. 27. Exponentially Weighted Moving Average https://corporatefinanceinstitute.com/resources/knowledge/trading-investing/exponentially-weighted-moving-average-ewma/ + +28. Dropping on the Edge + https://www.petsymposium.org/2018/files/papers/issue2/popets-2018-0011.pdf + +29. https://github.com/mikeperry-tor/vanguards/blob/master/README_TECHNICAL.md#the-bandguards-subsystem + +30. An Improved Algorithm for Tor Circuit Scheduling. + https://www.cypherpunks.ca/~iang/pubs/ewma-ccs.pdf + +31. KIST: Kernel-Informed Socket Transport for Tor + https://matt.traudt.xyz/static/papers/kist-tops2018.pdf diff --git a/proposals/328-relay-overload-report.md b/proposals/328-relay-overload-report.md index 8bcbaa3..5901b93 100644 --- a/proposals/328-relay-overload-report.md +++ b/proposals/328-relay-overload-report.md @@ -3,7 +3,7 @@ Filename: 328-relay-overload-report.md Title: Make Relays Report When They Are Overloaded Author: David Goulet, Mike Perry Created: November 3rd 2020 -Status: Draft +Status: Closed ``` # 0. Introduction @@ -25,8 +25,11 @@ possibly misbehaving or under DDoS attack. We propose that relays start collecting several metrics (see section 2) reflecting their loads from different component of tor. -Then, we propose that 3 new lines be added to the extra-info document (see -dir-spec.txt, section 2.1.2) if only the overload case arises. +Then, we propose that 1 new line be added to the server descriptor document +(see dir-spec.txt, section 2.1.1) for the general overload case. + +And 2 new lines to the extra-info document (see dir-spec.txt, section 2.1.2) +for more specific overload cases. The following describes a series of metrics to collect but more might come in the future and thus this is not an exhaustive list. @@ -38,13 +41,23 @@ state" which can be one or many of the following load metrics: - Any OOM invocation due to memory pressure - Any ntor onionskins are dropped + [Removed in tor-0.4.6.11 and 0.4.7.5-alpha] + - A certain ratio of ntor onionskins dropped. + [Added in tor-0.4.6.11 and 0.4.7.5-alpha] - TCP port exhaustion - - DNS timeout reached + - DNS timeout reached (X% of timeouts over Y seconds). + [Removed in tor-0.4.7.3-alpha] - CPU utilization of Tor's mainloop CPU core above 90% for 60 sec + [Never implemented] - Control port overload (too many messages queued) + [Never implemented] -The format of the overloaded line added in the extra-info document is as -follows: +For DNS timeouts, the X and Y are consensus parameters +(overload_dns_timeout_scale_percent and overload_dns_timeout_period_secs) +defined in param-spec.txt. + +The format of the overloaded line added in the server descriptor document is +as follows: ``` "overload-general" SP version SP YYYY-MM-DD HH:MM:SS NL @@ -64,9 +77,7 @@ this 72 hour period restarts. The 'version' field is set to '1' for the initial implementation of this proposal which includes all the above overload metrics except from the CPU and -control port overload. The first version also uses a primitive logic for -detecting DNS timeouts (only if libevent failed a set of 3 DNS requests/retries -in a row). +control port overload. # 1.2. Token bucket size @@ -75,6 +86,9 @@ descriptor, as well as the number of times these limits were reached, for read and write, in the past 24 hours starting at the provided timestamp rounded down to the hour. +The format of this overload line added in the extra-info document is as +follows: + ``` "overload-ratelimits" SP version SP YYYY-MM-DD SP HH:MM:SS SP rate-limit SP burst-limit @@ -100,7 +114,8 @@ Not having enough file descriptors in this day of age is really a misconfiguration or a too old operation system. That way, we can very quickly notice which relay has a value too small and we can notify them. -This should be published in this format: +The format of this overload line added in the extra-info document is as +follows: ``` "overload-fd-exhausted" SP version YYYY-MM-DD HH:MM:SS NL @@ -121,10 +136,7 @@ proposal which detects fd exhaustion only when a socket open fails. This section proposes a series of metrics that should be collected and reported to the MetricsPort. The Prometheus format (only one supported for -now) is described for each metrics but each of them are prefixed with the -following in order to have a proper namespace for "load" events: - -`tor_load_` +now) is described for each metrics. ## 2.1 Out-Of-Memory (OOM) Invocation @@ -134,7 +146,7 @@ so any invocation of the OOM should be reported. ``` # HELP Total number of bytes the OOM has cleaned up # TYPE counter -tor_load_oom_bytes_total{<LABEL>} <VALUE> +tor_relay_load_oom_bytes_total{<LABEL>} <VALUE> ``` Running counter of how many bytes were cleaned up by the OOM for a tor @@ -157,7 +169,7 @@ thus one can provide a total processed versus dropped ratio: ``` # HELP Total number of onionskins # TYPE counter -tor_load_onionskin_total{<LABEL>} <NUM> +tor_relay_load_onionskins_total{<LABEL>} <NUM> ``` Possible LABELs are: @@ -173,14 +185,14 @@ opened file descriptors. In Tor's use case, this is mostly sockets. File descriptors should be reported as follow: ``` -# HELP Total number of file descriptors +# HELP Total number of sockets # TYPE gauge -tor_load_fd_total{<LABEL>} <NUM> +tor_relay_load_socket_total{<LABEL>} <NUM> ``` Possible LABELs are: - - `state=total`: Maximum number of file descriptors allowed open - - `state=opened`: How many file descriptors are opened. + - <none>: How many available sockets. + - `state=opened`: How many sockets are opened. Note: since tor does track that value in order to reserve a block for critical port such as the Control Port, that value can easily be exported. @@ -192,15 +204,11 @@ open more outbound sockets, that is an overloaded state. It should be reported: ``` -# HELP Total number of opened outbound connections. +# HELP Total number of times we ran out of TCP ports # TYPE gauge -tor_load_socket_total{<LABEL>} <NUM> +tor_relay_load_tcp_exhaustion_total <NUM> ``` -Possible LABELs are: - - `state=total`: Maximum number of sockets allowed open - - `state=opened`: How sockets are opened. - ## 2.5 Connection Bucket Limit Rate limited connections track bandwidth using a bucket system. Once the @@ -210,7 +218,7 @@ second later. Once that is hit, it should be reported: ``` # HELP Total number of global connection bucket limit reached # TYPE counter -tor_load_global_rate_limit_reached_total{<LABEL>} <NUM> +tor_relay_load_global_rate_limit_reached_total{<LABEL>} <NUM> ``` Possible LABELs are: diff --git a/proposals/332-ntor-v3-with-extra-data.md b/proposals/332-ntor-v3-with-extra-data.md index 207bc07..b76a451 100644 --- a/proposals/332-ntor-v3-with-extra-data.md +++ b/proposals/332-ntor-v3-with-extra-data.md @@ -3,7 +3,7 @@ Filename: 332-ntor-v3-with-extra-data.md Title: Ntor protocol with extra data, version 3. Author: Nick Mathewson Created: 12 July 2021 -Status: Open +Status: Finished ``` # Overview @@ -338,20 +338,30 @@ We use the following meta-encoding for the contents of client and server messages. [Any number of times]: - TYPE [one byte] - LEN [one byte] - BODY [LEN bytes] + EXTENSION + EXT_FIELD_TYPE [one byte] + EXT_FIELD_LEN [one byte] + EXT_FIELD [EXT_FIELD_LEN bytes] -We do not specify specific TYPE semantics here; we leave those for -other proposals. +(`EXT_FIELD_LEN` may be zero, in which case EXT_FIELD is absent.) All parties MUST reject messages that are not well-formed per the rules above. -To avoid partitioning, clients MUST reject messages with TYPEs that -they do not recognize. (Therefore, whenever we specify a new server -message TYPE, we must say that it can only be included if the client -signals that it understands it.) +We do not specify specific TYPE semantics here; we leave those for +other proposals and specifications. + +Parties MUST ignore extensions with `EXT_FIELD_TYPE` bodies they do not +recognize. + +Unless otherwise specified in the documentation for an extension type: +* Each extension type SHOULD be sent only once in a message. +* Parties MUST ignore any occurrences all occurrences of an extension + with a given type after the first such occurrence. +* Extensions SHOULD be sent in numerically ascending order by type. + +(The above extension sorting and multiplicity rules are only defaults; +they may be overridden in the description of individual extensions.) # A.3 How much space is available? diff --git a/proposals/333-vanguards-lite.md b/proposals/333-vanguards-lite.md index 998bb4a..5e62b03 100644 --- a/proposals/333-vanguards-lite.md +++ b/proposals/333-vanguards-lite.md @@ -3,7 +3,8 @@ Filename: 333-vanguards-lite.md Title: Vanguards lite Author: George Kadianakis, Mike Perry Created: 2021-05-20 -Status: Draft +Status: Finished +Implemented-In: 0.4.7.1-alpha ``` # 0. Introduction & Motivation diff --git a/proposals/334-middle-only-flag.txt b/proposals/334-middle-only-flag.txt index ed5de42..823e927 100644 --- a/proposals/334-middle-only-flag.txt +++ b/proposals/334-middle-only-flag.txt @@ -2,7 +2,8 @@ Filename: 334-middle-only-flag.txt Title: A Directory Authority Flag To Mark Relays As Middle-only Author: Neel Chauhan Created: 2021-09-07 -Status: Open +Status: Superseded +Superseded-by: 335-middle-only-redux.md 1. Introduction diff --git a/proposals/335-middle-only-redux.md b/proposals/335-middle-only-redux.md new file mode 100644 index 0000000..b308e76 --- /dev/null +++ b/proposals/335-middle-only-redux.md @@ -0,0 +1,78 @@ +``` +Filename: 335-middle-only-redux.md +Title: An authority-only design for MiddleOnly +Author: Nick Mathewson +Created: 2021-10-08 +Status: Closed +Implemented-In: 0.4.7.2-alpha +``` + +# Introduction + +This proposal describes an alternative design for a `MiddleOnly` +flag. Instead of making changes at the client level, it adds a +little increased complexity at the directory authority's voting +process. In return for that complexity, this design will work +without additional changes required from Tor clients. + +For additional motivation and discussion see proposal 334 by Neel +Chauhan, and the related discussions on tor-dev. + +# Protocol changes + +## Generating votes + +When voting for a relay with the `MiddleOnly` flag, an authority +should vote _for_ all flags indicating that a relay is unusable for a +particular purpose, and _against_ all flags indicating that the relay +is usable for a particular position. + +Specifically, these flags SHOULD be set in a vote whenever +`MiddleOnly` is present, and only when the authority is configured +to vote on the `BadExit` flag. + + * `BadExit` + +And these flags SHOULD be cleared in a vote whenever `MiddleOnly` is +present. + + * `Exit` + * `Guard` + * `HSDir` + * `V2Dir` + +## Computing a consensus + +This proposal will introduce a new consensus method (probably 32). +Whenever computing a consensus using that consensus method or later, +authorities post-process the set of flags that appear in the +consensus after flag voting takes place, by applying the same rule +as above. + +That is, with this consensus method, the authorities first compute +the presence or absence of each flag on each relay as usual. Then, +if the `MiddleOnly` flag is present, the authorities set `BadExit`, +and clear `Exit`, `Guard`, `HSDir`, and `V2Dir`. + +# Configuring authorities + +We'll need a means for configuring which relays will receive this +flag. For now, we'll just reuse the same mechanism as +`AuthDirReject` and `AuthDirBadExit`: a set of torrc configuration +lines listing relays by address. We'll call this +`AuthDirMiddleOnly`. + +We'll also add an `AuthDirListsMiddleOnly` option to turn on or off +voting on this option at all. + +# Notes on safety and migration + +Under this design, the MiddleOnly option becomes useful immediately, +since authorities that use it will stop voting for certain +additional options for MiddleOnly relays without waiting for the +other authorities. + +We don't need to worry about a single authority setting MiddleOnly +unilaterally for all relays, since the MiddleOnly flag will have no +special effect until most authorities have upgraded to the new +consensus method. diff --git a/proposals/336-randomize-guard-retries.md b/proposals/336-randomize-guard-retries.md new file mode 100644 index 0000000..05cf1c3 --- /dev/null +++ b/proposals/336-randomize-guard-retries.md @@ -0,0 +1,87 @@ +``` +Filename: 336-randomize-guard-retries.md +Title: Randomized schedule for guard retries +Author: Nick Mathewson +Created: 2021-10-22 +Status: Accepted +``` + +# Introduction + +When we notice that a guard isn't working, we don't mark it as retriable +until a certain interval has passed. Currently, these intervals are +fixed, as described in the documentation for `GUARDS_RETRY_SCHED` in +`guard-spec` appendix A.1. Here we propose using a randomized retry +interval instead, based on the same decorrelated-jitter algorithm we use +for directory retries. + +The upside of this approach is that it makes our behavior in +the presence of an unreliable network a bit harder for an attacker to +predict. It also means that if a guard goes down for a while, its +clients will notice that it is up at staggered times, rather than +probing it in lock-step. + +The downside of this approach is that we can, if we get unlucky +enough, completely fail to notice that a preferred guard is online when +we would otherwise have noticed sooner. + +Note that when a guard is marked retriable, it isn't necessarily retried +immediately. Instead, its status is changed from "Unreachable" to +"Unknown", which will cause it to get retried. + +For reference, our previous schedule was: + +``` + {param:PRIMARY_GUARDS_RETRY_SCHED} + -- every 10 minutes for the first six hours, + -- every 90 minutes for the next 90 hours, + -- every 4 hours for the next 3 days, + -- every 9 hours thereafter. + + {param:GUARDS_RETRY_SCHED} -- + -- every hour for the first six hours, + -- every 4 hours for the next 90 hours, + -- every 18 hours for the next 3 days, + -- every 36 hours thereafter. +``` + +# The new algorithm + +We re-use the decorrelated-jitter algorithm from `dir-spec` section 5.5. +The specific formula used to compute the 'i+1'th delay is: + +``` +Delay_{i+1} = MIN(cap, random_between(lower_bound, upper_bound)) +where upper_bound = MAX(lower_bound+1, Delay_i * 3) + lower_bound = MAX(1, base_delay). +``` + +For primary guards, we set base_delay to 30 seconds and cap to 6 hours. + +For non-primary guards, we set base_delay to 10 minutes and cap to 36 +hours. + +(These parameters were selected by simulating the results of using them +until they looked "a bit more aggressive" than the current algorithm, but +not too much.) + +The average behavior for the new primary schedule is: + +``` +First 1.0 hours: 10.14283 attempts. (Avg delay 4m 47.41s) +First 6.0 hours: 19.02377 attempts. (Avg delay 15m 36.95s) +First 96.0 hours: 56.11173 attempts. (Avg delay 1h 40m 3.13s) +First 168.0 hours: 83.67091 attempts. (Avg delay 1h 58m 43.16s) +Steady state: 2h 36m 44.63s between attempts. +``` + +The average behavior for the new non-primary schedule is: + +``` +First 1.0 hours: 3.08069 attempts. (Avg delay 14m 26.08s) +First 6.0 hours: 8.1473 attempts. (Avg delay 35m 25.27s) +First 96.0 hours: 22.57442 attempts. (Avg delay 3h 49m 32.16s) +First 168.0 hours: 29.02873 attempts. (Avg delay 5h 27m 2.36s) +Steady state: 11h 15m 28.47s between attempts. +``` + diff --git a/proposals/337-simpler-guard-usability.md b/proposals/337-simpler-guard-usability.md new file mode 100644 index 0000000..898c6e0 --- /dev/null +++ b/proposals/337-simpler-guard-usability.md @@ -0,0 +1,138 @@ +``` +Filename: 337-simpler-guard-usability.md +Title: A simpler way to decide, "Is this guard usable?" +Author: Nick Mathewson +Created: 2021-10-22 +Status: Accepted +``` + +# Introduction + +The current `guard-spec` describes a mechanism for how to behave when +our primary guards are unreachable, and we don't know which other guards +are reachable. This proposal describes a simpler method, currently +implemented in [Arti](https://gitlab.torproject.org/tpo/core/arti/). + +(Note that this method might not actually give different results: its +only advantage is that it is much simpler to implement.) + +## The task at hand + +For illustration, we'll assume that our primary guards are P1, P2, and +P3, and our subsequent guards (in preference order) are G1, G2, G3, and +so on. The status of each guard is Reachable (we think we can connect +to it), Unreachable (we think it's down), or Unknown (we haven't tried +it recently). + +The question becomes, "What should we do when P1, P2, and P3 are +Unreachable, and G1, G2, ... are all Unknown"? + +In this circumstance, we _could_ say that we only build circuits to G1, +wait for them to succeed or fail, and only try G2 if we see that the +circuits to G1 have failed completely. But that delays in the case that +G1 is down. + +Instead, the first time we get a circuit request, we try to build one +circuit to G1. On the next circuit request, if the circuit to G1 isn't +done yet, we launch a circuit to G2 instead. The next request (if the +G1 and G2 circuits are still pending) goes to G3, and so on. But +(here's the critical part!) we don't actually _use_ the circuit to G2 +unless the circuit to G1 fails, and we don't actually _use_ the circuit +to G3 unless the circuits to G1 and G2 both fail. + +This approach causes Tor clients to check the status of multiple +possible guards in parallel, while not actually _using_ any guard until +we're sure that all the guards we'd rather use are down. + +## The current algorithm and its drawbacks + +For the current algorithm, see `guard-spec` section 4.9: circuits are +exploratory if they are not using a primary guard. If such an +exploratory circuit is `waiting_for_better_guard`, then we advance it +(or not) depending on the status of all other _circuits_ using guards that +we'd rather be using. + +In other words, the current algorithm is described in terms of actions +to take with given circuits. + +For Arti (and for other modular Tor implementations), however, this +algorithm is a bit of a pain: it introduces dependencies between the +guard code and the circuit handling code, requiring each one to mess +with the other. + +# Proposal + +I suggest that we describe an alternative algorithm for handing circuits +to non-primary guards, to be used in preference to the current +algorithm. Unlike the existing approach, it isolates the guard logic a +bit better from the circuit logic. + +## Handling exploratory circuits + +When all primary guards are Unreachable, we need to try non-primary +guards. We select the first such guard (in preference order) that is +neither Unreachable nor Pending. Whenever we give out such a guard, if +the guard's status is Unknown, then we call that guard "Pending" until +the attempt to use it succeeds or fails. We remember when the guard +became Pending. + +> Aside: None of the above is a change from our existing specification. + +After completing a circuit, the implementation must check whether +its guard is usable. A guard is usable according to these rules: + +Primary guards are always usable. + +Non-primary guards are usable for a given circuit if every guard earlier +in the preference list is either unsuitable for that circuit +(e.g. because of family restrictions), or marked as Unreachable, or has +been pending for at least `{NONPRIMARY_GUARD_CONNECT_TIMEOUT}`. + +Non-primary guards are unusable for a given circuit if some guard earlier +in the preference list is suitable for the circuit _and_ Reachable. + +Non-primary guards are unusable if they have not become usable after +`{NONPRIMARY_GUARD_IDLE_TIMEOUT}` seconds. + +If a circuit's guard is neither usable nor unusable immediately, the +circuit is not discarded; instead, it is kept (but not used) until it +becomes usable or unusable. + +> I am not 100% sure whether this description produces the same behavior +> as the current guard-spec, but it is simpler to describe, and has +> proven to be simpler to implement. + +## Implications for program design. + +(This entire section is implementation detail to explain why this is a +simplification from the previous algorithm. It is for explanatory +purposes only and is not part of the spec.) + +With this algorithm, we cut down the interaction between the guard code +and the circuit code considerably, but we do not remove it entirely. +Instead, there remains (in Arti terms) a pair of communication channels +between the circuit manager and the guard manager: + + * Whenever a guard is given to the circuit manager, the circuit manager + receives the write end of a single-use channel to + report whether the guard has succeeded or failed. + + * Whenever a non-primary guard is given to the circuit manager, the + circuit receives the read end of a single-use channel that will tell + it whether the guard is usable or unusable. This channel doesn't + report anything until the guard has one status or the other. + +With this design, the circuit manager never needs to look at the list of +guards, and the guard manager never needs to look at the list of +circuits. + +## Subtleties concerning "guard success" + +Note that the above definitions of a Reachable guard depend on reporting +when the _guard_ is successful or failed. This is not necessarily the +same as reporting whether the _circuit_ is successful or failed. For +example, a circuit that fails after the first hop does not necessarily +indicate that there's anything wrong with the guard. Similarly, we can +reasonably conclude that the guard is working (at least somewhat) as +long as we have an open channel to it. + diff --git a/proposals/338-netinfo-y2038.md b/proposals/338-netinfo-y2038.md new file mode 100644 index 0000000..c3a4c9c --- /dev/null +++ b/proposals/338-netinfo-y2038.md @@ -0,0 +1,79 @@ +``` +Filename: 338-netinfo-y2038.md +Title: Use an 8-byte timestamp in NETINFO cells +Author: Nick Mathewson +Created: 2022-03-14 +Status: Accepted +``` + +# Introduction + +Currently Tor relays use a 4-byte timestamp (in seconds since the Unix +epoch) in their NETINFO cells. Notoriously, such a timestamp will +overflow on 19 January 2038. + +Let's get ahead of the problem and squash this issue now, by expanding +the timestamp to 8 bytes. (8 bytes worth of seconds will be long enough +to outlast the Earth's sun.) + +# Proposed change + +I propose adding a new link protocol version. (The next one in +sequence, as of this writing, is version 6.) + +I propose that we change the text of tor-spec section 4.5 from: + +``` + TIME (Timestamp) [4 bytes] +``` + +to + +``` + TIME (Timestamp) [4 or 8 bytes *] +``` + +and specify that this field is 4 bytes wide on link protocols 1-5, but 8 +bytes wide on link protocols 6 and beyond. + +# Rejected alternatives + +Our protocol specifies that parties MUST ignore extra data at the end of +cells. Therefore we _could_ add additional data at the end of the +NETINFO cell, and use that to store the high 4 bytes of the timestamp +without having to increase the link protocol version number. I propose +that we don't do that: it's ugly. + +As another alternative, we could declare that parties must interpret the +timestamp such that its high 4 bytes place it as close as possible to +their current time. I'm rejecting this kludge because it would give +confusing results in the too-common case where clients have their clocks +mis-set to Jan 1, 1970. + +# Impacts on our implementations + +Arti won't be able to implement this change until it supports connection +padding (as required by link protocol 5), which is currently planned for +the next Arti milestone (1.0.0, scheduled for this fall). + +If we think that that's a problem, or if we want to have support for +implementations without connection padding in the future, we should +reconsider this plan so that connection padding support is independent +from 8-byte timestamps. + +# Other timestamps in Tor + +I've done a cursory search of our protocols to see if we have any other +instances of the Y2038 problem. + +There is a 4-byte timestamp in `cert-spec`, but that one is an unsigned +integer counting _hours_ since the Unix epoch, which will keep it from +wrapping around till 478756 C.E. (The rollover date of "10136 CE" +reported in `cert-spec` is wrong, and seems to be based on the +misapprehension that the counter is in *minutes*.) + +The v2 onion service protocol has 4-byte timestamps, but it is +thoroughly deprecated and unsupported. + +I couldn't find any other 4-byte timestamps, but that is no guarantee: +others should look for them too. diff --git a/proposals/339-udp-over-tor.md b/proposals/339-udp-over-tor.md new file mode 100644 index 0000000..3c1a1d4 --- /dev/null +++ b/proposals/339-udp-over-tor.md @@ -0,0 +1,342 @@ +``` +Filename: 339-udp-over-tor.md +Title: UDP traffic over Tor +Author: Nick Mathewson +Created: 11 May 2020 +Status: Accepted +``` + +# Introduction + +Tor currently only supports delivering two kinds of traffic to the +internet: TCP data streams, and a certain limited subset of DNS +requests. This proposal describes a plan to extend the Tor protocol so +that exit relays can also relay UDP traffic to the network?. + +Why would we want to do this? There are important protocols that use +UDP, and in order to support users that rely on these protocols, we'll +need to support them over Tor. + +This proposal is a minimal version of UDP-over-Tor. Notably, it _does +not_ add an unreliable out-of-order transport to Tor's semantics. +Instead, UDP messages are just tunneled over Tor's existing reliable +in-order circuits. (Adding a datagram transport to Tor is attractive +for some reasons, but it presents a number of problems; see +[this whitepaper](https://research.torproject.org/techreports/side-channel-analysis-2018-11-27.pdf) +for more information.) + +In some parts of this proposal I'll assume that we have accepted and +implemented some version of +[proposal 319](https://gitlab.torproject.org/tpo/core/torspec/-/blob/main/proposals/319-wide-everything.md) +(relay fragment cells) so that we can transmit relay messages larger +than 498 bytes. + +# Overview + +UDP is a datagram protocol; it allows messages of up to 65536 bytes, +though in practice most protocols will use smaller messages in order to +avoid having to deal with fragmentation. + +UDP messages can be dropped or re-ordered. There is no authentication +or encryption baked into UDP, though it can be added by higher-level +protocols like DTLS or QUIC. + +When an application opens a UDP socket, the OS assigns it a 16-bit port +on some IP address of a local interface. The application may send +datagrams from that address:port combination, and will receive datagrams +sent to that address:port. + +With most (all?) IP stacks, a UDP socket can either be _connected_ to a +remote address:port (in which case all messages will be sent to that +address:port, and only messages from that address will be passed to the +application), or _unconnected_ (in which case outgoing messages can be +sent to any address:port, and incoming messages from any address:port +will be accepted). + +In this version of the protocol, we support only _connected_ UDP +sockets, though we provide extension points for someday adding +_unconnected_ socket support. + + +# Tor protocol specification + + +## Overview + +We reserve three new relay commands: `CONNECT_UDP`, `CONNECTED_UDP` and +`DATAGRAM`. + +The `CONNECT_UDP` command is sent by a client to an exit relay to tell it +to open a new UDP stream "connected" to a targeted address and UDP port. +The same restrictions apply as for CONNECT cells: the target must be +permitted by the relay's exit policy, the target must not be private, +localhost, or ANY, the circuit must appear to be multi-hop, there must +not be a stream with the same ID on the same circuit, and so on. + +On success, the relay replies with a `CONNECTED_UDP` cell telling the client +the IP address it is connected to, and which IP address and port (on the +relay) it has bound to. On failure, the relay replies immediately with +an `END` cell. + +(Note that we do not allow the client to choose an arbitrary port to +bind to. It doesn't work when two clients want the same port, and makes +it too easy to probe which ports are in use.) + +When the UDP stream is open, the client can send and receive `DATAGRAM` +messages from the exit relay. Each such message corresponds to a single +UDP datagram. If a datagram is larger than 498 bytes, it is +transmitted as a fragmented message. + +When a client no longer wishes to use a UDP stream, but it wants to keep +the circuit open, it sends an END cell over the circuit. Upon receiving +this message, the exit closes the stream, and stops sending any more +cells on it. + +Exits MAY send an END cell on a UDP stream; when a client receives it, +it must treat the UDP stream as closed. Exits MAY send END cells in +response to resource exhaustion, time-out signals, or (TODO what else?). + +(TODO: Should there be an END ACK? We've wanted one in DATA streams for +a while, to know when we can treat a stream as definitively gone-away.) + +Optimistic traffic is permitted as with TCP streams: a client MAY send +`DATAGRAM` messages immediately after its `CONNECT_UDP` message, without +waiting for a `CONNECTED_UDP`. These are dropped if the `CONNECT_UDP` fails. + +Clients and exits MAY drop incoming datagrams if their stream +or circuit buffers are too full. (Once a DATAGRAM message has been sent +on a circuit, however, it cannot be dropped until it reaches its +intended recipient.) + +Circuits carrying UDP traffic obey the same SENDME congestion control +protocol as other circuits. Rather than using XON/XOFF to control +transmission, excess packets may simply be dropped. UDP and TCP traffic +can be mixed on the same circuit, but not on the same stream. + +## Discussion on "too full" + +(To be determined! We need an algorithm here before we implement, though +our choice of algorithm doesn't need to be the same on all exits or for +all clients, IIUC.) + +Discussion from the pad: + +``` + - "Too full" should be a pair of watermark consensus parameter in + implementation, imo. At the low watermark, random early dropping + MAY be performed, a-la RED, etc. At the high watermark, all packets + SHOULD be dropped. - mike + - +1. I left "too full" as deliberately underspecified here, since I figured + you would have a better idea than me about what it should really be. + Maybe we should say "for one suggested algorithm, see section X below" and + describe the algorithm you propose above in a bit more detail? -nickm + - I have not dug deeply into drop strategies, but I believe that BLUE + is what is in use now: https://en.wikipedia.org/wiki/Blue_(queue_management_algorithm) + - Additionally, an important implementation detail is that it is likely + best to actually continue to read even if our buffer is full, so we can + perform the drop ourselves and ensure the kernel/socket buffers don't + also bloat on us. Though this may have tradeoffs with the eventloop + bottleneck on C-Tor. Because of that bottleneck, it might be best to + stop reading. arti likely will have different optimal properties here. -mike +``` + + + +## Message formats + +Here we describe the format for the bodies of the new relay messages, +along with extensions to some older relay message types. We note in +passing how we could extend these messages to support unconnected UDP +sockets in the future. + + +### CONNECT_UDP + +``` +/* Tells an exit to connect a UDP port for connecting to a new target + address. The stream ID is chosen by the client, and is part of + the relay header. +*/ + +struct connect_udp_body { + /* As in BEGIN cells. */ + u32 flags; + /* Tag for union below. */ + u8 addr_type IN [T_HOSTNAME, T_IPV4, T_IPV6]; + /* Length of the following union */ + u8 addr_len; + /* The address to connect to. */ + union address[addr_type] with length addr_len { + T_IPV4: u32 ipv4; + T_IPV6: u8 ipv6[16]; + T_HOSTNAME: nulterm name + }; + u16 port; + // The rest is ignored. + + // TODO: Is "the rest is ignored" still a good idea? Look at Rochet's + // research. +} +/* Address types */ +const T_HOSTNAME = 0x01; +const T_IPV4 = 0x04; +const T_IPV6 = 0x06; + +/* As in BEGIN cells: these control how hostnames are interpreted. + Clients MUST NOT send unrecognized flags; relays MUST ignore them. + See tor-spec for semantics. + */ +const FLAG_IPV6_OKAY = 0x01; +const FLAG_IPV4_NOT_OKAY = 0x02; +const FLAG_IPV6_PREFERRED = 0x04; +``` + +### CONNECTED_UDP + +A CONNECTED_UDP cell sent in response to a CONNECT_UDP cell has the following +format. + +``` +struct udp_connected_body { + /* The address that the relay has bound locally. This might not + * be an address that is advertised in the relay's descriptor. */ + struct address our_address; + /* The address that the stream is connected to. */ + struct address their_address; + // The rest is ignored. There is no resolved-address TTL. + + // TODO: Is "the rest is ignored" still a good idea? Look at Rochet's + // research. +} + +/* Note that this is a subset of the allowable address parts of a CONNECT_UDP + * message */ +struct address { + u8 tag IN [T_IPV4, T_IPV6]; + u8 len; + union addr[tag] with length len { + T_IPV4: u32 ipv4; + T_IPV6: u8 ipv6[16]; + }; + u16 port; +} +``` + +### DATAGRAM + +``` +struct datagram_body { + /* The datagram body is the entire body of the message. + * This length is in the relay message header. */ + u8 body[..]; +} +``` + +### END + +We explicitly allow all END reasons from the existing Tor protocol. + +We may wish to add more as we gain experience with this protocol. + +### Extensions for unconnected sockets + +Because of security concerns I don't suggest that we support unconnected +sockets in the first version of this protocol. But _if we did_, here's how +I'd suggest we do it. + +1. We would add a new "`FLAG_UNCONNECTED`" flag for `CONNECT_UDP` messages. + +2. We would designate the ANY addresses 0.0.0.0:0 and [::]:0 as permitted in + `CONNECT_UDP` messages, and as indicating unconnected sockets. These would + be only permitted along with the `FLAG_UNCONNECTED` flag, and not + permitted otherwise. + +3. We would designate the ANY addresses above as permitted for the + `their_address` field in the `CONNECTED_UDP` message, in the case when + `FLAG_UNCONNECTED` was used. + +4. We would define a new `DATAGRAM` message format for unconnected streams, + where the first 6 or 18 bytes were reserved for an IPv4 or IPv6 + address:port respectively. + +## Specifying exit policies and compatibility + +We add the following fields to relay descriptors and microdescriptors: + +``` +// In relay descriptors +ipv4-udp-policy accept PortList +ipv6-udp-policy accept PostList + +// In microdescriptors +p4u accept PortList +p6u accept PortList +``` + +(We need to include the policies in relay descriptors so that the +authorities can include them in the microdescriptors when voting.) + +As in the `p` and `p6` fields, the PortList fields are comma-separated +lists of port ranges. Only "accept" policies are parsed or generated in +this case; the alternative is not appreciably shorter. When no policy +is listed, the default is "reject 1-65535". + +This proposal would also add a new subprotocol, "Datagram". Only relays +that implement this proposal would advertise "Datagram=1". Doing so +would not necessarily mean that they permitted datagram streams, if +their exit policies did not say so. + + +# MTU notes and issues + +Internet time. I might have this wrong. + +The "maximum safe IPv4 UDP payload" is "well known" to be only 508 bytes +long: that's defined by the 576-byte minimum-maximum IP datagram size in +[RFC 791 p.12](https://datatracker.ietf.org/doc/html/rfc791), minus 60 bytes +for a very big IPv4 header, minus 8 bytes for the UDP header. + +Unfortunately, our RELAY body size is only 498 bytes. It would be lovely if +we could easily move to larger relay cells, or tell applications not to send +datagrams whose bodies are larger than 498 bytes, but there is probably a +pretty large body of tools out there that assume that they will never have to +restrict their datagram size to fit into a transport this small. + +(That means that if we implement this proposal _without_ fragmentation, +we'll probably be breaking a bunch of stuff, and creating a great deal +of overhead.) + + +# Integration issues + +I do not know how applications should tell Tor that they want to use this +feature. Any ideas? We should probably integrate with their MTU discovery +systems too if we can. (TODO: write about some alternatives) + + +# Resource management issues + +TODO: Talk about sharing server-side relay sockets, and whether it's safe to +do so, and how to avoid information leakage when doing so. + +TODO: Talk about limiting UDP sockets per circuit, and whether that's a good +idea? + + +# Security issues + +- Are there any major DoS or amplification attack vectors that this + enables? I *think* no, because we don't allow spoofing the IP + header. But maybe some wacky protocol out there lets you specify a + reply address in the payload even if the source IP is different. -mike + +- Are there port-reuse issues with source port on exits, such that + destinations could become confused over the start and end of a UDP + stream, if a source port is reused "too fast"? This also likely varies + by protocol. We should prameterize time-before-reuse on source port, + in case we notice issues with some broken/braindead UDP protocol + later. -mike + +# Future work + +Extend this for onion services, possibly based on Matt's prototypes. diff --git a/proposals/340-packed-and-fragmented.md b/proposals/340-packed-and-fragmented.md new file mode 100644 index 0000000..e7f08f4 --- /dev/null +++ b/proposals/340-packed-and-fragmented.md @@ -0,0 +1,325 @@ +``` +Filename: 340-packed-and-fragmented.md +Title: Packed and fragmented relay messages +Author: Nick Mathewson +Created: 31 May 2022 +Status: Open +``` + +# Introduction + +Tor sends long-distance messages on circuits via _relay cells_. The +current relay cell format allows one _relay message_ (e.g., "BEGIN" or +"DATA" or "END") per relay cell. We want to relax this 1:1 requirement, +between messages and cells, for two reasons: + + * To support relay messages that are longer than the current 498-byte + limit. Applications would include wider handshake messages for + postquantum crypto, UDP messages, and SNIP transfer in walking + onions. + + * To transmit small messages more efficiently. Several message types + (notably `SENDME`, `XON`, `XOFF`, and several types from + [proposal 329](./329-traffic-splitting.txt)) are much smaller than + the relay cell size, and could be sent comparatively often. + +In this proposal, we describe a way to decouple relay cells from relay +messages. Relay messages can now be packed into multiple cells or split +across multiple cells. + +This proposal combines ideas from +[proposal 319](./319-wide-everything.md) (fragmentation) and +[proposal 325](./325-packed-relay-cells.md) (packed cells). It requires +[ntor v3](./332-ntor-v3-with-extra-data.md) and prepares for +[next-generation relay cryptography](./308-counter-galois-onion). + +## A preliminary change: Relay encryption, version 1.5 + +We are fairly sure that, whatever we do for our next batch of relay +cryptography, we will want to increase the size of the data used to +authenticate relay cells to 128 bits. (Currently it uses a 4-byte tag +plus 2 bytes of zeros.) + +To avoid proliferating formats, I'm going to suggest that we make the +other changes in this proposal changes concurrently with a change in our +relay cryptography, so that we do not have too many incompatible cell +formats going on at the same time. + +The new format for a decrypted relay _cell_ will be: + + recognized [2 bytes] + digest [14 bytes] + body [509 - 16 = 493 bytes] + +"Digest" and "recognized" are computed as before; the only difference +is that they occur _before_ the rest of the cell, and that "digest" is +truncated to 14 bytes instead of 4. + +If we are lucky, we won't have to build this encryption at all, and we +can just move to some version of GCM-UIV or other RPRP that reserves 16 +bytes for an authentication tag or similar cryptographic object. + +## New relay message packing + +Relay _messages_ now follow the following format: + + Header + command u8 + length u16 + stream_id u16 + Body + data u8[length] + +We require that "command" is never 0. + +Messages can be split across relay cells; multiple messages can occur in +a single relay cell. We enforce the following rules: + + * Headers may not be split across cells. + * If a 0 byte follows any relay message, there are no more messages in + that cell. + * A relay cell may not be "empty": it must have at least some part of + some message. + +Unless specified elsewhere, **all** message types may be packed, and +**all** message types may be fragmented. + +Every command has an associated maximum length for its messages. If not +specified elsewhere, the maximum length for every message is 498 bytes +(for legacy reasons). + +Receivers MUST validate that headers are well-formed and have valid +lengths while handling the cell in which the header is encoded. If the +header is invalid, the receiver must destroy the circuit. + +### Some examples + + +## Negotiation + +This message format requires a new `Relay` subprotocol version to +indicate support. If a client wants to indicate support for this +format, it sends the following extension as part of its `ntor3` +handshake: + + RELAY_PROTOCOL + version u8 + +The `version` field is the `Relay` subprotocol version that the client +wants to use. The relay must send back the same extension in its ntor3 +handshake to acknowledge support. + +## Migration + +We add a consensus parameter, "streamed-relay-messages", with default +value 0, minimum value 0, and maximum value 1. + +If this value is 0, then clients will not (by default) negotiate this +relay protocol. If it is 1, then clients will negotiate it when relays +support it. + +For testing, clients can override this setting. Once enough relays +support this proposal, we'll change the consensus parameter to 1. +Later, we'll change the default to 1 as well. + +## Packing decisions + +We specify the following greedy algorithm for making decisions about +fragmentation and packing. Other algorithms are possible, but this one +is fairly simple, and using it will help avoid distinguishability +issues: + +Whenever a client or relay is about to send a cell that would leave +at least 32 bytes unused in a relay cell, it checks to see whether there +is any pending data to be sent in the same circuit (in a data cell). If +there is, then it adds a DATA message to the end of the current cell, +with as much data as possible. Otherwise, the client sends the cell +with no packed data. + +## Onion services + +Negotiating this for onion services will happen in a separate proposal; +it is not a current priority, since there is nothing sent over +rendezvous circuits that we currently need to fragment or pack. + +## Miscellany + +### Handling `RELAY_EARLY` + +The `RELAY_EARLY` status for a command is determined based on the relay +cell in which the command's _header_ appeared. + +### Handling `SENDME`s + +SENDME messages may not be fragmented; the body and the command must +appear in the same cell. (This is necessary so authenticated sendmes +can have a reasonable implementation.) + +### An exception for `DATA`. + +Data messages may not be fragmented. (There is never a reason to do +this.) + +### Extending message-length maxima + +For now, the maximum length for every message is 498 bytes, except as +follows: + + - `DATAGRAM` messages (see proposal 339) have a maximum body length + of 1967 bytes. (This works out to four relay cells, and + accommodates most reasonable MTU choices) + +Any increase in maximum length for any other message type requires a new +Relay subprotocol version. (For example, if we later want to allow +EXTEND2 messages to be 2000 bytes long, we need to add a new proposal +saying so, and reserving a new subprotocol version.) + +# Appendix: Example cells + + +Here is an example of the simplest case: one message, sent in one relay +cell. Here it is a BEGIN message. + +``` + Cell 1: + Cell header + circid .. [4 bytes] + command RELAY [1 byte] + relay cell header + recognized 0 [2 bytes] + digest (...) [14 bytes] + message header: + command BEGIN [1 byte] + length 23 [2 bytes] + stream_id (...) [2 bytes] + message body + "www.torproject.org:443\0" [23 bytes] + end-of-messages marker + 0 [1 byte] + padding up to end of cell + random [464 bytes] + +``` + +Here's an example with fragmentation only: a large EXTEND2 message split +across two relay cells. + +``` + Cell 1: + Cell header + circid .. [4 bytes] + command RELAY_EARLY [1 byte] + relay cell header + recognized 0 [2 bytes] + digest (...) [14 bytes] + message header: + command EXTEND [1 byte] + length 800 [2 bytes] + stream_id 0 [2 bytes] + message body + (extend body, part 1) [488 bytes] + + Cell 2: + Cell header + circid .. [4 bytes] + command RELAY [1 byte] + relay cell header + recognized 0 [2 bytes] + digest (...) [14 bytes] + message body, continued + (extend body, part 2) [312 bytes] + end-of-messages marker + 0 [1 byte] + padding up to end of cell + random [180 bytes] + +``` + +Here is an example with packing only: A begin_dir message and a data +message in the same cell. + +``` + Cell 1: + Cell header + circid .. [4 bytes] + command RELAY [1 byte] + relay cell header + recognized 0 [2 bytes] + digest (...) [14 bytes] + message header: + command BEGIN_DIR [1 byte] + length 0 [2 bytes] + stream_id 32 [2 bytes] + message body: + (empty) --- [0 bytes] + message header: + command DATA [1 byte] + length 25 [2 bytes] + stream_id 32 [2 bytes] + message body: + "HTTP/1.0 GET /tor/foo\r\n\r\n" [25 bytes] + end-of-messages marker + 0 [1 byte] + padding up to end of cell + random [457 bytes] + +``` + +Here is an example with packing and fragmentation: a large DATAGRAM cell, a +SENDME cell, and an XON cell. (Note that this sequence of cells would not +actually be generated by the algorithm described in "Packing decisions" +above; this is only an example of what parties need to accept.) + +``` + Cell 1: + Cell header + circid .. [4 bytes] + command RELAY [1 byte] + relay cell header + recognized 0 [2 bytes] + digest (...) [14 bytes] + message header: + command DATAGRAM [1 byte] + length 1200 [2 bytes] + stream_id 99 [2 bytes] + message body + (datagram body, part 1) [488 bytes] + + Cell 2: + Cell header + circid .. [4 bytes] + command RELAY [1 byte] + relay cell header + recognized 0 [2 bytes] + digest (...) [14 bytes] + message body, continued + (datagram body, part 2) [493 bytes] + + Cell 3: + Cell header + circid .. [4 bytes] + command RELAY [1 byte] + relay cell header + recognized 0 [2 bytes] + digest (...) [14 bytes] + message body, continued + (datagram body, part 3) [219 bytes] (488+493+219=1200) + message header: + command SENDME [1 byte] + length 23 [2 bytes] + stream_id 0 [2 bytes] + message body: + version 1 [1 byte] + datalen 20 [2 bytes] + data (digest to ack) [20 bytes] + message header: + command XON [1 byte] + length 1 [2 bytes] + stream_id 50 [2 bytes] + message body: + version 1 [1 byte] + end-of-messages marker + 0 [1 byte] + padding up to end of cell + random [239 bytes] +``` diff --git a/proposals/BY_INDEX.md b/proposals/BY_INDEX.md index 9fa8a78..9383351 100644 --- a/proposals/BY_INDEX.md +++ b/proposals/BY_INDEX.md @@ -77,7 +77,7 @@ Below are a list of proposals sorted by their proposal number. See * [`157-specific-cert-download.txt`](/proposals/157-specific-cert-download.txt): Make certificate downloads specific [CLOSED] * [`158-microdescriptors.txt`](/proposals/158-microdescriptors.txt): Clients download consensus + microdescriptors [CLOSED] * [`159-exit-scanning.txt`](/proposals/159-exit-scanning.txt): Exit Scanning [INFORMATIONAL] -* [`160-bandwidth-offset.txt`](/proposals/160-bandwidth-offset.txt): Authorities vote for bandwidth offsets in consensus [FINISHED] +* [`160-bandwidth-offset.txt`](/proposals/160-bandwidth-offset.txt): Authorities vote for bandwidth offsets in consensus [CLOSED] * [`161-computing-bandwidth-adjustments.txt`](/proposals/161-computing-bandwidth-adjustments.txt): Computing Bandwidth Adjustments [CLOSED] * [`162-consensus-flavors.txt`](/proposals/162-consensus-flavors.txt): Publish the consensus in multiple flavors [CLOSED] * [`163-detecting-clients.txt`](/proposals/163-detecting-clients.txt): Detecting whether a connection comes from a client [SUPERSEDED] @@ -149,7 +149,7 @@ Below are a list of proposals sorted by their proposal number. See * [`229-further-socks5-extensions.txt`](/proposals/229-further-socks5-extensions.txt): Further SOCKS5 extensions [REJECTED] * [`230-rsa1024-relay-id-migration.txt`](/proposals/230-rsa1024-relay-id-migration.txt): How to change RSA1024 relay identity keys [OBSOLETE] * [`231-migrate-authority-rsa1024-ids.txt`](/proposals/231-migrate-authority-rsa1024-ids.txt): Migrating authority RSA1024 identity keys [OBSOLETE] -* [`232-pluggable-transports-through-proxy.txt`](/proposals/232-pluggable-transports-through-proxy.txt): Pluggable Transport through SOCKS proxy [FINISHED] +* [`232-pluggable-transports-through-proxy.txt`](/proposals/232-pluggable-transports-through-proxy.txt): Pluggable Transport through SOCKS proxy [CLOSED] * [`233-quicken-tor2web-mode.txt`](/proposals/233-quicken-tor2web-mode.txt): Making Tor2Web mode faster [REJECTED] * [`234-remittance-addresses.txt`](/proposals/234-remittance-addresses.txt): Adding remittance field to directory specification [REJECTED] * [`235-kill-named-flag.txt`](/proposals/235-kill-named-flag.txt): Stop assigning (and eventually supporting) the Named flag [CLOSED] @@ -159,7 +159,7 @@ Below are a list of proposals sorted by their proposal number. See * [`239-consensus-hash-chaining.txt`](/proposals/239-consensus-hash-chaining.txt): Consensus Hash Chaining [OPEN] * [`240-auth-cert-revocation.txt`](/proposals/240-auth-cert-revocation.txt): Early signing key revocation for directory authorities [OPEN] * [`241-suspicious-guard-turnover.txt`](/proposals/241-suspicious-guard-turnover.txt): Resisting guard-turnover attacks [REJECTED] -* [`242-better-families.txt`](/proposals/242-better-families.txt): Better performance and usability for the MyFamily option [RESERVE] +* [`242-better-families.txt`](/proposals/242-better-families.txt): Better performance and usability for the MyFamily option [SUPERSEDED] * [`243-hsdir-flag-need-stable.txt`](/proposals/243-hsdir-flag-need-stable.txt): Give out HSDir flag only to relays with Stable flag [CLOSED] * [`244-use-rfc5705-for-tls-binding.txt`](/proposals/244-use-rfc5705-for-tls-binding.txt): Use RFC5705 Key Exporting in our AUTHENTICATE calls [CLOSED] * [`245-tap-out.txt`](/proposals/245-tap-out.txt): Deprecating and removing the TAP circuit extension protocol [NEEDS-REVISION] @@ -190,22 +190,22 @@ Below are a list of proposals sorted by their proposal number. See * [`270-newhope-hybrid-handshake.txt`](/proposals/270-newhope-hybrid-handshake.txt): RebelAlliance: A Post-Quantum Secure Hybrid Handshake Based on NewHope [OBSOLETE] * [`271-another-guard-selection.txt`](/proposals/271-another-guard-selection.txt): Another algorithm for guard selection [CLOSED] * [`272-valid-and-running-by-default.txt`](/proposals/272-valid-and-running-by-default.txt): Listed routers should be Valid, Running, and treated as such [CLOSED] -* [`273-exit-relay-pinning.txt`](/proposals/273-exit-relay-pinning.txt): Exit relay pinning for web services [DRAFT] +* [`273-exit-relay-pinning.txt`](/proposals/273-exit-relay-pinning.txt): Exit relay pinning for web services [RESERVE] * [`274-rotate-onion-keys-less.txt`](/proposals/274-rotate-onion-keys-less.txt): Rotate onion keys less frequently [CLOSED] -* [`275-md-published-time-is-silly.txt`](/proposals/275-md-published-time-is-silly.txt): Stop including meaningful "published" time in microdescriptor consensus [ACCEPTED] +* [`275-md-published-time-is-silly.txt`](/proposals/275-md-published-time-is-silly.txt): Stop including meaningful "published" time in microdescriptor consensus [CLOSED] * [`276-lower-bw-granularity.txt`](/proposals/276-lower-bw-granularity.txt): Report bandwidth with lower granularity in consensus documents [DEAD] * [`277-detect-id-sharing.txt`](/proposals/277-detect-id-sharing.txt): Detect multiple relay instances running with same ID [OPEN] * [`278-directory-compression-scheme-negotiation.txt`](/proposals/278-directory-compression-scheme-negotiation.txt): Directory Compression Scheme Negotiation [CLOSED] * [`279-naming-layer-api.txt`](/proposals/279-naming-layer-api.txt): A Name System API for Tor Onion Services [NEEDS-REVISION] * [`280-privcount-in-tor.txt`](/proposals/280-privcount-in-tor.txt): Privacy-Preserving Statistics with Privcount in Tor [SUPERSEDED] * [`281-bulk-md-download.txt`](/proposals/281-bulk-md-download.txt): Downloading microdescriptors in bulk [RESERVE] -* [`282-remove-named-from-consensus.txt`](/proposals/282-remove-named-from-consensus.txt): Remove "Named" and "Unnamed" handling from consensus voting [FINISHED] +* [`282-remove-named-from-consensus.txt`](/proposals/282-remove-named-from-consensus.txt): Remove "Named" and "Unnamed" handling from consensus voting [ACCEPTED] * [`283-ipv6-in-micro-consensus.txt`](/proposals/283-ipv6-in-micro-consensus.txt): Move IPv6 ORPorts from microdescriptors to the microdesc consensus [CLOSED] * [`284-hsv3-control-port.txt`](/proposals/284-hsv3-control-port.txt): Hidden Service v3 Control Port [CLOSED] * [`285-utf-8.txt`](/proposals/285-utf-8.txt): Directory documents should be standardized as UTF-8 [ACCEPTED] * [`286-hibernation-api.txt`](/proposals/286-hibernation-api.txt): Controller APIs for hibernation access on mobile [REJECTED] * [`287-reduce-lifetime.txt`](/proposals/287-reduce-lifetime.txt): Reduce circuit lifetime without overloading the network [OPEN] -* [`288-privcount-with-shamir.txt`](/proposals/288-privcount-with-shamir.txt): Privacy-Preserving Statistics with Privcount in Tor (Shamir version) [ACCEPTED] +* [`288-privcount-with-shamir.txt`](/proposals/288-privcount-with-shamir.txt): Privacy-Preserving Statistics with Privcount in Tor (Shamir version) [RESERVE] * [`289-authenticated-sendmes.txt`](/proposals/289-authenticated-sendmes.txt): Authenticating sendme cells to mitigate bandwidth attacks [CLOSED] * [`290-deprecate-consensus-methods.txt`](/proposals/290-deprecate-consensus-methods.txt): Continuously update consensus methods [META] * [`291-two-guard-nodes.txt`](/proposals/291-two-guard-nodes.txt): The move to two guard nodes [NEEDS-REVISION] @@ -218,7 +218,7 @@ Below are a list of proposals sorted by their proposal number. See * [`298-canonical-families.txt`](/proposals/298-canonical-families.txt): Putting family lines in canonical form [CLOSED] * [`299-ip-failure-count.txt`](/proposals/299-ip-failure-count.txt): Preferring IPv4 or IPv6 based on IP Version Failure Count [SUPERSEDED] * [`300-walking-onions.txt`](/proposals/300-walking-onions.txt): Walking Onions: Scaling and Saving Bandwidth [INFORMATIONAL] -* [`301-dont-vote-on-package-fingerprints.txt`](/proposals/301-dont-vote-on-package-fingerprints.txt): Don't include package fingerprints in consensus documents [FINISHED] +* [`301-dont-vote-on-package-fingerprints.txt`](/proposals/301-dont-vote-on-package-fingerprints.txt): Don't include package fingerprints in consensus documents [OPEN] * [`302-padding-machines-for-onion-clients.txt`](/proposals/302-padding-machines-for-onion-clients.txt): Hiding onion service clients using padding [CLOSED] * [`303-protover-removal-policy.txt`](/proposals/303-protover-removal-policy.txt): When and how to remove support for protocol versions [OPEN] * [`304-socks5-extending-hs-error-codes.txt`](/proposals/304-socks5-extending-hs-error-codes.txt): Extending SOCKS5 Onion Service Error Codes [CLOSED] @@ -227,29 +227,35 @@ Below are a list of proposals sorted by their proposal number. See * [`307-onionbalance-v3.txt`](/proposals/307-onionbalance-v3.txt): Onion Balance Support for Onion Service v3 [RESERVE] * [`308-counter-galois-onion.txt`](/proposals/308-counter-galois-onion.txt): Counter Galois Onion: A New Proposal for Forward-Secure Relay Cryptography [OPEN] * [`309-optimistic-socks-in-tor.txt`](/proposals/309-optimistic-socks-in-tor.txt): Optimistic SOCKS Data [OPEN] -* [`310-bandaid-on-guard-selection.txt`](/proposals/310-bandaid-on-guard-selection.txt): Towards load-balancing in Prop 271 [FINISHED] +* [`310-bandaid-on-guard-selection.txt`](/proposals/310-bandaid-on-guard-selection.txt): Towards load-balancing in Prop 271 [CLOSED] * [`311-relay-ipv6-reachability.txt`](/proposals/311-relay-ipv6-reachability.txt): Tor Relay IPv6 Reachability [ACCEPTED] * [`312-relay-auto-ipv6-addr.txt`](/proposals/312-relay-auto-ipv6-addr.txt): Tor Relay Automatic IPv6 Address Discovery [ACCEPTED] * [`313-relay-ipv6-stats.txt`](/proposals/313-relay-ipv6-stats.txt): Tor Relay IPv6 Statistics [ACCEPTED] -* [`314-allow-markdown-proposals.md`](/proposals/314-allow-markdown-proposals.md): Allow Markdown for proposal format [FINISHED] -* [`315-update-dir-required-fields.txt`](/proposals/315-update-dir-required-fields.txt): Updating the list of fields required in directory documents [OPEN] +* [`314-allow-markdown-proposals.md`](/proposals/314-allow-markdown-proposals.md): Allow Markdown for proposal format [CLOSED] +* [`315-update-dir-required-fields.txt`](/proposals/315-update-dir-required-fields.txt): Updating the list of fields required in directory documents [CLOSED] * [`316-flashflow.md`](/proposals/316-flashflow.md): FlashFlow: A Secure Speed Test for Tor (Parent Proposal) [DRAFT] * [`317-secure-dns-name-resolution.txt`](/proposals/317-secure-dns-name-resolution.txt): Improve security aspects of DNS name resolution [NEEDS-REVISION] * [`318-limit-protovers.md`](/proposals/318-limit-protovers.md): Limit protover values to 0-63 [CLOSED] * [`319-wide-everything.md`](/proposals/319-wide-everything.md): RELAY_FRAGMENT cells [OPEN] * [`320-tap-out-again.md`](/proposals/320-tap-out-again.md): Removing TAP usage from v2 onion services [REJECTED] -* [`321-happy-families.md`](/proposals/321-happy-families.md): Better performance and usability for the MyFamily option (v2) [OPEN] +* [`321-happy-families.md`](/proposals/321-happy-families.md): Better performance and usability for the MyFamily option (v2) [ACCEPTED] * [`322-dirport-linkspec.md`](/proposals/322-dirport-linkspec.md): Extending link specifiers to include the directory port [OPEN] * [`323-walking-onions-full.md`](/proposals/323-walking-onions-full.md): Specification for Walking Onions [OPEN] * [`324-rtt-congestion-control.txt`](/proposals/324-rtt-congestion-control.txt): RTT-based Congestion Control for Tor [OPEN] * [`325-packed-relay-cells.md`](/proposals/325-packed-relay-cells.md): Packed relay cells: saving space on small commands [OPEN] * [`326-tor-relay-well-known-uri-rfc8615.md`](/proposals/326-tor-relay-well-known-uri-rfc8615.md): The "tor-relay" Well-Known Resource Identifier [OPEN] * [`327-pow-over-intro.txt`](/proposals/327-pow-over-intro.txt): A First Take at PoW Over Introduction Circuits [DRAFT] -* [`328-relay-overload-report.md`](/proposals/328-relay-overload-report.md): Make Relays Report When They Are Overloaded [DRAFT] +* [`328-relay-overload-report.md`](/proposals/328-relay-overload-report.md): Make Relays Report When They Are Overloaded [CLOSED] * [`329-traffic-splitting.txt`](/proposals/329-traffic-splitting.txt): Overcoming Tor's Bottlenecks with Traffic Splitting [DRAFT] * [`330-authority-contact.md`](/proposals/330-authority-contact.md): Modernizing authority contact entries [OPEN] * [`331-res-tokens-for-anti-dos.md`](/proposals/331-res-tokens-for-anti-dos.md): Res tokens: Anonymous Credentials for Onion Service DoS Resilience [DRAFT] -* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 [OPEN] -* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite [DRAFT] -* [`334-middle-only-flag.txt`](/proposals/334-middle-only-flag.txt): A Directory Authority Flag To Mark Relays As Middle-only [OPEN] +* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 [FINISHED] +* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite [FINISHED] +* [`334-middle-only-flag.txt`](/proposals/334-middle-only-flag.txt): A Directory Authority Flag To Mark Relays As Middle-only [SUPERSEDED] +* [`335-middle-only-redux.md`](/proposals/335-middle-only-redux.md): An authority-only design for MiddleOnly [CLOSED] +* [`336-randomize-guard-retries.md`](/proposals/336-randomize-guard-retries.md): Randomized schedule for guard retries [ACCEPTED] +* [`337-simpler-guard-usability.md`](/proposals/337-simpler-guard-usability.md): A simpler way to decide, "Is this guard usable?" [ACCEPTED] +* [`338-netinfo-y2038.md`](/proposals/338-netinfo-y2038.md): Use an 8-byte timestamp in NETINFO cells [ACCEPTED] +* [`339-udp-over-tor.md`](/proposals/339-udp-over-tor.md): UDP traffic over Tor [ACCEPTED] +* [`340-packed-and-fragmented.md`](/proposals/340-packed-and-fragmented.md): Packed and fragmented relay messages [OPEN] diff --git a/proposals/README.md b/proposals/README.md index 3e3645a..1431e8d 100644 --- a/proposals/README.md +++ b/proposals/README.md @@ -27,21 +27,19 @@ for discussion. * [`287-reduce-lifetime.txt`](/proposals/287-reduce-lifetime.txt): Reduce circuit lifetime without overloading the network * [`295-relay-crypto-with-adl.txt`](/proposals/295-relay-crypto-with-adl.txt): Using ADL for relay cryptography (solving the crypto-tagging attack) * [`296-expose-bandwidth-files.txt`](/proposals/296-expose-bandwidth-files.txt): Have Directory Authorities expose raw bandwidth list files +* [`301-dont-vote-on-package-fingerprints.txt`](/proposals/301-dont-vote-on-package-fingerprints.txt): Don't include package fingerprints in consensus documents * [`303-protover-removal-policy.txt`](/proposals/303-protover-removal-policy.txt): When and how to remove support for protocol versions * [`306-ipv6-happy-eyeballs.txt`](/proposals/306-ipv6-happy-eyeballs.txt): A Tor Implementation of IPv6 Happy Eyeballs * [`308-counter-galois-onion.txt`](/proposals/308-counter-galois-onion.txt): Counter Galois Onion: A New Proposal for Forward-Secure Relay Cryptography * [`309-optimistic-socks-in-tor.txt`](/proposals/309-optimistic-socks-in-tor.txt): Optimistic SOCKS Data -* [`315-update-dir-required-fields.txt`](/proposals/315-update-dir-required-fields.txt): Updating the list of fields required in directory documents * [`319-wide-everything.md`](/proposals/319-wide-everything.md): RELAY_FRAGMENT cells -* [`321-happy-families.md`](/proposals/321-happy-families.md): Better performance and usability for the MyFamily option (v2) * [`322-dirport-linkspec.md`](/proposals/322-dirport-linkspec.md): Extending link specifiers to include the directory port * [`323-walking-onions-full.md`](/proposals/323-walking-onions-full.md): Specification for Walking Onions * [`324-rtt-congestion-control.txt`](/proposals/324-rtt-congestion-control.txt): RTT-based Congestion Control for Tor * [`325-packed-relay-cells.md`](/proposals/325-packed-relay-cells.md): Packed relay cells: saving space on small commands * [`326-tor-relay-well-known-uri-rfc8615.md`](/proposals/326-tor-relay-well-known-uri-rfc8615.md): The "tor-relay" Well-Known Resource Identifier * [`330-authority-contact.md`](/proposals/330-authority-contact.md): Modernizing authority contact entries -* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 -* [`334-middle-only-flag.txt`](/proposals/334-middle-only-flag.txt): A Directory Authority Flag To Mark Relays As Middle-only +* [`340-packed-and-fragmented.md`](/proposals/340-packed-and-fragmented.md): Packed and fragmented relay messages ## ACCEPTED proposals: slated for implementation @@ -51,13 +49,17 @@ might or might not have a specific timeframe planned for their implementation. * [`265-load-balancing-with-overhead.txt`](/proposals/265-load-balancing-with-overhead.txt): Load Balancing with Overhead Parameters -* [`275-md-published-time-is-silly.txt`](/proposals/275-md-published-time-is-silly.txt): Stop including meaningful "published" time in microdescriptor consensus +* [`282-remove-named-from-consensus.txt`](/proposals/282-remove-named-from-consensus.txt): Remove "Named" and "Unnamed" handling from consensus voting * [`285-utf-8.txt`](/proposals/285-utf-8.txt): Directory documents should be standardized as UTF-8 -* [`288-privcount-with-shamir.txt`](/proposals/288-privcount-with-shamir.txt): Privacy-Preserving Statistics with Privcount in Tor (Shamir version) * [`292-mesh-vanguards.txt`](/proposals/292-mesh-vanguards.txt): Mesh-based vanguards * [`311-relay-ipv6-reachability.txt`](/proposals/311-relay-ipv6-reachability.txt): Tor Relay IPv6 Reachability * [`312-relay-auto-ipv6-addr.txt`](/proposals/312-relay-auto-ipv6-addr.txt): Tor Relay Automatic IPv6 Address Discovery * [`313-relay-ipv6-stats.txt`](/proposals/313-relay-ipv6-stats.txt): Tor Relay IPv6 Statistics +* [`321-happy-families.md`](/proposals/321-happy-families.md): Better performance and usability for the MyFamily option (v2) +* [`336-randomize-guard-retries.md`](/proposals/336-randomize-guard-retries.md): Randomized schedule for guard retries +* [`337-simpler-guard-usability.md`](/proposals/337-simpler-guard-usability.md): A simpler way to decide, "Is this guard usable?" +* [`338-netinfo-y2038.md`](/proposals/338-netinfo-y2038.md): Use an 8-byte timestamp in NETINFO cells +* [`339-udp-over-tor.md`](/proposals/339-udp-over-tor.md): UDP traffic over Tor ## FINISHED proposals: implemented, specs not merged @@ -65,13 +67,9 @@ implementation. These proposals are implemented in some version of Tor; the proposals themselves still need to be merged into the specifications proper. -* [`160-bandwidth-offset.txt`](/proposals/160-bandwidth-offset.txt): Authorities vote for bandwidth offsets in consensus -* [`232-pluggable-transports-through-proxy.txt`](/proposals/232-pluggable-transports-through-proxy.txt): Pluggable Transport through SOCKS proxy * [`260-rend-single-onion.txt`](/proposals/260-rend-single-onion.txt): Rendezvous Single Onion Services -* [`282-remove-named-from-consensus.txt`](/proposals/282-remove-named-from-consensus.txt): Remove "Named" and "Unnamed" handling from consensus voting -* [`301-dont-vote-on-package-fingerprints.txt`](/proposals/301-dont-vote-on-package-fingerprints.txt): Don't include package fingerprints in consensus documents -* [`310-bandaid-on-guard-selection.txt`](/proposals/310-bandaid-on-guard-selection.txt): Towards load-balancing in Prop 271 -* [`314-allow-markdown-proposals.md`](/proposals/314-allow-markdown-proposals.md): Allow Markdown for proposal format +* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 +* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite ## META proposals: about the proposal process @@ -105,14 +103,11 @@ These proposals have been marked as a draft by their author or the editors, indicating that they aren't yet in a complete form. They're still open for discussion. -* [`273-exit-relay-pinning.txt`](/proposals/273-exit-relay-pinning.txt): Exit relay pinning for web services * [`294-tls-1.3.txt`](/proposals/294-tls-1.3.txt): TLS 1.3 Migration * [`316-flashflow.md`](/proposals/316-flashflow.md): FlashFlow: A Secure Speed Test for Tor (Parent Proposal) * [`327-pow-over-intro.txt`](/proposals/327-pow-over-intro.txt): A First Take at PoW Over Introduction Circuits -* [`328-relay-overload-report.md`](/proposals/328-relay-overload-report.md): Make Relays Report When They Are Overloaded * [`329-traffic-splitting.txt`](/proposals/329-traffic-splitting.txt): Overcoming Tor's Bottlenecks with Traffic Splitting * [`331-res-tokens-for-anti-dos.md`](/proposals/331-res-tokens-for-anti-dos.md): Res tokens: Anonymous Credentials for Onion Service DoS Resilience -* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite ## NEEDS-REVISION proposals: ideas that we can't implement as-is @@ -181,6 +176,7 @@ necessary. * [`155-four-hidden-service-improvements.txt`](/proposals/155-four-hidden-service-improvements.txt): Four Improvements of Hidden Service Performance * [`157-specific-cert-download.txt`](/proposals/157-specific-cert-download.txt): Make certificate downloads specific * [`158-microdescriptors.txt`](/proposals/158-microdescriptors.txt): Clients download consensus + microdescriptors +* [`160-bandwidth-offset.txt`](/proposals/160-bandwidth-offset.txt): Authorities vote for bandwidth offsets in consensus * [`161-computing-bandwidth-adjustments.txt`](/proposals/161-computing-bandwidth-adjustments.txt): Computing Bandwidth Adjustments * [`162-consensus-flavors.txt`](/proposals/162-consensus-flavors.txt): Publish the consensus in multiple flavors * [`166-statistics-extra-info-docs.txt`](/proposals/166-statistics-extra-info-docs.txt): Including Network Statistics in Extra-Info Documents @@ -216,6 +212,7 @@ necessary. * [`224-rend-spec-ng.txt`](/proposals/224-rend-spec-ng.txt): Next-Generation Hidden Services in Tor * [`227-vote-on-package-fingerprints.txt`](/proposals/227-vote-on-package-fingerprints.txt): Include package fingerprints in consensus documents * [`228-cross-certification-onionkeys.txt`](/proposals/228-cross-certification-onionkeys.txt): Cross-certifying identity keys with onion keys +* [`232-pluggable-transports-through-proxy.txt`](/proposals/232-pluggable-transports-through-proxy.txt): Pluggable Transport through SOCKS proxy * [`235-kill-named-flag.txt`](/proposals/235-kill-named-flag.txt): Stop assigning (and eventually supporting) the Named flag * [`236-single-guard-node.txt`](/proposals/236-single-guard-node.txt): The move to a single guard node * [`237-directory-servers-for-all.txt`](/proposals/237-directory-servers-for-all.txt): All relays are directory servers @@ -229,6 +226,7 @@ necessary. * [`271-another-guard-selection.txt`](/proposals/271-another-guard-selection.txt): Another algorithm for guard selection * [`272-valid-and-running-by-default.txt`](/proposals/272-valid-and-running-by-default.txt): Listed routers should be Valid, Running, and treated as such * [`274-rotate-onion-keys-less.txt`](/proposals/274-rotate-onion-keys-less.txt): Rotate onion keys less frequently +* [`275-md-published-time-is-silly.txt`](/proposals/275-md-published-time-is-silly.txt): Stop including meaningful "published" time in microdescriptor consensus * [`278-directory-compression-scheme-negotiation.txt`](/proposals/278-directory-compression-scheme-negotiation.txt): Directory Compression Scheme Negotiation * [`283-ipv6-in-micro-consensus.txt`](/proposals/283-ipv6-in-micro-consensus.txt): Move IPv6 ORPorts from microdescriptors to the microdesc consensus * [`284-hsv3-control-port.txt`](/proposals/284-hsv3-control-port.txt): Hidden Service v3 Control Port @@ -239,7 +237,12 @@ necessary. * [`302-padding-machines-for-onion-clients.txt`](/proposals/302-padding-machines-for-onion-clients.txt): Hiding onion service clients using padding * [`304-socks5-extending-hs-error-codes.txt`](/proposals/304-socks5-extending-hs-error-codes.txt): Extending SOCKS5 Onion Service Error Codes * [`305-establish-intro-dos-defense-extention.txt`](/proposals/305-establish-intro-dos-defense-extention.txt): ESTABLISH_INTRO Cell DoS Defense Extension +* [`310-bandaid-on-guard-selection.txt`](/proposals/310-bandaid-on-guard-selection.txt): Towards load-balancing in Prop 271 +* [`314-allow-markdown-proposals.md`](/proposals/314-allow-markdown-proposals.md): Allow Markdown for proposal format +* [`315-update-dir-required-fields.txt`](/proposals/315-update-dir-required-fields.txt): Updating the list of fields required in directory documents * [`318-limit-protovers.md`](/proposals/318-limit-protovers.md): Limit protover values to 0-63 +* [`328-relay-overload-report.md`](/proposals/328-relay-overload-report.md): Make Relays Report When They Are Overloaded +* [`335-middle-only-redux.md`](/proposals/335-middle-only-redux.md): An authority-only design for MiddleOnly ## RESERVE proposals: saving for later @@ -257,11 +260,12 @@ confront the problems that they try to solve. * [`211-mapaddress-tor-status.txt`](/proposals/211-mapaddress-tor-status.txt): Internal Mapaddress for Tor Configuration Testing * [`223-ace-handshake.txt`](/proposals/223-ace-handshake.txt): Ace: Improved circuit-creation key exchange * [`226-bridgedb-database-improvements.txt`](/proposals/226-bridgedb-database-improvements.txt): "Scalability and Stability Improvements to BridgeDB: Switching to a Distributed Database System and RDBMS" -* [`242-better-families.txt`](/proposals/242-better-families.txt): Better performance and usability for the MyFamily option * [`255-hs-load-balancing.txt`](/proposals/255-hs-load-balancing.txt): Controller features to allow for load-balancing hidden services * [`256-key-revocation.txt`](/proposals/256-key-revocation.txt): Key revocation for relays and authorities * [`262-rekey-circuits.txt`](/proposals/262-rekey-circuits.txt): Re-keying live circuits with new cryptographic material +* [`273-exit-relay-pinning.txt`](/proposals/273-exit-relay-pinning.txt): Exit relay pinning for web services * [`281-bulk-md-download.txt`](/proposals/281-bulk-md-download.txt): Downloading microdescriptors in bulk +* [`288-privcount-with-shamir.txt`](/proposals/288-privcount-with-shamir.txt): Privacy-Preserving Statistics with Privcount in Tor (Shamir version) * [`307-onionbalance-v3.txt`](/proposals/307-onionbalance-v3.txt): Onion Balance Support for Onion Service v3 @@ -288,12 +292,14 @@ implemented. * [`194-mnemonic-urls.txt`](/proposals/194-mnemonic-urls.txt): Mnemonic .onion URLs * [`210-faster-headless-consensus-bootstrap.txt`](/proposals/210-faster-headless-consensus-bootstrap.txt): Faster Headless Consensus Bootstrapping * [`225-strawman-shared-rand.txt`](/proposals/225-strawman-shared-rand.txt): Strawman proposal: commit-and-reveal shared rng +* [`242-better-families.txt`](/proposals/242-better-families.txt): Better performance and usability for the MyFamily option * [`247-hs-guard-discovery.txt`](/proposals/247-hs-guard-discovery.txt): Defending Against Guard Discovery Attacks using Vanguards * [`249-large-create-cells.txt`](/proposals/249-large-create-cells.txt): Allow CREATE cells with >505 bytes of handshake data * [`252-single-onion.txt`](/proposals/252-single-onion.txt): Single Onion Services * [`266-removing-current-obsolete-clients.txt`](/proposals/266-removing-current-obsolete-clients.txt): Removing current obsolete clients from the Tor network * [`280-privcount-in-tor.txt`](/proposals/280-privcount-in-tor.txt): Privacy-Preserving Statistics with Privcount in Tor * [`299-ip-failure-count.txt`](/proposals/299-ip-failure-count.txt): Preferring IPv4 or IPv6 based on IP Version Failure Count +* [`334-middle-only-flag.txt`](/proposals/334-middle-only-flag.txt): A Directory Authority Flag To Mark Relays As Middle-only ## DEAD, REJECTED, OBSOLETE proposals: not in our plans diff --git a/pt-spec.txt b/pt-spec.txt index e43a3f7..45b4c31 100644 --- a/pt-spec.txt +++ b/pt-spec.txt @@ -1,4 +1,3 @@ - Pluggable Transport Specification (Version 1) Abstract @@ -452,7 +451,7 @@ Table of Contents The "VERSION" message is used to signal the Pluggable Transport Specification version (as in "TOR_PT_MANAGED_TRANSPORT_VER") - that the PT proxy will use to configure it's transports and + that the PT proxy will use to configure its transports and communicate with the parent process. The version for the environment values and reply messages @@ -644,7 +643,7 @@ Table of Contents For example, the tor daemon logs those messages at the Severity level and sends them onto the control port using the PT_LOG (see control-spec.txt) - event so any third part can pick them up for debugging. + event so any third party can pick them up for debugging. The format of the message: @@ -668,9 +667,9 @@ Table of Contents The format of the message: - STATUS TRANSPORT=Transport <K_1>=<V_1> [<K_2>=<V_2>, ...] + STATUS TRANSPORT=Transport <K_1>=<V_1> [<K_2>=<V_2> ...] - The TRANSPORT value indicate a hint on what the PT is such has the name or + The TRANSPORT value indicates a hint on what the PT is such has the name or the protocol used for instance. As an example, obfs4proxy would use "obfs4". Thus, the Transport value can be anything the PT itself defines and it can be a String or CString (see section 2 in control-spec.txt). @@ -711,7 +710,7 @@ Table of Contents causes cleanup and a graceful shutdown if able). - PT proxies SHOULD attempt to detect when the parent has - terminated (eg: via detecting that it's parent process ID haso + terminated (eg: via detecting that its parent process ID has changed on U*IX systems), and gracefully terminate. 3.5. Pluggable Transport Client Per-Connection Arguments diff --git a/rend-spec-v3.txt b/rend-spec-v3.txt index 2abc732..fac1395 100644 --- a/rend-spec-v3.txt +++ b/rend-spec-v3.txt @@ -35,7 +35,7 @@ Table of contents: 2.2.5. Expiring hidden service descriptors [EXPIRE-DESC] 2.2.6. URLs for anonymous uploading and downloading 2.3. Publishing shared random values [PUB-SHAREDRANDOM] - 2.3.1. Client behavior in the absense of shared random values + 2.3.1. Client behavior in the absence of shared random values 2.3.2. Hidden services and changing shared random values 2.4. Hidden service descriptors: outer wrapper [DESC-OUTER] 2.5. Hidden service descriptors: encryption format [HS-DESC-ENC] @@ -457,7 +457,7 @@ Table of contents: To learn the introduction points, clients must decrypt the body of the hidden service descriptor. To do so, clients must know the _unblinded_ - public key of the service, which makes the descriptor unuseable by entities + public key of the service, which makes the descriptor unusable by entities without that knowledge (e.g. HSDirs that don't know the onion address). Also, if optional client authorization is enabled, hidden service @@ -626,7 +626,7 @@ Table of contents: 1.9.1. In even more detail: Client authorization keys [CLIENT-AUTH] When client authorization is enabled, each authorized client of a hidden - service has two more assymetric keypairs which are shared with the hidden + service has two more asymmetric keypairs which are shared with the hidden service. An entity without those keys is not able to use the hidden service. Throughout this document, we assume that these pre-shared keys are exchanged between the hidden service and its clients in a secure out-of-band @@ -746,7 +746,7 @@ Table of contents: HSDirs. The set of responsible HSDirs is determined as specified in [WHERE-HSDESC]. - Specifically, everytime a hidden service publishes its descriptor, it also + Specifically, every time a hidden service publishes its descriptor, it also sets up a timer for a random time between 60 minutes and 120 minutes in the future. When the timer triggers, the hidden service needs to publish its descriptor again to the responsible HSDirs for that time period. @@ -831,7 +831,7 @@ Table of contents: 2.2.4. Using time periods and SRVs to fetch/upload HS descriptors [FETCHUPLOADDESC] Hidden services and clients need to make correct use of time periods (TP) - and shared random values (SRVs) to successfuly fetch and upload + and shared random values (SRVs) to successfully fetch and upload descriptors. Furthermore, to avoid problems with skewed clocks, both clients and services use the 'valid-after' time of a live consensus as a way to take decisions with regards to uploading and fetching descriptors. By using the @@ -894,7 +894,7 @@ Table of contents: As discussed above, services maintain two active descriptors at any time. We call these the "first" and "second" service descriptors. Services rotate - their descriptor everytime they receive a consensus with a valid_after time + their descriptor every time they receive a consensus with a valid_after time past the next SRV calculation time. They rotate their descriptors by discarding their first descriptor, pushing the second descriptor to the first, and rebuilding their second descriptor with the latest data. @@ -1008,7 +1008,7 @@ Table of contents: with a torsion component). The right way for clients to detect such fraudulent addresses (which should - only occur malevolently and never natutally) is to extract the ed25519 + only occur malevolently and never naturally) is to extract the ed25519 public key from the onion address and multiply it by the ed25519 group order and ensure that the result is the ed25519 identity element. For more details, please see [TORSION-REFS]. @@ -1028,7 +1028,7 @@ Table of contents: "shared-rand-previous-value" SP NUM_REVEALS SP VALUE NL "shared-rand-current-value" SP NUM_REVEALS SP VALUE NL -2.3.1. Client behavior in the absense of shared random values +2.3.1. Client behavior in the absence of shared random values If the previous or current shared random value cannot be found in a consensus, then Tor clients and services need to generate their own random @@ -1424,7 +1424,7 @@ Table of contents: MUST be present if "legacy-key" is present. The certificate is a proposal 220 RSA->Ed cross-certificate wrapped - in "-----BEGIN CROSSCERT-----" armor, cross-certifying the the RSA + in "-----BEGIN CROSSCERT-----" armor, cross-certifying the RSA public key found in "legacy-key" using the descriptor signing key. To remain compatible with future revisions to the descriptor format, @@ -1433,7 +1433,7 @@ Table of contents: should ignore ones they do not recognize. Clients who manage to extract the introduction points of the hidden service - can prroceed with the introduction protocol as specified in [INTRO-PROTOCOL]. + can proceed with the introduction protocol as specified in [INTRO-PROTOCOL]. 2.5.3. Deriving hidden service descriptor encryption keys [HS-DESC-ENCRYPTION-KEYS] @@ -1448,7 +1448,7 @@ Table of contents: Here is the key generation logic: - SALT = 16 bytes from H(random), changes each time we rebuld the + SALT = 16 bytes from H(random), changes each time we rebuild the descriptor even if the content of the descriptor hasn't changed. (So that we don't leak whether the intro point list etc. changed) @@ -1548,8 +1548,17 @@ Table of contents: authentication key. The EXT_FIELD_TYPE, EXT_FIELD_LEN, EXT_FIELD entries are reserved for - future extensions to the introduction protocol. Extensions with + extensions to the introduction protocol. Extensions with unrecognized EXT_FIELD_TYPE values must be ignored. + (`EXT_FIELD_LEN` may be zero, in which case EXT_FIELD is absent.) + + Unless otherwise specified in the documentation for an extension type: + * Each extension type SHOULD be sent only once in a message. + * Parties MUST ignore any occurrences all occurrences of an extension + with a given type after the first such occurrence. + * Extensions SHOULD be sent in numerically ascending order by type. + (The above extension sorting and multiplicity rules are only defaults; + they may be overridden in the descriptions of individual extensions.) The HANDSHAKE_AUTH field contains the MAC of all earlier fields in the cell using as its key the shared per-circuit material ("KH") @@ -1615,7 +1624,7 @@ Table of contents: The burst per second of INTRODUCE2 cell relayed to the service. - The PARAM_VALUE size is 8 bytes in order to accomodate 64bit values. + The PARAM_VALUE size is 8 bytes in order to accommodate 64bit values. It MUST match the specified limit for the following PARAM_TYPE: [01] -- Min: 0, Max: 2147483647 @@ -1685,6 +1694,10 @@ Table of contents: Older versions of Tor send back an empty INTRO_ESTABLISHED cell instead. Services must accept an empty INTRO_ESTABLISHED cell from a legacy relay. + The same rules for multiplicity, ordering, and handling unknown types + apply to the extension fields here as described [EST_INTRO] above. + + 3.2. Sending an INTRODUCE1 cell to the introduction point. [SEND_INTRO1] In order to participate in the introduction protocol, a client must @@ -1737,6 +1750,10 @@ Table of contents: INTRODUCE2 cell with exactly the same contents to the service, and sends an INTRODUCE_ACK response to the client. + The same rules for multiplicity, ordering, and handling unknown types + apply to the extension fields here as described [EST_INTRO] above. + + 3.2.2. INTRODUCE_ACK cell format. [INTRO_ACK] An INTRODUCE_ACK cell has the following fields: @@ -1755,6 +1772,10 @@ Table of contents: [00 02] -- Bad message format [00 03] -- Can't relay cell to service + The same rules for multiplicity, ordering, and handling unknown types + apply to the extension fields here as described [EST_INTRO] above. + + 3.3. Processing an INTRODUCE2 cell at the hidden service. [PROCESS_INTRO2] Upon receiving an INTRODUCE2 cell, the hidden service host checks whether @@ -1831,6 +1852,10 @@ Table of contents: shared key with the hidden service client. * A set of shared keys to use for end-to-end encryption. + The same rules for multiplicity, ordering, and handling unknown types + apply to the extension fields here as described [EST_INTRO] above. + + 3.3.1. Introduction handshake encryption requirements [INTRO-HANDSHAKE-REQS] When decoding the encrypted information in an INTRODUCE2 cell, a diff --git a/srv-spec.txt b/srv-spec.txt index a8bb878..a68ef3e 100644 --- a/srv-spec.txt +++ b/srv-spec.txt @@ -98,7 +98,7 @@ Tor works. This text used to be proposal 250-commit-reveal-consensus.txt. 2.1. Ten thousand feet view of the protocol Our commit-and-reveal protocol aims to produce a fresh shared random value - everyday at 00:00UTC. The final fresh random value is embedded in the + every day at 00:00UTC. The final fresh random value is embedded in the consensus document at that time. Our protocol has two phases and uses the hourly voting procedure of Tor. @@ -124,11 +124,11 @@ Tor works. This text used to be proposal 250-commit-reveal-consensus.txt. At 00:00UTC, the shared random value is computed from the agreed revealed values and added to the consensus. - This concludes the commit-and-reveal protocol at 00:00UTC everyday. + This concludes the commit-and-reveal protocol every day at 00:00UTC. 2.3. How we use the consensus [CONS] - The produced shared random values needs to be readily available to + The produced shared random values need to be readily available to clients. For this reason we include them in the consensus documents. Every hour the consensus documents need to include the shared random value @@ -403,7 +403,7 @@ Tor works. This text used to be proposal 250-commit-reveal-consensus.txt. from the COMMIT message. We say that the COMMIT and REVEAL messages correspond, if the comparison was successful. - Pariticipants MUST also check that corresponding COMMIT and REVEAL values + Participants MUST also check that corresponding COMMIT and REVEAL values have the same timestamp value. Authorities should ignore reveal values during the Reveal Phase that don't @@ -578,7 +578,7 @@ Tor works. This text used to be proposal 250-commit-reveal-consensus.txt. different shared randomness value than the others. We claim that this attack is not particularly fruitful: Alice ends up - having two shared random values to chose from which is a fundamental + having two shared random values to choose from which is a fundamental problem of commit-and-reveal protocols as well (since the last person can always abort or reveal). The attacker can also sabotage the consensus, but there are other ways this can be done with the current voting system. @@ -587,7 +587,7 @@ Tor works. This text used to be proposal 250-commit-reveal-consensus.txt. First of all, it requires the authority to sabotage two consensuses which will cause quite some noise. Furthermore, the authority needs to send different votes to different auths which is detectable. Like the commit - phase attack, the detection here is to make sure that the commiment values + phase attack, the detection here is to make sure that the commitment values in a vote coming from an authority are always the same for each authority. 6. Discussion diff --git a/tor-spec.txt b/tor-spec.txt index 4b2c7f2..234d209 100644 --- a/tor-spec.txt +++ b/tor-spec.txt @@ -944,12 +944,12 @@ see tor-design.pdf. TIME (Timestamp) [4 bytes] OTHERADDR (Other OR's address) [variable] ATYPE (Address type) [1 byte] - ALEN (Adress length) [1 byte] + ALEN (Address length) [1 byte] AVAL (Address value in NBO) [ALEN bytes] NMYADDR (Number of this OR's addresses) [1 byte] NMYADDR times: ATYPE (Address type) [1 byte] - ALEN (Adress length) [1 byte] + ALEN (Address length) [1 byte] AVAL (Address value in NBO)) [ALEN bytes] Recognized address types (ATYPE) are: @@ -1684,10 +1684,14 @@ see tor-design.pdf. 14 -- RELAY_EXTEND2 [forward] [control] 15 -- RELAY_EXTENDED2 [backward] [control] + 16..18 -- Reserved for UDP; Not yet in use, see prop339. + 32..40 -- Used for hidden services; see rend-spec-{v2,v3}.txt. 41..42 -- Used for circuit padding; see Section 3 of padding-spec.txt. + 43..44 -- Used for flow control; see Section 4 of prop324. + Commands labelled as "forward" must only be sent by the originator of the circuit. Commands labelled as "backward" must only be sent by other nodes in the circuit back to the originator. Commands marked @@ -1849,7 +1853,7 @@ see tor-design.pdf. and relays MUST ignore the payload. In response to a RELAY_BEGIN_DIR cell, relays respond either with a - RELAY_CONNECTED cell on succcess, or a RELAY_END cell on failure. They + RELAY_CONNECTED cell on success, or a RELAY_END cell on failure. They MUST send a RELAY_CONNECTED cell all-zero payload, and clients MUST ignore the payload. @@ -2153,6 +2157,8 @@ see tor-design.pdf. 8.1. Memory exhaustion. + (See also dos-spec.md.) + If RAM becomes low, an OR should begin destroying circuits until more memory is free again. We recommend the following algorithm: @@ -2320,7 +2326,11 @@ see tor-design.pdf. "Relay=3". This subprotocol version is described in proposal 311, and - implemented in Tor 0.4.4.1-alpha. + implemented in Tor 0.4.5.1-alpha. + + "4" -- support the ntorv3 (version 3) key exchange and all features in + 0.4.7.3-alpha. This adds a new CREATE2 cell type. See proposal 332 + for more details. 9.4. "HSIntro" @@ -2363,7 +2373,7 @@ see tor-design.pdf. "1" -- supports all features in Tor 0.2.4.19. - "2" -- adds support for consensus diffs. + "2" -- adds support for consensus diffs in Tor 0.3.1.1-alpha. 9.8. "Desc" @@ -2423,3 +2433,15 @@ see tor-design.pdf. "1" -- supports authenticated circuit level SENDMEs as of proposal 289 in Tor 0.4.1.1-alpha. + + "2" -- supports congestion control by the Exits which implies a new SENDME + format and algorithm. See proposal 324 for more details. Advertised + in tor 0.4.7.3-alpha. + +9.13. "Datagram" + + Describes the UDP protocol capabilities of a relay. + + "1" -- [RESERVED] supports UDP by an Exit as in the relay command + CONNECT_UDP, CONNECTED_UDP and DATAGRAM. See proposal + 339 for more details. (Not yet advertised, reserved) |