``` Filename: 332-ntor-v3-with-extra-data.md Title: Ntor protocol with extra data, version 3. Author: Nick Mathewson Created: 12 July 2021 Status: Open ```
# Overview
The ntor handshake is our current protocol for circuit establishment.
So far we have two variants of the ntor handshake in use: the "ntor v1" that we use for everyday circuit extension (see `tor-spec.txt`) and the "hs-ntor" that we use for v3 onion service handshake (see `rend-spec-v3.txt`). This document defines a third version of ntor, adapting the improvements from hs-ntor for use in regular circuit establishment.
These improvements include:
* Support for sending additional encrypted and authenticated protocol-setup handshake data as part of the ntor handshake. (The information sent from the client to the relay does not receive forward secrecy.)
* Support for using an external shared secret that both parties must know in order to complete the handshake. (In the HS handshake, this is the subcredential. We don't use it for circuit extension, but in theory we could.)
* Providing a single specification that can, in the future, be used both for circuit extension _and_ HS introduction.
# The improved protocol: an abstract view
Given a client "C" that wants to construct a circuit to a relay "S":
The client knows: * B: a public "onion key" for S * ID: an identity for S, represented as a fixed-length byte string. * CM: a message that it wants to send to S as part of the handshake. * An optional "verification" string.
The relay knows: * A set of [(b,B)...] "onion key" keypairs. One of them is "current", the others are outdated, but still valid. * ID: Its own identity. * A function for computing a server message SM, based on a given client message. * An optional "verification" string. This must match the "verification" string from the client.
Both parties have a strong source of randomness.
Given this information, the client computes a "client handshake" and sends it to the relay.
The relay then uses its information plus the client handshake to see if the incoming message is valid; if it is, then it computes a "server handshake" to send in reply.
The client processes the server handshake, and either succeeds or fails.
At this point, the client and the relay both have access to: * CM (the message the client sent) * SM (the message the relay sent) * KS (a shared byte stream of arbitrary length, used to compute keys to be used elsewhere in the protocol).
Additionally, the client knows that CM was sent _only_ to the relay whose public onion key is B, and that KS is shared _only_ with that relay.
The relay does not know which client participated in the handshake, but it does know that CM came from the same client that generated the key X, and that SM and KS were shared _only_ with that client.
Both parties know that CM, SM, and KS were shared correctly, or not at all.
Both parties know that they used the same verification string; if they did not, they do not learn what the verification string was. (This feature is required for HS handshakes.)
# The handshake in detail
## Notation
We use the following notation:
* `|` -- concatenation * `"..."` -- a byte string, with no terminating NUL. * `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.
We require the following crypto operations:
* `KDF(s,t)` -- a tweakable key derivation function, returning a keystream of arbitrary length. * `H(s,t)` -- a tweakable hash function of output length `DIGEST_LEN`. * `MAC(k, msg, t)` -- a tweakable message-authentication-code function, of output length `MAC_LEN`. * `EXP(pk,sk)` -- our Diffie Hellman group operation, taking a public key of length `PUB_KEY_LEN`. * `KEYGEN()` -- our Diffie-Hellman keypair generation algorithm, returning a (secret-key,public-key) pair. * `ENC(k, m)` -- a stream cipher with key of length `ENC_KEY_LEN`. `DEC(k, m)` is its inverse.
Parameters:
* `PROTOID` -- a short protocol identifier * `t_*` -- a set of "tweak" strings, used to derive distinct hashes from a single hash function. * `ID_LEN` -- the length of an identity key that uniquely identifies a relay.
Given our cryptographic operations and a set of tweak strings, we define:
``` H_foo(s) = H(s, t_foo) MAC_foo(k, msg) = MAC(k, msg, t_foo) KDF_foo(s) = KDF(s, t_foo) ```
See Appendix A.1 below for a set of instantiations for these operations and constants.
## Client operation, phase 1
The client knows: B, ID -- the onion key and ID of the relay it wants to use. CM -- the message that it wants to send as part of its handshake. VER -- a verification string.
First, the client generates a single-use keypair:
x,X = KEYGEN()
and computes:
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)
and sends:
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 [last MAC_LEN bytes of message]
The client remembers x, X, B, ID, Bx, and msg_mac.
## Server operation
The relay 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:
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 uses KEYSTREAM to generate the shared secrets for the newly created circuit.
## Client operation, phase 2
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.
# Security notes
Whenever comparing bytestrings, implementations SHOULD use constant-time comparison function to avoid side-channel attacks.
To avoid small-subgroup attacks against the Diffie-Hellman function, implementations SHOULD either:
* Make sure that all incoming group members are in fact in the DH group. * Validate all outputs from the EXP function to make sure that they are not degenerate.
# Notes on usage
We don't specify what should actually be done with the resulting keystreams; that depends on the usage for which this handshake is employed. Typically, they'll be divided up into a series of tags and symmetric keys.
The keystreams generated here are (conceptually) unlimited. In practice, the usage will determine the amount of key material actually needed: that's the amount that clients and relays will actually generate.
The PROTOID parameter should be changed not only if the cryptographic operations change here, but also if the usage changes at all, or if the meaning of any parameters changes. (For example, if the encoding of CM and SM changed, or if ID were a different length or represented a different type of key, then we should start using a new PROTOID.)
# A.1 Instantiation
Here are a set of functions based on SHA3, SHAKE128, Curve25519, and AES256:
``` H(s, t) = SHA3_256(ENCAP(t) | s) MAC(k, msg, t) = SHA3_256(ENCAP(t) | ENCAP(k) | s) KDF(s, t) = SHAKE_128(ENCAP(t) | s) ENC(k, m) = AES_256_CTR(k, m)
EXP(pk,sk), KEYGEN: defined as in curve25519
DIGEST_LEN = MAC_LEN = ENC_KEY_LEN = PUB_KEY_LEN = 32
ID_LEN = 32 (representing an ed25519 identity key) ```
Notes on selected operations: SHA3 can be pretty slow, and AES256 is likely overkill. I'm choosing them anyway because they are what we use in hs-ntor, and in my preliminary experiments they don't account for even 1% of the time spent on this handshake.
``` 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" ```
# A.2 Encoding for use with Tor circuit extension
Here we give a concrete instantiation of ntor-v3 for use with circuit extension in Tor, and the parameters in A.1 above.
If in use, this is a new CREATE2 type. Clients should not use it unless the relay advertises support by including an appropriate version of the `Relay=X` subprotocol in its protocols list.
When the encoding and methods of this section, along with the instantiations from the previous section, are in use, we specify:
PROTOID = "ntor3-curve25519-sha3_256-1"
The key material is extracted as follows, unless modified by the handshake (see below). See tor-spec.txt for more info on the specific values:
Df Digest authentication, forwards [20 bytes] Db Digest authentication, backwards [20 bytes] Kf Encryption key, forwards [16 bytes] Kb Encryption key, backwards [16 bytes] KH Onion service nonce [20 bytes]
We use the following meta-encoding for the contents of client and server messages.
[Any number of times]: TYPE [one byte] LEN [one byte] BODY [LEN bytes]
We do not specify specific TYPE semantics here; we leave those for other proposals.
All parties MUST reject messages that are not well-formed per the rules above.
To avoid partitioning, clients MUST reject messages with TYPEs that they do not recognize. (Therefore, whenever we specify a new server message TYPE, we must say that it can only be included if the client signals that it understands it.)
# A.3 How much space is available?
We start with a 498-byte payload in each relay cell.
The header of the EXTEND2 cell, including link specifiers and other headers, comes to 89 bytes.
The client handshake requires 128 bytes (excluding CM).
That leaves 281 bytes, "which should be plenty".
# X.1 Negotiating proposal-324 circuit windows
(We should move this section into prop324 when this proposal is finished.)
We define a type value, CIRCWINDOW_INC.
We define a triplet of consensus parameters: `circwindow_inc_min`, `cincwindow_inc_max`, and `circwindow_inc_dflt`. These all have range (1,65535).
When the authority operators want to experiment with different values for `circwindow_inc_dflt`, they set `circwindow_inc_min` and `circwindow_inc_max` to the range in which they want to experiment, making sure that the existing `circwindow_inc_dflt` is within that range.
vWhen a client sees that a relay supports the ntor3 handshake type (subprotocol `Relay=X`), and also supports the flow control algorithms of proposal 324 (subprotocol `FlowCtrl=X`), then the client sends a message, with type `CIRCWINDOW_INC`, containing a two-byte integer equal to `circwindow_inc_dflt`.
The relay rejects the message if the value given is outside of the [`circwindow_inc_min`, `circwindow_inc_max`] range. Otherwise, it accepts it, and replies with the same message that the client sent.