[tor-dev] Proposal 332: Ntor protocol with extra data, version 3.

[Nick Mathewson]

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