018: Handling SSH_MSG_KEXDH_INIT

The first order of business is to call out an omission in the RFCs. They were later added in errata, but the original documents have not been updated. Two extra packet types are defined for KEX. We need to update the PacketType enum to include these:

        SSH_MSG_KEXDH_INIT = 30,
        SSH_MSG_KEXDH_REPLY = 31,

Now we can create a KexDHInit class in the Packets folder and inherit from Packet. A simple implementation is:

    public class KexDHInit : Packet
    {
        public override PacketType PacketType
        {
            get
            {
                return PacketType.SSH_MSG_KEXDH_INIT;
            }
        }

        public byte[] ClientValue { get; private set; }

        protected override void InternalGetBytes(ByteWriter writer)
        {
            // Server never sends this
            throw new InvalidOperationException("SSH Server should never send a SSH_MSG_KEXDH_INIT message");
        }

        protected override void Load(ByteReader reader)
        {
            // First, the client sends the following:
            //  byte SSH_MSG_KEXDH_INIT (handled by base class)
            //  mpint e
            ClientValue = reader.GetMPInt();
        }
    }

This packet only contains a mpint type. We haven't really discussed this type, but details can be seen at 5. Data Type Representations Used in the SSH Protocols. Ultimately, an mpint is a uint32 with the length, and they a simple set of bytes of that length. Later we can plan to interpret them as a BigInteger in C#. The only catch, if the first byte is 0, we skip that byte.

Now that we have a packet, we can add a packet handler to the Client class:

    private void HandleSpecificPacket(KexDHInit packet)
    {
        m_Logger.LogDebug("Received KexDHInit");
        // TDOO: Implement Key Exchange!
    }

We should also create our KexDHReply class to handle our response we need to send to the client:

    public class KexDHReply : Packet
    {
        public override PacketType PacketType
        {
            get
            {
                return PacketType.SSH_MSG_KEXDH_REPLY;
            }
        }

        public byte[] ServerHostKey { get; set; }
        public byte[] ServerValue { get; set; }
        public byte[] Signature { get; set; }

        protected override void InternalGetBytes(ByteWriter writer)
        {
            // string server public host key and certificates(K_S)
            // mpint f
            // string signature of H
            writer.WriteBytes(ServerHostKey);
            writer.WriteMPInt(ServerValue);
            writer.WriteBytes(Signature);
        }

        protected override void Load(ByteReader reader)
        {
            // Client never sends this!
            throw new InvalidOperationException("SSH Client should never send a SSH_MSG_KEXDH_REPLY message");
        }
    }

Here, we have to write the values out that it expects. The RFC refers to these as "string" types, but the data is actually raw bytes generated via the various hashing algorithms. What the RFC means, is that it will write out the length as a uint32 first, then just write the raw bytes after that.

Now we have the pieces to receive the key from the client and we can write a reply to the client with our keys. So, let's do this! First we need to prepare to store the session ID. This is defined in the RFC 7.2. Output from Key Exchange. It states:

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.

    public class Client
    {
        ...
        private byte[] m_SessionId = null;
        ...
    }

The next section is probably going to be very hard to follow, but I hope you aren't lost. I'll try to explain.

We use the pending exchange context to generate the necessary pieces of the KEX as described in 8. Diffie-Hellman Key Exchange. The client sends us a value e in the KEXDH_INIT packet. I added a lot of inline comments to help explain:

        private void HandleSpecificPacket(KexDHInit packet)
        {
            m_Logger.LogDebug("Received KexDHInit");

            if ((m_PendingExchangeContext == null) || (m_PendingExchangeContext.KexAlgorithm == null))
            {
                throw new InvalidOperationException("Server did not receive SSH_MSG_KEX_INIT as expected.");
            }

            // 1. C generates a random number x (1 &lt x &lt q) and computes e = g ^ x mod p.  C sends e to S.
            // 2. S receives e.  It computes K = e^y mod p
            byte[] sharedSecret = m_PendingExchangeContext.KexAlgorithm.DecryptKeyExchange(packet.ClientValue);

            // 2. S generates a random number y (0 < y < q) and computes f = g ^ y mod p.
            byte[] serverKeyExchange = m_PendingExchangeContext.KexAlgorithm.CreateKeyExchange();

            byte[] hostKey = m_PendingExchangeContext.HostKeyAlgorithm.CreateKeyAndCertificatesData();

            // H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)
            byte[] exchangeHash = ComputeExchangeHash(
                m_PendingExchangeContext.KexAlgorithm,
                hostKey,
                packet.ClientValue,
                serverKeyExchange,
                sharedSecret);

            if (m_SessionId == null)
                m_SessionId = exchangeHash;

            // https://tools.ietf.org/html/rfc4253#section-7.2

            // 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).
            byte[] clientCipherIV = ComputeEncryptionKey(
                m_PendingExchangeContext.KexAlgorithm,
                exchangeHash,
                m_PendingExchangeContext.CipherClientToServer.BlockSize,
                sharedSecret, 'A');

            // Initial IV server to client: HASH(K || H || "B" || session_id)
            byte[] serverCipherIV = ComputeEncryptionKey(
                m_PendingExchangeContext.KexAlgorithm,
                exchangeHash,
                m_PendingExchangeContext.CipherServerToClient.BlockSize,
                sharedSecret, 'B');

            // Encryption key client to server: HASH(K || H || "C" || session_id)
            byte[] clientCipherKey = ComputeEncryptionKey(
                m_PendingExchangeContext.KexAlgorithm,
                exchangeHash,
                m_PendingExchangeContext.CipherClientToServer.KeySize,
                sharedSecret, 'C');

            // Encryption key server to client: HASH(K || H || "D" || session_id)
            byte[] serverCipherKey = ComputeEncryptionKey(
                m_PendingExchangeContext.KexAlgorithm,
                exchangeHash,
                m_PendingExchangeContext.CipherServerToClient.KeySize,
                sharedSecret, 'D');

            // Integrity key client to server: HASH(K || H || "E" || session_id)
            byte[] clientHmacKey = ComputeEncryptionKey(
                m_PendingExchangeContext.KexAlgorithm,
                exchangeHash,
                m_PendingExchangeContext.MACAlgorithmClientToServer.KeySize,
                sharedSecret, 'E');

            // Integrity key server to client: HASH(K || H || "F" || session_id)
            byte[] serverHmacKey = ComputeEncryptionKey(
                m_PendingExchangeContext.KexAlgorithm,
                exchangeHash,
                m_PendingExchangeContext.MACAlgorithmServerToClient.KeySize,
                sharedSecret, 'F');

            // Set all keys we just generated
            m_PendingExchangeContext.CipherClientToServer.SetKey(clientCipherKey, clientCipherIV);
            m_PendingExchangeContext.CipherServerToClient.SetKey(serverCipherKey, serverCipherIV);
            m_PendingExchangeContext.MACAlgorithmClientToServer.SetKey(clientHmacKey);
            m_PendingExchangeContext.MACAlgorithmServerToClient.SetKey(serverHmacKey);

            // Send reply to client!
            KexDHReply reply = new KexDHReply()
            {
                ServerHostKey = hostKey,
                ServerValue = serverKeyExchange,
                Signature = m_PendingExchangeContext.HostKeyAlgorithm.CreateSignatureData(exchangeHash)
            };

            Send(reply);
            
            // TODO: Send a NEWKEYS message
        }

Now there are two helper methods not covered above. The first is used to get the exchange hash: ComputeExchangeHash()

        private byte[] ComputeExchangeHash(IKexAlgorithm kexAlgorithm, byte[] hostKeyAndCerts, byte[] clientExchangeValue, byte[] serverExchangeValue, byte[] sharedSecret)
        {
            // H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)
            using (ByteWriter writer = new ByteWriter())
            {
                writer.WriteString(m_ProtocolVersionExchange);
                writer.WriteString(Server.ProtocolVersionExchange);

                writer.WriteBytes(m_KexInitClientToServer.GetBytes());
                writer.WriteBytes(m_KexInitServerToClient.GetBytes());
                writer.WriteBytes(hostKeyAndCerts);

                writer.WriteMPInt(clientExchangeValue);
                writer.WriteMPInt(serverExchangeValue);
                writer.WriteMPInt(sharedSecret);

                return kexAlgorithm.ComputeHash(writer.ToByteArray());
            }
        }

It literally just writes the data in the right order and uses the KEX algorithm to hash it. The other one is more complex, but very necessary: ComputeEncryptionKey()

        private byte[] ComputeEncryptionKey(IKexAlgorithm kexAlgorithm, byte[] exchangeHash, uint keySize, byte[] sharedSecret, char letter)
        {
            // K(X) = HASH(K || H || X || session_id)

            // Prepare the buffer
            byte[] keyBuffer = new byte[keySize];
            int keyBufferIndex = 0;
            int currentHashLength = 0;
            byte[] currentHash = null;

            // We can stop once we fill the key buffer
            while (keyBufferIndex < keySize)
            {
                using (ByteWriter writer = new ByteWriter())
                {
                    // Write "K"
                    writer.WriteMPInt(sharedSecret);

                    // Write "H"
                    writer.WriteRawBytes(exchangeHash);

                    if (currentHash == null)
                    {
                        // If we haven't done this yet, add the "X" and session_id
                        writer.WriteByte((byte)letter);
                        writer.WriteRawBytes(m_SessionId);
                    }
                    else
                    {
                        // If the key isn't long enough after the first pass, we need to
                        // write the current hash as described here:
                        //      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 || ...
                        writer.WriteRawBytes(currentHash);
                    }

                    currentHash = kexAlgorithm.ComputeHash(writer.ToByteArray());
                }

                currentHashLength = Math.Min(currentHash.Length, (int)(keySize - keyBufferIndex));
                Array.Copy(currentHash, 0, keyBuffer, keyBufferIndex, currentHashLength);

                keyBufferIndex += currentHashLength;
            }

            return keyBuffer;
        }

This is confusing, but the section of the RFC covers it pretty well. Basically, we need to keep going until we get enough bytes for the key size we need. To do this, we loop and recursively hash pieces of the existing hash. The good news is, we are ALMOST there! We just need to send a NEWKEYS message and handle it. So, create a class NewKeys in the Packets folder and inherit from Packet.

    public class NewKeys : Packet
    {
        public override PacketType PacketType
        {
            get
            {
                return PacketType.SSH_MSG_NEWKEYS;
            }
        }

        protected override void InternalGetBytes(ByteWriter writer)
        {
            // No data, nothing to write
        }

        protected override void Load(ByteReader reader)
        {
            // No data, nothing to load
        }
    }

This is a very simple packet. Now change the TODO at the end of the KexDHInit handler to:

        private void HandleSpecificPacket(KexDHInit packet)
        {
            ...
            // Send reply to client!
            KexDHReply reply = new KexDHReply()
            {
                ServerHostKey = hostKey,
                ServerValue = serverKeyExchange,
                Signature = m_PendingExchangeContext.HostKeyAlgorithm.CreateSignatureData(exchangeHash)
            };

            Send(reply);
            Send(new NewKeys());
        }

And add a handler for NewKeys:

        private void HandleSpecificPacket(NewKeys packet)
        {
            m_Logger.LogDebug("Received NewKeys");

            m_ActiveExchangeContext = m_PendingExchangeContext;
            m_PendingExchangeContext = null;
        }

All we do is swap the pending exchange context and make it the active exchange context, then clear the pending context. OH! CRAP! I almost forgot, we have a lot of TODO comments we need to look at! Let's review the Packet's ReadPacket() method for TODO!

// TODO: Get the block size based on the ClientToServer cipher

We need to find these and actually do it, but to do this, we need to provide the current exchange context among other things! After thinking about this, I think it's best to refactor this method over to the Client class to handle. This is a big change. I recommend you review the commit 927e907 for differences! Sorry about that refactor, but the code will thank us later.

A few things to call out from the commit:

I found a problem with the TripleDESCBC provider. The CryptoStream didn't work when called a second time. Some Crypto providers have state, so flushing and closing the stream must cause issues. I have fixed this by calling TransformBlock directly.

DiffieHellmanGroup14SHA1 had a few issues with the way to converted BitIntegers to bytes and back. I fixed this up in the refactor.

Client saw the most changes as I moved the Packet parsing into there, and implemented most of the TODO blocks to Decrypt and Decompress as necessary. I also moved the Send Packet logic into here and wired up the Encrypt and Compress methods as necessary. You will also see Packet Sequence numbers being tracked. These are necessary for the MAC checking. Everytime the server sends a packet, it increases it's sent sequence number. Every time the server receives a packet it increments the received sequence number.

Now, however, when we run the server and connect with OpenSSH!

...
dbug: 127.0.0.1:17263[0]
      Received Packet: SSH_MSG_KEXDH_INIT
dbug: 127.0.0.1:17263[0]
      Received KexDHInit
dbug: 127.0.0.1:17263[0]
      Received Packet: SSH_MSG_NEWKEYS
dbug: 127.0.0.1:17263[0]
      Received NewKeys

We received the NewKeys message, this means we swapped in our new algorithms. What you don't see is, the client sent us another packet, and we did read it correctly. If we hadn't, we would have shown an error and disconnected! And OpenSSH is saying:

debug1: expecting SSH2_MSG_KEXDH_REPLY
debug3: receive packet: type 31
debug1: Server host key: ssh-rsa SHA256:HMfYoW55M+82Gm0u7ORH/aMOng2fQvBVY1sROeeBQUI
...
debug3: load_hostkeys: loaded 1 keys from localhost
debug1: Host 'localhost' is known and matches the RSA host key.
...
debug2: bits set: 1003/2048
debug3: send packet: type 21
debug2: set_newkeys: mode 1
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug3: receive packet: type 21
debug2: set_newkeys: mode 0
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS received
...
debug3: send packet: type 5

So clearly, it got our message with our identification AND it received our NEWKEYS, then it sent us a packet type 5 (SSH_MSG_SERVICE_REQUEST). Sorry I wasn't able to keep this section cleaner and shorter and if you get confused, let me know. The source for this checkpoint is tagged Handling_SSH_MSG_KEXDH_INIT. Believe it or not, we are pretty much done! We have received an encrypted packet and decoded it successfully! However, we should probably send a reply back to the client to at least decline all services for now. We should also clean up the rest of our TODOs so we can better support the protocol. In the next section we'll wrap up.