Skip to main content

7. Key Exchange

7. Key Exchange​

Key exchange (kex) begins by each side sending name-lists of supported algorithms. Each side has a preferred algorithm in each category, and it is assumed that most implementations, at any given time, will use the same preferred algorithm. Each side MAY guess which algorithm the other side is using, and MAY send an initial key exchange packet according to the algorithm, if appropriate for the preferred method.

The guess is considered wrong if:

  • the kex algorithm and/or the host key algorithm is guessed wrong (server and client have different preferred algorithm), or

  • if any of the other algorithms cannot be agreed upon (the procedure is defined below in Section 7.1).

Otherwise, the guess is considered to be right, and the optimistically sent packet MUST be handled as the first key exchange packet.

However, if the guess was wrong, and a packet was optimistically sent by one or both parties, such packets MUST be ignored (even if the error in the guess would not affect the contents of the initial packet(s)), and the appropriate side MUST send the correct initial packet.

A key exchange method uses explicit server authentication if the key exchange messages include a signature or other proof of the server's authenticity. A key exchange method uses implicit server authentication if, in order to prove its authenticity, the server also has to prove that it knows the shared secret, K, by sending a message and a corresponding MAC that the client can verify.

The key exchange method defined by this document uses explicit server authentication. However, key exchange methods with implicit server authentication MAY be used with this protocol. After a key exchange with implicit server authentication, the client MUST wait for a response to its service request message before sending any further data.

7.1. Algorithm Negotiation​

Key exchange begins by each side sending the following packet:

      byte         SSH_MSG_KEXINIT
      byte[16]     cookie (random bytes)
      name-list    kex_algorithms
      name-list    server_host_key_algorithms
      name-list    encryption_algorithms_client_to_server
      name-list    encryption_algorithms_server_to_client
      name-list    mac_algorithms_client_to_server
      name-list    mac_algorithms_server_to_client
      name-list    compression_algorithms_client_to_server
      name-list    compression_algorithms_server_to_client
      name-list    languages_client_to_server
      name-list    languages_server_to_client
      boolean      first_kex_packet_follows
      uint32       0 (reserved for future extension)

Each of the algorithm name-lists MUST be a comma-separated list of algorithm names (see Algorithm Naming in [SSH-ARCH] and additional information in [SSH-NUMBERS]). Each supported (allowed) algorithm MUST be listed in order of preference, from most to least.

The first algorithm in each name-list MUST be the preferred (guessed) algorithm. Each name-list MUST contain at least one algorithm name.

      cookie
         The 'cookie' MUST be a random value generated by the sender.
         Its purpose is to make it impossible for either side to fully
         determine the keys and the session identifier.
      kex_algorithms
         Key exchange algorithms were defined above.  The first
         algorithm MUST be the preferred (and guessed) algorithm.  If
         both sides make the same guess, that algorithm MUST be used.
         Otherwise, the following algorithm MUST be used to choose a key
         exchange method: Iterate over client's kex algorithms, one at a
         time.  Choose the first algorithm that satisfies the following
         conditions:
         +  the server also supports the algorithm,
         +  if the algorithm requires an encryption-capable host key,
            there is an encryption-capable algorithm on the server's
            server_host_key_algorithms that is also supported by the
            client, and
         +  if the algorithm requires a signature-capable host key,
            there is a signature-capable algorithm on the server's
            server_host_key_algorithms that is also supported by the
            client.
      If no algorithm satisfying all these conditions can be found, the
      connection fails, and both sides MUST disconnect.
      server_host_key_algorithms
         A name-list of the algorithms supported for the server host
         key.  The server lists the algorithms for which it has host
         keys; the client lists the algorithms that it is willing to
         accept.  There MAY be multiple host keys for a host, possibly
         with different algorithms.
         Some host keys may not support both signatures and encryption
         (this can be determined from the algorithm), and thus not all
         host keys are valid for all key exchange methods.
         Algorithm selection depends on whether the chosen key exchange
         algorithm requires a signature or an encryption-capable host
         key.  It MUST be possible to determine this from the public key
         algorithm name.  The first algorithm on the client's name-list
         that satisfies the requirements and is also supported by the
         server MUST be chosen.  If there is no such algorithm, both
         sides MUST disconnect.
      encryption_algorithms
         A name-list of acceptable symmetric encryption algorithms (also
         known as ciphers) in order of preference.  The chosen
         encryption algorithm to each direction MUST be the first
         algorithm on the client's name-list that is also on the
         server's name-list.  If there is no such algorithm, both sides
         MUST disconnect.
         Note that "none" must be explicitly listed if it is to be
         acceptable.  The defined algorithm names are listed in Section
         6.3.
      mac_algorithms
         A name-list of acceptable MAC algorithms in order of
         preference.  The chosen MAC algorithm MUST be the first
         algorithm on the client's name-list that is also on the
         server's name-list.  If there is no such algorithm, both sides
         MUST disconnect.
         Note that "none" must be explicitly listed if it is to be
         acceptable.  The MAC algorithm names are listed in Section 6.4.
      compression_algorithms
         A name-list of acceptable compression algorithms in order of
         preference.  The chosen compression algorithm MUST be the first
         algorithm on the client's name-list that is also on the
         server's name-list.  If there is no such algorithm, both sides
         MUST disconnect.
         Note that "none" must be explicitly listed if it is to be
         acceptable.  The compression algorithm names are listed in
         Section 6.2.
      languages
         This is a name-list of language tags in order of preference
         [RFC3066].  Both parties MAY ignore this name-list.  If there
         are no language preferences, this name-list SHOULD be empty as
         defined in Section 5 of [SSH-ARCH].  Language tags SHOULD NOT
         be present unless they are known to be needed by the sending
         party.
      first_kex_packet_follows
         Indicates whether a guessed key exchange packet follows.  If a
         guessed packet will be sent, this MUST be TRUE.  If no guessed
         packet will be sent, this MUST be FALSE.
         After receiving the SSH_MSG_KEXINIT packet from the other side,
         each party will know whether their guess was right.  If the
         other party's guess was wrong, and this field was TRUE, the
         next packet MUST be silently ignored, and both sides MUST then
         act as determined by the negotiated key exchange method.  If
         the guess was right, key exchange MUST continue using the
         guessed packet.

After the SSH_MSG_KEXINIT message exchange, the key exchange algorithm is run. It may involve several packet exchanges, as specified by the key exchange method.

Once a party has sent a SSH_MSG_KEXINIT message for key exchange or re-exchange, until it has sent a SSH_MSG_NEWKEYS message (Section 7.3), it MUST NOT send any messages other than:

  • Transport layer generic messages (1 to 19) (but SSH_MSG_SERVICE_REQUEST and SSH_MSG_SERVICE_ACCEPT MUST NOT be sent);

  • Algorithm negotiation messages (20 to 29) (but further SSH_MSG_KEXINIT messages MUST NOT be sent);

  • Specific key exchange method messages (30 to 49).

The provisions of Section 11 apply to unrecognized messages.

Note, however, that during a key re-exchange, after sending a SSH_MSG_KEXINIT message, each party MUST be prepared to process an arbitrary number of messages that may be in-flight before receiving a SSH_MSG_KEXINIT message from the other party.

7.2. Output from Key Exchange​

The key exchange produces two values: a shared secret K, and an exchange hash H. Encryption and authentication keys are derived from these. The exchange hash H from the first key exchange is additionally used as the session identifier, which is a unique identifier for this connection. It is used by authentication methods as a part of the data that is signed as a proof of possession of a private key. Once computed, the session identifier is not changed, even if keys are later re-exchanged.

Each key exchange method specifies a hash function that is used in the key exchange. The same hash algorithm MUST be used in key derivation. Here, we'll call it HASH.

Encryption keys MUST be computed as HASH, of a known value and K, as follows:

  • Initial IV client to server: HASH(K || H || "A" || session_id) (Here K is encoded as mpint and "A" as byte and session_id as raw data. "A" means the single character A, ASCII 65).

  • Initial IV server to client: HASH(K || H || "B" || session_id)

  • Encryption key client to server: HASH(K || H || "C" || session_id)

  • Encryption key server to client: HASH(K || H || "D" || session_id)

  • Integrity key client to server: HASH(K || H || "E" || session_id)

  • Integrity key server to client: HASH(K || H || "F" || session_id)

Key data MUST be taken from the beginning of the hash output. As many bytes as needed are taken from the beginning of the hash value. If the key length needed is longer than the output of the HASH, the key is extended by computing HASH of the concatenation of K and H and the entire key so far, and appending the resulting bytes (as many as HASH generates) to the key. This process is repeated until enough key material is available; the key is taken from the beginning of this value. In other words:

      K1 = HASH(K || H || X || session_id)   (X is e.g., "A")
      K2 = HASH(K || H || K1)
      K3 = HASH(K || H || K1 || K2)
      ...
      key = K1 || K2 || K3 || ...

This process will lose entropy if the amount of entropy in K is larger than the internal state size of HASH.

7.3. Taking Keys Into Use​

Key exchange ends by each side sending an SSH_MSG_NEWKEYS message. This message is sent with the old keys and algorithms. All messages sent after this message MUST use the new keys and algorithms.

When this message is received, the new keys and algorithms MUST be used for receiving.

The purpose of this message is to ensure that a party is able to respond with an SSH_MSG_DISCONNECT message that the other party can understand if something goes wrong with the key exchange.

      byte      SSH_MSG_NEWKEYS
Last updated on