Key exchange is slow when size of group is more than 1024 bits

[ignas-sakalauskas-cko]

Hello,

I am using .Net Core 2.0 and running local WinSCP SSH server.

Code to replicate the issue below.

using (var client = new SftpClient(host, username, password))
{
   var start = DateTime.Now;
   client.Connect();
   Console.WriteLine($"Time elapsed: {DateTime.Now.Subtract(start).Seconds} s");
}

And the result is Time elapsed: 5 s

SSH clients like WinSCP or FileZilla connect to the server instantly.

After digging into SSH.NET code seems like _prime.BitLength is 8192, hence BigInteger.ModPow runs while loop 8191 times, twice during Connect().

Please advise.

Thanks,
Ignas

UPDATE.
Tested several remote servers, and results were very different.
localhost: "hmac-sha1" time: 5s
test.rebex.net: "hmac-sha2-256" time: 1s
demo.wftpserver.com: "hmac-sha1" time: 2-3s

Using a different local server seems to work as expected, Connect() takes under 500 ms.

[drieseng]

The size of the private component that we generate is based on the size of the (safe) prime that the server generated. This greatly affects the time it takes to create our public key component.

In case of WinSCP, I suppose the prime they generate is 8192 bit.

I'll modify our key exchange implementation to use twice the size of the hash that a given algorithm produces as size of the private component, with a minimum of 1024 bits.

[drieseng]

@ignas-sakalauskas-cko I've commited a fix to the develop branch.
Would it be possible for you to build SSH.NET from source, and confirm that it fixes the problem for you?

[ignas-sakalauskas-cko]

Thanks for the quick response @drieseng! Connection time now averages to about 3s (local WinSCP SSH server), which is a great improvement. However, ideally the connection time should be under a second. Do you think it's feasible?

[drieseng]

On a Windows machine with the MS port of OpenSSH (x64) - which generates a 8192 bit prime - the connection is now established in about 700 ms (vs. 1xx ms when connecting to an older version of OpenSSH on Linux which still generates a 1024 bit prime).

We send a SSH_MSG_KEY_DH_GEX_REQUEST with a 1024 bit minimum and preferred group size, and 8192 bit maximum group size. Apparently newer versions of OpenSSH generate a group of the maximum size.

Since my commit, we generate a 1024 bit private exponent (instead of 8192 bit). If someone with more expertise on the matter can confirm that we can go lower, I'll be happy to update our implementation accordingly.

[drieseng]

@ignas-sakalauskas-cko Are you sure you compiled in release mode?

[drieseng]

In release mode, establishing the connection takes about 4500 ms before my changes and 700 ms after. Please confirm whether you built SSH.NET in debug mode.

[drieseng]

@tmds Can you give your view on this fragment from RFC 4419:

To increase the speed of the key exchange, both client and server may reduce the size of their private exponents. It should be at least twice as long as the key material that is generated from the shared secret.

Does this mean that generating a private exponent that is twice the hash size (eg. 2 x 256 bit in case of SHA-256) should be ok?

[ignas-sakalauskas-cko]

@drieseng Sorry, I was using Debug mode. Compiled in Release mode it connects in under 500ms, which is great! The fix works as expected, than you very much! Looking forward to the release!

[drieseng]

@ignas-sakalauskas-cko Glad it works for you. I'll try to release a new beta this weekend. That should be the last one before I consider the 2016.1.0 release stable.