CREATE and CREATED cells
Users set up circuits incrementally, one hop at a time. To create a new circuit, OPs send a CREATE/CREATE2 cell to the first node, with the first half of an authenticated handshake; that node responds with a CREATED/CREATED2 cell with the second half of the handshake. To extend a circuit past the first hop, the OP sends an EXTEND/EXTEND2 relay cell (see section 5.1.2) which instructs the last node in the circuit to send a CREATE/CREATE2 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 HTYPEs (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 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 TAP_S_HANDSHAKE_LEN.)
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 second format of CREATE cells (the one with the handshake type tag) to a server directly.
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.]
Choosing circuit IDs in create cells
The CircID for a CREATE/CREATE2 cell is a nonzero integer, selected by the node (OP or OR) that sends the CREATE/CREATED2 cell. Depending on the link protocol version, there are certain rules for choosing the value of CircID which MUST be obeyed, as implementations MAY decide to refuse in case of a violation. In link protocol 3 or lower, CircIDs are 2 bytes long; in protocol 4 or higher, CircIDs are 4 bytes long.
In link protocol version 3 or lower, the nodes choose from only one half of the possible values based on the ORs' public identity keys, in order to avoid collisions. 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. (Public keys are compared numerically by modulus.) A client with no public key MAY choose any CircID it wishes, since clients never need to process CREATE/CREATE2 cells.
In link protocol version 4 or higher, whichever node initiated the connection MUST set its MSB to 1, and whichever node didn't initiate the connection MUST set its MSB to 0.
The CircID value 0 is specifically reserved for cells that do not belong to any circuit: CircID 0 MUST not be used for circuits. No other CircID value, including 0x8000 or 0x80000000, is reserved.
Existing Tor implementations choose their CircID values at random from among the available unused values. To avoid distinguishability, new implementations should do the same. Implementations MAY give up and stop attempting to build new circuits on a channel, if a certain number of randomly chosen CircID values are all in use (today's Tor stops after 64).
EXTEND and EXTENDED cells
To extend an existing circuit, the client sends an EXTEND or EXTEND2 RELAY_EARLY 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.
[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 'Ed25519 identity'. (Nodes SHOULD reject link specifier lists that include multiple instances of either one of those specifiers.)
For purposes of indistinguishability, implementations SHOULD send these link specifiers, if using them, in this order: [00], [02], [03], [01].
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.) 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 man-in-the-middle attacks.
Extending ORs MUST check all provided identity keys (if they recognize the format), and and MUST NOT extend the circuit if the target OR did not prove its ownership of any such identity key. If only one identity key is provided, but the extending OR knows the other (from directory information), then the OR SHOULD also enforce the key in the directory.
If an extending OR has a channel with a given Ed25519 ID and RSA identity, and receives a request for that Ed25519 ID and a different RSA identity, it SHOULD NOT attempt to make another connection: it should just fail and DESTROY the circuit.
The client MAY include multiple IPv4 or IPv6 link specifiers in an EXTEND cell; current OR implementations only consider the first of each type.
After checking relay identities, extending ORs generate a CREATE/CREATE2 cell from the contents of the EXTEND/EXTEND2 cell. See section 5.3 for details.
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/EXTENDED2 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 generating an EXTEND2 cell, clients SHOULD include the target's Ed25519 identity whenever the target has one, and whenever the target supports LinkAuth subprotocol version "3". (See section 9.2.)
When encoding a non-TAP handshake in an EXTEND cell, clients SHOULD use the format with 'client handshake type tag'.
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+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 value is encrypted using the "legacy hybrid encryption" algorithm (see 0.4 above) to the server's onion key, giving a client handshake:
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:
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.
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"
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 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_KP 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_KP 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.
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. Because of this, it is not always necessary for the OP to perform the public key operations to create a circuit. In this case, the OP MAY send a CREATE_FAST cell instead of a CREATE cell for the first hop only. The OR responds with a CREATED_FAST cell, and the circuit is created.
A CREATE_FAST cell contains:
Key material (X) [HASH_LEN bytes]
A CREATED_FAST cell contains:
Key material (Y) [HASH_LEN bytes]
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.
The CREATE_FAST handshake is currently deprecated whenever it is not necessary; the migration is controlled by the "usecreatefast" networkstatus parameter as described in dir-spec.txt.
[Tor 0.3.1.1-alpha and later disable CREATE_FAST by default.]