SSH Key Done Right

Sometimes there is a time when we need a SSH key. Either to connect to a server or to use some git services to store our project's code. So let's try and create one!

A command ssh-keygen has many algorithms that we can choose from (DSA, ECDSA, ECDSA-SK, Ed25519, Ed25519-SK or RSA) but not every one of them is the best choice from a security point of view. We will explain a little the most used algorithm - RSA and a newer modern alternative - Ed25519.

RSA

RSA is an asymmetric algorithm developed in 1977 by three mathematicians - Ron Rivest, Adi Shamir, and Leonard Adleman. The name RSA is derived from the first letter of each mathematician's last name and algorithm is based on prime numbers. How this algorithm works and how the value is calculated is a different story for another article. The strength of the key is defined by the number of bits used. Thanks to technological advancement, in 2009, Benjamin Moody was able to factor 512-bit key in 73 days and later in 2010 researches were able to factor 768-bit key. So the number of bits used for a key needs to be increased from time to time. Also the longer the key, the more resources are needed to generate a key or to encrypt data with that key.

It is considered secure enough when using a SHA256 or SHA512 signatures and at least 3072-bit key. RSA key with 2048-bit key was a standard and a default for a long time, but becomes less and less secure in the long run and thus lower bit keys should be avoided. Even ssh-keygen command by default uses 3072-bit key since its 8.0 release in 17 Apr. 2019. Here is an example of RSA key generation:

                # Generates RSA 4096-bit key with a SHA-512 signature

ssh-keygen -t rsa -b 4096 -f my_key_id_rsa

The output of this command are two files: my_key_id_rsa and my_key_id_rsa.pub. A public key is a file with an extension .pub which can be added to git services like github or bitbucket or uploaded to a server with a command ssh-copy-id.

Ed25519

A newer algorithm is becoming more and more popular and is called Ed25519, which stands for Edwards-curve Digital Signature Algorithm based on 255-bit elliptic curve called Curve25519. It's a more modern, secure and efficient algorithm used also in other modern software like wireguard vpn. In comparison with other algorithms, this one has many advantages. For example:

fast single-signature verification
fast signing
fast key generation
high security level (has similar difficulty to breaking RSA with approx. 3000-bit keys)
small signatures and small keys

More information can be found in this official paper. Here is an example of Ed25519 key generation:

                # Generates Ed25519 key with a round of 100
# By default 16 rounds are used. More rounds
# mean slower verification but increased
# resistance to brute-force cracking

ssh-keygen -t ed25519 -a 100 -f my_key_id_ed25519

Conclusion

If a server or git service supports it, you can use Ed25519 key as it is fast, secure enough and has much shorter keys. It is still new but from time to time, some older software may have problem with it. Otherwise I would use RSA with 4096-bit key as an alternative.