When connecting via SSH, does the Diffie-Hellman key exchange take place over an unencrypted TCP session or does encryption occur before the exchange?

Question

I'm a cybersecurity student and I'm eager to understand the basic processes of an SSH session. I wrote down the stages to the best of my ability but need help understanding what happens right after the TCP handshake and right before the Diffie-Hellman key exchange. Please help:

Session Start/TCP Handshake

1.Client begins a session with Server by initiating a TCP handshake.

Assymetric Encryption for TCP Session

2.Server and Client negotiate back-and-forth and agree upon a mutually supported encryption protocol for the TCP session.

At this point, post-protocol-negotiation, it is unclear to me how their session is initially being encrypted. I used Wireshark to try and capture the Client or Server sending over their public key or something but could only see the protocol version exchange. Regardless, please explain this stage if you can.

Client and Server negotiate a shared secret key for this session using the Diffie-Hellman algorithm in order to establish a symmetric-key encrypted session.

3.Client and Server begin process of producing temporary key pairs, using 1. Shared prime number 2. Encryption generator (typically AES) 3. Private prime number (as private key).

4.Client and Server use these three to each generate their own public key that can be derived from their own private key.

5.Client and Server each share their generated public key with each other.

6.Client and Server each use their own private key, the other's public key and their original shared prime number to generate the same secret key.

7.Client and Server use this key as their shared secret key to encrypt and decrypt all future communication on this session.

At this stage, Client and Server have successfully established a symmetric-key-encrypted session without having needed to send the secret key over the network.

If I got anything else wrong I'd really appreciate any clarification. Thanks!

Answer 1

See RFC 5656, section 4, which describes the protocol for Diffie Hellman key exchange for SSH. I've coped the diagram from this section below:

  Client                                                Server
  ------                                                ------
  Generate ephemeral key pair.
  SSH_MSG_KEX_ECDH_INIT  -------------->

                                  Verify received key is valid.
                                   Generate ephemeral key pair.
                                         Compute shared secret.
                               Generate and sign exchange hash.
                         <------------- SSH_MSG_KEX_ECDH_REPLY

  Verify received key is valid.
  *Verify host key belongs to server.
  Compute shared secret.
  Generate exchange hash.
  Verify server's signature.

  *  It is RECOMMENDED that the client verify that the host key sent
     is the server's host key (for example, using a local database).
     The client MAY accept the host key without verification, but
     doing so will render the protocol insecure against active
     attacks; see the discussion in Section 4.1 of [RFC4251].

So, the session starts off unencrypted. Key exchange takes place over the unencrypted connection. At that point, the client and the server share a shared secret. Then, this shared secret is used as an ephemeral key to encrypt the remainder of the session.

Answer 2

... I used Wireshark to try and capture the Client or Server sending over their public key or something but could only see the protocol version exchange. ...

Then you are probably doing something wrong. I can see fine, as below.

1.Client begins a session with Server by initiating a TCP handshake.

2.Server and Client negotiate back-and-forth and agree upon a mutually supported encryption protocol for the TCP session.

Client initiates and server accepts a TCP connection (frames 1-3). Then they nominally 'negotiate' the protocol version, but since the turn of the century this is ALWAYS 2.0 (frames 4 and 6). Finally they each send a list of supported algorithms for all of the SSH protocol components, of which encryption is only two. Frame 7 is the client list; frame 8 is the server list which I didn't show:

Based on these two lists, both peers compute the 'best' shared algorithms for each component, according to rules in RFC4253 7.1. (If this doesn't work, because there is not a shared algorithm for each component, the connection is aborted.)

Since you apparently want 'classic' Diffie-Hellman using a prime integer (also called modp, finite-field, or in mathematical notation Z_p*) I have forced that. By default the version of PuTTY I use would have preferred Elliptic-Curve DH (ECDH), as described by mti2935's answer, which is more efficient and thus more popular nowadays.

3.Client and Server begin process of producing temporary key pairs, using 1. Shared prime number 2. Encryption generator (typically AES) 3. Private prime number (as private key).

4.Client and Server use these three to each generate their own public key that can be derived from their own private key.

5.Client and Server each share their generated public key with each other.

Classic DH uses a group defined by a large prime number called the modulus and a number called the generator which is usually small and in fact usually 2. AES is not involved in any way. SSH can use either a standard group, or 'group-exchange' where the server specifies the group explicitly, usually based on data in its configuration (e.g. OpenSSH uses a file /etc/ssh/moduli). In this example the group preferred by my client, and therefore used, is 'group14', defined in RFC3526 3:

   This group is assigned id 14.

   This prime is: 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }

   Its hexadecimal value is:

      FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
      29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
      EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
      E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
      EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
      C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
      83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
      670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
      E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
      DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
      15728E5A 8AACAA68 FFFFFFFF FFFFFFFF

   The generator is: 2.

To do classic DH, each party chooses a private key x which is a number in the range (1,order(g)), which is not necessarily and not usually prime, and computes the public key y = g^x mod p. SSH labels the client publickey 'e' and the server publickey 'f'. The client sends a KEXDH_INIT message containing e, and the server sends a KEXDH_REPLY message containing among other things f, per RFC4253 8 which are quite nicely visible in frames 9 and 10:

6.Client and Server each use their own private key, the other's public key and their original shared prime number to generate the same secret key.

7.Client and Server use this key as their shared secret key to encrypt and decrypt all future communication on this session.

Almost. The shared secret isn't used directly for encryption and decryption, but goes through some further processing first, see RFC 4253 7.2. And it is also used for generating and verifying MACs, except with ciphers that have builtin data authentication (like GCM).

Encryption is actually initiated by a NEWKEYS message; you can see above the server included this in frame 10, and the client sent it at the beginning of frame 11 (not shown).

Did you notice that the specification for SSH contains a good deal of useful information about SSH? You might want to consider, like, reading it.