RSA vs. DSA for SSH authentication keys

  • When generating SSH authentication keys on a Unix/Linux system with ssh-keygen, you're given the choice of creating a RSA or DSA key pair (using -t type).

    What is the difference between RSA and DSA keys? What would lead someone to choose one over the other?

    @Bhanu The default of `ssh-keygen` from OpenSSH 6.3p1 is 2048 bits. Read the answers below, and you will also find out that 2048 bits is sufficient.

    Really, I don't see why the suggestion is to "choose the fastest key." I would think one would want to choose the slowest key, which would take the longest time to crack; given that authentication is really only done once and one can wait for authentication to complete for the "realtime" time that it takes for a function.

    The reason we have DSA is that RSA used to have patents before. So DSA was implemented in open source tools. Now all the patents of RSA have expired. So no practical advantage to use DSA over RSA. tools retain the support for backwards compatibility and there is no reason to remove as it is also one of good crypto

  • emboss

    emboss Correct answer

    9 years ago

    Go with RSA.

    DSA is faster for signature generation but slower for validation, slower when encrypting but faster when decrypting and security can be considered equivalent compared to an RSA key of equal key length. That's the punch line, now some justification.

    The security of the RSA algorithm is based on the fact that factorization of large integers is known to be "difficult", whereas DSA security is based on the discrete logarithm problem. Today the fastest known algorithm for factoring large integers is the General Number Field Sieve, also the fastest algorithm to solve the discrete logarithm problem in finite fields modulo a large prime p as specified for DSA.

    Now, if the security can be deemed as equal, we would of course favour the algorithm that is faster. But again, there is no clear winner.

    You may have a look at this study or, if you have OpenSSL installed on your machine, run openssl speed. You will see that DSA performs faster in generating a signature but much slower when verifying a signature of the same key length. Verification is generally what you want to be faster if you deal e.g. with a signed document. The signature is generated once - so it's fine if this takes a bit longer - but the document signature may be verified much more often by end users.

    Both do support some form of encryption method, RSA out of the box and DSA using an El Gamal. DSA is generally faster in decryption but slower for encryption, with RSA it's the other way round. Again you want decryption to be faster here because one encrypted document might be decrypted many times.

    In commercial terms, RSA is clearly the winner, commercial RSA certificates are much more widely deployed than DSA certificates.

    But I saved the killer argument for the end: man ssh-keygen says that a DSA key has to be exactly 1024 bits long to be compliant with NIST's FIPS 186-2. So although in theory longer DSA keys are possible (FIPS 186-3 also explicitly allows them) you are still restricted to 1024 bits. And if you take the considerations of this [article], we are no longer secure with 1024 bits for either RSA or DSA.

    So today, you are better of with an RSA 2048 bit key.

    Sorry, you got it wrong on several points. DSA is defined in a finite field of size _p_ where _p_ is a big prime integer, _not_ a power of 2. With regards to discrete logarithm, a finite field of size _2^1024_ is weaker than a finite field of size _p_, with a specific algorithm (designed by Coppersmith) which is faster than Index Calculus. The current FIPS 186 is FIPS 186-3, and this one allows DSA keys longer than 1024 bits (and `ssh-keygen` can make 2048-bit DSA keys). In the case of SSH (client side) there is no question of encryption, only signatures.

    Although FIPS-3 does allow larger key lengths, current ssh-keygen (Fedora 15) does *not* -> ssh-keygen -t dsa -b 2048 -> DSA keys must be 1024 bits. Although SSH does just involve signatures I think it's still relevant to point out the difference. You're right about DSA being defined on Zp, I will change that. Thanks for your remarks!

    oh yes, `ssh-keygen` currently refuses DSA keys longer than 1024 bits. But there used to be a version (as integrated in OpenBSD) which allowed larger DSA keys.

    @Thomas, it's called `openssl gendsa`. (The key format is the same.)

    *DSA [...] is faster when decrypting* is not quite right: DSA can only sign/validate, there is no encryption build in.

    @emboss:I don't understand this answer.DSA is NOT an encryption scheme.It is a signature validation scheme

    The link to the article which explains why 1024 bits is insufficient appears to be missing. Can you please, provide one as I was interested in why?

    Is this still true at the end of 2014?

    @emboss If you are calling the OpenSSL library directly in your program, you can actually get DSA with higher than 1024 bits.

    @pablox pretty much yeah, the more paranoid will use 4096 bit RSA keys. ed25519 (see Shnatsel's answer) may be an option for some but it will likely be a few more years before one can confidently assume that every host they want to access supports it.

    There's also the GnuPG about why RSA 4096 is not the default (https://www.gnupg.org/faq/gnupg-faq.html#no_default_of_rsa4096). It basically goes down to: "Because it gives us almost nothing, while costing us quite a lot.".

    As for generating DSA keys bigger than 1024, PuTTY's PuTTYgen tool can also generate DSA keys of arbitrary size. I just generated a 20480 bit SSH-2 DSA key. Actually, I'm in the middle of doing so. It seems to be taking a while (as in, about 20 minutes and still going).

    @PaŭloEbermann what do you mean DSA can only sign/validate?

    @jayarjo Yes, DSA is not an encryption algorithm, only a signature one. (There are encryption algorithms based on related mathematics, e.g. ElGamal, but they are not DSA.)

License under CC-BY-SA with attribution


Content dated before 6/26/2020 9:53 AM