CREATE and CREATED cells

Users set up circuits incrementally, one hop at a time. To create a new circuit, clients 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 client sends an EXTEND/EXTEND2 client relay message (see EXTEND and EXTENDED messages 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 obsolete "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:

A CREATED2 cell contains:

Recognized HTYPEs (handshake types) are:

The format of a CREATE cell is one of the following:

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 "EXTEND and EXTENDED messages" below. Recognized HTAG values are:

The format of a CREATED cell is:

(It's equivalent to a CREATED2 cell with length of TAP_S_HANDSHAKE_LEN.)

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 (client or relay) that sends the CREATE/CREATE2 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 relays' 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 messagess

To extend an existing circuit, the client sends an EXTEND or EXTEND2 message, in a RELAY_EARLY cell, to the last node in the circuit.

The body of an EXTEND2 message contains:

Link specifiers describe the next node in the circuit and how to connect to it. Recognized specifiers are:

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 body for an (obsolete) EXTEND relay message consists of:

Clients SHOULD NOT send EXTEND messages; relays SHOULD NOT accept them.

The "legacy identity" and "identity fingerprint" fields are computed as SHA1(DER(KP_relayid_rsa)).

The "Ed25519 identity" field is the Ed25519 identity key (KP_relayid_ed) of the target node. Including this key information allows the relay extending to verify that it is indeed connected to the correct target relay, and prevents certain man-in-the-middle attacks.

The extending relay MUST check all provided identity keys (if they recognize the format), and and MUST NOT extend the circuit if the target relay did not prove its ownership of any such identity key. If only one identity key is provided, but the extending relay knows the other (from directory information), then the relay SHOULD also enforce the key in the directory.

If the extending relay 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 EXTEND2 message; current relay implementations only consider the first of each type.

After checking relay identities, extending relays generate a CREATE/CREATE2 cell from the contents of the EXTEND/EXTEND2 message. See Creating circuits for details.

The body of an (obsolete) EXTENDED message is the same as the body of a CREATED cell.

The body of an EXTENDED2 message is the same as the body 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 message 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 message, clients SHOULD include the target's Ed25519 identity whenever the target has one, and whenever the target supports LinkAuth subprotocol version "3". (See LinkAuth).

When encoding a non-TAP handshake in an EXTEND message, clients SHOULD use the format with 'client handshake type tag'.

The "TAP" handshake

This obsolete 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".)

Clients SHOULD NOT use this handshake. Relays SHOULD NOT accept this handshake, and MAY reply to it with a DESTROY cell.

Define TAP_C_HANDSHAKE_LEN as DH_LEN+KEY_LEN+KP_PAD_LEN. Define TAP_S_HANDSHAKE_LEN as DH_LEN+SHA1_LEN.

The body 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 described below, to the server's onion key (KP_onion_tap), giving a client handshake:

The body for a CREATED cell, or the body for an EXTENDED relay message, contains:

As usual with DH, x and y MUST be generated randomly.

Once the handshake between the client and a relay 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 relay's CREATED cell's g^y with 0 or 1, thus creating a known g^xy and impersonating the relay. 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.

TAP's bad hybrid encryption algorithm

The description of TAP above refer to the "legacy hybrid encryption" of a byte sequence M with a public key KP. It is computed as follows:

      1. If the length of M is no more than KP_ENC_LEN-KP_PAD_LEN,
         pad and encrypt M with KP.
      2. Otherwise, generate a KEY_LEN byte random key K.
         Let M1 = the first KP_ENC_LEN-KP_PAD_LEN-KEY_LEN bytes of M,
         and let M2 = the rest of M.
         Pad and encrypt K|M1 with KP.  Encrypt M2 with our stream cipher,
         using the key K.  Concatenate these encrypted values.

Note that this "hybrid encryption" approach does not prevent an attacker from adding or removing bytes to the end of M. It also allows attackers to modify the bytes not covered by the OAEP -- see Goldberg's PET2006 paper for details. Do not use it as the basis for new protocols! Also note that as used in TAP protocols, case 1 never occurs.

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 NODEID = SHA1(DER(KP_relayid_id)) for the server, and an ntor onion key (a curve25519 public key, KP_onion_ntor) 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:

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:

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 "KDF-RFC5869" and the tag m_expand.

The "ntor-v3" handshake

This handshake extends the ntor handshake to include support for extra data transmitted as part of the handshake. Both the client and the server can transmit extra data; in both cases, the extra data is encrypted, but only server data receives forward secrecy.

To advertise support for this handshake, servers advertise the "Relay=4" subprotocol version. To select it, clients use the 'ntor-v3' HTYPE value in their CREATE2 cells.

In this handshake, we define:

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`).

`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)

EXP(pk,sk), KEYGEN: defined as in curve25519

DIGEST_LEN = MAC_LEN = MAC_KEY_LEN = ENC_KEY_LEN = PUB_KEY_LEN = 32

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)

Other notation is as in the ntor description above.

The client begins by knowing:

B, ID -- The curve25519 onion key (KP_onion_tap)
          and Ed25519 ID (KP_relayid_ed)
          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:

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 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.

Now the relay uses X=CLIENT_PK to compute:

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)

If expected_mac is not MAC, the handshake fails. Otherwise the relay computes CM as:

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:

y,Y = KEYGEN()

and computes the rest of the handshake:

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, ...)

encrypted_msg = ENC(ENC_KEY, SM)

auth_input = verify | ID | B | Y | X | MAC | ENCAP(encrypted_msg) |
    PROTOID | "Server"
AUTH = H_auth(auth_input)

The relay then sends as its CREATED handshake:

Upon receiving this handshake, the client computes:

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 succeeded. The client can then calculate:

RAW_KEYSTREAM = KDF_final(ntor_key_seed)
(ENC_KEY, KEYSTREAM) = PARTITION(RAW_KEYSTREAM, ENC_KEY_LKEN, ...)

SM = DEC(ENC_KEY, MSG)

SM is the message from the relay, and the client uses KEYSTREAM to generate the shared secrets for the newly created circuit.

Now both parties share the same KEYSTREAM, and can use it to generate their circuit keys.

CREATE_FAST/CREATED_FAST cells

When creating a one-hop circuit, the client has already established the relay's identity and negotiated a secret key using TLS. Because of this, it is not necessary for the client to perform the public key operations to create a circuit. In this case, the client MAY send a CREATE_FAST cell instead of a CREATE/CREATE2 cell. The relay responds with a CREATED_FAST cell, and the circuit is created.

A CREATE_FAST cell contains:

A CREATED_FAST cell contains:

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.

Parties SHOULD NOT use CREATE_FAST except for creating one-hop circuits.

Additional data in the circuit extension handshake

Some handshakes (currently ntor-v3 defined above) allow the client or the relay to send additional data as part of the handshake. When used in a CREATE2/CREATED2 handshake, this additional data must have the following format:

(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 occurrence 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 body. 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 (proposal 346).