009: Key Exchange

This page will reference RFC 4253 - 7. Key Exchange. This covers the first packet that both sides must send immediately following their Protocol Version Exchange message. The purpose of this packet is so each side can tell the other about the known list of possible algorithms they support. From this list, the client and server will pick the first (best) match in each list, and using that, they will exchange the necessary keys to be able to encrypt and decrypt their conversation.

The packet looks like:

      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)

We have seen byte, byte[x], and unit32 before, but there are two new types. name-list is a comma delimited string and string is a uint32 that contains the length of the string followed by a byte[x] that is the string (usually ASCII encoded, unless displayed to the user). For more details, see 5. Data Type Representations Used in the SSH Protocols. boolean is a byte that must be 0x00 for false and 0x01 for true.

So, what does it mean when the packet lists the first byte as SSH_MSG_KEXINIT. These are constants that are defined (mostly) by RFC 4250 - 4.1.2. Initial Assignments. In this case, SSH_MSG_KEXINIT is always the 20 (0x14 in hex). So, the first byte of this packet will be 20. Then it will have 16 bytes of random data. It will be followed by 10 strings (comma delimited lists of names). Then a byte of 0x00 or 0x01 to indicate if the first key exchange packet is already in route. This can be used if the client wants to guess at the algorithms to use, but usually it will be false. Then the packet is ended with a uint32 (four bytes) with a value of 0.

What does this look like? Well OpenSSH sends:

KEX algorithms:  curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,ext-info-c
host key algorithms:  ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ssh-ed25519-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
ciphers ctos:  chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc,3des-cbc
ciphers stoc:  chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,aes192-cbc,aes256-cbc,3des-cbc
MACs ctos:  umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
MACs stoc:  umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
compression ctos:  none,zlib@openssh.com,zlib
compression stoc:  none,zlib@openssh.com,zlib
languages ctos:
languages stoc:
first_kex_follows:  0
reserved:  0

At the same time, the server sends it's list of supported algorithms to the client, and they pick the best matches. If one cannot be found for any of the categories, both client and server should disconnect.

At this point we need to take the packet payload that we read previously load it into the correct type for processing. I like to use reflection offered by the .NET framework to make this easy. I will reflect over all classes that inherit from the abstract class Packet and create an instance of them, then use that to look at the Packet Type, and use that to save a dictionary of packet type to class. Then, when a packet comes in, I will use this dictionary to find the correct type, create an instance of it, and let it parse it's own payload. I like this mechanism because it requires no work to add support for new packets. Other languages will have different mechanisms that can/should be used. It might be easier for C++ or Rust to just process the raw bytes as you need them.

We will also need to make a ByteWriter helper class that will is just a wrapper for MemoryStream for writing to a stream in the expected format. The server will use this when it sends a packet to the client to convert a packet into a byte[] for sending.

So, up next, Sending A Packet