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.)