Add proposal 332: Ntor protocol with extra data, version 3

4 files changed, 400 insertions, 0 deletions

diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index 49261e3..adfe0ba 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -252,6 +252,7 @@ Proposals by number:
 329  Overcoming Tor's Bottlenecks with Traffic Splitting [DRAFT]
 330  Modernizing authority contact entries [OPEN]
 331  Res tokens: Anonymous Credentials for Onion Service DoS Resilience [DRAFT]
+332  Ntor protocol with extra data, version 3 [OPEN]
 
 
 Proposals by status:
@@ -294,6 +295,7 @@ Proposals by status:
    325  Packed relay cells: saving space on small commands
    326  The "tor-relay" Well-Known Resource Identifier
    330  Modernizing authority contact entries
+   332  Ntor protocol with extra data, version 3
  ACCEPTED:
    265  Load Balancing with Overhead Parameters [for 0.2.9.x]
    275  Stop including meaningful "published" time in microdescriptor consensus [for 0.3.1.x-alpha]
diff --git a/proposals/332-ntor-v3-with-extra-data.md b/proposals/332-ntor-v3-with-extra-data.md
new file mode 100644
index 0000000..06c55f9
--- /dev/null
+++ b/proposals/332-ntor-v3-with-extra-data.md
@@ -0,0 +1,396 @@
+```
+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.
+
+
+
+
diff --git a/proposals/BY_INDEX.md b/proposals/BY_INDEX.md
index 8000a83..2279bd2 100644
--- a/proposals/BY_INDEX.md
+++ b/proposals/BY_INDEX.md
@@ -249,4 +249,5 @@ Below are a list of proposals sorted by their proposal number.  See
 * [`329-traffic-splitting.txt`](/proposals/329-traffic-splitting.txt): Overcoming Tor's Bottlenecks with Traffic Splitting [DRAFT]
 * [`330-authority-contact.md`](/proposals/330-authority-contact.md): Modernizing authority contact entries [OPEN]
 * [`331-res-tokens-for-anti-dos.md`](/proposals/331-res-tokens-for-anti-dos.md): Res tokens: Anonymous Credentials for Onion Service DoS Resilience [DRAFT]
+* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 [OPEN]
 
diff --git a/proposals/README.md b/proposals/README.md
index 1a83435..ba73953 100644
--- a/proposals/README.md
+++ b/proposals/README.md
@@ -40,6 +40,7 @@ for discussion.
 * [`325-packed-relay-cells.md`](/proposals/325-packed-relay-cells.md): Packed relay cells: saving space on small commands
 * [`326-tor-relay-well-known-uri-rfc8615.md`](/proposals/326-tor-relay-well-known-uri-rfc8615.md): The "tor-relay" Well-Known Resource Identifier
 * [`330-authority-contact.md`](/proposals/330-authority-contact.md): Modernizing authority contact entries
+* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3
 
 
 ## ACCEPTED proposals: slated for implementation