SSH Key Exchange Deep Dive

How does SSH generate shared secret for encryption

---

SSH is a Secure Shell Protocol used broadly to connect to a server. Although it is not implemented based on TLS, it is treated as secure because all packets in the TCP session are encrypted. Even though we did not set any certificate or private key for SSH, this magical communication happens automatically.

I would like to dive deep into how this magical communication can happen. By the way, I am not an expert in mathematics, so I will skip the detailed implementation or calculation about cryptography(because I can’t even understand all of them…). I don’t think you need to know all the internal formulas for software engineering.

Preparation

I prepared the packet capture to explain what happens inside the SSH protocol. I created the EC2 instance with an RSA PEM key and tried to connect to the server with the paramiko library. Paramiko is a pure Python implementation of the SSHv2 protocol, providing both client and server functionality. Even though I’m unsure if the implementation is the same as other libraries, I think it is enough to understand the overall process.

import paramiko
from io import StringIO

def main():
    client = paramiko.SSHClient()
    ip = "<ssh server ip>"
    port = 22
    keypair_file_path = "test-key.pem"

    with open(keypair_file_path, "r") as f:
        keypair = f.read()
    keypair_io = StringIO(keypair)
    key = paramiko.RSAKey.from_private_key(keypair_io)
    client.set_missing_host_key_policy(paramiko.AutoAddPolicy())
    client.connect(hostname=ip, port=port, username="ec2-user", pkey=key)

    stdin, stdout, stderr = client.exec_command("ls -al")
    print(stdin, stdout, stderr)
    client.close()


if __name__ == '__main__':
    main()

Here’s the packet capture opened with Wireshark. You can see the SSHv2 in the protocol tap. Now, let’s inspect what happens step by step.

1. TCP connection

First, it is implemented over TCP. The client tries to create a TCP connection to the server. In the paramiko library, the client.connect function creates a socket if no socket is passed.

2. Version Check

Before starting the key exchange, the client and the server identify the SSH version. As you can see, it is now v2.

3. Negotiating the key exchange algorithm

The client sends the key exchange message through the TCP connection with supported and preferred key exchange algorithms.

You can find the kex(key exchange) algorithm if you check the packet inside. The client sends first, and then the server returns. If you inspect the packet in detail, you can find all the algorithms the client and server use.

If the client receives the exchange algorithm list from the server, it decides which algorithm to use. It searches for the algorithms that it prefers and that are contained in the algorithm list that the server sends. The paramiko library sets the first algorithm in the list for exchanging keys.

Here are the client's preferred key exchange algorithms. If you look at the packet from the server, you will see the curve25519-sha256@libssh.org.

3. Key Exchange with Diffie-Hellman algorithm

Now that we have decided to use the curve25519-sha256@libssh.org method, the client generates the private key to exchange with the DH algorithm. Diffie-Hellman is a key exchange algorithm usually used to safely exchange keys for generating the symmetric key. In my test environment, it is using the Elliptic Curve Diffie-Hellman Key Exchange algorithm, but normal DH works similarly.

The client and server generate the private key, a random number. The x25519 private key is a cryptographic key used in the X25519 key exchange protocol based on elliptic curve cryptography. The server just waits after generating its own private key.

On the other hand, the client sends the KEXECDH_INIT message to exchange the key with the Elliptic Curve DH method. At this time, it calculates the public key, which is a point on the elliptic curve derived from the private key. After sending a message, it waits for the KEXECDH_REPLY message.

The server, waiting for the KEXECDH_INIT packet, receives the packet from the client. The public key is included in the packet capture, but it is not encrypted yet.

Now, the server parses the packet to initiate the ECDH exchange. First, it retrieves the public key value from the packet. Then, it calculates the shared secret with its private key. Then, it generates its public key from the private key and sends it to the client.

Here’s the server's reply packet. It sends its ephemeral public key and its public host key.

The client, waiting for the rely, also tries to generate the shared secret. It retrieves the public key from the packet and computes the shared secret.

Here’s where the magic happens.

Even the calculation on the client side seems different from that on the server side because the client calculates the shared secret with its private key and the server’s public key, and the server does so with its private key and the client’s public key.

• Server: Server’s private key & Client’s public key.

• Client: Client’s private key & Server’s public key

Behind the scenes, the curve25519 algorithm contains the curve’s base point. Generating a public key from each side is the mathematical scala-multiplication of its private key and the curve's base point. This means the public key already contains the private key as the calculation.

• Server: Server’s private key & (Client’s private key & curve base point)

• Client: Client’s private key & (Server’s private key & curve base point)

In this case, both results are the same mathematically.

4. Retrieves the in & out key and IV

Both sides have the same shared secret, so they can encrypt and decrypt with the symmetric key, which is the shared secret. The client and server retrieve the Initialization Vector(IV) and the encryption key for outbound traffic. Those values are used when each encrypts the outbound packet.

You should know that they are not using the same key for inbound and outbound traffic. The code above shows that the client and server compute keys with different ID values. The order is changed for the inbound traffic.

_active_inbound method is called when it gets a NEW_KEYS message. As you can see, IDs used in the client for outbound are the same as those used in the server for inbound.

• Client-side

  • Encryption: Uses key derived from "C" and IV from "A"

  • Decryption: Uses key derived from "D" and IV from "B"

• Server-side

  • Encryption: Uses key derived from "D" and IV from "B"

  • Decryption: Uses key derived from "C" and IV from "A"

Until now, both client and server have exchanged keys and calculated the ciphers for encryption and decryption. In the current session, all packets are encrypted with precalculated ciphers. If a new session is created, all exchange processes will happen again.

5. Encrypt and decrypt the packet

When the client sends the packet, it checks the self.__block_engine_out method. It is defined as retrieving keys from a shared secret. So, before exchanging the key, the packet is not encrypted.

It’s the same when it gets an inbound packet. When it gets a packet from the other side, the read_message method is called. This method uses __block_engine_in to decrypt the packet.

Conclusion

In conclusion, when the SSH session is created via TCP, the client and server exchange keys to calculate the shared secret with the Diffie-Hellman algorithm.

In the Diffie-Hellman key exchange algorithm, each generates the public key by multiplying its private key and a common random number. Those public keys don’t need to be hidden from the hacker. When the client and server exchange the public key, they calculate it with their private key. Then, they get the same shared secret to generate the encryption key. After setting up the encryption and decryption ciphers, they can encrypt and decrypt both inbound and outbound packets.