Is it possible for an SSH MITM to attack only if the key isn't in the known_hosts?

Question

I was trying to connect a server using a different port when the network seemed too slow. It gives an ECDSA key, while the previous key in the known_hosts is RSA. I refused to continue the connection and tried more times using both ports, and never got a warning. Finally I connected to the server using the original port, and found that the server doesn't have any ECDSA keys.

It may just be some sort of DNS error or gateway error. But is it possible to be used in an attack? Some careless new users may get their servers compromised, and other users with the key already in known_hosts may never notice the attack has happened.

And if it is used in an attack, would it be safer to use public key authentication instead of a password?

Here is my theory for the attack:

The attacker firstly scans the server to make sure it doesn't have an ECDSA key. If a client tries to connect without specifying the algorithm, it says it only has the ECDSA key. If instead the client choose to use RSA, the attacker can redirect the connection to the real server without being noticed.

If the redirection is impossible, the attacker may try to make the network apparently very unstable, and finally disconnects before sending the key. Since it never sent a fake key, the user never get the warning that the server key is changed.

They may also set a small probability to just let the user connect to the real server, so they are unlikely to investigate this problem. And they can add the ECDSA key to the real server if the attack is successful, to pretend that the attack never happened.

More specifically, is the algorithm selection part done before verifying the server key, and does it work in a way that may leak the known_hosts status without a warning?

An alternative theory would be an attacker is only intercepting the traffic on specific port. But I'll be able to confirm only if this problem appears again later.

Edit: It turned out to be some very weird server configuration. (The virtual machine get cloned by someone with the privilege, and one of them has upgraded to have an ECDSA key. It was swapped with another when I connect.)

Answer 1

First of all, the answer depends on your SSH client. Let's assume you are using latest OpenSSH client. The SSH2 protocol starts like this:

Client -> Server: Initiate connection, send client software version + SSH version
Server -> Client: Server software version and SSH version
Client -> Server: Client supported algorithms
Server -> Client: Server supported algorithms
Client -> Server: Diffie-Hellman key exchange init
Server -> Client: Diffie-Hellman parameters and server key!

Let's say known_hosts contains the known good RSA key, but the server sent an ECDSA key. OpenSSH detects a key change!

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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
78:16:03:b0:88:c3:9b:a7:7d:34:87:a5:8b:36:f1:4f.
Please contact your system administrator.
Add correct host key in /root/.ssh/known_hosts to get rid of this message.
Offending RSA key in /root/.ssh/known_hosts:1
ECDSA host key for 127.0.0.1 has changed and you have requested strict checking.
Host key verification failed.

Now the question is: Is StrictHostKeyChecking set to yes in your SSH config?

And last but not least, if you are worried about being hacked by an SSH MitM, I suggest you authenticate with SSH keys instead of using passwords. It is much more secure, and your password is safe (as long as you don't use the password for sudo :) or something else).

Answer 2

For the simple attack on Trust On First Use host keys in SSH, the attack works only if the client doesn't yet have a key for the host, i.e. on "First Use".

But the more general "Man In The Middle attack" term applies to more interesting attacks like forging digital signatures. This is now possible against the venerable "rsa-sha" signature from the original SSH RFCs, at a modest cost under $50K. So a man-in-the-middle attack against an SSH client connecting to an SSH host, not on first use, with the host key in known_hosts file is possible. That is why openssh 8.3 deprecate that algorithm. It should not be used, everyone should migrate to something better (ed25519 is a good choice).