OpenSSH supports using different key types. For the current protocol version 2 the supported key types are:
OpenSSH version 5.7 and newer support additionally:
In April 2006 Debian added a patch to OpenSSL to fix valgrind errors (#363516). In May 2008 it was discovered that this patch caused a weak Random Number Generator (RNG) due to almost no entropy in the pool. Having such a weak RNG limited the amount of possible different key generations to such a minimum that, in the case of OpenSSH to less than 32‘000, a simple brute force attack with all possible keys is rather quickly to acchieve.
Since OpenSSL is reused in other projects, keys affected by this include OpenSSH, OpenVPN, DNSSEC and more. Notably GnuPG was not affected.
For more information see:
RSA keys rely only during key generation on a strong RNG. Therefore any RSA keys created with a vulnerable OpenSSL version need to be replaced with ones created from a fixed OpenSSL version. RSA keys can be easily checked against a blacklist of vulnerable keys and in the case of OpenSSH, authentication attempts be rejected. In Debian this is done through the openssh-blacklist package. Individual keys can be checked with the ssh-vulnkey program.
DSA keys rely both during key generation and key usage (signing) on a strong RNG. The same procedure for RSA keys applies to any DSA keys created with a vulnerable OpenSSL version too. Additionally, from a system administration point, it is not possible to ensure that existing non-vulernable DSA user keys are not used on vulnerable systems. It is enough to get a signature made from a non-vulnerable DSA key on a system with a vulnerable OpenSSL version to compute the private key. Therefore, all DSA keys should be considered to be vulnerable.
ECDSA does not suffer from the OpenSSL vulnerability. There are issues with it from time to time as it is a rather newly implemented algorithm (e.g. CVE-2008-5077, CVE-2011-1945). There are several rumours that NSA has subverted EC-based algorithms (FIXME: add links to the usual suspects). Dan Bernstein and Tanja Lange have presented their own curve (Curve25519) which has been adopted by OpenSSH and others. However, it remains to be seen if this curve has been proberly choosen and implemented.
We recommend to:
OpenSSH supports using different key sizes. For the current protocol version 2 the supported key sizes are:
OpenSSH version 5.7 and newer support additionally:
FIXME