openssh unix dev - Sep 2020 - ssh-ed25519 and ecdsa-sha2-nistp256 host keys

Hello.

I am running OpenSSH 7.9p1 on my client and server. ssh-keyscan shows
the server has ssh-rsa, ssh-ed25519, and ecdsa-sha2-nistp256 host
keys. My /etc/ssh/ssh_known_hosts file contains the server's
ssh-ed25519 host key. When I try to SSH to the server I get this
error:


@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 ECDSA key sent by the remote host is
SHA256:{redacted}.
Please contact your system administrator.
Add correct host key in /home/ryantm/.ssh/known_hosts to get rid of
this message.
Offending ED25519 key in /etc/ssh/ssh_known_hosts:64
ECDSA host key for HOST has changed and you have requested strict checking.
Host key verification failed.


If I add `HostKeyAlgorithms -ecdsa-sha2-nistp256` to my SSH config
file it connects fine. If I order ssh-ed25519 before ecdsa in the
HostKeyAlgorithms it works fine (however, it then breaks if I only
have the ecdsa key in the known_hosts file.).

It seems like there is some equivalence of ssh-ed25519 and
ecdsa-sha2-nistp256 host keys.

I was expecting OpenSSH to look through all the host keys to find one
that matched my known_hosts entry. Is that an invalid expectation?

Do I need to add every host key to the known_hosts file to reliably connect?

Am I missing some configuration option that will make OpenSSH treat
these host keys distinctly?

Sincerely,
Ryan Mulligan

On Tue, 15 Sep 2020, Ryan Mulligan wrote:
> Hello.
> 
> I am running OpenSSH 7.9p1 on my client and server. ssh-keyscan shows
> the server has ssh-rsa, ssh-ed25519, and ecdsa-sha2-nistp256 host
> keys. My /etc/ssh/ssh_known_hosts file contains the server's
> ssh-ed25519 host key. When I try to SSH to the server I get this
> error:
> 
> 
> @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
> @    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 ECDSA key sent by the remote host is
> SHA256:{redacted}.
> Please contact your system administrator.
> Add correct host key in /home/ryantm/.ssh/known_hosts to get rid of
> this message.
> Offending ED25519 key in /etc/ssh/ssh_known_hosts:64
> ECDSA host key for HOST has changed and you have requested strict checking.
> Host key verification failed.
Can you share a debug trace from a connection that shows this error?
"ssh -vvv user at host"

-d

Here you go:

OpenSSH_7.9p1, OpenSSL 1.1.1d  10 Sep 2019
debug1: Reading configuration data /home/ryantm/.ssh/config
debug1: /home/ryantm/.ssh/config line 4: Applying options for *
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 13: Applying options for *
debug2: resolving "{REDACTED}" port 22
debug2: ssh_connect_direct
debug1: Connecting to {REDACTED} [{REDACTED}] port 22.
debug2: fd 3 setting O_NONBLOCK
debug1: fd 3 clearing O_NONBLOCK
debug1: Connection established.
debug3: timeout: 982 ms remain after connect
debug1: identity file /home/ryantm/.ssh/id_ed25519 type 3
debug1: identity file /home/ryantm/.ssh/id_ed25519-cert type -1
debug1: identity file /home/ryantm/.ssh/id_rsa type 0
debug1: identity file /home/ryantm/.ssh/id_rsa-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_7.9
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.9
debug1: match: OpenSSH_7.9 pat OpenSSH* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to {REDACTED}:22 as 'ryantm'
debug3: send packet: type 20
debug1: SSH2_MSG_KEXINIT sent
debug3: receive packet: type 20
debug1: SSH2_MSG_KEXINIT received
debug2: local client KEXINIT proposal
debug2: KEX algorithms:
curve25519-sha256,curve25519-sha256 at
libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1,ext-info-c
debug2: host key algorithms:
ecdsa-sha2-nistp256-cert-v01 at openssh.com,ecdsa-sha2-nistp384-cert-v01 at
openssh.com,ecdsa-sha2-nistp521-cert-v01 at openssh.com,ssh-ed25519-cert-v01 at
openssh.com,rsa-sha2-512-cert-v01 at openssh.com,rsa-sha2-256-cert-v01 at
openssh.com,ssh-rsa-cert-v01 at
openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa,ssh-dss
debug2: ciphers ctos:
chacha20-poly1305 at openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm at
openssh.com,aes256-gcm at openssh.com
debug2: ciphers stoc:
chacha20-poly1305 at openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm at
openssh.com,aes256-gcm at openssh.com
debug2: MACs ctos:
umac-64-etm at openssh.com,umac-128-etm at openssh.com,hmac-sha2-256-etm at
openssh.com,hmac-sha2-512-etm at openssh.com,hmac-sha1-etm at
openssh.com,umac-64 at openssh.com,umac-128 at
openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc:
umac-64-etm at openssh.com,umac-128-etm at openssh.com,hmac-sha2-256-etm at
openssh.com,hmac-sha2-512-etm at openssh.com,hmac-sha1-etm at
openssh.com,umac-64 at openssh.com,umac-128 at
openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,zlib at openssh.com,zlib
debug2: compression stoc: none,zlib at openssh.com,zlib
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug2: peer server KEXINIT proposal
debug2: KEX algorithms:
curve25519-sha256 at libssh.org,diffie-hellman-group-exchange-sha256
debug2: host key algorithms:
rsa-sha2-512,rsa-sha2-256,ssh-rsa,ecdsa-sha2-nistp256,ssh-ed25519
debug2: ciphers ctos:
chacha20-poly1305 at openssh.com,aes256-gcm at openssh.com,aes128-gcm at
openssh.com,aes256-ctr,aes192-ctr,aes128-ctr
debug2: ciphers stoc:
chacha20-poly1305 at openssh.com,aes256-gcm at openssh.com,aes128-gcm at
openssh.com,aes256-ctr,aes192-ctr,aes128-ctr
debug2: MACs ctos:
hmac-sha2-512-etm at openssh.com,hmac-sha2-256-etm at openssh.com,umac-128-etm
at openssh.com,hmac-sha2-512,hmac-sha2-256,umac-128 at openssh.com
debug2: MACs stoc:
hmac-sha2-512-etm at openssh.com,hmac-sha2-256-etm at openssh.com,umac-128-etm
at openssh.com,hmac-sha2-512,hmac-sha2-256,umac-128 at openssh.com
debug2: compression ctos: none,zlib at openssh.com
debug2: compression stoc: none,zlib at openssh.com
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug1: kex: algorithm: curve25519-sha256 at libssh.org
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: chacha20-poly1305 at openssh.com MAC:
<implicit> compression: none
debug1: kex: client->server cipher: chacha20-poly1305 at openssh.com MAC:
<implicit> compression: none
debug3: send packet: type 30
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug3: receive packet: type 31
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:{REDACTED}
debug3: hostkeys_foreach: reading file "/home/ryantm/.ssh/known_hosts"
debug3: hostkeys_foreach: reading file "/etc/ssh/ssh_known_hosts"
debug3: record_hostkey: found key type ED25519 in file
/etc/ssh/ssh_known_hosts:64
debug3: load_hostkeys: loaded 1 keys from {REDACTED}
debug3: hostkeys_foreach: reading file "/home/ryantm/.ssh/known_hosts"
debug3: hostkeys_foreach: reading file "/etc/ssh/ssh_known_hosts"
debug3: record_hostkey: found key type ED25519 in file
/etc/ssh/ssh_known_hosts:64
debug3: load_hostkeys: loaded 1 keys from {REDACTED}
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 ECDSA key sent by the remote host is
SHA256:{REDACTED}
Please contact your system administrator.
Add correct host key in /home/ryantm/.ssh/known_hosts to get rid of
this message.
Offending ED25519 key in /etc/ssh/ssh_known_hosts:64
ECDSA host key for {REDACTED} has changed and you have requested
strict checking.
Host key verification failed.


The relevant part of my .ssh/config file is


Host *
IdentityFile ~/.ssh/id_ed25519
IdentityFile ~/.ssh/id_rsa


The relevant part of my /etc/ssh/ssh_config is:


Host *
AddressFamily inet
PubkeyAcceptedKeyTypes +ssh-dss
HostKeyAlgorithms +ssh-dss


- Ryan

On Tue, Sep 15, 2020 at 11:25 PM Damien Miller <djm at mindrot.org>
wrote:
>
> On Tue, 15 Sep 2020, Ryan Mulligan wrote:
>
> > Hello.
> >
> > I am running OpenSSH 7.9p1 on my client and server. ssh-keyscan shows
> > the server has ssh-rsa, ssh-ed25519, and ecdsa-sha2-nistp256 host
> > keys. My /etc/ssh/ssh_known_hosts file contains the server's
> > ssh-ed25519 host key. When I try to SSH to the server I get this
> > error:
> >
> >
> > @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
> > @    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 ECDSA key sent by the remote host is
> > SHA256:{redacted}.
> > Please contact your system administrator.
> > Add correct host key in /home/ryantm/.ssh/known_hosts to get rid of
> > this message.
> > Offending ED25519 key in /etc/ssh/ssh_known_hosts:64
> > ECDSA host key for HOST has changed and you have requested strict
checking.
> > Host key verification failed.
>
> Can you share a debug trace from a connection that shows this error?
> "ssh -vvv user at host"
>
> -d