commit aac1ee24e8b5f7c764cd8d7d7851733c94d94905 Author: Nick Mathewson nickm@torproject.org Date: Mon Jul 12 11:47:48 2021 -0400
Add proposal 332: Ntor protocol with extra data, version 3 --- proposals/000-index.txt | 2 + proposals/332-ntor-v3-with-extra-data.md | 396 +++++++++++++++++++++++++++++++ proposals/BY_INDEX.md | 1 + proposals/README.md | 1 + 4 files changed, 400 insertions(+)
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