Bug 3219

According to RFC 4253, "There MAY be multiple host keys for a host, possibly 
with different algorithms." (https://tools.ietf.org/html/rfc4253#section-7.1)

It is possible to connect using all keys that are using different algorithms 
(e.g. you can use ecdsa-sha2-nistp256 and ecdsa-sha2-nistp521 at the same 
time). It also seems to be possible to *specify* multiple keys of the same 
type (e.g. two ecdsa-sha2-nistp256 keys). But in the latter case, I couldn't 
connect using any key except the first one that was specified in configuration.

To reproduce, run

    $ rm ~/.ssh/known_hosts
    $ cd /etc/ssh/
    $ ssh-keygen -t rsa -f ssh_host_rsa_key_2
    $ `which sshd` -ddd -p 23 \
          -oHostKey=/etc/ssh/ssh_host_rsa_key \
          -oHostKey=/etc/ssh/ssh_host_rsa_key_2 

Note that both keys are loaded:

    debug1: private host key #0: ssh-rsa SHA256:xlqcusIXWGVZHjhv4HCW8mE5UfJi/rv6feiIL5sL9kE
    debug1: private host key #1: ssh-rsa SHA256:HkcubZ7yV//gGxmHhOnB72gdy0nWnlNkkgBkwMHS9t4

Also note that host key algorithms has duplicate strings. This probably should
not be happening:

    debug2: host key algorithms: rsa-sha2-512,rsa-sha2-256,ssh-rsa,rsa-sha2-512,rsa-sha2-256,ssh-rsa [preauth]

Connect and accept the key

    $ ssh user@localhost -p 23
    The authenticity of host '[localhost]:23 ([127.0.0.1]:23)' can't be established.
    RSA key fingerprint is SHA256:xlqcusIXWGVZHjhv4HCW8mE5UfJi/rv6feiIL5sL9kE.
    Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
    Warning: Permanently added '[localhost]:23' (RSA) to the list of known hosts.
    user@localhost's password:

Reconnect to verify that the key is known:

    $ ssh user@localhost -p 23
    user@localhost's password:

Now rerurn sshd but swap the two host keys, and try to connect:

    $ `which sshd` -ddd -p 23 \
          -oHostKey=/etc/ssh/ssh_host_rsa_key_2 \
          -oHostKey=/etc/ssh/ssh_host_rsa_key 

    $ ssh user@localhost -p 23
    @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
    @    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
    @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
    IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
    Someone could be eavesdropping on you right now (man-in-the-middle attack)!
    It is also possible that a host key has just been changed.
    The fingerprint for the RSA key sent by the remote host is
    SHA256:HkcubZ7yV//gGxmHhOnB72gdy0nWnlNkkgBkwMHS9t4.
    Please contact your system administrator.
    Add correct host key in /home/user/.ssh/known_hosts to get rid of this message.
    Offending RSA key in /home/user/.ssh/known_hosts:1
    RSA host key for [localhost]:23 has changed and you have requested strict checking.
    Host key verification failed.

Also note the output of ssh-keyscan (rerun sshd wihout -d's)—it only includes
the first key:

    $ `which sshd` -p 23 \
          -oHostKey=/etc/ssh/ssh_host_rsa_key_2 \
          -oHostKey=/etc/ssh/ssh_host_rsa_key 
    $ ssh-keyscan -p 23 localhost
    # localhost:23 SSH-2.0-OpenSSH_8.4
    [localhost]:23 ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABgQC2fitD0wgrjJNzlTeVjLH8KWCkZMW19BoRtiy64WTxGfADZugofpzgjk5+MWD+IQLWTsFeuuNU8ygwAvY9l2EfAC88U2mXbAWYRpkKrm9GWEja3d2mrEx3caRNGwhk6bG4YO+nid9KbdgpYzJp06EQG/DSIcvdohW8qwQJc0Of6l6j0Kam+p8NjKVkbXeJ7L//n52TTGjqfnydqDRk1IDq/2hf2sS88rYZ6PA4UrT0l1k/jWhLyKp4YL2p5dzgv9fbnn7LIhZhNhTugyjtZQdI5sxgtbqX13GSfOtWF811wlwuiDbDDWG69TmueKPnBUj9MQY4KILrw+Y/agLa6b9MMIrdj/ahYRfR9/TVYWQ4zsBmmmuqN4QiaRGvxaP24pYBeGvL6aU4YhKIFln89ENS9NQvCFtAX315OcnFOY+Xq6bGpGiAdess4a01O5GJzO4ePFDXZgRZlwoIwVC/edk+tl8VwQ9WxswuRsb4mq/mBGUZNfyjlkI2gu3TnZd0JM8=
    # localhost:23 SSH-2.0-OpenSSH_8.4
    # localhost:23 SSH-2.0-OpenSSH_8.4
    # localhost:23 SSH-2.0-OpenSSH_8.4
    # localhost:23 SSH-2.0-OpenSSH_8.4    

In the case of different ECDSA keys, the behavior is similar. However, in this
case it is possible to connect by demanding the specific host key algorithm:

    $ rm ~/.ssh/known_hosts
    $ `which sshd` -p 23 \
          -oHostKey=/etc/ssh/ssh_host_ecdsa_256 \
          -oHostKey=/etc/ssh/ssh_host_ecdsa_521
    $ ssh-keyscan -p 23 localhost
    # localhost:23 SSH-2.0-OpenSSH_8.4
    # localhost:23 SSH-2.0-OpenSSH_8.4
    [localhost]:23 ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBL+Lcu52+K6lal94JOmPItpyMiqL57VrWZ1fmX9ntom+RiJahg8dRMR8dCxtUdo8782LwbH0uYWj/iaGh4DMJRg=
    # localhost:23 SSH-2.0-OpenSSH_8.4
    # localhost:23 SSH-2.0-OpenSSH_8.4
    # localhost:23 SSH-2.0-OpenSSH_8.4
    $ ssh user@localhost -p 23 -oHostKeyAlgorithms=ecdsa-sha2-nistp256
    The authenticity of host '[localhost]:23 ([127.0.0.1]:23)' can't be established.
    ECDSA key fingerprint is SHA256:TsMF+1PrXvdV9XNfrN3oYMvlL6sUc4koxtX8JekLBIY.
    Are you sure you want to continue connecting (yes/no/[fingerprint])? ^C
    $ ssh user@localhost -p 23 -oHostKeyAlgorithms=ecdsa-sha2-nistp521
    The authenticity of host '[localhost]:23 ([127.0.0.1]:23)' can't be established.
    ECDSA key fingerprint is SHA256:Egg8iKcjEXSAUuzn/fLEOniOzB6BNXaXzd52FPQxYr0.