011: The Algorithms

Let's cover each of the algorithms and the purpose of each. The RFC specifies ones that it considers REQUIRED and others that it considers RECOMMENDED and OPTIONAL. At the end of the day, you need to just make sure to implement at least one of each type that your client uses. Let's start with the Key Exchange.

####Key Exchange#### This is covered in various places in the RFC, but let's start at the 6.5. Key Exchange Methods. Here, it clearly states that diffie-hellman-group1-sha1 and diffie-hellman-group14-sha1 are both required. However, I was confused when I looked at the supported OpenSSH key exchange (KEX) algorithms as it has:

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

It does support diffie-hellman-group14-sha1, but the other one seems to be misnamed. It is missing the "1" after the group. For my sample server I decided to ONLY implement diffie-hellman-group14-sha1. Once your server is running, you can easily add new algorithms.

The purpose of the KEX is to decide on a mechanism that will allow the client and server to politely exchange private keys. The diffie-hellman exchange is described in 8. Diffie-Hellman Key Exchange. It is basically a mechanism for generating a set of hashes based on well known values. We will cover this in detail when we implement our KEX algorithm. However, once the KEX is done, then both sides will send one more packet (SSH_MSG_NEWKEYS) before switching to the selected algorithm sets.

Finally, at any time, either side may choose to trigger another KEX. The RFC recommends doing this after 1 hour of connectivity or after 1 gigabyte of transferred data.

####Host Key Algorithms#### I found this to be confusing, but mostly because it wasn't really explained in the RFC. The host key algorithm is referred to as 6.6. Public Key Algorithms. The RFC requires ssh-dss and recommends ssh-rsa.

OpenSSH supports:

ssh-rsa-cert-v01@openssh.com
rsa-sha2-512
rsa-sha2-256
ssh-rsa
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
ecdsa-sha2-nistp256
ecdsa-sha2-nistp384
ecdsa-sha2-nistp521
ssh-ed25519

Ironically, it doesn't support the ssh-dss, so it doesn't support the "required" choice. In our case, we'll add ssh-rsa support. As stated before, we'll be able to add more choices later if we want.

The purpose of the host (public) key algorithm is to allow the server to provide public key data to the client. The client can use this data to confirm the server is who they claim to be. When you connect with OpenSSH, it will ask you to confirm that you recognize the server's hash. The RFC expresses that it would like to see a centralized server that allows you to look up servers by hash so you can safely identify the server is who they claim to be, but I haven't seen any real implementation of this.

Finally, the host key is also used to generating part of the exchange hash. We'll cover this in more detail when we implement our ssh-rsa provider.

####Encryption or Ciphers#### This is one of the core pieces of SSH. The part where we choose how we will encrypt the data. This is covered in 6.3. Encryption. And you can see the required cipher 3des-cbc, however it is quoted from the RFC:

At some future time, it is expected that another algorithm, one with better strength, will become so prevalent and ubiquitous that the use of "3des-cbc" will be deprecated by another STANDARDS ACTION.

And OpenSSH supports:

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

So, we will add 3des-cbc, but you should consider other options too. There are a few pieces of each cipher algorithm. Each one has a specific block size. This block size is size of one encrypted block. When decrypting, you can decrypt each block if desired. We use this fact when reading the beginning of the packet to just decrypt the packet header.

Each cipher will have a set key size. This is the size of the key necessary to see the algorithm. Each cipher needs to be able to have the server set their key (which is received from the KEX chosen above). And finally, a way to encrypt and decrypt the data.

It is worth noting that there are two entries in the KEX_INIT packet for ciphers. One is for supported ciphers from client to server and the other is for supported ciphers from server to client. This means it is possible to use different algorithms for receiving and sending. However, in practice, they are almost always the same algorithm, but with different keys.

####MAC Algorithms#### At the end of each packet is a hash that can be used to confirm it came from the server and that it wasn't altered in transit. This is covered in 6.4. Data Integrity. The RFC lists hmac-sha1 as required and OpenSSH supports:

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

Each MAC algorithm has a set length, this allows each side to know exactly how big the MAC should be. Until an algorithm is chosen, there should be no MAC added (0 bytes). All MAC algorithms have a set key size, a digest length, a way to set the key which is created during KEX, and finally a way to compute the hash for a given payload and packet number. As with ciphers, it is possible to have a different algorithm used for client to server and server to client, but generally, they are the same algorithm with different keys.

####Compression Algorithms#### The last algorithm that is selected during KEX is used to compress the payload (and only the payload) of the packet. This is covered in the RFC section 6.2. Compression. By default it will be assumed to be none, which means, you don't need to actually support compression. OpenSSH supports:

none
zlib@openssh.com
zlib

For our server, we'll just implement provider of none to allow for compression support later. The compression algorithm needs to be able to compress and decompress any block of data. As with the cipher and MAC algorithms, the compression algorithm can be different between the send and receive, but is generally the same.

####Summary#### This is a lot of information to digest, but the purpose of the KEX_INIT packet is for both client and server to decide the best algorithms to use. After each side sends this packet, both sides should know the best algorithms to use for each type and direction. We are now ready to begin the key exchange. The first step of this, is the client sending a SSH_MSG_KEXDH_INIT packet and waiting for the server to send a SSH_MSG_KEXDH_REPLY. But before we can do this, we need to implement one of each algorithm! So, up next, we will Implement diffie-hellman-group14-sha1.