RSA vs. DSA for SSH authentication keys

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).

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.

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."

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 only ECC algorithm supported by OpenSSH is ECDSA, so that's the safest bet against the underlying algorithm being mathematically broken.

However, 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.

Also, both DSA and ECDSA have a nasty property: they requires 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.
• RSA is the best bet, at least until OpenSSH implements better curves, such as Ed25519.
• Don't use ECDSA just yet. You might get stronger-than-RSA encryption out of it someday, when OpenSSH implements better curves. But even then you'd have to use a really really good random number generator at all times and change keys often, before the k parameter happens to repeat itself even once.

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 (I can't post the link due to reputation)