What's the most computationally expensive step in a SSH2 session?

I'm trying to figure out what exactly uses the most CPU in a SSH2 key-exchange/authentication/session initialization. I'm optimizing it for an embedded CPU,开发者_开发百科 and currently session initialization seems to be the biggest bottleneck. Specifically, I'm using dropbear server with RSA keypair. Does RSA or one of its parts require significant CPU power?

Thanks!

---

The three most expensive operations in a SSH2 key exchange are (on the server):

• The Diffie-Hellman key exchange.
• The RSA signature dynamically computed by the server.
• The verification on the signature which has been dynamically computed by the client (in case the client uses an asymmetric key pair to authenticate itself).

The third operation is made much faster is the client uses a RSA key pair: RSA signature verification is very fast, whereas DSA signature verification is expensive (actually somewhat more expensive than DSA signature generation).

The DH is done over one of two groups, called diffie-hellman-group1-sha1 and diffie-hellman-group14-sha1 in the SSH specification (section 8). The latter uses a 2048-bit modulus, whereas the former sticks to a 1024-bit modulus. It is expected that the bigger modulus implies a DH cost between 4 and 8 times bigger than the smaller. However, 1024-bit DH is deemed to be about as secure as 1024-bit RSA, and, as such, not recommended for long-term security (and in SSH, the DH is used to obtain the actual encryption key; hence, you want the DH to resist for as lng as the data which was exchanged through the SSH connection must remain confidential).

Similarly, RSA signature generation cost is mostly cubic in the key size: a 2048-bit RSA signature generation takes about 8 times the CPU than what a 1024-bit RSA signature generation requires. A DSA signature generation could be somewhat faster than a RSA signature generation (maybe up to twice faster).

So the recommendations for faster standard SSH2 server operation would be:

• use diffie-hellman-group1-sha1 for key exchange (if you can tolerate the not optimal security);
• use a DSA key for the server;
• use a RSA key for the client.

Some SSH implementations (in particular newer versions of OpenSSH) support ECDSA signatures, and may use ECDH (Diffie-Hellman on an Elliptic Curve) instead of plain DH. ECDSA and ECDH should be way faster than, respectively, DSA and DH. Moreover, ECDSA and ECDH over a 256-bit elliptic curve should achieve proper long-term security. In OpenSSH, you select such a curve for ECDH by setting the KexAlgorithms server option to ecdh-sha2-nistp256; and ssh-keygen -t ecdsa -b 256 will produce an ECDSA key pair on the same curve.

So the recommendation for faster OpenSSH server operation are:

• use ecdh-sha2-nistp256 for key exchange;
• use a 256-bit ECDSA key pair for the server;
• use a RSA key for the client.

For faster client operation, reverse the conditions on client and server key pairs.