Merge branch 'ntorv3-merge' into 'main'

Merge proposal 332 (ntor-v3) into torspec.

See merge request tpo/core/torspec!163

5 files changed, 204 insertions, 7 deletions

diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index ff6bf8b..968d7cf 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -252,7 +252,7 @@ Proposals by number:
 329  Overcoming Tor's Bottlenecks with Traffic Splitting [FINISHED]
 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 [FINISHED]
+332  Ntor protocol with extra data, version 3 [CLOSED]
 333  Vanguards lite [FINISHED]
 334  A Directory Authority Flag To Mark Relays As Middle-only [SUPERSEDED]
 335  An authority-only design for MiddleOnly [CLOSED]
@@ -324,7 +324,6 @@ Proposals by status:
    324  RTT-based Congestion Control for Tor
    327  A First Take at PoW Over Introduction Circuits
    329  Overcoming Tor's Bottlenecks with Traffic Splitting
-   332  Ntor protocol with extra data, version 3
    333  Vanguards lite [in 0.4.7.1-alpha]
  CLOSED:
    101  Voting on the Tor Directory System [in 0.2.0.x]
@@ -428,6 +427,7 @@ Proposals by status:
    315  Updating the list of fields required in directory documents [in 0.4.5.1-alpha]
    318  Limit protover values to 0-63 [in 0.4.5.1-alpha]
    328  Make Relays Report When They Are Overloaded
+   332  Ntor protocol with extra data, version 3
    335  An authority-only design for MiddleOnly [in 0.4.7.2-alpha]
    336  Randomized schedule for guard retries
    337  A simpler way to decide, "Is this guard usable?"
diff --git a/proposals/332-ntor-v3-with-extra-data.md b/proposals/332-ntor-v3-with-extra-data.md
index b76a451..58a3bf3 100644
--- a/proposals/332-ntor-v3-with-extra-data.md
+++ b/proposals/332-ntor-v3-with-extra-data.md
@@ -3,7 +3,7 @@ Filename: 332-ntor-v3-with-extra-data.md
 Title: Ntor protocol with extra data, version 3.
 Author: Nick Mathewson
 Created: 12 July 2021
-Status: Finished
+Status: Closed
 ```
 
 # Overview
diff --git a/proposals/BY_INDEX.md b/proposals/BY_INDEX.md
index c0ab2d8..73a2775 100644
--- a/proposals/BY_INDEX.md
+++ b/proposals/BY_INDEX.md
@@ -249,7 +249,7 @@ 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 [FINISHED]
 * [`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 [FINISHED]
+* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3 [CLOSED]
 * [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite [FINISHED]
 * [`334-middle-only-flag.txt`](/proposals/334-middle-only-flag.txt): A Directory Authority Flag To Mark Relays As Middle-only [SUPERSEDED]
 * [`335-middle-only-redux.md`](/proposals/335-middle-only-redux.md): An authority-only design for MiddleOnly [CLOSED]
diff --git a/proposals/README.md b/proposals/README.md
index 4503667..910c63b 100644
--- a/proposals/README.md
+++ b/proposals/README.md
@@ -68,7 +68,6 @@ themselves still need to be merged into the specifications proper.
 * [`324-rtt-congestion-control.txt`](/proposals/324-rtt-congestion-control.txt): RTT-based Congestion Control for Tor
 * [`327-pow-over-intro.txt`](/proposals/327-pow-over-intro.txt): A First Take at PoW Over Introduction Circuits
 * [`329-traffic-splitting.txt`](/proposals/329-traffic-splitting.txt): Overcoming Tor's Bottlenecks with Traffic Splitting
-* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3
 * [`333-vanguards-lite.md`](/proposals/333-vanguards-lite.md): Vanguards lite
 
 
@@ -239,6 +238,7 @@ necessary.
 * [`315-update-dir-required-fields.txt`](/proposals/315-update-dir-required-fields.txt): Updating the list of fields required in directory documents
 * [`318-limit-protovers.md`](/proposals/318-limit-protovers.md): Limit protover values to 0-63
 * [`328-relay-overload-report.md`](/proposals/328-relay-overload-report.md): Make Relays Report When They Are Overloaded
+* [`332-ntor-v3-with-extra-data.md`](/proposals/332-ntor-v3-with-extra-data.md): Ntor protocol with extra data, version 3
 * [`335-middle-only-redux.md`](/proposals/335-middle-only-redux.md): An authority-only design for MiddleOnly
 * [`336-randomize-guard-retries.md`](/proposals/336-randomize-guard-retries.md): Randomized schedule for guard retries
 * [`337-simpler-guard-usability.md`](/proposals/337-simpler-guard-usability.md): A simpler way to decide, "Is this guard usable?"
diff --git a/tor-spec.txt b/tor-spec.txt
index 669851f..4d21c9a 100644
--- a/tor-spec.txt
+++ b/tor-spec.txt
@@ -31,7 +31,9 @@ Table of Contents
             5.1.2. EXTEND and EXTENDED cells
             5.1.3. The "TAP" handshake
             5.1.4. The "ntor" handshake
+            5.1.4.1. The "ntor-v3" handshake.
             5.1.5. CREATE_FAST/CREATED_FAST cells
+            5.1.6. Additional data in CREATE/CREATED cells
         5.2. Setting circuit keys
             5.2.1. KDF-TOR
             5.2.2. KDF-RFC5869
@@ -1030,7 +1032,7 @@ see tor-design.pdf.
        0x0000  TAP  -- the original Tor handshake; see 5.1.3
        0x0001  reserved
        0x0002  ntor -- the ntor+curve25519+sha256 handshake; see 5.1.4
-
+       0x0003  ntor-v3 -- ntor extended with extra data; see 5.1.4.1
 
    The format of a CREATE cell is one of the following:
 
@@ -1311,6 +1313,152 @@ see tor-design.pdf.
    into the keys needed for the Tor relay protocol, using the KDF
    described in 5.2.2 and the tag m_expand.
 
+5.1.4.1. 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 in 5.1.4 above.
+
+   The client begins by knowing:
+
+     B, ID -- The curve25519 onion key and Ed25519 ID 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:
+
+     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          [MAC_LEN bytes]
+
+   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:
+
+       Y          Y              [PUB_KEY_LEN bytes]
+       AUTH       AUTH           [DIGEST_LEN bytes]
+       MSG        encrypted_msg  [len(SM) bytes, up to end of the message]
+
+   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.
+
 5.1.5. CREATE_FAST/CREATED_FAST cells
 
    When initializing the first hop of a circuit, the OP has already
@@ -1341,6 +1489,55 @@ see tor-design.pdf.
 
    [Tor 0.3.1.1-alpha and later disable CREATE_FAST by default.]
 
+5.1.6. Additional data in CREATE/CREATED cells
+
+   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
+   CREATE/CREATED handshake, this additional data must have the following
+   format:
+
+        N_EXTENSIONS           [one byte]
+        N_EXTENSIONS times:
+            EXT_FIELD_TYPE     [one byte]
+            EXT_FIELD_LEN      [one byte]
+            EXT_FIELD          [EXT_FIELD_LEN bytes]
+
+    (`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 occurrences all occurrences 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 payload.  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]
+
 5.2. Setting circuit keys
 
 5.2.1. KDF-TOR
@@ -2421,7 +2618,7 @@ see tor-design.pdf.
 
    "4" -- support the ntorv3 (version 3) key exchange and all features in
           0.4.7.3-alpha. This adds a new CREATE2 cell type. See proposal 332
-          for more details.
+          and section 5.1.4.1 above for more details.
 
 9.4. "HSIntro"