There was a question RSA vs. DSA for SSH authentication keys asking which key is better. Basically all answers were more in a favour of RSA over DSA but didn't really tell that DSA would be somehow insecure.

Now however DSA was deprecated by OpenSSH and is later going to be entirely dropped: https://www.gentoo.org/support/news-items/2015-08-13-openssh-weak-keys.html

The information states:

Starting with the 7.0 release of OpenSSH, support for ssh-dss keys has been disabled by default at runtime due to their inherit weakness. If you rely on these key types, you will have to take corrective action or risk being locked out.

Your best option is to generate new keys using strong algos such as rsa or ecdsa or ed25519. RSA keys will give you the greatest portability with other clients/servers while ed25519 will get you the best security with OpenSSH.

What makes DSA keys inherently weak?

  • 4
    Possible duplicate of Should DSA keys be considered deprecated? – Steffen Ullrich Feb 4 '16 at 16:26
  • 5
    No, not really a duplicate. The underlying question has not been answered yet. – Tom Leek Feb 4 '16 at 17:24
  • If you really want large DSA keys for ssh, you can generate dsa keys with openssl, with a different bit size (such as 2048 or 3072), then import it into ssh with ssh-keygen. This is nonstandard, but openssh allows it as a client and a server, and I have personally verified interoperability with openssh client and PuTTY as a client, talking to openssh as a server and dropbear as a server. – Brian Minton Aug 20 '19 at 16:32

This is a good question. The dedicated page from OpenSSH only says:

OpenSSH 7.0 and greater similarly disables the ssh-dss (DSA) public key algorithm. It too is weak and we recommend against its use.

which is no more detailed than the "inherit weakness" from the announce. I did not find any published explanation about these weaknesses except some unsubstantiated weaselling that talks of "recent discoveries". Thus, it is time for some sleuthing.

In the source code of OpenSSH-6.9p1 (Ubuntu 15.10 package), for the key generation tool ssh-keygen, I find this remarkable bit of code:

    maxbits = (type == KEY_DSA) ?
    if (*bitsp > maxbits)
            fatal("key bits exceeds maximum %d", maxbits);
    if (type == KEY_DSA && *bitsp != 1024)
            fatal("DSA keys must be 1024 bits");

The OPENSSL_DSA_MAX_MODULUS_BITS is a constant from OpenSSL's headers, that define it to 10000. So the first four lines check that the requested key size, at generation time, can actually be handled by the key generation process. However, the next two lines basically say: "regardless of the test above, if the key is DSA and the size is not 1024, niet."

These 6 lines are, in themselves, a sure sign that whoever developed that code did not completely agree with himself with regards to key sizes. This code was probably assembled incrementally and possibly by different people. The source of the "1024" can be traced to the actual DSA standard (called "DSS" as "Digital Signature Standard"), FIPS 186-4. That standard was revised several times. In its first version, DSA was mandated to use a modulus whose size was between 512 and 1024 bits (and should be a multiple of 64, presumably to simplify the task for implementers). A later version acknowledged the increases in technological power and mathematical advances, and banned any size other than 1024 bits. The modern version of FIPS 186 (the fourth revision, as of early 2016) allows the modulus to have size 1024, 2048 or 3072 bits.

It can thus be surmised that ssh-keygen refuses to use a modulus size different from 1024 bits because someone, at some point, read the then-current FIPS 186 version that mandated exactly that, and nobody bothered to update ssh-keygen when the FIPS standard was amended. Regardless of how this spectacular piece of programming schizophrenia came to be, the raw result is that most if not all SSH keys of type DSA in use today rely on a 1024-bit modulus.

The next piece of the puzzle is the Logjam attack. Logjam is basically about noticing that when a client and server agree to use weak crypto, they can be attacked. This is an attack on SSL/TLS, not SSH. However, the Logjam article does not stop at (rightfully) bashing SSL/TLS implementations for using a 512-bit modulus for DH; it also dedicates some talking space to "state-level adversaries". That part mostly says something which was already known, i.e. that breaking discrete logarithm modulo a 1024-bit modulus (something which would allow breaking both DH and DSA) is right now horrifyingly expensive, but not impossible with regards to our current knowledge of the problem and available technology (similar to breaking RSA-1024, and quite unlike breaking a 2048-bit DH or DSA, which are beyond the feasible with current Earth resources).

To receptive ears, this all sounded like "OMG we are all pirated by the NSA !" and the publicity around the Logjam issue (which is very real) trailed in its wake a substantial amount of hysteria on the subject of 1024-bit DSA keys, included when they are used in SSH.

An extra point was that using DSA requires generating, for each signature, a new random value, and the quality of the generation of that value is of paramount importance. Some implementations have failed spectacularly, leading to private key leakage (notably for some "Bitcoin wallets"). This characteristic of DSA is shared with its elliptic-curve version ECDSA. It can be fixed. But it instilled the idea that DSA signatures can be tricky to do properly (and ECDSA signatures equally, but elliptic curves are cool and nobody wants to ban them).

These parameters, taken all together, explain the ban. This can be viewed as a case of OpenSSH developers being proactive in their notion of security and are ready to force users to use strong crypto. Another way of seeing the very same sequence of decisions is that OpenSSH developers blundered badly at some point because of some poor reading of FIPS 186, and then sought to cover it in the equivalent of dumping at sea the corpse of the inconvenient husband.

Note that breaking your DSA key would allow the attacker to impersonate you, but not to decrypt recorded sessions. While it can be said that switching to an ECDSA key would be a good idea at some point (it saves a bit of bandwidth and CPU), there is no cryptanalytic urgency to do so. You will still have to do it, because otherwise you may be locked out of your servers because some packager was too zealous in the deprecation policy.

| improve this answer | |
  • Another possible explanation is that somebody got spooked by the progress on solving DLP over non-prime fields. (Though experts believe that these attacks can't be generalized to the prime fields used in practice.) – CodesInChaos Apr 8 '17 at 20:59
  • 2
    >> Note that breaking your DSA key would allow the attacker to impersonate you, but not to decrypt recorded sessions. << Out of curiosity, should I record a session from handshake to end, what prevents me from decrypting that, once I have the private keys? – dualed Sep 11 '17 at 10:46
  • 6
    @dualed SSH protocol 2 uses Diffie-Hellman for key exchange. The actual session key is generated by both sides at the start of the session and is not stored locally or sent over the communication channel. Knowledge of a private key does not reveal the session key. See How does SSH use both RSA and Diffie-Hellman. – bain Oct 21 '17 at 15:52
  • 4
    I always love answers that dig into the source. It reveals so much more than the documentation about the mindset of the authors! – forest Dec 21 '17 at 1:13

https://bugzilla.mindrot.org/show_bug.cgi?id=1647 has the reasoning behind the restricting DSA keys to 1024 bits, but basically:

  • RFC4253 section 6.6 requires the SHA1 hash (160 bits) for ssh-dss (ie DSA) authentication.
  • FIPS 186-3 section 4.2 requires DSA keys >1024 bits to use a hash stronger than 160 bits.
  • the only way to comply with both is to allow only 1024 bit keys.
| improve this answer | |
  • 1
    186-3 (and -4) 4.2 says 'ordinarily should not' use a hash weaker than L,N and bold 'should' is defined as 'strong recommendation but not a requirement'. 4253 also requires SHA1 for ssh-rsa (regardless of size) but OpenSSH implemented new pkalgs rsa-sha2-256 and rsa-sha2-512 two years before rfc8338 was published. – dave_thompson_085 Nov 22 '19 at 6:59

186-3 (and -4) 4.2 says 'ordinarily should not' use a hash weaker than L,N

That part says

A hash function that provides a lower security strength than the (L, N) pair ordinarily should not be used.

Above that it says

This Standard specifies the following choices for the pair L and N (the bit lengths of p and q,
L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256
Federal Government entities *shall* generate digital signatures using use one or more of
these choices.

[edit: I went and (re)read NIST SP.800-57. sec 5.6.1. Even if it's permissible to go against the recommendation in FIPS 186-3 and use SHA-1 with a larger DSA key it's not going to be any stronger since it'll still be limited by the strength of the SHA-1]

OpenSSH implemented new pkalgs rsa-sha2-256 and rsa-sha2-512 two years before rfc8338 was published

Those were a draft standard for three years prior to publication as an RFC.

In fact there was originally a dsa-sha2-256 that would have allowed 2k and 3k DSA keys while conforming to FIPS 186-3 but that was pretty quickly dropped. Such a scheme would have also required a software upgrade.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.