012: Implement diffie hellman group14 sha1

Let's start by creating a generic interface for all of our algorithms called IAlgorithm at the root of the project.

    public interface IAlgorithm
    {
        string Name { get; }
    }

This means all of our algorithms can and will have a Name property. Now create a folder to hold our "KexAlgorithms". In this folder, let's create a public interface called IKexAlgorithm.

    public interface IKexAlgorithm : IAlgorithm
    {
        byte[] CreateKeyExchange();
        byte[] DecryptKeyExchange(byte[] keyEx);
        byte[] ComputeHash(byte[] value);
    }

This makes our all of our KEX algorithms have these 3 methods. Now create a class called DiffieHellmanGroup14SHA1 and implement the IKexAlgorithm interface:

    public class DiffieHellmanGroup14SHA1 : IKexAlgorithm
    {
        public string Name
        {
            get
            {
                throw new NotImplementedException();
            }
        }

        public byte[] ComputeHash(byte[] value)
        {
            throw new NotImplementedException();
        }

        public byte[] CreateKeyExchange()
        {
            throw new NotImplementedException();
        }

        public byte[] DecryptKeyExchange(byte[] keyEx)
        {
            throw new NotImplementedException();
        }
    }

It currently does nothing, but it is ready to be filled in with specific behavior. RFC 3526 covers the basic diffie-hellman algorithms and constants used for generating keys. The implementation looks like this:

    public class DiffieHellmanGroup14SHA1 : IKexAlgorithm
    {
        // http://tools.ietf.org/html/rfc3526 - 2048-bit MODP Group
        private const string MODPGroup2048 = "00FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF";
        private static readonly BigInteger s_P;
        private static readonly BigInteger s_G;

        private readonly BigInteger m_Y;

        private readonly SHA1 m_HashAlgorithm = SHA1.Create();

        // The following steps are used to exchange a key. In this:
        //    C is the client
        //    S is the server
        //    p is a large safe prime (RFC 3526)
        //    g is a generator (RFC 3526)
        // For a subgroup of GF(p); q is the order of the subgroup; V_S is S's
        // identification string; V_C is C's identification string; K_S is S's
        // public host key; I_C is C's SSH_MSG_KEXINIT message and I_S is S's
        // SSH_MSG_KEXINIT message that have been exchanged before this part
        // begins.

        public string Name
        {
            get
            {
                return "diffie-hellman-group14-sha1";
            }
        }

        static DiffieHellmanGroup14SHA1()
        {
            //    p is a large safe prime (RFC 3526)
            s_P = BigInteger.Parse(MODPGroup2048, NumberStyles.HexNumber);

            //    g is a generator (RFC 3526)
            s_G = new BigInteger(2);
        }

        public DiffieHellmanGroup14SHA1()
        {
            // 2. S generates a random number y (0 < y < q) 
            var bytes = new byte[80]; // 80 * 8 = 640 bits
            RandomNumberGenerator.Create().GetBytes(bytes);
            m_Y = BigInteger.Abs(new BigInteger(bytes));
        }

        public byte[] CreateKeyExchange()
        {
            //  and computes: f = g ^ y mod p.
            BigInteger keyExchange = BigInteger.ModPow(s_G, m_Y, s_P);
            byte[] key = keyExchange.ToByteArray();
            if (BitConverter.IsLittleEndian)
                key = key.Reverse().ToArray();

            return key;
        }

        public byte[] DecryptKeyExchange(byte[] keyEx)
        {
            // https://tools.ietf.org/html/rfc4253#section-8
            // 1. C generates a random number x (1 < x < q) and computes
            //    e = g ^ x mod p.  C sends e to S.

            // S receives e.  It computes K = e^y mod p,
            if (BitConverter.IsLittleEndian)
                keyEx = keyEx.Reverse().ToArray();

            BigInteger e = new BigInteger(keyEx.Concat(new byte[] { 0 }).ToArray());
            byte[] decrypted = BigInteger.ModPow(e, m_Y, s_P).ToByteArray();
            if (BitConverter.IsLittleEndian)
                decrypted = decrypted.Reverse().ToArray();

            return decrypted;
        }

        public byte[] ComputeHash(byte[] value)
        {
            // H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)
            return m_HashAlgorithm.ComputeHash(value);
        }
    }

Now, let's add a few thing to the Server class:

    public class Server
    {
        ...
        public static IReadOnlyList<Type> SupportedKexAlgorithms { get; private set; } = new List<Type>() 
        { 
            typeof(DiffieHellmanGroup14SHA1) 
        };
        ...
        public static IEnumerable<string> GetNames(IReadOnlyList<Type> types) 
        { 
            foreach (Type type in types) 
            { 
                IAlgorithm algo = Activator.CreateInstance(type) as IAlgorithm; 
                yield return algo.Name; 
            } 
        } 
        ...
    }

This holds a list of supported types for the KEX algorithms, and a way to retrieve the list of names for a given type. Now, we update the Client code to provide this to the connected client.

    m_KexInitServerToClient.KexAlgorithms.AddRange(Server.GetNames(Server.SupportedKexAlgorithms));

Now, when we run, we don't see any difference in the Server log, but we do see a difference in the OpenSSH client debug:

...
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: diffie-hellman-group14-sha1
...
debug1: kex: algorithm: diffie-hellman-group14-sha1
debug1: kex: host key algorithm: (no match)
Unable to negotiate with 127.0.0.1 port 22: no matching host key type found. Their offer:

They received our offer and support of the diffie-hellman-group14-sha1 algorithm and selected it! Sadly, they stopped because they don't see a matching host key algorithm. The code to this point can be seen at tag Add_Diffie_Hellman_Group14_SHA1. In the next section, we'll add our ssh-rsa host key algorithm support.