commit 2e695e7674ba9f8d5ca712578db6ea67d5be0092 Author: Nick Mathewson <nickm@torproject.org> Date: Wed Mar 13 13:02:18 2013 -0400 Integrate proposals 200 (create2) and 216 (ntor) into the specs --- dir-spec.txt | 28 ++- proposals/200-new-create-and-extend-cells.txt | 3 +- proposals/216-ntor-handshake.txt | 3 +- tor-spec.txt | 314 +++++++++++++++++++++---- 4 files changed, 294 insertions(+), 54 deletions(-) diff --git a/dir-spec.txt b/dir-spec.txt index c75bbb9..c5ca5c1 100644 --- a/dir-spec.txt +++ b/dir-spec.txt @@ -444,10 +444,20 @@ [Exactly once] - This key is used to encrypt EXTEND cells for this OR. The key MUST be + This key is used to encrypt CREATE cells for this OR. The key MUST be accepted for at least 1 week after any new key is published in a subsequent descriptor. It MUST be 1024 bits. + "ntor-onion-key" base-64-encoded-key + + [At most once] + + A public key used for the ntor circuit extended handshake. It's the + standard encoding of the OR's curve25519 public key, encoded in base + 64. The trailing = sign may be omitted from the base64 encoding. The + key MUST be accepted for at least 1 week after any new key is + published in a subsequent descriptor. + "signing-key" NL a public key in PEM format [Exactly once] @@ -1098,6 +1108,15 @@ The "onion-key" element as specified in 2.1. + "ntor-onion-key" base-64-encoded-key + + [At most once] + + The "ntor-onion-key" element as specified in 2.1. + + (Only included when the vote or consensus is generated with + consensus-method 16 or later.) + "a" SP address ":" portlist NL [Any number] @@ -1836,6 +1855,13 @@ consensuses may include "a" lines listing additional OR ports. + * XXXXX 15 + + * If consensus method 16 or later is used, ntor-onion-key + are included in microdescriptors + + * XXXXX 17 + The signatures at the end of a consensus document are sorted in ascending order by identity digest. diff --git a/proposals/200-new-create-and-extend-cells.txt b/proposals/200-new-create-and-extend-cells.txt index 43025d4..1a556dc 100644 --- a/proposals/200-new-create-and-extend-cells.txt +++ b/proposals/200-new-create-and-extend-cells.txt @@ -2,7 +2,8 @@ Filename: 200-new-create-and-extend-cells.txt Title: Adding new, extensible CREATE, EXTEND, and related cells Author: Robert Ransom Created: 2012-03-22 -Status: Finished +Status: Closed +Implemented-In: 0.2.4.8-alpha History diff --git a/proposals/216-ntor-handshake.txt b/proposals/216-ntor-handshake.txt index 35d4a37..e0c4f63 100644 --- a/proposals/216-ntor-handshake.txt +++ b/proposals/216-ntor-handshake.txt @@ -2,7 +2,8 @@ Filename: 216-ntor-handshake.txt Title: Improved circuit-creation key exchange Author: Nick Mathewson Created: 11-May-2011 -Status: Finished +Status: Closed +Implemented-In: 0.2.4.8-alpha Summary: diff --git a/tor-spec.txt b/tor-spec.txt index f107da5..0c333e7 100644 --- a/tor-spec.txt +++ b/tor-spec.txt @@ -69,6 +69,8 @@ see tor-design.pdf. function. We leave the optional "Label" parameter unset. (For OAEP padding, see ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf) + For the "ntor" handshake, we also use the Curve25519 elliptic curve group. + For Diffie-Hellman, we use a generator (g) of 2. For the modulus (p), we use the 1024-bit safe prime from rfc2409 section 6.2 whose hex representation is: @@ -386,6 +388,8 @@ see tor-design.pdf. 6 -- CREATED_FAST (Circuit created, no PK) (See Sec 5.1) 8 -- NETINFO (Time and address info) (See Sec 4.5) 9 -- RELAY_EARLY (End-to-end data; limited)(See Sec 5.6) + 10 -- CREATE2 (Extended CREATE cell) (See Sec 5.1) + 11 -- CREATED2 (Extended CREATED cell) (See Sec 5.1) Variable-length command values are: 7 -- VERSIONS (Negotiate proto version) (See Sec 4) @@ -647,43 +651,64 @@ see tor-design.pdf. 5.1. CREATE and CREATED cells Users set up circuits incrementally, one hop at a time. To create a - new circuit, OPs send a CREATE cell to the first node, with the - first half of the DH handshake; that node responds with a CREATED - cell with the second half of the DH handshake plus the first 20 bytes - of derivative key data (see section 5.2). To extend a circuit past - the first hop, the OP sends an EXTEND relay cell (see section 5) - which instructs the last node in the circuit to send a CREATE cell - to extend the circuit. - - 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 value is hybrid-encrypted (see 0.3) to Bob's onion key, giving - an onion-skin of: - PK-encrypted: - Padding [PK_PAD_LEN bytes] - Symmetric key [KEY_LEN bytes] - First part of g^x [PK_ENC_LEN-PK_PAD_LEN-KEY_LEN bytes] - Symmetrically encrypted: - Second part of g^x [DH_LEN-(PK_ENC_LEN-PK_PAD_LEN-KEY_LEN) - bytes] + new circuit, OPs send a CREATE cell to the first node, with the first + half of an authenticated handshake; that node responds with a CREATED + cell with the second half of the handshake. To extend a circuit past + the first hop, the OP sends an EXTEND relay cell (see section 5.1.2) + which instructs the last node in the circuit to send a CREATE cell to + extend the circuit. + + There are two kinds of CREATE and CREATED cells: The older + "CREATE/CREATED" format, and the newer "CREATE2/CREATED2" format. The + newer format is extensible by design; the older one is not. + + A CREATE2 cell contains: + HTYPE (Client Handshake Type) [2 bytes] + HLEN (Client Handshake Data Len) [2 bytes] + HDATA (Client Handshake Data) [HLEN bytes] + + A CREATED2 cell contains: + HLEN (Server Handshake Data Len) [2 bytes] + HDATA (Server Handshake Data) [HLEN bytes] + + Recognized handshake types are: + 0x0000 TAP -- the original Tor handshake; see 5.1.3 + 0x0001 reserved + 0x0002 ntor -- the ntor+curve25519+sha256 handshake; see 5.1.4 + + + The format of a CREATE cell is one of the following: + HDATA (Client Handshake Data) [TAP_C_HANDSHAKE_LEN bytes] + or + HTAG (Client Handshake Type Tag) [16 bytes] + HDATA (Client Handshake Data) [TAP_C_HANDSHAKE_LEN-16 bytes] + + 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.1 below. Recognized HTAG values are: + + ntor -- 'ntorNTORntorNTOR' + + The format of a CREATED cell is: + HDATA (Server Handshake Data) [TAP_S_HANDSHAKE_LEN bytes] + It's equivalent to a CREATED2 cell with length of and length of + TAP_S_HANDSHAKE_LEN. - The relay payload for an EXTEND relay cell consists of: - Address [4 bytes] - Port [2 bytes] - Onion skin [DH_LEN+KEY_LEN+PK_PAD_LEN bytes] - Identity fingerprint [HASH_LEN bytes] + As usual with DH, x and y MUST be generated randomly. - The port and address field denote the IPv4 address and port of the next - onion router in the circuit; the public key hash is the hash of the PKCS#1 - ASN1 encoding of the next onion router's identity (signing) key. (See 0.3 - above.) Including this hash allows the extending OR verify that it is - indeed connected to the correct target OR, and prevents certain - man-in-the-middle attacks. + In general, clients SHOULD use CREATE whenever they are using the TAP + handshake, and CREATE2 otherwise. Clients SHOULD NOT send the + second format of CREATE cells (the one with the handshake type tag) + to a server directly. - The payload for a CREATED cell, or the relay payload for an - EXTENDED cell, contains: - DH data (g^y) [DH_LEN bytes] - Derivative key data (KH) [HASH_LEN bytes] <see 5.2 below> + Servers always reply to a successful CREATE with a CREATED, and to a + successful CREATE2 with a CREATED2. On failure, a server sends a + DESTROY cell to tear down the circuit. + + [CREATE2 is handled by Tor 0.2.4.7-alpha and later.] + +5.1.1. Choosing circuit IDs in create cells The CircID for a CREATE cell is an arbitrarily chosen nonzero 2-byte integer, selected by the node (OP or OR) that sends the CREATE cell. @@ -692,15 +717,183 @@ see tor-design.pdf. on the ORs' public identity keys: if the sending node has a lower key, it chooses a CircID with an MSB of 0; otherwise, it chooses a CircID with an MSB of 1. + [XXXX fix this when documenting link protocol 4.] (An OP with no public key MAY choose any CircID it wishes, since an OP never needs to process a CREATE cell.) + [XXXX fix this when documenting link protocol 4.] Public keys are compared numerically by modulus. - As usual with DH, x and y MUST be generated randomly. +5.1.2. EXTEND and EXTENDED cells + + To extend an existing circuit, the client sends a EXTEND or EXTENDED2 + relay cell to the last node in the circuit. + + An EXTEND2 cell's relay payload contains: + 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: + [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. + + Nodes MUST ignore unrecognized specifiers, and MUST accept multiple + instances of specifiers other than 'legacy identity'. -5.1.1. CREATE_FAST/CREATED_FAST cells + The relay payload for an EXTEND relay cell consists of: + 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.) Including this hash allows the + extending OR verify that it is indeed connected to the correct target + OR, and prevents certain man-in-the-middle attacks. + + The payload of an EXTENDED cell is the same as the payload of a + CREATED cell. + + The payload of an EXTENDED2 cell is the same as the payload of a + CREATED2 cell. + + [Support for EXTEND2 was added in Tor 0.2.4.8-alpha.] + + Clients SHOULD use the EXTEND format whenever sending a TAP + handshake, and MUST use it whenever the EXTEND cell will be handled + by a node running a version of Tor too old to support EXTEND2. In + other cases, clients SHOULD use EXTEND2. + + When encoding a non-TAP handshake in an EXTEND cell, clients SHOULD + use the format with 'client handshake type tag'. + +5.1.3. The "TAP" handshake + + This handshake uses Diffie-Hellman in Z_p 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+PK_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 + value is hybrid-encrypted (see 0.3) to the server's onion key, giving + a client handshake of: + + PK-encrypted: + Padding [PK_PAD_LEN bytes] + Symmetric key [KEY_LEN bytes] + First part of g^x [PK_ENC_LEN-PK_PAD_LEN-KEY_LEN bytes] + Symmetrically encrypted: + Second part of g^x [DH_LEN-(PK_ENC_LEN-PK_PAD_LEN-KEY_LEN) + bytes] + + The payload for a CREATED cell, or the relay payload for an + EXTENDED cell, contains: + DH data (g^y) [DH_LEN bytes] + Derivative key data (KH) [HASH_LEN bytes] <see 5.2 below> + + 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 + with degenerate keys. Implementations MUST NOT discard other "weak" + 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 + 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. + +5.1.4. The "ntor" handshake + + This handshake uses a set of DH handshakes 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). Here we use the + "curve25519" group and representation as specified in "Curve25519: + new Diffie-Hellman speed records" by D. J. Bernstein. + + [The ntor handshake was added in Tor 0.2.4.8-alpha.] + + In this section, define: + 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" + MULT(a,b) = the multiplication of the curve25519 point 'a' by the + scalar 'b'. + G = The preferred base point for curve25519 ([9]) + KEYGEN() = The curve25519 key generation algorithm, returning + a private/public keypair. + m_expand = PROTOID | ":key_expand" + + 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 + generates a temporary keypair: + x,X = KEYGEN() + and generates a client-side handshake with contents: + NODEID Server identity digest [ID_LENGTH bytes] + KEYID KEYID(B) [H_LENGTH bytes] + CLIENT_PK X [G_LENGTH bytes] + + The server generates a keypair of y,Y = KEYGEN(), and uses its ntor + private key 'b' to compute: + + 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: + SERVER_PK Y [G_LENGTH bytes] + AUTH H(auth_input, t_mac) [H_LENGTH bytes] + + The client then checks Y is in G^* [see NOTE below], and computes + + 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 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.] + + 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. + +5.1.5. CREATE_FAST/CREATED_FAST cells When initializing the first hop of a circuit, the OP has already established the OR's identity and negotiated a secret key using TLS. @@ -717,10 +910,13 @@ see tor-design.pdf. A CREATED_FAST cell contains: Key material (Y) [HASH_LEN bytes] - Derivative key data [HASH_LEN bytes] (See 5.2 below) + Derivative key data [HASH_LEN bytes] (See 5.2.1 below) 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. + If an OR sees a circuit created with CREATE_FAST, the OR is sure to be the first hop of a circuit. ORs SHOULD reject attempts to create streams with RELAY_BEGIN exiting the circuit at the first hop: letting Tor be used as a @@ -728,21 +924,13 @@ see tor-design.pdf. 5.2. Setting circuit keys - 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 - with degenerate keys. Implementations MUST NOT discard other "weak" - g^x values. +5.2.1. KDF-TOR - (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 - the OR. Discarding other keys may allow attacks to learn bits of - the private key.) + This key derivation function is used by the TAP and CREATE_FAST + handshakes, and in the current hidden service protocol. It shouldn't + be used for new functionality. - If CREATE or EXTEND is used to extend a circuit, both parties + If the TAP handshake is used to extend a circuit, both parties base their key material on K0=g^xy, represented as a big-endian unsigned integer. @@ -765,6 +953,28 @@ see tor-design.pdf. is used to encrypt the stream of data going from the OP to the OR, and Kb is used to encrypt the stream of data going from the OR to the OP. +5.2.2. KDF-RFC5869 + + For newer KDF needs, Tor uses the key derivation function HKDF from + RFC5869, instantiated with SHA256. (This is due to a construction + from Krawczyk.) The generated key material is: + + K = K_1 | K_2 | K_3 | ... + + Where H(x,t) is HMAC_SHA256 with value x and key t + and K_1 = H(m_expand | INT8(1) , KEY_SEED ) + and K_(i+1) = H(K_i | m_expand | INT8(i) , KEY_SEED ) + and m_expand is an arbitrarily chosen value, + and INT8(i) is a octet with the value "i". + + In RFC5869's vocabulary, this is HKDF-SHA256 with info == m_expand, + salt == t_key, and IKM == secret_input. + + When used in the ntor handshake, the first HASH_LEN bytes form the + forward digest Df; the next HASH_LEN form the backward digest Db; the + next KEY_LEN form Kf, and the final KEY_LEN form Kb. Excess bytes + from K are discarded. + 5.3. Creating circuits When creating a circuit through the network, the circuit creator @@ -808,7 +1018,7 @@ see tor-design.pdf. all zeroes, or asks to extend back to the relay that sent the extend cell, the circuit will fail and be torn down. The initiating onion router chooses some circID not yet used on the connection between the - two onion routers. (But see section 5.1. above, concerning choosing + two onion routers. (But see section 5.1.1 above, concerning choosing circIDs based on lexicographic order of nicknames.) When an onion router receives a CREATE cell, if it already has a @@ -989,6 +1199,8 @@ see tor-design.pdf. 11 -- RELAY_RESOLVE [forward] 12 -- RELAY_RESOLVED [backward] 13 -- RELAY_BEGIN_DIR [forward] + 14 -- RELAY_EXTEND2 [forward] [control] + 15 -- RELAY_EXTENDED2 [backward] [control] 32..40 -- Used for hidden services; see rend-spec.txt.