The introduction protocol

The introduction protocol proceeds in three steps.

First, a hidden service host builds an anonymous circuit to a Tor node and registers that circuit as an introduction point.

Single Onion Services attempt to build a non-anonymous single-hop circuit, but use an anonymous 3-hop circuit if:

     * the intro point is on an address that is configured as unreachable via
       a direct connection, or
     * the initial attempt to connect to the intro point over a single-hop
       circuit fails, and they are retrying the intro point connection.

        [After 'First' and before 'Second', the hidden service publishes its
        introduction points and associated keys, and the client fetches
        them as described in section [HSDIR] above.]

Second, a client builds an anonymous circuit to the introduction point, and sends an introduction request.

Third, the introduction point relays the introduction request along the introduction circuit to the hidden service host, and acknowledges the introduction request to the client.

Registering an introduction point

Extensible ESTABLISH_INTRO protocol

When a hidden service is establishing a new introduction point, it sends an ESTABLISH_INTRO message with the following contents:

     AUTH_KEY_TYPE    [1 byte]
     AUTH_KEY_LEN     [2 bytes]
     AUTH_KEY         [AUTH_KEY_LEN bytes]
     N_EXTENSIONS     [1 byte]
     N_EXTENSIONS times:
        EXT_FIELD_TYPE [1 byte]
        EXT_FIELD_LEN  [1 byte]
        EXT_FIELD      [EXT_FIELD_LEN bytes]
     HANDSHAKE_AUTH   [MAC_LEN bytes]
     SIG_LEN          [2 bytes]
     SIG              [SIG_LEN bytes]

The AUTH_KEY_TYPE field indicates the type of the introduction point authentication key and the type of the MAC to use in HANDSHAKE_AUTH. Recognized types are:

       [00, 01] -- Reserved for legacy introduction messages; see
                   [LEGACY_EST_INTRO below]
       [02] -- Ed25519; SHA3-256.

The AUTH_KEY_LEN field determines the length of the AUTH_KEY field. The AUTH_KEY field contains the public introduction point authentication key, KP_hs_ipt_sid.

The EXT_FIELD_TYPE, EXT_FIELD_LEN, EXT_FIELD entries are reserved for extensions to the introduction protocol. Extensions with unrecognized EXT_FIELD_TYPE values must be ignored. (EXT_FIELD_LEN may be zero, in which case EXT_FIELD is absent.)

   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 descriptions of individual extensions.)

The following extensions are currently defined:

The HANDSHAKE_AUTH field contains the MAC of all earlier fields in the message using as its key the shared per-circuit material ("KH") generated during the circuit extension protocol; see tor-spec.txt section 5.2, "Setting circuit keys". It prevents replays of ESTABLISH_INTRO messages.

SIG_LEN is the length of the signature.

SIG is a signature, using AUTH_KEY, of all contents of the message, up to but not including SIG_LEN and SIG. These contents are prefixed with the string "Tor establish-intro cell v1".

(Note that this string is sic; it predates our efforts to distinguish cells from relay messages.)

Upon receiving an ESTABLISH_INTRO message, a Tor node first decodes the key and the signature, and checks the signature. The node must reject the ESTABLISH_INTRO message and destroy the circuit in these cases:

        * If the key type is unrecognized
        * If the key is ill-formatted
        * If the signature is incorrect
        * If the HANDSHAKE_AUTH value is incorrect

        * If the circuit is already a rendezvous circuit.
        * If the circuit is already an introduction circuit.
          [TODO: some scalability designs fail there.]
        * If the key is already in use by another circuit.

Otherwise, the node must associate the key with the circuit, for use later in INTRODUCE1 messages.

Denial-of-Service defense extension (DOS_PARAMS)

The DOS_PARAMS extension in ESTABLISH_INTRO is used to send Denial-of-Service (DoS) parameters to the introduction point in order for it to apply them for the introduction circuit.

This is for the rate limiting DoS mitigation specifically.

The EXT_FIELD_TYPE value for the DOS_PARAMS extension is [01].

The content is defined as follows:

Recognized values for PARAM_TYPE in this extension are:

Together, these parameters configure a token bucket that determines how many INTRODUCE2 messages the introduction point may send to the service.

Technically speaking, the BURST parameter is misnamed in that it is not actually "per second": only a rate has an associated time.

If either of these parameters is set to 0, the defense is disabled, and the introduction point should ignore the other parameter.

If the burst is lower than the rate, the introduction point SHOULD ignore the extension.

Using this extension extends the body of the ESTABLISH_INTRO message by 19 bytes bringing it from 134 bytes to 155 bytes.

When this extension is not sent, introduction points use default settings taken from taken from the consensus parameters HiddenServiceEnableIntroDoSDefense, HiddenServiceEnableIntroDoSRatePerSec, and HiddenServiceEnableIntroDoSBurstPerSec.

This extension can only be used with relays supporting the protocol version "HSIntro=5".

Introduced in tor-0.4.2.1-alpha.

Registering an introduction point on a legacy Tor node

This section is obsolete and refers to a workaround for now-obsolete Tor relay versions. It is included for historical reasons.

Tor nodes should also support an older version of the ESTABLISH_INTRO message, first documented in rend-spec.txt. New hidden service hosts must use this format when establishing introduction points at older Tor nodes that do not support the format above in [EST_INTRO].

In this older protocol, an ESTABLISH_INTRO message contains:

        KEY_LEN        [2 bytes]
        KEY            [KEY_LEN bytes]
        HANDSHAKE_AUTH [20 bytes]
        SIG            [variable, up to end of relay message body]

   The KEY_LEN variable determines the length of the KEY field.

The KEY field is the ASN1-encoded legacy RSA public key that was also included in the hidden service descriptor.

The HANDSHAKE_AUTH field contains the SHA1 digest of (KH | "INTRODUCE").

The SIG field contains an RSA signature, using PKCS1 padding, of all earlier fields.

Older versions of Tor always use a 1024-bit RSA key for these introduction authentication keys.

Acknowledging establishment of introduction point

After setting up an introduction circuit, the introduction point reports its status back to the hidden service host with an INTRO_ESTABLISHED message.

The INTRO_ESTABLISHED message has the following contents:

     N_EXTENSIONS [1 byte]
     N_EXTENSIONS times:
       EXT_FIELD_TYPE [1 byte]
       EXT_FIELD_LEN  [1 byte]
       EXT_FIELD      [EXT_FIELD_LEN bytes]

Older versions of Tor send back an empty INTRO_ESTABLISHED message instead. Services must accept an empty INTRO_ESTABLISHED message from a legacy relay. [The above paragraph is obsolete and refers to a workaround for now-obsolete Tor relay versions. It is included for historical reasons.]

The same rules for multiplicity, ordering, and handling unknown types apply to the extension fields here as described [EST_INTRO] above.

Sending an INTRODUCE1 message to the introduction point

In order to participate in the introduction protocol, a client must know the following:

     * An introduction point for a service.
     * The introduction authentication key for that introduction point.
     * The introduction encryption key for that introduction point.

The client sends an INTRODUCE1 message to the introduction point, containing an identifier for the service, an identifier for the encryption key that the client intends to use, and an opaque blob to be relayed to the hidden service host.

In reply, the introduction point sends an INTRODUCE_ACK message back to the client, either informing it that its request has been delivered, or that its request will not succeed.

If the INTRODUCE_ACK message indicates success, the client SHOULD close the circuit to the introduction point, and not use it for anything else. If the INTRODUCE_ACK message indicates failure, the client MAY try a different introduction point. It MAY reach the different introduction point either by extending its introduction circuit an additional hop, or by building a new introduction circuit.

   [TODO: specify what tor should do when receiving a malformed message. Drop it?
          Kill circuit? This goes for all possible messages.]

Extensible INTRODUCE1 message format

When a client is connecting to an introduction point, INTRODUCE1 messages should be of the form:

     LEGACY_KEY_ID   [20 bytes]
     AUTH_KEY_TYPE   [1 byte]
     AUTH_KEY_LEN    [2 bytes]
     AUTH_KEY        [AUTH_KEY_LEN bytes]
     N_EXTENSIONS    [1 byte]
     N_EXTENSIONS times:
       EXT_FIELD_TYPE [1 byte]
       EXT_FIELD_LEN  [1 byte]
       EXT_FIELD      [EXT_FIELD_LEN bytes]
     ENCRYPTED        [Up to end of relay message body]

The ENCRYPTED field is described in the [PROCESS_INTRO2] section.

AUTH_KEY_TYPE is defined as in [EST_INTRO]. Currently, the only value of AUTH_KEY_TYPE for this message is an Ed25519 public key [02].

The LEGACY_KEY_ID field is used to distinguish between legacy and new style INTRODUCE1 messages. In new style INTRODUCE1 messages, LEGACY_KEY_ID is 20 zero bytes. Upon receiving an INTRODUCE1 messages, the introduction point checks the LEGACY_KEY_ID field. If LEGACY_KEY_ID is non-zero, the INTRODUCE1 message should be handled as a legacy INTRODUCE1 message by the intro point.

Upon receiving a INTRODUCE1 message, the introduction point checks whether AUTH_KEY matches the introduction point authentication key for an active introduction circuit. If so, the introduction point sends an INTRODUCE2 message with exactly the same contents to the service, and sends an INTRODUCE_ACK response to the client.

(Note that the introduction point does not "clean up" the INTRODUCE1 message that it retransmits. Specifically, it does not change the order or multiplicity of the extensions sent by the client.)

The same rules for multiplicity, ordering, and handling unknown types apply to the extension fields here as described [EST_INTRO] above.

INTRODUCE_ACK message format.

An INTRODUCE_ACK message has the following fields:

     STATUS       [2 bytes]
     N_EXTENSIONS [1 bytes]
     N_EXTENSIONS times:
       EXT_FIELD_TYPE [1 byte]
       EXT_FIELD_LEN  [1 byte]
       EXT_FIELD      [EXT_FIELD_LEN bytes]

   Recognized status values are:

     [00 00] -- Success: message relayed to hidden service host.
     [00 01] -- Failure: service ID not recognized
     [00 02] -- Bad message format
     [00 03] -- Can't relay message to service

The same rules for multiplicity, ordering, and handling unknown types apply to the extension fields here as described [EST_INTRO] above.

Processing an INTRODUCE2 message at the hidden service.

Upon receiving an INTRODUCE2 message, the hidden service host checks whether the AUTH_KEY or LEGACY_KEY_ID field matches the keys for this introduction circuit.

The service host then checks whether it has received a message with these contents or rendezvous cookie before. If it has, it silently drops it as a replay. (It must maintain a replay cache for as long as it accepts messages with the same encryption key. Note that the encryption format below should be non-malleable.)

If the message is not a replay, it decrypts the ENCRYPTED field, establishes a shared key with the client, and authenticates the whole contents of the message as having been unmodified since they left the client. There may be multiple ways of decrypting the ENCRYPTED field, depending on the chosen type of the encryption key. Requirements for an introduction handshake protocol are described in [INTRO-HANDSHAKE-REQS]. We specify one below in section [NTOR-WITH-EXTRA-DATA].

The decrypted plaintext must have the form:

      RENDEZVOUS_COOKIE                          [20 bytes]
      N_EXTENSIONS                               [1 byte]
      N_EXTENSIONS times:
          EXT_FIELD_TYPE                         [1 byte]
          EXT_FIELD_LEN                          [1 byte]
          EXT_FIELD                              [EXT_FIELD_LEN bytes]
      ONION_KEY_TYPE                             [1 bytes]
      ONION_KEY_LEN                              [2 bytes]
      ONION_KEY                                  [ONION_KEY_LEN bytes]
      NSPEC      (Number of link specifiers)     [1 byte]
      NSPEC times:
          LSTYPE (Link specifier type)           [1 byte]
          LSLEN  (Link specifier length)         [1 byte]
          LSPEC  (Link specifier)                [LSLEN bytes]
      PAD        (optional padding)              [up to end of plaintext]

Upon processing this plaintext, the hidden service makes sure that any required authentication is present in the extension fields, and then extends a rendezvous circuit to the node described in the LSPEC fields, using the ONION_KEY to complete the extension. As mentioned in [BUILDING-BLOCKS], the "TLS-over-TCP, IPv4" and "Legacy node identity" specifiers must be present.

As of 0.4.1.1-alpha, clients include both IPv4 and IPv6 link specifiers in INTRODUCE1 messages. All available addresses SHOULD be included in the message, regardless of the address that the client actually used to extend to the rendezvous point.

The hidden service should handle invalid or unrecognised link specifiers the same way as clients do in section 2.5.2.2. In particular, services SHOULD perform basic validity checks on link specifiers, and SHOULD NOT reject unrecognised link specifiers, to avoid information leaks. The list of link specifiers received here SHOULD either be rejected, or sent verbatim when extending to the rendezvous point, in the same order received.

The service MAY reject the list of link specifiers if it is inconsistent with relay information from the directory, but SHOULD NOT modify it.

The ONION_KEY_TYPE field is:

[01] NTOR: ONION_KEY is 32 bytes long.

The ONION_KEY field describes the onion key that must be used when extending to the rendezvous point. It must be of a type listed as supported in the hidden service descriptor.

The PAD field should be filled with zeros; its size should be chosen so that the INTRODUCE2 message occupies a fixed maximum size, in order to hide the length of the encrypted data. (This maximum size is 490, since we assume that a future Tor implementations will implement proposal 340 and thus lower the number of bytes that can be contained in a single relay message.) Note also that current versions of Tor only pad the INTRODUCE2 message up to 246 bytes.

Upon receiving a well-formed INTRODUCE2 message, the hidden service host will have:

     * The information needed to connect to the client's chosen
       rendezvous point.
     * The second half of a handshake to authenticate and establish a
       shared key with the hidden service client.
     * A set of shared keys to use for end-to-end encryption.

The same rules for multiplicity, ordering, and handling unknown types apply to the extension fields here as described [EST_INTRO] above.

INTRODUCE1/INTRODUCE2 Extensions

The following sections details the currently supported or reserved extensions of an INTRODUCE1/INTRODUCE2 message.

Note that there are two sets of extensions in INTRODUCE1/INTRODUCE2: one in the top-level, unencrypted portion, and one within the plaintext of ENCRYPTED (ie, after RENDEZVOUS_COOKIE and before ONION_KEY_TYPE.

The sets of extensions allowed in each part of the message are disjoint: each extension is valid in only one of the two places.

Nevertheless, for historical reasons, both kinds of extension are listed in this section, and they use nonoverlapping values of EXT_FIELD_TYPE.

Congestion Control

This is used to request that the rendezvous circuit with the service be configured with congestion control.

EXT_FIELD_TYPE:

 \[01\] -- Congestion Control Request.

This field is has zero body length. Its presence signifies that the client wants to use congestion control. The client MUST NOT set this field, or use ntorv3, if the service did not list "2" in the FlowCtrl line in the descriptor. The client SHOULD NOT provide this field if the consensus parameter 'cc_alg' is 0.

This appears in the ENCRYPTED section of the INTRODUCE1/INTRODUCE2 message.

Proof-of-Work (PoW)

This extension can be used to optionally attach a proof of work to the introduction request. The proof must be calculated using unique parameters appropriate for this specific service. An acceptable proof will raise the priority of this introduction request according to the proof's verified computational effort.

This is for the proof-of-work DoS mitigation, described in depth by the Proof of Work for onion service introduction specification.

This appears in the ENCRYPTED section of the INTRODUCE1/INTRODUCE2 message.

The content is defined as follows:

EXT_FIELD_TYPE:

[02] -- PROOF_OF_WORK

The EXT_FIELD content format is:

    POW_SCHEME     [1 byte]
    POW_NONCE      [16 bytes]
    POW_EFFORT     [4 bytes]
    POW_SEED       [4 bytes]
    POW_SOLUTION   [16 bytes]

where:

POW_SCHEME is 1 for the `v1` protocol specified here
POW_NONCE is the nonce value chosen by the client's solver
POW_EFFORT is the effort value chosen by the client,
           as a 32-bit integer in network byte order
POW_SEED identifies which seed was in use, by its first 4 bytes
POW_SOLUTION is a matching proof computed by the client's solver

Only SCHEME 1, v1, is currently defined. Other schemes may have a different format, after the POW_SCHEME byte. A correctly functioning client only submits solutions with a scheme and seed which were advertised by the server (using a "pow-params" Item in the HS descriptor) and have not yet expired. An extension with an unknown scheme or expired seed is suspicious and SHOULD result in introduction failure.

Introduced in tor-0.4.8.1-alpha.

Subprotocol Request

[RESERVED]

EXT_FIELD_TYPE:

 \[03\] -- Subprotocol Request

Introduction handshake encryption requirements

When decoding the encrypted information in an INTRODUCE2 message, a hidden service host must be able to:

     * Decrypt additional information included in the INTRODUCE2 message,
       to include the rendezvous token and the information needed to
       extend to the rendezvous point.

     * Establish a set of shared keys for use with the client.

     * Authenticate that the message has not been modified since the client
       generated it.

Note that the old TAP-derived protocol of the previous hidden service design achieved the first two requirements, but not the third.

Example encryption handshake: ntor with extra data

TODO: relocate this

This is a variant of the ntor handshake (also see "Anonymity and one-way authentication in key-exchange protocols" by Goldberg, Stebila, and Ustaoglu).

It behaves the same as the ntor handshake, except that, in addition to negotiating forward secure keys, it also provides a means for encrypting non-forward-secure data to the server (in this case, to the hidden service host) as part of the handshake.

Notation here is as in section 5.1.4 of tor-spec.txt, which defines the ntor handshake.

The PROTOID for this variant is "tor-hs-ntor-curve25519-sha3-256-1". We also use the following tweak values:

      t_hsenc    = PROTOID | ":hs_key_extract"
      t_hsverify = PROTOID | ":hs_verify"
      t_hsmac    = PROTOID | ":hs_mac"
      m_hsexpand = PROTOID | ":hs_key_expand"

To make an INTRODUCE1 message, the client must know a public encryption key B for the hidden service on this introduction circuit. The client generates a single-use keypair:

x,X = KEYGEN()

and computes:

             intro_secret_hs_input = EXP(B,x) | AUTH_KEY | X | B | PROTOID
             info = m_hsexpand | N_hs_subcred
             hs_keys = KDF(intro_secret_hs_input | t_hsenc | info, S_KEY_LEN+MAC_LEN)
             ENC_KEY = hs_keys[0:S_KEY_LEN]
             MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]

   and sends, as the ENCRYPTED part of the INTRODUCE1 message:

          CLIENT_PK                [PK_PUBKEY_LEN bytes]
          ENCRYPTED_DATA           [Padded to length of plaintext]
          MAC                      [MAC_LEN bytes]

Substituting those fields into the INTRODUCE1 message body format described in [FMT_INTRO1] above, we have

            LEGACY_KEY_ID               [20 bytes]
            AUTH_KEY_TYPE               [1 byte]
            AUTH_KEY_LEN                [2 bytes]
            AUTH_KEY                    [AUTH_KEY_LEN bytes]
            N_EXTENSIONS                [1 bytes]
            N_EXTENSIONS times:
               EXT_FIELD_TYPE           [1 byte]
               EXT_FIELD_LEN            [1 byte]
               EXT_FIELD                [EXT_FIELD_LEN bytes]
            ENCRYPTED:
               CLIENT_PK                [PK_PUBKEY_LEN bytes]
               ENCRYPTED_DATA           [Padded to length of plaintext]
               MAC                      [MAC_LEN bytes]

(This format is as documented in [FMT_INTRO1] above, except that here we describe how to build the ENCRYPTED portion.)

Here, the encryption key plays the role of B in the regular ntor handshake, and the AUTH_KEY field plays the role of the node ID. The CLIENT_PK field is the public key X. The ENCRYPTED_DATA field is the message plaintext, encrypted with the symmetric key ENC_KEY. The MAC field is a MAC of all of the message from the AUTH_KEY through the end of ENCRYPTED_DATA, using the MAC_KEY value as its key.

To process this format, the hidden service checks PK_VALID(CLIENT_PK) as necessary, and then computes ENC_KEY and MAC_KEY as the client did above, except using EXP(CLIENT_PK,b) in the calculation of intro_secret_hs_input. The service host then checks whether the MAC is correct. If it is invalid, it drops the message. Otherwise, it computes the plaintext by decrypting ENCRYPTED_DATA.

The hidden service host now completes the service side of the extended ntor handshake, as described in tor-spec.txt section 5.1.4, with the modified PROTOID as given above. To be explicit, the hidden service host generates a keypair of y,Y = KEYGEN(), and uses its introduction point encryption key 'b' to compute:

      intro_secret_hs_input = EXP(X,b) | AUTH_KEY | X | B | PROTOID
      info = m_hsexpand | N_hs_subcred
      hs_keys = KDF(intro_secret_hs_input | t_hsenc | info, S_KEY_LEN+MAC_LEN)
      HS_DEC_KEY = hs_keys[0:S_KEY_LEN]
      HS_MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]

      (The above are used to check the MAC and then decrypt the
      encrypted data.)

      rend_secret_hs_input = EXP(X,y) | EXP(X,b) | AUTH_KEY | B | X | Y | PROTOID
      NTOR_KEY_SEED = MAC(rend_secret_hs_input, t_hsenc)
      verify = MAC(rend_secret_hs_input, t_hsverify)
      auth_input = verify | AUTH_KEY | B | Y | X | PROTOID | "Server"
      AUTH_INPUT_MAC = MAC(auth_input, t_hsmac)

      (The above are used to finish the ntor handshake.)

   The server's handshake reply is:

       SERVER_PK   Y                         [PK_PUBKEY_LEN bytes]
       AUTH        AUTH_INPUT_MAC            [MAC_LEN bytes]

These fields will be sent to the client in a RENDEZVOUS1 message using the HANDSHAKE_INFO element (see [JOIN_REND]).

The hidden service host now also knows the keys generated by the handshake, which it will use to encrypt and authenticate data end-to-end between the client and the server. These keys are as computed with the ntor handshake, except that instead of using AES-128 and SHA1 for this hop, we use AES-256 and SHA3-256.

Authentication during the introduction phase.

Hidden services may restrict access only to authorized users. One mechanism to do so is the credential mechanism, where only users who know the credential for a hidden service may connect at all.

There is one defined authentication type: ed25519.

Ed25519-based authentication ed25519

(NOTE: This section is not implemented by Tor. It is likely that we would want to change its design substantially before deploying any implementation. At the very least, we would want to bind these extensions to a single onion service, to prevent replays. We might also want to look for ways to limit the number of keys a user needs to have.)

To authenticate with an Ed25519 private key, the user must include an extension field in the encrypted part of the INTRODUCE1 message with an EXT_FIELD_TYPE type of [02] and the contents:

        Nonce     [16 bytes]
        Pubkey    [32 bytes]
        Signature [64 bytes]

Nonce is a random value. Pubkey is the public key that will be used to authenticate. [TODO: should this be an identifier for the public key instead?] Signature is the signature, using Ed25519, of:

        "hidserv-userauth-ed25519"
        Nonce       (same as above)
        Pubkey      (same as above)
        AUTH_KEY    (As in the INTRODUCE1 message)

The hidden service host checks this by seeing whether it recognizes and would accept a signature from the provided public key. If it would, then it checks whether the signature is correct. If it is, then the correct user has authenticated.

Replay prevention on the whole message is sufficient to prevent replays on the authentication.

Users SHOULD NOT use the same public key with multiple hidden services.