``` 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.
On Mon, Jul 12, 2021 at 12:01:47PM -0400, Nick Mathewson wrote:
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.)
I'm not sure the protocol you specify has this feature as written. For example, if the verification string has low entropy, the server could brute-force the client's verification string (using the MAC to check its guess). This is unlike, say, OTR's SMP or a PAKE, in which each online execution of the protocol allows the server just one guess.
But perhaps you don't actually need the property in as strong a form as you wrote it, since the HS handshake application has high-entropy secrets?
On Mon, Jul 12, 2021 at 3:04 PM Ian Goldberg iang@uwaterloo.ca wrote:
On Mon, Jul 12, 2021 at 12:01:47PM -0400, Nick Mathewson wrote:
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.)
I'm not sure the protocol you specify has this feature as written. For example, if the verification string has low entropy, the server could brute-force the client's verification string (using the MAC to check its guess). This is unlike, say, OTR's SMP or a PAKE, in which each online execution of the protocol allows the server just one guess.
But perhaps you don't actually need the property in as strong a form as you wrote it, since the HS handshake application has high-entropy secrets?
Oh yes, you are right, of course.
Can you suggest a way to phrase this property that encompasses what the protocol actually does provide?
best wishes,
On Mon, Jul 12, 2021 at 03:09:02PM -0400, Nick Mathewson wrote:
On Mon, Jul 12, 2021 at 3:04 PM Ian Goldberg iang@uwaterloo.ca wrote:
On Mon, Jul 12, 2021 at 12:01:47PM -0400, Nick Mathewson wrote:
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.)
I'm not sure the protocol you specify has this feature as written. For example, if the verification string has low entropy, the server could brute-force the client's verification string (using the MAC to check its guess). This is unlike, say, OTR's SMP or a PAKE, in which each online execution of the protocol allows the server just one guess.
But perhaps you don't actually need the property in as strong a form as you wrote it, since the HS handshake application has high-entropy secrets?
Oh yes, you are right, of course.
Can you suggest a way to phrase this property that encompasses what the protocol actually does provide?
Could I convince you to use a hash (domain-separated but not keyed) of VER instead of ENCAP(VER)? Then you could say that the protocol reveals no more about VER than H_verstr(VER) does. [Note: H_verstr is different from H_verify.]
Hi Nick, you might look at the Noise framework:
http://noiseprotocol.org/noise.html
Noise has a naming scheme for "handshake patterns". Ntor matches what we call NK1. Your new scheme I think matches NK (the 1 in NK1 indicates a "deferred" pattern where the DH operation that authenticates the server is performed prior to the 2nd message rather than the first).
NK1: <- s ... -> e <- e, ee, es
(read as: initiator has pre-knowledge of server's static public key s; initiator sends their ephemeral in first message; responder sends their ephemeral in second message, then performs the two 2 DH operations, hashing them together and using the result for encrypting future data).
In NK, the ephemeral-static DH is performed earlier so that the first message's handshake payload can be encrypted:
NK: <- s ... -> e, es <- e, ee
You also wanted to add an (optional) pre-shared key, which Noise supports:
NKpsk0: <- s ... -> psk, e, es <- e, ee
Some advantages of Noise are that you could reuse existing libraries and Noise's growing body of security analysis.
Also, we're working on KEM extensions for post-quantum, signatures, and other things, so Noise might make it easier to evolve the protocol (eg NK1 vs NK vs NKpsk0).
Trevor
On Mon, Jul 12, 2021 at 9:02 AM Nick Mathewson nickm@torproject.org wrote:
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. _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
On Tue, Jul 13, 2021 at 11:34:47AM -0700, Trevor Perrin wrote:
You also wanted to add an (optional) pre-shared key, which Noise supports:
NKpsk0: <- s ... -> psk, e, es <- e, ee
Out of curiosity, Trevor, what properties does this Noise protocol provide for low-entropy psk?
Nick, what are the settings in Tor (if any) in which low-entropy psk will come up?
But this post from Trevor also made me realize a bigger issue with the protocol Nick proposed:
If you want the protocol to work with Walking Onions, it needs to be *post-specified peer*. That is, contrary to:
The client knows:
- B: a public "onion key" for S
The client will in fact _not_ know B in advance in a Walking Onions setting, but rather will learn it at the end of the handshake. The protocol Nick specified does in fact use B in the first message, unlike the current ntor handshake, which just sends KEYID(B) in the first flow, but it's not part of the math, or indeed as far as I can see, used for anything at all in Section 5.1.4 of tor-spec.txt, and so can be easily removed (and replaced with B being sent by the server) for Walking Onions.
On Fri, Jul 16, 2021 at 5:31 AM Ian Goldberg iang@uwaterloo.ca wrote:
On Tue, Jul 13, 2021 at 11:34:47AM -0700, Trevor Perrin wrote:
You also wanted to add an (optional) pre-shared key, which Noise supports:
NKpsk0: <- s ... -> psk, e, es <- e, ee
Out of curiosity, Trevor, what properties does this Noise protocol provide for low-entropy psk?
The Noise PSK is intended for 256-bit secrets, however:
* A low-entropy (even malicious) PSK can't reduce the security of the rest of the handshake. I.e. NKpsk0 with a bad PSK has all the security properties of NK.
* The handshake will only complete successfully if both parties use the same PSK.
This is *NOT* a PAKE: the legitimate recipient of the first NKpsk0 handshake message will be able to try offline guesses for the PSK.
Noise doesn't have a PAKE feature. You could generically combine a Noise handshake with an Oblivious PRF to produce a PAKE (like Hugo's OPAQUE). Integrating a "balanced" PAKE, like in OTR, would be more complicated.
If you want the protocol to work with Walking Onions, it needs to be *post-specified peer*. That is, contrary to:
The client knows:
- B: a public "onion key" for S
The client will in fact _not_ know B in advance in a Walking Onions setting, but rather will learn it at the end of the handshake.
I don't know the requirements here, but fwiw here's what pre-specified peer (NK or NK1) vs post-specified peer (NX) looks like for a Noise handshake:
NK: <- s ... -> e, es <- e, ee
NX: -> e <- e, ee, s, es
Trevor
On Fri, Jul 16, 2021 at 8:31 AM Ian Goldberg iang@uwaterloo.ca wrote: [...]
But this post from Trevor also made me realize a bigger issue with the protocol Nick proposed:
If you want the protocol to work with Walking Onions, it needs to be *post-specified peer*. That is, contrary to:
The client knows:
- B: a public "onion key" for S
The client will in fact _not_ know B in advance in a Walking Onions setting, but rather will learn it at the end of the handshake. The protocol Nick specified does in fact use B in the first message, unlike the current ntor handshake, which just sends KEYID(B) in the first flow, but it's not part of the math, or indeed as far as I can see, used for anything at all in Section 5.1.4 of tor-spec.txt, and so can be easily removed (and replaced with B being sent by the server) for Walking Onions.
Well, in the current deployment, the client only knows one B for each server at a time, and if the server responds with a B that the client _doesn't_ recognize, the client won't have any idea whether or not B is really authentic. (Priving that B is authentic is a big part of what Walking Onions has to solve.)
Walking Onions is a big enough set of protocol changes that I'm comfortable requiring a subsequent handshake bump when we get there. Who knows, we may want another one between now and then if we decide to go hybrid-PQ or use Noise or something :)
cheers,
-
Ian Goldberg -
Nick Mathewson -
Nick Mathewson -
Trevor Perrin