diff options
| -rw-r--r-- | proposals/000-index.txt | 8 | ||||
| -rw-r--r-- | proposals/292-mesh-vanguards.txt | 2 | ||||
| -rw-r--r-- | proposals/333-vanguards-lite.md | 2 | ||||
| -rw-r--r-- | proposals/BY_INDEX.md | 4 | ||||
| -rw-r--r-- | proposals/BY_STATUS.md | 4 | ||||
| -rw-r--r-- | proposals/SUMMARY.md | 4 | ||||
| -rw-r--r-- | spec/SUMMARY.md | 5 | ||||
| -rw-r--r-- | spec/tor-spec/closing-streams.md | 2 | ||||
| -rw-r--r-- | spec/tor-spec/create-created-cells.md | 489 | ||||
| -rw-r--r-- | spec/tor-spec/creating-circuits.md | 66 | ||||
| -rw-r--r-- | spec/tor-spec/opening-streams.md | 6 | ||||
| -rw-r--r-- | spec/tor-spec/preliminaries.md | 4 | ||||
| -rw-r--r-- | spec/tor-spec/relay-cells.md | 122 | ||||
| -rw-r--r-- | spec/tor-spec/setting-circuit-keys.md | 4 | ||||
| -rw-r--r-- | spec/vanguards-spec/full-vanguards.md | 133 | ||||
| -rw-r--r-- | spec/vanguards-spec/index.md | 144 | ||||
| -rw-r--r-- | spec/vanguards-spec/path-construction.md | 53 | ||||
| -rw-r--r-- | spec/vanguards-spec/vanguards-stats.md | 195 |
18 files changed, 900 insertions, 347 deletions
diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 7acc0f7..0329640 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -213,7 +213,7 @@ Proposals by number: 289 Authenticating sendme cells to mitigate bandwidth attacks [CLOSED] 290 Continuously update consensus methods [META] 291 The move to two guard nodes [FINISHED] -292 Mesh-based vanguards [ACCEPTED] +292 Mesh-based vanguards [CLOSED] 293 Other ways for relays to know when to publish [CLOSED] 294 TLS 1.3 Migration [DRAFT] 295 Using ADL for relay cryptography (solving the crypto-tagging attack) [OPEN] @@ -254,7 +254,7 @@ Proposals by number: 330 Modernizing authority contact entries [OPEN] 331 Res tokens: Anonymous Credentials for Onion Service DoS Resilience [DRAFT] 332 Ntor protocol with extra data, version 3 [CLOSED] -333 Vanguards lite [FINISHED] +333 Vanguards lite [CLOSED] 334 A Directory Authority Flag To Mark Relays As Middle-only [SUPERSEDED] 335 An authority-only design for MiddleOnly [CLOSED] 336 Randomized schedule for guard retries [CLOSED] @@ -310,7 +310,6 @@ Proposals by status: ACCEPTED: 282 Remove "Named" and "Unnamed" handling from consensus voting [for arti-dirauth] 285 Directory documents should be standardized as UTF-8 [for arti-dirauth] - 292 Mesh-based vanguards 311 Tor Relay IPv6 Reachability 312 Tor Relay Automatic IPv6 Address Discovery 313 Tor Relay IPv6 Statistics @@ -329,7 +328,6 @@ Proposals by status: 324 RTT-based Congestion Control for Tor 327 A First Take at PoW Over Introduction Circuits 329 Overcoming Tor's Bottlenecks with Traffic Splitting - 333 Vanguards lite [in 0.4.7.1-alpha] CLOSED: 101 Voting on the Tor Directory System [in 0.2.0.x] 102 Dropping "opt" from the directory format [in 0.2.0.x] @@ -420,6 +418,7 @@ Proposals by status: 283 Move IPv6 ORPorts from microdescriptors to the microdesc consensus [for 0.3.3.x] [in 0.3.3.1-alpha] 284 Hidden Service v3 Control Port 289 Authenticating sendme cells to mitigate bandwidth attacks [in 0.4.1.1-alpha] + 292 Mesh-based vanguards 293 Other ways for relays to know when to publish [for 0.3.5] [in 0.4.0.1-alpha] 296 Have Directory Authorities expose raw bandwidth list files [in 0.4.0.1-alpha] 297 Relaxing the protover-based shutdown rules [for 0.3.5.x] [in 0.4.0.x] @@ -434,6 +433,7 @@ Proposals by status: 318 Limit protover values to 0-63 [in 0.4.5.1-alpha] 328 Make Relays Report When They Are Overloaded 332 Ntor protocol with extra data, version 3 + 333 Vanguards lite [in 0.4.7.1-alpha] 335 An authority-only design for MiddleOnly [in 0.4.7.2-alpha] 336 Randomized schedule for guard retries 337 A simpler way to decide, "Is this guard usable?" diff --git a/proposals/292-mesh-vanguards.txt b/proposals/292-mesh-vanguards.txt index e0dc6e8..7e579c8 100644 --- a/proposals/292-mesh-vanguards.txt +++ b/proposals/292-mesh-vanguards.txt @@ -3,7 +3,7 @@ Filename: 292-mesh-vanguards.txt Title: Mesh-based vanguards Authors: George Kadianakis and Mike Perry Created: 2018-05-08 -Status: Accepted +Status: Closed Supersedes: 247 0. Motivation diff --git a/proposals/333-vanguards-lite.md b/proposals/333-vanguards-lite.md index 8c1ccb9..1e83046 100644 --- a/proposals/333-vanguards-lite.md +++ b/proposals/333-vanguards-lite.md @@ -3,7 +3,7 @@ Filename: 333-vanguards-lite.md Title: Vanguards lite Author: George Kadianakis, Mike Perry Created: 2021-05-20 -Status: Finished +Status: Closed Implemented-In: 0.4.7.1-alpha ``` diff --git a/proposals/BY_INDEX.md b/proposals/BY_INDEX.md index 24a770e..b60a656 100644 --- a/proposals/BY_INDEX.md +++ b/proposals/BY_INDEX.md @@ -209,7 +209,7 @@ Below are a list of proposals sorted by their proposal number. See * [`289-authenticated-sendmes.txt`](/proposals/289-authenticated-sendmes.txt): Authenticating sendme cells to mitigate bandwidth attacks [CLOSED] * [`290-deprecate-consensus-methods.txt`](/proposals/290-deprecate-consensus-methods.txt): Continuously update consensus methods [META] * [`291-two-guard-nodes.txt`](/proposals/291-two-guard-nodes.txt): The move to two guard nodes [FINISHED] -* [`292-mesh-vanguards.txt`](/proposals/292-mesh-vanguards.txt): Mesh-based vanguards [ACCEPTED] +* [`292-mesh-vanguards.txt`](/proposals/292-mesh-vanguards.txt): Mesh-based vanguards [CLOSED] * [`293-know-when-to-publish.txt`](/proposals/293-know-when-to-publish.txt): Other ways for relays to know when to publish [CLOSED] * [`294-tls-1.3.txt`](/proposals/294-tls-1.3.txt): TLS 1.3 Migration [DRAFT] * [`295-relay-crypto-with-adl.txt`](/proposals/295-relay-crypto-with-adl.txt): Using ADL for relay cryptography (solving the crypto-tagging attack) [OPEN] @@ -250,7 +250,7 @@ Below are a list of proposals sorted by their proposal number. See * [`330-authority-contact.md`](/proposals/330-authority-contact.md): Modernizing authority contact entries [OPEN] * [`331-res-tokens-for-anti-dos.md`](/proposals/331-res-tokens-for-anti-dos.md): Res tokens: Anonymous Credentials for Onion Service DoS Resilience [DRAFT] * [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 [CLOSED] -* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite [FINISHED] +* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite [CLOSED] * [`334-middle-only-flag.txt`](/proposals/334-middle-only-flag.txt): A Directory Authority Flag To Mark Relays As Middle-only [SUPERSEDED] * [`335-middle-only-redux.md`](/proposals/335-middle-only-redux.md): An authority-only design for MiddleOnly [CLOSED] * [`336-randomize-guard-retries.md`](/proposals/336-randomize-guard-retries.md): Randomized schedule for guard retries [CLOSED] diff --git a/proposals/BY_STATUS.md b/proposals/BY_STATUS.md index 8e5f0ed..865fac0 100644 --- a/proposals/BY_STATUS.md +++ b/proposals/BY_STATUS.md @@ -50,7 +50,6 @@ implementation. * [`282-remove-named-from-consensus.txt`](/proposals/282-remove-named-from-consensus.txt): Remove "Named" and "Unnamed" handling from consensus voting * [`285-utf-8.txt`](/proposals/285-utf-8.txt): Directory documents should be standardized as UTF-8 -* [`292-mesh-vanguards.txt`](/proposals/292-mesh-vanguards.txt): Mesh-based vanguards * [`311-relay-ipv6-reachability.txt`](/proposals/311-relay-ipv6-reachability.txt): Tor Relay IPv6 Reachability * [`312-relay-auto-ipv6-addr.txt`](/proposals/312-relay-auto-ipv6-addr.txt): Tor Relay Automatic IPv6 Address Discovery * [`313-relay-ipv6-stats.txt`](/proposals/313-relay-ipv6-stats.txt): Tor Relay IPv6 Statistics @@ -69,7 +68,6 @@ themselves still need to be merged into the specifications proper. * [`324-rtt-congestion-control.txt`](/proposals/324-rtt-congestion-control.txt): RTT-based Congestion Control for Tor * [`327-pow-over-intro.txt`](/proposals/327-pow-over-intro.txt): A First Take at PoW Over Introduction Circuits * [`329-traffic-splitting.txt`](/proposals/329-traffic-splitting.txt): Overcoming Tor's Bottlenecks with Traffic Splitting -* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite ## META proposals: about the proposal process @@ -227,6 +225,7 @@ necessary. * [`283-ipv6-in-micro-consensus.txt`](/proposals/283-ipv6-in-micro-consensus.txt): Move IPv6 ORPorts from microdescriptors to the microdesc consensus * [`284-hsv3-control-port.txt`](/proposals/284-hsv3-control-port.txt): Hidden Service v3 Control Port * [`289-authenticated-sendmes.txt`](/proposals/289-authenticated-sendmes.txt): Authenticating sendme cells to mitigate bandwidth attacks +* [`292-mesh-vanguards.txt`](/proposals/292-mesh-vanguards.txt): Mesh-based vanguards * [`293-know-when-to-publish.txt`](/proposals/293-know-when-to-publish.txt): Other ways for relays to know when to publish * [`296-expose-bandwidth-files.txt`](/proposals/296-expose-bandwidth-files.txt): Have Directory Authorities expose raw bandwidth list files * [`297-safer-protover-shutdowns.txt`](/proposals/297-safer-protover-shutdowns.txt): Relaxing the protover-based shutdown rules @@ -241,6 +240,7 @@ necessary. * [`318-limit-protovers.md`](/proposals/318-limit-protovers.md): Limit protover values to 0-63 * [`328-relay-overload-report.md`](/proposals/328-relay-overload-report.md): Make Relays Report When They Are Overloaded * [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 +* [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite * [`335-middle-only-redux.md`](/proposals/335-middle-only-redux.md): An authority-only design for MiddleOnly * [`336-randomize-guard-retries.md`](/proposals/336-randomize-guard-retries.md): Randomized schedule for guard retries * [`337-simpler-guard-usability.md`](/proposals/337-simpler-guard-usability.md): A simpler way to decide, "Is this guard usable?" diff --git a/proposals/SUMMARY.md b/proposals/SUMMARY.md index b8d6265..15b787b 100644 --- a/proposals/SUMMARY.md +++ b/proposals/SUMMARY.md @@ -202,7 +202,7 @@ - [`289-authenticated-sendmes`](./289-authenticated-sendmes.txt): Authenticating sendme cells to mitigate bandwidth attacks (CLOSED) - [`290-deprecate-consensus-methods`](./290-deprecate-consensus-methods.txt): Continuously update consensus methods (META) - [`291-two-guard-nodes`](./291-two-guard-nodes.txt): The move to two guard nodes (FINISHED) - - [`292-mesh-vanguards`](./292-mesh-vanguards.txt): Mesh-based vanguards (ACCEPTED) + - [`292-mesh-vanguards`](./292-mesh-vanguards.txt): Mesh-based vanguards (CLOSED) - [`293-know-when-to-publish`](./293-know-when-to-publish.txt): Other ways for relays to know when to publish (CLOSED) - [`294-tls-1.3`](./294-tls-1.3.txt): TLS 1.3 Migration (DRAFT) - [`295-relay-crypto-with-adl`](./295-relay-crypto-with-adl.txt): Using ADL for relay cryptography (solving the crypto-tagging attack) (OPEN) @@ -243,7 +243,7 @@ - [`330-authority-contact`](./330-authority-contact.md): Modernizing authority contact entries (OPEN) - [`331-res-tokens-for-anti-dos`](./331-res-tokens-for-anti-dos.md): Res tokens: Anonymous Credentials for Onion Service DoS Resilience (DRAFT) - [`332-ntor-v3-with-extra-data`](./332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 (CLOSED) - - [`333-vanguards-lite`](./333-vanguards-lite.md): Vanguards lite (FINISHED) + - [`333-vanguards-lite`](./333-vanguards-lite.md): Vanguards lite (CLOSED) - [`334-middle-only-flag`](./334-middle-only-flag.txt): A Directory Authority Flag To Mark Relays As Middle-only (SUPERSEDED) - [`335-middle-only-redux`](./335-middle-only-redux.md): An authority-only design for MiddleOnly (CLOSED) - [`336-randomize-guard-retries`](./336-randomize-guard-retries.md): Randomized schedule for guard retries (CLOSED) diff --git a/spec/SUMMARY.md b/spec/SUMMARY.md index 548d8c1..a3725c1 100644 --- a/spec/SUMMARY.md +++ b/spec/SUMMARY.md @@ -82,6 +82,11 @@ - [Circuit Creation, Entry Guard Selection (1000 foot view)](./guard-spec/guard-selection/index.md) - [The algorithm.](./guard-spec/algorithm.md) - [Appendices](./guard-spec/appendices.md) +- [`Tor Vanguards Specification`](./vanguards-spec/index.md) + - [Full Vanguards](./vanguards-spec/full-vanguards.md) + - [Vanguards-Lite](./vanguards-spec/vanguards-lite.md) + - [Path Construction](./vanguards-spec/path-construction.md) + - [Statistical Analysis](./vanguards-spec/vanguards-stats.md) - [`Tor Padding Specification`](./padding-spec/index.md) - [Overview](./padding-spec/overview.md) - [Connection-level padding](./padding-spec/connection-level-padding.md) diff --git a/spec/tor-spec/closing-streams.md b/spec/tor-spec/closing-streams.md index 7182f48..265e9d1 100644 --- a/spec/tor-spec/closing-streams.md +++ b/spec/tor-spec/closing-streams.md @@ -1,6 +1,6 @@ <a id="tor-spec.txt-6.3"></a> -# Closing streams +# Closing streams{#closing-streams} When an anonymized TCP connection is closed, or an edge node encounters error on any stream, it sends a 'RELAY_END' cell along the diff --git a/spec/tor-spec/create-created-cells.md b/spec/tor-spec/create-created-cells.md index 24cf6e6..965cad1 100644 --- a/spec/tor-spec/create-created-cells.md +++ b/spec/tor-spec/create-created-cells.md @@ -55,7 +55,7 @@ or The first format is equivalent to a CREATE2 cell with HTYPE of 'tap' and length of `TAP_C_HANDSHAKE_LEN`. The second format is a way to encapsulate new handshake types into the old CREATE cell format for -migration. See 5.1.2 below. Recognized HTAG values are: +migration. See ["EXTEND and EXTENDED cells"](#EXTEND) below. Recognized HTAG values are: | Value | Description | | ----- | ----------- | @@ -69,7 +69,7 @@ The format of a CREATED cell is: (It's equivalent to a CREATED2 cell with length of `TAP_S_HANDSHAKE_LEN`.) -As usual with DH, x and y MUST be generated randomly. +As usual with DH, `x` and `y` MUST be generated randomly. In general, clients SHOULD use CREATE whenever they are using the TAP handshake, and CREATE2 otherwise. Clients SHOULD NOT send the @@ -125,31 +125,26 @@ RELAY_EARLY cell to the last node in the circuit. An EXTEND2 cell's relay payload contains: -```text - NSPEC (Number of link specifiers) [1 byte] - NSPEC times: - LSTYPE (Link specifier type) [1 byte] - LSLEN (Link specifier length) [1 byte] - LSPEC (Link specifier) [LSLEN bytes] - HTYPE (Client Handshake Type) [2 bytes] - HLEN (Client Handshake Data Len) [2 bytes] - HDATA (Client Handshake Data) [HLEN bytes] -``` +| Field | Description | Size | +| ----- | ----------- | ---- | +| `NSPEC` | Number of link specifiers | 1 byte +| `NSPEC` times: | +| - `LSTYPE` | Link specifier type | 1 byte +| - `LSLEN` | Link specifier length | 1 byte +| - `LSPEC` | Link specifier | LSLEN bytes +| `HTYPE` | Client Handshake Type | 2 bytes +| `HLEN` | Client Handshake Data Len | 2 bytes +| `HDATA` | Client Handshake Data | HLEN bytes Link specifiers describe the next node in the circuit and how to connect to it. Recognized specifiers are: -```text - [00] TLS-over-TCP, IPv4 address - A four-byte IPv4 address plus two-byte ORPort - [01] TLS-over-TCP, IPv6 address - A sixteen-byte IPv6 address plus two-byte ORPort - [02] Legacy identity - A 20-byte SHA1 identity fingerprint. At most one may be listed. - [03] Ed25519 identity - A 32-byte Ed25519 identity fingerprint. At most one may - be listed. -``` +| Value | Description +| ----- | ----------- +| [00] | TLS-over-TCP, IPv4 address. A four-byte IPv4 address plus two-byte ORPort. +| [01] | TLS-over-TCP, IPv6 address. A sixteen-byte IPv6 address plus two-byte ORPort. +| [02] | Legacy identity. A 20-byte SHA1 identity fingerprint. At most one may be listed. +| [03] | Ed25519 identity. A 32-byte Ed25519 identity fingerprint. At most one may be listed. Nodes MUST ignore unrecognized specifiers, and MUST accept multiple instances of specifiers other than 'legacy identity' and @@ -162,16 +157,17 @@ these link specifiers, if using them, in this order: \[00\], \[02\], \[03\], The relay payload for an EXTEND relay cell consists of: -```text - Address [4 bytes] - Port [2 bytes] - Onion skin [TAP_C_HANDSHAKE_LEN bytes] - Identity fingerprint [HASH_LEN bytes] -``` +| Field | Size +| ----- | ---- +| Address | 4 bytes +| Port | 2 bytes +| Onion skin | `TAP_C_HANDSHAKE_LEN` bytes +| Identity fingerprint | `HASH_LEN` bytes The "legacy identity" and "identity fingerprint" fields are the SHA1 hash of the PKCS#1 ASN1 encoding of the next onion router's -identity (signing) key. (See 0.3 above.) The "Ed25519 identity" +identity (signing) key. (See ["Preliminaries » Ciphers"](./preliminaries.md#ciphers)) +The "Ed25519 identity" field is the Ed25519 identity key of the target node. Including this key information allows the extending OR verify that it is indeed connected to the correct target OR, and prevents certain @@ -222,55 +218,57 @@ use the format with 'client handshake type tag'. ## The "TAP" handshake {#TAP} -This handshake uses Diffie-Hellman in Z_p and RSA to compute a set of +This handshake uses Diffie-Hellman in Z<sub>p</sub> and RSA to compute a set of shared keys which the client knows are shared only with a particular server, and the server knows are shared with whomever sent the original handshake (or with nobody at all). It's not very fast and not very good. (See Goldberg's "On the Security of the Tor Authentication Protocol".) -Define TAP_C_HANDSHAKE_LEN as DH_LEN+KEY_LEN+KP_PAD_LEN. -Define TAP_S_HANDSHAKE_LEN as DH_LEN+HASH_LEN. +Define `TAP_C_HANDSHAKE_LEN` as `DH_LEN+KEY_LEN+KP_PAD_LEN`. +Define `TAP_S_HANDSHAKE_LEN` as `DH_LEN+HASH_LEN`. The payload for a CREATE cell is an 'onion skin', which consists of -the first step of the DH handshake data (also known as g^x). This +the first step of the DH handshake data (also known as `g^x`). This value is encrypted using the "legacy hybrid encryption" algorithm -(see 0.4 above) to the server's onion key, giving a client handshake: - -```text - KP-encrypted: - Padding [KP_PAD_LEN bytes] - Symmetric key [KEY_LEN bytes] - First part of g^x [KP_ENC_LEN-KP_PAD_LEN-KEY_LEN bytes] - Symmetrically encrypted: - Second part of g^x [DH_LEN-(KP_ENC_LEN-KP_PAD_LEN-KEY_LEN) - bytes] -``` +(see ["Preliminaries » A bad hybrid encryption algorithm..."](./preliminaries.md#legacy-hybrid-encryption)) +to the server's onion key, giving a client handshake: + +| Field | Size +| ----- | ---- +| KP-encrypted: +| - Padding | `KP_PAD_LEN` bytes +| - Symmetric key | `KEY_LEN` bytes +| - First part of `g^x` | `KP_ENC_LEN-KP_PAD_LEN-KEY_LEN` bytes +| Symmetrically encrypted +| - Second part of `g^x` | `DH_LEN-(KP_ENC_LEN-KP_PAD_LEN-KEY_LEN)` bytes The payload for a CREATED cell, or the relay payload for an EXTENDED cell, contains: -```text - DH data (g^y) [DH_LEN bytes] - Derivative key data (KH) [HASH_LEN bytes] <see 5.2 below> -``` +| Field | Size +| ----- | ---- +| DH data (`g^y`) | `DH_LEN` bytes +| Derivative key data (`KH`) | `HASH_LEN` bytes (see ["Setting Circuit Keys"](./setting-circuit-keys.md)) + Once the handshake between the OP and an OR is completed, both can -now calculate g^xy with ordinary DH. Before computing g^xy, both parties -MUST verify that the received g^x or g^y value is not degenerate; -that is, it must be strictly greater than 1 and strictly less than p-1 -where p is the DH modulus. Implementations MUST NOT complete a handshake +now calculate `g^xy` with ordinary DH. Before computing `g^xy`, both parties +MUST verify that the received `g^x` or `g^y` value is not degenerate; +that is, it must be strictly greater than `1` and strictly less than `p-1` +where `p` is the DH modulus. Implementations MUST NOT complete a handshake with degenerate keys. Implementations MUST NOT discard other "weak" -g^x values. +`g^x` values. (Discarding degenerate keys is critical for security; if bad keys are not discarded, an attacker can substitute the OR's CREATED -cell's g^y with 0 or 1, thus creating a known g^xy and impersonating +cell's `g^y` with `0` or `1`, thus creating a known `g^xy` and impersonating the OR. Discarding other keys may allow attacks to learn bits of the private key.) -Once both parties have g^xy, they derive their shared circuit keys -and 'derivative key data' value via the KDF-TOR function in 5.2.1. +Once both parties have `g^xy`, they derive their shared circuit keys +and 'derivative key data' value via the +[KDF-TOR function](./setting-circuit-keys.md#kdf-tor). <a id="tor-spec.txt-5.1.4"></a> @@ -288,68 +286,75 @@ new Diffie-Hellman speed records" by D. J. Bernstein. In this section, define: ```text - H(x,t) as HMAC_SHA256 with message x and key t. - H_LENGTH = 32. - ID_LENGTH = 20. - G_LENGTH = 32 - PROTOID = "ntor-curve25519-sha256-1" - t_mac = PROTOID | ":mac" - t_key = PROTOID | ":key_extract" - t_verify = PROTOID | ":verify" - G = The preferred base point for curve25519 ([9]) - KEYGEN() = The curve25519 key generation algorithm, returning - a private/public keypair. - m_expand = PROTOID | ":key_expand" - KEYID(A) = A - EXP(a, b) = The ECDH algorithm for establishing a shared secret. +H(x,t) as HMAC_SHA256 with message x and key t. +H_LENGTH = 32. +ID_LENGTH = 20. +G_LENGTH = 32 +PROTOID = "ntor-curve25519-sha256-1" +t_mac = PROTOID | ":mac" +t_key = PROTOID | ":key_extract" +t_verify = PROTOID | ":verify" +G = The preferred base point for curve25519 ([9]) +KEYGEN() = The curve25519 key generation algorithm, returning + a private/public keypair. +m_expand = PROTOID | ":key_expand" +KEYID(A) = A +EXP(a, b) = The ECDH algorithm for establishing a shared secret. ``` To perform the handshake, the client needs to know an identity key digest for the server, and an ntor onion key (a curve25519 public -key) for that server. Call the ntor onion key "B". The client +key) for that server. Call the ntor onion key `B`. The client generates a temporary keypair: +```text x,X = KEYGEN() +``` and generates a client-side handshake with contents: -```text - NODEID Server identity digest [ID_LENGTH bytes] - KEYID KEYID(B) [H_LENGTH bytes] - CLIENT_KP X [G_LENGTH bytes] -``` +| Field | Value | Size +| ----- | ----- | ---- +| `NODEID` | Server identity digest | `ID_LENGTH` bytes +| `KEYID` | KEYID(B) | `H_LENGTH` bytes +| `CLIENT_KP` | X | `G_LENGTH` bytes -The server generates a keypair of y,Y = KEYGEN(), and uses its ntor -private key 'b' to compute: +The server generates a keypair of `y,Y = KEYGEN()`, and uses its ntor +private key `b` to compute: ```text - secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID - KEY_SEED = H(secret_input, t_key) - verify = H(secret_input, t_verify) - auth_input = verify | ID | B | Y | X | PROTOID | "Server" - - The server's handshake reply is: +secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID +KEY_SEED = H(secret_input, t_key) +verify = H(secret_input, t_verify) +auth_input = verify | ID | B | Y | X | PROTOID | "Server" +``` - SERVER_KP Y [G_LENGTH bytes] - AUTH H(auth_input, t_mac) [H_LENGTH bytes] +The server's handshake reply is: - The client then checks Y is in G^* [see NOTE below], and computes +| Field | Value | Size +| ----- | ----- | ---- +| `SERVER_KP` | `Y` | `G_LENGTH` bytes +| `AUTH` | `H(auth_input, t_mac)` | `H_LENGTH` bytes - secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID - KEY_SEED = H(secret_input, t_key) - verify = H(secret_input, t_verify) - auth_input = verify | ID | B | Y | X | PROTOID | "Server" +The client then checks `Y` is in G<sup>*</sup> [see NOTE below], and computes - The client verifies that AUTH == H(auth_input, t_mac). +```text +secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID +KEY_SEED = H(secret_input, t_key) +verify = H(secret_input, t_verify) +auth_input = verify | ID | B | Y | X | PROTOID | "Server" ``` -Both parties check that none of the EXP() operations produced the +The client verifies that `AUTH == H(auth_input, t_mac)`. + +Both parties check that none of the `EXP()` operations produced the point at infinity. \[NOTE: This is an adequate replacement for -checking Y for group membership, if the group is curve25519.\] +checking `Y` for group membership, if the group is curve25519.\] -Both parties now have a shared value for KEY_SEED. They expand this +Both parties now have a shared value for `KEY_SEED`. They expand this into the keys needed for the Tor relay protocol, using the KDF -described in 5.2.2 and the tag m_expand. +described in ["KDF-RFC5869"](./setting-circuit-keys.md#kdf-rfc5869) +and the tag `m_expand`. <a id="tor-spec.txt-5.1.4.1"></a> @@ -368,137 +373,151 @@ To advertise support for this handshake, servers advertise the In this handshake, we define: ```text - PROTOID = "ntor3-curve25519-sha3_256-1" - t_msgkdf = PROTOID | ":kdf_phase1" - t_msgmac = PROTOID | ":msg_mac" - t_key_seed = PROTOID | ":key_seed" - t_verify = PROTOID | ":verify" - t_final = PROTOID | ":kdf_final" - t_auth = PROTOID | ":auth_final" +PROTOID = "ntor3-curve25519-sha3_256-1" +t_msgkdf = PROTOID | ":kdf_phase1" +t_msgmac = PROTOID | ":msg_mac" +t_key_seed = PROTOID | ":key_seed" +t_verify = PROTOID | ":verify" +t_final = PROTOID | ":kdf_final" +t_auth = PROTOID | ":auth_final" - `ENCAP(s)` -- an encapsulation function. We define this - as `htonll(len(s)) | s`. (Note that `len(ENCAP(s)) = len(s) + 8`). +`ENCAP(s)` -- an encapsulation function. We define this +as `htonll(len(s)) | s`. (Note that `len(ENCAP(s)) = len(s) + 8`). - `PARTITION(s, n1, n2, n3, ...)` -- a function that partitions a - bytestring `s` into chunks of length `n1`, `n2`, `n3`, and so - on. Extra data is put into a final chunk. If `s` is not long - enough, the function fails. +`PARTITION(s, n1, n2, n3, ...)` -- a function that partitions a +bytestring `s` into chunks of length `n1`, `n2`, `n3`, and so +on. Extra data is put into a final chunk. If `s` is not long +enough, the function fails. - H(s, t) = SHA3_256(ENCAP(t) | s) - MAC(k, msg, t) = SHA3_256(ENCAP(t) | ENCAP(k) | s) - KDF(s, t) = SHAKE_256(ENCAP(t) | s) - ENC(k, m) = AES_256_CTR(k, m) +H(s, t) = SHA3_256(ENCAP(t) | s) +MAC(k, msg, t) = SHA3_256(ENCAP(t) | ENCAP(k) | s) +KDF(s, t) = SHAKE_256(ENCAP(t) | s) +ENC(k, m) = AES_256_CTR(k, m) - EXP(pk,sk), KEYGEN: defined as in curve25519 +EXP(pk,sk), KEYGEN: defined as in curve25519 - DIGEST_LEN = MAC_LEN = MAC_KEY_LEN = ENC_KEY_LEN = PUB_KEY_LEN = 32 +DIGEST_LEN = MAC_LEN = MAC_KEY_LEN = ENC_KEY_LEN = PUB_KEY_LEN = 32 - ID_LEN = 32 (representing an ed25519 identity key) +ID_LEN = 32 (representing an ed25519 identity key) - For any tag "t_foo": - H_foo(s) = H(s, t_foo) - MAC_foo(k, msg) = MAC(k, msg, t_foo) - KDF_foo(s) = KDF(s, t_foo) +For any tag "t_foo": + H_foo(s) = H(s, t_foo) + MAC_foo(k, msg) = MAC(k, msg, t_foo) + KDF_foo(s) = KDF(s, t_foo) +``` - Other notation is as in the ntor description in 5.1.4 above. +Other notation is as in the [ntor description above](#ntor). - The client begins by knowing: +The client begins by knowing: - B, ID -- The curve25519 onion key and Ed25519 ID of the server that it - wants to use. - CM -- A message it wants to send as part of its handshake. - VER -- An optional shared verification string: +```text +B, ID -- The curve25519 onion key and Ed25519 ID of the server that it + wants to use. +CM -- A message it wants to send as part of its handshake. +VER -- An optional shared verification string: +``` - The client computes: +The client computes: - x,X = KEYGEN() - Bx = EXP(B,x) - secret_input_phase1 = Bx | ID | X | B | PROTOID | ENCAP(VER) - phase1_keys = KDF_msgkdf(secret_input_phase1) - (ENC_K1, MAC_K1) = PARTITION(phase1_keys, ENC_KEY_LEN, MAC_KEY_LEN) - encrypted_msg = ENC(ENC_K1, CM) - msg_mac = MAC_msgmac(MAC_K1, ID | B | X | encrypted_msg) +```text +x,X = KEYGEN() +Bx = EXP(B,x) +secret_input_phase1 = Bx | ID | X | B | PROTOID | ENCAP(VER) +phase1_keys = KDF_msgkdf(secret_input_phase1) +(ENC_K1, MAC_K1) = PARTITION(phase1_keys, ENC_KEY_LEN, MAC_KEY_LEN) +encrypted_msg = ENC(ENC_K1, CM) +msg_mac = MAC_msgmac(MAC_K1, ID | B | X | encrypted_msg) +``` - The client then sends, as its CREATE handshake: + The client then sends, as its CREATE handshake: - NODEID ID [ID_LEN bytes] - KEYID B [PUB_KEY_LEN bytes] - CLIENT_PK X [PUB_KEY_LEN bytes] - MSG encrypted_msg [len(CM) bytes] - MAC msg_mac [MAC_LEN bytes] +| Field | Value | Size +| ----- | ----- | ---- +| `NODEID` | `ID` | `ID_LEN` bytes +| `KEYID` | `B` | `PUB_KEY_LEN` bytes +| `CLIENT_PK` | `X` | `PUB_KEY_LEN` bytes +| `MSG` | `encrypted_msg` | `len(CM)` bytes +| `MAC` | `msg_mac` | `MAC_LEN` bytes - The client remembers x, X, B, ID, Bx, and msg_mac. -``` +The client remembers `x`, `X`, `B`, `ID`, `Bx`, and `msg_mac`. -When the server receives this handshake, it checks whether NODEID is as -expected, and looks up the (b,B) keypair corresponding to KEYID. If the -keypair is missing or the NODEID is wrong, the handshake fails. +When the server receives this handshake, it checks whether `NODEID` is as +expected, and looks up the `(b,B)` keypair corresponding to `KEYID`. If the +keypair is missing or the `NODEID` is wrong, the handshake fails. Now the relay uses `X=CLIENT_PK` to compute: ```text - Xb = EXP(X,b) - secret_input_phase1 = Xb | ID | X | B | PROTOID | ENCAP(VER) - phase1_keys = KDF_msgkdf(secret_input_phase1) - (ENC_K1, MAC_K1) = PARTITION(phase1_keys, ENC_KEY_LEN, MAC_KEY_LEN) +Xb = EXP(X,b) +secret_input_phase1 = Xb | ID | X | B | PROTOID | ENCAP(VER) +phase1_keys = KDF_msgkdf(secret_input_phase1) +(ENC_K1, MAC_K1) = PARTITION(phase1_keys, ENC_KEY_LEN, MAC_KEY_LEN) - expected_mac = MAC_msgmac(MAC_K1, ID | B | X | MSG) +expected_mac = MAC_msgmac(MAC_K1, ID | B | X | MSG) ``` If `expected_mac` is not `MAC`, the handshake fails. Otherwise the relay computes `CM` as: +```text CM = DEC(MSG, ENC_K1) +``` The relay then checks whether `CM` is well-formed, and in response composes `SM`, the reply that it wants to send as part of the handshake. It then generates a new ephemeral keypair: +```text y,Y = KEYGEN() +``` and computes the rest of the handshake: ```text - Xy = EXP(X,y) - secret_input = Xy | Xb | ID | B | X | Y | PROTOID | ENCAP(VER) - ntor_key_seed = H_key_seed(secret_input) - verify = H_verify(secret_input) - - RAW_KEYSTREAM = KDF_final(ntor_key_seed) - (ENC_KEY, KEYSTREAM) = PARTITION(RAW_KEYSTREAM, ENC_KEY_LKEN, ...) +Xy = EXP(X,y) +secret_input = Xy | Xb | ID | B | X | Y | PROTOID | ENCAP(VER) +ntor_key_seed = H_key_seed(secret_input) +verify = H_verify(secret_input) - encrypted_msg = ENC(ENC_KEY, SM) +RAW_KEYSTREAM = KDF_final(ntor_key_seed) +(ENC_KEY, KEYSTREAM) = PARTITION(RAW_KEYSTREAM, ENC_KEY_LKEN, ...) - auth_input = verify | ID | B | Y | X | MAC | ENCAP(encrypted_msg) | - PROTOID | "Server" - AUTH = H_auth(auth_input) +encrypted_msg = ENC(ENC_KEY, SM) - The relay then sends as its CREATED handshake: +auth_input = verify | ID | B | Y | X | MAC | ENCAP(encrypted_msg) | + PROTOID | "Server" +AUTH = H_auth(auth_input) +``` - Y Y [PUB_KEY_LEN bytes] - AUTH AUTH [DIGEST_LEN bytes] - MSG encrypted_msg [len(SM) bytes, up to end of the message] +The relay then sends as its CREATED handshake: - Upon receiving this handshake, the client computes: +| Field | Value | Size +| ----- | ----- | ---- +| `Y` | `Y` | `PUB_KEY_LEN` bytes +| `AUTH` | `AUTH` | `DIGEST_LEN` bytes +| `MSG` | `encrypted_msg` | `len(SM)` bytes, up to end of the message - Yx = EXP(Y, x) - secret_input = Yx | Bx | ID | B | X | Y | PROTOID | ENCAP(VER) - ntor_key_seed = H_key_seed(secret_input) - verify = H_verify(secret_input) +Upon receiving this handshake, the client computes: - auth_input = verify | ID | B | Y | X | MAC | ENCAP(MSG) | - PROTOID | "Server" - AUTH_expected = H_auth(auth_input) +```text +Yx = EXP(Y, x) +secret_input = Yx | Bx | ID | B | X | Y | PROTOID | ENCAP(VER) +ntor_key_seed = H_key_seed(secret_input) +verify = H_verify(secret_input) + +auth_input = verify | ID | B | Y | X | MAC | ENCAP(MSG) | + PROTOID | "Server" +AUTH_expected = H_auth(auth_input) ``` -If AUTH_expected is equal to AUTH, then the handshake has +If `AUTH_expected` is equal to `AUTH`, then the handshake has succeeded. The client can then calculate: ```text - RAW_KEYSTREAM = KDF_final(ntor_key_seed) - (ENC_KEY, KEYSTREAM) = PARTITION(RAW_KEYSTREAM, ENC_KEY_LKEN, ...) +RAW_KEYSTREAM = KDF_final(ntor_key_seed) +(ENC_KEY, KEYSTREAM) = PARTITION(RAW_KEYSTREAM, ENC_KEY_LKEN, ...) - SM = DEC(ENC_KEY, MSG) +SM = DEC(ENC_KEY, MSG) ``` SM is the message from the relay, and the client uses KEYSTREAM to @@ -521,19 +540,21 @@ created. A CREATE_FAST cell contains: -Key material (X) \[HASH_LEN bytes\] +| Field | Size +| ----- | ---- +| Key material (`X`) | `HASH_LEN` bytes A CREATED_FAST cell contains: -```text - Key material (Y) [HASH_LEN bytes] - Derivative key data [HASH_LEN bytes] (See 5.2.1 below) +| Field | Size +| ----- | ---- +| Key material (`Y`) | `HASH_LEN` bytes +| Derivative key data | `HASH_LEN` bytes (See [KDF-TOR](./setting-circuit-keys.md#kdf-tor)) - The values of X and Y must be generated randomly. -``` +The values of `X` and `Y` must be generated randomly. -Once both parties have X and Y, they derive their shared circuit keys -and 'derivative key data' value via the KDF-TOR function in 5.2.1. +Once both parties have `X` and `Y`, they derive their shared circuit keys +and 'derivative key data' value via the [KDF-TOR function](./setting-circuit-keys.md#kdf-tor). The CREATE_FAST handshake is currently deprecated whenever it is not necessary; the migration is controlled by the "usecreatefast" @@ -550,51 +571,51 @@ relay to send additional data as part of the handshake. When used in a CREATE/CREATED handshake, this additional data must have the following format: -```text - N_EXTENSIONS [one byte] - N_EXTENSIONS times: - EXT_FIELD_TYPE [one byte] - EXT_FIELD_LEN [one byte] - EXT_FIELD [EXT_FIELD_LEN bytes] - - (`EXT_FIELD_LEN` may be zero, in which case EXT_FIELD is absent.) - - All parties MUST reject messages that are not well-formed per the - rules above. - - We do not specify specific TYPE semantics here; we leave those for - other proposals and specifications. - - Parties MUST ignore extensions with `EXT_FIELD_TYPE` bodies they do not - recognize. - - Unless otherwise specified in the documentation for an extension type: - * Each extension type SHOULD be sent only once in a message. - * Parties MUST ignore any occurrences all occurrences of an extension - with a given type after the first such occurrence. - * Extensions SHOULD be sent in numerically ascending order by type. - - (The above extension sorting and multiplicity rules are only defaults; - they may be overridden in the description of individual extensions.) - - Currently supported extensions are: - - 1 -- CC_FIELD_REQUEST [Client to server] - - Contains an empty payload. Signifies that the client - wants to use the extended congestion control described - in proposal 324. - - 2 -- CC_FIELD_RESPONSE [Server to client] - - Indicates that the relay will use the congestion control - of proposal 324, as requested by the client. One byte - in length: - - sendme_inc [1 byte] - - 3 -- Subprotocol Request [Client to Server] - - (RESERVED) Tells the endpoint what protocol version to use on the - circuit (prop346). -``` +| Field | Size +| ----- | ---- +| `N_EXTENSIONS` | one byte +| `N_EXTENSIONS` times: | +| - `EXT_FIELD_TYPE` | one byte +| - `EXT_FIELD_LEN` | one byte +| - `EXT_FIELD` | `EXT_FIELD_LEN` bytes + +(`EXT_FIELD_LEN` may be zero, in which case `EXT_FIELD` is absent.) + +All parties MUST reject messages that are not well-formed per the +rules above. + +We do not specify specific TYPE semantics here; we leave those for +other proposals and specifications. + +Parties MUST ignore extensions with `EXT_FIELD_TYPE` bodies they do not +recognize. + +Unless otherwise specified in the documentation for an extension type: + * Each extension type SHOULD be sent only once in a message. + * Parties MUST ignore any occurrences all occurrences of an extension + with a given type after the first such occurrence. + * Extensions SHOULD be sent in numerically ascending order by type. + +(The above extension sorting and multiplicity rules are only defaults; +they may be overridden in the description of individual extensions.) + +Currently supported extensions are: + + * 1 -- `CC_FIELD_REQUEST` [Client to server] + + Contains an empty payload. Signifies that the client + wants to use the extended congestion control described + in proposal 324. + + * 2 -- `CC_FIELD_RESPONSE` [Server to client] + + Indicates that the relay will use the congestion control + of proposal 324, as requested by the client. One byte + in length: + + `sendme_inc [1 byte]` + + * 3 -- Subprotocol Request [Client to Server] + + (RESERVED) Tells the endpoint what protocol version to use on the + circuit (prop346). diff --git a/spec/tor-spec/creating-circuits.md b/spec/tor-spec/creating-circuits.md index f2a1c7d..eb8de36 100644 --- a/spec/tor-spec/creating-circuits.md +++ b/spec/tor-spec/creating-circuits.md @@ -5,44 +5,42 @@ When creating a circuit through the network, the circuit creator (OP) performs the following steps: -```text - 1. Choose an onion router as an end node (R_N): - * N MAY be 1 for non-anonymous directory mirror, introduction point, - or service rendezvous connections. - * N SHOULD be 3 or more for anonymous connections. - Some end nodes accept streams (see 6.1), others are introduction - or rendezvous points (see rend-spec-{v2,v3}.txt). +1. Choose an onion router as an end node (R_N): + * N MAY be 1 for non-anonymous directory mirror, introduction point, + or service rendezvous connections. + * N SHOULD be 3 or more for anonymous connections. + Some end nodes accept streams (see ["Relay Cells"](./relay-cells.md#relay-cells)), + others are introduction or rendezvous points (see the [Rendezvous Spec](../rend-spec/index.md)). - 2. Choose a chain of (N-1) onion routers (R_1...R_N-1) to constitute - the path, such that no router appears in the path twice. +2. Choose a chain of (N-1) onion routers (R_1...R_N-1) to constitute + the path, such that no router appears in the path twice. - 3. If not already connected to the first router in the chain, - open a new connection to that router. +3. If not already connected to the first router in the chain, + open a new connection to that router. - 4. Choose a circID not already in use on the connection with the - first router in the chain; send a CREATE/CREATE2 cell along - the connection, to be received by the first onion router. +4. Choose a circID not already in use on the connection with the + first router in the chain; send a CREATE/CREATE2 cell along + the connection, to be received by the first onion router. - 5. Wait until a CREATED/CREATED2 cell is received; finish the - handshake and extract the forward key Kf_1 and the backward - key Kb_1. +5. Wait until a CREATED/CREATED2 cell is received; finish the + handshake and extract the forward key Kf_1 and the backward + key Kb_1. - 6. For each subsequent onion router R (R_2 through R_N), extend - the circuit to R. -``` +6. For each subsequent onion router R (R_2 through R_N), extend + the circuit to R. To extend the circuit by a single onion router R_M, the OP performs these steps: 1. Create an onion skin, encrypted to R_M's public onion key. -```text - 2. Send the onion skin in a relay EXTEND/EXTEND2 cell along - the circuit (see sections 5.1.2 and 5.5). +2. Send the onion skin in a relay EXTEND/EXTEND2 cell along + the circuit (see + ["EXTEND and EXTENDED cells"](./create-created-cells.md#EXTEND) + and ["Routing relay cells"](./routing-relay-cells.md#routing-relay-cells)). - 3. When a relay EXTENDED/EXTENDED2 cell is received, verify KH, - and calculate the shared keys. The circuit is now extended. -``` +3. When a relay EXTENDED/EXTENDED2 cell is received, verify KH, + and calculate the shared keys. The circuit is now extended. When an onion router receives an EXTEND relay cell, it sends a CREATE cell to the next onion router, with the enclosed onion skin as its @@ -52,7 +50,7 @@ When an onion router receives an EXTEND2 relay cell, it sends a CREATE2 cell to the next onion router, with the enclosed HLEN, HTYPE, and HDATA as its payload. The initiating onion router chooses some circID not yet used on the connection between the two onion routers. (But see section -5.1.1 above, concerning choosing circIDs.) +["Choosing circuit IDs in create cells"](./create-created-cells.md#choosing-circid)) As special cases, if the EXTEND/EXTEND2 cell includes a legacy identity, or identity fingerprint of all zeroes, or asks to extend back to the relay @@ -95,12 +93,10 @@ To prevent this, when an OR gets an extend request, it SHOULD use an existing OR connection if the ID matches, and ANY of the following conditions hold: -```text - - The IP matches the requested IP. - - The OR knows that the IP of the connection it's using is canonical - because it was listed in the NETINFO cell. + - The IP matches the requested IP. + - The OR knows that the IP of the connection it's using is canonical + because it was listed in the NETINFO cell. - ORs SHOULD NOT check the IPs that are listed in the server descriptor. - Trusting server IPs makes it easier to covertly impersonate a relay, after - stealing its keys. -``` +ORs SHOULD NOT check the IPs that are listed in the server descriptor. +Trusting server IPs makes it easier to covertly impersonate a relay, after +stealing its keys. diff --git a/spec/tor-spec/opening-streams.md b/spec/tor-spec/opening-streams.md index c3a0aa6..d59e26b 100644 --- a/spec/tor-spec/opening-streams.md +++ b/spec/tor-spec/opening-streams.md @@ -26,7 +26,8 @@ fingerprinting. Implementations MUST accept strings in any case. The FLAGS value has one or more of the following bits set, where "bit 1" is the LSB of the 32-bit value, and "bit 32" is the MSB. -(Remember that all values in Tor are big-endian (see 0.1.1 above), so +(Remember that all values in Tor are big-endian (see +["Preliminaries » Encoding integers"](./preliminaries.md#encoding)), so the MSB of a 4-byte value is the MSB of the first byte, and the LSB of a 4-byte value is the LSB of its last byte.) @@ -49,7 +50,8 @@ FLAGS, FLAGS is omitted from the message payload. Upon receiving this cell, the exit node resolves the address as necessary, and opens a new TCP connection to the target port. If the address cannot be resolved, or a connection can't be established, the -exit node replies with a RELAY_END cell. (See 6.3 below.) +exit node replies with a RELAY_END cell. (See +["Closing streams"](./closing-streams.md#closing-streams).) Otherwise, the exit node replies with a RELAY_CONNECTED cell, whose payload is in one of the following formats: diff --git a/spec/tor-spec/preliminaries.md b/spec/tor-spec/preliminaries.md index d911a5e..36468d8 100644 --- a/spec/tor-spec/preliminaries.md +++ b/spec/tor-spec/preliminaries.md @@ -11,7 +11,7 @@ <a id="tor-spec.txt-0.1"></a> -## Notation and encoding +## Notation and encoding{#notation-and-encoding} ```text KP -- a public key for an asymmetric cipher. @@ -34,7 +34,7 @@ Some specs mention "base32". This means RFC4648, without "=" padding. <a id="tor-spec.txt-0.1.1"></a> -### Encoding integers +### Encoding integers{#encoding} Unless we explicitly say otherwise below, all numeric values in the Tor protocol are encoded in network (big-endian) order. So a "32-bit diff --git a/spec/tor-spec/relay-cells.md b/spec/tor-spec/relay-cells.md index add1f42..e704d6a 100644 --- a/spec/tor-spec/relay-cells.md +++ b/spec/tor-spec/relay-cells.md @@ -15,45 +15,47 @@ End nodes that accept streams may be: The payload of each unencrypted RELAY cell consists of: -```text - Relay command [1 byte] - 'Recognized' [2 bytes] - StreamID [2 bytes] - Digest [4 bytes] - Length [2 bytes] - Data [Length bytes] - Padding [PAYLOAD_LEN - 11 - Length bytes] - - The relay commands are: - - 1 -- RELAY_BEGIN [forward] - 2 -- RELAY_DATA [forward or backward] - 3 -- RELAY_END [forward or backward] - 4 -- RELAY_CONNECTED [backward] - 5 -- RELAY_SENDME [forward or backward] [sometimes control] - 6 -- RELAY_EXTEND [forward] [control] - 7 -- RELAY_EXTENDED [backward] [control] - 8 -- RELAY_TRUNCATE [forward] [control] - 9 -- RELAY_TRUNCATED [backward] [control] - 10 -- RELAY_DROP [forward or backward] [control] - 11 -- RELAY_RESOLVE [forward] - 12 -- RELAY_RESOLVED [backward] - 13 -- RELAY_BEGIN_DIR [forward] - 14 -- RELAY_EXTEND2 [forward] [control] - 15 -- RELAY_EXTENDED2 [backward] [control] - - 16..18 -- Reserved for UDP; Not yet in use, see prop339. - - 19..22 -- Reserved for Conflux, see prop329. - - 32..40 -- Used for hidden services; see rend-spec-{v2,v3}.txt. - - 41..42 -- Used for circuit padding; see Section 3 of padding-spec.txt. - - Used for flow control; see Section 4 of prop324. - 43 -- XON [forward or backward] - 44 -- XOFF [forward or backward] -``` +| Field | Size +| ----- | ---- +| Relay command | 1 byte +| 'Recognized' | 2 bytes +| StreamID | 2 bytes +| Digest | 4 bytes +| Length | 2 bytes +| Data | Length bytes +| Padding | PAYLOAD_LEN - 11 - Length bytes + +The relay commands are: + +| Command | Identifier | Direction | Control? +| ------- | ---------- | --------- | -------- +| 1 | RELAY_BEGIN | forward | +| 2 | RELAY_DATA | forward or backward | +| 3 | RELAY_END | forward or backward | +| 4 | RELAY_CONNECTED | backward | +| 5 | RELAY_SENDME | forward or backward | sometimes control +| 6 | RELAY_EXTEND | forward | control +| 7 | RELAY_EXTENDED | backward | control +| 8 | RELAY_TRUNCATE | forward | control +| 9 | RELAY_TRUNCATED | backward | control +| 10 | RELAY_DROP | forward or backward | control +| 11 | RELAY_RESOLVE | forward | +| 12 | RELAY_RESOLVED | backward | +| 13 | RELAY_BEGIN_DIR | forward | +| 14 | RELAY_EXTEND2 | forward | control +| 15 | RELAY_EXTENDED2 | backward | control +| 16..18 | Reserved for UDP; Not yet in use, see [prop339][prop339]. +| 19..22 | Reserved for Conflux, see [prop329][prop329]. +| 32..40 | Used for hidden services; see the [rendezvous spec][rend-spec]. +| 41..42 | Used for circuit padding; see ["Circuit-level padding"][circ-padding] in the padding spec. +| 43 | XON (See Sec 4 of [prop324][prop324]) | forward or backward | +| 44 | XOFF (See Sec 4 of [prop324][prop324]) | forward or backward | + +[prop324]: ../proposals/324-rtt-congestion-control.txt +[prop329]: ../proposals/329-traffic-splitting.md +[prop339]: ../proposals/339-udp-over-tor.md +[rend-spec]: ../rend-spec/index.md +[circ-padding]: ../padding-spec/circuit-level-padding.md#circuit-level-padding Commands labelled as "forward" must only be sent by the originator of the circuit. Commands labelled as "backward" must only be sent by @@ -127,34 +129,36 @@ single field, namely 'Recognized' is not sufficient, as outlined above. When ENCRYPTING a RELAY cell, an implementation does the following: ```text - # Encode the cell in binary (recognized and digest set to zero) - tmp = cmd + [0, 0] + stream_id + [0, 0, 0, 0] + length + data + padding +# Encode the cell in binary (recognized and digest set to zero) +tmp = cmd + [0, 0] + stream_id + [0, 0, 0, 0] + length + data + padding - # Update the digest with the encoded data - digest_state = hash_update(digest_state, tmp) - digest = hash_calculate(digest_state) +# Update the digest with the encoded data +digest_state = hash_update(digest_state, tmp) +digest = hash_calculate(digest_state) - # The encoded data is the same as above with the digest field not being - # zero anymore - encoded = cmd + [0, 0] + stream_id + digest[0..4] + length + data + - padding +# The encoded data is the same as above with the digest field not being +# zero anymore +encoded = cmd + [0, 0] + stream_id + digest[0..4] + length + data + + padding - # Now we can encrypt the cell by adding the onion layers ... +# Now we can encrypt the cell by adding the onion layers ... +``` - When DECRYPTING a RELAY cell, an implementation does the following: + When DECRYPTING a RELAY cell, an implementation does the following: - decrypted = decrypt(cell) +```text +decrypted = decrypt(cell) - # Replace the digest field in decrypted by zeros - tmp = decrypted[0..5] + [0, 0, 0, 0] + decrypted[9..] +# Replace the digest field in decrypted by zeros +tmp = decrypted[0..5] + [0, 0, 0, 0] + decrypted[9..] - # Update the digest field with the decrypted data and its digest field - # set to zero - digest_state = hash_update(digest_state, tmp) - digest = hash_calculate(digest_state) +# Update the digest field with the decrypted data and its digest field +# set to zero +digest_state = hash_update(digest_state, tmp) +digest = hash_calculate(digest_state) - if digest[0..4] == decrypted[5..9] - # The cell has been fully decrypted ... +if digest[0..4] == decrypted[5..9] + # The cell has been fully decrypted ... ``` The caveat itself is that only the binary data with the digest bytes set to diff --git a/spec/tor-spec/setting-circuit-keys.md b/spec/tor-spec/setting-circuit-keys.md index 6cea0f3..200862f 100644 --- a/spec/tor-spec/setting-circuit-keys.md +++ b/spec/tor-spec/setting-circuit-keys.md @@ -4,7 +4,7 @@ <a id="tor-spec.txt-5.2.1"></a> -## KDF-TOR +## KDF-TOR{#kdf-tor} This key derivation function is used by the TAP and CREATE_FAST handshakes, and in the current hidden service protocol. It shouldn't @@ -36,7 +36,7 @@ Kb is used to encrypt the stream of data going from the OR to the OP. <a id="tor-spec.txt-5.2.2"></a> -## KDF-RFC5869 +## KDF-RFC5869{#kdf-rfc5869} For newer KDF needs, Tor uses the key derivation function HKDF from RFC5869, instantiated with SHA256. (This is due to a construction diff --git a/spec/vanguards-spec/full-vanguards.md b/spec/vanguards-spec/full-vanguards.md new file mode 100644 index 0000000..c733d8a --- /dev/null +++ b/spec/vanguards-spec/full-vanguards.md @@ -0,0 +1,133 @@ +# Full Vanguards + +Full Vanguards is intended for use by long-lived onion services, which intend +to remain in operation for longer than one month. + +Full Vanguards achieves this longer expected duration by having +two layers of additional fixed relays, of different rotation periods. + +The rotation period of the first vanguard layer (layer 2 guards) is chosen +such that it requires an extremely long and persistent Sybil attack, or a +coercion/compromise attack. + +The rotation period of the second vanguard layer (layer 3 guards) is chosen to +be small enough to force the adversary to perform a Sybil attack against this +layer, rather than attempting to coerce these relays. + +## Threat model, Assumptions, and Goals + +Consider an adversary with the following powers: + +```text + - Can launch a Sybil guard discovery attack against any position of a + rendezvous circuit. The slower the rotation period of their target + position, the longer the attack takes. Similarly, the higher the + percentage of the network is controlled by them, the faster the + attack runs. + + - Can compromise additional relays on the network, but this compromise + takes time and potentially even coercive action, and also carries risk + of discovery. +``` + +We also make the following assumptions about the types of attacks: + + 1. A Sybil attack is observable by both people monitoring the network + for large numbers of new relays, as well as vigilant hidden service + operators. It will require large amounts of traffic sent towards the + hidden service over many many test circuits. + + 2. A Sybil attack requires either a protocol side channel or an application-layer + timing side channel in order to determine successful placement next + to the relay that the adversary is attempting to discover. When Tor's internal + protocol side channels are dealt with, this will be both observable and + controllable at the Application Layer, by operators. + + 3. The adversary is strongly disincentivized from compromising additional + relays that may prove useless, as active compromise attempts are even more + risky for the adversary than a Sybil attack in terms of being noticed. In + other words, the adversary is unlikely to attempt to compromise or coerce + additional relays that are in use for only a short period of time. + +Given this threat model, our security parameters were selected so that the +first two layers of guards should take a very long period of time to attack +using a Sybil guard discovery attack and hence require a relay compromise +attack. + +On the other hand, the outermost layer of guards (the third layer) should +rotate fast enough to _require_ a Sybil attack. If the adversary were to +attempt to compromise or coerce these relays after they are discovered, their +rotation times should be fast enough that the adversary has a very high +probability of them no longer being in use. + +# Design + +When a hidden service picks its guard relays, it also picks an +additional NUM_LAYER2_GUARDS-sized set of middle relays for its +`second_guard_set`, as well as a NUM_LAYER3_GUARDS-sized set of +middle relays for its `third_guard_set`. + +When a hidden service needs to establish a circuit to an HSDir, +introduction point or a rendezvous point, it uses relays from +`second_guard_set` as the second hop of the circuit and relays from +`third_guard_set` as third hop of the circuit. + +A hidden service rotates relays from the 'second_guard_set' at a uniformly +random time between MIN_SECOND_GUARD_LIFETIME hours and +MAX_SECOND_GUARD_LIFETIME hours, chosen for each layer 2 relay. +Implementations MAY expose this layer as an explicit configuration option to +pin specific relays, similar to how a user is allowed to pin specific Guards. + +A hidden service rotates relays from the 'third_guard_set' at a random time +between MIN_THIRD_GUARD_LIFETIME and MAX_THIRD_GUARD_LIFETIME hours, as +weighted by the [max(X,X) +distribution](../vanguards-spec/vanguards-stats.md#MaxDist), chosen for each +relay. This skewed distribution was chosen so that there is some probability +of a very short rotation period, to deter compromise/coercion, but biased +towards the longer periods, in favor of a somewhat lengthy Sybil attack. For +this reason, users SHOULD NOT be encouraged to pin this layer. + +Each relay's rotation time is tracked independently, to avoid disclosing +the rotation times of the primary and second-level guards. + +The selected vanguards and their rotation timestamp MUST be persisted to disk. + +## Parameterization + +We set NUM_LAYER2_GUARDS to 4 relays and NUM_LAYER3_GUARDS to 6 relays. + +We set MIN_SECOND_GUARD_LIFETIME to 30 days, and MAX_SECOND_GUARD_LIFETIME to +60 days inclusive, for an average rotation rate of 45 days, using a uniform +distribution. This range was chosen to average out to half of the Guard +rotation period; there is no strong motivation for it otherwise, other than to +be long. In fact, it could be set as long as the Guard rotation, and longer +periods MAY be provided as a configuration parameter. + +From the [Sybil rotation table](../vanguards-spec/vanguards-stats.md#SybilTable) in [statistical +analysis](../vanguards-spec/vanguards-stats.md), with NUM_LAYER2_GUARDS=4, it +can be seen that this means that the Sybil attack on layer3 will complete with +50% chance in 18\*45 days (2.2 years) for the 1% adversary, 180 days for the +5% adversary, and 90 days for the 10% adversary, with a 45 day average +rotation period. + +If this range is set equal to the Guard rotation period (90 days), the 50% +probability of Sybil success requires 18\*90 days (4.4 years) for the 1% +adversary, 4\*90 days (1 year) for the 5% adversary, and 2\*90 days (6 months) +for the 10% adversary. + +We set MIN_THIRD_GUARD_LIFETIME to 1 hour, and MAX_THIRD_GUARD_LIFETIME to 48 +hours inclusive, for an average rotation rate of 31.5 hours, using the +[max(X,X) distribution](../vanguards-spec/vanguards-stats.md#MaxDist). +(Again, this wide range and bias is used to discourage the adversary from +exclusively performing coercive attacks, as opposed to mounting the Sybil +attack, so increasing it substantially is not recommended). + +From the [Sybil rotation +table](./vanguards-spec/vanguards-stats.md#SybilTable) in [statistical +analysis](../vanguards-spec/vanguards-stats.md), with NUM_LAYER3_GUARDS=6, it +can be seen that this means that the Sybil attack on layer3 will complete with +50% chance in 9\*31.5 hours (15.75 days) for the 1% adversary, ~4 days for the +5% adversary, and 2.62 days for the 10% adversary. + +See the [statistical analysis](../vanguards-spec/vanguards-stats.md) for more +analysis on these constants. diff --git a/spec/vanguards-spec/index.md b/spec/vanguards-spec/index.md new file mode 100644 index 0000000..44883e9 --- /dev/null +++ b/spec/vanguards-spec/index.md @@ -0,0 +1,144 @@ +# Tor Vanguards Specification + +<a id="vanguards-spec.txt-1"></a> + +## Introduction and motivation + +A guard discovery attack allows attackers to determine the guard relay of a +Tor client. The hidden service protocol provides an attack vector for a guard +discovery attack since anyone can force an HS to construct a 3-hop circuit to +a relay, and repeat this process until one of the adversary's middle relays +eventually ends up chosen in a circuit. These attacks are also possible to +perform against clients, by causing an application to make repeated +connections to multiple unique onion services. + +The adversary must use a protocol side channel to confirm that their relay was +chosen in this position (see [Proposal +#344](../proposals/344-protocol-info-leaks.txt)), and then learns the guard +relay of a client, or service. + +When a successful guard discovery attack is followed with compromise or +coercion of the guard relay, the onion service or onion client can be +deanonymized. Alternatively, Netflow analytics data purchase can be (and has +been) used for this deanonymization, without interacting with the Guard relay +directly (see again [Proposal #344](../proposals/344-protocol-info-leaks.txt)). + +This specification assumes that Tor protocol side channels have 100% accuracy +and are undetectable, for simplicity in [reasoning about expected attack +times](../vanguards-spec/vanguards-stats.md). Presently, such 100% accurate +side channels exist in silent form, in the Tor Protocol itself. + +As work on addressing Tor's protocol side channels progresses, these attacks +will require application-layer activity that can be monitored and managed by +service operators, as opposed to silent and unobservable side channel activity +via the Tor Protocol itself. Application-layer side channels are also expected +to have less accuracy than native Tor protocol side channels, due to the +possibility of false positives caused by similar application activity +elsewhere on the Tor network. Despite this, we will preserve the original +assumption of 100% accuracy, for simplicity of explanation. + +## Overview + +In this specification, we specify two forms of a multi-layered Guard system: +one for long-lived services, called Full Vanguards, and one for onion clients +and short-lived services, called Vanguards-Lite. + +Both approaches use a mesh topology, where circuits can be created from any +relay in a preceding layer to any relay in a subsequent layer. + +The core difference between these two mechanisms is that Full Vanguards has +two additional layers of fixed vanguard relays, which results in longer path +lengths and higher latency. In contrast, Vanguards-Lite has only one +additional layer of fixed vanguard relays, and preserves the original path +lengths in use by onion services. Thus, Full Vanguards comes with a +performance cost, where as Vanguards-Lite does not. The rotation periods +of the two approaches also differ. + +Vanguards-Lite MUST be the default for all onion service and onion client +activity; Full Vanguards SHOULD be available as an optional configuration +option for services. + +Neither system applies to Exit activity. + +### Terminology + +Tor's original guards are called First Layer Guards. + +The first layer of vanguards is at the second hop, and is called the +Second Layer Guards. + +The second layer of vanguards is at the third hop, and is called the Third +Layer Guards. + +### Visualizing Full Vanguards + +Full Vanguards pins these two middle positions into a mesh topology, where any +relay in a layer can be used in that position in a circuit, as follows: + +```text + -> vanguard_2A + -> vanguard_3A + -> guard_1A -> vanguard_2B -> vanguard_3B + HS -> vanguard_3C + -> guard_1B -> vanguard_2C -> vanguard_3D + -> vanguard_3E + -> vanguard_2D -> vanguard_3F +``` + +Additionally, to avoid trivial discovery of the third layer, and to minimize +linkability, we insert an extra middle relay after the third layer guard for +client side intro and hsdir circuits, and service-side rendezvous circuits. +This means that the set of paths for Client (C) and Service (S) side look like +this: + +```text + Client hsdir: C - G - L2 - L3 - M - HSDIR + Client intro: C - G - L2 - L3 - M - I + Client rend: C - G - L2 - L3 - R + Service hsdir: S - G - L2 - L3 - HSDIR + Service intro: S - G - L2 - L3 - I + Service rend: S - G - L2 - L3 - M - R +``` + +### Visualizing Vanguards-Lite + +Vanguards-Lite uses only one layer of vanguards: + +```text + -> vanguard_2A + + -> guard_1A -> vanguard_2B + HS + -> guard_1B -> vanguard_2C + + -> vanguard_2D +``` + +This yields shorter path lengths, of the following form: + +```text + Client hsdir: C -> G -> L2 -> M -> HSDir + Client intro: C -> G -> L2 -> M -> Intro + Client rend: C -> G -> L2 -> Rend + Service hsdir: C -> G -> L2 -> M -> HSDir + Service intro: C -> G -> L2 -> M -> Intro + Service rend: C -> G -> L2 -> M -> Rend +``` + +## Alternatives + +An alternative to vanguards for client activity is to restrict the number of +onion services that a Tor client is allowed to connect to, in a certain period +of time. This defense was explored in [Onion Not +Found](https://petsymposium.org/2022/files/papers/issue1/popets-2022-0026.pdf). + +We have opted not to deploy this defense, for three reasons: + + 1. It does not generalize to the service-side of onion services + 2. Setting appropriate rate limits on the number of onion service content +elements on a page for Tor Browser is difficult. Sites like Facebook use +multiple onion domains for various content elements on a single page. + 3. It is even more difficult to limit the number of service connections for + arbitrary applications, such as cryptocurrency wallets, mining, and other + distributed apps deployed on top of onion services that connect to multiple + services (such as Ricochet). diff --git a/spec/vanguards-spec/path-construction.md b/spec/vanguards-spec/path-construction.md new file mode 100644 index 0000000..521629e --- /dev/null +++ b/spec/vanguards-spec/path-construction.md @@ -0,0 +1,53 @@ +# Path Construction + +Both vanguards systems use a mesh topology: this means that circuits select +a hop from each layer independently, allowing paths from any relay in a +layer to any relay in the next layer. + +## Selecting Relays + +Vanguards relays are selected from relays with the Stable and Fast flags. + +Tor replaces a vanguard whenever it is no longer listed in the most +recent consensus, with the goal that we will always have the right +number of vanguards ready to be used. + +For implementation reasons, we also replace a vanguard if it loses +the Fast or Stable flag, because the path selection logic wants middle +nodes to have those flags when it's building preemptive vanguard-using +circuits. + +The design doesn't have to be this way: we might instead have chosen to keep +vanguards in our list as long as possible, and continue to use them even if +they have lost some flags. This tradeoff is similar to the one in [Bug +#17773](https://bugs.torproject.org/17773), about whether to continue using +Entry Guards if they lose the Guard flag -- and Tor's current choice is "no, +rotate" for that case too. + +## Path Restriction Changes + +Path restrictions, as well as the ordering of their application, are currently +extremely problematic, resulting in information leaks with this topology. +Until they are reworked, we disable many of them for onion service circuits. + +In particular, we allow the following: + 1. Nodes from the same /16 and same family for any/all hops in a circuit + 2. Guard nodes can be chosen for RP/IP/HSDIR + 3. Guard nodes can be chosen for hop before RP/IP/HSDIR. + +The first change prevents the situation where paths cannot be built if two +layers all share the same subnet and/or node family, or if a layer consists of +only one family and that family is the same as the RP/IP/HSDIR. It also +prevents the the use of a different entry guard based on the family or subnet +of the IP, HSDIR, or RP. (Alternatives of this permissive behavior are +possible: For example, each layer could ensure that it does not consist solely +of the same family or /16, but this property cannot easily apply to conflux +circuits). + +The second change prevents an adversary from forcing the use of a different +entry guard by enumerating all guard-flagged nodes as the RP. This change is +important once onion services support conflux. + +The third change prevents an adversary from learning the guard node by way +of noticing which nodes were not chosen for the hop before it. This change is +important once onion services support conflux. diff --git a/spec/vanguards-spec/vanguards-stats.md b/spec/vanguards-spec/vanguards-stats.md new file mode 100644 index 0000000..445f2f0 --- /dev/null +++ b/spec/vanguards-spec/vanguards-stats.md @@ -0,0 +1,195 @@ +# Vanguard Rotation Statistics + +## Sybil rotation counts for a given number of Guards {#SybilTable} + +The probability of Sybil success for Guard discovery can be modeled as +the probability of choosing 1 or more malicious middle nodes for a +sensitive circuit over some period of time. + +```text + P(At least 1 bad middle) = 1 - P(All Good Middles) + = 1 - P(One Good middle)^(num_middles) + = 1 - (1 - c/n)^(num_middles) +``` + +c/n is the adversary compromise percentage + +In the case of Vanguards, num_middles is the number of Guards you rotate +through in a given time period. This is a function of the number of vanguards +in that position (v), as well as the number of rotations (r). + +```text + P(At least one bad middle) = 1 - (1 - c/n)^(v*r) +``` + +Here's detailed tables in terms of the number of rotations required for +a given Sybil success rate for certain number of guards. + +```text + 1.0% Network Compromise: + Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen + 10% 11 6 4 3 3 2 2 2 2 1 1 + 15% 17 9 6 5 4 3 3 2 2 2 2 + 25% 29 15 10 8 6 5 4 4 3 3 2 + 50% 69 35 23 18 14 12 9 8 7 6 5 + 60% 92 46 31 23 19 16 12 11 10 8 6 + 75% 138 69 46 35 28 23 18 16 14 12 9 + 85% 189 95 63 48 38 32 24 21 19 16 12 + 90% 230 115 77 58 46 39 29 26 23 20 15 + 95% 299 150 100 75 60 50 38 34 30 25 19 + 99% 459 230 153 115 92 77 58 51 46 39 29 + + 5.0% Network Compromise: + Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen + 10% 3 2 1 1 1 1 1 1 1 1 1 + 15% 4 2 2 1 1 1 1 1 1 1 1 + 25% 6 3 2 2 2 1 1 1 1 1 1 + 50% 14 7 5 4 3 3 2 2 2 2 1 + 60% 18 9 6 5 4 3 3 2 2 2 2 + 75% 28 14 10 7 6 5 4 4 3 3 2 + 85% 37 19 13 10 8 7 5 5 4 4 3 + 90% 45 23 15 12 9 8 6 5 5 4 3 + 95% 59 30 20 15 12 10 8 7 6 5 4 + 99% 90 45 30 23 18 15 12 10 9 8 6 + + 10.0% Network Compromise: + Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen + 10% 2 1 1 1 1 1 1 1 1 1 1 + 15% 2 1 1 1 1 1 1 1 1 1 1 + 25% 3 2 1 1 1 1 1 1 1 1 1 + 50% 7 4 3 2 2 2 1 1 1 1 1 + 60% 9 5 3 3 2 2 2 1 1 1 1 + 75% 14 7 5 4 3 3 2 2 2 2 1 + 85% 19 10 7 5 4 4 3 3 2 2 2 + 90% 22 11 8 6 5 4 3 3 3 2 2 + 95% 29 15 10 8 6 5 4 4 3 3 2 + 99% 44 22 15 11 9 8 6 5 5 4 3 +``` + +The rotation counts in these tables were generated with: + +## Skewed Rotation Distribution {#MaxDist} + +In order to skew the distribution of the third layer guard towards +higher values, we use max(X,X) for the distribution, where X is a +random variable that takes on values from the uniform distribution. + +Here's a table of expectation (arithmetic means) for relevant +ranges of X (sampled from 0..N-1). The table was generated with the +following python functions: + +```text + + def ProbMinXX(N, i): return (2.0*(N-i)-1)/(N*N) + def ProbMaxXX(N, i): return (2.0*i+1)/(N*N) + + def ExpFn(N, ProbFunc): + exp = 0.0 + for i in range(N): exp += i*ProbFunc(N, i) + return exp +``` + +The current choice for second-layer Vanguards-Lite guards is noted with **, +and the current choice for third-layer Full Vanguards is noted with ***. + +```text + Range Min(X,X) Max(X,X) + 22 6.84 14.16** + 23 7.17 14.83 + 24 7.51 15.49 + 25 7.84 16.16 + 26 8.17 16.83 + 27 8.51 17.49 + 28 8.84 18.16 + 29 9.17 18.83 + 30 9.51 19.49 + 31 9.84 20.16 + 32 10.17 20.83 + 33 10.51 21.49 + 34 10.84 22.16 + 35 11.17 22.83 + 36 11.50 23.50 + 37 11.84 24.16 + 38 12.17 24.83 + 39 12.50 25.50 + 40 12.84 26.16 + 40 12.84 26.16 + 41 13.17 26.83 + 42 13.50 27.50 + 43 13.84 28.16 + 44 14.17 28.83 + 45 14.50 29.50 + 46 14.84 30.16 + 47 15.17 30.83 + 48 15.50 31.50*** +``` + +The Cumulative Density Function (CDF) tells us the probability that a +guard will no longer be in use after a given number of time units have +passed. + +Because the Sybil attack on the third node is expected to complete at any +point in the second node's rotation period with uniform probability, if we +want to know the probability that a second-level Guard node will still be in +use after t days, we first need to compute the probability distribution of +the rotation duration of the second-level guard at a uniformly random point +in time. Let's call this P(R=r). + +For P(R=r), the probability of the rotation duration depends on the selection +probability of a rotation duration, and the fraction of total time that +rotation is likely to be in use. This can be written as: + +```text + P(R=r) = ProbMaxXX(X=r)*r / \sum_{i=1}^N ProbMaxXX(X=i)*i +``` + + or in Python: + +```text + def ProbR(N, r, ProbFunc=ProbMaxXX): + return ProbFunc(N, r)*r/ExpFn(N, ProbFunc) +``` + +For the full CDF, we simply sum up the fractional probability density for +all rotation durations. For rotation durations less than t days, we add the +entire probability mass for that period to the density function. For +durations d greater than t days, we take the fraction of that rotation +period's selection probability and multiply it by t/d and add it to the +density. In other words: + +```text + def FullCDF(N, t, ProbFunc=ProbR): + density = 0.0 + for d in range(N): + if t >= d: density += ProbFunc(N, d) + # The +1's below compensate for 0-indexed arrays: + else: density += ProbFunc(N, d)*(float(t+1))/(d+1) + return density +``` + +Computing this yields the following distribution for our current parameters: + +```text + t P(SECOND_ROTATION <= t) + 1 0.03247 + 2 0.06494 + 3 0.09738 + 4 0.12977 + 5 0.16207 + 10 0.32111 + 15 0.47298 + 20 0.61353 + 25 0.73856 + 30 0.84391 + 35 0.92539 + 40 0.97882 + 45 1.00000 +``` + +This CDF tells us that for the second-level Guard rotation, the +adversary can expect that 3.3% of the time, their third-level Sybil +attack will provide them with a second-level guard node that has only +1 day remaining before it rotates. 6.5% of the time, there will +be only 2 day or less remaining, and 9.7% of the time, 3 days or less. + +Note that this distribution is still a day-resolution approximation. |