diff options
| -rw-r--r-- | address-spec.txt | 2 | ||||
| -rw-r--r-- | control-spec.txt | 180 | ||||
| -rw-r--r-- | dir-spec.txt | 194 | ||||
| -rw-r--r-- | proposals/000-index.txt | 12 | ||||
| -rw-r--r-- | proposals/001-process.txt | 3 | ||||
| -rw-r--r-- | proposals/172-circ-getinfo-option.txt | 138 | ||||
| -rw-r--r-- | proposals/173-getinfo-option-expansion.txt | 101 | ||||
| -rw-r--r-- | proposals/174-optimistic-data-server.txt | 242 | ||||
| -rw-r--r-- | proposals/175-automatic-node-promotion.txt | 238 | ||||
| -rw-r--r-- | rend-spec.txt | 608 | ||||
| -rw-r--r-- | tor-fw-helper-spec.txt | 57 | ||||
| -rw-r--r-- | tor-spec.txt | 13 |
12 files changed, 1453 insertions, 335 deletions
diff --git a/address-spec.txt b/address-spec.txt index 2e1aff2..ce6d2b6 100644 --- a/address-spec.txt +++ b/address-spec.txt @@ -12,7 +12,7 @@ These hostnames can be passed to Tor as the address part of a SOCKS4a or SOCKS5 request. If the application is connected to Tor using an IP-only - method (such as SOCKS4, TransPort, or NatdPort), these hostnames can be + method (such as SOCKS4, TransPort, or NATDPort), these hostnames can be substituted for certain IP addresses using the MapAddress configuration option or the MAPADDRESS control command. diff --git a/control-spec.txt b/control-spec.txt index 5a68864..e8a314c 100644 --- a/control-spec.txt +++ b/control-spec.txt @@ -92,36 +92,39 @@ 2.4. General-use tokens - ; CRLF means, "the ASCII Carriage Return character (decimal value value 13) + ; CRLF means, "the ASCII Carriage Return character (decimal value 13) ; followed by the ASCII Linefeed character (decimal value 10)." CRLF = CR LF - ; Identifiers for servers. - ServerID = Nickname / Fingerprint - - Nickname = 1*19 NicknameChar - NicknameChar = "a"-"z" / "A"-"Z" / "0" - "9" - Fingerprint = "$" 40*HEXDIG - - ; A "=" indicates that the given nickname is canonical; a "~" indicates - ; that the given nickname is not canonical. If no nickname is given at - ; all, Tor does not even have a guess for what this router calls itself. - LongName = Fingerprint [ ( "=" / "~" ) Nickname ] - ; How a controller tells Tor about a particular OR. There are four ; possible formats: - ; $Digest -- The router whose identity key hashes to the given digest. + ; $Fingerprint -- The router whose identity key hashes to the fingerprint. ; This is the preferred way to refer to an OR. - ; $Digest~Name -- The router whose identity key hashes to the given - ; digest, but only if the router has the given nickname. - ; $Digest=Name -- The router whose identity key hashes to the given - ; digest, but only if the router is Named and has the given + ; $Fingerprint~Nickname -- The router whose identity key hashes to the + ; given fingerprint, but only if the router has the given nickname. + ; $Fingerprint=Nickname -- The router whose identity key hashes to the + ; given fingerprint, but only if the router is Named and has the given ; nickname. - ; Name -- The Named router with the given nickname, or, if no such + ; Nickname -- The Named router with the given nickname, or, if no such ; router exists, any router whose nickname matches the one given. ; This is not a safe way to refer to routers, since Named status ; could under some circumstances change over time. + ; + ; The tokens that implement the above follow: + ServerSpec = LongName / Nickname + LongName = Fingerprint [ ( "=" / "~" ) Nickname ] + + Fingerprint = "$" 40*HEXDIG + NicknameChar = "a"-"z" / "A"-"Z" / "0" - "9" + Nickname = 1*19 NicknameChar + + ; What follows is an outdated way to refer to ORs. + ; Feature VERBOSE_NAMES replaces ServerID with LongName in events and + ; GETINFO results. VERBOSE_NAMES can be enabled starting in Tor version + ; 0.1.2.2-alpha and it is always-on in 0.2.2.1-alpha and later. + ServerID = Nickname / Fingerprint + ; Unique identifiers for streams or circuits. Currently, Tor only ; uses digits, but this may change @@ -228,7 +231,7 @@ "INFO" / "NOTICE" / "WARN" / "ERR" / "NEWDESC" / "ADDRMAP" / "AUTHDIR_NEWDESCS" / "DESCCHANGED" / "STATUS_GENERAL" / "STATUS_CLIENT" / "STATUS_SERVER" / "GUARD" / "NS" / "STREAM_BW" / - "CLIENTS_SEEN" / "NEWCONSENSUS" / "BUILDTIMEOUT_SET" + "CLIENTS_SEEN" / "NEWCONSENSUS" / "BUILDTIMEOUT_SET" / "SIGNAL" Any events *not* listed in the SETEVENTS line are turned off; thus, sending SETEVENTS with an empty body turns off all event reporting. @@ -477,25 +480,36 @@ StreamID SP StreamStatus SP CircID SP Target CRLF "orconn-status" - A series of lines as for an OR connection status event. Each is of the - form: + A series of lines as for an OR connection status event. In Tor + 0.1.2.2-alpha with feature VERBOSE_NAMES enabled and in Tor + 0.2.2.1-alpha and later by default, each line is of the form: + LongName SP ORStatus CRLF + + In Tor versions 0.1.2.2-alpha through 0.2.2.1-alpha with feature + VERBOSE_NAMES turned off and before version 0.1.2.2-alpha, each line + is of the form: ServerID SP ORStatus CRLF "entry-guards" A series of lines listing the currently chosen entry guards, if any. - Each is of the form: - ServerID2 SP Status [SP ISOTime] CRLF - - Status-with-time = ("unlisted") SP ISOTime - Status = ("up" / "never-connected" / "down" / - "unusable" / "unlisted" ) + In Tor 0.1.2.2-alpha with feature VERBOSE_NAMES enabled and in Tor + 0.2.2.1-alpha and later by default, each line is of the form: + LongName SP Status [SP ISOTime] CRLF + In Tor versions 0.1.2.2-alpha through 0.2.2.1-alpha with feature + VERBOSE_NAMES turned off and before version 0.1.2.2-alpha, each line + is of the form: + ServerID2 SP Status [SP ISOTime] CRLF ServerID2 = Nickname / 40*HEXDIG - [From 0.1.1.4-alpha to 0.1.1.10-alpha, this was called "helper-nodes". - Tor still supports calling it that for now, but support will be - removed in 0.1.3.x.] + The definition of Status is the same for both: + Status = "up" / "never-connected" / "down" / + "unusable" / "unlisted" + [From 0.1.1.4-alpha to 0.1.1.10-alpha, entry-guards was called + "helper-nodes". Tor still supports calling "helper-nodes", but it + is deprecated and should not be used.] + [Older versions of Tor (before 0.1.2.x-final) generated 'down' instead of unlisted/unusable. Current Tors never generate 'down'.] @@ -525,9 +539,9 @@ of the form: OptionName SP OptionType [ SP Documentation ] CRLF OptionName = Keyword - OptionType = "Integer" / "TimeInterval" / "DataSize" / "Float" / - "Boolean" / "Time" / "CommaList" / "Dependant" / "Virtual" / - "String" / "LineList" + OptionType = "Integer" / "TimeInterval" / "TimeMsecInterval" / + "DataSize" / "Float" / "Boolean" / "Time" / "CommaList" / + "Dependant" / "Virtual" / "String" / "LineList" Documentation = Text "info/names" @@ -770,46 +784,47 @@ 3.19. USEFEATURE + Adding additional features to the control protocol sometimes will break + backwards compatibility. Initially such features are added into Tor and + disabled by default. USEFEATURE can enable these additional features. + The syntax is: "USEFEATURE" *(SP FeatureName) CRLF FeatureName = 1*(ALPHA / DIGIT / "_" / "-") - Sometimes extensions to the controller protocol break compatibility with - older controllers. In this case, whenever possible, the extensions are - first included in Tor disabled by default, and only enabled on a given - controller connection when the "USEFEATURE" command is given. Once a - "USEFEATURE" command is given, it applies to all subsequent interactions on - the same connection; to disable an enabled feature, a new controller - connection must be opened. + Feature names are case-insensitive. - This is a forward-compatibility mechanism; each feature will eventually - become a regular part of the control protocol in some future version of Tor. - Tor will ignore a request to use any feature that is already on by default. - Tor will give a "552" error if any requested feature is not recognized. + Once enabled, a feature stays enabled for the duration of the connection + to the controller. A new connection to the controller must be opened to + disable an enabled feature. - Feature names are case-insensitive. + Features are a forward-compatibility mechanism; each feature will eventually + become a standard part of the control protocol. Once a feature becomes part + of the protocol, it is always-on. Each feature documents the version it was + introduced as a feature and the version in which it became part of the + protocol. + + Tor will ignore a request to use any feature that is always-on. Tor will give + a 552 error in response to an unrecognized feature. EXTENDED_EVENTS Same as passing 'EXTENDED' to SETEVENTS; this is the preferred way to request the extended event syntax. - This feature was first used in 0.1.2.3-alpha. It is always-on in - Tor 0.2.2.1-alpha and later. + This feature was first introduced in 0.1.2.3-alpha. It is always-on + and part of the protocol in Tor 0.2.2.1-alpha and later. VERBOSE_NAMES - Instead of ServerID as specified above, the controller should - identify ORs by LongName in events and GETINFO results. This format is - strictly more informative: rather than including Nickname for - known Named routers and Fingerprint for unknown or unNamed routers, the - LongName format includes a Fingerprint, an indication of Named status, - and a Nickname (if one is known). + Replaces ServerID with LongName in events and GETINFO results. LongName + provides a Fingerprint for all routers, an indication of Named status, + and a Nickname if one is known. LongName is strictly more informative + than ServerID, which only provides either a Fingerprint or a Nickname. - This will not be always-enabled until at least two stable - releases after 0.1.2.2-alpha, the release where it was first - available. It is always-on in Tor 0.2.2.1-alpha and later. + This feature was first introduced in 0.1.2.2-alpha. It is always-on and + part of the protocol in Tor 0.2.2.1-alpha and later. 3.20. RESOLVE @@ -1000,12 +1015,17 @@ "FAILED" / ; circuit closed (was not built) "CLOSED" ; circuit closed (was built) - Path = ServerID *("," ServerID) + Path = LongName *("," LongName) + ; In Tor versions 0.1.2.2-alpha through 0.2.2.1-alpha with feature + ; VERBOSE_NAMES turned off and before version 0.1.2.2-alpha, Path + ; is as follows: + Path = ServerID *("," ServerID) Reason = "NONE" / "TORPROTOCOL" / "INTERNAL" / "REQUESTED" / "HIBERNATING" / "RESOURCELIMIT" / "CONNECTFAILED" / "OR_IDENTITY" / "OR_CONN_CLOSED" / "TIMEOUT" / - "FINISHED" / "DESTROYED" / "NOPATH" / "NOSUCHSERVICE" + "FINISHED" / "DESTROYED" / "NOPATH" / "NOSUCHSERVICE" / + "MEASUREMENT_EXPIRED" The path is provided only when the circuit has been extended at least one hop. @@ -1049,7 +1069,7 @@ Reason = "MISC" / "RESOLVEFAILED" / "CONNECTREFUSED" / "EXITPOLICY" / "DESTROY" / "DONE" / "TIMEOUT" / - "HIBERNATING" / "INTERNAL"/ "RESOURCELIMIT" / + "NOROUTE" / "HIBERNATING" / "INTERNAL"/ "RESOURCELIMIT" / "CONNRESET" / "TORPROTOCOL" / "NOTDIRECTORY" / "END" The "REASON" field is provided only for FAILED, CLOSED, and DETACHED @@ -1088,19 +1108,26 @@ 4.1.3. OR Connection status changed The syntax is: - "650" SP "ORCONN" SP (ServerID / Target) SP ORStatus [ SP "REASON=" + + "650" SP "ORCONN" SP (LongName / Target) SP ORStatus [ SP "REASON=" Reason ] [ SP "NCIRCS=" NumCircuits ] CRLF ORStatus = "NEW" / "LAUNCHED" / "CONNECTED" / "FAILED" / "CLOSED" + ; In Tor versions 0.1.2.2-alpha through 0.2.2.1-alpha with feature + ; VERBOSE_NAMES turned off and before version 0.1.2.2-alpha, OR + ; Connection is as follows: + "650" SP "ORCONN" SP (ServerID / Target) SP ORStatus [ SP "REASON=" + Reason ] [ SP "NCIRCS=" NumCircuits ] CRLF + NEW is for incoming connections, and LAUNCHED is for outgoing connections. CONNECTED means the TLS handshake has finished (in either direction). FAILED means a connection is being closed that hasn't finished its handshake, and CLOSED is for connections that have handshaked. - A ServerID is specified unless it's a NEW connection, in which - case we don't know what server it is yet, so we use Address:Port. + A LongName or ServerID is specified unless it's a NEW connection, in + which case we don't know what server it is yet, so we use Address:Port. If extended events are enabled (see 3.19), optional reason and circuit counting information is provided for CLOSED and FAILED @@ -1137,7 +1164,11 @@ 4.1.6. New descriptors available Syntax: - "650" SP "NEWDESC" 1*(SP ServerID) CRLF + "650" SP "NEWDESC" 1*(SP LongName) CRLF + ; In Tor versions 0.1.2.2-alpha through 0.2.2.1-alpha with feature + ; VERBOSE_NAMES turned off and before version 0.1.2.2-alpha, it + ; is as follows: + "650" SP "NEWDESC" 1*(SP ServerID) CRLF 4.1.7. New Address mapping @@ -1707,6 +1738,27 @@ [First added in 0.2.2.7-alpha] +4.1.17. Signal received + + The syntax is: + "650" SP "SIGNAL" SP Signal CRLF + + Signal = "RELOAD" / "DUMP" / "DEBUG" / "NEWNYM" / "CLEARDNSCACHE" + + A signal has been received and actions taken by Tor. The meaning of each + signal, and the mapping to Unix signals, is as defined in section 3.7. + Future versions of Tor MAY generate signals other than those listed here; + controllers MUST be able to accept them. + + If Tor chose to ignore a signal (such as NEWNYM), this event will not be + sent. Note that some options (like ReloadTorrcOnSIGHUP) may affect the + semantics of the signals here. + + Note that the HALT (SIGTERM) and SHUTDOWN (SIGINT) signals do not currently + generate any event. + + [First added in 0.2.3.1-alpha] + 5. Implementation notes 5.1. Authentication diff --git a/dir-spec.txt b/dir-spec.txt index a5abdf0..1498437 100644 --- a/dir-spec.txt +++ b/dir-spec.txt @@ -530,16 +530,8 @@ dns logic. Versions of Tor with this field set to false SHOULD NOT be used for reverse hostname lookups. - [All versions of Tor before 0.1.2.2-alpha should be assumed to have - this option set to 0 if it is not present. All Tor versions at - 0.1.2.2-alpha or later should be assumed to have this option set to - 1 if it is not present. Until 0.1.2.1-alpha-dev, this option was - not generated, even when the new DNS code was in use. Versions of Tor - before 0.1.2.1-alpha-dev did not parse this option, so it should be - marked "opt". The dnsworker logic has been removed, so this option - should not be used by new server code. However, it can still be - used, and should still be recognized by new code until Tor 0.1.2.x - is obsolete.] + [This option is obsolete. All Tor current servers should be presumed + to have the evdns backend.] "caches-extra-info" NL @@ -630,6 +622,12 @@ As documented in 2.1 above. See migration notes in section 2.2.1. + "geoip-db-digest" Digest NL + [At most once.] + + SHA1 digest of the GeoIP database file that is used to resolve IP + addresses to country codes. + ("geoip-start" YYYY-MM-DD HH:MM:SS NL) ("geoip-client-origins" CC=N,CC=N,... NL) @@ -779,6 +777,17 @@ had a smaller bandwidth than md, the other half had a larger bandwidth than md. + "dirreq-read-history" YYYY-MM-DD HH:MM:SS (NSEC s) NUM,NUM,NUM... NL + [At most once] + "dirreq-write-history" YYYY-MM-DD HH:MM:SS (NSEC s) NUM,NUM,NUM... NL + [At most once] + + Declare how much bandwidth the OR has spent on answering directory + requests. Usage is divided into intervals of NSEC seconds. The + YYYY-MM-DD HH:MM:SS field defines the end of the most recent + interval. The numbers are the number of bytes used in the most + recent intervals, ordered from oldest to newest. + "entry-stats-end" YYYY-MM-DD HH:MM:SS (NSEC s) NL [At most once.] @@ -839,6 +848,20 @@ Mean number of circuits that are included in any of the deciles, rounded up to the next integer. + "conn-bi-direct" YYYY-MM-DD HH:MM:SS (NSEC s) BELOW,READ,WRITE,BOTH NL + [At most once] + + Number of connections, split into 10-second intervals, that are + used uni-directionally or bi-directionally as observed in the NSEC + seconds (usually 86400 seconds) before YYYY-MM-DD HH:MM:SS. Every + 10 seconds, we determine for every connection whether we read and + wrote less than a threshold of 20 KiB (BELOW), read at least 10 + times more than we wrote (READ), wrote at least 10 times more than + we read (WRITE), or read and wrote more than the threshold, but + not 10 times more in either direction (BOTH). After classifying a + connection, read and write counters are reset for the next + 10-second interval. + "exit-stats-end" YYYY-MM-DD HH:MM:SS (NSEC s) NL [At most once.] @@ -1137,15 +1160,15 @@ Parameters ::= Parameter | Parameters SP Parameter The parameters list, if present, contains a space-separated list of - key-value pairs, sorted in lexical order by their keyword. Each - parameter has its own meaning. + case-sensitive key-value pairs, sorted in lexical order by + their keyword. Each parameter has its own meaning. (Only included when the vote is generated with consensus-method 7 or later.) Commonly used "param" arguments at this point include: - "CircWindow" -- the default package window that circuits should + "circwindow" -- the default package window that circuits should be established with. It started out at 1000 cells, but some research indicates that a lower value would mean fewer cells in transit in the network at any given time. Obeyed by Tor 0.2.1.20 @@ -1157,6 +1180,25 @@ and 0.2.2.10-alpha recognized a "CircPriorityHalflifeMsec" parameter, but mishandled it badly.) + "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 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 bwconnburst, but then + did the wrong thing with them; see bug 1830 for details.) + + "refuseunknownexits" -- if set and non-zero, exit relays look at + the previous hop of circuits that ask to open an exit stream, + and refuse to exit if they don't recognize it as a relay. The + goal is to make it harder for people to use them as one-hop + proxies. See trac entry 1751 for details. + + See also "2.4.5. Consensus parameters governing behavior" + in path-spec.txt for a series of circuit build time related + consensus params. + The authority section of a vote contains the following items, followed in turn by the authority's current key certificate: @@ -1351,9 +1393,9 @@ Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes - Wbg - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests - Wbm - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests - Wbe - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests + Wbg - Weight for Guard flagged nodes for BEGIN_DIR requests + Wbm - Weight for non-flagged nodes for BEGIN_DIR requests + Wbe - Weight for Exit-flagged nodes for BEGIN_DIR requests Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests These values are calculated as specified in Section 3.4.3. @@ -1608,6 +1650,7 @@ "7" -- Provides keyword=integer pairs of consensus parameters "8" -- Provides microdescriptor summaries "9" -- Provides weights for selecting flagged routers in paths + "10" -- Fixes edge case bugs in router flag selection weights Before generating a consensus, an authority must decide which consensus method to use. To do this, it looks for the highest version number @@ -1670,22 +1713,25 @@ Wme*E + Wee*E == E (aka: Wee = 1-Wme) We are short 2 constraints with the above set. The remaining constraints - come from examining different cases of network load. + come from examining different cases of network load. The following + constraints are used in consensus method 10 and above. There are another + incorrect and obsolete set of constraints used for these same cases in + consensus method 9. For those, see dir-spec.txt in Tor 0.2.2.10-alpha + to 0.2.2.16-alpha. Case 1: E >= T/3 && G >= T/3 (Neither Exit nor Guard Scarce) - In this case, the additional two constraints are: Wme*E == Wmd*D and - Wgd == 0, which maximizes Exit-flagged bandwidth in the middle position. + In this case, the additional two constraints are: Wmg == Wmd, + Wed == 1/3. This leads to the solution: - - Wgg = (weight_scale*(D+E+G+M))/(3*G) - Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D) - Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E) - Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E) - Wmg = weight_scale - Wgg - Wed = weight_scale - Wmd - Wgd = 0 + Wgd = weight_scale/3 + Wed = weight_scale/3 + Wmd = weight_scale/3 + Wee = (weight_scale*(E+G+M))/(3*E) + Wme = weight_scale - Wee + Wmg = (weight_scale*(2*G-E-M))/(3*G) + Wgg = weight_scale - Wmg Case 2: E < T/3 && G < T/3 (Both are scarce) @@ -1709,25 +1755,35 @@ Subcase b: R+D >= S In this case, if M <= T/3, we have enough bandwidth to try to achieve - a balancing condition, and add the constraints Wgg == 1 and - Wme*E == Wmd*D: + a balancing condition. - Wgg = weight_scale - Wgd = (weight_scale*(D + E - 2*G + M))/(3*D) (T/3 >= G (Ok)) - Wmd = (weight_scale*(D + E + G - 2*M))/(6*D) (T/3 >= M) - Wme = (weight_scale*(D + E + G - 2*M))/(6*E) - Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E) (2E+M >= T/3) - Wmg = 0; - Wed = weight_scale - Wgd - Wmd + Add constraints Wgg = 1, Wmd == Wgd to maximize bandwidth in the guard + position while still allowing exits to be used as middle nodes: + + Wee = (weight_scale*(E - G + M))/E + Wed = (weight_scale*(D - 2*E + 4*G - 2*M))/(3*D) + Wme = (weight_scale*(G-M))/E + Wmg = 0 + Wgg = weight_scale + Wmd = (weight_scale - Wed)/2 + Wgd = (weight_scale - Wed)/2 - If M >= T/3, the above solution will not be valid (one of the weights - will be < 0 or > 1). In this case, we use: + If this system ends up with any values out of range (ie negative, or + above weight_scale), use the constraints Wgg == 1 and Wee == 1, since + both those positions are scarce: Wgg = weight_scale Wee = weight_scale - Wmg = Wme = Wmd = 0 - Wgd = (weight_scale*(D+E-G))/(2*D) - Wed = weight_scale - Wgd + Wed = (weight_scale*(D - 2*E + G + M))/(3*D) + Wmd = (weight_Scale*(D - 2*M + G + E))/(3*D) + Wme = 0 + Wmg = 0 + Wgd = weight_scale - Wed - Wmd + + If M > T/3, then the Wmd weight above will become negative. Set it to 0 + in this case: + Wmd = 0 + Wgd = weight_scale - Wed Case 3: One of E < T/3 or G < T/3 @@ -1735,36 +1791,44 @@ Subcase a: (S+D) < T/3: if G=S: - Wgg = Wgd = weight_scale; - Wmd = Wed = Wmg = 0; - Wme = (weight_scale*(E-M))/(2*E); - Wee = weight_scale-Wme; + Wgg = Wgd = weight_scale; + Wmd = Wed = Wmg = 0; + // Minor subcase, if E is more scarce than M, + // keep its bandwidth in place. + if (E < M) Wme = 0; + else Wme = (weight_scale*(E-M))/(2*E); + Wee = weight_scale-Wme; if E=S: - Wee = Wed = weight_scale; - Wmd = Wgd = Wmg = 0; - Wmg = (weight_scale*(G-M))/(2*G); - Wgg = weight_scale-Wmg; + Wee = Wed = weight_scale; + Wmd = Wgd = Wme = 0; + // Minor subcase, if G is more scarce than M, + // keep its bandwidth in place. + if (G < M) Wmg = 0; + else Wmg = (weight_scale*(G-M))/(2*G); + Wgg = weight_scale-Wmg; Subcase b: (S+D) >= T/3 if G=S: - Add constraints Wmg = 0, Wme*E == Wmd*D to maximize exit bandwidth - in the middle position: - Wgd = (weight_scale*(D + E - 2*G + M))/(3*D); - Wmd = (weight_scale*(D + E + G - 2*M))/(6*D); - Wme = (weight_scale*(D + E + G - 2*M))/(6*E); - Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E); - Wgg = weight_scale; - Wmg = 0; - Wed = weight_scale - Wgd - Wmd; + Add constraints Wgg = 1, Wmd == Wed to maximize bandwidth + in the guard position, while still allowing exits to be + used as middle nodes: + Wgg = weight_scale + Wgd = (weight_scale*(D - 2*G + E + M))/(3*D) + Wmg = 0 + Wee = (weight_scale*(E+M))/(2*E) + Wme = weight_scale - Wee + Wmd = (weight_scale - Wgd)/2 + Wed = (weight_scale - Wgd)/2 if E=S: - Add constraints Wgd = 0, Wme*E == Wmd*D: - Wgg = (weight_scale*(D + E + G + M))/(3*G); - Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D); - Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E); - Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E); - Wgd = 0; + Add constraints Wee == 1, Wmd == Wgd to maximize bandwidth + in the exit position: + Wee = weight_scale; + Wed = (weight_scale*(D - 2*E + G + M))/(3*D); + Wme = 0; + Wgg = (weight_scale*(G+M))/(2*G); Wmg = weight_scale - Wgg; - Wed = weight_scale - Wmd; + Wmd = (weight_scale - Wed)/2; + Wgd = (weight_scale - Wed)/2; To ensure consensus, all calculations are performed using integer math with a fixed precision determined by the bwweightscale consensus diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 1009b6b..9fa2868 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -91,7 +91,11 @@ Proposals by number: 168 Reduce default circuit window [OPEN] 169 Eliminate TLS renegotiation for the Tor connection handshake [DRAFT] 170 Configuration options regarding circuit building [DRAFT] -171 Separate streams across circuits by destination port or destination host [DRAFT] +171 Separate streams across circuits by connection metadata [OPEN] +172 GETINFO controller option for circuit information [ACCEPTED] +173 GETINFO Option Expansion [ACCEPTED] +174 Optimistic Data for Tor: Server Side [OPEN] +175 Automatically promoting Tor clients to nodes [DRAFT] Proposals by status: @@ -104,7 +108,7 @@ Proposals by status: 144 Increase the diversity of circuits by detecting nodes belonging the same provider 169 Eliminate TLS renegotiation for the Tor connection handshake [for 0.2.2] 170 Configuration options regarding circuit building - 171 Separate streams across circuits by destination port or destination host + 175 Automatically promoting Tor clients to nodes NEEDS-REVISION: 131 Help users to verify they are using Tor OPEN: @@ -120,6 +124,8 @@ Proposals by status: 164 Reporting the status of server votes [for 0.2.2] 165 Easy migration for voting authority sets 168 Reduce default circuit window [for 0.2.2] + 171 Separate streams across circuits by connection metadata + 174 Optimistic Data for Tor: Server Side ACCEPTED: 110 Avoiding infinite length circuits [for 0.2.1.x] [in 0.2.1.3-alpha] 117 IPv6 exits [for 0.2.1.x] @@ -128,6 +134,8 @@ Proposals by status: 147 Eliminate the need for v2 directories in generating v3 directories [for 0.2.1.x] 157 Make certificate downloads specific [for 0.2.1.x] 166 Including Network Statistics in Extra-Info Documents [for 0.2.2] + 172 GETINFO controller option for circuit information + 173 GETINFO Option Expansion META: 000 Index of Tor Proposals 001 The Tor Proposal Process diff --git a/proposals/001-process.txt b/proposals/001-process.txt index e35215e..53ad32b 100644 --- a/proposals/001-process.txt +++ b/proposals/001-process.txt @@ -127,7 +127,8 @@ What should go in a proposal: Implementation: If the proposal will be tricky to implement in Tor's current architecture, the document can contain some discussion of how - to go about making it work. + to go about making it work. Actual patches should go on public git + branches, or be uploaded to trac. Performance and scalability notes: If the feature will have an effect on performance (in RAM, CPU, bandwidth) or scalability, there should diff --git a/proposals/172-circ-getinfo-option.txt b/proposals/172-circ-getinfo-option.txt new file mode 100644 index 0000000..b7fd79c --- /dev/null +++ b/proposals/172-circ-getinfo-option.txt @@ -0,0 +1,138 @@ +Filename: 172-circ-getinfo-option.txt +Title: GETINFO controller option for circuit information +Author: Damian Johnson +Created: 03-June-2010 +Status: Accepted + +Overview: + + This details an additional GETINFO option that would provide information + concerning a relay's current circuits. + +Motivation: + + The original proposal was for connection related information, but Jake make + the excellent point that any information retrieved from the control port + is... + + 1. completely ineffectual for auditing purposes since either (a) these + results can be fetched from netstat already or (b) the information would + only be provided via tor and can't be validated. + + 2. The more useful uses for connection information can be achieved with + much less (and safer) information. + + Hence the proposal is now for circuit based rather than connection based + information. This would strip the most controversial and sensitive data + entirely (ip addresses, ports, and connection based bandwidth breakdowns) + while still being useful for the following purposes: + + - Basic Relay Usage Questions + How is the bandwidth I'm contributing broken down? Is it being evenly + distributed or is someone hogging most of it? Do these circuits belong to + the hidden service I'm running or something else? Now that I'm using exit + policy X am I desirable as an exit, or are most people just using me as a + relay? + + - Debugging + Say a relay has a restrictive firewall policy for outbound connections, + with the ORPort whitelisted but doesn't realize that tor needs random high + ports. Tor would report success ("your orport is reachable - excellent") + yet the relay would be nonfunctional. This proposed information would + reveal numerous RELAY -> YOU -> UNESTABLISHED circuits, giving a good + indicator of what's wrong. + + - Visualization + A nice benefit of visualizing tor's behavior is that it becomes a helpful + tool in puzzling out how tor works. For instance, tor spawns numerous + client connections at startup (even if unused as a client). As a newcomer + to tor these asymmetric (outbound only) connections mystified me for quite + a while until until Roger explained their use to me. The proposed + TYPE_FLAGS would let controllers clearly label them as being client + related, making their purpose a bit clearer. + + At the moment connection data can only be retrieved via commands like + netstat, ss, and lsof. However, providing an alternative via the control + port provides several advantages: + + - scrubbing for private data + Raw connection data has no notion of what's sensitive and what is + not. The relay's flags and cached consensus can be used to take + educated guesses concerning which connections could possibly belong + to client or exit traffic, but this is both difficult and inaccurate. + Anything provided via the control port can scrubbed to make sure we + aren't providing anything we think relay operators should not see. + + - additional information + All connection querying commands strictly provide the ip address and + port of connections, and nothing else. However, for the uses listed + above the far more interesting attributes are the circuit's type, + bandwidth usage and uptime. + + - improved performance + Querying connection data is an expensive activity, especially for + busy relays or low end processors (such as mobile devices). Tor + already internally knows its circuits, allowing for vastly quicker + lookups. + + - cross platform capability + The connection querying utilities mentioned above not only aren't + available under Windows, but differ widely among different *nix + platforms. FreeBSD in particular takes a very unique approach, + dropping important options from netstat and assigning ss to a + spreadsheet application instead. A controller interface, however, + would provide a uniform means of retrieving this information. + +Security Implications: + + This is an open question. This proposal lacks the most controversial pieces + of information (ip addresses and ports) and insight into potential threats + this would pose would be very welcomed! + +Specification: + + The following addition would be made to the control-spec's GETINFO section: + + "rcirc/id/<Circuit identity>" -- Provides entry for the associated relay + circuit, formatted as: + CIRC_ID=<circuit ID> CREATED=<timestamp> UPDATED=<timestamp> TYPE=<flag> + READ=<bytes> WRITE=<bytes> + + none of the parameters contain whitespace, and additional results must be + ignored to allow for future expansion. Parameters are defined as follows: + CIRC_ID - Unique numeric identifier for the circuit this belongs to. + CREATED - Unix timestamp (as seconds since the Epoch) for when the + circuit was created. + UPDATED - Unix timestamp for when this information was last updated. + TYPE - Single character flags indicating attributes in the circuit: + (E)ntry : has a connection that doesn't belong to a known Tor server, + indicating that this is either the first hop or bridged + E(X)it : has been used for at least one exit stream + (R)elay : has been extended + Rende(Z)vous : is being used for a rendezvous point + (I)ntroduction : is being used for a hidden service introduction + (N)one of the above: none of the above have happened yet. + READ - Total bytes transmitted toward the exit over the circuit. + WRITE - Total bytes transmitted toward the client over the circuit. + + "rcirc/all" -- The 'rcirc/id/*' output for all current circuits, joined by + newlines. + + The following would be included for circ info update events. + +4.1.X. Relay circuit status changed + + The syntax is: + "650" SP "RCIRC" SP CircID SP Notice [SP Created SP Updated SP Type SP + Read SP Write] CRLF + + Notice = + "NEW" / ; first information being provided for this circuit + "UPDATE" / ; update for a previously reported circuit + "CLOSED" ; notice that the circuit no longer exists + + Notice indicating that queryable information on a relay related circuit has + changed. If the Notice parameter is either "NEW" or "UPDATE" then this + provides the same fields that would be given by calling "GETINFO rcirc/id/" + with the CircID. + diff --git a/proposals/173-getinfo-option-expansion.txt b/proposals/173-getinfo-option-expansion.txt new file mode 100644 index 0000000..03e18ef --- /dev/null +++ b/proposals/173-getinfo-option-expansion.txt @@ -0,0 +1,101 @@ +Filename: 173-getinfo-option-expansion.txt +Title: GETINFO Option Expansion +Author: Damian Johnson +Created: 02-June-2010 +Status: Accepted + +Overview: + + Over the course of developing arm there's been numerous hacks and + workarounds to gleam pieces of basic, desirable information about the tor + process. As per Roger's request I've compiled a list of these pain points + to try and improve the control protocol interface. + +Motivation: + + The purpose of this proposal is to expose additional process and relay + related information that is currently unavailable in a convenient, + dependable, and/or platform independent way. Examples of this are... + + - The relay's total contributed bandwidth. This is a highly requested + piece of information and, based on the following patch from pipe, looks + trivial to include. + http://www.mail-archive.com/or-talk@freehaven.net/msg13085.html + + - The process ID of the tor process. There is a high degree of guess work + in obtaining this. Arm for instance uses pidof, netstat, and ps yet + still fails on some platforms, and Orbot recently got a ticket about + its own attempt to fetch it with ps: + https://trac.torproject.org/projects/tor/ticket/1388 + + This just includes the pieces of missing information I've noticed + (suggestions or questions of their usefulness are welcome!). + +Security Implications: + + None that I'm aware of. From a security standpoint this seems decently + innocuous. + +Specification: + + The following addition would be made to the control-spec's GETINFO section: + + "relay/bw-limit" -- Effective relayed bandwidth limit. + + "relay/burst-limit" -- Effective relayed burst limit. + + "relay/read-total" -- Total bytes relayed (download). + + "relay/write-total" -- Total bytes relayed (upload). + + "relay/flags" -- Space separated listing of flags currently held by the + relay as repored by the currently cached consensus. + + "process/user" -- Username under which the tor process is running, + providing an empty string if none exists. + + "process/pid" -- Process id belonging to the main tor process, -1 if none + exists for the platform. + + "process/uptime" -- Total uptime of the tor process (in seconds). + + "process/uptime-reset" -- Time since last reset (startup, sighup, or RELOAD + signal, in seconds). + + "process/descriptors-used" -- Count of file descriptors used. + + "process/descriptor-limit" -- File descriptor limit (getrlimit results). + + "ns/authority" -- Router status info (v2 directory style) for all + recognized directory authorities, joined by newlines. + + "state/names" -- A space-separated list of all the keys supported by this + version of Tor's state. + + "state/val/<key>" -- Provides the current state value belonging to the + given key. If undefined, this provides the key's default value. + + "status/ports-seen" -- A summary of which ports we've seen connections + circuits connect to recently, formatted the same as the EXITS_SEEN status + event described in Section 4.1.XX. This GETINFO option is currently + available only for exit relays. + +4.1.XX. Per-port exit stats + + The syntax is: + "650" SP "EXITS_SEEN" SP TimeStarted SP PortSummary CRLF + + We just generated a new summary of which ports we've seen exiting circuits + connecting to recently. The controller could display this for the user, e.g. + in their "relay" configuration window, to give them a sense of how they're + being used (popularity of the various ports they exit to). Currently only + exit relays will receive this event. + + TimeStarted is a quoted string indicating when the reported summary + counts from (in GMT). + + The PortSummary keyword has as its argument a comma-separated, possibly + empty set of "port=count" pairs. For example (without linebreak), + 650-EXITS_SEEN TimeStarted="2008-12-25 23:50:43" + PortSummary=80=16,443=8 + diff --git a/proposals/174-optimistic-data-server.txt b/proposals/174-optimistic-data-server.txt new file mode 100644 index 0000000..d97c45e --- /dev/null +++ b/proposals/174-optimistic-data-server.txt @@ -0,0 +1,242 @@ +Filename: 174-optimistic-data-server.txt +Title: Optimistic Data for Tor: Server Side +Author: Ian Goldberg +Created: 2-Aug-2010 +Status: Open + +Overview: + +When a SOCKS client opens a TCP connection through Tor (for an HTTP +request, for example), the query latency is about 1.5x higher than it +needs to be. Simply, the problem is that the sequence of data flows +is this: + +1. The SOCKS client opens a TCP connection to the OP +2. The SOCKS client sends a SOCKS CONNECT command +3. The OP sends a BEGIN cell to the Exit +4. The Exit opens a TCP connection to the Server +5. The Exit returns a CONNECTED cell to the OP +6. The OP returns a SOCKS CONNECTED notification to the SOCKS client +7. The SOCKS client sends some data (the GET request, for example) +8. The OP sends a DATA cell to the Exit +9. The Exit sends the GET to the server +10. The Server returns the HTTP result to the Exit +11. The Exit sends the DATA cells to the OP +12. The OP returns the HTTP result to the SOCKS client + +Note that the Exit node knows that the connection to the Server was +successful at the end of step 4, but is unable to send the HTTP query to +the server until step 9. + +This proposal (as well as its upcoming sibling concerning the client +side) aims to reduce the latency by allowing: +1. SOCKS clients to optimistically send data before they are notified + that the SOCKS connection has completed successfully +2. OPs to optimistically send DATA cells on streams in the CONNECT_WAIT + state +3. Exit nodes to accept and queue DATA cells while in the + EXIT_CONN_STATE_CONNECTING state + +This particular proposal deals with #3. + +In this way, the flow would be as follows: + +1. The SOCKS client opens a TCP connection to the OP +2. The SOCKS client sends a SOCKS CONNECT command, followed immediately + by data (such as the GET request) +3. The OP sends a BEGIN cell to the Exit, followed immediately by DATA + cells +4. The Exit opens a TCP connection to the Server +5. The Exit returns a CONNECTED cell to the OP, and sends the queued GET + request to the Server +6. The OP returns a SOCKS CONNECTED notification to the SOCKS client, + and the Server returns the HTTP result to the Exit +7. The Exit sends the DATA cells to the OP +8. The OP returns the HTTP result to the SOCKS client + +Motivation: + +This change will save one OP<->Exit round trip (down to one from two). +There are still two SOCKS Client<->OP round trips (negligible time) and +two Exit<->Server round trips. Depending on the ratio of the +Exit<->Server (Internet) RTT to the OP<->Exit (Tor) RTT, this will +decrease the latency by 25 to 50 percent. Experiments validate these +predictions. [Goldberg, PETS 2010 rump session; see +https://thunk.cs.uwaterloo.ca/optimistic-data-pets2010-rump.pdf ] + +Design: + +The current code actually correctly handles queued data at the Exit; if +there is queued data in a EXIT_CONN_STATE_CONNECTING stream, that data +will be immediately sent when the connection succeeds. If the +connection fails, the data will be correctly ignored and freed. The +problem with the current server code is that the server currently +drops DATA cells on streams in the EXIT_CONN_STATE_CONNECTING state. +Also, if you try to queue data in the EXIT_CONN_STATE_RESOLVING state, +bad things happen because streams in that state don't yet have +conn->write_event set, and so some existing sanity checks (any stream +with queued data is at least potentially writable) are no longer sound. + +The solution is to simply not drop received DATA cells while in the +EXIT_CONN_STATE_CONNECTING state. Also do not send SENDME cells in this +state, so that the OP cannot send more than one window's worth of data +to be queued at the Exit. Finally, patch the sanity checks so that +streams in the EXIT_CONN_STATE_RESOLVING state that have buffered data +can pass. + +If no clients ever send such optimistic data, the new code will never be +executed, and the behaviour of Tor will not change. When clients begin +to send optimistic data, the performance of those clients' streams will +improve. + +After discussion with nickm, it seems best to just have the server +version number be the indicator of whether a particular Exit supports +optimistic data. (If a client sends optimistic data to an Exit which +does not support it, the data will be dropped, and the client's request +will fail to complete.) What do version numbers for hypothetical future +protocol-compatible implementations look like, though? + +Security implications: + +Servers (for sure the Exit, and possibly others, by watching the +pattern of packets) will be able to tell that a particular client +is using optimistic data. This will be discussed more in the sibling +proposal. + +On the Exit side, servers will be queueing a little bit extra data, but +no more than one window. Clients today can cause Exits to queue that +much data anyway, simply by establishing a Tor connection to a slow +machine, and sending one window of data. + +Specification: + +tor-spec section 6.2 currently says: + + The OP waits for a RELAY_CONNECTED cell before sending any data. + Once a connection has been established, the OP and exit node + package stream data in RELAY_DATA cells, and upon receiving such + cells, echo their contents to the corresponding TCP stream. + RELAY_DATA cells sent to unrecognized streams are dropped. + +It is not clear exactly what an "unrecognized" stream is, but this last +sentence would be changed to say that RELAY_DATA cells received on a +stream that has processed a RELAY_BEGIN cell and has not yet issued a +RELAY_END or a RELAY_CONNECTED cell are queued; that queue is processed +immediately after a RELAY_CONNECTED cell is issued for the stream, or +freed after a RELAY_END cell is issued for the stream. + +The earlier part of this section will be addressed in the sibling +proposal. + +Compatibility: + +There are compatibility issues, as mentioned above. OPs MUST NOT send +optimistic data to Exit nodes whose version numbers predate (something). +OPs MAY send optimistic data to Exit nodes whose version numbers match +or follow that value. (But see the question about independent server +reimplementations, above.) + +Implementation: + +Here is a simple patch. It seems to work with both regular streams and +hidden services, but there may be other corner cases I'm not aware of. +(Do streams used for directory fetches, hidden services, etc. take a +different code path?) + +diff --git a/src/or/connection.c b/src/or/connection.c +index 7b1493b..f80cd6e 100644 +--- a/src/or/connection.c ++++ b/src/or/connection.c +@@ -2845,7 +2845,13 @@ _connection_write_to_buf_impl(const char *string, size_t len, + return; + } + +- connection_start_writing(conn); ++ /* If we receive optimistic data in the EXIT_CONN_STATE_RESOLVING ++ * state, we don't want to try to write it right away, since ++ * conn->write_event won't be set yet. Otherwise, write data from ++ * this conn as the socket is available. */ ++ if (conn->state != EXIT_CONN_STATE_RESOLVING) { ++ connection_start_writing(conn); ++ } + if (zlib) { + conn->outbuf_flushlen += buf_datalen(conn->outbuf) - old_datalen; + } else { +@@ -3382,7 +3388,11 @@ assert_connection_ok(connection_t *conn, time_t now) + tor_assert(conn->s < 0); + + if (conn->outbuf_flushlen > 0) { +- tor_assert(connection_is_writing(conn) || conn->write_blocked_on_bw || ++ /* With optimistic data, we may have queued data in ++ * EXIT_CONN_STATE_RESOLVING while the conn is not yet marked to writing. ++ * */ ++ tor_assert(conn->state == EXIT_CONN_STATE_RESOLVING || ++ connection_is_writing(conn) || conn->write_blocked_on_bw || + (CONN_IS_EDGE(conn) && TO_EDGE_CONN(conn)->edge_blocked_on_circ)); + } + +diff --git a/src/or/relay.c b/src/or/relay.c +index fab2d88..e45ff70 100644 +--- a/src/or/relay.c ++++ b/src/or/relay.c +@@ -1019,6 +1019,9 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ, + relay_header_t rh; + unsigned domain = layer_hint?LD_APP:LD_EXIT; + int reason; ++ int optimistic_data = 0; /* Set to 1 if we receive data on a stream ++ that's in the EXIT_CONN_STATE_RESOLVING ++ or EXIT_CONN_STATE_CONNECTING states.*/ + + tor_assert(cell); + tor_assert(circ); +@@ -1038,9 +1041,20 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ, + /* either conn is NULL, in which case we've got a control cell, or else + * conn points to the recognized stream. */ + +- if (conn && !connection_state_is_open(TO_CONN(conn))) +- return connection_edge_process_relay_cell_not_open( +- &rh, cell, circ, conn, layer_hint); ++ if (conn && !connection_state_is_open(TO_CONN(conn))) { ++ if ((conn->_base.state == EXIT_CONN_STATE_CONNECTING || ++ conn->_base.state == EXIT_CONN_STATE_RESOLVING) && ++ rh.command == RELAY_COMMAND_DATA) { ++ /* We're going to allow DATA cells to be delivered to an exit ++ * node in state EXIT_CONN_STATE_CONNECTING or ++ * EXIT_CONN_STATE_RESOLVING. This speeds up HTTP, for example. */ ++ log_warn(domain, "Optimistic data received."); ++ optimistic_data = 1; ++ } else { ++ return connection_edge_process_relay_cell_not_open( ++ &rh, cell, circ, conn, layer_hint); ++ } ++ } + + switch (rh.command) { + case RELAY_COMMAND_DROP: +@@ -1090,7 +1104,9 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ, + log_debug(domain,"circ deliver_window now %d.", layer_hint ? + layer_hint->deliver_window : circ->deliver_window); + +- circuit_consider_sending_sendme(circ, layer_hint); ++ if (!optimistic_data) { ++ circuit_consider_sending_sendme(circ, layer_hint); ++ } + + if (!conn) { + log_info(domain,"data cell dropped, unknown stream (streamid %d).", +@@ -1107,7 +1123,9 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ, + stats_n_data_bytes_received += rh.length; + connection_write_to_buf(cell->payload + RELAY_HEADER_SIZE, + rh.length, TO_CONN(conn)); +- connection_edge_consider_sending_sendme(conn); ++ if (!optimistic_data) { ++ connection_edge_consider_sending_sendme(conn); ++ } + return 0; + case RELAY_COMMAND_END: + reason = rh.length > 0 ? + +Performance and scalability notes: + +There may be more RAM used at Exit nodes, as mentioned above, but it is +transient. diff --git a/proposals/175-automatic-node-promotion.txt b/proposals/175-automatic-node-promotion.txt new file mode 100644 index 0000000..c990b3f --- /dev/null +++ b/proposals/175-automatic-node-promotion.txt @@ -0,0 +1,238 @@ +Filename: 175-automatic-node-promotion.txt +Title: Automatically promoting Tor clients to nodes +Author: Steven Murdoch +Created: 12-Mar-2010 +Status: Draft + +1. Overview + + This proposal describes how Tor clients could determine when they + have sufficient bandwidth capacity and are sufficiently reliable to + become either bridges or Tor relays. When they meet this + criteria, they will automatically promote themselves, based on user + preferences. The proposal also defines the new controller messages + and options which will control this process. + + Note that for the moment, only transitions between client and + bridge are being considered. Transitions to public relay will + be considered at a future date, but will use the same + infrastructure for measuring capacity and reliability. + +2. Motivation and history + + Tor has a growing user-base and one of the major impediments to the + quality of service offered is the lack of network capacity. This is + particularly the case for bridges, because these are gradually + being blocked, and thus no longer of use to people within some + countries. By automatically promoting Tor clients to bridges, and + perhaps also to full public relays, this proposal aims to solve + these problems. + + Only Tor clients which are sufficiently useful should be promoted, + and the process of determining usefulness should be performed + without reporting the existence of the client to the central + authorities. The criteria used for determining usefulness will be + in terms of bandwidth capacity and uptime, but parameters should be + specified in the directory consensus. State stored at the client + should be in no more detail than necessary, to prevent sensitive + information being recorded. + +3. Design + +3.x Opt-in state model + + Tor can be in one of five node-promotion states: + + - off (O): Currently a client, and will stay as such + - auto (A): Currently a client, but will consider promotion + - bridge (B): Currently a bridge, and will stay as such + - auto-bridge (AB): Currently a bridge, but will consider promotion + - relay (R): Currently a public relay, and will stay as such + + The state can be fully controlled from the configuration file or + controller, but the normal state transitions are as follows: + + Any state -> off: User has opted out of node promotion + Off -> any state: Only permitted with user consent + + Auto -> auto-bridge: Tor has detected that it is sufficiently + reliable to be a *bridge* + Auto -> bridge: Tor has detected that it is sufficiently reliable + to be a *relay*, but the user has chosen to remain a *bridge* + Auto -> relay: Tor has detected that it is sufficiently reliable + to be *relay*, and will skip being a *bridge* + Auto-bridge -> relay: Tor has detected that it is sufficiently + reliable to be a *relay* + + Note that this model does not support automatic demotion. If this + is desirable, there should be some memory as to whether the + previous state was relay, bridge, or auto-bridge. Otherwise the + user may be prompted to become a relay, although he has opted to + only be a bridge. + +3.x User interaction policy + + There are a variety of options in how to involve the user into the + decision as to whether and when to perform node promotion. The + choice also may be different when Tor is running from Vidalia (and + thus can readily prompt the user for information), and standalone + (where Tor can only log messages, which may or may not be read). + + The option requiring minimal user interaction is to automatically + promote nodes according to reliability, and allow the user to opt + out, by changing settings in the configuration file or Vidalia user + interface. + + Alternatively, if a user interface is available, Tor could prompt + the user when it detects that a transition is available, and allow + the user to choose which of the available options to select. If + Vidalia is not available, it still may be possible to solicit an + email address on install, and contact the operator to ask whether + a transition to bridge or relay is permitted. + + Finally, Tor could by default not make any transition, and the user + would need to opt in by stating the maximum level (bridge or + relay) to which the node may automatically promote itself. + +3.x Performance monitoring model + + To prevent a large number of clients activating as relays, but + being too unreliable to be useful, clients should measure their + performance. If this performance meets a parameterized acceptance + criteria, a client should consider promotion. To measure + reliability, this proposal adopts a simple user model: + + - A user decides to use Tor at times which follow a Poisson + distribution + - At each time, the user will be happy if the bridge chosen has + adequate bandwidth and is reachable + - If the chosen bridge is down or slow too many times, the user + will consider Tor to be bad + + If we additionally assume that the recent history of relay + performance matches the current performance, we can measure + reliability by simulating this simple user. + + The following parameters are distributed to clients in the + directory consensus: + + - min_bandwidth: Minimum self-measured bandwidth for a node to be + considered useful, in bytes per second + - check_period: How long, in seconds, to wait between checking + reachability and bandwidth (on average) + - num_samples: Number of recent samples to keep + - num_useful: Minimum number of recent samples where the node was + reachable and had at least min_bandwidth capacity, for a client + to consider promoting to a bridge + + A different set of parameters may be used for considering when to + promote a bridge to a full relay, but this will be the subject of a + future revision of the proposal. + +3.x Performance monitoring algorithm + + The simulation described above can be implemented as follows: + + Every 60 seconds: + 1. Tor generates a random floating point number x in + the interval [0, 1). + 2. If x > (1 / (check_period / 60)) GOTO end; otherwise: + 3. Tor sets the value last_check to the current_time (in seconds) + 4. Tor measures reachability + 5. If the client is reachable, Tor measures its bandwidth + 6. If the client is reachable and the bandwidth is >= + min_bandwidth, the test has succeeded, otherwise it has failed. + 7. Tor adds the test result to the end of a ring-buffer containing + the last num_samples results: measurement_results + 8. Tor saves last_check and measurements_results to disk + 9. If the length of measurements_results == num_samples and + the number of successes >= num_useful, Tor should consider + promotion to a bridge + end. + + When Tor starts, it must fill in the samples for which it was not + running. This can only happen once the consensus has downloaded, + because the value of check_period is needed. + + 1. Tor generates a random number y from the Poisson distribution [1] + with lambda = (current_time - last_check) * (1 / check_period) + 2. Tor sets the value last_check to the current_time (in seconds) + 3. Add y test failures to the ring buffer measurements_results + 4. Tor saves last_check and measurements_results to disk + + In this way, a Tor client will measure its bandwidth and + reachability every check_period seconds, on average. Provided + check_period is sufficiently greater than a minute (say, at least an + hour), the times of check will follow a Poisson distribution. [2] + + While this does require that Tor does record the state of a client + over time, this does not leak much information. Only a binary + reachable/non-reachable is stored, and the timing of samples becomes + increasingly fuzzy as the data becomes less recent. + + On IP address changes, Tor should clear the ring-buffer, because + from the perspective of users with the old IP address, this node + might as well be a new one with no history. This policy may change + once we start allowing the bridge authority to hand out new IP + addresses given the fingerprint. + +3.x Bandwidth measurement + + Tor needs to measure its bandwidth to test the usefulness as a + bridge. A non-intrusive way to do this would be to passively measure + the peak data transfer rate since the last reachability test. Once + this exceeds min_bandwidth, Tor can set a flag that this node + currently has sufficient bandwidth to pass the bandwidth component + of the upcoming performance measurement. + + For the first version we may simply skip the bandwidth test, + because the existing reachability test sends 500 kB over several + circuits, and checks whether the node can transfer at least 50 + kB/s. This is probably good enough for a bridge, so this test + might be sufficient to record a success in the ring buffer. + +3.x New options + +3.x New controller message + +4. Migration plan + + We should start by setting a high bandwidth and uptime requirement + in the consensus, so as to avoid overloading the bridge authority + with too many bridges. Once we are confident our systems can scale, + the criteria can be gradually shifted down to gain more bridges. + +5. Related proposals + +6. Open questions: + + - What user interaction policy should we take? + + - When (if ever) should we turn a relay into an exit relay? + + - What should the rate limits be for auto-promoted bridges/relays? + Should we prompt the user for this? + + - Perhaps the bridge authority should tell potential bridges + whether to enable themselves, by taking into account whether + their IP address is blocked + + - How do we explain the possible risks of running a bridge/relay + * Use of bandwidth/congestion + * Publication of IP address + * Blocking from IRC (even for non-exit relays) + + - What feedback should we give to bridge relays, to encourage then + e.g. number of recent users (what about reserve bridges)? + + - Can clients back-off from doing these tests (yes, we should do + this) + +[1] For algorithms to generate random numbers from the Poisson + distribution, see: http://en.wikipedia.org/wiki/Poisson_distribution#Generating_Poisson-distributed_random_variables +[2] "The sample size n should be equal to or larger than 20 and the + probability of a single success, p, should be smaller than or equal to + .05. If n >= 100, the approximation is excellent if np is also <= 10." + http://www.itl.nist.gov/div898/handbook/pmc/section3/pmc331.htm (e-Handbook of Statistical Methods) + +% vim: spell ai et: diff --git a/rend-spec.txt b/rend-spec.txt index e5bc18e..3c14ebc 100644 --- a/rend-spec.txt +++ b/rend-spec.txt @@ -9,7 +9,7 @@ RFC 2119. Read - https://www.torproject.org/doc/design-paper/tor-design.html#sec:rendezvous + https://svn.torproject.org/svn/projects/design-paper/tor-design.html#sec:rendezvous before you read this specification. It will make more sense. Rendezvous points provide location-hidden services (server @@ -20,11 +20,10 @@ Bob does this by anonymously advertising a public key for his service, along with a list of onion routers to act as "Introduction Points" for his service. He creates forward circuits to those - introduction points, and tells them about his public key. To + introduction points, and tells them about his service. To connect to Bob, Alice first builds a circuit to an OR to act as her "Rendezvous Point." She then connects to one of Bob's chosen - introduction points, optionally provides authentication or - authorization information, and asks it to tell him about her Rendezvous + introduction points, and asks it to tell him about her Rendezvous Point (RP). If Bob chooses to answer, he builds a circuit to her RP, and tells it to connect him to Alice. The RP joins their circuits together, and begins relaying cells. Alice's 'BEGIN' @@ -64,23 +63,21 @@ 0.2. Protocol outline - 1. Bob->Bob's OP: "Offer IP:Port as - public-key-name:Port". [configuration] + 1. Bob->Bob's OP: "Offer IP:Port as public-key-name:Port". [configuration] (We do not specify this step; it is left to the implementor of Bob's OP.) - 2. Bob's OP generates keypair and rendezvous service descriptor: - "Meet public-key X at introduction point A, B, or C." (signed) + 2. Bob's OP generates a long-term keypair. 3. Bob's OP->Introduction point via Tor: [introduction setup] - "This pk is me." + "This public key is (currently) associated to me." - 4. Bob's OP->directory service via Tor: publishes Bob's service - descriptor [advertisement] + 4. Bob's OP->directory service via Tor: publishes Bob's service descriptor + [advertisement] + "Meet public-key X at introduction point A, B, or C." (signed) - 5. Out of band, Alice receives a [x.y.]z.onion:port address. - She opens a SOCKS connection to her OP, and requests - x.y.z.onion:port. + 5. Out of band, Alice receives a z.onion:port address. + She opens a SOCKS connection to her OP, and requests z.onion:port. 6. Alice's OP retrieves Bob's descriptor via Tor. [descriptor lookup.] @@ -89,29 +86,31 @@ setup.] 8. Alice connects to the Introduction point via Tor, and tells it about - her rendezvous point and optional authentication/authorization - information. (Encrypted to Bob.) [Introduction 1] + her rendezvous point. (Encrypted to Bob.) [Introduction 1] 9. The Introduction point passes this on to Bob's OP via Tor, along the introduction circuit. [Introduction 2] 10. Bob's OP decides whether to connect to Alice, and if so, creates a circuit to Alice's RP via Tor. Establishes a shared circuit. - [Rendezvous.] + [Rendezvous 1] - 11. Alice's OP sends begin cells to Bob's OP. [Connection] + 11. The Rendezvous point forwards Bob's confirmation to Alice's OP. + [Rendezvous 2] + + 12. Alice's OP sends begin cells to Bob's OP. [Connection] 0.3. Constants and new cell types Relay cell types - 32 -- RELAY_ESTABLISH_INTRO - 33 -- RELAY_ESTABLISH_RENDEZVOUS - 34 -- RELAY_INTRODUCE1 - 35 -- RELAY_INTRODUCE2 - 36 -- RELAY_RENDEZVOUS1 - 37 -- RELAY_RENDEZVOUS2 - 38 -- RELAY_INTRO_ESTABLISHED - 39 -- RELAY_RENDEZVOUS_ESTABLISHED + 32 -- RELAY_COMMAND_ESTABLISH_INTRO + 33 -- RELAY_COMMAND_ESTABLISH_RENDEZVOUS + 34 -- RELAY_COMMAND_INTRODUCE1 + 35 -- RELAY_COMMAND_INTRODUCE2 + 36 -- RELAY_COMMAND_RENDEZVOUS1 + 37 -- RELAY_COMMAND_RENDEZVOUS2 + 38 -- RELAY_COMMAND_INTRO_ESTABLISHED + 39 -- RELAY_COMMAND_RENDEZVOUS_ESTABLISHED 40 -- RELAY_COMMAND_INTRODUCE_ACK 0.4. Version overview @@ -121,14 +120,14 @@ other parts remained the same. The following list of potentially versioned protocol parts should help reduce some confusion: - - Hidden service descriptor: the binary-based v0 was the default for - a long time, and an ascii-based v2 has been added by proposal - 114. See 1.2. + - Hidden service descriptor: the binary-based v0 was the default for a + long time, and an ASCII-based v2 has been added by proposal 114. The + v0 descriptor format has been deprecated in 0.2.2.1-alpha. See 1.3. - Hidden service descriptor propagation mechanism: currently related to the hidden service descriptor version -- v0 publishes to the original hs directory authorities, whereas v2 publishes to a rotating subset - of relays with the "hsdir" flag; see 1.4 and 1.6. + of relays with the "HSDir" flag; see 1.4 and 1.6. - Introduction protocol for how to generate an introduction cell: v0 specified a nickname for the rendezvous point and assumed the @@ -146,13 +145,80 @@ service. Bob provides a mapping from each of these virtual ports to a local IP:Port pair. -1.2. Bob's OP generates service descriptors. +1.2. Bob's OP establishes his introduction points. The first time the OP provides an advertised service, it generates a public/private keypair (stored locally). - Beginning with 0.2.0.10-alpha, Bob's OP encodes "V2" descriptors. The - format of a "V2" descriptor is as follows: + The OP chooses a small number of Tor servers as introduction points. + The OP establishes a new introduction circuit to each introduction + point. These circuits MUST NOT be used for anything but hidden service + introduction. To establish the introduction, Bob sends a + RELAY_COMMAND_ESTABLISH_INTRO cell, containing: + + KL Key length [2 octets] + PK Bob's public key or service key [KL octets] + HS Hash of session info [20 octets] + SIG Signature of above information [variable] + + KL is the length of PK, in octets. + + To prevent replay attacks, the HS field contains a SHA-1 hash based on the + shared secret KH between Bob's OP and the introduction point, as + follows: + HS = H(KH | "INTRODUCE") + That is: + HS = H(KH | [49 4E 54 52 4F 44 55 43 45]) + (KH, as specified in tor-spec.txt, is H(g^xy | [00]) .) + + Upon receiving such a cell, the OR first checks that the signature is + correct with the included public key. If so, it checks whether HS is + correct given the shared state between Bob's OP and the OR. If either + check fails, the OP discards the cell; otherwise, it associates the + circuit with Bob's public key, and dissociates any other circuits + currently associated with PK. On success, the OR sends Bob a + RELAY_COMMAND_INTRO_ESTABLISHED cell with an empty payload. + + Bob's OP uses either Bob's public key or a freshly generated, single-use + service key in the RELAY_COMMAND_ESTABLISH_INTRO cell, depending on the + configured hidden service descriptor version. The public key is used for + v0 descriptors, the service key for v2 descriptors. In the latter case, the + service keys of all introduction points are included in the v2 hidden + service descriptor together with the other introduction point information. + The reason is that the introduction point does not need to and therefore + should not know for which hidden service it works, so as to prevent it from + tracking the hidden service's activity. If the hidden service is configured + to publish both v0 and v2 descriptors, two separate sets of introduction + points are established. + +1.3. Bob's OP generates service descriptors. + + For versions before 0.2.2.1-alpha, Bob's OP periodically generates and + publishes a descriptor of type "V0". + + The "V0" descriptor contains: + + KL Key length [2 octets] + PK Bob's public key [KL octets] + TS A timestamp [4 octets] + NI Number of introduction points [2 octets] + Ipt A list of NUL-terminated ORs [variable] + SIG Signature of above fields [variable] + + TS is the number of seconds elapsed since Jan 1, 1970. + + The members of Ipt may be either (a) nicknames, or (b) identity key + digests, encoded in hex, and prefixed with a '$'. Clients must + accept both forms. Services must only generate the second form. + Once 0.0.9.x is obsoleted, we can drop the first form. + + [It's ok for Bob to advertise 0 introduction points. He might want + to do that if he previously advertised some introduction points, + and now he doesn't have any. -RD] + + Beginning with 0.2.0.10-alpha, Bob's OP encodes "V2" descriptors in + addition to (or instead of) "V0" descriptors. The format of a "V2" + descriptor is as follows: "rendezvous-service-descriptor" descriptor-id NL @@ -160,11 +226,7 @@ Indicates the beginning of the descriptor. "descriptor-id" is a periodically changing identifier of 160 bits formatted as 32 base32 - chars that is calculated by the hidden service and its clients. If - the optional "descriptor-cookie" is used, this "descriptor-id" - cannot be computed by anyone else. (Everyone can verify that this - "descriptor-id" belongs to the rest of the descriptor, even without - knowing the optional "descriptor-cookie", as described below.) The + chars that is calculated by the hidden service and its clients. The "descriptor-id" is calculated by performing the following operation: descriptor-id = @@ -176,29 +238,20 @@ permanent-id = H(public-key)[:10] - "H(time-period | descriptor-cookie | replica)" is the (possibly - secret) id part that is - necessary to verify that the hidden service is the true originator - of this descriptor. It can only be created by the hidden service - and its clients, but the "signature" below can only be created by - the service. - - "descriptor-cookie" is an optional secret password of 128 bits that - is shared between the hidden service provider and its clients. + Note: If Bob's OP has "stealth" authorization enabled (see Section 2.2), + it uses the client key in place of the public hidden service key. - "replica" denotes the number of the non-consecutive replica. + "H(time-period | descriptor-cookie | replica)" is the (possibly + secret) id part that is necessary to verify that the hidden service is + the true originator of this descriptor and that is therefore contained + in the descriptor, too. The descriptor ID can only be created by the + hidden service and its clients, but the "signature" below can only be + created by the service. - (Each descriptor is replicated on a number of _consecutive_ nodes - in the identifier ring by making every storing node responsible - for the identifier intervals starting from its 3rd predecessor's - ID to its own ID. In addition to that, every service publishes - multiple descriptors with different descriptor IDs in order to - distribute them to different places on the ring. Therefore, - "replica" chooses one of the _non-consecutive_ replicas. -KL) + "time-period" changes periodically as a function of time and - The "time-period" changes periodically depending on the global time and - as a function of "permanent-id". The current value for "time-period" can - be calculated using the following formula: + "permanent-id". The current value for "time-period" can be calculated + using the following formula: time-period = (current-time + permanent-id-byte * 86400 / 256) / 86400 @@ -212,6 +265,15 @@ of the overall operation is a (network-ordered) 32-bit integer, e.g. 13753 or 0x000035B9 with the example values given above. + "descriptor-cookie" is an optional secret password of 128 bits that + is shared between the hidden service provider and its clients. If the + descriptor-cookie is left out, the input to the hash function is 128 + bits shorter. + + "replica" denotes the number of the replica. A service publishes + multiple descriptors with different descriptor IDs in order to + distribute them to different places on the ring. + "version" version-number NL [Exactly once] @@ -265,13 +327,16 @@ The unencrypted string may begin with: - ["service-authentication" auth-type NL auth-data ... reserved] + "service-authentication" auth-type auth-data NL - [At start, any number] + [Any number] The service-specific authentication data can be used to perform client authentication. This data is independent of the selected - introduction point as opposed to "intro-authentication" below. + introduction point as opposed to "intro-authentication" below. The + format of auth-data (base64-encoded or PEM format) depends on + auth-type. See section 2 of this document for details on auth + mechanisms. Subsequently, an arbitrary number of introduction point entries may follow, each containing the following data: @@ -310,14 +375,16 @@ The public key that can be used to encrypt messages to the hidden service. - ["intro-authentication" auth-type NL auth-data ... reserved] + "intro-authentication" auth-type auth-data NL [Any number] The introduction-point-specific authentication data can be used to perform client authentication. This data depends on the selected introduction point as opposed to "service-authentication" - above. + above. The format of auth-data (base64-encoded or PEM format) + depends on auth-type. See section 2 of this document for details + on auth mechanisms. (This ends the fields in the encrypted portion of the descriptor.) @@ -332,7 +399,7 @@ A signature of all fields above with the private key of the hidden service. -1.2.1. Other descriptor formats we don't use. +1.3.1. Other descriptor formats we don't use. Support for the V0 descriptor format was dropped in 0.2.2.0-alpha-dev: @@ -401,53 +468,17 @@ Currently only AUTHT of [00 00] is supported, with an AUTHL of 0. See section 2 of this document for details on auth mechanisms. -1.3. Bob's OP establishes his introduction points. - - The OP establishes a new introduction circuit to each introduction - point. These circuits MUST NOT be used for anything but hidden service - introduction. To establish the introduction, Bob sends a - RELAY_ESTABLISH_INTRO cell, containing: - - KL Key length [2 octets] - PK Introduction public key [KL octets] - HS Hash of session info [20 octets] - SIG Signature of above information [variable] - - [XXX011, need to add auth information here. -RD] - - To prevent replay attacks, the HS field contains a SHA-1 hash based on the - shared secret KH between Bob's OP and the introduction point, as - follows: - HS = H(KH | "INTRODUCE") - That is: - HS = H(KH | [49 4E 54 52 4F 44 55 43 45]) - (KH, as specified in tor-spec.txt, is H(g^xy | [00]) .) - - Upon receiving such a cell, the OR first checks that the signature is - correct with the included public key. If so, it checks whether HS is - correct given the shared state between Bob's OP and the OR. If either - check fails, the OP discards the cell; otherwise, it associates the - circuit with Bob's public key, and dissociates any other circuits - currently associated with PK. On success, the OR sends Bob a - RELAY_INTRO_ESTABLISHED cell with an empty payload. - - Bob's OP does not include its own public key in the RELAY_ESTABLISH_INTRO - cell, but the public key of a freshly generated introduction key pair. - The OP also includes these fresh public keys in the v2 hidden service - descriptor together with the other introduction point information. The - reason is that the introduction point does not need to and therefore - should not know for which hidden service it works, so as to prevent it - from tracking the hidden service's activity. - 1.4. Bob's OP advertises his service descriptor(s). - Bob's OP opens a stream to each directory server's directory port via Tor. - (He may re-use old circuits for this.) Over this stream, Bob's OP makes - an HTTP 'POST' request, to a URL "/tor/rendezvous/publish" relative to the - directory server's root, containing as its body Bob's service descriptor. + Bob's OP advertises his service descriptor to a fixed set of v0 hidden + service directory servers and/or a changing subset of all v2 hidden service + directories. - Bob should upload a service descriptor for each version format that - is supported in the current Tor network. + For versions before 0.2.2.1-alpha, Bob's OP opens a stream to each v0 + directory server's directory port via Tor. (He may re-use old circuits for + this.) Over this stream, Bob's OP makes an HTTP 'POST' request, to a URL + "/tor/rendezvous/publish" relative to the directory server's root, + containing as its body Bob's service descriptor. Upon receiving a descriptor, the directory server checks the signature, and discards the descriptor if the signature does not match the enclosed @@ -461,11 +492,12 @@ after its timestamp. At least every 18 hours, Bob's OP uploads a fresh descriptor. - Bob's OP publishes v2 descriptors to a changing subset of all v2 hidden - service directories. Therefore, Bob's OP opens a stream via Tor to each - responsible hidden service directory. (He may re-use old circuits - for this.) Over this stream, Bob's OP makes an HTTP 'POST' request to a - URL "/tor/rendezvous2/publish" relative to the hidden service + If Bob's OP is configured to publish v2 descriptors, it does so to a + changing subset of all v2 hidden service directories instead of the + authoritative directory servers. Therefore, Bob's OP opens a stream via + Tor to each responsible hidden service directory. (He may re-use old + circuits for this.) Over this stream, Bob's OP makes an HTTP 'POST' + request to a URL "/tor/rendezvous2/publish" relative to the hidden service directory's root, containing as its body Bob's service descriptor. At any time, there are 6 hidden service directories responsible for @@ -482,54 +514,41 @@ Bob's OP publishes a new v2 descriptor once an hour or whenever its content changes. V2 descriptors can be found by clients within a given time period of 24 hours, after which they change their ID as described - under 1.2. If a published descriptor would be valid for less than 60 + under 1.3. If a published descriptor would be valid for less than 60 minutes (= 2 x 30 minutes to allow the server to be 30 minutes behind and the client 30 minutes ahead), Bob's OP publishes the descriptor under the ID of both, the current and the next publication period. -1.5. Alice receives a x.y.z.onion address. +1.5. Alice receives a z.onion address. When Alice receives a pointer to a location-hidden service, it is as a - hostname of the form "z.onion" or "y.z.onion" or "x.y.z.onion", where - z is a base-32 encoding of a 10-octet hash of Bob's service's public - key, computed as follows: + hostname of the form "z.onion", where z is a base-32 encoding of a + 10-octet hash of Bob's service's public key, computed as follows: 1. Let H = H(PK). 2. Let H' = the first 80 bits of H, considering each octet from most significant bit to least significant bit. - 2. Generate a 16-character encoding of H', using base32 as defined + 3. Generate a 16-character encoding of H', using base32 as defined in RFC 3548. (We only use 80 bits instead of the 160 bits from SHA1 because we don't need to worry about arbitrary collisions, and because it will make handling the url's more convenient.) - The string "x", if present, is the base-32 encoding of the - authentication/authorization required by the introduction point. - The string "y", if present, is the base-32 encoding of the - authentication/authorization required by the hidden service. - Omitting a string is taken to mean auth type [00 00]. - See section 2 of this document for details on auth mechanisms. - [Yes, numbers are allowed at the beginning. See RFC 1123. -NM] 1.6. Alice's OP retrieves a service descriptor. - Similarly to the description in section 1.4, Alice's OP fetches a v2 - descriptor from a randomly chosen hidden service directory out of the - changing subset of 6 nodes. If the request is unsuccessful, Alice retries - the other remaining responsible hidden service directories in a random - order. Alice relies on Bob to care about a potential clock skew between - the two by possibly storing two sets of descriptors (see end of section - 1.4). + Alice's OP fetches the service descriptor from the fixed set of v0 hidden + service directory servers and/or a changing subset of all v2 hidden service + directories. - Alice's OP opens a stream via Tor to the chosen v2 hidden service - directory. (She may re-use old circuits for this.) Over this stream, - Alice's OP makes an HTTP 'GET' request for the document - "/tor/rendezvous2/<z>", where z is replaced with the encoding of the - descriptor ID. The directory replies with a 404 HTTP response if it does - not recognize <z>, and otherwise returns Bob's most recently uploaded - service descriptor. + For versions before 0.2.2.1-alpha, Alice's OP opens a stream to a directory + server via Tor, and makes an HTTP GET request for the document + '/tor/rendezvous/<z>', where '<z>' is replaced with the encoding of Bob's + public key as described above. (She may re-use old circuits for this.) The + directory replies with a 404 HTTP response if it does not recognize <z>, + and otherwise returns Bob's most recently uploaded service descriptor. If Alice's OP receives a 404 response, it tries the other directory servers, and only fails the lookup if none recognize the public key hash. @@ -545,25 +564,42 @@ [Caching may make her partitionable, but she fetched it anonymously, and we can't very well *not* cache it. -RD] + If Alice's OP is running 0.2.1.10-alpha or higher, it fetches v2 hidden + service descriptors. Versions before 0.2.2.1-alpha are fetching both v0 and + v2 descriptors in parallel. Similar to the description in section 1.4, + Alice's OP fetches a v2 descriptor from a randomly chosen hidden service + directory out of the changing subset of 6 nodes. If the request is + unsuccessful, Alice retries the other remaining responsible hidden service + directories in a random order. Alice relies on Bob to care about a potential + clock skew between the two by possibly storing two sets of descriptors (see + end of section 1.4). + + Alice's OP opens a stream via Tor to the chosen v2 hidden service + directory. (She may re-use old circuits for this.) Over this stream, + Alice's OP makes an HTTP 'GET' request for the document + "/tor/rendezvous2/<z>", where z is replaced with the encoding of the + descriptor ID. The directory replies with a 404 HTTP response if it does + not recognize <z>, and otherwise returns Bob's most recently uploaded + service descriptor. + 1.7. Alice's OP establishes a rendezvous point. When Alice requests a connection to a given location-hidden service, and Alice's OP does not have an established circuit to that service, the OP builds a rendezvous circuit. It does this by establishing a circuit to a randomly chosen OR, and sending a - RELAY_ESTABLISH_RENDEZVOUS cell to that OR. The body of that cell + RELAY_COMMAND_ESTABLISH_RENDEZVOUS cell to that OR. The body of that cell contains: RC Rendezvous cookie [20 octets] - [XXX011 this looks like an auth mechanism. should we generalize here? -RD] - The rendezvous cookie is an arbitrary 20-byte value, chosen randomly by - Alice's OP. + Alice's OP. Alice SHOULD choose a new rendezvous cookie for each new + connection attempt. - Upon receiving a RELAY_ESTABLISH_RENDEZVOUS cell, the OR associates the - RC with the circuit that sent it. It replies to Alice with an empty - RELAY_RENDEZVOUS_ESTABLISHED cell to indicate success. + Upon receiving a RELAY_COMMAND_ESTABLISH_RENDEZVOUS cell, the OR associates + the RC with the circuit that sent it. It replies to Alice with an empty + RELAY_COMMAND_RENDEZVOUS_ESTABLISHED cell to indicate success. Alice's OP MUST NOT use the circuit which sent the cell for any purpose other than rendezvous with the given location-hidden service. @@ -571,7 +607,7 @@ 1.8. Introduction: from Alice's OP to Introduction Point Alice builds a separate circuit to one of Bob's chosen introduction - points, and sends it a RELAY_INTRODUCE1 cell containing: + points, and sends it a RELAY_COMMAND_INTRODUCE1 cell containing: Cleartext PK_ID Identifier for Bob's PK [20 octets] @@ -593,15 +629,32 @@ KEY Rendezvous point onion key [KLEN octets] RC Rendezvous cookie [20 octets] g^x Diffie-Hellman data, part 1 [128 octets] + OR (in the v3 intro protocol) + VER Version byte: set to 3. [1 octet] + AUTHT The auth type that is used [1 octet] + AUTHL Length of auth data [2 octets] + AUTHD Auth data [variable] + TS A timestamp [4 octets] + IP Rendezvous point's address [4 octets] + PORT Rendezvous point's OR port [2 octets] + ID Rendezvous point identity ID [20 octets] + KLEN Length of onion key [2 octets] + KEY Rendezvous point onion key [KLEN octets] + RC Rendezvous cookie [20 octets] + g^x Diffie-Hellman data, part 1 [128 octets] + + PK_ID is the hash of Bob's public key or the service key, depending on the + hidden service descriptor version. In case of a v0 descriptor, Alice's OP + uses Bob's public key. If Alice has downloaded a v2 descriptor, she uses + the contained public key ("service-key"). - PK_ID is the hash of Bob's public key. RP is NUL-padded and - terminated. In version 0, it must contain a nickname. In version 1, - it must contain EITHER a nickname or an identity key digest that is - encoded in hex and prefixed with a '$'. + RP is NUL-padded and terminated. In version 0 of the intro protocol, RP + must contain a nickname. In version 1, it must contain EITHER a nickname or + an identity key digest that is encoded in hex and prefixed with a '$'. The hybrid encryption to Bob's PK works just like the hybrid encryption in CREATE cells (see tor-spec). Thus the payload of the - version 0 RELAY_INTRODUCE1 cell on the wire will contain + version 0 RELAY_COMMAND_INTRODUCE1 cell on the wire will contain 20+42+16+20+20+128=246 bytes, and the version 1 and version 2 introduction formats have other sizes. @@ -610,51 +663,31 @@ v1, and v2 since 0.1.1.x. As of Tor 0.2.0.7-alpha and 0.1.2.18, clients switched to using the v2 intro format. - If Alice has downloaded a v2 descriptor, she uses the contained public - key ("service-key") instead of Bob's public key to create the - RELAY_INTRODUCE1 cell as described above. - -1.8.1. Other introduction formats we don't use. - - We briefly speculated about using the following format for the - "encrypted to Bob's PK" part of the introduction, but no Tors have - ever generated these. - - VER Version byte: set to 3. [1 octet] - ATYPE An address type (typically 4) [1 octet] - ADDR Rendezvous point's IP address [4 or 16 octets] - PORT Rendezvous point's OR port [2 octets] - AUTHT The auth type that is supported [2 octets] - AUTHL Length of auth data [1 octet] - AUTHD Auth data [variable] - ID Rendezvous point identity ID [20 octets] - KLEN Length of onion key [2 octets] - KEY Rendezvous point onion key [KLEN octets] - RC Rendezvous cookie [20 octets] - g^x Diffie-Hellman data, part 1 [128 octets] - 1.9. Introduction: From the Introduction Point to Bob's OP If the Introduction Point recognizes PK_ID as a public key which has - established a circuit for introductions as in 1.3 above, it sends the body - of the cell in a new RELAY_INTRODUCE2 cell down the corresponding circuit. - (If the PK_ID is unrecognized, the RELAY_INTRODUCE1 cell is discarded.) - - After sending the RELAY_INTRODUCE2 cell, the OR replies to Alice with an - empty RELAY_COMMAND_INTRODUCE_ACK cell. If no RELAY_INTRODUCE2 cell can - be sent, the OR replies to Alice with a non-empty cell to indicate an - error. (The semantics of the cell body may be determined later; the - current implementation sends a single '1' byte on failure.) - - When Bob's OP receives the RELAY_INTRODUCE2 cell, it decrypts it with - the private key for the corresponding hidden service, and extracts the + established a circuit for introductions as in 1.2 above, it sends the body + of the cell in a new RELAY_COMMAND_INTRODUCE2 cell down the corresponding + circuit. (If the PK_ID is unrecognized, the RELAY_COMMAND_INTRODUCE1 cell is + discarded.) + + After sending the RELAY_COMMAND_INTRODUCE2 cell to Bob, the OR replies to + Alice with an empty RELAY_COMMAND_INTRODUCE_ACK cell. If no + RELAY_COMMAND_INTRODUCE2 cell can be sent, the OR replies to Alice with a + non-empty cell to indicate an error. (The semantics of the cell body may be + determined later; the current implementation sends a single '1' byte on + failure.) + + When Bob's OP receives the RELAY_COMMAND_INTRODUCE2 cell, it decrypts it + with the private key for the corresponding hidden service, and extracts the rendezvous point's nickname, the rendezvous cookie, and the value of g^x chosen by Alice. 1.10. Rendezvous Bob's OP builds a new Tor circuit ending at Alice's chosen rendezvous - point, and sends a RELAY_RENDEZVOUS1 cell along this circuit, containing: + point, and sends a RELAY_COMMAND_RENDEZVOUS1 cell along this circuit, + containing: RC Rendezvous cookie [20 octets] g^y Diffie-Hellman [128 octets] KH Handshake digest [20 octets] @@ -662,7 +695,7 @@ (Bob's OP MUST NOT use this circuit for any other purpose.) If the RP recognizes RC, it relays the rest of the cell down the - corresponding circuit in a RELAY_RENDEZVOUS2 cell, containing: + corresponding circuit in a RELAY_COMMAND_RENDEZVOUS2 cell, containing: g^y Diffie-Hellman [128 octets] KH Handshake digest [20 octets] @@ -670,10 +703,10 @@ (If the RP does not recognize the RC, it discards the cell and tears down the circuit.) - When Alice's OP receives a RELAY_RENDEZVOUS2 cell on a circuit which - has sent a RELAY_ESTABLISH_RENDEZVOUS cell but which has not yet received - a reply, it uses g^y and H(g^xy) to complete the handshake as in the Tor - circuit extend process: they establish a 60-octet string as + When Alice's OP receives a RELAY_COMMAND_RENDEZVOUS2 cell on a circuit which + has sent a RELAY_COMMAND_ESTABLISH_RENDEZVOUS cell but which has not yet + received a reply, it uses g^y and H(g^xy) to complete the handshake as in + the Tor circuit extend process: they establish a 60-octet string as K = SHA1(g^xy | [00]) | SHA1(g^xy | [01]) | SHA1(g^xy | [02]) and generate KH = K[0..15] @@ -692,7 +725,7 @@ 1.11. Creating streams To open TCP connections to Bob's location-hidden service, Alice's OP sends - a RELAY_BEGIN cell along the established circuit, using the special + a RELAY_COMMAND_BEGIN cell along the established circuit, using the special address "", and a chosen port. Bob's OP chooses a destination IP and port, based on the configuration of the service connected to the circuit, and opens a TCP stream. From then on, Bob's OP treats the stream as an @@ -700,13 +733,190 @@ [ Except he doesn't include addr in the connected cell or the end cell. -RD] - Alice MAY send multiple RELAY_BEGIN cells along the circuit, to open - multiple streams to Bob. Alice SHOULD NOT send RELAY_BEGIN cells for any - other address along her circuit to Bob; if she does, Bob MUST reject them. + Alice MAY send multiple RELAY_COMMAND_BEGIN cells along the circuit, to open + multiple streams to Bob. Alice SHOULD NOT send RELAY_COMMAND_BEGIN cells + for any other address along her circuit to Bob; if she does, Bob MUST reject + them. 2. Authentication and authorization. -Foo. + The rendezvous protocol as described in Section 1 provides a few options + for implementing client-side authorization. There are two steps in the + rendezvous protocol that can be used for performing client authorization: + when downloading and decrypting parts of the hidden service descriptor and + at Bob's Tor client before contacting the rendezvous point. A service + provider can restrict access to his service at these two points to + authorized clients only. + + There are currently two authorization protocols specified that are + described in more detail below: + + 1. The first protocol allows a service provider to restrict access + to clients with a previously received secret key only, but does not + attempt to hide service activity from others. + + 2. The second protocol, albeit being feasible for a limited set of about + 16 clients, performs client authorization and hides service activity + from everyone but the authorized clients. + +2.1. Service with large-scale client authorization + + The first client authorization protocol aims at performing access control + while consuming as few additional resources as possible. This is the "basic" + authorization protocol. A service provider should be able to permit access + to a large number of clients while denying access for everyone else. + However, the price for scalability is that the service won't be able to hide + its activity from unauthorized or formerly authorized clients. + + The main idea of this protocol is to encrypt the introduction-point part + in hidden service descriptors to authorized clients using symmetric keys. + This ensures that nobody else but authorized clients can learn which + introduction points a service currently uses, nor can someone send a + valid INTRODUCE1 message without knowing the introduction key. Therefore, + a subsequent authorization at the introduction point is not required. + + A service provider generates symmetric "descriptor cookies" for his + clients and distributes them outside of Tor. The suggested key size is + 128 bits, so that descriptor cookies can be encoded in 22 base64 chars + (which can hold up to 22 * 5 = 132 bits, leaving 4 bits to encode the + authorization type (here: "0") and allow a client to distinguish this + authorization protocol from others like the one proposed below). + Typically, the contact information for a hidden service using this + authorization protocol looks like this: + + v2cbb2l4lsnpio4q.onion Ll3X7Xgz9eHGKCCnlFH0uz + + When generating a hidden service descriptor, the service encrypts the + introduction-point part with a single randomly generated symmetric + 128-bit session key using AES-CTR as described for v2 hidden service + descriptors in rend-spec. Afterwards, the service encrypts the session + key to all descriptor cookies using AES. Authorized client should be able + to efficiently find the session key that is encrypted for him/her, so + that 4 octet long client ID are generated consisting of descriptor cookie + and initialization vector. Descriptors always contain a number of + encrypted session keys that is a multiple of 16 by adding fake entries. + Encrypted session keys are ordered by client IDs in order to conceal + addition or removal of authorized clients by the service provider. + + ATYPE Authorization type: set to 1. [1 octet] + ALEN Number of clients := 1 + ((clients - 1) div 16) [1 octet] + for each symmetric descriptor cookie: + ID Client ID: H(descriptor cookie | IV)[:4] [4 octets] + SKEY Session key encrypted with descriptor cookie [16 octets] + (end of client-specific part) + RND Random data [(15 - ((clients - 1) mod 16)) * 20 octets] + IV AES initialization vector [16 octets] + IPOS Intro points, encrypted with session key [remaining octets] + + An authorized client needs to configure Tor to use the descriptor cookie + when accessing the hidden service. Therefore, a user adds the contact + information that she received from the service provider to her torrc + file. Upon downloading a hidden service descriptor, Tor finds the + encrypted introduction-point part and attempts to decrypt it using the + configured descriptor cookie. (In the rare event of two or more client + IDs being equal a client tries to decrypt all of them.) + + Upon sending the introduction, the client includes her descriptor cookie + as auth type "1" in the INTRODUCE2 cell that she sends to the service. + The hidden service checks whether the included descriptor cookie is + authorized to access the service and either responds to the introduction + request, or not. + +2.2. Authorization for limited number of clients + + A second, more sophisticated client authorization protocol goes the extra + mile of hiding service activity from unauthorized clients. This is the + "stealth" authorization protocol. With all else being equal to the preceding + authorization protocol, the second protocol publishes hidden service + descriptors for each user separately and gets along with encrypting the + introduction-point part of descriptors to a single client. This allows the + service to stop publishing descriptors for removed clients. As long as a + removed client cannot link descriptors issued for other clients to the + service, it cannot derive service activity any more. The downside of this + approach is limited scalability. Even though the distributed storage of + descriptors (cf. proposal 114) tackles the problem of limited scalability to + a certain extent, this protocol should not be used for services with more + than 16 clients. (In fact, Tor should refuse to advertise services for more + than this number of clients.) + + A hidden service generates an asymmetric "client key" and a symmetric + "descriptor cookie" for each client. The client key is used as + replacement for the service's permanent key, so that the service uses a + different identity for each of his clients. The descriptor cookie is used + to store descriptors at changing directory nodes that are unpredictable + for anyone but service and client, to encrypt the introduction-point + part, and to be included in INTRODUCE2 cells. Once the service has + created client key and descriptor cookie, he tells them to the client + outside of Tor. The contact information string looks similar to the one + used by the preceding authorization protocol (with the only difference + that it has "1" encoded as auth-type in the remaining 4 of 132 bits + instead of "0" as before). + + When creating a hidden service descriptor for an authorized client, the + hidden service uses the client key and descriptor cookie to compute + secret ID part and descriptor ID: + + secret-id-part = H(time-period | descriptor-cookie | replica) + + descriptor-id = H(client-key[:10] | secret-id-part) + + The hidden service also replaces permanent-key in the descriptor with + client-key and encrypts introduction-points with the descriptor cookie. + + ATYPE Authorization type: set to 2. [1 octet] + IV AES initialization vector [16 octets] + IPOS Intro points, encr. with descriptor cookie [remaining octets] + + When uploading descriptors, the hidden service needs to make sure that + descriptors for different clients are not uploaded at the same time (cf. + Section 1.1) which is also a limiting factor for the number of clients. + + When a client is requested to establish a connection to a hidden service + it looks up whether it has any authorization data configured for that + service. If the user has configured authorization data for authorization + protocol "2", the descriptor ID is determined as described in the last + paragraph. Upon receiving a descriptor, the client decrypts the + introduction-point part using its descriptor cookie. Further, the client + includes its descriptor cookie as auth-type "2" in INTRODUCE2 cells that + it sends to the service. + +2.3. Hidden service configuration + + A hidden service that is meant to perform client authorization adds a + new option HiddenServiceAuthorizeClient to its hidden service + configuration. This option contains the authorization type which is + either "basic" for the protocol described in 2.1 or "stealth" for the + protocol in 2.2 and a comma-separated list of human-readable client + names, so that Tor can create authorization data for these clients: + + HiddenServiceAuthorizeClient auth-type client-name,client-name,... + + If this option is configured, HiddenServiceVersion is automatically + reconfigured to contain only version numbers of 2 or higher. There is + a maximum of 512 client names for basic auth and a maximum of 16 for + stealth auth. + + Tor stores all generated authorization data for the authorization + protocols described in Sections 2.1 and 2.2 in a new file using the + following file format: + + "client-name" human-readable client identifier NL + "descriptor-cookie" 128-bit key ^= 22 base64 chars NL + + If the authorization protocol of Section 2.2 is used, Tor also generates + and stores the following data: + + "client-key" NL a public key in PEM format + +2.4. Client configuration + + Clients need to make their authorization data known to Tor using another + configuration option that contains a service name (mainly for the sake of + convenience), the service address, and the descriptor cookie that is + required to access a hidden service (the authorization protocol number is + encoded in the descriptor cookie): + + HidServAuth service-name service-address descriptor-cookie 3. Hidden service directory operation diff --git a/tor-fw-helper-spec.txt b/tor-fw-helper-spec.txt new file mode 100644 index 0000000..0068b26 --- /dev/null +++ b/tor-fw-helper-spec.txt @@ -0,0 +1,57 @@ + + Tor's (little) Firewall Helper specification + Jacob Appelbaum + +0. Preface + + This document describes issues faced by Tor users who are behind NAT devices + and wish to share their resources with the rest of the Tor network. It also + explains a possible solution for some NAT devices. + +1. Overview + + Tor users often wish to relay traffic for the Tor network and their upstream + firewall thwarts their attempted generosity. Automatic port forwarding + configuration for many consumer NAT devices is often available with two common + protocols NAT-PMP[0] and UPnP[1]. + +2. Implementation + + tor-fw-helper is a program that implements basic port forwarding requests; it + may be used alone or called from Tor itself. + +2.1 Output format + + When tor-fw-helper has completed the requested action successfully, it will + report the following message to standard output: + + tor-fw-helper: SUCCESS + + If tor-fw-helper was unable to complete the requested action successfully, it + will report the following message to standard error: + + tor-fw-helper: FAILURE + + All informational messages are printed to standard output; all error messages + are printed to standard error. Messages other than SUCCESS and FAILURE + may be printed by any compliant tor-fw-helper. + +2.2 Output format stability + + The above SUCCESS and FAILURE messages are the only stable output formats + provided by this specification. tor-fw-helper-spec compliant implementations + must return SUCCESS or FAILURE as defined above. + +3. Security Concerns + + It is probably best to hand configure port forwarding and in the process, we + suggest disabling NAT-PMP and/or UPnP. This is of course absolutely confusing + to users and so we support automatic, non-authenticated NAT port mapping + protocols with compliant tor-fw-helper applications. + + NAT should not be considered a security boundary. NAT-PMP and UPnP are hacks + to deal with the shortcomings of user education about TCP/IP, IPv4 shortages, + and of course, NAT devices that suffer from horrible user interface design. + +[0] http://en.wikipedia.org/wiki/NAT_Port_Mapping_Protocol +[1] http://en.wikipedia.org/wiki/Universal_Plug_and_Play diff --git a/tor-spec.txt b/tor-spec.txt index f448f6d..91ad561 100644 --- a/tor-spec.txt +++ b/tor-spec.txt @@ -597,6 +597,14 @@ see tor-design.pdf. cell to the next node in the circuit, and replies to the OP with a RELAY_TRUNCATED cell. + [Note: If an OR receives a TRUNCATE cell and it has any RELAY cells + still queued on the circuit for the next node it will drop them + without sending them. This is not considered conformant behavior, + but it probably won't get fixed until a later version of Tor. Thus, + clients SHOULD NOT send a TRUNCATE cell to a node running any current + version of Tor if a) they have sent relay cells through that node, + and b) they aren't sure whether those cells have been sent on yes.] + When an unrecoverable error occurs along one connection in a circuit, the nodes on either side of the connection should, if they are able, act as follows: the node closer to the OP should send a @@ -835,7 +843,8 @@ see tor-design.pdf. 6 -- REASON_DONE (Anonymized TCP connection was closed) 7 -- REASON_TIMEOUT (Connection timed out, or OR timed out while connecting) - 8 -- (unallocated) [**] + 8 -- REASON_NOROUTE (Routing error while attempting to + contact destination) 9 -- REASON_HIBERNATING (OR is temporarily hibernating) 10 -- REASON_INTERNAL (Internal error at the OR) 11 -- REASON_RESOURCELIMIT (OR has no resources to fulfill request) @@ -857,8 +866,6 @@ see tor-design.pdf. [*] Older versions of Tor also send this reason when connections are reset. - [**] Due to a bug in versions of Tor through 0095, error reason 8 must - remain allocated until that version is obsolete. --- [The rest of this section describes unimplemented functionality.] |