Open SSH key formats

We can start by looking in the .ssh/authorized_keys file. This is the ssh-dss format:

ssh-dss AAAAB3NzaC1kc3MAAACBA...x= userid

The AAAAB3NzaC1kc3M simply encodes "7 characters ssh-dss" in base 64

The RSA1 format has key length, a prime and the key as digits:

 1024 37 1234567......1234 userid

This format was used in the original ssh version 1.

The current default format (as of Aug 2015) is an ssh-rsa key

ssh-rsa AAAAB3NzaC1yc2EAAAABIwA...x= userid

The AAAAB3NzaC1yc2E encodes "ssh-rsa"

The Ed25519 Elliptic curve keys:

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIBc....je userid@host

The NIST p-256 (FIPS 186 standard) Elliptic curve keys:

ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAA....8= userid@host

Elliptic curve ECDH has the same weakness has the DSA if the random number generator is bad.

To answer the question of which type of key to use, there are several factors. DSA keys used to work on all versions of ssh but they have known weaknesses and are being phased out. There is a known weakness if the hosts random number generator is broken. DSA keys must be 1024 bits which is considered the minium size for that type of key today. Best practice at this point is to use a 2048 or 4096 bit RSA key. Note that other key sizes work too and SSH is happy with a 2049 bit RSA key.

OpenSSH Version 7.0 migration

ssh -oPubkeyAcceptedKeyTypes=+ssh-dss -i some-dss-key hostname

For the sshd server:

-oPubkeyAcceptedKeyTypes=+ssh-dss
/home/src/archive/openssh-7.0p1/sshd -oPubkeyAcceptedKeyTypes=+ssh-dss

Then look in the logs:

grep sshd sshlog | grep Accepted | grep DSA | sed s/.*\ for\ // | sed s/\ from\ .*// | sort -u

What size are the keys?

Bad common and well known DH primes

For example, https://www.ssllabs.com/ssltest gave this wrning:
Uses common DH primes Yes Replace with custom DH parameters if possible

The solution is simple:
$ cd apache_1.3.42/src/modules/ssl
perl ssl_engine_dh.c
cd ../../.. && make && make install

With other code, look for the function "static DH *get_dh1024()" and see if it was generated with "openssl dh -noout -text -in dh1024.pem; openssl dh -noout -C -in dh1024.pem"