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
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
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-keygensays 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.
*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?
@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).
@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.)
DSA can now be used for encryption: https://www.thesecuritybuddy.com/encryption/dsa-vs-rsa/
Right now the question is a bit broader: RSA vs. DSA vs. ECDSA vs. Ed25519. So:
A presentation at BlackHat 2013 suggests that significant advances have been made in solving the problems on complexity of which the strength of DSA and some other algorithms is founded, so they can be mathematically broken very soon. Moreover, the attack may be possible (but harder) to extend to RSA as well.
The presentation suggests using elliptic curve cryptography instead. The ECC algorithms supported by OpenSSH are ECDSA and, since OpenSSH 6.5, Ed25519.
OpenSSH only supports NIST curves for ECDSA and according to this study those curves look really suspicious for NSA backdoors. And if NSA can already crack it, then it won't be as hard to crack for somebody else as a proper curve would be. Ed25519 is the same thing but with a better curve, so it's the safest bet against the underlying algorithm being mathematically broken.
Also, DSA and ECDSA have a nasty property: they require a parameter usually called k to be completely random, secret, and unique. In practice that means that if you connect to your server from a machine with a poor random number generator and e.g. the the same k happens to be used twice, an observer of the traffic can figure out your private key. (source: Wikipedia on DSA and ECDSA, also this).
The bottom line is:
- Never use DSA or ECDSA.
- Ed25519 is probably the strongest mathematically (and also the fastest), but not yet widely supported. As a bonus, it has stronger encryption (password-protection) of the private key by default than other key types.
- RSA is the best bet if you can't use Ed25519.
Ed25519 doesn't use a random *k* (it derives it from private key and message instead), so you only need a PRNG to generate the key, but not to sign. With DSA and ECDSA many implementations fail is the PRNG is bad, but there are ways to implement it so it survives bad PRNGs, for example by using Pornin's deterministic variant.
The recent discrete logarithm advances were is small characteristic field. There is no obvious way to transfer it to DSA over prime characteristic fields or RSA. RSA and DSA over prime fields are probably closer to each other security wise that DSA over prime fields is to DSA over small characteristic fields. Advances in factoring or DL can happen, but they'll need to go far beyond the recent advances, so abandoning DSA and/or RSA over these is unnecessary alarmism. It's just as well possible that somebody breaks ECC.
Yes, it bothers me to hear anyone say 'abandon DSA'. I'm not a mathematician, nor are most users of public key cryptography, but I'd only abandon something if there were a truly imminent threat to it, and certainly wouldn't adopt something relatively new until it had been extensively field-tested and proven to be secure. How do we know this user isn't the NSA saying that the NSA can more easily break DSA and ECDSA, so that we switch to algorithms they can break. Oh, those pesky intelligence agencies, they will blow your mind!
@bitsum The RNG issue is real and "imminent." OpenSSH can only generate 1024 bit DSA keys, which are too weak. While it can use 2048 and 3072 bit keys generated by OpenSSL, that's a lot of hassle. Also, as of OpenSSH 7.0, DSA is disabled by default. See also my Stack Overflow answer. Want tried-and-true? Use 4096 bit RSA.
In SSH, on the client side, the choice between RSA and DSA does not matter much, because both offer similar security for the same key size (use 2048 bits and you will be happy).
Historically, version 1 of the SSH protocol supported only RSA keys. When version 2 was defined, RSA was still patented, so support of DSA was added, so that an opensource patent-free implementation could be made. RSA patent expired more than 10 years ago, so there is no worry now.
Theoretically, in some very specific situations, you can have a performance issue with one or the other: if the server is a very small machine (say, an i486), it will prefer clients with RSA keys, because verifying a RSA signature is less computationally expensive than verifying a DSA signature. Conversely, a DSA signature is shorter (typically 64 bytes vs 256) so if you are very short on bandwidth you would prefer DSA. Anyway, you will have a hard time detecting those effects, let alone find them important.
On the server, a DSA key is preferred, because then the key exchange will use a transient Diffie-Hellman key, which opens the road for "Perfect Forward Secrecy" (i.e. if a bad guy steals the server private key, he still cannot decrypt past connections that he would have recorded).
@jrdioko: when connecting, a session key is established, using a key exchange mechanism such as RSA (encryption) or Diffie-Hellman. A corresponding private key is used on the server. If that key is transient (generated on-the-fly, kept in RAM only, discarded after usage), then it is safe against subsequent stealing. When the server key (the one which is permanent, stored in a file) is for signatures only (e.g. DSA key), then you are sure that the key exchange key is transient (the public key is then signed by the server), and that's good.
@Paŭlo: actually, with SSHv2, DHE is always used, even with a RSA key. Using a DSA key is just an easy way to be sure of getting PFS, because it cannot be used otherwise.
Another important advantage of RSA over both DSA and ECDSA is that you don't ever need a secure random number generator to create signatures.
To generate a signature, (EC)DSA needs a value that has to be random, secret/unpredictable and can never be used again. If one of those properties is violated, it's possible to trivially recover the private key from one or two signatures.
This has happened before (once with a broken patch of the OpenSSL PRNG in Debian, and once with a bug in Android's SecureRandom implementation), and is pretty hard to completely prevent.
With RSA, in those situations only your ephemeral session key would have been compromised, if the actual authentication key pairs have been created using a properly seeded PRNG before.
Theoretically, there is a way to make (EC)DSA signatures depend on the message and private key, which can avoid total failure in case of a broken RNG, but until this gets integrated into your SSH client (there is no OpenSSL release version including the patch right now), I'd definitely go with RSA keys.
That advantage you talk about - we all know now that the RSA random number generator is not that random. I don't know if it matters much, but anyway...
Not knowing much about cryptography, as a OpenSSH user I would stick to a simple fact: in http://www.openssh.com/legacy.html, which states that SHA1 is now disabled by default because it is considered weak:
OpenSSH 7.0 and greater similarly disables the ssh-dss (DSA) public key algorithm. It too is weak and we recommend against its use.
Tom Leek explained that in “Why OpenSSH deprecated DSA keys”: simply put, it is a consequence of their own coding practice and inability to stay on par with the current standards.
RSA and DSA are two completely different algorithms. RSA keys can go up to 4096 bits, where DSA has to be exactly 1024 bits (although OpenSSL allows for more.) According to Bruce Schneier, "both DSA and RSA with the same length keys are just about identical in difficulty to crack."
The math might not matter. This thread seems pre-Snowden. Here is a Reuters article dated December 20, 2013:
(Reuters) - As a key part of a campaign to embed encryption software that it could crack into widely used computer products, the U.S. National Security Agency arranged a secret $10 million contract with RSA, one of the most influential firms in the computer security industry, Reuters has learned.
Documents leaked by former NSA contractor Edward Snowden show that the NSA created and promulgated a flawed formula for generating random numbers to create a "back door" in encryption products, the New York Times reported in September. Reuters later reported that RSA became the most important distributor of that formula by rolling it into a software tool called Bsafe that is used to enhance security in personal computers and many other products.
Undisclosed until now was that RSA received $10 million in a deal that set the NSA formula as the preferred, or default, method for number generation in the BSafe software, according to two sources familiar with the contract. Although that sum might seem paltry, it represented more than a third of the revenue that the relevant division at RSA had taken in during the entire previous year, securities filings show.
During this Science Friday podcast Ira asks Matt Green, Martin Hellman (inventor of Public Key Cryptography), and Phil Zimmerman (creator of PGP) what they think the NSA has cracked:
Ira: What are some of the things that we know that the NSA has broken into?
Matt: So we have heard a number of things that we can probably credit for real. … random number generators … we know that NSA through NIST … has very likely put back doors in some of those standard algorithms that allow them to essentially break those systems entirely.
Ira: You mean the NSA created those back doors?
Matt: That's exactly right. So NIST works with NSA --- and they're required to by law. We thought NSA was helping NIST by developing more secure standards for Americans to use. We now suspect --- and have strong evidence to believe --- that the situation was exactly the opposite; that NIST was being used to put out standards that the NSA could break.
Considering these recent revelations the strength of the algorithms seems largely irrelevant. RSA appears to have been a private company somehow bought by the NSA, and DSA was created by NIST itself, which, according to these experts is largely a front for NSA crypto research.
In other words, it really doesn't matter if you are using the random number generators that come with pretty much any modern computer, which OpenSSH and others do.
Pick the one that is the fastest for what you want. In my case, I reuse the same key for a lot of stuff so DSA's faster generation speed is less desirable. Also, maybe there is some wild chance that RSA was actually an independent entity from NIST and NSA, whereas we know DSA was created by NIST.
I personally just use 1028 bit keys because, as we've seen, it really doesn't matter unless someone is placing some requirement on you who still believes bigger keys will protect you. The whole thing is largely just an annoyance to anyone seeking to break in.
Fair enough. I've added the relevant quotes and transcribed some of the audio. Thanks for the reminder.
Your answer is not entirely consistent. You're mixing facts about a RNG developed by the company RSA which seems was tampered, and about the public/private key algorithms called RSA (developed by the founders of the mentioned above company). The RSA algorithm (with big enough keys) cannot be easily broken unless you have a monster optimised cluster or a quantum computer. As for DSA, this might be published by NIST (I haven't checked) but NIST publication are also peered reviewed by other independant cryptographers. For example they warned about the dubious RNG approved by NIST.
The fact that RSA Inc's BSAFE product used Dual EC DRBG as the *default* (not even the only one offered) random-number generator has *nothing whatsoever* to do with the security properties of the RSA *algorithm* or the security properties of any software that was not or is not built to use BSAFE. If you are going to throw conspiracy theories around, at least get your facts right. There's plenty enough to blame the NSA (and many other intelligence agencies around the world) for, and there's good reason to blame RSA for the default, without need for making claims that have no basis in reality.
The problem with ECDSA is not so much backdoors. Bernstein/Lange specifically mention that curve cryptanalysis does not attack specific curves, but classes of curves (see slide 6).
The problem with ECDSA is that NIST curves are hard to implement correctly (ie. constant time and with all proper verification) compared to Curve25519. OpenSSL has a constant-time P256 implementation, so OpenSSH is safe in that regard.
If you're still worried about NIST curves, OpenSSH recently added support for the Ed25519 scheme