Setting circuit keys

As a final step in creating or extending a circuit, both parties derive a shared set of circuit keys used to encrypt, decrypt, and authenticate relay cells sent over that circuit.

To do this, the parties first use a key expansion algorithm to derive a long (possibly unlimited) keystream from the output of the generator, and then partition the output of that keystream into the necessary circuit keys.

The exact key extension algorithm used, and the format of the partitioned keys, depends on which circuit extension handshake is in use.

KDF-TOR

This key derivation function is used by the TAP and CREATE_FAST handshakes. It shouldn't be used for new functionality.

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.

If CREATE_FAST is used, both parties base their key material on K0=X|Y.

From the base key material K0, they compute a stream of derivative key data as

K = SHA1(K0 | \[00\]) | SHA1(K0 | \[01\]) | SHA1(K0 | \[02\]) | ...

Note that because of the one-byte counter used in each SHA1 input, this KDF MUST NOT be used to generate more than SHA1_LEN * 256 = 5120 bytes of output. We never approach this amount in practice.

When partitioning this keystream for the current relay cell encryption protocol, the first SHA1_LEN bytes of K form KH; the next SHA1_LEN form the forward digest Df; the next SHA1_LEN form the backward digest Db; the next KEY_LEN 61-76 form Kf, and the final KEY_LEN form Kb. Excess bytes from K are discarded.

KH is used in the handshake response to demonstrate knowledge of the computed shared key. Df is used to seed the integrity-checking hash for the stream of data going from the client to the relay, and Db seeds the integrity-checking hash for the data stream from the relay to the client. Kf is used to encrypt the stream of data going from the client to the relay, and Kb is used to encrypt the stream of data going from the relay to the client.

KDF-RFC5869

For newer KDF needs, including ntor and hs-ntor. 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+1) , 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 (a constant), and IKM == secret_input (the output of the ntor handshake). m_expand and t_key are constant parameters, whose values are stated whenever the use of KDF-RFC5869 is specified.

When partitioning this keystream for the current relay cell encryption protocol from the ntor handshake, the first SHA1_LEN bytes form the forward digest Df; the next SHA1_LEN form the backward digest Db; the next KEY_LEN form Kf, the next KEY_LEN form Kb, and the final SHA1_LEN bytes are taken as a nonce to use in the place of KH in the hidden service protocol. Excess bytes from K are discarded.