Which of 'RSA', 'DSA', 'ECDSA' and 'EdDSA' should be used for SSH public key encryption?

SSH , a protocol for accessing computers remotely, uses public key cryptography to authenticate computers. Public key cryptosystems include ' RSA ', ' DSA ', ' ECDSA ' and ' EdDSA ', and Virag Mody of software company ' Gravitational ' explains each mechanism and 'method suitable for SSH'.

Comparing SSH Encryption Algorithms-RSA, DSA, ECDSA, or EdDSA?
https://gravitational.com/blog/comparing-ssh-keys/

Public key cryptography is an encryption method that uses different keys for encryption and decryption. For example, when Bob and Alice interact, Alice creates a private key and a public key, and passes the public key to Bob. Bob encrypts the message with Alice's public key and sends it to Alice. Upon receiving the encrypted message, Alice decrypts the message with her private key. Since a private key cannot be created from a public key, only Alice with a private key pair can read a message encrypted with Alice's public key. SSH uses this mechanism to perform authentication between computers.

There are 'RSA', 'DSA', 'ECDSA', and 'EdDSA' in public key cryptography, and the encryption methods are different.

◆RSA
Mody explained that

RSA is a public key cryptosystem with a history that appeared in 1977, and it takes advantage of the fact that it is extremely difficult to factorize a semi-prime number with a large number of digits. Specifically, given only 'n', which is the product of two large prime numbers 'p' and 'q', it is possible to factor n into p and q from the beginning. The answer is that there is no one other than the person who 'knows.' By using p and q as the elements of the private key and n as the elements of the public key, a cipher that can derive the public key from the private key but cannot derive the private key from the public key is completed. It is a mechanism.

◆DSA
DSA is a cryptography based on the difficulty of the discrete logarithm problem. The important point of DSA is that it uses a random number 'm' to sign a message with a private key 'k'. m must be kept secret.

◆ECDSA and EdDSA
ECDSA and EdDSA are ciphers that use the difficulty of the discrete logarithm problem like DSA, but ECDSA and EdDSA use elliptic curve cryptography and Edwards curve to reduce the size of the public key.

For each encryption method, Mody evaluates 'whether it is suitable for SSH public key encryption' on the following evaluation axis.

・Implementation: Whether there are many libraries that engineers can handle
Compatibility: Does the SSH client support the cipher?
· Performance: how long it takes for key generation
・Security: Is it possible to generate a private key from a public key?

Because RSA has a long history, libraries are available in major programming languages such as JavaScript, Python, and Go. Regarding compatibility with

OpenSSH, the key using SHA-1 for the hash function and the key whose public key length is less than 2048 bit cannot be used, but the default key length that can be generated with the latest OpenSSL at the time of article creation is 2048 bit. Given that there is a high degree of compatibility. However, as the computational performance of computers has improved, the key length required to ensure security has also increased, and performance has not been evaluated. There are also algorithms for factoring specific integers, such as the quadratic sieving method and the number field sieving method.

DSA is a cipher that appeared in 1994, and the library is as rich as RSA. However, DSA security is not perfect. In DSA, random number m is used as a nonce value that is used once in key generation, but in DSA, since this m needs to be kept secret, the nonce value that should be disposable is similar to the key in nature. thing. Moreover, it is difficult to generate a perfect random number, and a value having a certain law may be used as m due to a program implementation error, so the cipher may be broken through the analysis of m. For this reason DSA is disabled by default from OpenSSH 7.0

ECDSA has a smaller key length than DSA, but security is not improved. In contrast to ECDSA, EdDSA does not generate random nonce values but rather as a hash to increase the strength against collisions. Since EdDSA is a relatively new encryption, it is inferior in implementation and compatibility compared to RSA and DSA, but it has high performance and security, and the public key infrastructure industry is gradually moving to EdDSA. Mody points out.

Finally, Mody recommends RSA with a public key length of 2048bit or 4096bit when emphasizing implementation and compatibility, and EdDSA when emphasizing performance or security. We are calling for not to use DSA or ECDSA.

in Software,   Security, Posted by darkhorse_log